1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 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)
29 static void ATTRIBUTE_PRINTF_1
30 debug_print (const char *fmt ATTRIBUTE_UNUSED
, ...)
35 vfprintf (stderr
, fmt
, ap
);
37 #endif /* VERIFY_DEBUG */
40 /* This started as a fairly ordinary verifier, and for the most part
41 it remains so. It works in the obvious way, by modeling the effect
42 of each opcode as it is encountered. For most opcodes, this is a
43 straightforward operation.
45 This verifier does not do type merging. It used to, but this
46 results in difficulty verifying some relatively simple code
47 involving interfaces, and it pushed some verification work into the
50 Instead of merging reference types, when we reach a point where two
51 flows of control merge, we simply keep the union of reference types
52 from each branch. Then, when we need to verify a fact about a
53 reference on the stack (e.g., that it is compatible with the
54 argument type of a method), we check to ensure that all possible
55 types satisfy the requirement.
57 Another area this verifier differs from the norm is in its handling
58 of subroutines. The JVM specification has some confusing things to
59 say about subroutines. For instance, it makes claims about not
60 allowing subroutines to merge and it rejects recursive subroutines.
61 For the most part these are red herrings; we used to try to follow
62 these things but they lead to problems. For example, the notion of
63 "being in a subroutine" is not well-defined: is an exception
64 handler in a subroutine? If you never execute the `ret' but
65 instead `goto 1' do you remain in the subroutine?
67 For clarity on what is really required for type safety, read
68 "Simple Verification Technique for Complex Java Bytecode
69 Subroutines" by Alessandro Coglio. Among other things this paper
70 shows that recursive subroutines are not harmful to type safety.
71 We implement something similar to what he proposes. Note that this
72 means that this verifier will accept code that is rejected by some
75 For those not wanting to read the paper, the basic observation is
76 that we can maintain split states in subroutines. We maintain one
77 state for each calling `jsr'. In other words, we re-verify a
78 subroutine once for each caller, using the exact types held by the
79 callers (as opposed to the old approach of merging types and
80 keeping a bitmap registering what did or did not change). This
81 approach lets us continue to verify correctly even when a
82 subroutine is exited via `goto' or `athrow' and not `ret'.
84 In some other areas the JVM specification is (mildly) incorrect,
85 so we diverge. For instance, you cannot
86 violate type safety by allocating an object with `new' and then
87 failing to initialize it, no matter how one branches or where one
88 stores the uninitialized reference. See "Improving the official
89 specification of Java bytecode verification" by Alessandro Coglio.
91 Note that there's no real point in enforcing that padding bytes or
92 the mystery byte of invokeinterface must be 0, but we do that
95 The verifier is currently neither completely lazy nor eager when it
96 comes to loading classes. It tries to represent types by name when
97 possible, and then loads them when it needs to verify a fact about
98 the type. Checking types by name is valid because we only use
99 names which come from the current class' constant pool. Since all
100 such names are looked up using the same class loader, there is no
101 danger that we might be fooled into comparing different types with
104 In the future we plan to allow for a completely lazy mode of
105 operation, where the verifier will construct a list of type
106 assertions to be checked later.
108 Some test cases for the verifier live in the "verify" module of the
109 Mauve test suite. However, some of these are presently
110 (2004-01-20) believed to be incorrect. (More precisely the notion
111 of "correct" is not well-defined, and this verifier differs from
112 others while remaining type-safe.) Some other tests live in the
115 This verifier is also written to be pluggable. This means that it
116 is intended for use in a variety of environments, not just libgcj.
117 As a result the verifier expects a number of type and method
118 declarations to be declared in "verify.h". The intent is that you
119 recompile the verifier for your particular environment. This
120 approach was chosen so that operations could be inlined in verify.h
123 See the verify.h that accompanies this copy of the verifier to see
124 what types, preprocessor defines, and functions must be declared.
125 The interface is ad hoc, but was defined so that it could be
126 implemented to connect to a pure C program.
129 #define FLAG_INSN_START 1
130 #define FLAG_BRANCH_TARGET 2
131 #define FLAG_INSN_SEEN 4
135 struct ref_intersection
;
137 typedef struct state state
;
138 typedef struct type type
;
139 typedef struct ref_intersection ref_intersection
;
141 /*typedef struct state_list state_list;*/
143 typedef struct state_list
146 struct state_list
*next
;
149 typedef struct vfy_string_list
152 struct vfy_string_list
*next
;
155 typedef struct verifier_context
157 /* The current PC. */
159 /* The PC corresponding to the start of the current instruction. */
162 /* The current state of the stack, locals, etc. */
163 state
*current_state
;
165 /* At each branch target we keep a linked list of all the states we
166 can process at that point. We'll only have multiple states at a
167 given PC if they both have different return-address types in the
168 same stack or local slot. This array is indexed by PC and holds
169 the list of all such states. */
172 /* We keep a linked list of all the states which we must reverify.
173 This is the head of the list. */
174 state
*next_verify_state
;
176 /* We keep some flags for each instruction. The values are the
177 FLAG_* constants defined above. This is an array indexed by PC. */
180 /* The bytecode itself. */
181 const unsigned char *bytecode
;
182 /* The exceptions. */
183 vfy_exception
*exception
;
185 /* Defining class. */
186 vfy_jclass current_class
;
188 vfy_method
*current_method
;
190 /* A linked list of utf8 objects we allocate. */
191 vfy_string_list
*utf8_list
;
193 /* A linked list of all ref_intersection objects we allocate. */
194 ref_intersection
*isect_list
;
197 /* The current verifier's state data. This is maintained by
198 {push/pop}_verifier_context to provide a shorthand form to access
199 the verification state. */
200 static GTY(()) verifier_context
*vfr
;
202 /* Local function declarations. */
203 bool type_initialized (type
*t
);
204 int ref_count_dimensions (ref_intersection
*ref
);
207 verify_fail_pc (const char *s
, int pc
)
209 vfy_fail (s
, pc
, vfr
->current_class
, vfr
->current_method
);
213 verify_fail (const char *s
)
215 verify_fail_pc (s
, vfr
->PC
);
218 /* This enum holds a list of tags for all the different types we
219 need to handle. Reference types are treated specially by the
221 typedef enum type_val
225 /* The values for primitive types are chosen to correspond to values
226 specified to newarray. */
236 /* Used when overwriting second word of a double or long in the
237 local variables. Also used after merging local variable states
238 to indicate an unusable value. */
241 /* This is the second word of a two-word value, i.e., a double or
245 /* Everything after `reference_type' must be a reference type. */
248 uninitialized_reference_type
251 /* This represents a merged class type. Some verifiers (including
252 earlier versions of this one) will compute the intersection of
253 two class types when merging states. However, this loses
254 critical information about interfaces implemented by the various
255 classes. So instead we keep track of all the actual classes that
257 struct ref_intersection
259 /* Whether or not this type has been resolved. */
262 /* Actual type data. */
265 /* For a resolved reference type, this is a pointer to the class. */
267 /* For other reference types, this it the name of the class. */
271 /* Link to the next reference in the intersection. */
272 ref_intersection
*ref_next
;
274 /* This is used to keep track of all the allocated
275 ref_intersection objects, so we can free them.
276 FIXME: we should allocate these in chunks. */
277 ref_intersection
*alloc_next
;
280 static ref_intersection
*
283 ref_intersection
*new_ref
=
284 (ref_intersection
*) vfy_alloc (sizeof (ref_intersection
));
286 new_ref
->alloc_next
= vfr
->isect_list
;
287 vfr
->isect_list
= new_ref
;
291 static ref_intersection
*
292 clone_ref (ref_intersection
*dup
)
294 ref_intersection
*new_ref
= make_ref ();
296 new_ref
->is_resolved
= dup
->is_resolved
;
297 new_ref
->data
= dup
->data
;
302 resolve_ref (ref_intersection
*ref
)
304 if (ref
->is_resolved
)
306 ref
->data
.klass
= vfy_find_class (vfr
->current_class
, ref
->data
.name
);
307 ref
->is_resolved
= true;
311 refs_equal (ref_intersection
*ref1
, ref_intersection
*ref2
)
313 if (! ref1
->is_resolved
&& ! ref2
->is_resolved
314 && vfy_strings_equal (ref1
->data
.name
, ref2
->data
.name
))
316 if (! ref1
->is_resolved
)
318 if (! ref2
->is_resolved
)
320 return ref1
->data
.klass
== ref2
->data
.klass
;
323 /* Merge REF1 type into REF2, returning the result. This will
324 return REF2 if all the classes in THIS already appear in
326 static ref_intersection
*
327 merge_refs (ref_intersection
*ref1
, ref_intersection
*ref2
)
329 ref_intersection
*tail
= ref2
;
330 for (; ref1
!= NULL
; ref1
= ref1
->ref_next
)
333 ref_intersection
*iter
;
334 for (iter
= ref2
; iter
!= NULL
; iter
= iter
->ref_next
)
336 if (refs_equal (ref1
, iter
))
345 ref_intersection
*new_tail
= clone_ref (ref1
);
346 new_tail
->ref_next
= tail
;
353 /* See if an object of type SOURCE can be assigned to an object of
354 type TARGET. This might resolve classes in one chain or the other. */
356 ref_compatible (ref_intersection
*target
, ref_intersection
*source
)
358 for (; target
!= NULL
; target
= target
->ref_next
)
360 ref_intersection
*source_iter
= source
;
362 for (; source_iter
!= NULL
; source_iter
= source_iter
->ref_next
)
364 /* Avoid resolving if possible. */
365 if (! target
->is_resolved
366 && ! source_iter
->is_resolved
367 && vfy_strings_equal (target
->data
.name
,
368 source_iter
->data
.name
))
371 if (! target
->is_resolved
)
372 resolve_ref (target
);
373 if (! source_iter
->is_resolved
)
374 resolve_ref (source_iter
);
376 if (! vfy_is_assignable_from (target
->data
.klass
,
377 source_iter
->data
.klass
))
386 ref_isarray (ref_intersection
*ref
)
388 /* assert (ref_next == NULL); */
389 if (ref
->is_resolved
)
390 return vfy_is_array (ref
->data
.klass
);
392 return vfy_string_bytes (ref
->data
.name
)[0] == '[';
396 ref_isinterface (ref_intersection
*ref
)
398 /* assert (ref_next == NULL); */
399 if (! ref
->is_resolved
)
401 return vfy_is_interface (ref
->data
.klass
);
405 ref_isabstract (ref_intersection
*ref
)
407 /* assert (ref_next == NULL); */
408 if (! ref
->is_resolved
)
410 return vfy_is_abstract (ref
->data
.klass
);
414 ref_getclass (ref_intersection
*ref
)
416 if (! ref
->is_resolved
)
418 return ref
->data
.klass
;
422 ref_count_dimensions (ref_intersection
*ref
)
425 if (ref
->is_resolved
)
427 vfy_jclass k
= ref
->data
.klass
;
428 while (vfy_is_array (k
))
430 k
= vfy_get_component_type (k
);
436 const char *p
= vfy_string_bytes (ref
->data
.name
);
443 /* Return the type_val corresponding to a primitive signature
444 character. For instance `I' returns `int.class'. */
446 get_type_val_for_signature (char sig
)
479 verify_fail ("invalid signature");
485 /* Return the type_val corresponding to a primitive class. */
487 get_type_val_for_primtype (vfy_jclass k
)
489 return get_type_val_for_signature (vfy_get_primitive_char (k
));
492 /* The `type' class is used to represent a single type in the verifier. */
498 /* For reference types, the representation of the type. */
499 ref_intersection
*klass
;
501 /* This is used in two situations.
503 First, when constructing a new object, it is the PC of the
504 `new' instruction which created the object. We use the special
505 value UNINIT to mean that this is uninitialized. The special
506 value SELF is used for the case where the current method is
507 itself the <init> method. the special value EITHER is used
508 when we may optionally allow either an uninitialized or
509 initialized reference to match.
511 Second, when the key is return_address_type, this holds the PC
512 of the instruction following the `jsr'. */
520 /* Make a new instance given the type tag. We assume a generic
521 `reference_type' means Object. */
523 init_type_from_tag (type
*t
, type_val k
)
526 /* For reference_type, if KLASS==NULL then that means we are
527 looking for a generic object of any kind, including an
528 uninitialized reference. */
533 /* Make a type for the given type_val tag K. */
535 make_type (type_val k
)
538 init_type_from_tag (&t
, k
);
542 /* Make a new instance given a class. */
544 init_type_from_class (type
*t
, vfy_jclass k
)
546 t
->key
= reference_type
;
547 t
->klass
= make_ref ();
548 t
->klass
->is_resolved
= true;
549 t
->klass
->data
.klass
= k
;
550 t
->klass
->ref_next
= NULL
;
555 make_type_from_class (vfy_jclass k
)
558 init_type_from_class (&t
, k
);
563 init_type_from_string (type
*t
, vfy_string n
)
565 t
->key
= reference_type
;
566 t
->klass
= make_ref ();
567 t
->klass
->is_resolved
= false;
568 t
->klass
->data
.name
= n
;
569 t
->klass
->ref_next
= NULL
;
574 make_type_from_string (vfy_string n
)
577 init_type_from_string (&t
, n
);
581 /* Promote a numeric type. */
583 vfy_promote_type (type
*t
)
585 if (t
->key
== boolean_type
|| t
->key
== char_type
586 || t
->key
== byte_type
|| t
->key
== short_type
)
589 #define promote_type vfy_promote_type
591 /* Mark this type as the uninitialized result of `new'. */
593 type_set_uninitialized (type
*t
, int npc
)
595 if (t
->key
== reference_type
)
596 t
->key
= uninitialized_reference_type
;
598 verify_fail ("internal error in type::uninitialized");
602 /* Mark this type as now initialized. */
604 type_set_initialized (type
*t
, int npc
)
606 if (npc
!= UNINIT
&& t
->pc
== npc
&& t
->key
== uninitialized_reference_type
)
608 t
->key
= reference_type
;
613 /* Mark this type as a particular return address. */
614 static void type_set_return_address (type
*t
, int npc
)
619 /* Return true if this type and type OTHER are considered
620 mergeable for the purposes of state merging. This is related
621 to subroutine handling. For this purpose two types are
622 considered unmergeable if they are both return-addresses but
623 have different PCs. */
625 type_state_mergeable_p (type
*t1
, type
*t2
)
627 return (t1
->key
!= return_address_type
628 || t2
->key
!= return_address_type
629 || t1
->pc
== t2
->pc
);
632 /* Return true if an object of type K can be assigned to a variable
633 of type T. Handle various special cases too. Might modify
634 T or K. Note however that this does not perform numeric
637 types_compatible (type
*t
, type
*k
)
639 /* Any type is compatible with the unsuitable type. */
640 if (k
->key
== unsuitable_type
)
643 if (t
->key
< reference_type
|| k
->key
< reference_type
)
644 return t
->key
== k
->key
;
646 /* The `null' type is convertible to any initialized reference
648 if (t
->key
== null_type
)
649 return k
->key
!= uninitialized_reference_type
;
650 if (k
->key
== null_type
)
651 return t
->key
!= uninitialized_reference_type
;
653 /* A special case for a generic reference. */
654 if (t
->klass
== NULL
)
656 if (k
->klass
== NULL
)
657 verify_fail ("programmer error in type::compatible");
659 /* Handle the special 'EITHER' case, which is only used in a
660 special case of 'putfield'. Note that we only need to handle
661 this on the LHS of a check. */
662 if (! type_initialized (t
) && t
->pc
== EITHER
)
664 /* If the RHS is uninitialized, it must be an uninitialized
666 if (! type_initialized (k
) && k
->pc
!= SELF
)
669 else if (type_initialized (t
) != type_initialized (k
))
671 /* An initialized type and an uninitialized type are not
672 otherwise compatible. */
677 /* Two uninitialized objects are compatible if either:
678 * The PCs are identical, or
679 * One PC is UNINIT. */
680 if (type_initialized (t
))
682 if (t
->pc
!= k
->pc
&& t
->pc
!= UNINIT
&& k
->pc
!= UNINIT
)
687 return ref_compatible (t
->klass
, k
->klass
);
690 /* Return true if two types are equal. Only valid for reference
693 types_equal (type
*t1
, type
*t2
)
695 if ((t1
->key
!= reference_type
&& t1
->key
!= uninitialized_reference_type
)
696 || (t2
->key
!= reference_type
697 && t2
->key
!= uninitialized_reference_type
))
699 /* Only single-ref types are allowed. */
700 if (t1
->klass
->ref_next
|| t2
->klass
->ref_next
)
702 return refs_equal (t1
->klass
, t2
->klass
);
706 type_isvoid (type
*t
)
708 return t
->key
== void_type
;
712 type_iswide (type
*t
)
714 return t
->key
== long_type
|| t
->key
== double_type
;
717 /* Return number of stack or local variable slots taken by this type. */
721 return type_iswide (t
) ? 2 : 1;
725 type_isarray (type
*t
)
727 /* We treat null_type as not an array. This is ok based on the
728 current uses of this method. */
729 if (t
->key
== reference_type
)
730 return ref_isarray (t
->klass
);
735 type_isnull (type
*t
)
737 return t
->key
== null_type
;
741 type_isinterface (type
*t
)
743 if (t
->key
!= reference_type
)
745 return ref_isinterface (t
->klass
);
749 type_isabstract (type
*t
)
751 if (t
->key
!= reference_type
)
753 return ref_isabstract (t
->klass
);
756 /* Return the element type of an array. */
758 type_array_element (type
*t
)
763 if (t
->key
!= reference_type
)
764 verify_fail ("programmer error in type::element_type()");
766 k
= vfy_get_component_type (ref_getclass (t
->klass
));
767 if (vfy_is_primitive (k
))
768 init_type_from_tag (&et
, get_type_val_for_primtype (k
));
770 init_type_from_class (&et
, k
);
774 /* Return the array type corresponding to an initialized
775 reference. We could expand this to work for other kinds of
776 types, but currently we don't need to. */
778 type_to_array (type
*t
)
783 if (t
->key
!= reference_type
)
784 verify_fail ("internal error in type::to_array()");
786 k
= ref_getclass (t
->klass
);
787 init_type_from_class (&at
, vfy_get_array_class (k
));
792 type_isreference (type
*t
)
794 return t
->key
>= reference_type
;
798 type_get_pc (type
*t
)
804 type_initialized (type
*t
)
806 return t
->key
== reference_type
|| t
->key
== null_type
;
810 type_verify_dimensions (type
*t
, int ndims
)
812 /* The way this is written, we don't need to check isarray(). */
813 if (t
->key
!= reference_type
)
814 verify_fail ("internal error in verify_dimensions:"
815 " not a reference type");
817 if (ref_count_dimensions (t
->klass
) < ndims
)
818 verify_fail ("array type has fewer dimensions"
822 /* Merge OLD_TYPE into this. On error throw exception. Return
823 true if the merge caused a type change. */
825 merge_types (type
*t
, type
*old_type
, bool local_semantics
)
827 bool changed
= false;
828 bool refo
= type_isreference (old_type
);
829 bool refn
= type_isreference (t
);
832 if (old_type
->key
== null_type
)
834 else if (t
->key
== null_type
)
839 else if (type_initialized (t
) != type_initialized (old_type
))
840 verify_fail ("merging initialized and uninitialized types");
843 ref_intersection
*merged
;
844 if (! type_initialized (t
))
847 t
->pc
= old_type
->pc
;
848 else if (old_type
->pc
== UNINIT
)
850 else if (t
->pc
!= old_type
->pc
)
851 verify_fail ("merging different uninitialized types");
854 merged
= merge_refs (old_type
->klass
, t
->klass
);
855 if (merged
!= t
->klass
)
862 else if (refo
|| refn
|| t
->key
!= old_type
->key
)
866 /* If we already have an `unsuitable' type, then we
867 don't need to change again. */
868 if (t
->key
!= unsuitable_type
)
870 t
->key
= unsuitable_type
;
875 verify_fail ("unmergeable type");
887 case boolean_type
: c
= 'Z'; break;
888 case byte_type
: c
= 'B'; break;
889 case char_type
: c
= 'C'; break;
890 case short_type
: c
= 'S'; break;
891 case int_type
: c
= 'I'; break;
892 case long_type
: c
= 'J'; break;
893 case float_type
: c
= 'F'; break;
894 case double_type
: c
= 'D'; break;
895 case void_type
: c
= 'V'; break;
896 case unsuitable_type
: c
= '-'; break;
897 case return_address_type
: c
= 'r'; break;
898 case continuation_type
: c
= '+'; break;
899 case reference_type
: c
= 'L'; break;
900 case null_type
: c
= '@'; break;
901 case uninitialized_reference_type
: c
= 'U'; break;
903 debug_print ("%c", c
);
905 #endif /* VERIFY_DEBUG */
907 /* This class holds all the state information we need for a given
911 /* The current top of the stack, in terms of slots. */
913 /* The current depth of the stack. This will be larger than
914 STACKTOP when wide types are on the stack. */
918 /* The local variables. */
920 /* We keep track of the type of `this' specially. This is used to
921 ensure that an instance initializer invokes another initializer
922 on `this' before returning. We must keep track of this
923 specially because otherwise we might be confused by code which
924 assigns to locals[0] (overwriting `this') and then returns
925 without really initializing. */
928 /* The PC for this state. This is only valid on states which are
929 permanently attached to a given PC. For an object like
930 `current_state', which is used transiently, this has no
933 /* We keep a linked list of all states requiring reverification.
934 If this is the special value INVALID_STATE then this state is
935 not on the list. NULL marks the end of the linked list. */
939 /* NO_NEXT is the PC value meaning that a new state must be
940 acquired from the verification list. */
944 init_state_with_stack (state
*s
, int max_stack
, int max_locals
)
949 s
->stack
= (type
*) vfy_alloc (max_stack
* sizeof (type
));
950 for (i
= 0; i
< max_stack
; ++i
)
951 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
952 s
->locals
= (type
*) vfy_alloc (max_locals
* sizeof (type
));
953 for (i
= 0; i
< max_locals
; ++i
)
954 init_type_from_tag (&s
->locals
[i
], unsuitable_type
);
955 init_type_from_tag (&s
->this_type
, unsuitable_type
);
957 s
->next
= INVALID_STATE
;
961 copy_state (state
*s
, state
*copy
, int max_stack
, int max_locals
)
964 s
->stacktop
= copy
->stacktop
;
965 s
->stackdepth
= copy
->stackdepth
;
966 for (i
= 0; i
< max_stack
; ++i
)
967 s
->stack
[i
] = copy
->stack
[i
];
968 for (i
= 0; i
< max_locals
; ++i
)
969 s
->locals
[i
] = copy
->locals
[i
];
971 s
->this_type
= copy
->this_type
;
972 /* Don't modify `next' or `pc'. */
976 copy_state_with_stack (state
*s
, state
*orig
, int max_stack
, int max_locals
)
978 init_state_with_stack (s
, max_stack
, max_locals
);
979 copy_state (s
, orig
, max_stack
, max_locals
);
982 /* Allocate a new state, copying ORIG. */
984 make_state_copy (state
*orig
, int max_stack
, int max_locals
)
986 state
*s
= vfy_alloc (sizeof (state
));
987 copy_state_with_stack (s
, orig
, max_stack
, max_locals
);
992 make_state (int max_stack
, int max_locals
)
994 state
*s
= vfy_alloc (sizeof (state
));
995 init_state_with_stack (s
, max_stack
, max_locals
);
1000 free_state (state
*s
)
1002 if (s
->stack
!= NULL
)
1003 vfy_free (s
->stack
);
1004 if (s
->locals
!= NULL
)
1005 vfy_free (s
->locals
);
1008 /* Modify this state to reflect entry to an exception handler. */
1010 state_set_exception (state
*s
, type
*t
, int max_stack
)
1016 for (i
= s
->stacktop
; i
< max_stack
; ++i
)
1017 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
1020 /* Merge STATE_OLD into this state. Destructively modifies this
1021 state. Returns true if the new state was in fact changed.
1022 Will throw an exception if the states are not mergeable. */
1024 merge_states (state
*s
, state
*state_old
, int max_locals
)
1027 bool changed
= false;
1029 /* Special handling for `this'. If one or the other is
1030 uninitialized, then the merge is uninitialized. */
1031 if (type_initialized (&s
->this_type
))
1032 s
->this_type
= state_old
->this_type
;
1035 if (state_old
->stacktop
!= s
->stacktop
) /* FIXME stackdepth instead? */
1036 verify_fail ("stack sizes differ");
1037 for (i
= 0; i
< state_old
->stacktop
; ++i
)
1039 if (merge_types (&s
->stack
[i
], &state_old
->stack
[i
], false))
1043 /* Merge local variables. */
1044 for (i
= 0; i
< max_locals
; ++i
)
1046 if (merge_types (&s
->locals
[i
], &state_old
->locals
[i
], true))
1053 /* Ensure that `this' has been initialized. */
1055 state_check_this_initialized (state
*s
)
1057 if (type_isreference (&s
->this_type
) && ! type_initialized (&s
->this_type
))
1058 verify_fail ("`this' is uninitialized");
1061 /* Set type of `this'. */
1063 state_set_this_type (state
*s
, type
*k
)
1068 /* Mark each `new'd object we know of that was allocated at PC as
1071 state_set_initialized (state
*s
, int pc
, int max_locals
)
1074 for (i
= 0; i
< s
->stacktop
; ++i
)
1075 type_set_initialized (&s
->stack
[i
], pc
);
1076 for (i
= 0; i
< max_locals
; ++i
)
1077 type_set_initialized (&s
->locals
[i
], pc
);
1078 type_set_initialized (&s
->this_type
, pc
);
1081 /* This tests to see whether two states can be considered "merge
1082 compatible". If both states have a return-address in the same
1083 slot, and the return addresses are different, then they are not
1084 compatible and we must not try to merge them. */
1086 state_mergeable_p (state
*s
, state
*other
, int max_locals
)
1091 /* This is tricky: if the stack sizes differ, then not only are
1092 these not mergeable, but in fact we should give an error, as
1093 we've found two execution paths that reach a branch target
1094 with different stack depths. FIXME stackdepth instead? */
1095 if (s
->stacktop
!= other
->stacktop
)
1096 verify_fail ("stack sizes differ");
1098 for (i
= 0; i
< s
->stacktop
; ++i
)
1099 if (! type_state_mergeable_p (&s
->stack
[i
], &other
->stack
[i
]))
1101 for (i
= 0; i
< max_locals
; ++i
)
1102 if (! type_state_mergeable_p (&s
->locals
[i
], &other
->locals
[i
]))
1108 state_reverify (state
*s
)
1110 if (s
->next
== INVALID_STATE
)
1112 s
->next
= vfr
->next_verify_state
;
1113 vfr
->next_verify_state
= s
;
1119 debug_print_state (state
*s
, const char *leader
, int pc
, int max_stack
,
1123 debug_print ("%s [%4d]: [stack] ", leader
, pc
);
1124 for (i
= 0; i
< s
->stacktop
; ++i
)
1125 type_print (&s
->stack
[i
]);
1126 for (; i
< max_stack
; ++i
)
1128 debug_print (" [local] ");
1129 for (i
= 0; i
< max_locals
; ++i
)
1130 type_print (&s
->locals
[i
]);
1131 debug_print (" | %p\n", s
);
1135 debug_print_state (state
*s ATTRIBUTE_UNUSED
,
1136 const char *leader ATTRIBUTE_UNUSED
,
1137 int pc ATTRIBUTE_UNUSED
, int max_stack ATTRIBUTE_UNUSED
,
1138 int max_locals ATTRIBUTE_UNUSED
)
1141 #endif /* VERIFY_DEBUG */
1147 state
*s
= vfr
->current_state
;
1148 if (s
->stacktop
<= 0)
1149 verify_fail ("stack empty");
1150 r
= s
->stack
[--s
->stacktop
];
1151 s
->stackdepth
-= type_depth (&r
);
1152 if (s
->stackdepth
< 0)
1153 verify_fail_pc ("stack empty", vfr
->start_PC
);
1160 type r
= pop_raw ();
1161 if (type_iswide (&r
))
1162 verify_fail ("narrow pop of wide type");
1167 vfy_pop_type_t (type match
)
1170 vfy_promote_type (&match
);
1172 if (! types_compatible (&match
, &t
))
1173 verify_fail ("incompatible type on stack");
1178 vfy_pop_type (type_val match
)
1180 type t
= make_type (match
);
1181 return vfy_pop_type_t (t
);
1184 #define pop_type vfy_pop_type
1185 #define pop_type_t vfy_pop_type_t
1187 /* Pop a reference which is guaranteed to be initialized. MATCH
1188 doesn't have to be a reference type; in this case this acts like
1191 pop_init_ref_t (type match
)
1193 type t
= pop_raw ();
1194 if (type_isreference (&t
) && ! type_initialized (&t
))
1195 verify_fail ("initialized reference required");
1196 else if (! types_compatible (&match
, &t
))
1197 verify_fail ("incompatible type on stack");
1202 pop_init_ref (type_val match
)
1204 type t
= make_type (match
);
1205 return pop_init_ref_t (t
);
1208 /* Pop a reference type or a return address. */
1210 pop_ref_or_return (void)
1212 type t
= pop_raw ();
1213 if (! type_isreference (&t
) && t
.key
!= return_address_type
)
1214 verify_fail ("expected reference or return address on stack");
1219 vfy_push_type_t (type t
)
1222 state
*s
= vfr
->current_state
;
1223 /* If T is a numeric type like short, promote it to int. */
1226 depth
= type_depth (&t
);
1228 if (s
->stackdepth
+ depth
> vfr
->current_method
->max_stack
)
1229 verify_fail ("stack overflow");
1230 s
->stack
[s
->stacktop
++] = t
;
1231 s
->stackdepth
+= depth
;
1235 vfy_push_type (type_val tval
)
1237 type t
= make_type (tval
);
1238 vfy_push_type_t (t
);
1241 #define push_type vfy_push_type
1242 #define push_type_t vfy_push_type_t
1245 set_variable (int index
, type t
)
1248 state
*s
= vfr
->current_state
;
1249 /* If T is a numeric type like short, promote it to int. */
1252 depth
= type_depth (&t
);
1253 if (index
> vfr
->current_method
->max_locals
- depth
)
1254 verify_fail ("invalid local variable");
1255 s
->locals
[index
] = t
;
1258 init_type_from_tag (&s
->locals
[index
+ 1], continuation_type
);
1259 if (index
> 0 && type_iswide (&s
->locals
[index
- 1]))
1260 init_type_from_tag (&s
->locals
[index
- 1], unsuitable_type
);
1264 get_variable_t (int index
, type
*t
)
1266 state
*s
= vfr
->current_state
;
1267 int depth
= type_depth (t
);
1268 if (index
> vfr
->current_method
->max_locals
- depth
)
1269 verify_fail ("invalid local variable");
1270 if (! types_compatible (t
, &s
->locals
[index
]))
1271 verify_fail ("incompatible type in local variable");
1274 type cont
= make_type (continuation_type
);
1275 if (! types_compatible (&s
->locals
[index
+ 1], &cont
))
1276 verify_fail ("invalid local variable");
1278 return s
->locals
[index
];
1282 get_variable (int index
, type_val v
)
1284 type t
= make_type (v
);
1285 return get_variable_t (index
, &t
);
1288 /* Make sure ARRAY is an array type and that its elements are
1289 compatible with type ELEMENT. Returns the actual element type. */
1291 require_array_type_t (type array
, type element
)
1294 /* An odd case. Here we just pretend that everything went ok. If
1295 the requested element type is some kind of reference, return
1296 the null type instead. */
1297 if (type_isnull (&array
))
1298 return type_isreference (&element
) ? make_type (null_type
) : element
;
1300 if (! type_isarray (&array
))
1301 verify_fail ("array required");
1303 t
= type_array_element (&array
);
1304 if (! types_compatible (&element
, &t
))
1306 /* Special case for byte arrays, which must also be boolean
1309 if (element
.key
== byte_type
)
1311 type e2
= make_type (boolean_type
);
1312 ok
= types_compatible (&e2
, &t
);
1315 verify_fail ("incompatible array element type");
1318 /* Return T and not ELEMENT, because T might be specialized. */
1323 require_array_type (type array
, type_val element
)
1325 type t
= make_type (element
);
1326 return require_array_type_t (array
, t
);
1332 if (vfr
->PC
>= vfr
->current_method
->code_length
)
1333 verify_fail ("premature end of bytecode");
1334 return (jint
) vfr
->bytecode
[vfr
->PC
++] & 0xff;
1340 jint b1
= get_byte ();
1341 jint b2
= get_byte ();
1342 return (jint
) ((b1
<< 8) | b2
) & 0xffff;
1348 signed char b1
= (signed char) get_byte ();
1349 jint b2
= get_byte ();
1350 jshort s
= (b1
<< 8) | b2
;
1357 jint b1
= get_byte ();
1358 jint b2
= get_byte ();
1359 jint b3
= get_byte ();
1360 jint b4
= get_byte ();
1361 jword result
= (b1
<< 24) | (b2
<< 16) | (b3
<< 8) | b4
;
1362 /* In the compiler, 'jint' might have more than 32 bits, so we must
1364 return WORD_TO_INT (result
);
1368 compute_jump (int offset
)
1370 int npc
= vfr
->start_PC
+ offset
;
1371 if (npc
< 0 || npc
>= vfr
->current_method
->code_length
)
1372 verify_fail_pc ("branch out of range", vfr
->start_PC
);
1376 /* Add a new state to the state list at NPC. */
1378 add_new_state (int npc
, state
*old_state
)
1381 vfy_method
*current_method
= vfr
->current_method
;
1382 state
*new_state
= make_state_copy (old_state
, current_method
->max_stack
,
1383 current_method
->max_locals
);
1384 debug_print ("== New state in add_new_state\n");
1385 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1386 current_method
->max_locals
);
1388 nlink
= vfy_alloc (sizeof (state_list
));
1389 nlink
->val
= new_state
;
1390 nlink
->next
= vfr
->states
[npc
];
1391 vfr
->states
[npc
] = nlink
;
1392 new_state
->pc
= npc
;
1396 /* Merge the indicated state into the state at the branch target and
1397 schedule a new PC if there is a change. NPC is the PC of the
1398 branch target, and FROM_STATE is the state at the source of the
1399 branch. This method returns true if the destination state
1400 changed and requires reverification, false otherwise. */
1402 merge_into (int npc
, state
*from_state
)
1404 /* Iterate over all target states and merge our state into each,
1405 if applicable. FIXME one improvement we could make here is
1406 "state destruction". Merging a new state into an existing one
1407 might cause a return_address_type to be merged to
1408 unsuitable_type. In this case the resulting state may now be
1409 mergeable with other states currently held in parallel at this
1410 location. So in this situation we could pairwise compare and
1411 reduce the number of parallel states. */
1413 bool applicable
= false;
1414 for (iter
= vfr
->states
[npc
]; iter
!= NULL
; iter
= iter
->next
)
1416 state
*new_state
= iter
->val
;
1417 vfy_method
*current_method
= vfr
->current_method
;
1419 if (state_mergeable_p (new_state
, from_state
,
1420 current_method
->max_locals
))
1425 debug_print ("== Merge states in merge_into\n");
1426 debug_print_state (from_state
, "Frm", vfr
->start_PC
, current_method
->max_stack
,
1427 current_method
->max_locals
);
1428 debug_print_state (new_state
, " To", npc
, current_method
->max_stack
,
1429 current_method
->max_locals
);
1430 changed
= merge_states (new_state
, from_state
,
1431 current_method
->max_locals
);
1432 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1433 current_method
->max_locals
);
1436 state_reverify (new_state
);
1442 /* Either we don't yet have a state at NPC, or we have a
1443 return-address type that is in conflict with all existing
1444 state. So, we need to create a new entry. */
1445 state
*new_state
= add_new_state (npc
, from_state
);
1446 /* A new state added in this way must always be reverified. */
1447 state_reverify (new_state
);
1452 push_jump (int offset
)
1454 int npc
= compute_jump (offset
);
1455 /* According to the JVM Spec, we need to check for uninitialized
1456 objects here. However, this does not actually affect type
1457 safety, and the Eclipse java compiler generates code that
1458 violates this constraint. */
1459 merge_into (npc
, vfr
->current_state
);
1463 push_exception_jump (type t
, int pc
)
1466 /* According to the JVM Spec, we need to check for uninitialized
1467 objects here. However, this does not actually affect type
1468 safety, and the Eclipse java compiler generates code that
1469 violates this constraint. */
1470 copy_state_with_stack (&s
, vfr
->current_state
,
1471 vfr
->current_method
->max_stack
,
1472 vfr
->current_method
->max_locals
);
1473 if (vfr
->current_method
->max_stack
< 1)
1474 verify_fail ("stack overflow at exception handler");
1475 state_set_exception (&s
, &t
, vfr
->current_method
->max_stack
);
1476 merge_into (pc
, &s
);
1477 /* FIXME: leak.. need free_state or GC */
1483 state
*new_state
= vfr
->next_verify_state
;
1484 if (new_state
== INVALID_STATE
)
1485 verify_fail ("programmer error in pop_jump");
1486 if (new_state
!= NULL
)
1488 vfr
->next_verify_state
= new_state
->next
;
1489 new_state
->next
= INVALID_STATE
;
1495 invalidate_pc (void)
1501 note_branch_target (int pc
)
1503 /* Don't check `pc <= PC', because we've advanced PC after
1504 fetching the target and we haven't yet checked the next
1506 if (pc
< vfr
->PC
&& ! (vfr
->flags
[pc
] & FLAG_INSN_START
))
1507 verify_fail_pc ("branch not to instruction start", vfr
->start_PC
);
1508 vfr
->flags
[pc
] |= FLAG_BRANCH_TARGET
;
1514 while ((vfr
->PC
% 4) > 0)
1515 if (get_byte () != 0)
1516 verify_fail ("found nonzero padding byte");
1519 /* Do the work for a `ret' instruction. INDEX is the index into the
1522 handle_ret_insn (int index
)
1524 type ret
= make_type (return_address_type
);
1525 type ret_addr
= get_variable_t (index
, &ret
);
1526 /* It would be nice if we could do this. However, the JVM Spec
1527 doesn't say that this is what happens. It is implied that
1528 reusing a return address is invalid, but there's no actual
1529 prohibition against it. */
1530 /* set_variable (index, unsuitable_type); */
1532 int npc
= type_get_pc (&ret_addr
);
1533 /* We might be returning to a `jsr' that is at the end of the
1534 bytecode. This is ok if we never return from the called
1535 subroutine, but if we see this here it is an error. */
1536 if (npc
>= vfr
->current_method
->code_length
)
1537 verify_fail ("fell off end");
1539 /* According to the JVM Spec, we need to check for uninitialized
1540 objects here. However, this does not actually affect type
1541 safety, and the Eclipse java compiler generates code that
1542 violates this constraint. */
1543 merge_into (npc
, vfr
->current_state
);
1547 static void handle_jsr_insn (int offset
)
1550 int npc
= compute_jump (offset
);
1552 /* According to the JVM Spec, we need to check for uninitialized
1553 objects here. However, this does not actually affect type
1554 safety, and the Eclipse java compiler generates code that
1555 violates this constraint. */
1557 /* Modify our state as appropriate for entry into a subroutine. */
1558 ret_addr
= make_type (return_address_type
);
1559 type_set_return_address (&ret_addr
, vfr
->PC
);
1560 vfy_push_type_t (ret_addr
);
1561 merge_into (npc
, vfr
->current_state
);
1566 construct_primitive_array_type (type_val prim
)
1568 vfy_jclass k
= NULL
;
1579 k
= vfy_get_primitive_type ((int) prim
);
1582 /* These aren't used here but we call them out to avoid
1585 case unsuitable_type
:
1586 case return_address_type
:
1587 case continuation_type
:
1588 case reference_type
:
1590 case uninitialized_reference_type
:
1592 verify_fail ("unknown type in construct_primitive_array_type");
1594 k
= vfy_get_array_class (k
);
1598 /* This pass computes the location of branch targets and also
1599 instruction starts. */
1601 branch_prepass (void)
1604 vfr
->flags
= (char *) vfy_alloc (vfr
->current_method
->code_length
);
1606 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
1610 while (vfr
->PC
< vfr
->current_method
->code_length
)
1613 /* Set `start_PC' early so that error checking can have the
1615 vfr
->start_PC
= vfr
->PC
;
1616 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_START
;
1618 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
1622 case op_aconst_null
:
1758 case op_monitorenter
:
1759 case op_monitorexit
:
1767 case op_arraylength
:
1799 case op_invokespecial
:
1800 case op_invokestatic
:
1801 case op_invokevirtual
:
1805 case op_multianewarray
:
1828 note_branch_target (compute_jump (get_short ()));
1831 case op_tableswitch
:
1835 note_branch_target (compute_jump (get_int ()));
1839 verify_fail_pc ("invalid tableswitch", vfr
->start_PC
);
1840 for (i
= low
; i
<= hi
; ++i
)
1841 note_branch_target (compute_jump (get_int ()));
1845 case op_lookupswitch
:
1849 note_branch_target (compute_jump (get_int ()));
1850 npairs
= get_int ();
1852 verify_fail_pc ("too few pairs in lookupswitch", vfr
->start_PC
);
1853 while (npairs
-- > 0)
1856 note_branch_target (compute_jump (get_int ()));
1861 case op_invokeinterface
:
1869 opcode
= (java_opcode
) get_byte ();
1871 if (opcode
== op_iinc
)
1878 note_branch_target (compute_jump (get_int ()));
1882 /* These are unused here, but we call them out explicitly
1883 so that -Wswitch-enum doesn't complain. */
1889 case op_putstatic_1
:
1890 case op_putstatic_2
:
1891 case op_putstatic_4
:
1892 case op_putstatic_8
:
1893 case op_putstatic_a
:
1895 case op_getfield_2s
:
1896 case op_getfield_2u
:
1900 case op_getstatic_1
:
1901 case op_getstatic_2s
:
1902 case op_getstatic_2u
:
1903 case op_getstatic_4
:
1904 case op_getstatic_8
:
1905 case op_getstatic_a
:
1906 #endif /* VFY_FAST_OPCODES */
1908 verify_fail_pc ("unrecognized instruction in branch_prepass",
1912 /* See if any previous branch tried to branch to the middle of
1913 this instruction. */
1914 for (pc
= vfr
->start_PC
+ 1; pc
< vfr
->PC
; ++pc
)
1916 if ((vfr
->flags
[pc
] & FLAG_BRANCH_TARGET
))
1917 verify_fail_pc ("branch to middle of instruction", pc
);
1921 /* Verify exception handlers. */
1922 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
1924 int handler
, start
, end
, htype
;
1925 vfy_get_exception (vfr
->exception
, i
, &handler
, &start
, &end
, &htype
);
1926 if (! (vfr
->flags
[handler
] & FLAG_INSN_START
))
1927 verify_fail_pc ("exception handler not at instruction start",
1929 if (! (vfr
->flags
[start
] & FLAG_INSN_START
))
1930 verify_fail_pc ("exception start not at instruction start", start
);
1931 if (end
!= vfr
->current_method
->code_length
1932 && ! (vfr
->flags
[end
] & FLAG_INSN_START
))
1933 verify_fail_pc ("exception end not at instruction start", end
);
1935 vfr
->flags
[handler
] |= FLAG_BRANCH_TARGET
;
1940 check_pool_index (int index
)
1942 if (index
< 0 || index
>= vfy_get_constants_size (vfr
->current_class
))
1943 verify_fail_pc ("constant pool index out of range", vfr
->start_PC
);
1947 check_class_constant (int index
)
1949 type t
= { 0, 0, 0 };
1950 vfy_constants
*pool
;
1952 check_pool_index (index
);
1953 pool
= vfy_get_constants (vfr
->current_class
);
1954 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedClass
)
1955 init_type_from_class (&t
, vfy_get_pool_class (pool
, index
));
1956 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Class
)
1957 init_type_from_string (&t
, vfy_get_pool_string (pool
, index
));
1959 verify_fail_pc ("expected class constant", vfr
->start_PC
);
1964 check_constant (int index
)
1966 type t
= { 0, 0, 0 };
1967 vfy_constants
*pool
;
1969 check_pool_index (index
);
1970 pool
= vfy_get_constants (vfr
->current_class
);
1971 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedString
1972 || vfy_tag (pool
, index
) == JV_CONSTANT_String
)
1973 init_type_from_class (&t
, vfy_string_type ());
1974 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Integer
)
1975 init_type_from_tag (&t
, int_type
);
1976 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Float
)
1977 init_type_from_tag (&t
, float_type
);
1979 verify_fail_pc ("String, int, or float constant expected", vfr
->start_PC
);
1984 check_wide_constant (int index
)
1986 type t
= { 0, 0, 0 };
1987 vfy_constants
*pool
;
1989 check_pool_index (index
);
1990 pool
= vfy_get_constants (vfr
->current_class
);
1991 if (vfy_tag (pool
, index
) == JV_CONSTANT_Long
)
1992 init_type_from_tag (&t
, long_type
);
1993 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Double
)
1994 init_type_from_tag (&t
, double_type
);
1996 verify_fail_pc ("long or double constant expected", vfr
->start_PC
);
2000 /* Helper for both field and method. These are laid out the same in
2001 the constant pool. */
2003 handle_field_or_method (int index
, int expected
,
2004 vfy_string
*name
, vfy_string
*fmtype
)
2006 vfy_uint_16 class_index
, name_and_type_index
;
2007 vfy_uint_16 name_index
, desc_index
;
2008 vfy_constants
*pool
;
2010 check_pool_index (index
);
2011 pool
= vfy_get_constants (vfr
->current_class
);
2012 if (vfy_tag (pool
, index
) != expected
)
2013 verify_fail_pc ("didn't see expected constant", vfr
->start_PC
);
2014 /* Once we know we have a Fieldref or Methodref we assume that it
2015 is correctly laid out in the constant pool. I think the code
2016 in defineclass.cc guarantees this. */
2017 vfy_load_indexes (pool
, index
, &class_index
, &name_and_type_index
);
2018 vfy_load_indexes (pool
, name_and_type_index
, &name_index
, &desc_index
);
2020 *name
= vfy_get_pool_string (pool
, name_index
);
2021 *fmtype
= vfy_get_pool_string (pool
, desc_index
);
2023 return check_class_constant (class_index
);
2026 /* Return field's type, compute class' type if requested. If
2027 PUTFIELD is true, use the special 'putfield' semantics. */
2029 check_field_constant (int index
, type
*class_type
, bool putfield
)
2031 vfy_string name
, field_type
;
2036 type ct
= handle_field_or_method (index
,
2037 JV_CONSTANT_Fieldref
,
2038 &name
, &field_type
);
2041 typec
= vfy_string_bytes (field_type
);
2042 len
= vfy_string_length (field_type
);
2043 if (typec
[0] == '[' || typec
[0] == 'L')
2044 init_type_from_string (&t
, field_type
);
2046 init_type_from_tag (&t
, get_type_val_for_signature (typec
[0]));
2048 /* We have an obscure special case here: we can use `putfield' on a
2049 field declared in this class, even if `this' has not yet been
2052 && ! type_initialized (&vfr
->current_state
->this_type
)
2053 && vfr
->current_state
->this_type
.pc
== SELF
2054 && types_equal (&vfr
->current_state
->this_type
, &ct
)
2055 && vfy_class_has_field (vfr
->current_class
, name
, field_type
))
2056 /* Note that we don't actually know whether we're going to match
2057 against 'this' or some other object of the same type. So,
2058 here we set things up so that it doesn't matter. This relies
2059 on knowing what our caller is up to. */
2060 type_set_uninitialized (class_type
, EITHER
);
2066 check_method_constant (int index
, bool is_interface
,
2067 vfy_string
*method_name
,
2068 vfy_string
*method_signature
)
2070 return handle_field_or_method (index
,
2072 ? JV_CONSTANT_InterfaceMethodref
2073 : JV_CONSTANT_Methodref
),
2074 method_name
, method_signature
);
2078 get_one_type (char *p
, type
*t
)
2080 const char *start
= p
;
2100 name
= vfy_get_string (start
, p
- start
);
2101 *t
= make_type_from_string (name
);
2105 /* Casting to jchar here is ok since we are looking at an ASCII
2107 rt
= get_type_val_for_signature (v
);
2109 if (arraycount
== 0)
2111 /* Callers of this function eventually push their arguments on
2112 the stack. So, promote them here. */
2113 type new_t
= make_type (rt
);
2114 vfy_promote_type (&new_t
);
2119 k
= construct_primitive_array_type (rt
);
2120 while (--arraycount
> 0)
2121 k
= vfy_get_array_class (k
);
2122 *t
= make_type_from_class (k
);
2127 compute_argument_types (vfy_string signature
, type
*types
)
2130 char *p
= (char *) vfy_string_bytes (signature
);
2137 p
= get_one_type (p
, &types
[i
++]);
2141 compute_return_type (vfy_string signature
)
2143 char *p
= (char *) vfy_string_bytes (signature
);
2148 get_one_type (p
, &t
);
2153 check_return_type (type onstack
)
2155 type rt
= compute_return_type (vfy_get_signature (vfr
->current_method
));
2156 if (! types_compatible (&rt
, &onstack
))
2157 verify_fail ("incompatible return type");
2160 /* Initialize the stack for the new method. Returns true if this
2161 method is an instance initializer. */
2163 initialize_stack (void)
2167 bool is_init
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2169 bool is_clinit
= vfy_strings_equal (vfy_get_method_name (vfr
->current_method
),
2172 if (! vfy_is_static (vfr
->current_method
))
2174 type kurr
= make_type_from_class (vfr
->current_class
);
2177 type_set_uninitialized (&kurr
, SELF
);
2181 verify_fail ("<clinit> method must be static");
2182 set_variable (0, kurr
);
2183 state_set_this_type (vfr
->current_state
, &kurr
);
2189 verify_fail ("<init> method must be non-static");
2192 /* We have to handle wide arguments specially here. */
2193 arg_count
= vfy_count_arguments (vfy_get_signature (vfr
->current_method
));
2195 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2196 compute_argument_types (vfy_get_signature (vfr
->current_method
), arg_types
);
2197 for (i
= 0; i
< arg_count
; ++i
)
2199 set_variable (var
, arg_types
[i
]);
2201 if (type_iswide (&arg_types
[i
]))
2204 vfy_free (arg_types
);
2211 verify_instructions_0 (void)
2216 vfr
->current_state
= make_state (vfr
->current_method
->max_stack
,
2217 vfr
->current_method
->max_locals
);
2222 /* True if we are verifying an instance initializer. */
2223 this_is_init
= initialize_stack ();
2225 vfr
->states
= (state_list
**) vfy_alloc (sizeof (state_list
*)
2226 * vfr
->current_method
->code_length
);
2228 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
2229 vfr
->states
[i
] = NULL
;
2231 vfr
->next_verify_state
= NULL
;
2237 /* If the PC was invalidated, get a new one from the work list. */
2238 if (vfr
->PC
== NO_NEXT
)
2240 state
*new_state
= pop_jump ();
2241 /* If it is null, we're done. */
2242 if (new_state
== NULL
)
2245 vfr
->PC
= new_state
->pc
;
2246 debug_print ("== State pop from pending list\n");
2247 /* Set up the current state. */
2248 copy_state (vfr
->current_state
, new_state
,
2249 vfr
->current_method
->max_stack
, vfr
->current_method
->max_locals
);
2253 /* We only have to do this checking in the situation where
2254 control flow falls through from the previous instruction.
2255 Otherwise merging is done at the time we push the branch.
2256 Note that we'll catch the off-the-end problem just
2258 if (vfr
->PC
< vfr
->current_method
->code_length
2259 && vfr
->states
[vfr
->PC
] != NULL
)
2261 /* We've already visited this instruction. So merge
2262 the states together. It is simplest, but not most
2263 efficient, to just always invalidate the PC here. */
2264 merge_into (vfr
->PC
, vfr
->current_state
);
2270 /* Control can't fall off the end of the bytecode. We need to
2271 check this in both cases, not just the fall-through case,
2272 because we don't check to see whether a `jsr' appears at
2273 the end of the bytecode until we process a `ret'. */
2274 if (vfr
->PC
>= vfr
->current_method
->code_length
)
2275 verify_fail ("fell off end");
2276 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_SEEN
;
2278 /* We only have to keep saved state at branch targets. If
2279 we're at a branch target and the state here hasn't been set
2280 yet, we set it now. You might notice that `ret' targets
2281 won't necessarily have FLAG_BRANCH_TARGET set. This
2282 doesn't matter, since those states will be filled in by
2284 /* Note that other parts of the compiler assume that there is a
2285 label with a type map at PC=0. */
2286 if (vfr
->states
[vfr
->PC
] == NULL
2287 && (vfr
->PC
== 0 || (vfr
->flags
[vfr
->PC
] & FLAG_BRANCH_TARGET
) != 0))
2288 add_new_state (vfr
->PC
, vfr
->current_state
);
2290 /* Set this before handling exceptions so that debug output is
2292 vfr
->start_PC
= vfr
->PC
;
2294 /* Update states for all active exception handlers. Ordinarily
2295 there are not many exception handlers. So we simply run
2296 through them all. */
2297 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
2299 int hpc
, start
, end
, htype
;
2300 vfy_get_exception (vfr
->exception
, i
, &hpc
, &start
, &end
, &htype
);
2301 if (vfr
->PC
>= start
&& vfr
->PC
< end
)
2303 type handler
= make_type_from_class (vfy_throwable_type ());
2305 handler
= check_class_constant (htype
);
2306 push_exception_jump (handler
, hpc
);
2311 debug_print_state (vfr
->current_state
, " ", vfr
->PC
,
2312 vfr
->current_method
->max_stack
,
2313 vfr
->current_method
->max_locals
);
2314 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
2320 case op_aconst_null
:
2321 push_type (null_type
);
2331 push_type (int_type
);
2336 push_type (long_type
);
2342 push_type (float_type
);
2347 push_type (double_type
);
2352 push_type (int_type
);
2357 push_type (int_type
);
2361 push_type_t (check_constant (get_byte ()));
2364 push_type_t (check_constant (get_ushort ()));
2367 push_type_t (check_wide_constant (get_ushort ()));
2371 push_type_t (get_variable (get_byte (), int_type
));
2374 push_type_t (get_variable (get_byte (), long_type
));
2377 push_type_t (get_variable (get_byte (), float_type
));
2380 push_type_t (get_variable (get_byte (), double_type
));
2383 push_type_t (get_variable (get_byte (), reference_type
));
2390 push_type_t (get_variable (opcode
- op_iload_0
, int_type
));
2396 push_type_t (get_variable (opcode
- op_lload_0
, long_type
));
2402 push_type_t (get_variable (opcode
- op_fload_0
, float_type
));
2408 push_type_t (get_variable (opcode
- op_dload_0
, double_type
));
2414 push_type_t (get_variable (opcode
- op_aload_0
, reference_type
));
2417 pop_type (int_type
);
2418 push_type_t (require_array_type (pop_init_ref (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 require_array_type (pop_init_ref (reference_type
), byte_type
);
2444 push_type (int_type
);
2447 pop_type (int_type
);
2448 require_array_type (pop_init_ref (reference_type
), char_type
);
2449 push_type (int_type
);
2452 pop_type (int_type
);
2453 require_array_type (pop_init_ref (reference_type
), short_type
);
2454 push_type (int_type
);
2457 set_variable (get_byte (), pop_type (int_type
));
2460 set_variable (get_byte (), pop_type (long_type
));
2463 set_variable (get_byte (), pop_type (float_type
));
2466 set_variable (get_byte (), pop_type (double_type
));
2469 set_variable (get_byte (), pop_ref_or_return ());
2475 set_variable (opcode
- op_istore_0
, pop_type (int_type
));
2481 set_variable (opcode
- op_lstore_0
, pop_type (long_type
));
2487 set_variable (opcode
- op_fstore_0
, pop_type (float_type
));
2493 set_variable (opcode
- op_dstore_0
, pop_type (double_type
));
2499 set_variable (opcode
- op_astore_0
, pop_ref_or_return ());
2502 pop_type (int_type
);
2503 pop_type (int_type
);
2504 require_array_type (pop_init_ref (reference_type
), int_type
);
2507 pop_type (long_type
);
2508 pop_type (int_type
);
2509 require_array_type (pop_init_ref (reference_type
), long_type
);
2512 pop_type (float_type
);
2513 pop_type (int_type
);
2514 require_array_type (pop_init_ref (reference_type
), float_type
);
2517 pop_type (double_type
);
2518 pop_type (int_type
);
2519 require_array_type (pop_init_ref (reference_type
), double_type
);
2522 pop_type (reference_type
);
2523 pop_type (int_type
);
2524 require_array_type (pop_init_ref (reference_type
), reference_type
);
2527 pop_type (int_type
);
2528 pop_type (int_type
);
2529 require_array_type (pop_init_ref (reference_type
), byte_type
);
2532 pop_type (int_type
);
2533 pop_type (int_type
);
2534 require_array_type (pop_init_ref (reference_type
), char_type
);
2537 pop_type (int_type
);
2538 pop_type (int_type
);
2539 require_array_type (pop_init_ref (reference_type
), short_type
);
2546 type t
= pop_raw ();
2547 if (! type_iswide (&t
))
2570 type t2
= pop_raw ();
2571 if (! type_iswide (&t2
))
2585 type t
= pop_raw ();
2586 if (! type_iswide (&t
))
2600 type t1
= pop_raw ();
2602 if (! type_iswide (&t1
))
2617 type t1
= pop_raw ();
2618 if (type_iswide (&t1
))
2620 type t2
= pop_raw ();
2621 if (type_iswide (&t2
))
2638 type t3
= pop_raw ();
2639 if (type_iswide (&t3
))
2676 pop_type (int_type
);
2677 push_type_t (pop_type (int_type
));
2687 pop_type (long_type
);
2688 push_type_t (pop_type (long_type
));
2693 pop_type (int_type
);
2694 push_type_t (pop_type (long_type
));
2701 pop_type (float_type
);
2702 push_type_t (pop_type (float_type
));
2709 pop_type (double_type
);
2710 push_type_t (pop_type (double_type
));
2716 push_type_t (pop_type (int_type
));
2719 push_type_t (pop_type (long_type
));
2722 push_type_t (pop_type (float_type
));
2725 push_type_t (pop_type (double_type
));
2728 get_variable (get_byte (), int_type
);
2732 pop_type (int_type
);
2733 push_type (long_type
);
2736 pop_type (int_type
);
2737 push_type (float_type
);
2740 pop_type (int_type
);
2741 push_type (double_type
);
2744 pop_type (long_type
);
2745 push_type (int_type
);
2748 pop_type (long_type
);
2749 push_type (float_type
);
2752 pop_type (long_type
);
2753 push_type (double_type
);
2756 pop_type (float_type
);
2757 push_type (int_type
);
2760 pop_type (float_type
);
2761 push_type (long_type
);
2764 pop_type (float_type
);
2765 push_type (double_type
);
2768 pop_type (double_type
);
2769 push_type (int_type
);
2772 pop_type (double_type
);
2773 push_type (long_type
);
2776 pop_type (double_type
);
2777 push_type (float_type
);
2780 pop_type (long_type
);
2781 pop_type (long_type
);
2782 push_type (int_type
);
2786 pop_type (float_type
);
2787 pop_type (float_type
);
2788 push_type (int_type
);
2792 pop_type (double_type
);
2793 pop_type (double_type
);
2794 push_type (int_type
);
2802 pop_type (int_type
);
2803 push_jump (get_short ());
2811 pop_type (int_type
);
2812 pop_type (int_type
);
2813 push_jump (get_short ());
2817 pop_type (reference_type
);
2818 pop_type (reference_type
);
2819 push_jump (get_short ());
2822 push_jump (get_short ());
2826 handle_jsr_insn (get_short ());
2829 handle_ret_insn (get_byte ());
2831 case op_tableswitch
:
2835 pop_type (int_type
);
2837 push_jump (get_int ());
2840 /* Already checked LOW -vs- HIGH. */
2841 for (i
= low
; i
<= high
; ++i
)
2842 push_jump (get_int ());
2847 case op_lookupswitch
:
2850 jint npairs
, lastkey
;
2852 pop_type (int_type
);
2854 push_jump (get_int ());
2855 npairs
= get_int ();
2856 /* Already checked NPAIRS >= 0. */
2858 for (i
= 0; i
< npairs
; ++i
)
2860 jint key
= get_int ();
2861 if (i
> 0 && key
<= lastkey
)
2862 verify_fail_pc ("lookupswitch pairs unsorted", vfr
->start_PC
);
2864 push_jump (get_int ());
2870 check_return_type (pop_type (int_type
));
2874 check_return_type (pop_type (long_type
));
2878 check_return_type (pop_type (float_type
));
2882 check_return_type (pop_type (double_type
));
2886 check_return_type (pop_init_ref (reference_type
));
2890 /* We only need to check this when the return type is void,
2891 because all instance initializers return void. We also
2892 need to special-case Object constructors, as they can't
2893 call a superclass <init>. */
2894 if (this_is_init
&& vfr
->current_class
!= vfy_object_type ())
2895 state_check_this_initialized (vfr
->current_state
);
2896 check_return_type (make_type (void_type
));
2900 push_type_t (check_field_constant (get_ushort (), NULL
, false));
2903 pop_type_t (check_field_constant (get_ushort (), NULL
, false));
2908 type field
= check_field_constant (get_ushort (), &klass
, false);
2910 push_type_t (field
);
2916 type field
= check_field_constant (get_ushort (), &klass
, true);
2922 case op_invokevirtual
:
2923 case op_invokespecial
:
2924 case op_invokestatic
:
2925 case op_invokeinterface
:
2927 vfy_string method_name
, method_signature
;
2931 bool is_init
= false;
2934 = check_method_constant (get_ushort (),
2935 opcode
== op_invokeinterface
,
2938 /* NARGS is only used when we're processing
2939 invokeinterface. It is simplest for us to compute it
2940 here and then verify it later. */
2942 if (opcode
== op_invokeinterface
)
2944 nargs
= get_byte ();
2945 if (get_byte () != 0)
2946 verify_fail ("invokeinterface dummy byte is wrong");
2949 namec
= vfy_string_bytes (method_name
);
2951 if (vfy_strings_equal (method_name
, vfy_init_name()))
2954 if (opcode
!= op_invokespecial
)
2955 verify_fail ("can't invoke <init>");
2957 else if (namec
[0] == '<')
2958 verify_fail ("can't invoke method starting with `<'");
2960 arg_count
= vfy_count_arguments (method_signature
);
2962 /* Pop arguments and check types. */
2963 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2965 compute_argument_types (method_signature
, arg_types
);
2966 for (i
= arg_count
- 1; i
>= 0; --i
)
2968 /* This is only used for verifying the byte for
2970 nargs
-= type_depth (&arg_types
[i
]);
2971 pop_init_ref_t (arg_types
[i
]);
2974 vfy_free (arg_types
);
2977 if (opcode
== op_invokeinterface
2979 verify_fail ("wrong argument count for invokeinterface");
2981 if (opcode
!= op_invokestatic
)
2984 type t
= class_type
;
2987 /* In this case the PC doesn't matter. */
2988 type_set_uninitialized (&t
, UNINIT
);
2989 /* FIXME: check to make sure that the <init>
2990 call is to the right class.
2991 It must either be super or an exact class
2995 if (! types_compatible (&t
, &raw
))
2996 verify_fail ("incompatible type on stack");
2999 state_set_initialized (vfr
->current_state
,
3000 type_get_pc (&raw
), vfr
->current_method
->max_locals
);
3003 rt
= compute_return_type (method_signature
);
3004 if (! type_isvoid (&rt
))
3011 type t
= check_class_constant (get_ushort ());
3012 if (type_isarray (&t
) || type_isinterface (&t
)
3013 || type_isabstract (&t
))
3014 verify_fail ("type is array, interface, or abstract");
3015 type_set_uninitialized (&t
, vfr
->start_PC
);
3022 int atype
= get_byte ();
3024 /* We intentionally have chosen constants to make this
3026 if (atype
< boolean_type
|| atype
> long_type
)
3027 verify_fail_pc ("type not primitive", vfr
->start_PC
);
3028 pop_type (int_type
);
3029 init_type_from_class (&t
, construct_primitive_array_type (atype
));
3036 pop_type (int_type
);
3037 t
= check_class_constant (get_ushort ());
3038 push_type_t (type_to_array (&t
));
3041 case op_arraylength
:
3043 type t
= pop_init_ref (reference_type
);
3044 if (! type_isarray (&t
) && ! type_isnull (&t
))
3045 verify_fail ("array type expected");
3046 push_type (int_type
);
3050 pop_type_t (make_type_from_class (vfy_throwable_type ()));
3054 pop_init_ref (reference_type
);
3055 push_type_t (check_class_constant (get_ushort ()));
3058 pop_init_ref (reference_type
);
3059 check_class_constant (get_ushort ());
3060 push_type (int_type
);
3062 case op_monitorenter
:
3063 pop_init_ref (reference_type
);
3065 case op_monitorexit
:
3066 pop_init_ref (reference_type
);
3070 switch (get_byte ())
3073 push_type_t (get_variable (get_ushort (), int_type
));
3076 push_type_t (get_variable (get_ushort (), long_type
));
3079 push_type_t (get_variable (get_ushort (), float_type
));
3082 push_type_t (get_variable (get_ushort (), double_type
));
3085 push_type_t (get_variable (get_ushort (), reference_type
));
3088 set_variable (get_ushort (), pop_type (int_type
));
3091 set_variable (get_ushort (), pop_type (long_type
));
3094 set_variable (get_ushort (), pop_type (float_type
));
3097 set_variable (get_ushort (), pop_type (double_type
));
3100 set_variable (get_ushort (), pop_init_ref (reference_type
));
3103 handle_ret_insn (get_short ());
3106 get_variable (get_ushort (), int_type
);
3110 verify_fail_pc ("unrecognized wide instruction", vfr
->start_PC
);
3114 case op_multianewarray
:
3117 type atype
= check_class_constant (get_ushort ());
3118 int dim
= get_byte ();
3120 verify_fail_pc ("too few dimensions to multianewarray", vfr
->start_PC
);
3121 type_verify_dimensions (&atype
, dim
);
3122 for (i
= 0; i
< dim
; ++i
)
3123 pop_type (int_type
);
3124 push_type_t (atype
);
3129 pop_type (reference_type
);
3130 push_jump (get_short ());
3133 push_jump (get_int ());
3137 handle_jsr_insn (get_int ());
3141 /* Unrecognized opcode. */
3142 verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3148 /* This turns a `type' into something suitable for use by the type map
3149 in the other parts of the compiler. In particular, reference types
3150 are mapped to Object, primitive types are unchanged, and other
3151 types are mapped using special functions declared in verify.h. */
3153 collapse_type (type
*t
)
3166 return vfy_get_primitive_type (t
->key
);
3168 case unsuitable_type
:
3169 case continuation_type
:
3170 return vfy_unsuitable_type ();
3172 case return_address_type
:
3173 return vfy_return_address_type ();
3176 return vfy_null_type ();
3178 case reference_type
:
3179 case uninitialized_reference_type
:
3180 return vfy_object_type ();
3187 verify_instructions (void)
3192 verify_instructions_0 ();
3194 /* Now tell the rest of the compiler about the types we've found. */
3195 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3200 if ((vfr
->flags
[i
] & FLAG_INSN_SEEN
) != 0)
3201 vfy_note_instruction_seen (i
);
3203 if (! vfr
->states
[i
])
3206 curr
= vfr
->states
[i
]->val
;
3207 vfy_note_stack_depth (vfr
->current_method
, i
, curr
->stackdepth
);
3209 /* Tell the compiler about each local variable. */
3210 for (j
= 0; j
< vfr
->current_method
->max_locals
; ++j
)
3211 vfy_note_local_type (vfr
->current_method
, i
, j
,
3212 collapse_type (&curr
->locals
[j
]));
3213 /* Tell the compiler about each stack slot. */
3214 for (slot
= j
= 0; j
< curr
->stacktop
; ++j
, ++slot
)
3216 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3217 collapse_type (&curr
->stack
[j
]));
3218 if (type_iswide (&curr
->stack
[j
]))
3221 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3222 vfy_unsuitable_type ());
3225 gcc_assert (slot
== curr
->stackdepth
);
3230 make_verifier_context (vfy_method
*m
)
3232 vfr
= (verifier_context
*) vfy_alloc (sizeof (struct verifier_context
));
3234 vfr
->current_method
= m
;
3235 vfr
->bytecode
= vfy_get_bytecode (m
);
3236 vfr
->exception
= vfy_get_exceptions (m
);
3237 vfr
->current_class
= m
->defining_class
;
3241 vfr
->utf8_list
= NULL
;
3242 vfr
->isect_list
= NULL
;
3246 free_verifier_context (void)
3248 vfy_string_list
*utf8_list
;
3249 ref_intersection
*isect_list
;
3252 vfy_free (vfr
->flags
);
3254 utf8_list
= vfr
->utf8_list
;
3255 while (utf8_list
!= NULL
)
3257 vfy_string_list
*n
= utf8_list
->next
;
3258 vfy_free (utf8_list
);
3262 isect_list
= vfr
->isect_list
;
3263 while (isect_list
!= NULL
)
3265 ref_intersection
*next
= isect_list
->alloc_next
;
3266 vfy_free (isect_list
);
3270 if (vfr
->states
!= NULL
)
3273 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3275 state_list
*iter
= vfr
->states
[i
];
3276 while (iter
!= NULL
)
3278 state_list
*next
= iter
->next
;
3279 free_state (iter
->val
);
3280 vfy_free (iter
->val
);
3285 vfy_free (vfr
->states
);
3292 verify_method (vfy_method
*meth
)
3294 debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth
->name
),
3298 verify_fail ("verifier re-entered");
3300 make_verifier_context (meth
);
3301 verify_instructions ();
3302 free_verifier_context ();