1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009
2 Free Software Foundation
4 This file is part of libgcj.
6 This software is copyrighted work licensed under the terms of the
7 Libgcj License. Please consult the file "LIBGCJ_LICENSE" for
10 /* Written by Tom Tromey <tromey@redhat.com> */
12 /* Uncomment this to enable debugging output. */
13 /* #define VERIFY_DEBUG */
19 /* Hack to work around namespace pollution from java-tree.h. */
24 #endif /* VERIFY_DEBUG */
26 /* This is used to mark states which are not scheduled for
28 #define INVALID_STATE ((state *) -1)
30 static void ATTRIBUTE_PRINTF_1
31 debug_print (const char *fmt ATTRIBUTE_UNUSED
, ...)
36 vfprintf (stderr
, fmt
, ap
);
38 #endif /* VERIFY_DEBUG */
41 /* This started as a fairly ordinary verifier, and for the most part
42 it remains so. It works in the obvious way, by modeling the effect
43 of each opcode as it is encountered. For most opcodes, this is a
44 straightforward operation.
46 This verifier does not do type merging. It used to, but this
47 results in difficulty verifying some relatively simple code
48 involving interfaces, and it pushed some verification work into the
51 Instead of merging reference types, when we reach a point where two
52 flows of control merge, we simply keep the union of reference types
53 from each branch. Then, when we need to verify a fact about a
54 reference on the stack (e.g., that it is compatible with the
55 argument type of a method), we check to ensure that all possible
56 types satisfy the requirement.
58 Another area this verifier differs from the norm is in its handling
59 of subroutines. The JVM specification has some confusing things to
60 say about subroutines. For instance, it makes claims about not
61 allowing subroutines to merge and it rejects recursive subroutines.
62 For the most part these are red herrings; we used to try to follow
63 these things but they lead to problems. For example, the notion of
64 "being in a subroutine" is not well-defined: is an exception
65 handler in a subroutine? If you never execute the `ret' but
66 instead `goto 1' do you remain in the subroutine?
68 For clarity on what is really required for type safety, read
69 "Simple Verification Technique for Complex Java Bytecode
70 Subroutines" by Alessandro Coglio. Among other things this paper
71 shows that recursive subroutines are not harmful to type safety.
72 We implement something similar to what he proposes. Note that this
73 means that this verifier will accept code that is rejected by some
76 For those not wanting to read the paper, the basic observation is
77 that we can maintain split states in subroutines. We maintain one
78 state for each calling `jsr'. In other words, we re-verify a
79 subroutine once for each caller, using the exact types held by the
80 callers (as opposed to the old approach of merging types and
81 keeping a bitmap registering what did or did not change). This
82 approach lets us continue to verify correctly even when a
83 subroutine is exited via `goto' or `athrow' and not `ret'.
85 In some other areas the JVM specification is (mildly) incorrect,
86 so we diverge. For instance, you cannot
87 violate type safety by allocating an object with `new' and then
88 failing to initialize it, no matter how one branches or where one
89 stores the uninitialized reference. See "Improving the official
90 specification of Java bytecode verification" by Alessandro Coglio.
92 Note that there's no real point in enforcing that padding bytes or
93 the mystery byte of invokeinterface must be 0, but we do that
96 The verifier is currently neither completely lazy nor eager when it
97 comes to loading classes. It tries to represent types by name when
98 possible, and then loads them when it needs to verify a fact about
99 the type. Checking types by name is valid because we only use
100 names which come from the current class' constant pool. Since all
101 such names are looked up using the same class loader, there is no
102 danger that we might be fooled into comparing different types with
105 In the future we plan to allow for a completely lazy mode of
106 operation, where the verifier will construct a list of type
107 assertions to be checked later.
109 Some test cases for the verifier live in the "verify" module of the
110 Mauve test suite. However, some of these are presently
111 (2004-01-20) believed to be incorrect. (More precisely the notion
112 of "correct" is not well-defined, and this verifier differs from
113 others while remaining type-safe.) Some other tests live in the
116 This verifier is also written to be pluggable. This means that it
117 is intended for use in a variety of environments, not just libgcj.
118 As a result the verifier expects a number of type and method
119 declarations to be declared in "verify.h". The intent is that you
120 recompile the verifier for your particular environment. This
121 approach was chosen so that operations could be inlined in verify.h
124 See the verify.h that accompanies this copy of the verifier to see
125 what types, preprocessor defines, and functions must be declared.
126 The interface is ad hoc, but was defined so that it could be
127 implemented to connect to a pure C program.
130 #define FLAG_INSN_START 1
131 #define FLAG_BRANCH_TARGET 2
132 #define FLAG_INSN_SEEN 4
136 struct ref_intersection
;
138 typedef struct state state
;
139 typedef struct type type
;
140 typedef struct ref_intersection ref_intersection
;
142 /*typedef struct state_list state_list;*/
144 typedef struct state_list
147 struct state_list
*next
;
150 typedef struct vfy_string_list
153 struct vfy_string_list
*next
;
156 typedef struct verifier_context
158 /* The current PC. */
160 /* The PC corresponding to the start of the current instruction. */
163 /* The current state of the stack, locals, etc. */
164 state
*current_state
;
166 /* At each branch target we keep a linked list of all the states we
167 can process at that point. We'll only have multiple states at a
168 given PC if they both have different return-address types in the
169 same stack or local slot. This array is indexed by PC and holds
170 the list of all such states. */
173 /* We keep a linked list of all the states which we must reverify.
174 This is the head of the list. */
175 state
*next_verify_state
;
177 /* We keep some flags for each instruction. The values are the
178 FLAG_* constants defined above. This is an array indexed by PC. */
181 /* The bytecode itself. */
182 const unsigned char *bytecode
;
183 /* The exceptions. */
184 vfy_exception
*exception
;
186 /* Defining class. */
187 vfy_jclass current_class
;
189 vfy_method
*current_method
;
191 /* A linked list of utf8 objects we allocate. */
192 vfy_string_list
*utf8_list
;
194 /* A linked list of all ref_intersection objects we allocate. */
195 ref_intersection
*isect_list
;
198 /* The current verifier's state data. This is maintained by
199 {push/pop}_verifier_context to provide a shorthand form to access
200 the verification state. */
201 static GTY(()) verifier_context
*vfr
;
203 /* Local function declarations. */
204 bool type_initialized (type
*t
);
205 int ref_count_dimensions (ref_intersection
*ref
);
208 verify_fail_pc (const char *s
, int pc
)
210 vfy_fail (s
, pc
, vfr
->current_class
, vfr
->current_method
);
214 verify_fail (const char *s
)
216 verify_fail_pc (s
, vfr
->PC
);
219 /* This enum holds a list of tags for all the different types we
220 need to handle. Reference types are treated specially by the
222 typedef enum type_val
226 /* The values for primitive types are chosen to correspond to values
227 specified to newarray. */
237 /* Used when overwriting second word of a double or long in the
238 local variables. Also used after merging local variable states
239 to indicate an unusable value. */
242 /* This is the second word of a two-word value, i.e., a double or
246 /* Everything after `reference_type' must be a reference type. */
249 uninitialized_reference_type
252 /* This represents a merged class type. Some verifiers (including
253 earlier versions of this one) will compute the intersection of
254 two class types when merging states. However, this loses
255 critical information about interfaces implemented by the various
256 classes. So instead we keep track of all the actual classes that
258 struct ref_intersection
260 /* Whether or not this type has been resolved. */
263 /* Actual type data. */
266 /* For a resolved reference type, this is a pointer to the class. */
268 /* For other reference types, this it the name of the class. */
272 /* Link to the next reference in the intersection. */
273 ref_intersection
*ref_next
;
275 /* This is used to keep track of all the allocated
276 ref_intersection objects, so we can free them.
277 FIXME: we should allocate these in chunks. */
278 ref_intersection
*alloc_next
;
281 static ref_intersection
*
284 ref_intersection
*new_ref
=
285 (ref_intersection
*) vfy_alloc (sizeof (ref_intersection
));
287 new_ref
->alloc_next
= vfr
->isect_list
;
288 vfr
->isect_list
= new_ref
;
292 static ref_intersection
*
293 clone_ref (ref_intersection
*dup
)
295 ref_intersection
*new_ref
= make_ref ();
297 new_ref
->is_resolved
= dup
->is_resolved
;
298 new_ref
->data
= dup
->data
;
303 resolve_ref (ref_intersection
*ref
)
305 if (ref
->is_resolved
)
307 ref
->data
.klass
= vfy_find_class (vfr
->current_class
, ref
->data
.name
);
308 ref
->is_resolved
= true;
312 refs_equal (ref_intersection
*ref1
, ref_intersection
*ref2
)
314 if (! ref1
->is_resolved
&& ! ref2
->is_resolved
315 && vfy_strings_equal (ref1
->data
.name
, ref2
->data
.name
))
317 if (! ref1
->is_resolved
)
319 if (! ref2
->is_resolved
)
321 return ref1
->data
.klass
== ref2
->data
.klass
;
324 /* Merge REF1 type into REF2, returning the result. This will
325 return REF2 if all the classes in THIS already appear in
327 static ref_intersection
*
328 merge_refs (ref_intersection
*ref1
, ref_intersection
*ref2
)
330 ref_intersection
*tail
= ref2
;
331 for (; ref1
!= NULL
; ref1
= ref1
->ref_next
)
334 ref_intersection
*iter
;
335 for (iter
= ref2
; iter
!= NULL
; iter
= iter
->ref_next
)
337 if (refs_equal (ref1
, iter
))
346 ref_intersection
*new_tail
= clone_ref (ref1
);
347 new_tail
->ref_next
= tail
;
354 /* See if an object of type SOURCE can be assigned to an object of
355 type TARGET. This might resolve classes in one chain or the other. */
357 ref_compatible (ref_intersection
*target
, ref_intersection
*source
)
359 for (; target
!= NULL
; target
= target
->ref_next
)
361 ref_intersection
*source_iter
= source
;
363 for (; source_iter
!= NULL
; source_iter
= source_iter
->ref_next
)
365 /* Avoid resolving if possible. */
366 if (! target
->is_resolved
367 && ! source_iter
->is_resolved
368 && vfy_strings_equal (target
->data
.name
,
369 source_iter
->data
.name
))
372 if (! target
->is_resolved
)
373 resolve_ref (target
);
374 if (! source_iter
->is_resolved
)
375 resolve_ref (source_iter
);
377 if (! vfy_is_assignable_from (target
->data
.klass
,
378 source_iter
->data
.klass
))
387 ref_isarray (ref_intersection
*ref
)
389 /* assert (ref_next == NULL); */
390 if (ref
->is_resolved
)
391 return vfy_is_array (ref
->data
.klass
);
393 return vfy_string_bytes (ref
->data
.name
)[0] == '[';
397 ref_isinterface (ref_intersection
*ref
)
399 /* assert (ref_next == NULL); */
400 if (! ref
->is_resolved
)
402 return vfy_is_interface (ref
->data
.klass
);
406 ref_isabstract (ref_intersection
*ref
)
408 /* assert (ref_next == NULL); */
409 if (! ref
->is_resolved
)
411 return vfy_is_abstract (ref
->data
.klass
);
415 ref_getclass (ref_intersection
*ref
)
417 if (! ref
->is_resolved
)
419 return ref
->data
.klass
;
423 ref_count_dimensions (ref_intersection
*ref
)
426 if (ref
->is_resolved
)
428 vfy_jclass k
= ref
->data
.klass
;
429 while (vfy_is_array (k
))
431 k
= vfy_get_component_type (k
);
437 const char *p
= vfy_string_bytes (ref
->data
.name
);
444 /* Return the type_val corresponding to a primitive signature
445 character. For instance `I' returns `int.class'. */
447 get_type_val_for_signature (char sig
)
480 verify_fail ("invalid signature");
486 /* Return the type_val corresponding to a primitive class. */
488 get_type_val_for_primtype (vfy_jclass k
)
490 return get_type_val_for_signature (vfy_get_primitive_char (k
));
493 /* The `type' class is used to represent a single type in the verifier. */
499 /* For reference types, the representation of the type. */
500 ref_intersection
*klass
;
502 /* This is used in two situations.
504 First, when constructing a new object, it is the PC of the
505 `new' instruction which created the object. We use the special
506 value UNINIT to mean that this is uninitialized. The special
507 value SELF is used for the case where the current method is
508 itself the <init> method. the special value EITHER is used
509 when we may optionally allow either an uninitialized or
510 initialized reference to match.
512 Second, when the key is return_address_type, this holds the PC
513 of the instruction following the `jsr'. */
521 /* Make a new instance given the type tag. We assume a generic
522 `reference_type' means Object. */
524 init_type_from_tag (type
*t
, type_val k
)
527 /* For reference_type, if KLASS==NULL then that means we are
528 looking for a generic object of any kind, including an
529 uninitialized reference. */
534 /* Make a type for the given type_val tag K. */
536 make_type (type_val k
)
539 init_type_from_tag (&t
, k
);
543 /* Make a new instance given a class. */
545 init_type_from_class (type
*t
, vfy_jclass k
)
547 t
->key
= reference_type
;
548 t
->klass
= make_ref ();
549 t
->klass
->is_resolved
= true;
550 t
->klass
->data
.klass
= k
;
551 t
->klass
->ref_next
= NULL
;
556 make_type_from_class (vfy_jclass k
)
559 init_type_from_class (&t
, k
);
564 init_type_from_string (type
*t
, vfy_string n
)
566 t
->key
= reference_type
;
567 t
->klass
= make_ref ();
568 t
->klass
->is_resolved
= false;
569 t
->klass
->data
.name
= n
;
570 t
->klass
->ref_next
= NULL
;
575 make_type_from_string (vfy_string n
)
578 init_type_from_string (&t
, n
);
582 /* Promote a numeric type. */
584 vfy_promote_type (type
*t
)
586 if (t
->key
== boolean_type
|| t
->key
== char_type
587 || t
->key
== byte_type
|| t
->key
== short_type
)
590 #define promote_type vfy_promote_type
592 /* Mark this type as the uninitialized result of `new'. */
594 type_set_uninitialized (type
*t
, int npc
)
596 if (t
->key
== reference_type
)
597 t
->key
= uninitialized_reference_type
;
599 verify_fail ("internal error in type::uninitialized");
603 /* Mark this type as now initialized. */
605 type_set_initialized (type
*t
, int npc
)
607 if (npc
!= UNINIT
&& t
->pc
== npc
&& t
->key
== uninitialized_reference_type
)
609 t
->key
= reference_type
;
614 /* Mark this type as a particular return address. */
615 static void type_set_return_address (type
*t
, int npc
)
620 /* Return true if this type and type OTHER are considered
621 mergeable for the purposes of state merging. This is related
622 to subroutine handling. For this purpose two types are
623 considered unmergeable if they are both return-addresses but
624 have different PCs. */
626 type_state_mergeable_p (type
*t1
, type
*t2
)
628 return (t1
->key
!= return_address_type
629 || t2
->key
!= return_address_type
630 || t1
->pc
== t2
->pc
);
633 /* Return true if an object of type K can be assigned to a variable
634 of type T. Handle various special cases too. Might modify
635 T or K. Note however that this does not perform numeric
638 types_compatible (type
*t
, type
*k
)
640 /* Any type is compatible with the unsuitable type. */
641 if (k
->key
== unsuitable_type
)
644 if (t
->key
< reference_type
|| k
->key
< reference_type
)
645 return t
->key
== k
->key
;
647 /* The `null' type is convertible to any initialized reference
649 if (t
->key
== null_type
)
650 return k
->key
!= uninitialized_reference_type
;
651 if (k
->key
== null_type
)
652 return t
->key
!= uninitialized_reference_type
;
654 /* A special case for a generic reference. */
655 if (t
->klass
== NULL
)
657 if (k
->klass
== NULL
)
658 verify_fail ("programmer error in type::compatible");
660 /* Handle the special 'EITHER' case, which is only used in a
661 special case of 'putfield'. Note that we only need to handle
662 this on the LHS of a check. */
663 if (! type_initialized (t
) && t
->pc
== EITHER
)
665 /* If the RHS is uninitialized, it must be an uninitialized
667 if (! type_initialized (k
) && k
->pc
!= SELF
)
670 else if (type_initialized (t
) != type_initialized (k
))
672 /* An initialized type and an uninitialized type are not
673 otherwise compatible. */
678 /* Two uninitialized objects are compatible if either:
679 * The PCs are identical, or
680 * One PC is UNINIT. */
681 if (type_initialized (t
))
683 if (t
->pc
!= k
->pc
&& t
->pc
!= UNINIT
&& k
->pc
!= UNINIT
)
688 return ref_compatible (t
->klass
, k
->klass
);
691 /* Return true if two types are equal. Only valid for reference
694 types_equal (type
*t1
, type
*t2
)
696 if ((t1
->key
!= reference_type
&& t1
->key
!= uninitialized_reference_type
)
697 || (t2
->key
!= reference_type
698 && t2
->key
!= uninitialized_reference_type
))
700 /* Only single-ref types are allowed. */
701 if (t1
->klass
->ref_next
|| t2
->klass
->ref_next
)
703 return refs_equal (t1
->klass
, t2
->klass
);
707 type_isvoid (type
*t
)
709 return t
->key
== void_type
;
713 type_iswide (type
*t
)
715 return t
->key
== long_type
|| t
->key
== double_type
;
718 /* Return number of stack or local variable slots taken by this type. */
722 return type_iswide (t
) ? 2 : 1;
726 type_isarray (type
*t
)
728 /* We treat null_type as not an array. This is ok based on the
729 current uses of this method. */
730 if (t
->key
== reference_type
)
731 return ref_isarray (t
->klass
);
736 type_isnull (type
*t
)
738 return t
->key
== null_type
;
742 type_isinterface (type
*t
)
744 if (t
->key
!= reference_type
)
746 return ref_isinterface (t
->klass
);
750 type_isabstract (type
*t
)
752 if (t
->key
!= reference_type
)
754 return ref_isabstract (t
->klass
);
757 /* Return the element type of an array. */
759 type_array_element (type
*t
)
764 if (t
->key
!= reference_type
)
765 verify_fail ("programmer error in type::element_type()");
767 k
= vfy_get_component_type (ref_getclass (t
->klass
));
768 if (vfy_is_primitive (k
))
769 init_type_from_tag (&et
, get_type_val_for_primtype (k
));
771 init_type_from_class (&et
, k
);
775 /* Return the array type corresponding to an initialized
776 reference. We could expand this to work for other kinds of
777 types, but currently we don't need to. */
779 type_to_array (type
*t
)
784 if (t
->key
!= reference_type
)
785 verify_fail ("internal error in type::to_array()");
787 k
= ref_getclass (t
->klass
);
788 init_type_from_class (&at
, vfy_get_array_class (k
));
793 type_isreference (type
*t
)
795 return t
->key
>= reference_type
;
799 type_get_pc (type
*t
)
805 type_initialized (type
*t
)
807 return t
->key
== reference_type
|| t
->key
== null_type
;
811 type_verify_dimensions (type
*t
, int ndims
)
813 /* The way this is written, we don't need to check isarray(). */
814 if (t
->key
!= reference_type
)
815 verify_fail ("internal error in verify_dimensions:"
816 " not a reference type");
818 if (ref_count_dimensions (t
->klass
) < ndims
)
819 verify_fail ("array type has fewer dimensions"
823 /* Merge OLD_TYPE into this. On error throw exception. Return
824 true if the merge caused a type change. */
826 merge_types (type
*t
, type
*old_type
, bool local_semantics
)
828 bool changed
= false;
829 bool refo
= type_isreference (old_type
);
830 bool refn
= type_isreference (t
);
833 if (old_type
->key
== null_type
)
835 else if (t
->key
== null_type
)
840 else if (type_initialized (t
) != type_initialized (old_type
))
841 verify_fail ("merging initialized and uninitialized types");
844 ref_intersection
*merged
;
845 if (! type_initialized (t
))
848 t
->pc
= old_type
->pc
;
849 else if (old_type
->pc
== UNINIT
)
851 else if (t
->pc
!= old_type
->pc
)
852 verify_fail ("merging different uninitialized types");
855 merged
= merge_refs (old_type
->klass
, t
->klass
);
856 if (merged
!= t
->klass
)
863 else if (refo
|| refn
|| t
->key
!= old_type
->key
)
867 /* If we already have an `unsuitable' type, then we
868 don't need to change again. */
869 if (t
->key
!= unsuitable_type
)
871 t
->key
= unsuitable_type
;
876 verify_fail ("unmergeable type");
888 case boolean_type
: c
= 'Z'; break;
889 case byte_type
: c
= 'B'; break;
890 case char_type
: c
= 'C'; break;
891 case short_type
: c
= 'S'; break;
892 case int_type
: c
= 'I'; break;
893 case long_type
: c
= 'J'; break;
894 case float_type
: c
= 'F'; break;
895 case double_type
: c
= 'D'; break;
896 case void_type
: c
= 'V'; break;
897 case unsuitable_type
: c
= '-'; break;
898 case return_address_type
: c
= 'r'; break;
899 case continuation_type
: c
= '+'; break;
900 case reference_type
: c
= 'L'; break;
901 case null_type
: c
= '@'; break;
902 case uninitialized_reference_type
: c
= 'U'; break;
904 debug_print ("%c", c
);
906 #endif /* VERIFY_DEBUG */
908 /* This class holds all the state information we need for a given
912 /* The current top of the stack, in terms of slots. */
914 /* The current depth of the stack. This will be larger than
915 STACKTOP when wide types are on the stack. */
919 /* The local variables. */
921 /* We keep track of the type of `this' specially. This is used to
922 ensure that an instance initializer invokes another initializer
923 on `this' before returning. We must keep track of this
924 specially because otherwise we might be confused by code which
925 assigns to locals[0] (overwriting `this') and then returns
926 without really initializing. */
929 /* The PC for this state. This is only valid on states which are
930 permanently attached to a given PC. For an object like
931 `current_state', which is used transiently, this has no
934 /* We keep a linked list of all states requiring reverification.
935 If this is the special value INVALID_STATE then this state is
936 not on the list. NULL marks the end of the linked list. */
940 /* NO_NEXT is the PC value meaning that a new state must be
941 acquired from the verification list. */
945 init_state_with_stack (state
*s
, int max_stack
, int max_locals
)
950 s
->stack
= (type
*) vfy_alloc (max_stack
* sizeof (type
));
951 for (i
= 0; i
< max_stack
; ++i
)
952 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
953 s
->locals
= (type
*) vfy_alloc (max_locals
* sizeof (type
));
954 for (i
= 0; i
< max_locals
; ++i
)
955 init_type_from_tag (&s
->locals
[i
], unsuitable_type
);
956 init_type_from_tag (&s
->this_type
, unsuitable_type
);
958 s
->next
= INVALID_STATE
;
962 copy_state (state
*s
, state
*copy
, int max_stack
, int max_locals
)
965 s
->stacktop
= copy
->stacktop
;
966 s
->stackdepth
= copy
->stackdepth
;
967 for (i
= 0; i
< max_stack
; ++i
)
968 s
->stack
[i
] = copy
->stack
[i
];
969 for (i
= 0; i
< max_locals
; ++i
)
970 s
->locals
[i
] = copy
->locals
[i
];
972 s
->this_type
= copy
->this_type
;
973 /* Don't modify `next' or `pc'. */
977 copy_state_with_stack (state
*s
, state
*orig
, int max_stack
, int max_locals
)
979 init_state_with_stack (s
, max_stack
, max_locals
);
980 copy_state (s
, orig
, max_stack
, max_locals
);
983 /* Allocate a new state, copying ORIG. */
985 make_state_copy (state
*orig
, int max_stack
, int max_locals
)
987 state
*s
= (state
*) vfy_alloc (sizeof (state
));
988 copy_state_with_stack (s
, orig
, max_stack
, max_locals
);
993 make_state (int max_stack
, int max_locals
)
995 state
*s
= (state
*) vfy_alloc (sizeof (state
));
996 init_state_with_stack (s
, max_stack
, max_locals
);
1001 free_state (state
*s
)
1003 if (s
->stack
!= NULL
)
1004 vfy_free (s
->stack
);
1005 if (s
->locals
!= NULL
)
1006 vfy_free (s
->locals
);
1009 /* Modify this state to reflect entry to an exception handler. */
1011 state_set_exception (state
*s
, type
*t
, int max_stack
)
1017 for (i
= s
->stacktop
; i
< max_stack
; ++i
)
1018 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
1021 /* Merge STATE_OLD into this state. Destructively modifies this
1022 state. Returns true if the new state was in fact changed.
1023 Will throw an exception if the states are not mergeable. */
1025 merge_states (state
*s
, state
*state_old
, int max_locals
)
1028 bool changed
= false;
1030 /* Special handling for `this'. If one or the other is
1031 uninitialized, then the merge is uninitialized. */
1032 if (type_initialized (&s
->this_type
))
1033 s
->this_type
= state_old
->this_type
;
1036 if (state_old
->stacktop
!= s
->stacktop
) /* FIXME stackdepth instead? */
1037 verify_fail ("stack sizes differ");
1038 for (i
= 0; i
< state_old
->stacktop
; ++i
)
1040 if (merge_types (&s
->stack
[i
], &state_old
->stack
[i
], false))
1044 /* Merge local variables. */
1045 for (i
= 0; i
< max_locals
; ++i
)
1047 if (merge_types (&s
->locals
[i
], &state_old
->locals
[i
], true))
1054 /* Ensure that `this' has been initialized. */
1056 state_check_this_initialized (state
*s
)
1058 if (type_isreference (&s
->this_type
) && ! type_initialized (&s
->this_type
))
1059 verify_fail ("`this' is uninitialized");
1062 /* Set type of `this'. */
1064 state_set_this_type (state
*s
, type
*k
)
1069 /* Mark each `new'd object we know of that was allocated at PC as
1072 state_set_initialized (state
*s
, int pc
, int max_locals
)
1075 for (i
= 0; i
< s
->stacktop
; ++i
)
1076 type_set_initialized (&s
->stack
[i
], pc
);
1077 for (i
= 0; i
< max_locals
; ++i
)
1078 type_set_initialized (&s
->locals
[i
], pc
);
1079 type_set_initialized (&s
->this_type
, pc
);
1082 /* This tests to see whether two states can be considered "merge
1083 compatible". If both states have a return-address in the same
1084 slot, and the return addresses are different, then they are not
1085 compatible and we must not try to merge them. */
1087 state_mergeable_p (state
*s
, state
*other
, int max_locals
)
1092 /* This is tricky: if the stack sizes differ, then not only are
1093 these not mergeable, but in fact we should give an error, as
1094 we've found two execution paths that reach a branch target
1095 with different stack depths. FIXME stackdepth instead? */
1096 if (s
->stacktop
!= other
->stacktop
)
1097 verify_fail ("stack sizes differ");
1099 for (i
= 0; i
< s
->stacktop
; ++i
)
1100 if (! type_state_mergeable_p (&s
->stack
[i
], &other
->stack
[i
]))
1102 for (i
= 0; i
< max_locals
; ++i
)
1103 if (! type_state_mergeable_p (&s
->locals
[i
], &other
->locals
[i
]))
1109 state_reverify (state
*s
)
1111 if (s
->next
== INVALID_STATE
)
1113 s
->next
= vfr
->next_verify_state
;
1114 vfr
->next_verify_state
= s
;
1120 debug_print_state (state
*s
, const char *leader
, int pc
, int max_stack
,
1124 debug_print ("%s [%4d]: [stack] ", leader
, pc
);
1125 for (i
= 0; i
< s
->stacktop
; ++i
)
1126 type_print (&s
->stack
[i
]);
1127 for (; i
< max_stack
; ++i
)
1129 debug_print (" [local] ");
1130 for (i
= 0; i
< max_locals
; ++i
)
1131 type_print (&s
->locals
[i
]);
1132 debug_print (" | %p\n", s
);
1136 debug_print_state (state
*s ATTRIBUTE_UNUSED
,
1137 const char *leader ATTRIBUTE_UNUSED
,
1138 int pc ATTRIBUTE_UNUSED
, int max_stack ATTRIBUTE_UNUSED
,
1139 int max_locals ATTRIBUTE_UNUSED
)
1142 #endif /* VERIFY_DEBUG */
1148 state
*s
= vfr
->current_state
;
1149 if (s
->stacktop
<= 0)
1150 verify_fail ("stack empty");
1151 r
= s
->stack
[--s
->stacktop
];
1152 s
->stackdepth
-= type_depth (&r
);
1153 if (s
->stackdepth
< 0)
1154 verify_fail_pc ("stack empty", vfr
->start_PC
);
1161 type r
= pop_raw ();
1162 if (type_iswide (&r
))
1163 verify_fail ("narrow pop of wide type");
1168 vfy_pop_type_t (type match
)
1171 vfy_promote_type (&match
);
1173 if (! types_compatible (&match
, &t
))
1174 verify_fail ("incompatible type on stack");
1179 vfy_pop_type (type_val match
)
1181 type t
= make_type (match
);
1182 return vfy_pop_type_t (t
);
1185 #define pop_type vfy_pop_type
1186 #define pop_type_t vfy_pop_type_t
1188 /* Pop a reference which is guaranteed to be initialized. MATCH
1189 doesn't have to be a reference type; in this case this acts like
1192 pop_init_ref_t (type match
)
1194 type t
= pop_raw ();
1195 if (type_isreference (&t
) && ! type_initialized (&t
))
1196 verify_fail ("initialized reference required");
1197 else if (! types_compatible (&match
, &t
))
1198 verify_fail ("incompatible type on stack");
1203 pop_init_ref (type_val match
)
1205 type t
= make_type (match
);
1206 return pop_init_ref_t (t
);
1209 /* Pop a reference type or a return address. */
1211 pop_ref_or_return (void)
1213 type t
= pop_raw ();
1214 if (! type_isreference (&t
) && t
.key
!= return_address_type
)
1215 verify_fail ("expected reference or return address on stack");
1220 vfy_push_type_t (type t
)
1223 state
*s
= vfr
->current_state
;
1224 /* If T is a numeric type like short, promote it to int. */
1227 depth
= type_depth (&t
);
1229 if (s
->stackdepth
+ depth
> vfr
->current_method
->max_stack
)
1230 verify_fail ("stack overflow");
1231 s
->stack
[s
->stacktop
++] = t
;
1232 s
->stackdepth
+= depth
;
1236 vfy_push_type (type_val tval
)
1238 type t
= make_type (tval
);
1239 vfy_push_type_t (t
);
1242 #define push_type vfy_push_type
1243 #define push_type_t vfy_push_type_t
1246 set_variable (int index
, type t
)
1249 state
*s
= vfr
->current_state
;
1250 /* If T is a numeric type like short, promote it to int. */
1253 depth
= type_depth (&t
);
1254 if (index
> vfr
->current_method
->max_locals
- depth
)
1255 verify_fail ("invalid local variable");
1256 s
->locals
[index
] = t
;
1259 init_type_from_tag (&s
->locals
[index
+ 1], continuation_type
);
1260 if (index
> 0 && type_iswide (&s
->locals
[index
- 1]))
1261 init_type_from_tag (&s
->locals
[index
- 1], unsuitable_type
);
1265 get_variable_t (int index
, type
*t
)
1267 state
*s
= vfr
->current_state
;
1268 int depth
= type_depth (t
);
1269 if (index
> vfr
->current_method
->max_locals
- depth
)
1270 verify_fail ("invalid local variable");
1271 if (! types_compatible (t
, &s
->locals
[index
]))
1272 verify_fail ("incompatible type in local variable");
1275 type cont
= make_type (continuation_type
);
1276 if (! types_compatible (&s
->locals
[index
+ 1], &cont
))
1277 verify_fail ("invalid local variable");
1279 return s
->locals
[index
];
1283 get_variable (int index
, type_val v
)
1285 type t
= make_type (v
);
1286 return get_variable_t (index
, &t
);
1289 /* Make sure ARRAY is an array type and that its elements are
1290 compatible with type ELEMENT. Returns the actual element type. */
1292 require_array_type_t (type array
, type element
)
1295 /* An odd case. Here we just pretend that everything went ok. If
1296 the requested element type is some kind of reference, return
1297 the null type instead. */
1298 if (type_isnull (&array
))
1299 return type_isreference (&element
) ? make_type (null_type
) : element
;
1301 if (! type_isarray (&array
))
1302 verify_fail ("array required");
1304 t
= type_array_element (&array
);
1305 if (! types_compatible (&element
, &t
))
1307 /* Special case for byte arrays, which must also be boolean
1310 if (element
.key
== byte_type
)
1312 type e2
= make_type (boolean_type
);
1313 ok
= types_compatible (&e2
, &t
);
1316 verify_fail ("incompatible array element type");
1319 /* Return T and not ELEMENT, because T might be specialized. */
1324 require_array_type (type array
, type_val element
)
1326 type t
= make_type (element
);
1327 return require_array_type_t (array
, t
);
1333 if (vfr
->PC
>= vfr
->current_method
->code_length
)
1334 verify_fail ("premature end of bytecode");
1335 return (jint
) vfr
->bytecode
[vfr
->PC
++] & 0xff;
1341 jint b1
= get_byte ();
1342 jint b2
= get_byte ();
1343 return (jint
) ((b1
<< 8) | b2
) & 0xffff;
1349 signed char b1
= (signed char) get_byte ();
1350 jint b2
= get_byte ();
1351 jshort s
= (b1
<< 8) | b2
;
1358 jint b1
= get_byte ();
1359 jint b2
= get_byte ();
1360 jint b3
= get_byte ();
1361 jint b4
= get_byte ();
1362 jword result
= (b1
<< 24) | (b2
<< 16) | (b3
<< 8) | b4
;
1363 /* In the compiler, 'jint' might have more than 32 bits, so we must
1365 return WORD_TO_INT (result
);
1369 compute_jump (int offset
)
1371 int npc
= vfr
->start_PC
+ offset
;
1372 if (npc
< 0 || npc
>= vfr
->current_method
->code_length
)
1373 verify_fail_pc ("branch out of range", vfr
->start_PC
);
1377 /* Add a new state to the state list at NPC. */
1379 add_new_state (int npc
, state
*old_state
)
1382 vfy_method
*current_method
= vfr
->current_method
;
1383 state
*new_state
= make_state_copy (old_state
, current_method
->max_stack
,
1384 current_method
->max_locals
);
1385 debug_print ("== New state in add_new_state\n");
1386 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1387 current_method
->max_locals
);
1389 nlink
= (state_list
*) vfy_alloc (sizeof (state_list
));
1390 nlink
->val
= new_state
;
1391 nlink
->next
= vfr
->states
[npc
];
1392 vfr
->states
[npc
] = nlink
;
1393 new_state
->pc
= npc
;
1397 /* Merge the indicated state into the state at the branch target and
1398 schedule a new PC if there is a change. NPC is the PC of the
1399 branch target, and FROM_STATE is the state at the source of the
1400 branch. This method returns true if the destination state
1401 changed and requires reverification, false otherwise. */
1403 merge_into (int npc
, state
*from_state
)
1405 /* Iterate over all target states and merge our state into each,
1406 if applicable. FIXME one improvement we could make here is
1407 "state destruction". Merging a new state into an existing one
1408 might cause a return_address_type to be merged to
1409 unsuitable_type. In this case the resulting state may now be
1410 mergeable with other states currently held in parallel at this
1411 location. So in this situation we could pairwise compare and
1412 reduce the number of parallel states. */
1414 bool applicable
= false;
1415 for (iter
= vfr
->states
[npc
]; iter
!= NULL
; iter
= iter
->next
)
1417 state
*new_state
= iter
->val
;
1418 vfy_method
*current_method
= vfr
->current_method
;
1420 if (state_mergeable_p (new_state
, from_state
,
1421 current_method
->max_locals
))
1426 debug_print ("== Merge states in merge_into\n");
1427 debug_print_state (from_state
, "Frm", vfr
->start_PC
, current_method
->max_stack
,
1428 current_method
->max_locals
);
1429 debug_print_state (new_state
, " To", npc
, current_method
->max_stack
,
1430 current_method
->max_locals
);
1431 changed
= merge_states (new_state
, from_state
,
1432 current_method
->max_locals
);
1433 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1434 current_method
->max_locals
);
1437 state_reverify (new_state
);
1443 /* Either we don't yet have a state at NPC, or we have a
1444 return-address type that is in conflict with all existing
1445 state. So, we need to create a new entry. */
1446 state
*new_state
= add_new_state (npc
, from_state
);
1447 /* A new state added in this way must always be reverified. */
1448 state_reverify (new_state
);
1453 push_jump (int offset
)
1455 int npc
= compute_jump (offset
);
1456 /* According to the JVM Spec, we need to check for uninitialized
1457 objects here. However, this does not actually affect type
1458 safety, and the Eclipse java compiler generates code that
1459 violates this constraint. */
1460 merge_into (npc
, vfr
->current_state
);
1464 push_exception_jump (type t
, int pc
)
1467 /* According to the JVM Spec, we need to check for uninitialized
1468 objects here. However, this does not actually affect type
1469 safety, and the Eclipse java compiler generates code that
1470 violates this constraint. */
1471 copy_state_with_stack (&s
, vfr
->current_state
,
1472 vfr
->current_method
->max_stack
,
1473 vfr
->current_method
->max_locals
);
1474 if (vfr
->current_method
->max_stack
< 1)
1475 verify_fail ("stack overflow at exception handler");
1476 state_set_exception (&s
, &t
, vfr
->current_method
->max_stack
);
1477 merge_into (pc
, &s
);
1478 /* FIXME: leak.. need free_state or GC */
1484 state
*new_state
= vfr
->next_verify_state
;
1485 if (new_state
== INVALID_STATE
)
1486 verify_fail ("programmer error in pop_jump");
1487 if (new_state
!= NULL
)
1489 vfr
->next_verify_state
= new_state
->next
;
1490 new_state
->next
= INVALID_STATE
;
1496 invalidate_pc (void)
1502 note_branch_target (int pc
)
1504 /* Don't check `pc <= PC', because we've advanced PC after
1505 fetching the target and we haven't yet checked the next
1507 if (pc
< vfr
->PC
&& ! (vfr
->flags
[pc
] & FLAG_INSN_START
))
1508 verify_fail_pc ("branch not to instruction start", vfr
->start_PC
);
1509 vfr
->flags
[pc
] |= FLAG_BRANCH_TARGET
;
1515 while ((vfr
->PC
% 4) > 0)
1516 if (get_byte () != 0)
1517 verify_fail ("found nonzero padding byte");
1520 /* Do the work for a `ret' instruction. INDEX is the index into the
1523 handle_ret_insn (int index
)
1525 type ret
= make_type (return_address_type
);
1526 type ret_addr
= get_variable_t (index
, &ret
);
1527 /* It would be nice if we could do this. However, the JVM Spec
1528 doesn't say that this is what happens. It is implied that
1529 reusing a return address is invalid, but there's no actual
1530 prohibition against it. */
1531 /* set_variable (index, unsuitable_type); */
1533 int npc
= type_get_pc (&ret_addr
);
1534 /* We might be returning to a `jsr' that is at the end of the
1535 bytecode. This is ok if we never return from the called
1536 subroutine, but if we see this here it is an error. */
1537 if (npc
>= vfr
->current_method
->code_length
)
1538 verify_fail ("fell off end");
1540 /* According to the JVM Spec, we need to check for uninitialized
1541 objects here. However, this does not actually affect type
1542 safety, and the Eclipse java compiler generates code that
1543 violates this constraint. */
1544 merge_into (npc
, vfr
->current_state
);
1548 static void handle_jsr_insn (int offset
)
1551 int npc
= compute_jump (offset
);
1553 /* According to the JVM Spec, we need to check for uninitialized
1554 objects here. However, this does not actually affect type
1555 safety, and the Eclipse java compiler generates code that
1556 violates this constraint. */
1558 /* Modify our state as appropriate for entry into a subroutine. */
1559 ret_addr
= make_type (return_address_type
);
1560 type_set_return_address (&ret_addr
, vfr
->PC
);
1561 vfy_push_type_t (ret_addr
);
1562 merge_into (npc
, vfr
->current_state
);
1567 construct_primitive_array_type (type_val prim
)
1569 vfy_jclass k
= NULL
;
1580 k
= vfy_get_primitive_type ((int) prim
);
1583 /* These aren't used here but we call them out to avoid
1586 case unsuitable_type
:
1587 case return_address_type
:
1588 case continuation_type
:
1589 case reference_type
:
1591 case uninitialized_reference_type
:
1593 verify_fail ("unknown type in construct_primitive_array_type");
1595 k
= vfy_get_array_class (k
);
1599 /* This pass computes the location of branch targets and also
1600 instruction starts. */
1602 branch_prepass (void)
1605 vfr
->flags
= (char *) vfy_alloc (vfr
->current_method
->code_length
);
1607 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
1611 while (vfr
->PC
< vfr
->current_method
->code_length
)
1614 /* Set `start_PC' early so that error checking can have the
1616 vfr
->start_PC
= vfr
->PC
;
1617 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_START
;
1619 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
1623 case op_aconst_null
:
1759 case op_monitorenter
:
1760 case op_monitorexit
:
1768 case op_arraylength
:
1800 case op_invokespecial
:
1801 case op_invokestatic
:
1802 case op_invokevirtual
:
1806 case op_multianewarray
:
1829 note_branch_target (compute_jump (get_short ()));
1832 case op_tableswitch
:
1836 note_branch_target (compute_jump (get_int ()));
1840 verify_fail_pc ("invalid tableswitch", vfr
->start_PC
);
1841 for (i
= low
; i
<= hi
; ++i
)
1842 note_branch_target (compute_jump (get_int ()));
1846 case op_lookupswitch
:
1850 note_branch_target (compute_jump (get_int ()));
1851 npairs
= get_int ();
1853 verify_fail_pc ("too few pairs in lookupswitch", vfr
->start_PC
);
1854 while (npairs
-- > 0)
1857 note_branch_target (compute_jump (get_int ()));
1862 case op_invokeinterface
:
1870 opcode
= (java_opcode
) get_byte ();
1872 if (opcode
== op_iinc
)
1879 note_branch_target (compute_jump (get_int ()));
1883 /* These are unused here, but we call them out explicitly
1884 so that -Wswitch-enum doesn't complain. */
1890 case op_putstatic_1
:
1891 case op_putstatic_2
:
1892 case op_putstatic_4
:
1893 case op_putstatic_8
:
1894 case op_putstatic_a
:
1896 case op_getfield_2s
:
1897 case op_getfield_2u
:
1901 case op_getstatic_1
:
1902 case op_getstatic_2s
:
1903 case op_getstatic_2u
:
1904 case op_getstatic_4
:
1905 case op_getstatic_8
:
1906 case op_getstatic_a
:
1907 #endif /* VFY_FAST_OPCODES */
1909 verify_fail_pc ("unrecognized instruction in branch_prepass",
1913 /* See if any previous branch tried to branch to the middle of
1914 this instruction. */
1915 for (pc
= vfr
->start_PC
+ 1; pc
< vfr
->PC
; ++pc
)
1917 if ((vfr
->flags
[pc
] & FLAG_BRANCH_TARGET
))
1918 verify_fail_pc ("branch to middle of instruction", pc
);
1922 /* Verify exception handlers. */
1923 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
1925 int handler
, start
, end
, htype
;
1926 vfy_get_exception (vfr
->exception
, i
, &handler
, &start
, &end
, &htype
);
1927 if (! (vfr
->flags
[handler
] & FLAG_INSN_START
))
1928 verify_fail_pc ("exception handler not at instruction start",
1930 if (! (vfr
->flags
[start
] & FLAG_INSN_START
))
1931 verify_fail_pc ("exception start not at instruction start", start
);
1932 if (end
!= vfr
->current_method
->code_length
1933 && ! (vfr
->flags
[end
] & FLAG_INSN_START
))
1934 verify_fail_pc ("exception end not at instruction start", end
);
1936 vfr
->flags
[handler
] |= FLAG_BRANCH_TARGET
;
1941 check_pool_index (int index
)
1943 if (index
< 0 || index
>= vfy_get_constants_size (vfr
->current_class
))
1944 verify_fail_pc ("constant pool index out of range", vfr
->start_PC
);
1948 check_class_constant (int index
)
1950 type t
= { (type_val
) 0, 0, 0 };
1951 vfy_constants
*pool
;
1953 check_pool_index (index
);
1954 pool
= vfy_get_constants (vfr
->current_class
);
1955 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedClass
)
1956 init_type_from_class (&t
, vfy_get_pool_class (pool
, index
));
1957 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Class
)
1958 init_type_from_string (&t
, vfy_get_pool_string (pool
, index
));
1960 verify_fail_pc ("expected class constant", vfr
->start_PC
);
1965 check_constant (int index
)
1967 type t
= { (type_val
) 0, 0, 0 };
1968 vfy_constants
*pool
;
1970 check_pool_index (index
);
1971 pool
= vfy_get_constants (vfr
->current_class
);
1972 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedString
1973 || vfy_tag (pool
, index
) == JV_CONSTANT_String
)
1974 init_type_from_class (&t
, vfy_string_type ());
1975 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Integer
)
1976 init_type_from_tag (&t
, int_type
);
1977 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Float
)
1978 init_type_from_tag (&t
, float_type
);
1979 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Class
1980 || vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedClass
)
1981 /* FIXME: should only allow this for 1.5 bytecode. */
1982 init_type_from_class (&t
, vfy_class_type ());
1984 verify_fail_pc ("String, int, or float constant expected", vfr
->start_PC
);
1989 check_wide_constant (int index
)
1991 type t
= { (type_val
) 0, 0, 0 };
1992 vfy_constants
*pool
;
1994 check_pool_index (index
);
1995 pool
= vfy_get_constants (vfr
->current_class
);
1996 if (vfy_tag (pool
, index
) == JV_CONSTANT_Long
)
1997 init_type_from_tag (&t
, long_type
);
1998 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Double
)
1999 init_type_from_tag (&t
, double_type
);
2001 verify_fail_pc ("long or double constant expected", vfr
->start_PC
);
2005 /* Helper for both field and method. These are laid out the same in
2006 the constant pool. */
2008 handle_field_or_method (int index
, int expected
,
2009 vfy_string
*name
, vfy_string
*fmtype
)
2011 vfy_uint_16 class_index
, name_and_type_index
;
2012 vfy_uint_16 name_index
, desc_index
;
2013 vfy_constants
*pool
;
2015 check_pool_index (index
);
2016 pool
= vfy_get_constants (vfr
->current_class
);
2017 if (vfy_tag (pool
, index
) != expected
)
2018 verify_fail_pc ("didn't see expected constant", vfr
->start_PC
);
2019 /* Once we know we have a Fieldref or Methodref we assume that it
2020 is correctly laid out in the constant pool. I think the code
2021 in defineclass.cc guarantees this. */
2022 vfy_load_indexes (pool
, index
, &class_index
, &name_and_type_index
);
2023 vfy_load_indexes (pool
, name_and_type_index
, &name_index
, &desc_index
);
2025 *name
= vfy_get_pool_string (pool
, name_index
);
2026 *fmtype
= vfy_get_pool_string (pool
, desc_index
);
2028 return check_class_constant (class_index
);
2031 /* Return field's type, compute class' type if requested. If
2032 PUTFIELD is true, use the special 'putfield' semantics. */
2034 check_field_constant (int index
, type
*class_type
, bool putfield
)
2036 vfy_string name
, field_type
;
2041 type ct
= handle_field_or_method (index
,
2042 JV_CONSTANT_Fieldref
,
2043 &name
, &field_type
);
2046 typec
= vfy_string_bytes (field_type
);
2047 len
= vfy_string_length (field_type
);
2048 if (typec
[0] == '[' || typec
[0] == 'L')
2049 init_type_from_string (&t
, field_type
);
2051 init_type_from_tag (&t
, get_type_val_for_signature (typec
[0]));
2053 /* We have an obscure special case here: we can use `putfield' on a
2054 field declared in this class, even if `this' has not yet been
2057 && ! type_initialized (&vfr
->current_state
->this_type
)
2058 && vfr
->current_state
->this_type
.pc
== SELF
2059 && types_equal (&vfr
->current_state
->this_type
, &ct
)
2060 && vfy_class_has_field (vfr
->current_class
, name
, field_type
))
2061 /* Note that we don't actually know whether we're going to match
2062 against 'this' or some other object of the same type. So,
2063 here we set things up so that it doesn't matter. This relies
2064 on knowing what our caller is up to. */
2065 type_set_uninitialized (class_type
, EITHER
);
2071 check_method_constant (int index
, bool is_interface
,
2072 vfy_string
*method_name
,
2073 vfy_string
*method_signature
)
2075 return handle_field_or_method (index
,
2077 ? JV_CONSTANT_InterfaceMethodref
2078 : JV_CONSTANT_Methodref
),
2079 method_name
, method_signature
);
2083 get_one_type (const char *p
, type
*t
)
2085 const char *start
= p
;
2105 name
= vfy_get_string (start
, p
- start
);
2106 *t
= make_type_from_string (name
);
2110 /* Casting to jchar here is ok since we are looking at an ASCII
2112 rt
= get_type_val_for_signature (v
);
2114 if (arraycount
== 0)
2116 /* Callers of this function eventually push their arguments on
2117 the stack. So, promote them here. */
2118 type new_t
= make_type (rt
);
2119 vfy_promote_type (&new_t
);
2124 k
= construct_primitive_array_type (rt
);
2125 while (--arraycount
> 0)
2126 k
= vfy_get_array_class (k
);
2127 *t
= make_type_from_class (k
);
2132 compute_argument_types (vfy_string signature
, type
*types
)
2135 const char *p
= vfy_string_bytes (signature
);
2142 p
= get_one_type (p
, &types
[i
++]);
2146 compute_return_type (vfy_string signature
)
2148 const char *p
= vfy_string_bytes (signature
);
2153 get_one_type (p
, &t
);
2158 check_return_type (type onstack
)
2160 type rt
= compute_return_type (vfy_get_signature (vfr
->current_method
));
2161 if (! types_compatible (&rt
, &onstack
))
2162 verify_fail ("incompatible return type");
2165 /* Initialize the stack for the new method. Returns true if this
2166 method is an instance initializer. */
2168 initialize_stack (void)
2172 bool is_init
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2174 bool is_clinit
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2177 if (! vfy_is_static (vfr
->current_method
))
2179 type kurr
= make_type_from_class (vfr
->current_class
);
2182 type_set_uninitialized (&kurr
, SELF
);
2186 verify_fail ("<clinit> method must be static");
2187 set_variable (0, kurr
);
2188 state_set_this_type (vfr
->current_state
, &kurr
);
2194 verify_fail ("<init> method must be non-static");
2197 /* We have to handle wide arguments specially here. */
2198 arg_count
= vfy_count_arguments (vfy_get_signature (vfr
->current_method
));
2200 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2201 compute_argument_types (vfy_get_signature (vfr
->current_method
), arg_types
);
2202 for (i
= 0; i
< arg_count
; ++i
)
2204 set_variable (var
, arg_types
[i
]);
2206 if (type_iswide (&arg_types
[i
]))
2209 vfy_free (arg_types
);
2216 verify_instructions_0 (void)
2221 vfr
->current_state
= make_state (vfr
->current_method
->max_stack
,
2222 vfr
->current_method
->max_locals
);
2227 /* True if we are verifying an instance initializer. */
2228 this_is_init
= initialize_stack ();
2230 vfr
->states
= (state_list
**) vfy_alloc (sizeof (state_list
*)
2231 * vfr
->current_method
->code_length
);
2233 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
2234 vfr
->states
[i
] = NULL
;
2236 vfr
->next_verify_state
= NULL
;
2242 /* If the PC was invalidated, get a new one from the work list. */
2243 if (vfr
->PC
== NO_NEXT
)
2245 state
*new_state
= pop_jump ();
2246 /* If it is null, we're done. */
2247 if (new_state
== NULL
)
2250 vfr
->PC
= new_state
->pc
;
2251 debug_print ("== State pop from pending list\n");
2252 /* Set up the current state. */
2253 copy_state (vfr
->current_state
, new_state
,
2254 vfr
->current_method
->max_stack
, vfr
->current_method
->max_locals
);
2258 /* We only have to do this checking in the situation where
2259 control flow falls through from the previous instruction.
2260 Otherwise merging is done at the time we push the branch.
2261 Note that we'll catch the off-the-end problem just
2263 if (vfr
->PC
< vfr
->current_method
->code_length
2264 && vfr
->states
[vfr
->PC
] != NULL
)
2266 /* We've already visited this instruction. So merge
2267 the states together. It is simplest, but not most
2268 efficient, to just always invalidate the PC here. */
2269 merge_into (vfr
->PC
, vfr
->current_state
);
2275 /* Control can't fall off the end of the bytecode. We need to
2276 check this in both cases, not just the fall-through case,
2277 because we don't check to see whether a `jsr' appears at
2278 the end of the bytecode until we process a `ret'. */
2279 if (vfr
->PC
>= vfr
->current_method
->code_length
)
2280 verify_fail ("fell off end");
2281 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_SEEN
;
2283 /* We only have to keep saved state at branch targets. If
2284 we're at a branch target and the state here hasn't been set
2285 yet, we set it now. You might notice that `ret' targets
2286 won't necessarily have FLAG_BRANCH_TARGET set. This
2287 doesn't matter, since those states will be filled in by
2289 /* Note that other parts of the compiler assume that there is a
2290 label with a type map at PC=0. */
2291 if (vfr
->states
[vfr
->PC
] == NULL
2292 && (vfr
->PC
== 0 || (vfr
->flags
[vfr
->PC
] & FLAG_BRANCH_TARGET
) != 0))
2293 add_new_state (vfr
->PC
, vfr
->current_state
);
2295 /* Set this before handling exceptions so that debug output is
2297 vfr
->start_PC
= vfr
->PC
;
2299 /* Update states for all active exception handlers. Ordinarily
2300 there are not many exception handlers. So we simply run
2301 through them all. */
2302 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
2304 int hpc
, start
, end
, htype
;
2305 vfy_get_exception (vfr
->exception
, i
, &hpc
, &start
, &end
, &htype
);
2306 if (vfr
->PC
>= start
&& vfr
->PC
< end
)
2308 type handler
= make_type_from_class (vfy_throwable_type ());
2310 handler
= check_class_constant (htype
);
2311 push_exception_jump (handler
, hpc
);
2316 debug_print_state (vfr
->current_state
, " ", vfr
->PC
,
2317 vfr
->current_method
->max_stack
,
2318 vfr
->current_method
->max_locals
);
2319 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
2325 case op_aconst_null
:
2326 push_type (null_type
);
2336 push_type (int_type
);
2341 push_type (long_type
);
2347 push_type (float_type
);
2352 push_type (double_type
);
2357 push_type (int_type
);
2362 push_type (int_type
);
2366 push_type_t (check_constant (get_byte ()));
2369 push_type_t (check_constant (get_ushort ()));
2372 push_type_t (check_wide_constant (get_ushort ()));
2376 push_type_t (get_variable (get_byte (), int_type
));
2379 push_type_t (get_variable (get_byte (), long_type
));
2382 push_type_t (get_variable (get_byte (), float_type
));
2385 push_type_t (get_variable (get_byte (), double_type
));
2388 push_type_t (get_variable (get_byte (), reference_type
));
2395 push_type_t (get_variable (opcode
- op_iload_0
, int_type
));
2401 push_type_t (get_variable (opcode
- op_lload_0
, long_type
));
2407 push_type_t (get_variable (opcode
- op_fload_0
, float_type
));
2413 push_type_t (get_variable (opcode
- op_dload_0
, double_type
));
2419 push_type_t (get_variable (opcode
- op_aload_0
, reference_type
));
2422 pop_type (int_type
);
2423 push_type_t (require_array_type (pop_init_ref (reference_type
),
2427 pop_type (int_type
);
2428 push_type_t (require_array_type (pop_init_ref (reference_type
),
2432 pop_type (int_type
);
2433 push_type_t (require_array_type (pop_init_ref (reference_type
),
2437 pop_type (int_type
);
2438 push_type_t (require_array_type (pop_init_ref (reference_type
),
2442 pop_type (int_type
);
2443 push_type_t (require_array_type (pop_init_ref (reference_type
),
2447 pop_type (int_type
);
2448 require_array_type (pop_init_ref (reference_type
), byte_type
);
2449 push_type (int_type
);
2452 pop_type (int_type
);
2453 require_array_type (pop_init_ref (reference_type
), char_type
);
2454 push_type (int_type
);
2457 pop_type (int_type
);
2458 require_array_type (pop_init_ref (reference_type
), short_type
);
2459 push_type (int_type
);
2462 set_variable (get_byte (), pop_type (int_type
));
2465 set_variable (get_byte (), pop_type (long_type
));
2468 set_variable (get_byte (), pop_type (float_type
));
2471 set_variable (get_byte (), pop_type (double_type
));
2474 set_variable (get_byte (), pop_ref_or_return ());
2480 set_variable (opcode
- op_istore_0
, pop_type (int_type
));
2486 set_variable (opcode
- op_lstore_0
, pop_type (long_type
));
2492 set_variable (opcode
- op_fstore_0
, pop_type (float_type
));
2498 set_variable (opcode
- op_dstore_0
, pop_type (double_type
));
2504 set_variable (opcode
- op_astore_0
, pop_ref_or_return ());
2507 pop_type (int_type
);
2508 pop_type (int_type
);
2509 require_array_type (pop_init_ref (reference_type
), int_type
);
2512 pop_type (long_type
);
2513 pop_type (int_type
);
2514 require_array_type (pop_init_ref (reference_type
), long_type
);
2517 pop_type (float_type
);
2518 pop_type (int_type
);
2519 require_array_type (pop_init_ref (reference_type
), float_type
);
2522 pop_type (double_type
);
2523 pop_type (int_type
);
2524 require_array_type (pop_init_ref (reference_type
), double_type
);
2527 pop_type (reference_type
);
2528 pop_type (int_type
);
2529 require_array_type (pop_init_ref (reference_type
), reference_type
);
2532 pop_type (int_type
);
2533 pop_type (int_type
);
2534 require_array_type (pop_init_ref (reference_type
), byte_type
);
2537 pop_type (int_type
);
2538 pop_type (int_type
);
2539 require_array_type (pop_init_ref (reference_type
), char_type
);
2542 pop_type (int_type
);
2543 pop_type (int_type
);
2544 require_array_type (pop_init_ref (reference_type
), short_type
);
2551 type t
= pop_raw ();
2552 if (! type_iswide (&t
))
2575 type t2
= pop_raw ();
2576 if (! type_iswide (&t2
))
2590 type t
= pop_raw ();
2591 if (! type_iswide (&t
))
2605 type t1
= pop_raw ();
2607 if (! type_iswide (&t1
))
2622 type t1
= pop_raw ();
2623 if (type_iswide (&t1
))
2625 type t2
= pop_raw ();
2626 if (type_iswide (&t2
))
2643 type t3
= pop_raw ();
2644 if (type_iswide (&t3
))
2681 pop_type (int_type
);
2682 push_type_t (pop_type (int_type
));
2692 pop_type (long_type
);
2693 push_type_t (pop_type (long_type
));
2698 pop_type (int_type
);
2699 push_type_t (pop_type (long_type
));
2706 pop_type (float_type
);
2707 push_type_t (pop_type (float_type
));
2714 pop_type (double_type
);
2715 push_type_t (pop_type (double_type
));
2721 push_type_t (pop_type (int_type
));
2724 push_type_t (pop_type (long_type
));
2727 push_type_t (pop_type (float_type
));
2730 push_type_t (pop_type (double_type
));
2733 get_variable (get_byte (), int_type
);
2737 pop_type (int_type
);
2738 push_type (long_type
);
2741 pop_type (int_type
);
2742 push_type (float_type
);
2745 pop_type (int_type
);
2746 push_type (double_type
);
2749 pop_type (long_type
);
2750 push_type (int_type
);
2753 pop_type (long_type
);
2754 push_type (float_type
);
2757 pop_type (long_type
);
2758 push_type (double_type
);
2761 pop_type (float_type
);
2762 push_type (int_type
);
2765 pop_type (float_type
);
2766 push_type (long_type
);
2769 pop_type (float_type
);
2770 push_type (double_type
);
2773 pop_type (double_type
);
2774 push_type (int_type
);
2777 pop_type (double_type
);
2778 push_type (long_type
);
2781 pop_type (double_type
);
2782 push_type (float_type
);
2785 pop_type (long_type
);
2786 pop_type (long_type
);
2787 push_type (int_type
);
2791 pop_type (float_type
);
2792 pop_type (float_type
);
2793 push_type (int_type
);
2797 pop_type (double_type
);
2798 pop_type (double_type
);
2799 push_type (int_type
);
2807 pop_type (int_type
);
2808 push_jump (get_short ());
2816 pop_type (int_type
);
2817 pop_type (int_type
);
2818 push_jump (get_short ());
2822 pop_type (reference_type
);
2823 pop_type (reference_type
);
2824 push_jump (get_short ());
2827 push_jump (get_short ());
2831 handle_jsr_insn (get_short ());
2834 handle_ret_insn (get_byte ());
2836 case op_tableswitch
:
2840 pop_type (int_type
);
2842 push_jump (get_int ());
2845 /* Already checked LOW -vs- HIGH. */
2846 for (i
= low
; i
<= high
; ++i
)
2847 push_jump (get_int ());
2852 case op_lookupswitch
:
2855 jint npairs
, lastkey
;
2857 pop_type (int_type
);
2859 push_jump (get_int ());
2860 npairs
= get_int ();
2861 /* Already checked NPAIRS >= 0. */
2863 for (i
= 0; i
< npairs
; ++i
)
2865 jint key
= get_int ();
2866 if (i
> 0 && key
<= lastkey
)
2867 verify_fail_pc ("lookupswitch pairs unsorted", vfr
->start_PC
);
2869 push_jump (get_int ());
2875 check_return_type (pop_type (int_type
));
2879 check_return_type (pop_type (long_type
));
2883 check_return_type (pop_type (float_type
));
2887 check_return_type (pop_type (double_type
));
2891 check_return_type (pop_init_ref (reference_type
));
2895 /* We only need to check this when the return type is void,
2896 because all instance initializers return void. We also
2897 need to special-case Object constructors, as they can't
2898 call a superclass <init>. */
2899 if (this_is_init
&& vfr
->current_class
!= vfy_object_type ())
2900 state_check_this_initialized (vfr
->current_state
);
2901 check_return_type (make_type (void_type
));
2905 push_type_t (check_field_constant (get_ushort (), NULL
, false));
2908 pop_type_t (check_field_constant (get_ushort (), NULL
, false));
2913 type field
= check_field_constant (get_ushort (), &klass
, false);
2915 push_type_t (field
);
2921 type field
= check_field_constant (get_ushort (), &klass
, true);
2927 case op_invokevirtual
:
2928 case op_invokespecial
:
2929 case op_invokestatic
:
2930 case op_invokeinterface
:
2932 vfy_string method_name
, method_signature
;
2936 bool is_init
= false;
2939 = check_method_constant (get_ushort (),
2940 opcode
== op_invokeinterface
,
2943 /* NARGS is only used when we're processing
2944 invokeinterface. It is simplest for us to compute it
2945 here and then verify it later. */
2947 if (opcode
== op_invokeinterface
)
2949 nargs
= get_byte ();
2950 if (get_byte () != 0)
2951 verify_fail ("invokeinterface dummy byte is wrong");
2954 namec
= vfy_string_bytes (method_name
);
2956 if (vfy_strings_equal (method_name
, vfy_init_name()))
2959 if (opcode
!= op_invokespecial
)
2960 verify_fail ("can't invoke <init>");
2962 else if (namec
[0] == '<')
2963 verify_fail ("can't invoke method starting with `<'");
2965 arg_count
= vfy_count_arguments (method_signature
);
2967 /* Pop arguments and check types. */
2968 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2970 compute_argument_types (method_signature
, arg_types
);
2971 for (i
= arg_count
- 1; i
>= 0; --i
)
2973 /* This is only used for verifying the byte for
2975 nargs
-= type_depth (&arg_types
[i
]);
2976 pop_init_ref_t (arg_types
[i
]);
2979 vfy_free (arg_types
);
2982 if (opcode
== op_invokeinterface
2984 verify_fail ("wrong argument count for invokeinterface");
2986 if (opcode
!= op_invokestatic
)
2989 type t
= class_type
;
2992 /* In this case the PC doesn't matter. */
2993 type_set_uninitialized (&t
, UNINIT
);
2994 /* FIXME: check to make sure that the <init>
2995 call is to the right class.
2996 It must either be super or an exact class
3000 if (! types_compatible (&t
, &raw
))
3001 verify_fail ("incompatible type on stack");
3004 state_set_initialized (vfr
->current_state
,
3005 type_get_pc (&raw
), vfr
->current_method
->max_locals
);
3008 rt
= compute_return_type (method_signature
);
3009 if (! type_isvoid (&rt
))
3016 type t
= check_class_constant (get_ushort ());
3017 if (type_isarray (&t
) || type_isinterface (&t
)
3018 || type_isabstract (&t
))
3019 verify_fail ("type is array, interface, or abstract");
3020 type_set_uninitialized (&t
, vfr
->start_PC
);
3027 int atype
= get_byte ();
3030 /* We intentionally have chosen constants to make this
3032 if (atype
< boolean_type
|| atype
> long_type
)
3033 verify_fail_pc ("type not primitive", vfr
->start_PC
);
3034 pop_type (int_type
);
3035 k
= construct_primitive_array_type ((type_val
) atype
);
3036 init_type_from_class (&t
, k
);
3043 pop_type (int_type
);
3044 t
= check_class_constant (get_ushort ());
3045 push_type_t (type_to_array (&t
));
3048 case op_arraylength
:
3050 type t
= pop_init_ref (reference_type
);
3051 if (! type_isarray (&t
) && ! type_isnull (&t
))
3052 verify_fail ("array type expected");
3053 push_type (int_type
);
3057 pop_type_t (make_type_from_class (vfy_throwable_type ()));
3061 pop_init_ref (reference_type
);
3062 push_type_t (check_class_constant (get_ushort ()));
3065 pop_init_ref (reference_type
);
3066 check_class_constant (get_ushort ());
3067 push_type (int_type
);
3069 case op_monitorenter
:
3070 pop_init_ref (reference_type
);
3072 case op_monitorexit
:
3073 pop_init_ref (reference_type
);
3077 switch (get_byte ())
3080 push_type_t (get_variable (get_ushort (), int_type
));
3083 push_type_t (get_variable (get_ushort (), long_type
));
3086 push_type_t (get_variable (get_ushort (), float_type
));
3089 push_type_t (get_variable (get_ushort (), double_type
));
3092 push_type_t (get_variable (get_ushort (), reference_type
));
3095 set_variable (get_ushort (), pop_type (int_type
));
3098 set_variable (get_ushort (), pop_type (long_type
));
3101 set_variable (get_ushort (), pop_type (float_type
));
3104 set_variable (get_ushort (), pop_type (double_type
));
3107 set_variable (get_ushort (), pop_init_ref (reference_type
));
3110 handle_ret_insn (get_short ());
3113 get_variable (get_ushort (), int_type
);
3117 verify_fail_pc ("unrecognized wide instruction", vfr
->start_PC
);
3121 case op_multianewarray
:
3124 type atype
= check_class_constant (get_ushort ());
3125 int dim
= get_byte ();
3127 verify_fail_pc ("too few dimensions to multianewarray", vfr
->start_PC
);
3128 type_verify_dimensions (&atype
, dim
);
3129 for (i
= 0; i
< dim
; ++i
)
3130 pop_type (int_type
);
3131 push_type_t (atype
);
3136 pop_type (reference_type
);
3137 push_jump (get_short ());
3140 push_jump (get_int ());
3144 handle_jsr_insn (get_int ());
3148 /* Unrecognized opcode. */
3149 verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3155 /* This turns a `type' into something suitable for use by the type map
3156 in the other parts of the compiler. In particular, reference types
3157 are mapped to Object, primitive types are unchanged, and other
3158 types are mapped using special functions declared in verify.h. */
3160 collapse_type (type
*t
)
3173 return vfy_get_primitive_type (t
->key
);
3175 case unsuitable_type
:
3176 case continuation_type
:
3177 return vfy_unsuitable_type ();
3179 case return_address_type
:
3180 return vfy_return_address_type ();
3183 return vfy_null_type ();
3185 case reference_type
:
3186 case uninitialized_reference_type
:
3187 return vfy_object_type ();
3194 verify_instructions (void)
3199 verify_instructions_0 ();
3201 /* Now tell the rest of the compiler about the types we've found. */
3202 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3207 if ((vfr
->flags
[i
] & FLAG_INSN_SEEN
) != 0)
3208 vfy_note_instruction_seen (i
);
3210 if (! vfr
->states
[i
])
3213 curr
= vfr
->states
[i
]->val
;
3214 vfy_note_stack_depth (vfr
->current_method
, i
, curr
->stackdepth
);
3216 /* Tell the compiler about each local variable. */
3217 for (j
= 0; j
< vfr
->current_method
->max_locals
; ++j
)
3218 vfy_note_local_type (vfr
->current_method
, i
, j
,
3219 collapse_type (&curr
->locals
[j
]));
3220 /* Tell the compiler about each stack slot. */
3221 for (slot
= j
= 0; j
< curr
->stacktop
; ++j
, ++slot
)
3223 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3224 collapse_type (&curr
->stack
[j
]));
3225 if (type_iswide (&curr
->stack
[j
]))
3228 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3229 vfy_unsuitable_type ());
3232 gcc_assert (slot
== curr
->stackdepth
);
3237 make_verifier_context (vfy_method
*m
)
3239 vfr
= (verifier_context
*) vfy_alloc (sizeof (struct verifier_context
));
3241 vfr
->current_method
= m
;
3242 vfr
->bytecode
= vfy_get_bytecode (m
);
3243 vfr
->exception
= vfy_get_exceptions (m
);
3244 vfr
->current_class
= m
->defining_class
;
3248 vfr
->utf8_list
= NULL
;
3249 vfr
->isect_list
= NULL
;
3253 free_verifier_context (void)
3255 vfy_string_list
*utf8_list
;
3256 ref_intersection
*isect_list
;
3259 vfy_free (vfr
->flags
);
3261 utf8_list
= vfr
->utf8_list
;
3262 while (utf8_list
!= NULL
)
3264 vfy_string_list
*n
= utf8_list
->next
;
3265 vfy_free (utf8_list
);
3269 isect_list
= vfr
->isect_list
;
3270 while (isect_list
!= NULL
)
3272 ref_intersection
*next
= isect_list
->alloc_next
;
3273 vfy_free (isect_list
);
3277 if (vfr
->states
!= NULL
)
3280 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3282 state_list
*iter
= vfr
->states
[i
];
3283 while (iter
!= NULL
)
3285 state_list
*next
= iter
->next
;
3286 free_state (iter
->val
);
3287 vfy_free (iter
->val
);
3292 vfy_free (vfr
->states
);
3299 verify_method (vfy_method
*meth
)
3301 debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth
->name
),
3305 verify_fail ("verifier re-entered");
3307 make_verifier_context (meth
);
3308 verify_instructions ();
3309 free_verifier_context ();