1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation
3 This file is part of libgcj.
5 This software is copyrighted work licensed under the terms of the
6 Libgcj License. Please consult the file "LIBGCJ_LICENSE" for
9 /* Written by Tom Tromey <tromey@redhat.com> */
11 /* Uncomment this to enable debugging output. */
12 /* #define VERIFY_DEBUG */
18 /* Hack to work around namespace pollution from java-tree.h. */
23 #endif /* VERIFY_DEBUG */
25 /* This is used to mark states which are not scheduled for
27 #define INVALID_STATE ((state *) -1)
31 debug_print (const char *fmt, ...)
35 vfprintf (stderr, fmt, ap);
40 debug_print (const char *fmt ATTRIBUTE_UNUSED, ...)
43 #endif /* VERIFY_DEBUG */
46 static void debug_print (const char *fmt, ...)
47 __attribute__ ((format (printf, 1, 2)));
50 debug_print (const char *fmt, ...)
55 vfprintf (stderr, fmt, ap);
57 #endif /* VERIFY_DEBUG */
61 /* This started as a fairly ordinary verifier, and for the most part
62 it remains so. It works in the obvious way, by modeling the effect
63 of each opcode as it is encountered. For most opcodes, this is a
64 straightforward operation.
66 This verifier does not do type merging. It used to, but this
67 results in difficulty verifying some relatively simple code
68 involving interfaces, and it pushed some verification work into the
71 Instead of merging reference types, when we reach a point where two
72 flows of control merge, we simply keep the union of reference types
73 from each branch. Then, when we need to verify a fact about a
74 reference on the stack (e.g., that it is compatible with the
75 argument type of a method), we check to ensure that all possible
76 types satisfy the requirement.
78 Another area this verifier differs from the norm is in its handling
79 of subroutines. The JVM specification has some confusing things to
80 say about subroutines. For instance, it makes claims about not
81 allowing subroutines to merge and it rejects recursive subroutines.
82 For the most part these are red herrings; we used to try to follow
83 these things but they lead to problems. For example, the notion of
84 "being in a subroutine" is not well-defined: is an exception
85 handler in a subroutine? If you never execute the `ret' but
86 instead `goto 1' do you remain in the subroutine?
88 For clarity on what is really required for type safety, read
89 "Simple Verification Technique for Complex Java Bytecode
90 Subroutines" by Alessandro Coglio. Among other things this paper
91 shows that recursive subroutines are not harmful to type safety.
92 We implement something similar to what he proposes. Note that this
93 means that this verifier will accept code that is rejected by some
96 For those not wanting to read the paper, the basic observation is
97 that we can maintain split states in subroutines. We maintain one
98 state for each calling `jsr'. In other words, we re-verify a
99 subroutine once for each caller, using the exact types held by the
100 callers (as opposed to the old approach of merging types and
101 keeping a bitmap registering what did or did not change). This
102 approach lets us continue to verify correctly even when a
103 subroutine is exited via `goto' or `athrow' and not `ret'.
105 In some other areas the JVM specification is (mildly) incorrect,
106 so we diverge. For instance, you cannot
107 violate type safety by allocating an object with `new' and then
108 failing to initialize it, no matter how one branches or where one
109 stores the uninitialized reference. See "Improving the official
110 specification of Java bytecode verification" by Alessandro Coglio.
112 Note that there's no real point in enforcing that padding bytes or
113 the mystery byte of invokeinterface must be 0, but we do that
116 The verifier is currently neither completely lazy nor eager when it
117 comes to loading classes. It tries to represent types by name when
118 possible, and then loads them when it needs to verify a fact about
119 the type. Checking types by name is valid because we only use
120 names which come from the current class' constant pool. Since all
121 such names are looked up using the same class loader, there is no
122 danger that we might be fooled into comparing different types with
125 In the future we plan to allow for a completely lazy mode of
126 operation, where the verifier will construct a list of type
127 assertions to be checked later.
129 Some test cases for the verifier live in the "verify" module of the
130 Mauve test suite. However, some of these are presently
131 (2004-01-20) believed to be incorrect. (More precisely the notion
132 of "correct" is not well-defined, and this verifier differs from
133 others while remaining type-safe.) Some other tests live in the
136 This verifier is also written to be pluggable. This means that it
137 is intended for use in a variety of environments, not just libgcj.
138 As a result the verifier expects a number of type and method
139 declarations to be declared in "verify.h". The intent is that you
140 recompile the verifier for your particular environment. This
141 approach was chosen so that operations could be inlined in verify.h
144 See the verify.h that accompanies this copy of the verifier to see
145 what types, preprocessor defines, and functions must be declared.
146 The interface is ad hoc, but was defined so that it could be
147 implemented to connect to a pure C program.
150 #define FLAG_INSN_START 1
151 #define FLAG_BRANCH_TARGET 2
152 #define FLAG_INSN_SEEN 4
156 struct ref_intersection;
158 typedef struct state state;
159 typedef struct type type;
160 typedef struct ref_intersection ref_intersection;
162 /*typedef struct state_list state_list;*/
164 typedef struct state_list
167 struct state_list *next;
170 typedef struct vfy_string_list
173 struct vfy_string_list *next;
176 typedef struct verifier_context
178 /* The current PC. */
180 /* The PC corresponding to the start of the current instruction. */
183 /* The current state of the stack, locals, etc. */
184 state *current_state;
186 /* At each branch target we keep a linked list of all the states we
187 can process at that point. We'll only have multiple states at a
188 given PC if they both have different return-address types in the
189 same stack or local slot. This array is indexed by PC and holds
190 the list of all such states. */
193 /* We keep a linked list of all the states which we must reverify.
194 This is the head of the list. */
195 state *next_verify_state;
197 /* We keep some flags for each instruction. The values are the
198 FLAG_* constants defined above. This is an array indexed by PC. */
201 /* The bytecode itself. */
202 const unsigned char *bytecode;
203 /* The exceptions. */
204 vfy_exception *exception;
206 /* Defining class. */
207 vfy_jclass current_class;
209 vfy_method *current_method;
211 /* A linked list of utf8 objects we allocate. */
212 vfy_string_list *utf8_list;
214 /* A linked list of all ref_intersection objects we allocate. */
215 ref_intersection *isect_list;
218 /* The current verifier's state data. This is maintained by
219 {push/pop}_verifier_context to provide a shorthand form to access
220 the verification state. */
221 static GTY(()) verifier_context *vfr;
223 /* Local function declarations. */
224 bool type_initialized (type *t);
225 int ref_count_dimensions (ref_intersection *ref);
228 /* Create a new Utf-8 constant and return it. We do this to avoid
229 having our Utf-8 constants prematurely collected. */
231 make_utf8_const (const char *s, int len)
233 vfy_string val = vfy_make_string (s, len);
234 vfy_string_list *lu = vfy_alloc (sizeof (vfy_string_list));
236 lu->next = vfr->utf8_list;
244 verify_fail_pc (const char *s, int pc)
246 vfy_fail (s, pc, vfr->current_class, vfr->current_method);
250 verify_fail (const char *s)
252 verify_fail_pc (s, -1);
255 /* This enum holds a list of tags for all the different types we
256 need to handle. Reference types are treated specially by the
258 typedef enum type_val
262 /* The values for primitive types are chosen to correspond to values
263 specified to newarray. */
273 /* Used when overwriting second word of a double or long in the
274 local variables. Also used after merging local variable states
275 to indicate an unusable value. */
278 /* This is the second word of a two-word value, i.e., a double or
282 /* Everything after `reference_type' must be a reference type. */
285 uninitialized_reference_type
288 /* This represents a merged class type. Some verifiers (including
289 earlier versions of this one) will compute the intersection of
290 two class types when merging states. However, this loses
291 critical information about interfaces implemented by the various
292 classes. So instead we keep track of all the actual classes that
294 struct ref_intersection
296 /* Whether or not this type has been resolved. */
299 /* Actual type data. */
302 /* For a resolved reference type, this is a pointer to the class. */
304 /* For other reference types, this it the name of the class. */
308 /* Link to the next reference in the intersection. */
309 ref_intersection *ref_next;
311 /* This is used to keep track of all the allocated
312 ref_intersection objects, so we can free them.
313 FIXME: we should allocate these in chunks. */
314 ref_intersection *alloc_next;
317 static ref_intersection *
320 ref_intersection *new_ref =
321 (ref_intersection *) vfy_alloc (sizeof (ref_intersection));
323 new_ref->alloc_next = vfr->isect_list;
324 vfr->isect_list = new_ref;
328 static ref_intersection *
329 clone_ref (ref_intersection *dup)
331 ref_intersection *new_ref = make_ref ();
333 new_ref->is_resolved = dup->is_resolved;
334 new_ref->data = dup->data;
339 resolve_ref (ref_intersection *ref)
341 if (ref->is_resolved)
343 ref->data.klass = vfy_find_class (vfr->current_class, ref->data.name);
344 ref->is_resolved = true;
348 refs_equal (ref_intersection *ref1, ref_intersection *ref2)
350 if (! ref1->is_resolved && ! ref2->is_resolved
351 && vfy_strings_equal (ref1->data.name, ref2->data.name))
353 if (! ref1->is_resolved)
355 if (! ref2->is_resolved)
357 return ref1->data.klass == ref2->data.klass;
360 /* Merge REF1 type into REF2, returning the result. This will
361 return REF2 if all the classes in THIS already appear in
363 static ref_intersection *
364 merge_refs (ref_intersection *ref1, ref_intersection *ref2)
366 ref_intersection *tail = ref2;
367 for (; ref1 != NULL; ref1 = ref1->ref_next)
370 ref_intersection *iter;
371 for (iter = ref2; iter != NULL; iter = iter->ref_next)
373 if (refs_equal (ref1, iter))
382 ref_intersection *new_tail = clone_ref (ref1);
383 new_tail->ref_next = tail;
390 /* See if an object of type SOURCE can be assigned to an object of
391 type TARGET. This might resolve classes in one chain or the other. */
393 ref_compatible (ref_intersection *target, ref_intersection *source)
395 for (; target != NULL; target = target->ref_next)
397 ref_intersection *source_iter = source;
399 for (; source_iter != NULL; source_iter = source_iter->ref_next)
401 /* Avoid resolving if possible. */
402 if (! target->is_resolved
403 && ! source_iter->is_resolved
404 && vfy_strings_equal (target->data.name,
405 source_iter->data.name))
408 if (! target->is_resolved)
409 resolve_ref (target);
410 if (! source_iter->is_resolved)
411 resolve_ref (source_iter);
413 if (! vfy_is_assignable_from (target->data.klass,
414 source_iter->data.klass))
423 ref_isarray (ref_intersection *ref)
425 /* assert (ref_next == NULL); */
426 if (ref->is_resolved)
427 return vfy_is_array (ref->data.klass);
429 return vfy_string_bytes (ref->data.name)[0] == '[';
433 ref_isinterface (ref_intersection *ref)
435 /* assert (ref_next == NULL); */
436 if (! ref->is_resolved)
438 return vfy_is_interface (ref->data.klass);
442 ref_isabstract (ref_intersection *ref)
444 /* assert (ref_next == NULL); */
445 if (! ref->is_resolved)
447 return vfy_is_abstract (ref->data.klass);
451 ref_getclass (ref_intersection *ref)
453 if (! ref->is_resolved)
455 return ref->data.klass;
459 ref_count_dimensions (ref_intersection *ref)
462 if (ref->is_resolved)
464 vfy_jclass k = ref->data.klass;
465 while (vfy_is_array (k))
467 k = vfy_get_component_type (k);
473 const char *p = vfy_string_bytes (ref->data.name);
480 /* Return the type_val corresponding to a primitive signature
481 character. For instance `I' returns `int.class'. */
483 get_type_val_for_signature (char sig)
516 verify_fail ("invalid signature");
522 /* Return the type_val corresponding to a primitive class. */
524 get_type_val_for_primtype (vfy_jclass k)
526 return get_type_val_for_signature (vfy_get_primitive_char (k));
529 /* The `type' class is used to represent a single type in the verifier. */
535 /* For reference types, the representation of the type. */
536 ref_intersection *klass;
538 /* This is used in two situations.
540 First, when constructing a new object, it is the PC of the
541 `new' instruction which created the object. We use the special
542 value UNINIT to mean that this is uninitialized. The special
543 value SELF is used for the case where the current method is
544 itself the <init> method. the special value EITHER is used
545 when we may optionally allow either an uninitialized or
546 initialized reference to match.
548 Second, when the key is return_address_type, this holds the PC
549 of the instruction following the `jsr'. */
558 /* Basic constructor. */
562 t->key = unsuitable_type;
568 /* Make a new instance given the type tag. We assume a generic
569 `reference_type' means Object. */
571 init_type_from_tag (type *t, type_val k)
574 /* For reference_type, if KLASS==NULL then that means we are
575 looking for a generic object of any kind, including an
576 uninitialized reference. */
581 /* Make a type for the given type_val tag K. */
583 make_type (type_val k)
586 init_type_from_tag (&t, k);
590 /* Make a new instance given a class. */
592 init_type_from_class (type *t, vfy_jclass k)
594 t->key = reference_type;
595 t->klass = make_ref ();
596 t->klass->is_resolved = true;
597 t->klass->data.klass = k;
598 t->klass->ref_next = NULL;
603 make_type_from_class (vfy_jclass k)
606 init_type_from_class (&t, k);
611 init_type_from_string (type *t, vfy_string n)
613 t->key = reference_type;
614 t->klass = make_ref ();
615 t->klass->is_resolved = false;
616 t->klass->data.name = n;
617 t->klass->ref_next = NULL;
622 make_type_from_string (vfy_string n)
625 init_type_from_string (&t, n);
630 /* Make a new instance given the name of a class. */
633 key = reference_type;
634 klass = new ref_intersection (n, verifier);
638 /* Copy constructor. */
639 static type copy_type (type *t)
643 copy.klass = t->klass;
649 /* Promote a numeric type. */
651 vfy_promote_type (type *t)
653 if (t->key == boolean_type || t->key == char_type
654 || t->key == byte_type || t->key == short_type)
657 #define promote_type vfy_promote_type
659 /* Mark this type as the uninitialized result of `new'. */
661 type_set_uninitialized (type *t, int npc)
663 if (t->key == reference_type)
664 t->key = uninitialized_reference_type;
666 verify_fail ("internal error in type::uninitialized");
670 /* Mark this type as now initialized. */
672 type_set_initialized (type *t, int npc)
674 if (npc != UNINIT && t->pc == npc && t->key == uninitialized_reference_type)
676 t->key = reference_type;
681 /* Mark this type as a particular return address. */
682 static void type_set_return_address (type *t, int npc)
687 /* Return true if this type and type OTHER are considered
688 mergeable for the purposes of state merging. This is related
689 to subroutine handling. For this purpose two types are
690 considered unmergeable if they are both return-addresses but
691 have different PCs. */
693 type_state_mergeable_p (type *t1, type *t2)
695 return (t1->key != return_address_type
696 || t2->key != return_address_type
697 || t1->pc == t2->pc);
700 /* Return true if an object of type K can be assigned to a variable
701 of type T. Handle various special cases too. Might modify
702 T or K. Note however that this does not perform numeric
705 types_compatible (type *t, type *k)
707 /* Any type is compatible with the unsuitable type. */
708 if (k->key == unsuitable_type)
711 if (t->key < reference_type || k->key < reference_type)
712 return t->key == k->key;
714 /* The `null' type is convertible to any initialized reference
716 if (t->key == null_type)
717 return k->key != uninitialized_reference_type;
718 if (k->key == null_type)
719 return t->key != uninitialized_reference_type;
721 /* A special case for a generic reference. */
722 if (t->klass == NULL)
724 if (k->klass == NULL)
725 verify_fail ("programmer error in type::compatible");
727 /* Handle the special 'EITHER' case, which is only used in a
728 special case of 'putfield'. Note that we only need to handle
729 this on the LHS of a check. */
730 if (! type_initialized (t) && t->pc == EITHER)
732 /* If the RHS is uninitialized, it must be an uninitialized
734 if (! type_initialized (k) && k->pc != SELF)
737 else if (type_initialized (t) != type_initialized (k))
739 /* An initialized type and an uninitialized type are not
740 otherwise compatible. */
745 /* Two uninitialized objects are compatible if either:
746 * The PCs are identical, or
747 * One PC is UNINIT. */
748 if (type_initialized (t))
750 if (t->pc != k->pc && t->pc != UNINIT && k->pc != UNINIT)
755 return ref_compatible (t->klass, k->klass);
758 /* Return true if two types are equal. Only valid for reference
761 types_equal (type *t1, type *t2)
763 if ((t1->key != reference_type && t1->key != uninitialized_reference_type)
764 || (t2->key != reference_type
765 && t2->key != uninitialized_reference_type))
767 /* Only single-ref types are allowed. */
768 if (t1->klass->ref_next || t2->klass->ref_next)
770 return refs_equal (t1->klass, t2->klass);
774 type_isvoid (type *t)
776 return t->key == void_type;
780 type_iswide (type *t)
782 return t->key == long_type || t->key == double_type;
785 /* Return number of stack or local variable slots taken by this type. */
789 return type_iswide (t) ? 2 : 1;
793 type_isarray (type *t)
795 /* We treat null_type as not an array. This is ok based on the
796 current uses of this method. */
797 if (t->key == reference_type)
798 return ref_isarray (t->klass);
803 type_isnull (type *t)
805 return t->key == null_type;
809 type_isinterface (type *t)
811 if (t->key != reference_type)
813 return ref_isinterface (t->klass);
817 type_isabstract (type *t)
819 if (t->key != reference_type)
821 return ref_isabstract (t->klass);
824 /* Return the element type of an array. */
826 type_array_element (type *t)
831 if (t->key != reference_type)
832 verify_fail ("programmer error in type::element_type()");
834 k = vfy_get_component_type (ref_getclass (t->klass));
835 if (vfy_is_primitive (k))
836 init_type_from_tag (&et, get_type_val_for_primtype (k));
838 init_type_from_class (&et, k);
842 /* Return the array type corresponding to an initialized
843 reference. We could expand this to work for other kinds of
844 types, but currently we don't need to. */
846 type_to_array (type *t)
851 if (t->key != reference_type)
852 verify_fail ("internal error in type::to_array()");
854 k = ref_getclass (t->klass);
855 init_type_from_class (&at, vfy_get_array_class (k));
860 type_isreference (type *t)
862 return t->key >= reference_type;
866 type_get_pc (type *t)
872 type_initialized (type *t)
874 return t->key == reference_type || t->key == null_type;
879 type_isresolved (type *t)
881 return (t->key == reference_type
882 || t->key == null_type
883 || t->key == uninitialized_reference_type);
888 type_verify_dimensions (type *t, int ndims)
890 /* The way this is written, we don't need to check isarray(). */
891 if (t->key != reference_type)
892 verify_fail ("internal error in verify_dimensions:"
893 " not a reference type");
895 if (ref_count_dimensions (t->klass) < ndims)
896 verify_fail ("array type has fewer dimensions"
900 /* Merge OLD_TYPE into this. On error throw exception. Return
901 true if the merge caused a type change. */
903 merge_types (type *t, type *old_type, bool local_semantics)
905 bool changed = false;
906 bool refo = type_isreference (old_type);
907 bool refn = type_isreference (t);
910 if (old_type->key == null_type)
912 else if (t->key == null_type)
917 else if (type_initialized (t) != type_initialized (old_type))
918 verify_fail ("merging initialized and uninitialized types");
921 ref_intersection *merged;
922 if (! type_initialized (t))
925 t->pc = old_type->pc;
926 else if (old_type->pc == UNINIT)
928 else if (t->pc != old_type->pc)
929 verify_fail ("merging different uninitialized types");
932 merged = merge_refs (old_type->klass, t->klass);
933 if (merged != t->klass)
940 else if (refo || refn || t->key != old_type->key)
944 /* If we already have an `unsuitable' type, then we
945 don't need to change again. */
946 if (t->key != unsuitable_type)
948 t->key = unsuitable_type;
953 verify_fail ("unmergeable type");
965 case boolean_type: c = 'Z'; break;
966 case byte_type: c = 'B'; break;
967 case char_type: c = 'C'; break;
968 case short_type: c = 'S'; break;
969 case int_type: c = 'I'; break;
970 case long_type: c = 'J'; break;
971 case float_type: c = 'F'; break;
972 case double_type: c = 'D'; break;
973 case void_type: c = 'V'; break;
974 case unsuitable_type: c = '-'; break;
975 case return_address_type: c = 'r'; break;
976 case continuation_type: c = '+'; break;
977 case reference_type: c = 'L'; break;
978 case null_type: c = '@'; break;
979 case uninitialized_reference_type: c = 'U'; break;
981 debug_print ("%c", c);
983 #endif /* VERIFY_DEBUG */
985 /* This class holds all the state information we need for a given
989 /* The current top of the stack, in terms of slots. */
991 /* The current depth of the stack. This will be larger than
992 STACKTOP when wide types are on the stack. */
996 /* The local variables. */
998 /* We keep track of the type of `this' specially. This is used to
999 ensure that an instance initializer invokes another initializer
1000 on `this' before returning. We must keep track of this
1001 specially because otherwise we might be confused by code which
1002 assigns to locals[0] (overwriting `this') and then returns
1003 without really initializing. */
1006 /* The PC for this state. This is only valid on states which are
1007 permanently attached to a given PC. For an object like
1008 `current_state', which is used transiently, this has no
1011 /* We keep a linked list of all states requiring reverification.
1012 If this is the special value INVALID_STATE then this state is
1013 not on the list. NULL marks the end of the linked list. */
1017 /* NO_NEXT is the PC value meaning that a new state must be
1018 acquired from the verification list. */
1023 init_state (state *s)
1027 s->next = INVALID_STATE;
1032 init_state_with_stack (state *s, int max_stack, int max_locals)
1037 s->stack = (type *) vfy_alloc (max_stack * sizeof (type));
1038 for (i = 0; i < max_stack; ++i)
1039 init_type_from_tag (&s->stack[i], unsuitable_type);
1040 s->locals = (type *) vfy_alloc (max_locals * sizeof (type));
1041 for (i = 0; i < max_locals; ++i)
1042 init_type_from_tag (&s->locals[i], unsuitable_type);
1043 init_type_from_tag (&s->this_type, unsuitable_type);
1045 s->next = INVALID_STATE;
1049 copy_state (state *s, state *copy, int max_stack, int max_locals)
1052 s->stacktop = copy->stacktop;
1053 s->stackdepth = copy->stackdepth;
1054 for (i = 0; i < max_stack; ++i)
1055 s->stack[i] = copy->stack[i];
1056 for (i = 0; i < max_locals; ++i)
1057 s->locals[i] = copy->locals[i];
1059 s->this_type = copy->this_type;
1060 /* Don't modify `next' or `pc'. */
1064 copy_state_with_stack (state *s, state *orig, int max_stack, int max_locals)
1066 init_state_with_stack (s, max_stack, max_locals);
1067 copy_state (s, orig, max_stack, max_locals);
1070 /* Allocate a new state, copying ORIG. */
1072 make_state_copy (state *orig, int max_stack, int max_locals)
1074 state *s = vfy_alloc (sizeof (state));
1075 copy_state_with_stack (s, orig, max_stack, max_locals);
1080 make_state (int max_stack, int max_locals)
1082 state *s = vfy_alloc (sizeof (state));
1083 init_state_with_stack (s, max_stack, max_locals);
1089 free_state (state *s)
1091 if (s->stack != NULL)
1092 vfy_free (s->stack);
1093 if (s->locals != NULL)
1094 vfy_free (s->locals);
1099 void *operator new[] (size_t bytes)
1101 return vfy_alloc (bytes);
1104 void operator delete[] (void *mem)
1109 void *operator new (size_t bytes)
1111 return vfy_alloc (bytes);
1114 void operator delete (void *mem)
1120 /* Modify this state to reflect entry to an exception handler. */
1122 state_set_exception (state *s, type *t, int max_stack)
1128 for (i = s->stacktop; i < max_stack; ++i)
1129 init_type_from_tag (&s->stack[i], unsuitable_type);
1133 state_get_pc (state *s)
1140 set_pc (state *s, int npc)
1146 /* Merge STATE_OLD into this state. Destructively modifies this
1147 state. Returns true if the new state was in fact changed.
1148 Will throw an exception if the states are not mergeable. */
1150 merge_states (state *s, state *state_old, int max_locals)
1153 bool changed = false;
1155 /* Special handling for `this'. If one or the other is
1156 uninitialized, then the merge is uninitialized. */
1157 if (type_initialized (&s->this_type))
1158 s->this_type = state_old->this_type;
1161 if (state_old->stacktop != s->stacktop) /* FIXME stackdepth instead? */
1162 verify_fail ("stack sizes differ");
1163 for (i = 0; i < state_old->stacktop; ++i)
1165 if (merge_types (&s->stack[i], &state_old->stack[i], false))
1169 /* Merge local variables. */
1170 for (i = 0; i < max_locals; ++i)
1172 if (merge_types (&s->locals[i], &state_old->locals[i], true))
1179 /* Ensure that `this' has been initialized. */
1181 state_check_this_initialized (state *s)
1183 if (type_isreference (&s->this_type) && ! type_initialized (&s->this_type))
1184 verify_fail ("`this' is uninitialized");
1187 /* Set type of `this'. */
1189 state_set_this_type (state *s, type *k)
1194 /* Mark each `new'd object we know of that was allocated at PC as
1197 state_set_initialized (state *s, int pc, int max_locals)
1200 for (i = 0; i < s->stacktop; ++i)
1201 type_set_initialized (&s->stack[i], pc);
1202 for (i = 0; i < max_locals; ++i)
1203 type_set_initialized (&s->locals[i], pc);
1204 type_set_initialized (&s->this_type, pc);
1207 /* This tests to see whether two states can be considered "merge
1208 compatible". If both states have a return-address in the same
1209 slot, and the return addresses are different, then they are not
1210 compatible and we must not try to merge them. */
1212 state_mergeable_p (state *s, state *other, int max_locals)
1217 /* This is tricky: if the stack sizes differ, then not only are
1218 these not mergeable, but in fact we should give an error, as
1219 we've found two execution paths that reach a branch target
1220 with different stack depths. FIXME stackdepth instead? */
1221 if (s->stacktop != other->stacktop)
1222 verify_fail ("stack sizes differ");
1224 for (i = 0; i < s->stacktop; ++i)
1225 if (! type_state_mergeable_p (&s->stack[i], &other->stack[i]))
1227 for (i = 0; i < max_locals; ++i)
1228 if (! type_state_mergeable_p (&s->locals[i], &other->locals[i]))
1234 state_reverify (state *s)
1236 if (s->next == INVALID_STATE)
1238 s->next = vfr->next_verify_state;
1239 vfr->next_verify_state = s;
1245 debug_print_state (state *s, const char *leader, int pc, int max_stack,
1249 debug_print ("%s [%4d]: [stack] ", leader, pc);
1250 for (i = 0; i < s->stacktop; ++i)
1251 type_print (&s->stack[i]);
1252 for (; i < max_stack; ++i)
1254 debug_print (" [local] ");
1255 for (i = 0; i < max_locals; ++i)
1256 type_print (&s->locals[i]);
1257 debug_print (" | %p\n", s);
1261 debug_print_state (state *s ATTRIBUTE_UNUSED,
1262 const char *leader ATTRIBUTE_UNUSED,
1263 int pc ATTRIBUTE_UNUSED, int max_stack ATTRIBUTE_UNUSED,
1264 int max_locals ATTRIBUTE_UNUSED)
1267 #endif /* VERIFY_DEBUG */
1273 state *s = vfr->current_state;
1274 if (s->stacktop <= 0)
1275 verify_fail ("stack empty");
1276 r = s->stack[--s->stacktop];
1277 s->stackdepth -= type_depth (&r);
1278 if (s->stackdepth < 0)
1279 verify_fail_pc ("stack empty", vfr->start_PC);
1286 type r = pop_raw ();
1287 if (type_iswide (&r))
1288 verify_fail ("narrow pop of wide type");
1293 vfy_pop_type_t (type match)
1296 vfy_promote_type (&match);
1298 if (! types_compatible (&match, &t))
1299 verify_fail ("incompatible type on stack");
1304 vfy_pop_type (type_val match)
1306 type t = make_type (match);
1307 return vfy_pop_type_t (t);
1310 #define pop_type vfy_pop_type
1311 #define pop_type_t vfy_pop_type_t
1313 /* Pop a reference which is guaranteed to be initialized. MATCH
1314 doesn't have to be a reference type; in this case this acts like
1317 pop_init_ref_t (type match)
1319 type t = pop_raw ();
1320 if (type_isreference (&t) && ! type_initialized (&t))
1321 verify_fail ("initialized reference required");
1322 else if (! types_compatible (&match, &t))
1323 verify_fail ("incompatible type on stack");
1328 pop_init_ref (type_val match)
1330 type t = make_type (match);
1331 return pop_init_ref_t (t);
1334 /* Pop a reference type or a return address. */
1336 pop_ref_or_return (void)
1338 type t = pop_raw ();
1339 if (! type_isreference (&t) && t.key != return_address_type)
1340 verify_fail ("expected reference or return address on stack");
1345 vfy_push_type_t (type t)
1348 state *s = vfr->current_state;
1349 /* If T is a numeric type like short, promote it to int. */
1352 depth = type_depth (&t);
1354 if (s->stackdepth + depth > vfr->current_method->max_stack)
1355 verify_fail ("stack overflow");
1356 s->stack[s->stacktop++] = t;
1357 s->stackdepth += depth;
1361 vfy_push_type (type_val tval)
1363 type t = make_type (tval);
1364 vfy_push_type_t (t);
1367 #define push_type vfy_push_type
1368 #define push_type_t vfy_push_type_t
1371 set_variable (int index, type t)
1374 state *s = vfr->current_state;
1375 /* If T is a numeric type like short, promote it to int. */
1378 depth = type_depth (&t);
1379 if (index > vfr->current_method->max_locals - depth)
1380 verify_fail ("invalid local variable");
1381 s->locals[index] = t;
1384 init_type_from_tag (&s->locals[index + 1], continuation_type);
1385 if (index > 0 && type_iswide (&s->locals[index - 1]))
1386 init_type_from_tag (&s->locals[index - 1], unsuitable_type);
1390 get_variable_t (int index, type *t)
1392 state *s = vfr->current_state;
1393 int depth = type_depth (t);
1394 if (index > vfr->current_method->max_locals - depth)
1395 verify_fail ("invalid local variable");
1396 if (! types_compatible (t, &s->locals[index]))
1397 verify_fail ("incompatible type in local variable");
1400 type cont = make_type (continuation_type);
1401 if (! types_compatible (&s->locals[index + 1], &cont))
1402 verify_fail ("invalid local variable");
1404 return s->locals[index];
1408 get_variable (int index, type_val v)
1410 type t = make_type (v);
1411 return get_variable_t (index, &t);
1414 /* Make sure ARRAY is an array type and that its elements are
1415 compatible with type ELEMENT. Returns the actual element type. */
1417 require_array_type_t (type array, type element)
1420 /* An odd case. Here we just pretend that everything went ok. If
1421 the requested element type is some kind of reference, return
1422 the null type instead. */
1423 if (type_isnull (&array))
1424 return type_isreference (&element) ? make_type (null_type) : element;
1426 if (! type_isarray (&array))
1427 verify_fail ("array required");
1429 t = type_array_element (&array);
1430 if (! types_compatible (&element, &t))
1432 /* Special case for byte arrays, which must also be boolean
1435 if (element.key == byte_type)
1437 type e2 = make_type (boolean_type);
1438 ok = types_compatible (&e2, &t);
1441 verify_fail ("incompatible array element type");
1444 /* Return T and not ELEMENT, because T might be specialized. */
1449 require_array_type (type array, type_val element)
1451 type t = make_type (element);
1452 return require_array_type_t (array, t);
1458 if (vfr->PC >= vfr->current_method->code_length)
1459 verify_fail ("premature end of bytecode");
1460 return (jint) vfr->bytecode[vfr->PC++] & 0xff;
1466 jint b1 = get_byte ();
1467 jint b2 = get_byte ();
1468 return (jint) ((b1 << 8) | b2) & 0xffff;
1474 signed char b1 = (signed char) get_byte ();
1475 jint b2 = get_byte ();
1476 jshort s = (b1 << 8) | b2;
1483 jint b1 = get_byte ();
1484 jint b2 = get_byte ();
1485 jint b3 = get_byte ();
1486 jint b4 = get_byte ();
1487 jword result = (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
1488 /* In the compiler, 'jint' might have more than 32 bits, so we must
1490 return WORD_TO_INT (result);
1494 compute_jump (int offset)
1496 int npc = vfr->start_PC + offset;
1497 if (npc < 0 || npc >= vfr->current_method->code_length)
1498 verify_fail_pc ("branch out of range", vfr->start_PC);
1502 /* Add a new state to the state list at NPC. */
1504 add_new_state (int npc, state *old_state)
1507 vfy_method *current_method = vfr->current_method;
1508 state *new_state = make_state_copy (old_state, current_method->max_stack,
1509 current_method->max_locals);
1510 debug_print ("== New state in add_new_state\n");
1511 debug_print_state (new_state, "New", npc, current_method->max_stack,
1512 current_method->max_locals);
1514 nlink = vfy_alloc (sizeof (state_list));
1515 nlink->val = new_state;
1516 nlink->next = vfr->states[npc];
1517 vfr->states[npc] = nlink;
1518 new_state->pc = npc;
1522 /* Merge the indicated state into the state at the branch target and
1523 schedule a new PC if there is a change. NPC is the PC of the
1524 branch target, and FROM_STATE is the state at the source of the
1525 branch. This method returns true if the destination state
1526 changed and requires reverification, false otherwise. */
1528 merge_into (int npc, state *from_state)
1530 /* Iterate over all target states and merge our state into each,
1531 if applicable. FIXME one improvement we could make here is
1532 "state destruction". Merging a new state into an existing one
1533 might cause a return_address_type to be merged to
1534 unsuitable_type. In this case the resulting state may now be
1535 mergeable with other states currently held in parallel at this
1536 location. So in this situation we could pairwise compare and
1537 reduce the number of parallel states. */
1539 bool applicable = false;
1540 for (iter = vfr->states[npc]; iter != NULL; iter = iter->next)
1542 state *new_state = iter->val;
1543 vfy_method *current_method = vfr->current_method;
1545 if (state_mergeable_p (new_state, from_state,
1546 current_method->max_locals))
1551 debug_print ("== Merge states in merge_into\n");
1552 debug_print_state (from_state, "Frm", vfr->start_PC, current_method->max_stack,
1553 current_method->max_locals);
1554 debug_print_state (new_state, " To", npc, current_method->max_stack,
1555 current_method->max_locals);
1556 changed = merge_states (new_state, from_state,
1557 current_method->max_locals);
1558 debug_print_state (new_state, "New", npc, current_method->max_stack,
1559 current_method->max_locals);
1562 state_reverify (new_state);
1568 /* Either we don't yet have a state at NPC, or we have a
1569 return-address type that is in conflict with all existing
1570 state. So, we need to create a new entry. */
1571 state *new_state = add_new_state (npc, from_state);
1572 /* A new state added in this way must always be reverified. */
1573 state_reverify (new_state);
1578 push_jump (int offset)
1580 int npc = compute_jump (offset);
1581 /* According to the JVM Spec, we need to check for uninitialized
1582 objects here. However, this does not actually affect type
1583 safety, and the Eclipse java compiler generates code that
1584 violates this constraint. */
1585 merge_into (npc, vfr->current_state);
1589 push_exception_jump (type t, int pc)
1592 /* According to the JVM Spec, we need to check for uninitialized
1593 objects here. However, this does not actually affect type
1594 safety, and the Eclipse java compiler generates code that
1595 violates this constraint. */
1596 copy_state_with_stack (&s, vfr->current_state,
1597 vfr->current_method->max_stack,
1598 vfr->current_method->max_locals);
1599 if (vfr->current_method->max_stack < 1)
1600 verify_fail ("stack overflow at exception handler");
1601 state_set_exception (&s, &t, vfr->current_method->max_stack);
1602 merge_into (pc, &s);
1603 /* FIXME: leak.. need free_state or GC */
1609 state *new_state = vfr->next_verify_state;
1610 if (new_state == INVALID_STATE)
1611 verify_fail ("programmer error in pop_jump");
1612 if (new_state != NULL)
1614 vfr->next_verify_state = new_state->next;
1615 new_state->next = INVALID_STATE;
1621 invalidate_pc (void)
1627 note_branch_target (int pc)
1629 /* Don't check `pc <= PC', because we've advanced PC after
1630 fetching the target and we haven't yet checked the next
1632 if (pc < vfr->PC && ! (vfr->flags[pc] & FLAG_INSN_START))
1633 verify_fail_pc ("branch not to instruction start", vfr->start_PC);
1634 vfr->flags[pc] |= FLAG_BRANCH_TARGET;
1640 while ((vfr->PC % 4) > 0)
1641 if (get_byte () != 0)
1642 verify_fail ("found nonzero padding byte");
1645 /* Do the work for a `ret' instruction. INDEX is the index into the
1648 handle_ret_insn (int index)
1650 type ret = make_type (return_address_type);
1651 type ret_addr = get_variable_t (index, &ret);
1652 /* It would be nice if we could do this. However, the JVM Spec
1653 doesn't say that this is what happens. It is implied that
1654 reusing a return address is invalid, but there's no actual
1655 prohibition against it. */
1656 /* set_variable (index, unsuitable_type); */
1658 int npc = type_get_pc (&ret_addr);
1659 /* We might be returning to a `jsr' that is at the end of the
1660 bytecode. This is ok if we never return from the called
1661 subroutine, but if we see this here it is an error. */
1662 if (npc >= vfr->current_method->code_length)
1663 verify_fail ("fell off end");
1665 /* According to the JVM Spec, we need to check for uninitialized
1666 objects here. However, this does not actually affect type
1667 safety, and the Eclipse java compiler generates code that
1668 violates this constraint. */
1669 merge_into (npc, vfr->current_state);
1673 static void handle_jsr_insn (int offset)
1676 int npc = compute_jump (offset);
1678 /* According to the JVM Spec, we need to check for uninitialized
1679 objects here. However, this does not actually affect type
1680 safety, and the Eclipse java compiler generates code that
1681 violates this constraint. */
1683 /* Modify our state as appropriate for entry into a subroutine. */
1684 ret_addr = make_type (return_address_type);
1685 type_set_return_address (&ret_addr, vfr->PC);
1686 vfy_push_type_t (ret_addr);
1687 merge_into (npc, vfr->current_state);
1692 construct_primitive_array_type (type_val prim)
1694 vfy_jclass k = NULL;
1705 k = vfy_get_primitive_type ((int) prim);
1708 /* These aren't used here but we call them out to avoid
1711 case unsuitable_type:
1712 case return_address_type:
1713 case continuation_type:
1714 case reference_type:
1716 case uninitialized_reference_type:
1718 verify_fail ("unknown type in construct_primitive_array_type");
1720 k = vfy_get_array_class (k);
1724 /* This pass computes the location of branch targets and also
1725 instruction starts. */
1727 branch_prepass (void)
1730 vfr->flags = (char *) vfy_alloc (vfr->current_method->code_length);
1732 for (i = 0; i < vfr->current_method->code_length; ++i)
1736 while (vfr->PC < vfr->current_method->code_length)
1739 /* Set `start_PC' early so that error checking can have the
1741 vfr->start_PC = vfr->PC;
1742 vfr->flags[vfr->PC] |= FLAG_INSN_START;
1744 opcode = (java_opcode) vfr->bytecode[vfr->PC++];
1748 case op_aconst_null:
1884 case op_monitorenter:
1885 case op_monitorexit:
1893 case op_arraylength:
1925 case op_invokespecial:
1926 case op_invokestatic:
1927 case op_invokevirtual:
1931 case op_multianewarray:
1954 note_branch_target (compute_jump (get_short ()));
1957 case op_tableswitch:
1961 note_branch_target (compute_jump (get_int ()));
1965 verify_fail_pc ("invalid tableswitch", vfr->start_PC);
1966 for (i = low; i <= hi; ++i)
1967 note_branch_target (compute_jump (get_int ()));
1971 case op_lookupswitch:
1975 note_branch_target (compute_jump (get_int ()));
1976 npairs = get_int ();
1978 verify_fail_pc ("too few pairs in lookupswitch", vfr->start_PC);
1979 while (npairs-- > 0)
1982 note_branch_target (compute_jump (get_int ()));
1987 case op_invokeinterface:
1995 opcode = (java_opcode) get_byte ();
1997 if (opcode == op_iinc)
2004 note_branch_target (compute_jump (get_int ()));
2008 /* These are unused here, but we call them out explicitly
2009 so that -Wswitch-enum doesn't complain. */
2015 case op_putstatic_1:
2016 case op_putstatic_2:
2017 case op_putstatic_4:
2018 case op_putstatic_8:
2019 case op_putstatic_a:
2021 case op_getfield_2s:
2022 case op_getfield_2u:
2026 case op_getstatic_1:
2027 case op_getstatic_2s:
2028 case op_getstatic_2u:
2029 case op_getstatic_4:
2030 case op_getstatic_8:
2031 case op_getstatic_a:
2032 #endif /* VFY_FAST_OPCODES */
2034 verify_fail_pc ("unrecognized instruction in branch_prepass",
2038 /* See if any previous branch tried to branch to the middle of
2039 this instruction. */
2040 for (pc = vfr->start_PC + 1; pc < vfr->PC; ++pc)
2042 if ((vfr->flags[pc] & FLAG_BRANCH_TARGET))
2043 verify_fail_pc ("branch to middle of instruction", pc);
2047 /* Verify exception handlers. */
2048 for (i = 0; i < vfr->current_method->exc_count; ++i)
2050 int handler, start, end, htype;
2051 vfy_get_exception (vfr->exception, i, &handler, &start, &end, &htype);
2052 if (! (vfr->flags[handler] & FLAG_INSN_START))
2053 verify_fail_pc ("exception handler not at instruction start",
2055 if (! (vfr->flags[start] & FLAG_INSN_START))
2056 verify_fail_pc ("exception start not at instruction start", start);
2057 if (end != vfr->current_method->code_length
2058 && ! (vfr->flags[end] & FLAG_INSN_START))
2059 verify_fail_pc ("exception end not at instruction start", end);
2061 vfr->flags[handler] |= FLAG_BRANCH_TARGET;
2066 check_pool_index (int index)
2068 if (index < 0 || index >= vfy_get_constants_size (vfr->current_class))
2069 verify_fail_pc ("constant pool index out of range", vfr->start_PC);
2073 check_class_constant (int index)
2076 vfy_constants *pool;
2078 check_pool_index (index);
2079 pool = vfy_get_constants (vfr->current_class);
2080 if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedClass)
2081 init_type_from_class (&t, vfy_get_pool_class (pool, index));
2082 else if (vfy_tag (pool, index) == JV_CONSTANT_Class)
2083 init_type_from_string (&t, vfy_get_pool_string (pool, index));
2085 verify_fail_pc ("expected class constant", vfr->start_PC);
2090 check_constant (int index)
2093 vfy_constants *pool;
2095 check_pool_index (index);
2096 pool = vfy_get_constants (vfr->current_class);
2097 if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedString
2098 || vfy_tag (pool, index) == JV_CONSTANT_String)
2099 init_type_from_class (&t, vfy_string_type ());
2100 else if (vfy_tag (pool, index) == JV_CONSTANT_Integer)
2101 init_type_from_tag (&t, int_type);
2102 else if (vfy_tag (pool, index) == JV_CONSTANT_Float)
2103 init_type_from_tag (&t, float_type);
2105 verify_fail_pc ("String, int, or float constant expected", vfr->start_PC);
2110 check_wide_constant (int index)
2113 vfy_constants *pool;
2115 check_pool_index (index);
2116 pool = vfy_get_constants (vfr->current_class);
2117 if (vfy_tag (pool, index) == JV_CONSTANT_Long)
2118 init_type_from_tag (&t, long_type);
2119 else if (vfy_tag (pool, index) == JV_CONSTANT_Double)
2120 init_type_from_tag (&t, double_type);
2122 verify_fail_pc ("long or double constant expected", vfr->start_PC);
2126 /* Helper for both field and method. These are laid out the same in
2127 the constant pool. */
2129 handle_field_or_method (int index, int expected,
2130 vfy_string *name, vfy_string *fmtype)
2132 vfy_uint_16 class_index, name_and_type_index;
2133 vfy_uint_16 name_index, desc_index;
2134 vfy_constants *pool;
2136 check_pool_index (index);
2137 pool = vfy_get_constants (vfr->current_class);
2138 if (vfy_tag (pool, index) != expected)
2139 verify_fail_pc ("didn't see expected constant", vfr->start_PC);
2140 /* Once we know we have a Fieldref or Methodref we assume that it
2141 is correctly laid out in the constant pool. I think the code
2142 in defineclass.cc guarantees this. */
2143 vfy_load_indexes (pool, index, &class_index, &name_and_type_index);
2144 vfy_load_indexes (pool, name_and_type_index, &name_index, &desc_index);
2146 *name = vfy_get_pool_string (pool, name_index);
2147 *fmtype = vfy_get_pool_string (pool, desc_index);
2149 return check_class_constant (class_index);
2152 /* Return field's type, compute class' type if requested. If
2153 PUTFIELD is true, use the special 'putfield' semantics. */
2155 check_field_constant (int index, type *class_type, bool putfield)
2157 vfy_string name, field_type;
2162 type ct = handle_field_or_method (index,
2163 JV_CONSTANT_Fieldref,
2164 &name, &field_type);
2167 typec = vfy_string_bytes (field_type);
2168 len = vfy_string_length (field_type);
2169 if (typec[0] == '[' || typec[0] == 'L')
2170 init_type_from_string (&t, field_type);
2172 init_type_from_tag (&t, get_type_val_for_signature (typec[0]));
2174 /* We have an obscure special case here: we can use `putfield' on a
2175 field declared in this class, even if `this' has not yet been
2178 && ! type_initialized (&vfr->current_state->this_type)
2179 && vfr->current_state->this_type.pc == SELF
2180 && types_equal (&vfr->current_state->this_type, &ct)
2181 && vfy_class_has_field (vfr->current_class, name, field_type))
2182 /* Note that we don't actually know whether we're going to match
2183 against 'this' or some other object of the same type. So,
2184 here we set things up so that it doesn't matter. This relies
2185 on knowing what our caller is up to. */
2186 type_set_uninitialized (class_type, EITHER);
2192 check_method_constant (int index, bool is_interface,
2193 vfy_string *method_name,
2194 vfy_string *method_signature)
2196 return handle_field_or_method (index,
2198 ? JV_CONSTANT_InterfaceMethodref
2199 : JV_CONSTANT_Methodref),
2200 method_name, method_signature);
2204 get_one_type (char *p, type *t)
2206 const char *start = p;
2226 name = vfy_get_string (start, p - start);
2227 *t = make_type_from_string (name);
2231 /* Casting to jchar here is ok since we are looking at an ASCII
2233 rt = get_type_val_for_signature (v);
2235 if (arraycount == 0)
2237 /* Callers of this function eventually push their arguments on
2238 the stack. So, promote them here. */
2239 type new_t = make_type (rt);
2240 vfy_promote_type (&new_t);
2245 k = construct_primitive_array_type (rt);
2246 while (--arraycount > 0)
2247 k = vfy_get_array_class (k);
2248 *t = make_type_from_class (k);
2253 compute_argument_types (vfy_string signature, type *types)
2256 char *p = (char *) vfy_string_bytes (signature);
2263 p = get_one_type (p, &types[i++]);
2267 compute_return_type (vfy_string signature)
2269 char *p = (char *) vfy_string_bytes (signature);
2274 get_one_type (p, &t);
2279 check_return_type (type onstack)
2281 type rt = compute_return_type (vfy_get_signature (vfr->current_method));
2282 if (! types_compatible (&rt, &onstack))
2283 verify_fail ("incompatible return type");
2286 /* Initialize the stack for the new method. Returns true if this
2287 method is an instance initializer. */
2289 initialize_stack (void)
2293 bool is_init = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2295 bool is_clinit = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2298 if (! vfy_is_static (vfr->current_method))
2300 type kurr = make_type_from_class (vfr->current_class);
2303 type_set_uninitialized (&kurr, SELF);
2307 verify_fail ("<clinit> method must be static");
2308 set_variable (0, kurr);
2309 state_set_this_type (vfr->current_state, &kurr);
2315 verify_fail ("<init> method must be non-static");
2318 /* We have to handle wide arguments specially here. */
2319 arg_count = vfy_count_arguments (vfy_get_signature (vfr->current_method));
2321 type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2322 compute_argument_types (vfy_get_signature (vfr->current_method), arg_types);
2323 for (i = 0; i < arg_count; ++i)
2325 set_variable (var, arg_types[i]);
2327 if (type_iswide (&arg_types[i]))
2330 vfy_free (arg_types);
2337 verify_instructions_0 (void)
2342 vfr->current_state = make_state (vfr->current_method->max_stack,
2343 vfr->current_method->max_locals);
2348 /* True if we are verifying an instance initializer. */
2349 this_is_init = initialize_stack ();
2351 vfr->states = (state_list **) vfy_alloc (sizeof (state_list *)
2352 * vfr->current_method->code_length);
2354 for (i = 0; i < vfr->current_method->code_length; ++i)
2355 vfr->states[i] = NULL;
2357 vfr->next_verify_state = NULL;
2363 /* If the PC was invalidated, get a new one from the work list. */
2364 if (vfr->PC == NO_NEXT)
2366 state *new_state = pop_jump ();
2367 /* If it is null, we're done. */
2368 if (new_state == NULL)
2371 vfr->PC = state_get_pc (new_state);
2372 debug_print ("== State pop from pending list\n");
2373 /* Set up the current state. */
2374 copy_state (vfr->current_state, new_state,
2375 vfr->current_method->max_stack, vfr->current_method->max_locals);
2379 /* We only have to do this checking in the situation where
2380 control flow falls through from the previous
2381 instruction. Otherwise merging is done at the time we
2383 if (vfr->states[vfr->PC] != NULL)
2385 /* We've already visited this instruction. So merge
2386 the states together. It is simplest, but not most
2387 efficient, to just always invalidate the PC here. */
2388 merge_into (vfr->PC, vfr->current_state);
2394 /* Control can't fall off the end of the bytecode. We need to
2395 check this in both cases, not just the fall-through case,
2396 because we don't check to see whether a `jsr' appears at
2397 the end of the bytecode until we process a `ret'. */
2398 if (vfr->PC >= vfr->current_method->code_length)
2399 verify_fail ("fell off end");
2400 vfr->flags[vfr->PC] |= FLAG_INSN_SEEN;
2402 /* We only have to keep saved state at branch targets. If
2403 we're at a branch target and the state here hasn't been set
2404 yet, we set it now. You might notice that `ret' targets
2405 won't necessarily have FLAG_BRANCH_TARGET set. This
2406 doesn't matter, since those states will be filled in by
2408 /* Note that other parts of the compiler assume that there is a
2409 label with a type map at PC=0. */
2410 if (vfr->states[vfr->PC] == NULL
2411 && (vfr->PC == 0 || (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET) != 0))
2412 add_new_state (vfr->PC, vfr->current_state);
2414 /* Set this before handling exceptions so that debug output is
2416 vfr->start_PC = vfr->PC;
2418 /* Update states for all active exception handlers. Ordinarily
2419 there are not many exception handlers. So we simply run
2420 through them all. */
2421 for (i = 0; i < vfr->current_method->exc_count; ++i)
2423 int hpc, start, end, htype;
2424 vfy_get_exception (vfr->exception, i, &hpc, &start, &end, &htype);
2425 if (vfr->PC >= start && vfr->PC < end)
2427 type handler = make_type_from_class (vfy_throwable_type ());
2429 handler = check_class_constant (htype);
2430 push_exception_jump (handler, hpc);
2435 debug_print_state (vfr->current_state, " ", vfr->PC,
2436 vfr->current_method->max_stack,
2437 vfr->current_method->max_locals);
2438 opcode = (java_opcode) vfr->bytecode[vfr->PC++];
2444 case op_aconst_null:
2445 push_type (null_type);
2455 push_type (int_type);
2460 push_type (long_type);
2466 push_type (float_type);
2471 push_type (double_type);
2476 push_type (int_type);
2481 push_type (int_type);
2485 push_type_t (check_constant (get_byte ()));
2488 push_type_t (check_constant (get_ushort ()));
2491 push_type_t (check_wide_constant (get_ushort ()));
2495 push_type_t (get_variable (get_byte (), int_type));
2498 push_type_t (get_variable (get_byte (), long_type));
2501 push_type_t (get_variable (get_byte (), float_type));
2504 push_type_t (get_variable (get_byte (), double_type));
2507 push_type_t (get_variable (get_byte (), reference_type));
2514 push_type_t (get_variable (opcode - op_iload_0, int_type));
2520 push_type_t (get_variable (opcode - op_lload_0, long_type));
2526 push_type_t (get_variable (opcode - op_fload_0, float_type));
2532 push_type_t (get_variable (opcode - op_dload_0, double_type));
2538 push_type_t (get_variable (opcode - op_aload_0, reference_type));
2541 pop_type (int_type);
2542 push_type_t (require_array_type (pop_init_ref (reference_type),
2546 pop_type (int_type);
2547 push_type_t (require_array_type (pop_init_ref (reference_type),
2551 pop_type (int_type);
2552 push_type_t (require_array_type (pop_init_ref (reference_type),
2556 pop_type (int_type);
2557 push_type_t (require_array_type (pop_init_ref (reference_type),
2561 pop_type (int_type);
2562 push_type_t (require_array_type (pop_init_ref (reference_type),
2566 pop_type (int_type);
2567 require_array_type (pop_init_ref (reference_type), byte_type);
2568 push_type (int_type);
2571 pop_type (int_type);
2572 require_array_type (pop_init_ref (reference_type), char_type);
2573 push_type (int_type);
2576 pop_type (int_type);
2577 require_array_type (pop_init_ref (reference_type), short_type);
2578 push_type (int_type);
2581 set_variable (get_byte (), pop_type (int_type));
2584 set_variable (get_byte (), pop_type (long_type));
2587 set_variable (get_byte (), pop_type (float_type));
2590 set_variable (get_byte (), pop_type (double_type));
2593 set_variable (get_byte (), pop_ref_or_return ());
2599 set_variable (opcode - op_istore_0, pop_type (int_type));
2605 set_variable (opcode - op_lstore_0, pop_type (long_type));
2611 set_variable (opcode - op_fstore_0, pop_type (float_type));
2617 set_variable (opcode - op_dstore_0, pop_type (double_type));
2623 set_variable (opcode - op_astore_0, pop_ref_or_return ());
2626 pop_type (int_type);
2627 pop_type (int_type);
2628 require_array_type (pop_init_ref (reference_type), int_type);
2631 pop_type (long_type);
2632 pop_type (int_type);
2633 require_array_type (pop_init_ref (reference_type), long_type);
2636 pop_type (float_type);
2637 pop_type (int_type);
2638 require_array_type (pop_init_ref (reference_type), float_type);
2641 pop_type (double_type);
2642 pop_type (int_type);
2643 require_array_type (pop_init_ref (reference_type), double_type);
2646 pop_type (reference_type);
2647 pop_type (int_type);
2648 require_array_type (pop_init_ref (reference_type), reference_type);
2651 pop_type (int_type);
2652 pop_type (int_type);
2653 require_array_type (pop_init_ref (reference_type), byte_type);
2656 pop_type (int_type);
2657 pop_type (int_type);
2658 require_array_type (pop_init_ref (reference_type), char_type);
2661 pop_type (int_type);
2662 pop_type (int_type);
2663 require_array_type (pop_init_ref (reference_type), short_type);
2670 type t = pop_raw ();
2671 if (! type_iswide (&t))
2694 type t2 = pop_raw ();
2695 if (! type_iswide (&t2))
2709 type t = pop_raw ();
2710 if (! type_iswide (&t))
2724 type t1 = pop_raw ();
2726 if (! type_iswide (&t1))
2741 type t1 = pop_raw ();
2742 if (type_iswide (&t1))
2744 type t2 = pop_raw ();
2745 if (type_iswide (&t2))
2762 type t3 = pop_raw ();
2763 if (type_iswide (&t3))
2800 pop_type (int_type);
2801 push_type_t (pop_type (int_type));
2811 pop_type (long_type);
2812 push_type_t (pop_type (long_type));
2817 pop_type (int_type);
2818 push_type_t (pop_type (long_type));
2825 pop_type (float_type);
2826 push_type_t (pop_type (float_type));
2833 pop_type (double_type);
2834 push_type_t (pop_type (double_type));
2840 push_type_t (pop_type (int_type));
2843 push_type_t (pop_type (long_type));
2846 push_type_t (pop_type (float_type));
2849 push_type_t (pop_type (double_type));
2852 get_variable (get_byte (), int_type);
2856 pop_type (int_type);
2857 push_type (long_type);
2860 pop_type (int_type);
2861 push_type (float_type);
2864 pop_type (int_type);
2865 push_type (double_type);
2868 pop_type (long_type);
2869 push_type (int_type);
2872 pop_type (long_type);
2873 push_type (float_type);
2876 pop_type (long_type);
2877 push_type (double_type);
2880 pop_type (float_type);
2881 push_type (int_type);
2884 pop_type (float_type);
2885 push_type (long_type);
2888 pop_type (float_type);
2889 push_type (double_type);
2892 pop_type (double_type);
2893 push_type (int_type);
2896 pop_type (double_type);
2897 push_type (long_type);
2900 pop_type (double_type);
2901 push_type (float_type);
2904 pop_type (long_type);
2905 pop_type (long_type);
2906 push_type (int_type);
2910 pop_type (float_type);
2911 pop_type (float_type);
2912 push_type (int_type);
2916 pop_type (double_type);
2917 pop_type (double_type);
2918 push_type (int_type);
2926 pop_type (int_type);
2927 push_jump (get_short ());
2935 pop_type (int_type);
2936 pop_type (int_type);
2937 push_jump (get_short ());
2941 pop_type (reference_type);
2942 pop_type (reference_type);
2943 push_jump (get_short ());
2946 push_jump (get_short ());
2950 handle_jsr_insn (get_short ());
2953 handle_ret_insn (get_byte ());
2955 case op_tableswitch:
2959 pop_type (int_type);
2961 push_jump (get_int ());
2964 /* Already checked LOW -vs- HIGH. */
2965 for (i = low; i <= high; ++i)
2966 push_jump (get_int ());
2971 case op_lookupswitch:
2974 jint npairs, lastkey;
2976 pop_type (int_type);
2978 push_jump (get_int ());
2979 npairs = get_int ();
2980 /* Already checked NPAIRS >= 0. */
2982 for (i = 0; i < npairs; ++i)
2984 jint key = get_int ();
2985 if (i > 0 && key <= lastkey)
2986 verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC);
2988 push_jump (get_int ());
2994 check_return_type (pop_type (int_type));
2998 check_return_type (pop_type (long_type));
3002 check_return_type (pop_type (float_type));
3006 check_return_type (pop_type (double_type));
3010 check_return_type (pop_init_ref (reference_type));
3014 /* We only need to check this when the return type is
3015 void, because all instance initializers return void. */
3017 state_check_this_initialized (vfr->current_state);
3018 check_return_type (make_type (void_type));
3022 push_type_t (check_field_constant (get_ushort (), NULL, false));
3025 pop_type_t (check_field_constant (get_ushort (), NULL, false));
3030 type field = check_field_constant (get_ushort (), &klass, false);
3032 push_type_t (field);
3038 type field = check_field_constant (get_ushort (), &klass, true);
3044 case op_invokevirtual:
3045 case op_invokespecial:
3046 case op_invokestatic:
3047 case op_invokeinterface:
3049 vfy_string method_name, method_signature;
3053 bool is_init = false;
3056 = check_method_constant (get_ushort (),
3057 opcode == op_invokeinterface,
3060 /* NARGS is only used when we're processing
3061 invokeinterface. It is simplest for us to compute it
3062 here and then verify it later. */
3064 if (opcode == op_invokeinterface)
3066 nargs = get_byte ();
3067 if (get_byte () != 0)
3068 verify_fail ("invokeinterface dummy byte is wrong");
3071 namec = vfy_string_bytes (method_name);
3073 if (vfy_strings_equal (method_name, vfy_init_name()))
3076 if (opcode != op_invokespecial)
3077 verify_fail ("can't invoke <init>");
3079 else if (namec[0] == '<')
3080 verify_fail ("can't invoke method starting with `<'");
3082 arg_count = vfy_count_arguments (method_signature);
3084 /* Pop arguments and check types. */
3085 type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
3087 compute_argument_types (method_signature, arg_types);
3088 for (i = arg_count - 1; i >= 0; --i)
3090 /* This is only used for verifying the byte for
3092 nargs -= type_depth (&arg_types[i]);
3093 pop_init_ref_t (arg_types[i]);
3096 vfy_free (arg_types);
3099 if (opcode == op_invokeinterface
3101 verify_fail ("wrong argument count for invokeinterface");
3103 if (opcode != op_invokestatic)
3106 type t = class_type;
3109 /* In this case the PC doesn't matter. */
3110 type_set_uninitialized (&t, UNINIT);
3111 /* FIXME: check to make sure that the <init>
3112 call is to the right class.
3113 It must either be super or an exact class
3117 if (! types_compatible (&t, &raw))
3118 verify_fail ("incompatible type on stack");
3121 state_set_initialized (vfr->current_state,
3122 type_get_pc (&raw), vfr->current_method->max_locals);
3125 rt = compute_return_type (method_signature);
3126 if (! type_isvoid (&rt))
3133 type t = check_class_constant (get_ushort ());
3134 if (type_isarray (&t) || type_isinterface (&t)
3135 || type_isabstract (&t))
3136 verify_fail ("type is array, interface, or abstract");
3137 type_set_uninitialized (&t, vfr->start_PC);
3144 int atype = get_byte ();
3146 /* We intentionally have chosen constants to make this
3148 if (atype < boolean_type || atype > long_type)
3149 verify_fail_pc ("type not primitive", vfr->start_PC);
3150 pop_type (int_type);
3151 init_type_from_class (&t, construct_primitive_array_type (atype));
3158 pop_type (int_type);
3159 t = check_class_constant (get_ushort ());
3160 push_type_t (type_to_array (&t));
3163 case op_arraylength:
3165 type t = pop_init_ref (reference_type);
3166 if (! type_isarray (&t) && ! type_isnull (&t))
3167 verify_fail ("array type expected");
3168 push_type (int_type);
3172 pop_type_t (make_type_from_class (vfy_throwable_type ()));
3176 pop_init_ref (reference_type);
3177 push_type_t (check_class_constant (get_ushort ()));
3180 pop_init_ref (reference_type);
3181 check_class_constant (get_ushort ());
3182 push_type (int_type);
3184 case op_monitorenter:
3185 pop_init_ref (reference_type);
3187 case op_monitorexit:
3188 pop_init_ref (reference_type);
3192 switch (get_byte ())
3195 push_type_t (get_variable (get_ushort (), int_type));
3198 push_type_t (get_variable (get_ushort (), long_type));
3201 push_type_t (get_variable (get_ushort (), float_type));
3204 push_type_t (get_variable (get_ushort (), double_type));
3207 push_type_t (get_variable (get_ushort (), reference_type));
3210 set_variable (get_ushort (), pop_type (int_type));
3213 set_variable (get_ushort (), pop_type (long_type));
3216 set_variable (get_ushort (), pop_type (float_type));
3219 set_variable (get_ushort (), pop_type (double_type));
3222 set_variable (get_ushort (), pop_init_ref (reference_type));
3225 handle_ret_insn (get_short ());
3228 get_variable (get_ushort (), int_type);
3232 verify_fail_pc ("unrecognized wide instruction", vfr->start_PC);
3236 case op_multianewarray:
3239 type atype = check_class_constant (get_ushort ());
3240 int dim = get_byte ();
3242 verify_fail_pc ("too few dimensions to multianewarray", vfr->start_PC);
3243 type_verify_dimensions (&atype, dim);
3244 for (i = 0; i < dim; ++i)
3245 pop_type (int_type);
3246 push_type_t (atype);
3251 pop_type (reference_type);
3252 push_jump (get_short ());
3255 push_jump (get_int ());
3259 handle_jsr_insn (get_int ());
3263 /* These are unused here, but we call them out explicitly
3264 so that -Wswitch-enum doesn't complain. */
3270 case op_putstatic_1:
3271 case op_putstatic_2:
3272 case op_putstatic_4:
3273 case op_putstatic_8:
3274 case op_putstatic_a:
3276 case op_getfield_2s:
3277 case op_getfield_2u:
3281 case op_getstatic_1:
3282 case op_getstatic_2s:
3283 case op_getstatic_2u:
3284 case op_getstatic_4:
3285 case op_getstatic_8:
3286 case op_getstatic_a:
3289 /* Unrecognized opcode. */
3290 verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3296 /* This turns a `type' into something suitable for use by the type map
3297 in the other parts of the compiler. In particular, reference types
3298 are mapped to Object, primitive types are unchanged, and other
3299 types are mapped using special functions declared in verify.h. */
3301 collapse_type (type *t)
3314 return vfy_get_primitive_type (t->key);
3316 case unsuitable_type:
3317 case continuation_type:
3318 return vfy_unsuitable_type ();
3320 case return_address_type:
3321 return vfy_return_address_type ();
3324 return vfy_null_type ();
3326 case reference_type:
3327 case uninitialized_reference_type:
3328 return vfy_object_type ();
3335 verify_instructions (void)
3340 verify_instructions_0 ();
3342 /* Now tell the rest of the compiler about the types we've found. */
3343 for (i = 0; i < vfr->current_method->code_length; ++i)
3348 if ((vfr->flags[i] & FLAG_INSN_SEEN) != 0)
3349 vfy_note_instruction_seen (i);
3351 if (! vfr->states[i])
3354 curr = vfr->states[i]->val;
3355 vfy_note_stack_depth (vfr->current_method, i, curr->stackdepth);
3357 /* Tell the compiler about each local variable. */
3358 for (j = 0; j < vfr->current_method->max_locals; ++j)
3359 vfy_note_local_type (vfr->current_method, i, j,
3360 collapse_type (&curr->locals[j]));
3361 /* Tell the compiler about each stack slot. */
3362 for (slot = j = 0; j < curr->stacktop; ++j, ++slot)
3364 vfy_note_stack_type (vfr->current_method, i, slot,
3365 collapse_type (&curr->stack[j]));
3366 if (type_iswide (&curr->stack[j]))
3369 vfy_note_stack_type (vfr->current_method, i, slot,
3370 vfy_unsuitable_type ());
3373 if (slot != curr->stackdepth)
3379 _Jv_BytecodeVerifier (_Jv_InterpMethod *m)
3381 /* We just print the text as utf-8. This is just for debugging
3383 debug_print ("--------------------------------\n");
3384 debug_print ("-- Verifying method `%s'\n", m->self->name->chars());
3390 make_verifier_context (vfy_method *m)
3392 vfr = (verifier_context *) vfy_alloc (sizeof (struct verifier_context));
3394 vfr->current_method = m;
3395 vfr->bytecode = vfy_get_bytecode (m);
3396 vfr->exception = vfy_get_exceptions (m);
3397 vfr->current_class = m->defining_class;
3401 vfr->utf8_list = NULL;
3402 vfr->isect_list = NULL;
3406 free_verifier_context (void)
3408 vfy_string_list *utf8_list;
3409 ref_intersection *isect_list;
3412 vfy_free (vfr->flags);
3414 utf8_list = vfr->utf8_list;
3415 while (utf8_list != NULL)
3417 vfy_string_list *n = utf8_list->next;
3418 vfy_free (utf8_list);
3422 isect_list = vfr->isect_list;
3423 while (isect_list != NULL)
3425 ref_intersection *next = isect_list->alloc_next;
3426 vfy_free (isect_list);
3430 if (vfr->states != NULL)
3433 for (i = 0; i < vfr->current_method->code_length; ++i)
3435 state_list *iter = vfr->states[i];
3436 while (iter != NULL)
3438 state_list *next = iter->next;
3439 vfy_free (iter->val);
3444 vfy_free (vfr->states);
3451 verify_method (vfy_method *meth)
3453 debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth->name),
3457 verify_fail ("verifier re-entered");
3459 make_verifier_context (meth);
3460 verify_instructions ();
3461 free_verifier_context ();