1 /* Copyright (C) 2001, 2002, 2003, 2004 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, and the
543 special value SELF for the case where the current method is
544 itself the <init> method.
546 Second, when the key is return_address_type, this holds the PC
547 of the instruction following the `jsr'. */
555 /* Basic constructor. */
559 t
->key
= unsuitable_type
;
565 /* Make a new instance given the type tag. We assume a generic
566 `reference_type' means Object. */
568 init_type_from_tag (type
*t
, type_val k
)
571 /* For reference_type, if KLASS==NULL then that means we are
572 looking for a generic object of any kind, including an
573 uninitialized reference. */
578 /* Make a type for the given type_val tag K. */
580 make_type (type_val k
)
583 init_type_from_tag (&t
, k
);
587 /* Make a new instance given a class. */
589 init_type_from_class (type
*t
, vfy_jclass k
)
591 t
->key
= reference_type
;
592 t
->klass
= make_ref ();
593 t
->klass
->is_resolved
= true;
594 t
->klass
->data
.klass
= k
;
595 t
->klass
->ref_next
= NULL
;
600 make_type_from_class (vfy_jclass k
)
603 init_type_from_class (&t
, k
);
608 init_type_from_string (type
*t
, vfy_string n
)
610 t
->key
= reference_type
;
611 t
->klass
= make_ref ();
612 t
->klass
->is_resolved
= false;
613 t
->klass
->data
.name
= n
;
614 t
->klass
->ref_next
= NULL
;
619 make_type_from_string (vfy_string n
)
622 init_type_from_string (&t
, n
);
627 /* Make a new instance given the name of a class. */
630 key
= reference_type
;
631 klass
= new ref_intersection (n
, verifier
);
635 /* Copy constructor. */
636 static type
copy_type (type
*t
)
640 copy
.klass
= t
->klass
;
646 /* Promote a numeric type. */
648 vfy_promote_type (type
*t
)
650 if (t
->key
== boolean_type
|| t
->key
== char_type
651 || t
->key
== byte_type
|| t
->key
== short_type
)
654 #define promote_type vfy_promote_type
656 /* Mark this type as the uninitialized result of `new'. */
658 type_set_uninitialized (type
*t
, int npc
)
660 if (t
->key
== reference_type
)
661 t
->key
= uninitialized_reference_type
;
663 verify_fail ("internal error in type::uninitialized");
667 /* Mark this type as now initialized. */
669 type_set_initialized (type
*t
, int npc
)
671 if (npc
!= UNINIT
&& t
->pc
== npc
&& t
->key
== uninitialized_reference_type
)
673 t
->key
= reference_type
;
678 /* Mark this type as a particular return address. */
679 static void type_set_return_address (type
*t
, int npc
)
684 /* Return true if this type and type OTHER are considered
685 mergeable for the purposes of state merging. This is related
686 to subroutine handling. For this purpose two types are
687 considered unmergeable if they are both return-addresses but
688 have different PCs. */
690 type_state_mergeable_p (type
*t1
, type
*t2
)
692 return (t1
->key
!= return_address_type
693 || t2
->key
!= return_address_type
694 || t1
->pc
== t2
->pc
);
697 /* Return true if an object of type K can be assigned to a variable
698 of type T. Handle various special cases too. Might modify
699 T or K. Note however that this does not perform numeric
702 types_compatible (type
*t
, type
*k
)
704 /* Any type is compatible with the unsuitable type. */
705 if (k
->key
== unsuitable_type
)
708 if (t
->key
< reference_type
|| k
->key
< reference_type
)
709 return t
->key
== k
->key
;
711 /* The `null' type is convertible to any initialized reference
713 if (t
->key
== null_type
)
714 return k
->key
!= uninitialized_reference_type
;
715 if (k
->key
== null_type
)
716 return t
->key
!= uninitialized_reference_type
;
718 /* A special case for a generic reference. */
719 if (t
->klass
== NULL
)
721 if (k
->klass
== NULL
)
722 verify_fail ("programmer error in type::compatible");
724 /* An initialized type and an uninitialized type are not
726 if (type_initialized (t
) != type_initialized (k
))
729 /* Two uninitialized objects are compatible if either:
730 * The PCs are identical, or
731 * One PC is UNINIT. */
732 if (type_initialized (t
))
734 if (t
->pc
!= k
->pc
&& t
->pc
!= UNINIT
&& k
->pc
!= UNINIT
)
738 return ref_compatible (t
->klass
, k
->klass
);
742 type_isvoid (type
*t
)
744 return t
->key
== void_type
;
748 type_iswide (type
*t
)
750 return t
->key
== long_type
|| t
->key
== double_type
;
753 /* Return number of stack or local variable slots taken by this type. */
757 return type_iswide (t
) ? 2 : 1;
761 type_isarray (type
*t
)
763 /* We treat null_type as not an array. This is ok based on the
764 current uses of this method. */
765 if (t
->key
== reference_type
)
766 return ref_isarray (t
->klass
);
771 type_isnull (type
*t
)
773 return t
->key
== null_type
;
777 type_isinterface (type
*t
)
779 if (t
->key
!= reference_type
)
781 return ref_isinterface (t
->klass
);
785 type_isabstract (type
*t
)
787 if (t
->key
!= reference_type
)
789 return ref_isabstract (t
->klass
);
792 /* Return the element type of an array. */
794 type_array_element (type
*t
)
799 if (t
->key
!= reference_type
)
800 verify_fail ("programmer error in type::element_type()");
802 k
= vfy_get_component_type (ref_getclass (t
->klass
));
803 if (vfy_is_primitive (k
))
804 init_type_from_tag (&et
, get_type_val_for_primtype (k
));
806 init_type_from_class (&et
, k
);
810 /* Return the array type corresponding to an initialized
811 reference. We could expand this to work for other kinds of
812 types, but currently we don't need to. */
814 type_to_array (type
*t
)
819 if (t
->key
!= reference_type
)
820 verify_fail ("internal error in type::to_array()");
822 k
= ref_getclass (t
->klass
);
823 init_type_from_class (&at
, vfy_get_array_class (k
));
828 type_isreference (type
*t
)
830 return t
->key
>= reference_type
;
834 type_get_pc (type
*t
)
840 type_initialized (type
*t
)
842 return t
->key
== reference_type
|| t
->key
== null_type
;
847 type_isresolved (type
*t
)
849 return (t
->key
== reference_type
850 || t
->key
== null_type
851 || t
->key
== uninitialized_reference_type
);
856 type_verify_dimensions (type
*t
, int ndims
)
858 /* The way this is written, we don't need to check isarray(). */
859 if (t
->key
!= reference_type
)
860 verify_fail ("internal error in verify_dimensions:"
861 " not a reference type");
863 if (ref_count_dimensions (t
->klass
) < ndims
)
864 verify_fail ("array type has fewer dimensions"
868 /* Merge OLD_TYPE into this. On error throw exception. Return
869 true if the merge caused a type change. */
871 merge_types (type
*t
, type
*old_type
, bool local_semantics
)
873 bool changed
= false;
874 bool refo
= type_isreference (old_type
);
875 bool refn
= type_isreference (t
);
878 if (old_type
->key
== null_type
)
880 else if (t
->key
== null_type
)
885 else if (type_initialized (t
) != type_initialized (old_type
))
886 verify_fail ("merging initialized and uninitialized types");
889 ref_intersection
*merged
;
890 if (! type_initialized (t
))
893 t
->pc
= old_type
->pc
;
894 else if (old_type
->pc
== UNINIT
)
896 else if (t
->pc
!= old_type
->pc
)
897 verify_fail ("merging different uninitialized types");
900 merged
= merge_refs (old_type
->klass
, t
->klass
);
901 if (merged
!= t
->klass
)
908 else if (refo
|| refn
|| t
->key
!= old_type
->key
)
912 /* If we already have an `unsuitable' type, then we
913 don't need to change again. */
914 if (t
->key
!= unsuitable_type
)
916 t
->key
= unsuitable_type
;
921 verify_fail ("unmergeable type");
933 case boolean_type
: c
= 'Z'; break;
934 case byte_type
: c
= 'B'; break;
935 case char_type
: c
= 'C'; break;
936 case short_type
: c
= 'S'; break;
937 case int_type
: c
= 'I'; break;
938 case long_type
: c
= 'J'; break;
939 case float_type
: c
= 'F'; break;
940 case double_type
: c
= 'D'; break;
941 case void_type
: c
= 'V'; break;
942 case unsuitable_type
: c
= '-'; break;
943 case return_address_type
: c
= 'r'; break;
944 case continuation_type
: c
= '+'; break;
945 case reference_type
: c
= 'L'; break;
946 case null_type
: c
= '@'; break;
947 case uninitialized_reference_type
: c
= 'U'; break;
949 debug_print ("%c", c
);
951 #endif /* VERIFY_DEBUG */
953 /* This class holds all the state information we need for a given
957 /* The current top of the stack, in terms of slots. */
959 /* The current depth of the stack. This will be larger than
960 STACKTOP when wide types are on the stack. */
964 /* The local variables. */
966 /* We keep track of the type of `this' specially. This is used to
967 ensure that an instance initializer invokes another initializer
968 on `this' before returning. We must keep track of this
969 specially because otherwise we might be confused by code which
970 assigns to locals[0] (overwriting `this') and then returns
971 without really initializing. */
974 /* The PC for this state. This is only valid on states which are
975 permanently attached to a given PC. For an object like
976 `current_state', which is used transiently, this has no
979 /* We keep a linked list of all states requiring reverification.
980 If this is the special value INVALID_STATE then this state is
981 not on the list. NULL marks the end of the linked list. */
985 /* NO_NEXT is the PC value meaning that a new state must be
986 acquired from the verification list. */
991 init_state (state
*s
)
995 s
->next
= INVALID_STATE
;
1000 init_state_with_stack (state
*s
, int max_stack
, int max_locals
)
1005 s
->stack
= (type
*) vfy_alloc (max_stack
* sizeof (type
));
1006 for (i
= 0; i
< max_stack
; ++i
)
1007 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
1008 s
->locals
= (type
*) vfy_alloc (max_locals
* sizeof (type
));
1009 for (i
= 0; i
< max_locals
; ++i
)
1010 init_type_from_tag (&s
->locals
[i
], unsuitable_type
);
1011 init_type_from_tag (&s
->this_type
, unsuitable_type
);
1013 s
->next
= INVALID_STATE
;
1017 copy_state (state
*s
, state
*copy
, int max_stack
, int max_locals
)
1020 s
->stacktop
= copy
->stacktop
;
1021 s
->stackdepth
= copy
->stackdepth
;
1022 for (i
= 0; i
< max_stack
; ++i
)
1023 s
->stack
[i
] = copy
->stack
[i
];
1024 for (i
= 0; i
< max_locals
; ++i
)
1025 s
->locals
[i
] = copy
->locals
[i
];
1027 s
->this_type
= copy
->this_type
;
1028 /* Don't modify `next' or `pc'. */
1032 copy_state_with_stack (state
*s
, state
*orig
, int max_stack
, int max_locals
)
1034 init_state_with_stack (s
, max_stack
, max_locals
);
1035 copy_state (s
, orig
, max_stack
, max_locals
);
1038 /* Allocate a new state, copying ORIG. */
1040 make_state_copy (state
*orig
, int max_stack
, int max_locals
)
1042 state
*s
= vfy_alloc (sizeof (state
));
1043 copy_state_with_stack (s
, orig
, max_stack
, max_locals
);
1048 make_state (int max_stack
, int max_locals
)
1050 state
*s
= vfy_alloc (sizeof (state
));
1051 init_state_with_stack (s
, max_stack
, max_locals
);
1057 free_state (state
*s
)
1059 if (s
->stack
!= NULL
)
1060 vfy_free (s
->stack
);
1061 if (s
->locals
!= NULL
)
1062 vfy_free (s
->locals
);
1067 void *operator new[] (size_t bytes
)
1069 return vfy_alloc (bytes
);
1072 void operator delete[] (void *mem
)
1077 void *operator new (size_t bytes
)
1079 return vfy_alloc (bytes
);
1082 void operator delete (void *mem
)
1088 /* Modify this state to reflect entry to an exception handler. */
1090 state_set_exception (state
*s
, type
*t
, int max_stack
)
1096 for (i
= s
->stacktop
; i
< max_stack
; ++i
)
1097 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
1101 state_get_pc (state
*s
)
1108 set_pc (state
*s
, int npc
)
1114 /* Merge STATE_OLD into this state. Destructively modifies this
1115 state. Returns true if the new state was in fact changed.
1116 Will throw an exception if the states are not mergeable. */
1118 merge_states (state
*s
, state
*state_old
, int max_locals
)
1121 bool changed
= false;
1123 /* Special handling for `this'. If one or the other is
1124 uninitialized, then the merge is uninitialized. */
1125 if (type_initialized (&s
->this_type
))
1126 s
->this_type
= state_old
->this_type
;
1129 if (state_old
->stacktop
!= s
->stacktop
) /* FIXME stackdepth instead? */
1130 verify_fail ("stack sizes differ");
1131 for (i
= 0; i
< state_old
->stacktop
; ++i
)
1133 if (merge_types (&s
->stack
[i
], &state_old
->stack
[i
], false))
1137 /* Merge local variables. */
1138 for (i
= 0; i
< max_locals
; ++i
)
1140 if (merge_types (&s
->locals
[i
], &state_old
->locals
[i
], true))
1147 /* Ensure that `this' has been initialized. */
1149 state_check_this_initialized (state
*s
)
1151 if (type_isreference (&s
->this_type
) && ! type_initialized (&s
->this_type
))
1152 verify_fail ("`this' is uninitialized");
1155 /* Set type of `this'. */
1157 state_set_this_type (state
*s
, type
*k
)
1162 /* Mark each `new'd object we know of that was allocated at PC as
1165 state_set_initialized (state
*s
, int pc
, int max_locals
)
1168 for (i
= 0; i
< s
->stacktop
; ++i
)
1169 type_set_initialized (&s
->stack
[i
], pc
);
1170 for (i
= 0; i
< max_locals
; ++i
)
1171 type_set_initialized (&s
->locals
[i
], pc
);
1172 type_set_initialized (&s
->this_type
, pc
);
1175 /* This tests to see whether two states can be considered "merge
1176 compatible". If both states have a return-address in the same
1177 slot, and the return addresses are different, then they are not
1178 compatible and we must not try to merge them. */
1180 state_mergeable_p (state
*s
, state
*other
, int max_locals
)
1185 /* This is tricky: if the stack sizes differ, then not only are
1186 these not mergeable, but in fact we should give an error, as
1187 we've found two execution paths that reach a branch target
1188 with different stack depths. FIXME stackdepth instead? */
1189 if (s
->stacktop
!= other
->stacktop
)
1190 verify_fail ("stack sizes differ");
1192 for (i
= 0; i
< s
->stacktop
; ++i
)
1193 if (! type_state_mergeable_p (&s
->stack
[i
], &other
->stack
[i
]))
1195 for (i
= 0; i
< max_locals
; ++i
)
1196 if (! type_state_mergeable_p (&s
->locals
[i
], &other
->locals
[i
]))
1202 state_reverify (state
*s
)
1204 if (s
->next
== INVALID_STATE
)
1206 s
->next
= vfr
->next_verify_state
;
1207 vfr
->next_verify_state
= s
;
1213 debug_print_state (state
*s
, const char *leader
, int pc
, int max_stack
,
1217 debug_print ("%s [%4d]: [stack] ", leader
, pc
);
1218 for (i
= 0; i
< s
->stacktop
; ++i
)
1219 type_print (&s
->stack
[i
]);
1220 for (; i
< max_stack
; ++i
)
1222 debug_print (" [local] ");
1223 for (i
= 0; i
< max_locals
; ++i
)
1224 type_print (&s
->locals
[i
]);
1225 debug_print (" | %p\n", s
);
1229 debug_print_state (state
*s ATTRIBUTE_UNUSED
,
1230 const char *leader ATTRIBUTE_UNUSED
,
1231 int pc ATTRIBUTE_UNUSED
, int max_stack ATTRIBUTE_UNUSED
,
1232 int max_locals ATTRIBUTE_UNUSED
)
1235 #endif /* VERIFY_DEBUG */
1241 state
*s
= vfr
->current_state
;
1242 if (s
->stacktop
<= 0)
1243 verify_fail ("stack empty");
1244 r
= s
->stack
[--s
->stacktop
];
1245 s
->stackdepth
-= type_depth (&r
);
1246 if (s
->stackdepth
< 0)
1247 verify_fail_pc ("stack empty", vfr
->start_PC
);
1254 type r
= pop_raw ();
1255 if (type_iswide (&r
))
1256 verify_fail ("narrow pop of wide type");
1261 vfy_pop_type_t (type match
)
1264 vfy_promote_type (&match
);
1266 if (! types_compatible (&match
, &t
))
1267 verify_fail ("incompatible type on stack");
1272 vfy_pop_type (type_val match
)
1274 type t
= make_type (match
);
1275 return vfy_pop_type_t (t
);
1278 #define pop_type vfy_pop_type
1279 #define pop_type_t vfy_pop_type_t
1281 /* Pop a reference which is guaranteed to be initialized. MATCH
1282 doesn't have to be a reference type; in this case this acts like
1285 pop_init_ref_t (type match
)
1287 type t
= pop_raw ();
1288 if (type_isreference (&t
) && ! type_initialized (&t
))
1289 verify_fail ("initialized reference required");
1290 else if (! types_compatible (&match
, &t
))
1291 verify_fail ("incompatible type on stack");
1296 pop_init_ref (type_val match
)
1298 type t
= make_type (match
);
1299 return pop_init_ref_t (t
);
1302 /* Pop a reference type or a return address. */
1304 pop_ref_or_return (void)
1306 type t
= pop_raw ();
1307 if (! type_isreference (&t
) && t
.key
!= return_address_type
)
1308 verify_fail ("expected reference or return address on stack");
1313 vfy_push_type_t (type t
)
1316 state
*s
= vfr
->current_state
;
1317 /* If T is a numeric type like short, promote it to int. */
1320 depth
= type_depth (&t
);
1322 if (s
->stackdepth
+ depth
> vfr
->current_method
->max_stack
)
1323 verify_fail ("stack overflow");
1324 s
->stack
[s
->stacktop
++] = t
;
1325 s
->stackdepth
+= depth
;
1329 vfy_push_type (type_val tval
)
1331 type t
= make_type (tval
);
1332 vfy_push_type_t (t
);
1335 #define push_type vfy_push_type
1336 #define push_type_t vfy_push_type_t
1339 set_variable (int index
, type t
)
1342 state
*s
= vfr
->current_state
;
1343 /* If T is a numeric type like short, promote it to int. */
1346 depth
= type_depth (&t
);
1347 if (index
> vfr
->current_method
->max_locals
- depth
)
1348 verify_fail ("invalid local variable");
1349 s
->locals
[index
] = t
;
1352 init_type_from_tag (&s
->locals
[index
+ 1], continuation_type
);
1353 if (index
> 0 && type_iswide (&s
->locals
[index
- 1]))
1354 init_type_from_tag (&s
->locals
[index
- 1], unsuitable_type
);
1358 get_variable_t (int index
, type
*t
)
1360 state
*s
= vfr
->current_state
;
1361 int depth
= type_depth (t
);
1362 if (index
> vfr
->current_method
->max_locals
- depth
)
1363 verify_fail ("invalid local variable");
1364 if (! types_compatible (t
, &s
->locals
[index
]))
1365 verify_fail ("incompatible type in local variable");
1368 type cont
= make_type (continuation_type
);
1369 if (! types_compatible (&s
->locals
[index
+ 1], &cont
))
1370 verify_fail ("invalid local variable");
1372 return s
->locals
[index
];
1376 get_variable (int index
, type_val v
)
1378 type t
= make_type (v
);
1379 return get_variable_t (index
, &t
);
1382 /* Make sure ARRAY is an array type and that its elements are
1383 compatible with type ELEMENT. Returns the actual element type. */
1385 require_array_type_t (type array
, type element
)
1388 /* An odd case. Here we just pretend that everything went ok. If
1389 the requested element type is some kind of reference, return
1390 the null type instead. */
1391 if (type_isnull (&array
))
1392 return type_isreference (&element
) ? make_type (null_type
) : element
;
1394 if (! type_isarray (&array
))
1395 verify_fail ("array required");
1397 t
= type_array_element (&array
);
1398 if (! types_compatible (&element
, &t
))
1400 /* Special case for byte arrays, which must also be boolean
1403 if (element
.key
== byte_type
)
1405 type e2
= make_type (boolean_type
);
1406 ok
= types_compatible (&e2
, &t
);
1409 verify_fail ("incompatible array element type");
1412 /* Return T and not ELEMENT, because T might be specialized. */
1417 require_array_type (type array
, type_val element
)
1419 type t
= make_type (element
);
1420 return require_array_type_t (array
, t
);
1426 if (vfr
->PC
>= vfr
->current_method
->code_length
)
1427 verify_fail ("premature end of bytecode");
1428 return (jint
) vfr
->bytecode
[vfr
->PC
++] & 0xff;
1434 jint b1
= get_byte ();
1435 jint b2
= get_byte ();
1436 return (jint
) ((b1
<< 8) | b2
) & 0xffff;
1442 jint b1
= get_byte ();
1443 jint b2
= get_byte ();
1444 jshort s
= (b1
<< 8) | b2
;
1451 jint b1
= get_byte ();
1452 jint b2
= get_byte ();
1453 jint b3
= get_byte ();
1454 jint b4
= get_byte ();
1455 return (b1
<< 24) | (b2
<< 16) | (b3
<< 8) | b4
;
1459 compute_jump (int offset
)
1461 int npc
= vfr
->start_PC
+ offset
;
1462 if (npc
< 0 || npc
>= vfr
->current_method
->code_length
)
1463 verify_fail_pc ("branch out of range", vfr
->start_PC
);
1467 /* Add a new state to the state list at NPC. */
1469 add_new_state (int npc
, state
*old_state
)
1472 vfy_method
*current_method
= vfr
->current_method
;
1473 state
*new_state
= make_state_copy (old_state
, current_method
->max_stack
,
1474 current_method
->max_locals
);
1475 debug_print ("== New state in add_new_state\n");
1476 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1477 current_method
->max_locals
);
1479 nlink
= vfy_alloc (sizeof (state_list
));
1480 nlink
->val
= new_state
;
1481 nlink
->next
= vfr
->states
[npc
];
1482 vfr
->states
[npc
] = nlink
;
1483 new_state
->pc
= npc
;
1487 /* Merge the indicated state into the state at the branch target and
1488 schedule a new PC if there is a change. NPC is the PC of the
1489 branch target, and FROM_STATE is the state at the source of the
1490 branch. This method returns true if the destination state
1491 changed and requires reverification, false otherwise. */
1493 merge_into (int npc
, state
*from_state
)
1495 /* Iterate over all target states and merge our state into each,
1496 if applicable. FIXME one improvement we could make here is
1497 "state destruction". Merging a new state into an existing one
1498 might cause a return_address_type to be merged to
1499 unsuitable_type. In this case the resulting state may now be
1500 mergeable with other states currently held in parallel at this
1501 location. So in this situation we could pairwise compare and
1502 reduce the number of parallel states. */
1504 bool applicable
= false;
1505 for (iter
= vfr
->states
[npc
]; iter
!= NULL
; iter
= iter
->next
)
1507 state
*new_state
= iter
->val
;
1508 vfy_method
*current_method
= vfr
->current_method
;
1510 if (state_mergeable_p (new_state
, from_state
,
1511 current_method
->max_locals
))
1516 debug_print ("== Merge states in merge_into\n");
1517 debug_print_state (from_state
, "Frm", vfr
->start_PC
, current_method
->max_stack
,
1518 current_method
->max_locals
);
1519 debug_print_state (new_state
, " To", npc
, current_method
->max_stack
,
1520 current_method
->max_locals
);
1521 changed
= merge_states (new_state
, from_state
,
1522 current_method
->max_locals
);
1523 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1524 current_method
->max_locals
);
1527 state_reverify (new_state
);
1533 /* Either we don't yet have a state at NPC, or we have a
1534 return-address type that is in conflict with all existing
1535 state. So, we need to create a new entry. */
1536 state
*new_state
= add_new_state (npc
, from_state
);
1537 /* A new state added in this way must always be reverified. */
1538 state_reverify (new_state
);
1543 push_jump (int offset
)
1545 int npc
= compute_jump (offset
);
1546 /* According to the JVM Spec, we need to check for uninitialized
1547 objects here. However, this does not actually affect type
1548 safety, and the Eclipse java compiler generates code that
1549 violates this constraint. */
1550 merge_into (npc
, vfr
->current_state
);
1554 push_exception_jump (type t
, int pc
)
1557 /* According to the JVM Spec, we need to check for uninitialized
1558 objects here. However, this does not actually affect type
1559 safety, and the Eclipse java compiler generates code that
1560 violates this constraint. */
1561 copy_state_with_stack (&s
, vfr
->current_state
,
1562 vfr
->current_method
->max_stack
,
1563 vfr
->current_method
->max_locals
);
1564 if (vfr
->current_method
->max_stack
< 1)
1565 verify_fail ("stack overflow at exception handler");
1566 state_set_exception (&s
, &t
, vfr
->current_method
->max_stack
);
1567 merge_into (pc
, &s
);
1568 /* FIXME: leak.. need free_state or GC */
1574 state
*new_state
= vfr
->next_verify_state
;
1575 if (new_state
== INVALID_STATE
)
1576 verify_fail ("programmer error in pop_jump");
1577 if (new_state
!= NULL
)
1579 vfr
->next_verify_state
= new_state
->next
;
1580 new_state
->next
= INVALID_STATE
;
1586 invalidate_pc (void)
1592 note_branch_target (int pc
)
1594 /* Don't check `pc <= PC', because we've advanced PC after
1595 fetching the target and we haven't yet checked the next
1597 if (pc
< vfr
->PC
&& ! (vfr
->flags
[pc
] & FLAG_INSN_START
))
1598 verify_fail_pc ("branch not to instruction start", vfr
->start_PC
);
1599 vfr
->flags
[pc
] |= FLAG_BRANCH_TARGET
;
1605 while ((vfr
->PC
% 4) > 0)
1606 if (get_byte () != 0)
1607 verify_fail ("found nonzero padding byte");
1610 /* Do the work for a `ret' instruction. INDEX is the index into the
1613 handle_ret_insn (int index
)
1615 type ret
= make_type (return_address_type
);
1616 type ret_addr
= get_variable_t (index
, &ret
);
1617 /* It would be nice if we could do this. However, the JVM Spec
1618 doesn't say that this is what happens. It is implied that
1619 reusing a return address is invalid, but there's no actual
1620 prohibition against it. */
1621 /* set_variable (index, unsuitable_type); */
1623 int npc
= type_get_pc (&ret_addr
);
1624 /* We might be returning to a `jsr' that is at the end of the
1625 bytecode. This is ok if we never return from the called
1626 subroutine, but if we see this here it is an error. */
1627 if (npc
>= vfr
->current_method
->code_length
)
1628 verify_fail ("fell off end");
1630 /* According to the JVM Spec, we need to check for uninitialized
1631 objects here. However, this does not actually affect type
1632 safety, and the Eclipse java compiler generates code that
1633 violates this constraint. */
1634 merge_into (npc
, vfr
->current_state
);
1638 static void handle_jsr_insn (int offset
)
1641 int npc
= compute_jump (offset
);
1643 /* According to the JVM Spec, we need to check for uninitialized
1644 objects here. However, this does not actually affect type
1645 safety, and the Eclipse java compiler generates code that
1646 violates this constraint. */
1648 /* Modify our state as appropriate for entry into a subroutine. */
1649 ret_addr
= make_type (return_address_type
);
1650 type_set_return_address (&ret_addr
, vfr
->PC
);
1651 vfy_push_type_t (ret_addr
);
1652 merge_into (npc
, vfr
->current_state
);
1657 construct_primitive_array_type (type_val prim
)
1659 vfy_jclass k
= NULL
;
1670 k
= vfy_get_primitive_type ((int) prim
);
1673 /* These aren't used here but we call them out to avoid
1676 case unsuitable_type
:
1677 case return_address_type
:
1678 case continuation_type
:
1679 case reference_type
:
1681 case uninitialized_reference_type
:
1683 verify_fail ("unknown type in construct_primitive_array_type");
1685 k
= vfy_get_array_class (k
);
1689 /* This pass computes the location of branch targets and also
1690 instruction starts. */
1692 branch_prepass (void)
1695 vfr
->flags
= (char *) vfy_alloc (vfr
->current_method
->code_length
);
1697 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
1701 while (vfr
->PC
< vfr
->current_method
->code_length
)
1704 /* Set `start_PC' early so that error checking can have the
1706 vfr
->start_PC
= vfr
->PC
;
1707 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_START
;
1709 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
1713 case op_aconst_null
:
1849 case op_monitorenter
:
1850 case op_monitorexit
:
1858 case op_arraylength
:
1890 case op_invokespecial
:
1891 case op_invokestatic
:
1892 case op_invokevirtual
:
1896 case op_multianewarray
:
1919 note_branch_target (compute_jump (get_short ()));
1922 case op_tableswitch
:
1926 note_branch_target (compute_jump (get_int ()));
1930 verify_fail_pc ("invalid tableswitch", vfr
->start_PC
);
1931 for (i
= low
; i
<= hi
; ++i
)
1932 note_branch_target (compute_jump (get_int ()));
1936 case op_lookupswitch
:
1940 note_branch_target (compute_jump (get_int ()));
1941 npairs
= get_int ();
1943 verify_fail_pc ("too few pairs in lookupswitch", vfr
->start_PC
);
1944 while (npairs
-- > 0)
1947 note_branch_target (compute_jump (get_int ()));
1952 case op_invokeinterface
:
1960 opcode
= (java_opcode
) get_byte ();
1962 if (opcode
== op_iinc
)
1969 note_branch_target (compute_jump (get_int ()));
1973 /* These are unused here, but we call them out explicitly
1974 so that -Wswitch-enum doesn't complain. */
1980 case op_putstatic_1
:
1981 case op_putstatic_2
:
1982 case op_putstatic_4
:
1983 case op_putstatic_8
:
1984 case op_putstatic_a
:
1986 case op_getfield_2s
:
1987 case op_getfield_2u
:
1991 case op_getstatic_1
:
1992 case op_getstatic_2s
:
1993 case op_getstatic_2u
:
1994 case op_getstatic_4
:
1995 case op_getstatic_8
:
1996 case op_getstatic_a
:
1997 #endif /* VFY_FAST_OPCODES */
1999 verify_fail_pc ("unrecognized instruction in branch_prepass",
2003 /* See if any previous branch tried to branch to the middle of
2004 this instruction. */
2005 for (pc
= vfr
->start_PC
+ 1; pc
< vfr
->PC
; ++pc
)
2007 if ((vfr
->flags
[pc
] & FLAG_BRANCH_TARGET
))
2008 verify_fail_pc ("branch to middle of instruction", pc
);
2012 /* Verify exception handlers. */
2013 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
2015 int handler
, start
, end
, htype
;
2016 vfy_get_exception (vfr
->exception
, i
, &handler
, &start
, &end
, &htype
);
2017 if (! (vfr
->flags
[handler
] & FLAG_INSN_START
))
2018 verify_fail_pc ("exception handler not at instruction start",
2020 if (! (vfr
->flags
[start
] & FLAG_INSN_START
))
2021 verify_fail_pc ("exception start not at instruction start", start
);
2022 if (end
!= vfr
->current_method
->code_length
2023 && ! (vfr
->flags
[end
] & FLAG_INSN_START
))
2024 verify_fail_pc ("exception end not at instruction start", end
);
2026 vfr
->flags
[handler
] |= FLAG_BRANCH_TARGET
;
2031 check_pool_index (int index
)
2033 if (index
< 0 || index
>= vfy_get_constants_size (vfr
->current_class
))
2034 verify_fail_pc ("constant pool index out of range", vfr
->start_PC
);
2038 check_class_constant (int index
)
2041 vfy_constants
*pool
;
2043 check_pool_index (index
);
2044 pool
= vfy_get_constants (vfr
->current_class
);
2045 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedClass
)
2046 init_type_from_class (&t
, vfy_get_pool_class (pool
, index
));
2047 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Class
)
2048 init_type_from_string (&t
, vfy_get_pool_string (pool
, index
));
2050 verify_fail_pc ("expected class constant", vfr
->start_PC
);
2055 check_constant (int index
)
2058 vfy_constants
*pool
;
2060 check_pool_index (index
);
2061 pool
= vfy_get_constants (vfr
->current_class
);
2062 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedString
2063 || vfy_tag (pool
, index
) == JV_CONSTANT_String
)
2064 init_type_from_class (&t
, vfy_string_type ());
2065 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Integer
)
2066 init_type_from_tag (&t
, int_type
);
2067 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Float
)
2068 init_type_from_tag (&t
, float_type
);
2070 verify_fail_pc ("String, int, or float constant expected", vfr
->start_PC
);
2075 check_wide_constant (int index
)
2078 vfy_constants
*pool
;
2080 check_pool_index (index
);
2081 pool
= vfy_get_constants (vfr
->current_class
);
2082 if (vfy_tag (pool
, index
) == JV_CONSTANT_Long
)
2083 init_type_from_tag (&t
, long_type
);
2084 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Double
)
2085 init_type_from_tag (&t
, double_type
);
2087 verify_fail_pc ("long or double constant expected", vfr
->start_PC
);
2091 /* Helper for both field and method. These are laid out the same in
2092 the constant pool. */
2094 handle_field_or_method (int index
, int expected
,
2095 vfy_string
*name
, vfy_string
*fmtype
)
2097 vfy_uint_16 class_index
, name_and_type_index
;
2098 vfy_uint_16 name_index
, desc_index
;
2099 vfy_constants
*pool
;
2101 check_pool_index (index
);
2102 pool
= vfy_get_constants (vfr
->current_class
);
2103 if (vfy_tag (pool
, index
) != expected
)
2104 verify_fail_pc ("didn't see expected constant", vfr
->start_PC
);
2105 /* Once we know we have a Fieldref or Methodref we assume that it
2106 is correctly laid out in the constant pool. I think the code
2107 in defineclass.cc guarantees this. */
2108 vfy_load_indexes (pool
, index
, &class_index
, &name_and_type_index
);
2109 vfy_load_indexes (pool
, name_and_type_index
, &name_index
, &desc_index
);
2111 *name
= vfy_get_pool_string (pool
, name_index
);
2112 *fmtype
= vfy_get_pool_string (pool
, desc_index
);
2114 return check_class_constant (class_index
);
2117 /* Return field's type, compute class' type if requested. */
2119 check_field_constant (int index
, type
*class_type
)
2121 vfy_string name
, field_type
;
2126 type ct
= handle_field_or_method (index
,
2127 JV_CONSTANT_Fieldref
,
2128 &name
, &field_type
);
2131 typec
= vfy_string_bytes (field_type
);
2132 len
= vfy_string_length (field_type
);
2133 if (typec
[0] == '[' || typec
[0] == 'L')
2134 init_type_from_string (&t
, field_type
);
2136 init_type_from_tag (&t
, get_type_val_for_signature (typec
[0]));
2141 check_method_constant (int index
, bool is_interface
,
2142 vfy_string
*method_name
,
2143 vfy_string
*method_signature
)
2145 return handle_field_or_method (index
,
2147 ? JV_CONSTANT_InterfaceMethodref
2148 : JV_CONSTANT_Methodref
),
2149 method_name
, method_signature
);
2153 get_one_type (char *p
, type
*t
)
2155 const char *start
= p
;
2175 name
= vfy_get_string (start
, p
- start
);
2176 *t
= make_type_from_string (name
);
2180 /* Casting to jchar here is ok since we are looking at an ASCII
2182 rt
= get_type_val_for_signature (v
);
2184 if (arraycount
== 0)
2186 /* Callers of this function eventually push their arguments on
2187 the stack. So, promote them here. */
2188 type new_t
= make_type (rt
);
2189 vfy_promote_type (&new_t
);
2194 k
= construct_primitive_array_type (rt
);
2195 while (--arraycount
> 0)
2196 k
= vfy_get_array_class (k
);
2197 *t
= make_type_from_class (k
);
2202 compute_argument_types (vfy_string signature
, type
*types
)
2205 char *p
= (char *) vfy_string_bytes (signature
);
2212 p
= get_one_type (p
, &types
[i
++]);
2216 compute_return_type (vfy_string signature
)
2218 char *p
= (char *) vfy_string_bytes (signature
);
2223 get_one_type (p
, &t
);
2228 check_return_type (type onstack
)
2230 type rt
= compute_return_type (vfy_get_signature (vfr
->current_method
));
2231 if (! types_compatible (&rt
, &onstack
))
2232 verify_fail ("incompatible return type");
2235 /* Initialize the stack for the new method. Returns true if this
2236 method is an instance initializer. */
2238 initialize_stack (void)
2242 bool is_init
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2244 bool is_clinit
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2247 if (! vfy_is_static (vfr
->current_method
))
2249 type kurr
= make_type_from_class (vfr
->current_class
);
2252 type_set_uninitialized (&kurr
, SELF
);
2256 verify_fail ("<clinit> method must be static");
2257 set_variable (0, kurr
);
2258 state_set_this_type (vfr
->current_state
, &kurr
);
2264 verify_fail ("<init> method must be non-static");
2267 /* We have to handle wide arguments specially here. */
2268 arg_count
= vfy_count_arguments (vfy_get_signature (vfr
->current_method
));
2270 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2271 compute_argument_types (vfy_get_signature (vfr
->current_method
), arg_types
);
2272 for (i
= 0; i
< arg_count
; ++i
)
2274 set_variable (var
, arg_types
[i
]);
2276 if (type_iswide (&arg_types
[i
]))
2279 vfy_free (arg_types
);
2286 verify_instructions_0 (void)
2291 vfr
->current_state
= make_state (vfr
->current_method
->max_stack
,
2292 vfr
->current_method
->max_locals
);
2297 /* True if we are verifying an instance initializer. */
2298 this_is_init
= initialize_stack ();
2300 vfr
->states
= (state_list
**) vfy_alloc (sizeof (state_list
*)
2301 * vfr
->current_method
->code_length
);
2303 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
2304 vfr
->states
[i
] = NULL
;
2306 vfr
->next_verify_state
= NULL
;
2312 /* If the PC was invalidated, get a new one from the work list. */
2313 if (vfr
->PC
== NO_NEXT
)
2315 state
*new_state
= pop_jump ();
2316 /* If it is null, we're done. */
2317 if (new_state
== NULL
)
2320 vfr
->PC
= state_get_pc (new_state
);
2321 debug_print ("== State pop from pending list\n");
2322 /* Set up the current state. */
2323 copy_state (vfr
->current_state
, new_state
,
2324 vfr
->current_method
->max_stack
, vfr
->current_method
->max_locals
);
2328 /* We only have to do this checking in the situation where
2329 control flow falls through from the previous
2330 instruction. Otherwise merging is done at the time we
2332 if (vfr
->states
[vfr
->PC
] != NULL
)
2334 /* We've already visited this instruction. So merge
2335 the states together. It is simplest, but not most
2336 efficient, to just always invalidate the PC here. */
2337 merge_into (vfr
->PC
, vfr
->current_state
);
2343 /* Control can't fall off the end of the bytecode. We need to
2344 check this in both cases, not just the fall-through case,
2345 because we don't check to see whether a `jsr' appears at
2346 the end of the bytecode until we process a `ret'. */
2347 if (vfr
->PC
>= vfr
->current_method
->code_length
)
2348 verify_fail ("fell off end");
2349 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_SEEN
;
2351 /* We only have to keep saved state at branch targets. If
2352 we're at a branch target and the state here hasn't been set
2353 yet, we set it now. You might notice that `ret' targets
2354 won't necessarily have FLAG_BRANCH_TARGET set. This
2355 doesn't matter, since those states will be filled in by
2357 /* Note that other parts of the compiler assume that there is a
2358 label with a type map at PC=0. */
2359 if (vfr
->states
[vfr
->PC
] == NULL
2360 && (vfr
->PC
== 0 || (vfr
->flags
[vfr
->PC
] & FLAG_BRANCH_TARGET
) != 0))
2361 add_new_state (vfr
->PC
, vfr
->current_state
);
2363 /* Set this before handling exceptions so that debug output is
2365 vfr
->start_PC
= vfr
->PC
;
2367 /* Update states for all active exception handlers. Ordinarily
2368 there are not many exception handlers. So we simply run
2369 through them all. */
2370 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
2372 int hpc
, start
, end
, htype
;
2373 vfy_get_exception (vfr
->exception
, i
, &hpc
, &start
, &end
, &htype
);
2374 if (vfr
->PC
>= start
&& vfr
->PC
< end
)
2376 type handler
= make_type_from_class (vfy_throwable_type ());
2378 handler
= check_class_constant (htype
);
2379 push_exception_jump (handler
, hpc
);
2384 debug_print_state (vfr
->current_state
, " ", vfr
->PC
,
2385 vfr
->current_method
->max_stack
,
2386 vfr
->current_method
->max_locals
);
2387 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
2393 case op_aconst_null
:
2394 push_type (null_type
);
2404 push_type (int_type
);
2409 push_type (long_type
);
2415 push_type (float_type
);
2420 push_type (double_type
);
2425 push_type (int_type
);
2430 push_type (int_type
);
2434 push_type_t (check_constant (get_byte ()));
2437 push_type_t (check_constant (get_ushort ()));
2440 push_type_t (check_wide_constant (get_ushort ()));
2444 push_type_t (get_variable (get_byte (), int_type
));
2447 push_type_t (get_variable (get_byte (), long_type
));
2450 push_type_t (get_variable (get_byte (), float_type
));
2453 push_type_t (get_variable (get_byte (), double_type
));
2456 push_type_t (get_variable (get_byte (), reference_type
));
2463 push_type_t (get_variable (opcode
- op_iload_0
, int_type
));
2469 push_type_t (get_variable (opcode
- op_lload_0
, long_type
));
2475 push_type_t (get_variable (opcode
- op_fload_0
, float_type
));
2481 push_type_t (get_variable (opcode
- op_dload_0
, double_type
));
2487 push_type_t (get_variable (opcode
- op_aload_0
, reference_type
));
2490 pop_type (int_type
);
2491 push_type_t (require_array_type (pop_init_ref (reference_type
),
2495 pop_type (int_type
);
2496 push_type_t (require_array_type (pop_init_ref (reference_type
),
2500 pop_type (int_type
);
2501 push_type_t (require_array_type (pop_init_ref (reference_type
),
2505 pop_type (int_type
);
2506 push_type_t (require_array_type (pop_init_ref (reference_type
),
2510 pop_type (int_type
);
2511 push_type_t (require_array_type (pop_init_ref (reference_type
),
2515 pop_type (int_type
);
2516 require_array_type (pop_init_ref (reference_type
), byte_type
);
2517 push_type (int_type
);
2520 pop_type (int_type
);
2521 require_array_type (pop_init_ref (reference_type
), char_type
);
2522 push_type (int_type
);
2525 pop_type (int_type
);
2526 require_array_type (pop_init_ref (reference_type
), short_type
);
2527 push_type (int_type
);
2530 set_variable (get_byte (), pop_type (int_type
));
2533 set_variable (get_byte (), pop_type (long_type
));
2536 set_variable (get_byte (), pop_type (float_type
));
2539 set_variable (get_byte (), pop_type (double_type
));
2542 set_variable (get_byte (), pop_ref_or_return ());
2548 set_variable (opcode
- op_istore_0
, pop_type (int_type
));
2554 set_variable (opcode
- op_lstore_0
, pop_type (long_type
));
2560 set_variable (opcode
- op_fstore_0
, pop_type (float_type
));
2566 set_variable (opcode
- op_dstore_0
, pop_type (double_type
));
2572 set_variable (opcode
- op_astore_0
, pop_ref_or_return ());
2575 pop_type (int_type
);
2576 pop_type (int_type
);
2577 require_array_type (pop_init_ref (reference_type
), int_type
);
2580 pop_type (long_type
);
2581 pop_type (int_type
);
2582 require_array_type (pop_init_ref (reference_type
), long_type
);
2585 pop_type (float_type
);
2586 pop_type (int_type
);
2587 require_array_type (pop_init_ref (reference_type
), float_type
);
2590 pop_type (double_type
);
2591 pop_type (int_type
);
2592 require_array_type (pop_init_ref (reference_type
), double_type
);
2595 pop_type (reference_type
);
2596 pop_type (int_type
);
2597 require_array_type (pop_init_ref (reference_type
), reference_type
);
2600 pop_type (int_type
);
2601 pop_type (int_type
);
2602 require_array_type (pop_init_ref (reference_type
), byte_type
);
2605 pop_type (int_type
);
2606 pop_type (int_type
);
2607 require_array_type (pop_init_ref (reference_type
), char_type
);
2610 pop_type (int_type
);
2611 pop_type (int_type
);
2612 require_array_type (pop_init_ref (reference_type
), short_type
);
2619 type t
= pop_raw ();
2620 if (! type_iswide (&t
))
2643 type t2
= pop_raw ();
2644 if (! type_iswide (&t2
))
2658 type t
= pop_raw ();
2659 if (! type_iswide (&t
))
2673 type t1
= pop_raw ();
2675 if (! type_iswide (&t1
))
2690 type t1
= pop_raw ();
2691 if (type_iswide (&t1
))
2693 type t2
= pop_raw ();
2694 if (type_iswide (&t2
))
2711 type t3
= pop_raw ();
2712 if (type_iswide (&t3
))
2749 pop_type (int_type
);
2750 push_type_t (pop_type (int_type
));
2760 pop_type (long_type
);
2761 push_type_t (pop_type (long_type
));
2766 pop_type (int_type
);
2767 push_type_t (pop_type (long_type
));
2774 pop_type (float_type
);
2775 push_type_t (pop_type (float_type
));
2782 pop_type (double_type
);
2783 push_type_t (pop_type (double_type
));
2789 push_type_t (pop_type (int_type
));
2792 push_type_t (pop_type (long_type
));
2795 push_type_t (pop_type (float_type
));
2798 push_type_t (pop_type (double_type
));
2801 get_variable (get_byte (), int_type
);
2805 pop_type (int_type
);
2806 push_type (long_type
);
2809 pop_type (int_type
);
2810 push_type (float_type
);
2813 pop_type (int_type
);
2814 push_type (double_type
);
2817 pop_type (long_type
);
2818 push_type (int_type
);
2821 pop_type (long_type
);
2822 push_type (float_type
);
2825 pop_type (long_type
);
2826 push_type (double_type
);
2829 pop_type (float_type
);
2830 push_type (int_type
);
2833 pop_type (float_type
);
2834 push_type (long_type
);
2837 pop_type (float_type
);
2838 push_type (double_type
);
2841 pop_type (double_type
);
2842 push_type (int_type
);
2845 pop_type (double_type
);
2846 push_type (long_type
);
2849 pop_type (double_type
);
2850 push_type (float_type
);
2853 pop_type (long_type
);
2854 pop_type (long_type
);
2855 push_type (int_type
);
2859 pop_type (float_type
);
2860 pop_type (float_type
);
2861 push_type (int_type
);
2865 pop_type (double_type
);
2866 pop_type (double_type
);
2867 push_type (int_type
);
2875 pop_type (int_type
);
2876 push_jump (get_short ());
2884 pop_type (int_type
);
2885 pop_type (int_type
);
2886 push_jump (get_short ());
2890 pop_type (reference_type
);
2891 pop_type (reference_type
);
2892 push_jump (get_short ());
2895 push_jump (get_short ());
2899 handle_jsr_insn (get_short ());
2902 handle_ret_insn (get_byte ());
2904 case op_tableswitch
:
2908 pop_type (int_type
);
2910 push_jump (get_int ());
2913 /* Already checked LOW -vs- HIGH. */
2914 for (i
= low
; i
<= high
; ++i
)
2915 push_jump (get_int ());
2920 case op_lookupswitch
:
2923 jint npairs
, lastkey
;
2925 pop_type (int_type
);
2927 push_jump (get_int ());
2928 npairs
= get_int ();
2929 /* Already checked NPAIRS >= 0. */
2931 for (i
= 0; i
< npairs
; ++i
)
2933 jint key
= get_int ();
2934 if (i
> 0 && key
<= lastkey
)
2935 verify_fail_pc ("lookupswitch pairs unsorted", vfr
->start_PC
);
2937 push_jump (get_int ());
2943 check_return_type (pop_type (int_type
));
2947 check_return_type (pop_type (long_type
));
2951 check_return_type (pop_type (float_type
));
2955 check_return_type (pop_type (double_type
));
2959 check_return_type (pop_init_ref (reference_type
));
2963 /* We only need to check this when the return type is
2964 void, because all instance initializers return void. */
2966 state_check_this_initialized (vfr
->current_state
);
2967 check_return_type (make_type (void_type
));
2971 push_type_t (check_field_constant (get_ushort (), NULL
));
2974 pop_type_t (check_field_constant (get_ushort (), NULL
));
2979 type field
= check_field_constant (get_ushort (), &klass
);
2981 push_type_t (field
);
2987 type field
= check_field_constant (get_ushort (), &klass
);
2990 /* We have an obscure special case here: we can use
2991 `putfield' on a field declared in this class, even if
2992 `this' has not yet been initialized. */
2993 if (! type_initialized (&vfr
->current_state
->this_type
)
2994 && vfr
->current_state
->this_type
.pc
== SELF
)
2995 type_set_uninitialized (&klass
, SELF
);
3000 case op_invokevirtual
:
3001 case op_invokespecial
:
3002 case op_invokestatic
:
3003 case op_invokeinterface
:
3005 vfy_string method_name
, method_signature
;
3009 bool is_init
= false;
3012 = check_method_constant (get_ushort (),
3013 opcode
== op_invokeinterface
,
3016 /* NARGS is only used when we're processing
3017 invokeinterface. It is simplest for us to compute it
3018 here and then verify it later. */
3020 if (opcode
== op_invokeinterface
)
3022 nargs
= get_byte ();
3023 if (get_byte () != 0)
3024 verify_fail ("invokeinterface dummy byte is wrong");
3027 namec
= vfy_string_bytes (method_name
);
3029 if (vfy_strings_equal (method_name
, vfy_init_name()))
3032 if (opcode
!= op_invokespecial
)
3033 verify_fail ("can't invoke <init>");
3035 else if (namec
[0] == '<')
3036 verify_fail ("can't invoke method starting with `<'");
3038 arg_count
= vfy_count_arguments (method_signature
);
3040 /* Pop arguments and check types. */
3041 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
3043 compute_argument_types (method_signature
, arg_types
);
3044 for (i
= arg_count
- 1; i
>= 0; --i
)
3046 /* This is only used for verifying the byte for
3048 nargs
-= type_depth (&arg_types
[i
]);
3049 pop_init_ref_t (arg_types
[i
]);
3052 vfy_free (arg_types
);
3055 if (opcode
== op_invokeinterface
3057 verify_fail ("wrong argument count for invokeinterface");
3059 if (opcode
!= op_invokestatic
)
3062 type t
= class_type
;
3065 /* In this case the PC doesn't matter. */
3066 type_set_uninitialized (&t
, UNINIT
);
3067 /* FIXME: check to make sure that the <init>
3068 call is to the right class.
3069 It must either be super or an exact class
3073 if (! types_compatible (&t
, &raw
))
3074 verify_fail ("incompatible type on stack");
3077 state_set_initialized (vfr
->current_state
,
3078 type_get_pc (&raw
), vfr
->current_method
->max_locals
);
3081 rt
= compute_return_type (method_signature
);
3082 if (! type_isvoid (&rt
))
3089 type t
= check_class_constant (get_ushort ());
3090 if (type_isarray (&t
) || type_isinterface (&t
)
3091 || type_isabstract (&t
))
3092 verify_fail ("type is array, interface, or abstract");
3093 type_set_uninitialized (&t
, vfr
->start_PC
);
3100 int atype
= get_byte ();
3102 /* We intentionally have chosen constants to make this
3104 if (atype
< boolean_type
|| atype
> long_type
)
3105 verify_fail_pc ("type not primitive", vfr
->start_PC
);
3106 pop_type (int_type
);
3107 init_type_from_class (&t
, construct_primitive_array_type (atype
));
3114 pop_type (int_type
);
3115 t
= check_class_constant (get_ushort ());
3116 push_type_t (type_to_array (&t
));
3119 case op_arraylength
:
3121 type t
= pop_init_ref (reference_type
);
3122 if (! type_isarray (&t
) && ! type_isnull (&t
))
3123 verify_fail ("array type expected");
3124 push_type (int_type
);
3128 pop_type_t (make_type_from_class (vfy_throwable_type ()));
3132 pop_init_ref (reference_type
);
3133 push_type_t (check_class_constant (get_ushort ()));
3136 pop_init_ref (reference_type
);
3137 check_class_constant (get_ushort ());
3138 push_type (int_type
);
3140 case op_monitorenter
:
3141 pop_init_ref (reference_type
);
3143 case op_monitorexit
:
3144 pop_init_ref (reference_type
);
3148 switch (get_byte ())
3151 push_type_t (get_variable (get_ushort (), int_type
));
3154 push_type_t (get_variable (get_ushort (), long_type
));
3157 push_type_t (get_variable (get_ushort (), float_type
));
3160 push_type_t (get_variable (get_ushort (), double_type
));
3163 push_type_t (get_variable (get_ushort (), reference_type
));
3166 set_variable (get_ushort (), pop_type (int_type
));
3169 set_variable (get_ushort (), pop_type (long_type
));
3172 set_variable (get_ushort (), pop_type (float_type
));
3175 set_variable (get_ushort (), pop_type (double_type
));
3178 set_variable (get_ushort (), pop_init_ref (reference_type
));
3181 handle_ret_insn (get_short ());
3184 get_variable (get_ushort (), int_type
);
3188 verify_fail_pc ("unrecognized wide instruction", vfr
->start_PC
);
3192 case op_multianewarray
:
3195 type atype
= check_class_constant (get_ushort ());
3196 int dim
= get_byte ();
3198 verify_fail_pc ("too few dimensions to multianewarray", vfr
->start_PC
);
3199 type_verify_dimensions (&atype
, dim
);
3200 for (i
= 0; i
< dim
; ++i
)
3201 pop_type (int_type
);
3202 push_type_t (atype
);
3207 pop_type (reference_type
);
3208 push_jump (get_short ());
3211 push_jump (get_int ());
3215 handle_jsr_insn (get_int ());
3219 /* These are unused here, but we call them out explicitly
3220 so that -Wswitch-enum doesn't complain. */
3226 case op_putstatic_1
:
3227 case op_putstatic_2
:
3228 case op_putstatic_4
:
3229 case op_putstatic_8
:
3230 case op_putstatic_a
:
3232 case op_getfield_2s
:
3233 case op_getfield_2u
:
3237 case op_getstatic_1
:
3238 case op_getstatic_2s
:
3239 case op_getstatic_2u
:
3240 case op_getstatic_4
:
3241 case op_getstatic_8
:
3242 case op_getstatic_a
:
3245 /* Unrecognized opcode. */
3246 verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3252 /* This turns a `type' into something suitable for use by the type map
3253 in the other parts of the compiler. In particular, reference types
3254 are mapped to Object, primitive types are unchanged, and other
3255 types are mapped using special functions declared in verify.h. */
3257 collapse_type (type
*t
)
3270 return vfy_get_primitive_type (t
->key
);
3272 case unsuitable_type
:
3273 case continuation_type
:
3274 return vfy_unsuitable_type ();
3276 case return_address_type
:
3277 return vfy_return_address_type ();
3280 return vfy_null_type ();
3282 case reference_type
:
3283 case uninitialized_reference_type
:
3284 return vfy_object_type ();
3291 verify_instructions (void)
3296 verify_instructions_0 ();
3298 /* Now tell the rest of the compiler about the types we've found. */
3299 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3304 if ((vfr
->flags
[i
] & FLAG_INSN_SEEN
) != 0)
3305 vfy_note_instruction_seen (i
);
3307 if (! vfr
->states
[i
])
3310 curr
= vfr
->states
[i
]->val
;
3311 vfy_note_stack_depth (vfr
->current_method
, i
, curr
->stackdepth
);
3313 /* Tell the compiler about each local variable. */
3314 for (j
= 0; j
< vfr
->current_method
->max_locals
; ++j
)
3315 vfy_note_local_type (vfr
->current_method
, i
, j
,
3316 collapse_type (&curr
->locals
[j
]));
3317 /* Tell the compiler about each stack slot. */
3318 for (slot
= j
= 0; j
< curr
->stacktop
; ++j
, ++slot
)
3320 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3321 collapse_type (&curr
->stack
[j
]));
3322 if (type_iswide (&curr
->stack
[j
]))
3325 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3326 vfy_unsuitable_type ());
3329 if (slot
!= curr
->stackdepth
)
3335 _Jv_BytecodeVerifier (_Jv_InterpMethod
*m
)
3337 /* We just print the text as utf-8. This is just for debugging
3339 debug_print ("--------------------------------\n");
3340 debug_print ("-- Verifying method `%s'\n", m
->self
->name
->chars());
3346 make_verifier_context (vfy_method
*m
)
3348 vfr
= (verifier_context
*) vfy_alloc (sizeof (struct verifier_context
));
3350 vfr
->current_method
= m
;
3351 vfr
->bytecode
= vfy_get_bytecode (m
);
3352 vfr
->exception
= vfy_get_exceptions (m
);
3353 vfr
->current_class
= m
->defining_class
;
3357 vfr
->utf8_list
= NULL
;
3358 vfr
->isect_list
= NULL
;
3362 free_verifier_context (void)
3364 vfy_string_list
*utf8_list
;
3365 ref_intersection
*isect_list
;
3368 vfy_free (vfr
->flags
);
3370 utf8_list
= vfr
->utf8_list
;
3371 while (utf8_list
!= NULL
)
3373 vfy_string_list
*n
= utf8_list
->next
;
3374 vfy_free (utf8_list
);
3378 isect_list
= vfr
->isect_list
;
3379 while (isect_list
!= NULL
)
3381 ref_intersection
*next
= isect_list
->alloc_next
;
3382 vfy_free (isect_list
);
3386 if (vfr
->states
!= NULL
)
3389 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3391 state_list
*iter
= vfr
->states
[i
];
3392 while (iter
!= NULL
)
3394 state_list
*next
= iter
->next
;
3395 vfy_free (iter
->val
);
3400 vfy_free (vfr
->states
);
3407 verify_method (vfy_method
*meth
)
3409 debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth
->name
),
3413 verify_fail ("verifier re-entered");
3415 make_verifier_context (meth
);
3416 verify_instructions ();
3417 free_verifier_context ();