1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation
3 This file is part of libgcj.
5 This software is copyrighted work licensed under the terms of the
6 Libgcj License. Please consult the file "LIBGCJ_LICENSE" for
9 /* Written by Tom Tromey <tromey@redhat.com> */
11 /* Uncomment this to enable debugging output. */
12 /* #define VERIFY_DEBUG */
18 /* Hack to work around namespace pollution from java-tree.h. */
23 #endif /* VERIFY_DEBUG */
25 /* This is used to mark states which are not scheduled for
27 #define INVALID_STATE ((state *) -1)
31 debug_print (const char *fmt
, ...)
35 vfprintf (stderr
, fmt
, ap
);
40 debug_print (const char *fmt ATTRIBUTE_UNUSED
, ...)
43 #endif /* VERIFY_DEBUG */
45 /* This started as a fairly ordinary verifier, and for the most part
46 it remains so. It works in the obvious way, by modeling the effect
47 of each opcode as it is encountered. For most opcodes, this is a
48 straightforward operation.
50 This verifier does not do type merging. It used to, but this
51 results in difficulty verifying some relatively simple code
52 involving interfaces, and it pushed some verification work into the
55 Instead of merging reference types, when we reach a point where two
56 flows of control merge, we simply keep the union of reference types
57 from each branch. Then, when we need to verify a fact about a
58 reference on the stack (e.g., that it is compatible with the
59 argument type of a method), we check to ensure that all possible
60 types satisfy the requirement.
62 Another area this verifier differs from the norm is in its handling
63 of subroutines. The JVM specification has some confusing things to
64 say about subroutines. For instance, it makes claims about not
65 allowing subroutines to merge and it rejects recursive subroutines.
66 For the most part these are red herrings; we used to try to follow
67 these things but they lead to problems. For example, the notion of
68 "being in a subroutine" is not well-defined: is an exception
69 handler in a subroutine? If you never execute the `ret' but
70 instead `goto 1' do you remain in the subroutine?
72 For clarity on what is really required for type safety, read
73 "Simple Verification Technique for Complex Java Bytecode
74 Subroutines" by Alessandro Coglio. Among other things this paper
75 shows that recursive subroutines are not harmful to type safety.
76 We implement something similar to what he proposes. Note that this
77 means that this verifier will accept code that is rejected by some
80 For those not wanting to read the paper, the basic observation is
81 that we can maintain split states in subroutines. We maintain one
82 state for each calling `jsr'. In other words, we re-verify a
83 subroutine once for each caller, using the exact types held by the
84 callers (as opposed to the old approach of merging types and
85 keeping a bitmap registering what did or did not change). This
86 approach lets us continue to verify correctly even when a
87 subroutine is exited via `goto' or `athrow' and not `ret'.
89 In some other areas the JVM specification is (mildly) incorrect,
90 so we diverge. For instance, you cannot
91 violate type safety by allocating an object with `new' and then
92 failing to initialize it, no matter how one branches or where one
93 stores the uninitialized reference. See "Improving the official
94 specification of Java bytecode verification" by Alessandro Coglio.
96 Note that there's no real point in enforcing that padding bytes or
97 the mystery byte of invokeinterface must be 0, but we do that
100 The verifier is currently neither completely lazy nor eager when it
101 comes to loading classes. It tries to represent types by name when
102 possible, and then loads them when it needs to verify a fact about
103 the type. Checking types by name is valid because we only use
104 names which come from the current class' constant pool. Since all
105 such names are looked up using the same class loader, there is no
106 danger that we might be fooled into comparing different types with
109 In the future we plan to allow for a completely lazy mode of
110 operation, where the verifier will construct a list of type
111 assertions to be checked later.
113 Some test cases for the verifier live in the "verify" module of the
114 Mauve test suite. However, some of these are presently
115 (2004-01-20) believed to be incorrect. (More precisely the notion
116 of "correct" is not well-defined, and this verifier differs from
117 others while remaining type-safe.) Some other tests live in the
120 This verifier is also written to be pluggable. This means that it
121 is intended for use in a variety of environments, not just libgcj.
122 As a result the verifier expects a number of type and method
123 declarations to be declared in "verify.h". The intent is that you
124 recompile the verifier for your particular environment. This
125 approach was chosen so that operations could be inlined in verify.h
128 See the verify.h that accompanies this copy of the verifier to see
129 what types, preprocessor defines, and functions must be declared.
130 The interface is ad hoc, but was defined so that it could be
131 implemented to connect to a pure C program.
134 #define FLAG_INSN_START 1
135 #define FLAG_BRANCH_TARGET 2
136 #define FLAG_INSN_SEEN 4
140 struct ref_intersection
;
142 typedef struct state state
;
143 typedef struct type type
;
144 typedef struct ref_intersection ref_intersection
;
146 /*typedef struct state_list state_list;*/
148 typedef struct state_list
151 struct state_list
*next
;
154 typedef struct vfy_string_list
157 struct vfy_string_list
*next
;
160 typedef struct verifier_context
162 /* The current PC. */
164 /* The PC corresponding to the start of the current instruction. */
167 /* The current state of the stack, locals, etc. */
168 state
*current_state
;
170 /* At each branch target we keep a linked list of all the states we
171 can process at that point. We'll only have multiple states at a
172 given PC if they both have different return-address types in the
173 same stack or local slot. This array is indexed by PC and holds
174 the list of all such states. */
177 /* We keep a linked list of all the states which we must reverify.
178 This is the head of the list. */
179 state
*next_verify_state
;
181 /* We keep some flags for each instruction. The values are the
182 FLAG_* constants defined above. This is an array indexed by PC. */
185 /* The bytecode itself. */
186 const unsigned char *bytecode
;
187 /* The exceptions. */
188 vfy_exception
*exception
;
190 /* Defining class. */
191 vfy_jclass current_class
;
193 vfy_method
*current_method
;
195 /* A linked list of utf8 objects we allocate. */
196 vfy_string_list
*utf8_list
;
198 /* A linked list of all ref_intersection objects we allocate. */
199 ref_intersection
*isect_list
;
202 /* The current verifier's state data. This is maintained by
203 {push/pop}_verifier_context to provide a shorthand form to access
204 the verification state. */
205 static GTY(()) verifier_context
*vfr
;
207 /* Local function declarations. */
208 bool type_initialized (type
*t
);
209 int ref_count_dimensions (ref_intersection
*ref
);
212 verify_fail_pc (const char *s
, int pc
)
214 vfy_fail (s
, pc
, vfr
->current_class
, vfr
->current_method
);
218 verify_fail (const char *s
)
220 verify_fail_pc (s
, vfr
->PC
);
223 /* This enum holds a list of tags for all the different types we
224 need to handle. Reference types are treated specially by the
226 typedef enum type_val
230 /* The values for primitive types are chosen to correspond to values
231 specified to newarray. */
241 /* Used when overwriting second word of a double or long in the
242 local variables. Also used after merging local variable states
243 to indicate an unusable value. */
246 /* This is the second word of a two-word value, i.e., a double or
250 /* Everything after `reference_type' must be a reference type. */
253 uninitialized_reference_type
256 /* This represents a merged class type. Some verifiers (including
257 earlier versions of this one) will compute the intersection of
258 two class types when merging states. However, this loses
259 critical information about interfaces implemented by the various
260 classes. So instead we keep track of all the actual classes that
262 struct ref_intersection
264 /* Whether or not this type has been resolved. */
267 /* Actual type data. */
270 /* For a resolved reference type, this is a pointer to the class. */
272 /* For other reference types, this it the name of the class. */
276 /* Link to the next reference in the intersection. */
277 ref_intersection
*ref_next
;
279 /* This is used to keep track of all the allocated
280 ref_intersection objects, so we can free them.
281 FIXME: we should allocate these in chunks. */
282 ref_intersection
*alloc_next
;
285 static ref_intersection
*
288 ref_intersection
*new_ref
=
289 (ref_intersection
*) vfy_alloc (sizeof (ref_intersection
));
291 new_ref
->alloc_next
= vfr
->isect_list
;
292 vfr
->isect_list
= new_ref
;
296 static ref_intersection
*
297 clone_ref (ref_intersection
*dup
)
299 ref_intersection
*new_ref
= make_ref ();
301 new_ref
->is_resolved
= dup
->is_resolved
;
302 new_ref
->data
= dup
->data
;
307 resolve_ref (ref_intersection
*ref
)
309 if (ref
->is_resolved
)
311 ref
->data
.klass
= vfy_find_class (vfr
->current_class
, ref
->data
.name
);
312 ref
->is_resolved
= true;
316 refs_equal (ref_intersection
*ref1
, ref_intersection
*ref2
)
318 if (! ref1
->is_resolved
&& ! ref2
->is_resolved
319 && vfy_strings_equal (ref1
->data
.name
, ref2
->data
.name
))
321 if (! ref1
->is_resolved
)
323 if (! ref2
->is_resolved
)
325 return ref1
->data
.klass
== ref2
->data
.klass
;
328 /* Merge REF1 type into REF2, returning the result. This will
329 return REF2 if all the classes in THIS already appear in
331 static ref_intersection
*
332 merge_refs (ref_intersection
*ref1
, ref_intersection
*ref2
)
334 ref_intersection
*tail
= ref2
;
335 for (; ref1
!= NULL
; ref1
= ref1
->ref_next
)
338 ref_intersection
*iter
;
339 for (iter
= ref2
; iter
!= NULL
; iter
= iter
->ref_next
)
341 if (refs_equal (ref1
, iter
))
350 ref_intersection
*new_tail
= clone_ref (ref1
);
351 new_tail
->ref_next
= tail
;
358 /* See if an object of type SOURCE can be assigned to an object of
359 type TARGET. This might resolve classes in one chain or the other. */
361 ref_compatible (ref_intersection
*target
, ref_intersection
*source
)
363 for (; target
!= NULL
; target
= target
->ref_next
)
365 ref_intersection
*source_iter
= source
;
367 for (; source_iter
!= NULL
; source_iter
= source_iter
->ref_next
)
369 /* Avoid resolving if possible. */
370 if (! target
->is_resolved
371 && ! source_iter
->is_resolved
372 && vfy_strings_equal (target
->data
.name
,
373 source_iter
->data
.name
))
376 if (! target
->is_resolved
)
377 resolve_ref (target
);
378 if (! source_iter
->is_resolved
)
379 resolve_ref (source_iter
);
381 if (! vfy_is_assignable_from (target
->data
.klass
,
382 source_iter
->data
.klass
))
391 ref_isarray (ref_intersection
*ref
)
393 /* assert (ref_next == NULL); */
394 if (ref
->is_resolved
)
395 return vfy_is_array (ref
->data
.klass
);
397 return vfy_string_bytes (ref
->data
.name
)[0] == '[';
401 ref_isinterface (ref_intersection
*ref
)
403 /* assert (ref_next == NULL); */
404 if (! ref
->is_resolved
)
406 return vfy_is_interface (ref
->data
.klass
);
410 ref_isabstract (ref_intersection
*ref
)
412 /* assert (ref_next == NULL); */
413 if (! ref
->is_resolved
)
415 return vfy_is_abstract (ref
->data
.klass
);
419 ref_getclass (ref_intersection
*ref
)
421 if (! ref
->is_resolved
)
423 return ref
->data
.klass
;
427 ref_count_dimensions (ref_intersection
*ref
)
430 if (ref
->is_resolved
)
432 vfy_jclass k
= ref
->data
.klass
;
433 while (vfy_is_array (k
))
435 k
= vfy_get_component_type (k
);
441 const char *p
= vfy_string_bytes (ref
->data
.name
);
448 /* Return the type_val corresponding to a primitive signature
449 character. For instance `I' returns `int.class'. */
451 get_type_val_for_signature (char sig
)
484 verify_fail ("invalid signature");
490 /* Return the type_val corresponding to a primitive class. */
492 get_type_val_for_primtype (vfy_jclass k
)
494 return get_type_val_for_signature (vfy_get_primitive_char (k
));
497 /* The `type' class is used to represent a single type in the verifier. */
503 /* For reference types, the representation of the type. */
504 ref_intersection
*klass
;
506 /* This is used in two situations.
508 First, when constructing a new object, it is the PC of the
509 `new' instruction which created the object. We use the special
510 value UNINIT to mean that this is uninitialized. The special
511 value SELF is used for the case where the current method is
512 itself the <init> method. the special value EITHER is used
513 when we may optionally allow either an uninitialized or
514 initialized reference to match.
516 Second, when the key is return_address_type, this holds the PC
517 of the instruction following the `jsr'. */
525 /* Make a new instance given the type tag. We assume a generic
526 `reference_type' means Object. */
528 init_type_from_tag (type
*t
, type_val k
)
531 /* For reference_type, if KLASS==NULL then that means we are
532 looking for a generic object of any kind, including an
533 uninitialized reference. */
538 /* Make a type for the given type_val tag K. */
540 make_type (type_val k
)
543 init_type_from_tag (&t
, k
);
547 /* Make a new instance given a class. */
549 init_type_from_class (type
*t
, vfy_jclass k
)
551 t
->key
= reference_type
;
552 t
->klass
= make_ref ();
553 t
->klass
->is_resolved
= true;
554 t
->klass
->data
.klass
= k
;
555 t
->klass
->ref_next
= NULL
;
560 make_type_from_class (vfy_jclass k
)
563 init_type_from_class (&t
, k
);
568 init_type_from_string (type
*t
, vfy_string n
)
570 t
->key
= reference_type
;
571 t
->klass
= make_ref ();
572 t
->klass
->is_resolved
= false;
573 t
->klass
->data
.name
= n
;
574 t
->klass
->ref_next
= NULL
;
579 make_type_from_string (vfy_string n
)
582 init_type_from_string (&t
, n
);
586 /* Promote a numeric type. */
588 vfy_promote_type (type
*t
)
590 if (t
->key
== boolean_type
|| t
->key
== char_type
591 || t
->key
== byte_type
|| t
->key
== short_type
)
594 #define promote_type vfy_promote_type
596 /* Mark this type as the uninitialized result of `new'. */
598 type_set_uninitialized (type
*t
, int npc
)
600 if (t
->key
== reference_type
)
601 t
->key
= uninitialized_reference_type
;
603 verify_fail ("internal error in type::uninitialized");
607 /* Mark this type as now initialized. */
609 type_set_initialized (type
*t
, int npc
)
611 if (npc
!= UNINIT
&& t
->pc
== npc
&& t
->key
== uninitialized_reference_type
)
613 t
->key
= reference_type
;
618 /* Mark this type as a particular return address. */
619 static void type_set_return_address (type
*t
, int npc
)
624 /* Return true if this type and type OTHER are considered
625 mergeable for the purposes of state merging. This is related
626 to subroutine handling. For this purpose two types are
627 considered unmergeable if they are both return-addresses but
628 have different PCs. */
630 type_state_mergeable_p (type
*t1
, type
*t2
)
632 return (t1
->key
!= return_address_type
633 || t2
->key
!= return_address_type
634 || t1
->pc
== t2
->pc
);
637 /* Return true if an object of type K can be assigned to a variable
638 of type T. Handle various special cases too. Might modify
639 T or K. Note however that this does not perform numeric
642 types_compatible (type
*t
, type
*k
)
644 /* Any type is compatible with the unsuitable type. */
645 if (k
->key
== unsuitable_type
)
648 if (t
->key
< reference_type
|| k
->key
< reference_type
)
649 return t
->key
== k
->key
;
651 /* The `null' type is convertible to any initialized reference
653 if (t
->key
== null_type
)
654 return k
->key
!= uninitialized_reference_type
;
655 if (k
->key
== null_type
)
656 return t
->key
!= uninitialized_reference_type
;
658 /* A special case for a generic reference. */
659 if (t
->klass
== NULL
)
661 if (k
->klass
== NULL
)
662 verify_fail ("programmer error in type::compatible");
664 /* Handle the special 'EITHER' case, which is only used in a
665 special case of 'putfield'. Note that we only need to handle
666 this on the LHS of a check. */
667 if (! type_initialized (t
) && t
->pc
== EITHER
)
669 /* If the RHS is uninitialized, it must be an uninitialized
671 if (! type_initialized (k
) && k
->pc
!= SELF
)
674 else if (type_initialized (t
) != type_initialized (k
))
676 /* An initialized type and an uninitialized type are not
677 otherwise compatible. */
682 /* Two uninitialized objects are compatible if either:
683 * The PCs are identical, or
684 * One PC is UNINIT. */
685 if (type_initialized (t
))
687 if (t
->pc
!= k
->pc
&& t
->pc
!= UNINIT
&& k
->pc
!= UNINIT
)
692 return ref_compatible (t
->klass
, k
->klass
);
695 /* Return true if two types are equal. Only valid for reference
698 types_equal (type
*t1
, type
*t2
)
700 if ((t1
->key
!= reference_type
&& t1
->key
!= uninitialized_reference_type
)
701 || (t2
->key
!= reference_type
702 && t2
->key
!= uninitialized_reference_type
))
704 /* Only single-ref types are allowed. */
705 if (t1
->klass
->ref_next
|| t2
->klass
->ref_next
)
707 return refs_equal (t1
->klass
, t2
->klass
);
711 type_isvoid (type
*t
)
713 return t
->key
== void_type
;
717 type_iswide (type
*t
)
719 return t
->key
== long_type
|| t
->key
== double_type
;
722 /* Return number of stack or local variable slots taken by this type. */
726 return type_iswide (t
) ? 2 : 1;
730 type_isarray (type
*t
)
732 /* We treat null_type as not an array. This is ok based on the
733 current uses of this method. */
734 if (t
->key
== reference_type
)
735 return ref_isarray (t
->klass
);
740 type_isnull (type
*t
)
742 return t
->key
== null_type
;
746 type_isinterface (type
*t
)
748 if (t
->key
!= reference_type
)
750 return ref_isinterface (t
->klass
);
754 type_isabstract (type
*t
)
756 if (t
->key
!= reference_type
)
758 return ref_isabstract (t
->klass
);
761 /* Return the element type of an array. */
763 type_array_element (type
*t
)
768 if (t
->key
!= reference_type
)
769 verify_fail ("programmer error in type::element_type()");
771 k
= vfy_get_component_type (ref_getclass (t
->klass
));
772 if (vfy_is_primitive (k
))
773 init_type_from_tag (&et
, get_type_val_for_primtype (k
));
775 init_type_from_class (&et
, k
);
779 /* Return the array type corresponding to an initialized
780 reference. We could expand this to work for other kinds of
781 types, but currently we don't need to. */
783 type_to_array (type
*t
)
788 if (t
->key
!= reference_type
)
789 verify_fail ("internal error in type::to_array()");
791 k
= ref_getclass (t
->klass
);
792 init_type_from_class (&at
, vfy_get_array_class (k
));
797 type_isreference (type
*t
)
799 return t
->key
>= reference_type
;
803 type_get_pc (type
*t
)
809 type_initialized (type
*t
)
811 return t
->key
== reference_type
|| t
->key
== null_type
;
815 type_verify_dimensions (type
*t
, int ndims
)
817 /* The way this is written, we don't need to check isarray(). */
818 if (t
->key
!= reference_type
)
819 verify_fail ("internal error in verify_dimensions:"
820 " not a reference type");
822 if (ref_count_dimensions (t
->klass
) < ndims
)
823 verify_fail ("array type has fewer dimensions"
827 /* Merge OLD_TYPE into this. On error throw exception. Return
828 true if the merge caused a type change. */
830 merge_types (type
*t
, type
*old_type
, bool local_semantics
)
832 bool changed
= false;
833 bool refo
= type_isreference (old_type
);
834 bool refn
= type_isreference (t
);
837 if (old_type
->key
== null_type
)
839 else if (t
->key
== null_type
)
844 else if (type_initialized (t
) != type_initialized (old_type
))
845 verify_fail ("merging initialized and uninitialized types");
848 ref_intersection
*merged
;
849 if (! type_initialized (t
))
852 t
->pc
= old_type
->pc
;
853 else if (old_type
->pc
== UNINIT
)
855 else if (t
->pc
!= old_type
->pc
)
856 verify_fail ("merging different uninitialized types");
859 merged
= merge_refs (old_type
->klass
, t
->klass
);
860 if (merged
!= t
->klass
)
867 else if (refo
|| refn
|| t
->key
!= old_type
->key
)
871 /* If we already have an `unsuitable' type, then we
872 don't need to change again. */
873 if (t
->key
!= unsuitable_type
)
875 t
->key
= unsuitable_type
;
880 verify_fail ("unmergeable type");
892 case boolean_type
: c
= 'Z'; break;
893 case byte_type
: c
= 'B'; break;
894 case char_type
: c
= 'C'; break;
895 case short_type
: c
= 'S'; break;
896 case int_type
: c
= 'I'; break;
897 case long_type
: c
= 'J'; break;
898 case float_type
: c
= 'F'; break;
899 case double_type
: c
= 'D'; break;
900 case void_type
: c
= 'V'; break;
901 case unsuitable_type
: c
= '-'; break;
902 case return_address_type
: c
= 'r'; break;
903 case continuation_type
: c
= '+'; break;
904 case reference_type
: c
= 'L'; break;
905 case null_type
: c
= '@'; break;
906 case uninitialized_reference_type
: c
= 'U'; break;
908 debug_print ("%c", c
);
910 #endif /* VERIFY_DEBUG */
912 /* This class holds all the state information we need for a given
916 /* The current top of the stack, in terms of slots. */
918 /* The current depth of the stack. This will be larger than
919 STACKTOP when wide types are on the stack. */
923 /* The local variables. */
925 /* We keep track of the type of `this' specially. This is used to
926 ensure that an instance initializer invokes another initializer
927 on `this' before returning. We must keep track of this
928 specially because otherwise we might be confused by code which
929 assigns to locals[0] (overwriting `this') and then returns
930 without really initializing. */
933 /* The PC for this state. This is only valid on states which are
934 permanently attached to a given PC. For an object like
935 `current_state', which is used transiently, this has no
938 /* We keep a linked list of all states requiring reverification.
939 If this is the special value INVALID_STATE then this state is
940 not on the list. NULL marks the end of the linked list. */
944 /* NO_NEXT is the PC value meaning that a new state must be
945 acquired from the verification list. */
949 init_state_with_stack (state
*s
, int max_stack
, int max_locals
)
954 s
->stack
= (type
*) vfy_alloc (max_stack
* sizeof (type
));
955 for (i
= 0; i
< max_stack
; ++i
)
956 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
957 s
->locals
= (type
*) vfy_alloc (max_locals
* sizeof (type
));
958 for (i
= 0; i
< max_locals
; ++i
)
959 init_type_from_tag (&s
->locals
[i
], unsuitable_type
);
960 init_type_from_tag (&s
->this_type
, unsuitable_type
);
962 s
->next
= INVALID_STATE
;
966 copy_state (state
*s
, state
*copy
, int max_stack
, int max_locals
)
969 s
->stacktop
= copy
->stacktop
;
970 s
->stackdepth
= copy
->stackdepth
;
971 for (i
= 0; i
< max_stack
; ++i
)
972 s
->stack
[i
] = copy
->stack
[i
];
973 for (i
= 0; i
< max_locals
; ++i
)
974 s
->locals
[i
] = copy
->locals
[i
];
976 s
->this_type
= copy
->this_type
;
977 /* Don't modify `next' or `pc'. */
981 copy_state_with_stack (state
*s
, state
*orig
, int max_stack
, int max_locals
)
983 init_state_with_stack (s
, max_stack
, max_locals
);
984 copy_state (s
, orig
, max_stack
, max_locals
);
987 /* Allocate a new state, copying ORIG. */
989 make_state_copy (state
*orig
, int max_stack
, int max_locals
)
991 state
*s
= vfy_alloc (sizeof (state
));
992 copy_state_with_stack (s
, orig
, max_stack
, max_locals
);
997 make_state (int max_stack
, int max_locals
)
999 state
*s
= vfy_alloc (sizeof (state
));
1000 init_state_with_stack (s
, max_stack
, max_locals
);
1005 free_state (state
*s
)
1007 if (s
->stack
!= NULL
)
1008 vfy_free (s
->stack
);
1009 if (s
->locals
!= NULL
)
1010 vfy_free (s
->locals
);
1013 /* Modify this state to reflect entry to an exception handler. */
1015 state_set_exception (state
*s
, type
*t
, int max_stack
)
1021 for (i
= s
->stacktop
; i
< max_stack
; ++i
)
1022 init_type_from_tag (&s
->stack
[i
], unsuitable_type
);
1025 /* Merge STATE_OLD into this state. Destructively modifies this
1026 state. Returns true if the new state was in fact changed.
1027 Will throw an exception if the states are not mergeable. */
1029 merge_states (state
*s
, state
*state_old
, int max_locals
)
1032 bool changed
= false;
1034 /* Special handling for `this'. If one or the other is
1035 uninitialized, then the merge is uninitialized. */
1036 if (type_initialized (&s
->this_type
))
1037 s
->this_type
= state_old
->this_type
;
1040 if (state_old
->stacktop
!= s
->stacktop
) /* FIXME stackdepth instead? */
1041 verify_fail ("stack sizes differ");
1042 for (i
= 0; i
< state_old
->stacktop
; ++i
)
1044 if (merge_types (&s
->stack
[i
], &state_old
->stack
[i
], false))
1048 /* Merge local variables. */
1049 for (i
= 0; i
< max_locals
; ++i
)
1051 if (merge_types (&s
->locals
[i
], &state_old
->locals
[i
], true))
1058 /* Ensure that `this' has been initialized. */
1060 state_check_this_initialized (state
*s
)
1062 if (type_isreference (&s
->this_type
) && ! type_initialized (&s
->this_type
))
1063 verify_fail ("`this' is uninitialized");
1066 /* Set type of `this'. */
1068 state_set_this_type (state
*s
, type
*k
)
1073 /* Mark each `new'd object we know of that was allocated at PC as
1076 state_set_initialized (state
*s
, int pc
, int max_locals
)
1079 for (i
= 0; i
< s
->stacktop
; ++i
)
1080 type_set_initialized (&s
->stack
[i
], pc
);
1081 for (i
= 0; i
< max_locals
; ++i
)
1082 type_set_initialized (&s
->locals
[i
], pc
);
1083 type_set_initialized (&s
->this_type
, pc
);
1086 /* This tests to see whether two states can be considered "merge
1087 compatible". If both states have a return-address in the same
1088 slot, and the return addresses are different, then they are not
1089 compatible and we must not try to merge them. */
1091 state_mergeable_p (state
*s
, state
*other
, int max_locals
)
1096 /* This is tricky: if the stack sizes differ, then not only are
1097 these not mergeable, but in fact we should give an error, as
1098 we've found two execution paths that reach a branch target
1099 with different stack depths. FIXME stackdepth instead? */
1100 if (s
->stacktop
!= other
->stacktop
)
1101 verify_fail ("stack sizes differ");
1103 for (i
= 0; i
< s
->stacktop
; ++i
)
1104 if (! type_state_mergeable_p (&s
->stack
[i
], &other
->stack
[i
]))
1106 for (i
= 0; i
< max_locals
; ++i
)
1107 if (! type_state_mergeable_p (&s
->locals
[i
], &other
->locals
[i
]))
1113 state_reverify (state
*s
)
1115 if (s
->next
== INVALID_STATE
)
1117 s
->next
= vfr
->next_verify_state
;
1118 vfr
->next_verify_state
= s
;
1124 debug_print_state (state
*s
, const char *leader
, int pc
, int max_stack
,
1128 debug_print ("%s [%4d]: [stack] ", leader
, pc
);
1129 for (i
= 0; i
< s
->stacktop
; ++i
)
1130 type_print (&s
->stack
[i
]);
1131 for (; i
< max_stack
; ++i
)
1133 debug_print (" [local] ");
1134 for (i
= 0; i
< max_locals
; ++i
)
1135 type_print (&s
->locals
[i
]);
1136 debug_print (" | %p\n", s
);
1140 debug_print_state (state
*s ATTRIBUTE_UNUSED
,
1141 const char *leader ATTRIBUTE_UNUSED
,
1142 int pc ATTRIBUTE_UNUSED
, int max_stack ATTRIBUTE_UNUSED
,
1143 int max_locals ATTRIBUTE_UNUSED
)
1146 #endif /* VERIFY_DEBUG */
1152 state
*s
= vfr
->current_state
;
1153 if (s
->stacktop
<= 0)
1154 verify_fail ("stack empty");
1155 r
= s
->stack
[--s
->stacktop
];
1156 s
->stackdepth
-= type_depth (&r
);
1157 if (s
->stackdepth
< 0)
1158 verify_fail_pc ("stack empty", vfr
->start_PC
);
1165 type r
= pop_raw ();
1166 if (type_iswide (&r
))
1167 verify_fail ("narrow pop of wide type");
1172 vfy_pop_type_t (type match
)
1175 vfy_promote_type (&match
);
1177 if (! types_compatible (&match
, &t
))
1178 verify_fail ("incompatible type on stack");
1183 vfy_pop_type (type_val match
)
1185 type t
= make_type (match
);
1186 return vfy_pop_type_t (t
);
1189 #define pop_type vfy_pop_type
1190 #define pop_type_t vfy_pop_type_t
1192 /* Pop a reference which is guaranteed to be initialized. MATCH
1193 doesn't have to be a reference type; in this case this acts like
1196 pop_init_ref_t (type match
)
1198 type t
= pop_raw ();
1199 if (type_isreference (&t
) && ! type_initialized (&t
))
1200 verify_fail ("initialized reference required");
1201 else if (! types_compatible (&match
, &t
))
1202 verify_fail ("incompatible type on stack");
1207 pop_init_ref (type_val match
)
1209 type t
= make_type (match
);
1210 return pop_init_ref_t (t
);
1213 /* Pop a reference type or a return address. */
1215 pop_ref_or_return (void)
1217 type t
= pop_raw ();
1218 if (! type_isreference (&t
) && t
.key
!= return_address_type
)
1219 verify_fail ("expected reference or return address on stack");
1224 vfy_push_type_t (type t
)
1227 state
*s
= vfr
->current_state
;
1228 /* If T is a numeric type like short, promote it to int. */
1231 depth
= type_depth (&t
);
1233 if (s
->stackdepth
+ depth
> vfr
->current_method
->max_stack
)
1234 verify_fail ("stack overflow");
1235 s
->stack
[s
->stacktop
++] = t
;
1236 s
->stackdepth
+= depth
;
1240 vfy_push_type (type_val tval
)
1242 type t
= make_type (tval
);
1243 vfy_push_type_t (t
);
1246 #define push_type vfy_push_type
1247 #define push_type_t vfy_push_type_t
1250 set_variable (int index
, type t
)
1253 state
*s
= vfr
->current_state
;
1254 /* If T is a numeric type like short, promote it to int. */
1257 depth
= type_depth (&t
);
1258 if (index
> vfr
->current_method
->max_locals
- depth
)
1259 verify_fail ("invalid local variable");
1260 s
->locals
[index
] = t
;
1263 init_type_from_tag (&s
->locals
[index
+ 1], continuation_type
);
1264 if (index
> 0 && type_iswide (&s
->locals
[index
- 1]))
1265 init_type_from_tag (&s
->locals
[index
- 1], unsuitable_type
);
1269 get_variable_t (int index
, type
*t
)
1271 state
*s
= vfr
->current_state
;
1272 int depth
= type_depth (t
);
1273 if (index
> vfr
->current_method
->max_locals
- depth
)
1274 verify_fail ("invalid local variable");
1275 if (! types_compatible (t
, &s
->locals
[index
]))
1276 verify_fail ("incompatible type in local variable");
1279 type cont
= make_type (continuation_type
);
1280 if (! types_compatible (&s
->locals
[index
+ 1], &cont
))
1281 verify_fail ("invalid local variable");
1283 return s
->locals
[index
];
1287 get_variable (int index
, type_val v
)
1289 type t
= make_type (v
);
1290 return get_variable_t (index
, &t
);
1293 /* Make sure ARRAY is an array type and that its elements are
1294 compatible with type ELEMENT. Returns the actual element type. */
1296 require_array_type_t (type array
, type element
)
1299 /* An odd case. Here we just pretend that everything went ok. If
1300 the requested element type is some kind of reference, return
1301 the null type instead. */
1302 if (type_isnull (&array
))
1303 return type_isreference (&element
) ? make_type (null_type
) : element
;
1305 if (! type_isarray (&array
))
1306 verify_fail ("array required");
1308 t
= type_array_element (&array
);
1309 if (! types_compatible (&element
, &t
))
1311 /* Special case for byte arrays, which must also be boolean
1314 if (element
.key
== byte_type
)
1316 type e2
= make_type (boolean_type
);
1317 ok
= types_compatible (&e2
, &t
);
1320 verify_fail ("incompatible array element type");
1323 /* Return T and not ELEMENT, because T might be specialized. */
1328 require_array_type (type array
, type_val element
)
1330 type t
= make_type (element
);
1331 return require_array_type_t (array
, t
);
1337 if (vfr
->PC
>= vfr
->current_method
->code_length
)
1338 verify_fail ("premature end of bytecode");
1339 return (jint
) vfr
->bytecode
[vfr
->PC
++] & 0xff;
1345 jint b1
= get_byte ();
1346 jint b2
= get_byte ();
1347 return (jint
) ((b1
<< 8) | b2
) & 0xffff;
1353 signed char b1
= (signed char) get_byte ();
1354 jint b2
= get_byte ();
1355 jshort s
= (b1
<< 8) | b2
;
1362 jint b1
= get_byte ();
1363 jint b2
= get_byte ();
1364 jint b3
= get_byte ();
1365 jint b4
= get_byte ();
1366 jword result
= (b1
<< 24) | (b2
<< 16) | (b3
<< 8) | b4
;
1367 /* In the compiler, 'jint' might have more than 32 bits, so we must
1369 return WORD_TO_INT (result
);
1373 compute_jump (int offset
)
1375 int npc
= vfr
->start_PC
+ offset
;
1376 if (npc
< 0 || npc
>= vfr
->current_method
->code_length
)
1377 verify_fail_pc ("branch out of range", vfr
->start_PC
);
1381 /* Add a new state to the state list at NPC. */
1383 add_new_state (int npc
, state
*old_state
)
1386 vfy_method
*current_method
= vfr
->current_method
;
1387 state
*new_state
= make_state_copy (old_state
, current_method
->max_stack
,
1388 current_method
->max_locals
);
1389 debug_print ("== New state in add_new_state\n");
1390 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1391 current_method
->max_locals
);
1393 nlink
= vfy_alloc (sizeof (state_list
));
1394 nlink
->val
= new_state
;
1395 nlink
->next
= vfr
->states
[npc
];
1396 vfr
->states
[npc
] = nlink
;
1397 new_state
->pc
= npc
;
1401 /* Merge the indicated state into the state at the branch target and
1402 schedule a new PC if there is a change. NPC is the PC of the
1403 branch target, and FROM_STATE is the state at the source of the
1404 branch. This method returns true if the destination state
1405 changed and requires reverification, false otherwise. */
1407 merge_into (int npc
, state
*from_state
)
1409 /* Iterate over all target states and merge our state into each,
1410 if applicable. FIXME one improvement we could make here is
1411 "state destruction". Merging a new state into an existing one
1412 might cause a return_address_type to be merged to
1413 unsuitable_type. In this case the resulting state may now be
1414 mergeable with other states currently held in parallel at this
1415 location. So in this situation we could pairwise compare and
1416 reduce the number of parallel states. */
1418 bool applicable
= false;
1419 for (iter
= vfr
->states
[npc
]; iter
!= NULL
; iter
= iter
->next
)
1421 state
*new_state
= iter
->val
;
1422 vfy_method
*current_method
= vfr
->current_method
;
1424 if (state_mergeable_p (new_state
, from_state
,
1425 current_method
->max_locals
))
1430 debug_print ("== Merge states in merge_into\n");
1431 debug_print_state (from_state
, "Frm", vfr
->start_PC
, current_method
->max_stack
,
1432 current_method
->max_locals
);
1433 debug_print_state (new_state
, " To", npc
, current_method
->max_stack
,
1434 current_method
->max_locals
);
1435 changed
= merge_states (new_state
, from_state
,
1436 current_method
->max_locals
);
1437 debug_print_state (new_state
, "New", npc
, current_method
->max_stack
,
1438 current_method
->max_locals
);
1441 state_reverify (new_state
);
1447 /* Either we don't yet have a state at NPC, or we have a
1448 return-address type that is in conflict with all existing
1449 state. So, we need to create a new entry. */
1450 state
*new_state
= add_new_state (npc
, from_state
);
1451 /* A new state added in this way must always be reverified. */
1452 state_reverify (new_state
);
1457 push_jump (int offset
)
1459 int npc
= compute_jump (offset
);
1460 /* According to the JVM Spec, we need to check for uninitialized
1461 objects here. However, this does not actually affect type
1462 safety, and the Eclipse java compiler generates code that
1463 violates this constraint. */
1464 merge_into (npc
, vfr
->current_state
);
1468 push_exception_jump (type t
, int pc
)
1471 /* According to the JVM Spec, we need to check for uninitialized
1472 objects here. However, this does not actually affect type
1473 safety, and the Eclipse java compiler generates code that
1474 violates this constraint. */
1475 copy_state_with_stack (&s
, vfr
->current_state
,
1476 vfr
->current_method
->max_stack
,
1477 vfr
->current_method
->max_locals
);
1478 if (vfr
->current_method
->max_stack
< 1)
1479 verify_fail ("stack overflow at exception handler");
1480 state_set_exception (&s
, &t
, vfr
->current_method
->max_stack
);
1481 merge_into (pc
, &s
);
1482 /* FIXME: leak.. need free_state or GC */
1488 state
*new_state
= vfr
->next_verify_state
;
1489 if (new_state
== INVALID_STATE
)
1490 verify_fail ("programmer error in pop_jump");
1491 if (new_state
!= NULL
)
1493 vfr
->next_verify_state
= new_state
->next
;
1494 new_state
->next
= INVALID_STATE
;
1500 invalidate_pc (void)
1506 note_branch_target (int pc
)
1508 /* Don't check `pc <= PC', because we've advanced PC after
1509 fetching the target and we haven't yet checked the next
1511 if (pc
< vfr
->PC
&& ! (vfr
->flags
[pc
] & FLAG_INSN_START
))
1512 verify_fail_pc ("branch not to instruction start", vfr
->start_PC
);
1513 vfr
->flags
[pc
] |= FLAG_BRANCH_TARGET
;
1519 while ((vfr
->PC
% 4) > 0)
1520 if (get_byte () != 0)
1521 verify_fail ("found nonzero padding byte");
1524 /* Do the work for a `ret' instruction. INDEX is the index into the
1527 handle_ret_insn (int index
)
1529 type ret
= make_type (return_address_type
);
1530 type ret_addr
= get_variable_t (index
, &ret
);
1531 /* It would be nice if we could do this. However, the JVM Spec
1532 doesn't say that this is what happens. It is implied that
1533 reusing a return address is invalid, but there's no actual
1534 prohibition against it. */
1535 /* set_variable (index, unsuitable_type); */
1537 int npc
= type_get_pc (&ret_addr
);
1538 /* We might be returning to a `jsr' that is at the end of the
1539 bytecode. This is ok if we never return from the called
1540 subroutine, but if we see this here it is an error. */
1541 if (npc
>= vfr
->current_method
->code_length
)
1542 verify_fail ("fell off end");
1544 /* According to the JVM Spec, we need to check for uninitialized
1545 objects here. However, this does not actually affect type
1546 safety, and the Eclipse java compiler generates code that
1547 violates this constraint. */
1548 merge_into (npc
, vfr
->current_state
);
1552 static void handle_jsr_insn (int offset
)
1555 int npc
= compute_jump (offset
);
1557 /* According to the JVM Spec, we need to check for uninitialized
1558 objects here. However, this does not actually affect type
1559 safety, and the Eclipse java compiler generates code that
1560 violates this constraint. */
1562 /* Modify our state as appropriate for entry into a subroutine. */
1563 ret_addr
= make_type (return_address_type
);
1564 type_set_return_address (&ret_addr
, vfr
->PC
);
1565 vfy_push_type_t (ret_addr
);
1566 merge_into (npc
, vfr
->current_state
);
1571 construct_primitive_array_type (type_val prim
)
1573 vfy_jclass k
= NULL
;
1584 k
= vfy_get_primitive_type ((int) prim
);
1587 /* These aren't used here but we call them out to avoid
1590 case unsuitable_type
:
1591 case return_address_type
:
1592 case continuation_type
:
1593 case reference_type
:
1595 case uninitialized_reference_type
:
1597 verify_fail ("unknown type in construct_primitive_array_type");
1599 k
= vfy_get_array_class (k
);
1603 /* This pass computes the location of branch targets and also
1604 instruction starts. */
1606 branch_prepass (void)
1609 vfr
->flags
= (char *) vfy_alloc (vfr
->current_method
->code_length
);
1611 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
1615 while (vfr
->PC
< vfr
->current_method
->code_length
)
1618 /* Set `start_PC' early so that error checking can have the
1620 vfr
->start_PC
= vfr
->PC
;
1621 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_START
;
1623 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
1627 case op_aconst_null
:
1763 case op_monitorenter
:
1764 case op_monitorexit
:
1772 case op_arraylength
:
1804 case op_invokespecial
:
1805 case op_invokestatic
:
1806 case op_invokevirtual
:
1810 case op_multianewarray
:
1833 note_branch_target (compute_jump (get_short ()));
1836 case op_tableswitch
:
1840 note_branch_target (compute_jump (get_int ()));
1844 verify_fail_pc ("invalid tableswitch", vfr
->start_PC
);
1845 for (i
= low
; i
<= hi
; ++i
)
1846 note_branch_target (compute_jump (get_int ()));
1850 case op_lookupswitch
:
1854 note_branch_target (compute_jump (get_int ()));
1855 npairs
= get_int ();
1857 verify_fail_pc ("too few pairs in lookupswitch", vfr
->start_PC
);
1858 while (npairs
-- > 0)
1861 note_branch_target (compute_jump (get_int ()));
1866 case op_invokeinterface
:
1874 opcode
= (java_opcode
) get_byte ();
1876 if (opcode
== op_iinc
)
1883 note_branch_target (compute_jump (get_int ()));
1887 /* These are unused here, but we call them out explicitly
1888 so that -Wswitch-enum doesn't complain. */
1894 case op_putstatic_1
:
1895 case op_putstatic_2
:
1896 case op_putstatic_4
:
1897 case op_putstatic_8
:
1898 case op_putstatic_a
:
1900 case op_getfield_2s
:
1901 case op_getfield_2u
:
1905 case op_getstatic_1
:
1906 case op_getstatic_2s
:
1907 case op_getstatic_2u
:
1908 case op_getstatic_4
:
1909 case op_getstatic_8
:
1910 case op_getstatic_a
:
1911 #endif /* VFY_FAST_OPCODES */
1913 verify_fail_pc ("unrecognized instruction in branch_prepass",
1917 /* See if any previous branch tried to branch to the middle of
1918 this instruction. */
1919 for (pc
= vfr
->start_PC
+ 1; pc
< vfr
->PC
; ++pc
)
1921 if ((vfr
->flags
[pc
] & FLAG_BRANCH_TARGET
))
1922 verify_fail_pc ("branch to middle of instruction", pc
);
1926 /* Verify exception handlers. */
1927 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
1929 int handler
, start
, end
, htype
;
1930 vfy_get_exception (vfr
->exception
, i
, &handler
, &start
, &end
, &htype
);
1931 if (! (vfr
->flags
[handler
] & FLAG_INSN_START
))
1932 verify_fail_pc ("exception handler not at instruction start",
1934 if (! (vfr
->flags
[start
] & FLAG_INSN_START
))
1935 verify_fail_pc ("exception start not at instruction start", start
);
1936 if (end
!= vfr
->current_method
->code_length
1937 && ! (vfr
->flags
[end
] & FLAG_INSN_START
))
1938 verify_fail_pc ("exception end not at instruction start", end
);
1940 vfr
->flags
[handler
] |= FLAG_BRANCH_TARGET
;
1945 check_pool_index (int index
)
1947 if (index
< 0 || index
>= vfy_get_constants_size (vfr
->current_class
))
1948 verify_fail_pc ("constant pool index out of range", vfr
->start_PC
);
1952 check_class_constant (int index
)
1955 vfy_constants
*pool
;
1957 check_pool_index (index
);
1958 pool
= vfy_get_constants (vfr
->current_class
);
1959 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedClass
)
1960 init_type_from_class (&t
, vfy_get_pool_class (pool
, index
));
1961 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Class
)
1962 init_type_from_string (&t
, vfy_get_pool_string (pool
, index
));
1964 verify_fail_pc ("expected class constant", vfr
->start_PC
);
1969 check_constant (int index
)
1972 vfy_constants
*pool
;
1974 check_pool_index (index
);
1975 pool
= vfy_get_constants (vfr
->current_class
);
1976 if (vfy_tag (pool
, index
) == JV_CONSTANT_ResolvedString
1977 || vfy_tag (pool
, index
) == JV_CONSTANT_String
)
1978 init_type_from_class (&t
, vfy_string_type ());
1979 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Integer
)
1980 init_type_from_tag (&t
, int_type
);
1981 else if (vfy_tag (pool
, index
) == JV_CONSTANT_Float
)
1982 init_type_from_tag (&t
, float_type
);
1984 verify_fail_pc ("String, int, or float constant expected", vfr
->start_PC
);
1989 check_wide_constant (int index
)
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 (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 char *p
= (char *) vfy_string_bytes (signature
);
2142 p
= get_one_type (p
, &types
[i
++]);
2146 compute_return_type (vfy_string signature
)
2148 char *p
= (char *) 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
2260 instruction. Otherwise merging is done at the time we
2262 if (vfr
->states
[vfr
->PC
] != NULL
)
2264 /* We've already visited this instruction. So merge
2265 the states together. It is simplest, but not most
2266 efficient, to just always invalidate the PC here. */
2267 merge_into (vfr
->PC
, vfr
->current_state
);
2273 /* Control can't fall off the end of the bytecode. We need to
2274 check this in both cases, not just the fall-through case,
2275 because we don't check to see whether a `jsr' appears at
2276 the end of the bytecode until we process a `ret'. */
2277 if (vfr
->PC
>= vfr
->current_method
->code_length
)
2278 verify_fail ("fell off end");
2279 vfr
->flags
[vfr
->PC
] |= FLAG_INSN_SEEN
;
2281 /* We only have to keep saved state at branch targets. If
2282 we're at a branch target and the state here hasn't been set
2283 yet, we set it now. You might notice that `ret' targets
2284 won't necessarily have FLAG_BRANCH_TARGET set. This
2285 doesn't matter, since those states will be filled in by
2287 /* Note that other parts of the compiler assume that there is a
2288 label with a type map at PC=0. */
2289 if (vfr
->states
[vfr
->PC
] == NULL
2290 && (vfr
->PC
== 0 || (vfr
->flags
[vfr
->PC
] & FLAG_BRANCH_TARGET
) != 0))
2291 add_new_state (vfr
->PC
, vfr
->current_state
);
2293 /* Set this before handling exceptions so that debug output is
2295 vfr
->start_PC
= vfr
->PC
;
2297 /* Update states for all active exception handlers. Ordinarily
2298 there are not many exception handlers. So we simply run
2299 through them all. */
2300 for (i
= 0; i
< vfr
->current_method
->exc_count
; ++i
)
2302 int hpc
, start
, end
, htype
;
2303 vfy_get_exception (vfr
->exception
, i
, &hpc
, &start
, &end
, &htype
);
2304 if (vfr
->PC
>= start
&& vfr
->PC
< end
)
2306 type handler
= make_type_from_class (vfy_throwable_type ());
2308 handler
= check_class_constant (htype
);
2309 push_exception_jump (handler
, hpc
);
2314 debug_print_state (vfr
->current_state
, " ", vfr
->PC
,
2315 vfr
->current_method
->max_stack
,
2316 vfr
->current_method
->max_locals
);
2317 opcode
= (java_opcode
) vfr
->bytecode
[vfr
->PC
++];
2323 case op_aconst_null
:
2324 push_type (null_type
);
2334 push_type (int_type
);
2339 push_type (long_type
);
2345 push_type (float_type
);
2350 push_type (double_type
);
2355 push_type (int_type
);
2360 push_type (int_type
);
2364 push_type_t (check_constant (get_byte ()));
2367 push_type_t (check_constant (get_ushort ()));
2370 push_type_t (check_wide_constant (get_ushort ()));
2374 push_type_t (get_variable (get_byte (), int_type
));
2377 push_type_t (get_variable (get_byte (), long_type
));
2380 push_type_t (get_variable (get_byte (), float_type
));
2383 push_type_t (get_variable (get_byte (), double_type
));
2386 push_type_t (get_variable (get_byte (), reference_type
));
2393 push_type_t (get_variable (opcode
- op_iload_0
, int_type
));
2399 push_type_t (get_variable (opcode
- op_lload_0
, long_type
));
2405 push_type_t (get_variable (opcode
- op_fload_0
, float_type
));
2411 push_type_t (get_variable (opcode
- op_dload_0
, double_type
));
2417 push_type_t (get_variable (opcode
- op_aload_0
, reference_type
));
2420 pop_type (int_type
);
2421 push_type_t (require_array_type (pop_init_ref (reference_type
),
2425 pop_type (int_type
);
2426 push_type_t (require_array_type (pop_init_ref (reference_type
),
2430 pop_type (int_type
);
2431 push_type_t (require_array_type (pop_init_ref (reference_type
),
2435 pop_type (int_type
);
2436 push_type_t (require_array_type (pop_init_ref (reference_type
),
2440 pop_type (int_type
);
2441 push_type_t (require_array_type (pop_init_ref (reference_type
),
2445 pop_type (int_type
);
2446 require_array_type (pop_init_ref (reference_type
), byte_type
);
2447 push_type (int_type
);
2450 pop_type (int_type
);
2451 require_array_type (pop_init_ref (reference_type
), char_type
);
2452 push_type (int_type
);
2455 pop_type (int_type
);
2456 require_array_type (pop_init_ref (reference_type
), short_type
);
2457 push_type (int_type
);
2460 set_variable (get_byte (), pop_type (int_type
));
2463 set_variable (get_byte (), pop_type (long_type
));
2466 set_variable (get_byte (), pop_type (float_type
));
2469 set_variable (get_byte (), pop_type (double_type
));
2472 set_variable (get_byte (), pop_ref_or_return ());
2478 set_variable (opcode
- op_istore_0
, pop_type (int_type
));
2484 set_variable (opcode
- op_lstore_0
, pop_type (long_type
));
2490 set_variable (opcode
- op_fstore_0
, pop_type (float_type
));
2496 set_variable (opcode
- op_dstore_0
, pop_type (double_type
));
2502 set_variable (opcode
- op_astore_0
, pop_ref_or_return ());
2505 pop_type (int_type
);
2506 pop_type (int_type
);
2507 require_array_type (pop_init_ref (reference_type
), int_type
);
2510 pop_type (long_type
);
2511 pop_type (int_type
);
2512 require_array_type (pop_init_ref (reference_type
), long_type
);
2515 pop_type (float_type
);
2516 pop_type (int_type
);
2517 require_array_type (pop_init_ref (reference_type
), float_type
);
2520 pop_type (double_type
);
2521 pop_type (int_type
);
2522 require_array_type (pop_init_ref (reference_type
), double_type
);
2525 pop_type (reference_type
);
2526 pop_type (int_type
);
2527 require_array_type (pop_init_ref (reference_type
), reference_type
);
2530 pop_type (int_type
);
2531 pop_type (int_type
);
2532 require_array_type (pop_init_ref (reference_type
), byte_type
);
2535 pop_type (int_type
);
2536 pop_type (int_type
);
2537 require_array_type (pop_init_ref (reference_type
), char_type
);
2540 pop_type (int_type
);
2541 pop_type (int_type
);
2542 require_array_type (pop_init_ref (reference_type
), short_type
);
2549 type t
= pop_raw ();
2550 if (! type_iswide (&t
))
2573 type t2
= pop_raw ();
2574 if (! type_iswide (&t2
))
2588 type t
= pop_raw ();
2589 if (! type_iswide (&t
))
2603 type t1
= pop_raw ();
2605 if (! type_iswide (&t1
))
2620 type t1
= pop_raw ();
2621 if (type_iswide (&t1
))
2623 type t2
= pop_raw ();
2624 if (type_iswide (&t2
))
2641 type t3
= pop_raw ();
2642 if (type_iswide (&t3
))
2679 pop_type (int_type
);
2680 push_type_t (pop_type (int_type
));
2690 pop_type (long_type
);
2691 push_type_t (pop_type (long_type
));
2696 pop_type (int_type
);
2697 push_type_t (pop_type (long_type
));
2704 pop_type (float_type
);
2705 push_type_t (pop_type (float_type
));
2712 pop_type (double_type
);
2713 push_type_t (pop_type (double_type
));
2719 push_type_t (pop_type (int_type
));
2722 push_type_t (pop_type (long_type
));
2725 push_type_t (pop_type (float_type
));
2728 push_type_t (pop_type (double_type
));
2731 get_variable (get_byte (), int_type
);
2735 pop_type (int_type
);
2736 push_type (long_type
);
2739 pop_type (int_type
);
2740 push_type (float_type
);
2743 pop_type (int_type
);
2744 push_type (double_type
);
2747 pop_type (long_type
);
2748 push_type (int_type
);
2751 pop_type (long_type
);
2752 push_type (float_type
);
2755 pop_type (long_type
);
2756 push_type (double_type
);
2759 pop_type (float_type
);
2760 push_type (int_type
);
2763 pop_type (float_type
);
2764 push_type (long_type
);
2767 pop_type (float_type
);
2768 push_type (double_type
);
2771 pop_type (double_type
);
2772 push_type (int_type
);
2775 pop_type (double_type
);
2776 push_type (long_type
);
2779 pop_type (double_type
);
2780 push_type (float_type
);
2783 pop_type (long_type
);
2784 pop_type (long_type
);
2785 push_type (int_type
);
2789 pop_type (float_type
);
2790 pop_type (float_type
);
2791 push_type (int_type
);
2795 pop_type (double_type
);
2796 pop_type (double_type
);
2797 push_type (int_type
);
2805 pop_type (int_type
);
2806 push_jump (get_short ());
2814 pop_type (int_type
);
2815 pop_type (int_type
);
2816 push_jump (get_short ());
2820 pop_type (reference_type
);
2821 pop_type (reference_type
);
2822 push_jump (get_short ());
2825 push_jump (get_short ());
2829 handle_jsr_insn (get_short ());
2832 handle_ret_insn (get_byte ());
2834 case op_tableswitch
:
2838 pop_type (int_type
);
2840 push_jump (get_int ());
2843 /* Already checked LOW -vs- HIGH. */
2844 for (i
= low
; i
<= high
; ++i
)
2845 push_jump (get_int ());
2850 case op_lookupswitch
:
2853 jint npairs
, lastkey
;
2855 pop_type (int_type
);
2857 push_jump (get_int ());
2858 npairs
= get_int ();
2859 /* Already checked NPAIRS >= 0. */
2861 for (i
= 0; i
< npairs
; ++i
)
2863 jint key
= get_int ();
2864 if (i
> 0 && key
<= lastkey
)
2865 verify_fail_pc ("lookupswitch pairs unsorted", vfr
->start_PC
);
2867 push_jump (get_int ());
2873 check_return_type (pop_type (int_type
));
2877 check_return_type (pop_type (long_type
));
2881 check_return_type (pop_type (float_type
));
2885 check_return_type (pop_type (double_type
));
2889 check_return_type (pop_init_ref (reference_type
));
2893 /* We only need to check this when the return type is
2894 void, because all instance initializers return void. */
2896 state_check_this_initialized (vfr
->current_state
);
2897 check_return_type (make_type (void_type
));
2901 push_type_t (check_field_constant (get_ushort (), NULL
, false));
2904 pop_type_t (check_field_constant (get_ushort (), NULL
, false));
2909 type field
= check_field_constant (get_ushort (), &klass
, false);
2911 push_type_t (field
);
2917 type field
= check_field_constant (get_ushort (), &klass
, true);
2923 case op_invokevirtual
:
2924 case op_invokespecial
:
2925 case op_invokestatic
:
2926 case op_invokeinterface
:
2928 vfy_string method_name
, method_signature
;
2932 bool is_init
= false;
2935 = check_method_constant (get_ushort (),
2936 opcode
== op_invokeinterface
,
2939 /* NARGS is only used when we're processing
2940 invokeinterface. It is simplest for us to compute it
2941 here and then verify it later. */
2943 if (opcode
== op_invokeinterface
)
2945 nargs
= get_byte ();
2946 if (get_byte () != 0)
2947 verify_fail ("invokeinterface dummy byte is wrong");
2950 namec
= vfy_string_bytes (method_name
);
2952 if (vfy_strings_equal (method_name
, vfy_init_name()))
2955 if (opcode
!= op_invokespecial
)
2956 verify_fail ("can't invoke <init>");
2958 else if (namec
[0] == '<')
2959 verify_fail ("can't invoke method starting with `<'");
2961 arg_count
= vfy_count_arguments (method_signature
);
2963 /* Pop arguments and check types. */
2964 type
*arg_types
= (type
*) vfy_alloc (arg_count
* sizeof (type
));
2966 compute_argument_types (method_signature
, arg_types
);
2967 for (i
= arg_count
- 1; i
>= 0; --i
)
2969 /* This is only used for verifying the byte for
2971 nargs
-= type_depth (&arg_types
[i
]);
2972 pop_init_ref_t (arg_types
[i
]);
2975 vfy_free (arg_types
);
2978 if (opcode
== op_invokeinterface
2980 verify_fail ("wrong argument count for invokeinterface");
2982 if (opcode
!= op_invokestatic
)
2985 type t
= class_type
;
2988 /* In this case the PC doesn't matter. */
2989 type_set_uninitialized (&t
, UNINIT
);
2990 /* FIXME: check to make sure that the <init>
2991 call is to the right class.
2992 It must either be super or an exact class
2996 if (! types_compatible (&t
, &raw
))
2997 verify_fail ("incompatible type on stack");
3000 state_set_initialized (vfr
->current_state
,
3001 type_get_pc (&raw
), vfr
->current_method
->max_locals
);
3004 rt
= compute_return_type (method_signature
);
3005 if (! type_isvoid (&rt
))
3012 type t
= check_class_constant (get_ushort ());
3013 if (type_isarray (&t
) || type_isinterface (&t
)
3014 || type_isabstract (&t
))
3015 verify_fail ("type is array, interface, or abstract");
3016 type_set_uninitialized (&t
, vfr
->start_PC
);
3023 int atype
= get_byte ();
3025 /* We intentionally have chosen constants to make this
3027 if (atype
< boolean_type
|| atype
> long_type
)
3028 verify_fail_pc ("type not primitive", vfr
->start_PC
);
3029 pop_type (int_type
);
3030 init_type_from_class (&t
, construct_primitive_array_type (atype
));
3037 pop_type (int_type
);
3038 t
= check_class_constant (get_ushort ());
3039 push_type_t (type_to_array (&t
));
3042 case op_arraylength
:
3044 type t
= pop_init_ref (reference_type
);
3045 if (! type_isarray (&t
) && ! type_isnull (&t
))
3046 verify_fail ("array type expected");
3047 push_type (int_type
);
3051 pop_type_t (make_type_from_class (vfy_throwable_type ()));
3055 pop_init_ref (reference_type
);
3056 push_type_t (check_class_constant (get_ushort ()));
3059 pop_init_ref (reference_type
);
3060 check_class_constant (get_ushort ());
3061 push_type (int_type
);
3063 case op_monitorenter
:
3064 pop_init_ref (reference_type
);
3066 case op_monitorexit
:
3067 pop_init_ref (reference_type
);
3071 switch (get_byte ())
3074 push_type_t (get_variable (get_ushort (), int_type
));
3077 push_type_t (get_variable (get_ushort (), long_type
));
3080 push_type_t (get_variable (get_ushort (), float_type
));
3083 push_type_t (get_variable (get_ushort (), double_type
));
3086 push_type_t (get_variable (get_ushort (), reference_type
));
3089 set_variable (get_ushort (), pop_type (int_type
));
3092 set_variable (get_ushort (), pop_type (long_type
));
3095 set_variable (get_ushort (), pop_type (float_type
));
3098 set_variable (get_ushort (), pop_type (double_type
));
3101 set_variable (get_ushort (), pop_init_ref (reference_type
));
3104 handle_ret_insn (get_short ());
3107 get_variable (get_ushort (), int_type
);
3111 verify_fail_pc ("unrecognized wide instruction", vfr
->start_PC
);
3115 case op_multianewarray
:
3118 type atype
= check_class_constant (get_ushort ());
3119 int dim
= get_byte ();
3121 verify_fail_pc ("too few dimensions to multianewarray", vfr
->start_PC
);
3122 type_verify_dimensions (&atype
, dim
);
3123 for (i
= 0; i
< dim
; ++i
)
3124 pop_type (int_type
);
3125 push_type_t (atype
);
3130 pop_type (reference_type
);
3131 push_jump (get_short ());
3134 push_jump (get_int ());
3138 handle_jsr_insn (get_int ());
3142 /* Unrecognized opcode. */
3143 verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3149 /* This turns a `type' into something suitable for use by the type map
3150 in the other parts of the compiler. In particular, reference types
3151 are mapped to Object, primitive types are unchanged, and other
3152 types are mapped using special functions declared in verify.h. */
3154 collapse_type (type
*t
)
3167 return vfy_get_primitive_type (t
->key
);
3169 case unsuitable_type
:
3170 case continuation_type
:
3171 return vfy_unsuitable_type ();
3173 case return_address_type
:
3174 return vfy_return_address_type ();
3177 return vfy_null_type ();
3179 case reference_type
:
3180 case uninitialized_reference_type
:
3181 return vfy_object_type ();
3188 verify_instructions (void)
3193 verify_instructions_0 ();
3195 /* Now tell the rest of the compiler about the types we've found. */
3196 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3201 if ((vfr
->flags
[i
] & FLAG_INSN_SEEN
) != 0)
3202 vfy_note_instruction_seen (i
);
3204 if (! vfr
->states
[i
])
3207 curr
= vfr
->states
[i
]->val
;
3208 vfy_note_stack_depth (vfr
->current_method
, i
, curr
->stackdepth
);
3210 /* Tell the compiler about each local variable. */
3211 for (j
= 0; j
< vfr
->current_method
->max_locals
; ++j
)
3212 vfy_note_local_type (vfr
->current_method
, i
, j
,
3213 collapse_type (&curr
->locals
[j
]));
3214 /* Tell the compiler about each stack slot. */
3215 for (slot
= j
= 0; j
< curr
->stacktop
; ++j
, ++slot
)
3217 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3218 collapse_type (&curr
->stack
[j
]));
3219 if (type_iswide (&curr
->stack
[j
]))
3222 vfy_note_stack_type (vfr
->current_method
, i
, slot
,
3223 vfy_unsuitable_type ());
3226 if (slot
!= curr
->stackdepth
)
3232 make_verifier_context (vfy_method
*m
)
3234 vfr
= (verifier_context
*) vfy_alloc (sizeof (struct verifier_context
));
3236 vfr
->current_method
= m
;
3237 vfr
->bytecode
= vfy_get_bytecode (m
);
3238 vfr
->exception
= vfy_get_exceptions (m
);
3239 vfr
->current_class
= m
->defining_class
;
3243 vfr
->utf8_list
= NULL
;
3244 vfr
->isect_list
= NULL
;
3248 free_verifier_context (void)
3250 vfy_string_list
*utf8_list
;
3251 ref_intersection
*isect_list
;
3254 vfy_free (vfr
->flags
);
3256 utf8_list
= vfr
->utf8_list
;
3257 while (utf8_list
!= NULL
)
3259 vfy_string_list
*n
= utf8_list
->next
;
3260 vfy_free (utf8_list
);
3264 isect_list
= vfr
->isect_list
;
3265 while (isect_list
!= NULL
)
3267 ref_intersection
*next
= isect_list
->alloc_next
;
3268 vfy_free (isect_list
);
3272 if (vfr
->states
!= NULL
)
3275 for (i
= 0; i
< vfr
->current_method
->code_length
; ++i
)
3277 state_list
*iter
= vfr
->states
[i
];
3278 while (iter
!= NULL
)
3280 state_list
*next
= iter
->next
;
3281 free_state (iter
->val
);
3282 vfy_free (iter
->val
);
3287 vfy_free (vfr
->states
);
3294 verify_method (vfy_method
*meth
)
3296 debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth
->name
),
3300 verify_fail ("verifier re-entered");
3302 make_verifier_context (meth
);
3303 verify_instructions ();
3304 free_verifier_context ();