CodeVerify.h revision 319a33bf2d40e11a0074952d537584a0332b8e45 
1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * Dalvik bytecode verifier.
19 */
20#ifndef _DALVIK_CODEVERIFY
21#define _DALVIK_CODEVERIFY
22
23#include "analysis/VerifySubs.h"
24
25
26/*
27 * Enumeration for register type values.  The "hi" piece of a 64-bit value
28 * MUST immediately follow the "lo" piece in the enumeration, so we can check
29 * that hi==lo+1.
30 *
31 * Assignment of constants:
32 *   [-MAXINT,-32768)   : integer
33 *   [-32768,-128)      : short
34 *   [-128,0)           : byte
35 *   0                  : zero
36 *   1                  : one
37 *   [2,128)            : posbyte
38 *   [128,32768)        : posshort
39 *   [32768,65536)      : char
40 *   [65536,MAXINT]     : integer
41 *
42 * Allowed "implicit" widening conversions:
43 *   zero -> boolean, posbyte, byte, posshort, short, char, integer, ref (null)
44 *   one -> boolean, posbyte, byte, posshort, short, char, integer
45 *   boolean -> posbyte, byte, posshort, short, char, integer
46 *   posbyte -> posshort, short, integer, char
47 *   byte -> short, integer
48 *   posshort -> integer, char
49 *   short -> integer
50 *   char -> integer
51 *
52 * In addition, all of the above can convert to "float".
53 *
54 * We're more careful with integer values than the spec requires.  The
55 * motivation is to restrict byte/char/short to the correct range of values.
56 * For example, if a method takes a byte argument, we don't want to allow
57 * the code to load the constant "1024" and pass it in.
58 */
59enum {
60    kRegTypeUnknown = 0,    /* initial state; use value=0 so calloc works */
61    kRegTypeUninit = 1,     /* MUST be odd to distinguish from pointer */
62    kRegTypeConflict,       /* merge clash makes this reg's type unknowable */
63
64    /*
65     * Category-1nr types.  The order of these is chiseled into a couple
66     * of tables, so don't add, remove, or reorder if you can avoid it.
67     */
68#define kRegType1nrSTART    kRegTypeFloat
69    kRegTypeFloat,
70    kRegTypeZero,           /* 32-bit 0, could be Boolean, Int, Float, or Ref */
71    kRegTypeOne,            /* 32-bit 1, could be Boolean, Int, Float */
72    kRegTypeBoolean,        /* must be 0 or 1 */
73    kRegTypePosByte,        /* byte, known positive (can become char) */
74    kRegTypeByte,
75    kRegTypePosShort,       /* short, known positive (can become char) */
76    kRegTypeShort,
77    kRegTypeChar,
78    kRegTypeInteger,
79#define kRegType1nrEND      kRegTypeInteger
80
81    kRegTypeLongLo,         /* lower-numbered register; endian-independent */
82    kRegTypeLongHi,
83    kRegTypeDoubleLo,
84    kRegTypeDoubleHi,
85
86    /*
87     * Enumeration max; this is used with "full" (32-bit) RegType values.
88     *
89     * Anything larger than this is a ClassObject or uninit ref.  Mask off
90     * all but the low 8 bits; if you're left with kRegTypeUninit, pull
91     * the uninit index out of the high 24.  Because kRegTypeUninit has an
92     * odd value, there is no risk of a particular ClassObject pointer bit
93     * pattern being confused for it (assuming our class object allocator
94     * uses word alignment).
95     */
96    kRegTypeMAX
97};
98#define kRegTypeUninitMask  0xff
99#define kRegTypeUninitShift 8
100
101/*
102 * RegType holds information about the type of data held in a register.
103 * For most types it's a simple enum.  For reference types it holds a
104 * pointer to the ClassObject, and for uninitialized references it holds
105 * an index into the UninitInstanceMap.
106 */
107typedef u4 RegType;
108
109/*
110 * A bit vector indicating which entries in the monitor stack are
111 * associated with this register.  The low bit corresponds to the stack's
112 * bottom-most entry.
113 */
114typedef u4 MonitorEntries;
115#define kMaxMonitorStackDepth   (sizeof(MonitorEntries) * 8)
116
117/*
118 * During verification, we associate one of these with every "interesting"
119 * instruction.  We track the status of all registers, and (if the method
120 * has any monitor-enter instructions) maintain a stack of entered monitors
121 * (identified by code unit offset).
122 */
123typedef struct {
124    RegType*        regTypes;
125    MonitorEntries* monitorEntries;
126    u4*             monitorStack;
127    unsigned int    monitorStackTop;
128} RegisterLine;
129
130/*
131 * Table that maps uninitialized instances to classes, based on the
132 * address of the new-instance instruction.  One per method.
133 */
134typedef struct UninitInstanceMap {
135    int numEntries;
136    struct {
137        int             addr;   /* code offset, or -1 for method arg ("this") */
138        ClassObject*    clazz;  /* class created at this address */
139    } map[1];
140} UninitInstanceMap;
141#define kUninitThisArgAddr  (-1)
142#define kUninitThisArgSlot  0
143
144/*
145 * Various bits of data used by the verifier and register map generator.
146 */
147typedef struct VerifierData {
148    /*
149     * The method we're working on.
150     */
151    const Method*   method;
152
153    /*
154     * Number of code units of instructions in the method.  A cache of the
155     * value calculated by dvmGetMethodInsnsSize().
156     */
157    u4              insnsSize;
158
159    /*
160     * Number of registers we track for each instruction.  This is equal
161     * to the method's declared "registersSize".  (Does not include the
162     * pending return value.)
163     */
164    u4              insnRegCount;
165
166    /*
167     * Instruction widths and flags, one entry per code unit.
168     */
169    InsnFlags*      insnFlags;
170
171    /*
172     * Uninitialized instance map, used for tracking the movement of
173     * objects that have been allocated but not initialized.
174     */
175    UninitInstanceMap* uninitMap;
176
177    /*
178     * Array of RegisterLine structs, one entry per code unit.  We only need
179     * entries for code units that hold the start of an "interesting"
180     * instruction.  For register map generation, we're only interested
181     * in GC points.
182     */
183    RegisterLine*   registerLines;
184} VerifierData;
185
186
187/* table with static merge logic for primitive types */
188extern const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX];
189
190
191/*
192 * Returns "true" if the flags indicate that this address holds the start
193 * of an instruction.
194 */
195INLINE bool dvmInsnIsOpcode(const InsnFlags* insnFlags, int addr) {
196    return (insnFlags[addr] & kInsnFlagWidthMask) != 0;
197}
198
199/*
200 * Extract the unsigned 16-bit instruction width from "flags".
201 */
202INLINE int dvmInsnGetWidth(const InsnFlags* insnFlags, int addr) {
203    return insnFlags[addr] & kInsnFlagWidthMask;
204}
205
206/*
207 * Changed?
208 */
209INLINE bool dvmInsnIsChanged(const InsnFlags* insnFlags, int addr) {
210    return (insnFlags[addr] & kInsnFlagChanged) != 0;
211}
212INLINE void dvmInsnSetChanged(InsnFlags* insnFlags, int addr, bool changed)
213{
214    if (changed)
215        insnFlags[addr] |= kInsnFlagChanged;
216    else
217        insnFlags[addr] &= ~kInsnFlagChanged;
218}
219
220/*
221 * Visited?
222 */
223INLINE bool dvmInsnIsVisited(const InsnFlags* insnFlags, int addr) {
224    return (insnFlags[addr] & kInsnFlagVisited) != 0;
225}
226INLINE void dvmInsnSetVisited(InsnFlags* insnFlags, int addr, bool changed)
227{
228    if (changed)
229        insnFlags[addr] |= kInsnFlagVisited;
230    else
231        insnFlags[addr] &= ~kInsnFlagVisited;
232}
233
234/*
235 * Visited or changed?
236 */
237INLINE bool dvmInsnIsVisitedOrChanged(const InsnFlags* insnFlags, int addr) {
238    return (insnFlags[addr] & (kInsnFlagVisited|kInsnFlagChanged)) != 0;
239}
240
241/*
242 * In a "try" block?
243 */
244INLINE bool dvmInsnIsInTry(const InsnFlags* insnFlags, int addr) {
245    return (insnFlags[addr] & kInsnFlagInTry) != 0;
246}
247INLINE void dvmInsnSetInTry(InsnFlags* insnFlags, int addr, bool inTry)
248{
249    assert(inTry);
250    //if (inTry)
251        insnFlags[addr] |= kInsnFlagInTry;
252    //else
253    //    insnFlags[addr] &= ~kInsnFlagInTry;
254}
255
256/*
257 * Instruction is a branch target or exception handler?
258 */
259INLINE bool dvmInsnIsBranchTarget(const InsnFlags* insnFlags, int addr) {
260    return (insnFlags[addr] & kInsnFlagBranchTarget) != 0;
261}
262INLINE void dvmInsnSetBranchTarget(InsnFlags* insnFlags, int addr,
263    bool isBranch)
264{
265    assert(isBranch);
266    //if (isBranch)
267        insnFlags[addr] |= kInsnFlagBranchTarget;
268    //else
269    //    insnFlags[addr] &= ~kInsnFlagBranchTarget;
270}
271
272/*
273 * Instruction is a GC point?
274 */
275INLINE bool dvmInsnIsGcPoint(const InsnFlags* insnFlags, int addr) {
276    return (insnFlags[addr] & kInsnFlagGcPoint) != 0;
277}
278INLINE void dvmInsnSetGcPoint(InsnFlags* insnFlags, int addr,
279    bool isGcPoint)
280{
281    assert(isGcPoint);
282    //if (isGcPoint)
283        insnFlags[addr] |= kInsnFlagGcPoint;
284    //else
285    //    insnFlags[addr] &= ~kInsnFlagGcPoint;
286}
287
288
289/*
290 * Create a new UninitInstanceMap.
291 */
292UninitInstanceMap* dvmCreateUninitInstanceMap(const Method* meth,
293    const InsnFlags* insnFlags, int newInstanceCount);
294
295/*
296 * Release the storage associated with an UninitInstanceMap.
297 */
298void dvmFreeUninitInstanceMap(UninitInstanceMap* uninitMap);
299
300/*
301 * Associate a class with an address.  Returns the map slot index, or -1
302 * if the address isn't listed in the map (shouldn't happen) or if a
303 * different class is already associated with the address (shouldn't
304 * happen either).
305 */
306//int dvmSetUninitInstance(UninitInstanceMap* uninitMap, int addr,
307//    ClassObject* clazz);
308
309/*
310 * Return the class associated with an uninitialized reference.  Pass in
311 * the map index.
312 */
313//ClassObject* dvmGetUninitInstance(const UninitInstanceMap* uninitMap, int idx);
314
315/*
316 * Clear the class associated with an uninitialized reference.  Pass in
317 * the map index.
318 */
319//void dvmClearUninitInstance(UninitInstanceMap* uninitMap, int idx);
320
321
322/*
323 * Verify bytecode in "meth".  "insnFlags" should be populated with
324 * instruction widths and "in try" flags.
325 */
326bool dvmVerifyCodeFlow(VerifierData* vdata);
327
328#endif /*_DALVIK_CODEVERIFY*/
329