diff options
| author | 2011-09-08 17:57:10 -0700 | |
|---|---|---|
| committer | 2011-09-08 17:57:10 -0700 | |
| commit | 15041f433341f111665943ecfb9ca88c77d5c19a (patch) | |
| tree | 0587bef3a3a10acfc99e8586b0368be5dd10ef74 /src | |
| parent | 75bbd552bfe56e782473f669b7228e86189e243c (diff) | |
| parent | d1f0fdedff1dac7249e1ed61ddc52a09265c138f (diff) | |
Merge "Verifier now generates register maps, though nothing uses them yet." into dalvik-dev
Diffstat (limited to 'src')
| -rw-r--r-- | src/dex_verifier.cc | 851 | ||||
| -rw-r--r-- | src/dex_verifier.h | 349 | ||||
| -rw-r--r-- | src/leb128.h | 26 |
3 files changed, 988 insertions, 238 deletions
diff --git a/src/dex_verifier.cc b/src/dex_verifier.cc index 0a93109060..3380981fbb 100644 --- a/src/dex_verifier.cc +++ b/src/dex_verifier.cc @@ -145,7 +145,7 @@ bool DexVerifier::VerifyMethod(Method* method) { } /* - * Sanity-check the register counts. ins + locals = registers, so make + * Sanity-check the register counts. ins + locals = registers, so make * sure that ins <= registers. */ if (code_item->ins_size_ > code_item->registers_size_) { @@ -204,7 +204,7 @@ bool DexVerifier::VerifyInstructions(VerifierData* vdata) { while (width < insns_size) { if (!VerifyInstruction(vdata, inst, width)) { - LOG(ERROR) << "VFY: rejecting opcode 0x" << std::hex + LOG(ERROR) << "VFY: rejecting opcode 0x" << std::hex << (int) inst->Opcode() << " at 0x" << width << std::dec; return false; } @@ -316,6 +316,7 @@ bool DexVerifier::VerifyCodeFlow(VerifierData* vdata) { const DexFile::CodeItem* code_item = vdata->code_item_; uint16_t registers_size = code_item->registers_size_; uint32_t insns_size = code_item->insns_size_; + bool generate_register_map = true; RegisterTable reg_table; if (registers_size * insns_size > 4*1024*1024) { @@ -324,7 +325,8 @@ bool DexVerifier::VerifyCodeFlow(VerifierData* vdata) { } /* Create and initialize register lists. */ - if (!InitRegisterTable(vdata, ®_table, kTrackRegsGcPoints)) { + if (!InitRegisterTable(vdata, ®_table, + generate_register_map ? kTrackRegsGcPoints : kTrackRegsBranches)) { return false; } @@ -347,8 +349,16 @@ bool DexVerifier::VerifyCodeFlow(VerifierData* vdata) { return false; } - /* TODO: Generate a register map. */ - + /* Generate a register map. */ + if (generate_register_map) { + RegisterMap* map = GenerateRegisterMapV(vdata); + /* + * Tuck the map into the Method. It will either get used directly or, if + * we're in dexopt, will be packed up and appended to the DEX file. + */ + // TODO: Put the map somewhere... + delete map; + } return true; } @@ -792,7 +802,7 @@ bool DexVerifier::CheckBranchTarget(const DexFile::CodeItem* code_item, } /* - * Check for 32-bit overflow. This isn't strictly necessary if we can + * Check for 32-bit overflow. This isn't strictly necessary if we can * depend on the VM to have identical "wrap-around" behavior, but * it's unwise to depend on that. */ @@ -824,7 +834,7 @@ bool DexVerifier::InitRegisterTable(VerifierData* vdata, uint32_t i; /* - * Every address gets a RegisterLine struct. This is wasteful, but + * Every address gets a RegisterLine struct. This is wasteful, but * not so much that it's worth chasing through an extra level of * indirection. */ @@ -932,17 +942,15 @@ bool DexVerifier::IsInitMethod(const Method* method) { Class* DexVerifier::LookupClassByDescriptor(const Method* method, const char* descriptor, VerifyError* failure) { /* - * The compiler occasionally puts references to nonexistent - * classes in signatures. For example, if you have a non-static - * inner class with no constructor, the compiler provides - * a private <init> for you. Constructing the class - * requires <init>(parent), but the outer class can't call - * that because the method is private. So the compiler - * generates a package-scope <init>(parent,bogus) method that - * just calls the regular <init> (the "bogus" part being necessary - * to distinguish the signature of the synthetic method). - * Treating the bogus class as an instance of java.lang.Object - * allows the verifier to process the class successfully. + * The compiler occasionally puts references to nonexistent classes in + * signatures. For example, if you have a non-static inner class with no + * constructor, the compiler provides a private <init> for you. + * Constructing the class requires <init>(parent), but the outer class can't + * call that because the method is private. So the compiler generates a + * package-scope <init>(parent,bogus) method that just calls the regular + * <init> (the "bogus" part being necessary to distinguish the signature of + * the synthetic method). Treating the bogus class as an instance of + * java.lang.Object allows the verifier to process the class successfully. */ ClassLinker* class_linker = Runtime::Current()->GetClassLinker(); const ClassLoader* class_loader = @@ -971,12 +979,11 @@ Class* DexVerifier::LookupClassByDescriptor(const Method* method, } /* - * Try to continue with base array type. This will let - * us pass basic stuff (e.g. get array len) that wouldn't - * fly with an Object. This is NOT correct if the - * missing type is a primitive array, but we should never - * have a problem loading those. (I'm not convinced this - * is correct or even useful. Just use Object here?) + * Try to continue with base array type. This will let us pass basic + * stuff (e.g. get array len) that wouldn't fly with an Object. This + * is NOT correct if the missing type is a primitive array, but we + * should never have a problem loading those. (I'm not convinced this + * is correct or even useful. Just use Object here?) */ klass = class_linker->FindClass("[Ljava/lang/Object;", class_loader); } else if (descriptor[0] == 'L') { @@ -1061,7 +1068,7 @@ bool DexVerifier::SetTypesFromSignature(VerifierData* vdata, RegType* reg_types) if (!method->IsStatic()) { /* * If this is a constructor for a class other than java.lang.Object, - * mark the first ("this") argument as uninitialized. This restricts + * mark the first ("this") argument as uninitialized. This restricts * field access until the superclass constructor is called. */ ClassLinker* class_linker = Runtime::Current()->GetClassLinker(); @@ -1100,12 +1107,11 @@ bool DexVerifier::SetTypesFromSignature(VerifierData* vdata, RegType* reg_types) case 'L': case '[': /* - * We assume that reference arguments are initialized. The - * only way it could be otherwise (assuming the caller was - * verified) is if the current method is <init>, but in that - * case it's effectively considered initialized the instant - * we reach here (in the sense that we can return without - * doing anything or call virtual methods). + * We assume that reference arguments are initialized. The only way + * it could be otherwise (assuming the caller was verified) is if + * the current method is <init>, but in that case it's effectively + * considered initialized the instant we reach here (in the sense + * that we can return without doing anything or call virtual methods). */ { Class* klass = @@ -1166,8 +1172,8 @@ bool DexVerifier::SetTypesFromSignature(VerifierData* vdata, RegType* reg_types) const char* descriptor = dex_file->GetReturnTypeDescriptor(proto_id); /* - * Validate return type. We don't do the type lookup; just want to make - * sure that it has the right format. Only major difference from the + * Validate return type. We don't do the type lookup; just want to make + * sure that it has the right format. Only major difference from the * method argument format is that 'V' is supported. */ switch (*descriptor) { @@ -1216,7 +1222,7 @@ int DexVerifier::SetUninitInstance(UninitInstanceMap* uninit_map, int addr, int idx; assert(klass != NULL); - /* TODO: binary search when numEntries > 8 */ + /* TODO: binary search when num_entries > 8 */ for (idx = uninit_map->num_entries_ - 1; idx >= 0; idx--) { if (uninit_map->map_[idx].addr_ == addr) { if (uninit_map->map_[idx].klass_ != NULL && @@ -1253,7 +1259,7 @@ bool DexVerifier::CodeFlowVerifyMethod(VerifierData* vdata, /* Continue until no instructions are marked "changed". */ while (true) { /* - * Find the first marked one. Use "start_guess" as a way to find + * Find the first marked one. Use "start_guess" as a way to find * one quickly. */ for (insn_idx = start_guess; insn_idx < insns_size; insn_idx++) { @@ -1273,15 +1279,14 @@ bool DexVerifier::CodeFlowVerifyMethod(VerifierData* vdata, } /* - * We carry the working set of registers from instruction to - * instruction. If this address can be the target of a branch - * (or throw) instruction, or if we're skipping around chasing - * "changed" flags, we need to load the set of registers from - * the table. + * We carry the working set of registers from instruction to instruction. + * If this address can be the target of a branch (or throw) instruction, + * or if we're skipping around chasing "changed" flags, we need to load + * the set of registers from the table. * - * Because we always prefer to continue on to the next instruction, - * we should never have a situation where we have a stray - * "changed" flag set on an instruction that isn't a branch target. + * Because we always prefer to continue on to the next instruction, we + * should never have a situation where we have a stray "changed" flag set + * on an instruction that isn't a branch target. */ if (InsnIsBranchTarget(insn_flags, insn_idx)) { RegisterLine* work_line = ®_table->work_line_; @@ -1320,7 +1325,7 @@ bool DexVerifier::CodeFlowVerifyMethod(VerifierData* vdata, if (DEAD_CODE_SCAN && ((method->GetAccessFlags() & kAccWritable) == 0)) { /* - * Scan for dead code. There's nothing "evil" about dead code + * Scan for dead code. There's nothing "evil" about dead code * (besides the wasted space), but it indicates a flaw somewhere * down the line, possibly in the verifier. * @@ -1331,7 +1336,7 @@ bool DexVerifier::CodeFlowVerifyMethod(VerifierData* vdata, for (insn_idx = 0; insn_idx < insns_size; insn_idx += InsnGetWidth(insn_flags, insn_idx)) { /* - * Switch-statement data doesn't get "visited" by scanner. It + * Switch-statement data doesn't get "visited" by scanner. It * may or may not be preceded by a padding NOP (for alignment). */ if (insns[insn_idx] == Instruction::kPackedSwitchSignature || @@ -1392,14 +1397,14 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, /* * Once we finish decoding the instruction, we need to figure out where - * we can go from here. There are three possible ways to transfer + * we can go from here. There are three possible ways to transfer * control to another statement: * - * (1) Continue to the next instruction. Applies to all but + * (1) Continue to the next instruction. Applies to all but * unconditional branches, method returns, and exception throws. - * (2) Branch to one or more possible locations. Applies to branches + * (2) Branch to one or more possible locations. Applies to branches * and switch statements. - * (3) Exception handlers. Applies to any instruction that can + * (3) Exception handlers. Applies to any instruction that can * throw an exception that is handled by an encompassing "try" * block. * @@ -1422,7 +1427,7 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, VerifyError failure = VERIFY_ERROR_NONE; /* - * Make a copy of the previous register state. If the instruction + * Make a copy of the previous register state. If the instruction * can throw an exception, we will copy/merge this into the "catch" * address rather than work_line, because we don't want the result * from the "successful" code path (e.g. a check-cast that "improves" @@ -1442,7 +1447,7 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, switch (dec_insn.opcode_) { case Instruction::NOP: /* - * A "pure" NOP has no effect on anything. Data tables start with + * A "pure" NOP has no effect on anything. Data tables start with * a signature that looks like a NOP; if we see one of these in * the course of executing code then we have a problem. */ @@ -1472,12 +1477,12 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, /* * The move-result instructions copy data out of a "pseudo-register" - * with the results from the last method invocation. In practice we + * with the results from the last method invocation. In practice we * might want to hold the result in an actual CPU register, so the * Dalvik spec requires that these only appear immediately after an * invoke or filled-new-array. * - * These calls invalidate the "result" register. (This is now + * These calls invalidate the "result" register. (This is now * redundant with the reset done below, but it can make the debug info * easier to read in some cases.) */ @@ -1497,7 +1502,7 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, /* * This statement can only appear as the first instruction in an * exception handler (though not all exception handlers need to - * have one of these). We verify that as part of extracting the + * have one of these). We verify that as part of extracting the * exception type from the catch block list. * * "res_class" will hold the closest common superclass of all @@ -1585,7 +1590,7 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, /* * Verify that the reference in vAA is an instance of the type - * in "return_type". The Zero type is allowed here. If the + * in "return_type". The Zero type is allowed here. If the * method is declared to return an interface, then any * initialized reference is acceptable. * @@ -1659,21 +1664,21 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, break; case Instruction::MONITOR_EXIT: /* - * monitor-exit instructions are odd. They can throw exceptions, + * monitor-exit instructions are odd. They can throw exceptions, * but when they do they act as if they succeeded and the PC is - * pointing to the following instruction. (This behavior goes back + * pointing to the following instruction. (This behavior goes back * to the need to handle asynchronous exceptions, a now-deprecated * feature that Dalvik doesn't support.) * - * In practice we don't need to worry about this. The only + * In practice we don't need to worry about this. The only * exceptions that can be thrown from monitor-exit are for a - * null reference and -exit without a matching -enter. If the + * null reference and -exit without a matching -enter. If the * structured locking checks are working, the former would have * failed on the -enter instruction, and the latter is impossible. * * This is fortunate, because issue 3221411 prevents us from * chasing the "can throw" path when monitor verification is - * enabled. If we can fully verify the locking we can ignore + * enabled. If we can fully verify the locking we can ignore * some catch blocks (which will show up as "dead" code when * we skip them here); if we can't, then the code path could be * "live" so we still need to check it. @@ -1686,7 +1691,7 @@ bool DexVerifier::CodeFlowVerifyInstruction(VerifierData* vdata, case Instruction::CHECK_CAST: /* * If this instruction succeeds, we will promote register vA to - * the type in vB. (This could be a demotion -- not expected, so + * the type in vB. (This could be a demotion -- not expected, so * we don't try to address it.) * * If it fails, an exception is thrown, which we deal with later @@ -2100,7 +2105,7 @@ aget_1nr_common: } } else { /* - * Null array ref; this code path will fail at runtime. We + * Null array ref; this code path will fail at runtime. We * know this is either long or double, so label it const. */ dst_type = kRegTypeConstLo; @@ -2134,7 +2139,7 @@ aget_1nr_common: assert(res_class->GetComponentType() != NULL); /* - * Find the element class. res_class->GetComponentType() indicates + * Find the element class. res_class->GetComponentType() indicates * the basic type, which won't be what we want for a * multi-dimensional array. */ @@ -2158,7 +2163,7 @@ aget_1nr_common: } else { /* * The array reference is NULL, so the current code path will - * throw an exception. For proper merging with later code + * throw an exception. For proper merging with later code * paths, and correct handling of "if-eqz" tests on the * result of the array get, we want to treat this as a null * reference. @@ -2292,7 +2297,7 @@ aput_1nr_common: Class* element_class; /* - * Get the array class. If the array ref is null, we won't + * Get the array class. If the array ref is null, we won't * have type information (and we'll crash at runtime with a * null pointer exception). */ @@ -2308,12 +2313,12 @@ aput_1nr_common: } /* - * Find the element class. res_class->GetComponentType() indicates + * Find the element class. res_class->GetComponentType() indicates * the basic type, which won't be what we want for a * multi-dimensional array. * * All we want to check here is that the element type is a - * reference class. We *don't* check instanceof here, because + * reference class. We *don't* check instanceof here, because * you can still put a String into a String[] after the latter * has been cast to an Object[]. */ @@ -2730,7 +2735,7 @@ sput_1nr_common: break; /* - * Get type of field we're storing into. We know that the + * Get type of field we're storing into. We know that the * contents of the register match the instruction, but we also * need to ensure that the instruction matches the field type. * Using e.g. sput-short to write into a 32-bit integer field @@ -2899,9 +2904,9 @@ sput_1nr_common: break; /* - * Some additional checks when calling <init>. We know from + * Some additional checks when calling <init>. We know from * the invocation arg check that the "this" argument is an - * instance of called_method->klass. Now we further restrict + * instance of called_method->klass. Now we further restrict * that to require that called_method->klass is the same as * this->klass or this->super, allowing the latter only if * the "this" argument is the same as the "this" argument to @@ -2950,7 +2955,7 @@ sput_1nr_common: /* * Replace the uninitialized reference with an initialized - * one, and clear the entry in the uninit map. We need to + * one, and clear the entry in the uninit map. We need to * do this for all registers that have the same object * instance in them, not just the "this" register. */ @@ -2998,7 +3003,7 @@ sput_1nr_common: #if 0 /* can't do this here, fails on dalvik test 052-verifier-fun */ /* * Get the type of the "this" arg, which should always be an - * interface class. Because we don't do a full merge on + * interface class. Because we don't do a full merge on * interface classes, this might have reduced to Object. */ this_type = GetInvocationThis(work_line, &dec_insn, &failure); @@ -3020,7 +3025,7 @@ sput_1nr_common: /* * Either "this_class" needs to be the interface class that * defined abs_method, or abs_method's class needs to be one - * of the interfaces implemented by "this_class". (Or, if + * of the interfaces implemented by "this_class". (Or, if * we couldn't complete the merge, this will be Object.) */ if (this_class != abs_method->GetDeclaringClass() && @@ -3038,7 +3043,7 @@ sput_1nr_common: /* * We don't have an object instance, so we can't find the - * concrete method. However, all of the type information is + * concrete method. However, all of the type information is * in the abstract method, so we're good. */ return_type = GetMethodReturnType(dex_file, abs_method); @@ -3265,7 +3270,7 @@ sput_1nr_common: /* * This falls into the general category of "optimized" instructions, - * which don't generally appear during verification. Because it's + * which don't generally appear during verification. Because it's * inserted in the course of verification, we can expect to see it here. */ //case Instruction::THROW_VERIFICATION_ERROR: @@ -3274,32 +3279,32 @@ sput_1nr_common: /* * Verifying "quickened" instructions is tricky, because we have - * discarded the original field/method information. The byte offsets + * discarded the original field/method information. The byte offsets * and vtable indices only have meaning in the context of an object * instance. * * If a piece of code declares a local reference variable, assigns * null to it, and then issues a virtual method call on it, we - * cannot evaluate the method call during verification. This situation + * cannot evaluate the method call during verification. This situation * isn't hard to handle, since we know the call will always result in an - * NPE, and the arguments and return value don't matter. Any code that + * NPE, and the arguments and return value don't matter. Any code that * depends on the result of the method call is inaccessible, so the * fact that we can't fully verify anything that comes after the bad * call is not a problem. * * We must also consider the case of multiple code paths, only some of - * which involve a null reference. We can completely verify the method + * which involve a null reference. We can completely verify the method * if we sidestep the results of executing with a null reference. * For example, if on the first pass through the code we try to do a * virtual method invocation through a null ref, we have to skip the * method checks and have the method return a "wildcard" type (which - * merges with anything to become that other thing). The move-result + * merges with anything to become that other thing). The move-result * will tell us if it's a reference, single-word numeric, or double-word - * value. We continue to perform the verification, and at the end of + * value. We continue to perform the verification, and at the end of * the function any invocations that were never fully exercised are * marked as null-only. * - * We would do something similar for the field accesses. The field's + * We would do something similar for the field accesses. The field's * type, once known, can be used to recover the width of short integers. * If the object reference was null, the field-get returns the "wildcard" * type, which is acceptable for any operation. @@ -3332,9 +3337,9 @@ sput_1nr_common: /* * These instructions are equivalent (from the verifier's point of view) - * to the original form. The change was made for correctness rather + * to the original form. The change was made for correctness rather * than improved performance (except for invoke-object-init, which - * provides both). The substitution takes place after verification + * provides both). The substitution takes place after verification * completes, though, so we don't expect to see them here. */ case Instruction::UNUSED_F0: @@ -3385,7 +3390,7 @@ sput_1nr_common: break; /* - * DO NOT add a "default" clause here. Without it the compiler will + * DO NOT add a "default" clause here. Without it the compiler will * complain if an instruction is missing (which is desirable). */ } @@ -3418,9 +3423,9 @@ sput_1nr_common: } /* - * If we didn't just set the result register, clear it out. This + * If we didn't just set the result register, clear it out. This * ensures that you can only use "move-result" immediately after the - * result is set. (We could check this statically, but it's not + * result is set. (We could check this statically, but it's not * expensive and it makes our debugging output cleaner.) */ if (!just_set_result) { @@ -3430,7 +3435,7 @@ sput_1nr_common: } /* - * Handle "continue". Tag the next consecutive instruction. + * Handle "continue". Tag the next consecutive instruction. */ if ((opcode_flag & Instruction::kContinue) != 0) { size_t insn_width = InsnGetWidth(insn_flags, insn_idx); @@ -3442,7 +3447,7 @@ sput_1nr_common: /* * The only way to get to a move-exception instruction is to get - * thrown there. Make sure the next instruction isn't one. + * thrown there. Make sure the next instruction isn't one. */ if (!CheckMoveException(code_item->insns_, insn_idx + insn_width)) return false; @@ -3458,7 +3463,7 @@ sput_1nr_common: } else { /* * We're not recording register data for the next instruction, - * so we don't know what the prior state was. We have to + * so we don't know what the prior state was. We have to * assume that something has changed and re-evaluate it. */ InsnSetChanged(insn_flags, insn_idx + insn_width, true); @@ -3466,13 +3471,13 @@ sput_1nr_common: } /* - * Handle "branch". Tag the branch target. + * Handle "branch". Tag the branch target. * * NOTE: instructions like Instruction::EQZ provide information about the - * state of the register when the branch is taken or not taken. For example, + * state of the register when the branch is taken or not taken. For example, * somebody could get a reference field, check it for zero, and if the * branch is taken immediately store that register in a boolean field - * since the value is known to be zero. We do not currently account for + * since the value is known to be zero. We do not currently account for * that, and will reject the code. * * TODO: avoid re-fetching the branch target @@ -3499,7 +3504,7 @@ sput_1nr_common: } /* - * Handle "switch". Tag all possible branch targets. + * Handle "switch". Tag all possible branch targets. * * We've already verified that the table is structurally sound, so we * just need to walk through and tag the targets. @@ -3541,7 +3546,7 @@ sput_1nr_common: /* * Handle instructions that can throw and that are sitting in a - * "try" block. (If they're not in a "try" block when they throw, + * "try" block. (If they're not in a "try" block when they throw, * control transfers out of the method.) */ if ((opcode_flag & Instruction::kThrow) != 0 && @@ -3555,10 +3560,10 @@ sput_1nr_common: has_catch_all = true; /* - * Merge registers into the "catch" block. We want to - * use the "savedRegs" rather than "work_regs", because - * at runtime the exception will be thrown before the - * instruction modifies any registers. + * Merge registers into the "catch" block. We want to use the + * "savedRegs" rather than "work_regs", because at runtime the + * exception will be thrown before the instruction modifies any + * registers. */ if (!UpdateRegisters(insn_flags, reg_table, iterator.Get().address_, ®_table->saved_line_)) @@ -3567,7 +3572,7 @@ sput_1nr_common: /* * If the monitor stack depth is nonzero, there must be a "catch all" - * handler for this instruction. This does apply to monitor-exit + * handler for this instruction. This does apply to monitor-exit * because of async exception handling. */ if (work_line->monitor_stack_top_ != 0 && !has_catch_all) { @@ -3587,9 +3592,7 @@ sput_1nr_common: } } - /* - * If we're returning from the method, make sure our monitor stack is empty. - */ + /* If we're returning from the method, make sure monitor stack is empty. */ if ((opcode_flag & Instruction::kReturn) != 0 && work_line->monitor_stack_top_ != 0) { LOG(ERROR) << "VFY: return with stack depth=" @@ -3599,8 +3602,8 @@ sput_1nr_common: } /* - * Update start_guess. Advance to the next instruction of that's - * possible, otherwise use the branch target if one was found. If + * Update start_guess. Advance to the next instruction of that's + * possible, otherwise use the branch target if one was found. If * neither of those exists we're in a return or throw; leave start_guess * alone and let the caller sort it out. */ @@ -3769,7 +3772,7 @@ void DexVerifier::HandleMonitorExit(RegisterLine* work_line, uint32_t reg_idx, /* * Confirm that the entry at the top of the stack is associated with - * the register. Pop the top entry off. + * the register. Pop the top entry off. */ work_line->monitor_stack_top_--; #ifdef BUG_3215458_FIXED @@ -3840,7 +3843,6 @@ Field* DexVerifier::GetInstField(VerifierData* vdata, RegType obj_type, must_be_local = true; } - //if (!obj_class->InstanceOf(field->GetDeclaringClass())) { if (!field->GetDeclaringClass()->IsAssignableFrom(obj_class)) { LOG(ERROR) << "VFY: invalid field access (field " << field->GetDeclaringClass()->GetDescriptor()->ToModifiedUtf8() @@ -3927,10 +3929,10 @@ Class* DexVerifier::GetCaughtExceptionType(VerifierData* vdata, int insn_idx, LOG(ERROR) << "VFY: unable to resolve exception class " << handler.type_idx_ << " (" << dex_file->dexStringByTypeIdx(handler.type_idx_) << ")"; - /* TODO: do we want to keep going? If we don't fail - * this we run the risk of having a non-Throwable - * introduced at runtime. However, that won't pass - * an instanceof test, so is essentially harmless. + /* TODO: do we want to keep going? If we don't fail this we run + * the risk of having a non-Throwable introduced at runtime. + * However, that won't pass an instanceof test, so is essentially + * harmless. */ } else { if (common_super == NULL) @@ -4054,9 +4056,9 @@ void DexVerifier::SetRegisterType(RegisterLine* register_line, uint32_t vdst, /* * In most circumstances we won't see a reference to a primitive * class here (e.g. "D"), since that would mean the object in the - * register is actually a primitive type. It can happen as the + * register is actually a primitive type. It can happen as the * result of an assumed-successful check-cast instruction in - * which the second argument refers to a primitive class. (In + * which the second argument refers to a primitive class. (In * practice, such an instruction will always throw an exception.) * * This is not an issue for instructions like const-class, where @@ -4274,7 +4276,7 @@ void DexVerifier::CopyResultRegister1(RegisterLine* register_line, } /* - * Implement "move-result-wide". Copy the category-2 value from the result + * Implement "move-result-wide". Copy the category-2 value from the result * register to another register, and reset the result register. */ void DexVerifier::CopyResultRegister2(RegisterLine* register_line, @@ -4358,7 +4360,7 @@ Class* DexVerifier::FindCommonArraySuperclass(Class* c1, Class* c2) { if (!has_primitive && array_dim1 == array_dim2) { /* - * Two arrays of reference types with equal dimensions. Try to + * Two arrays of reference types with equal dimensions. Try to * find a good match. */ common_elem = FindCommonSuperclass(c1->GetComponentType(), @@ -4366,7 +4368,7 @@ Class* DexVerifier::FindCommonArraySuperclass(Class* c1, Class* c2) { num_dims = array_dim1; } else { /* - * Mismatched array depths and/or array(s) of primitives. We want + * Mismatched array depths and/or array(s) of primitives. We want * Object, or an Object array with appropriate dimensions. * * We initialize array_class to Object here, because it's possible @@ -4380,7 +4382,7 @@ Class* DexVerifier::FindCommonArraySuperclass(Class* c1, Class* c2) { } /* - * Find an appropriately-dimensioned array class. This is easiest + * Find an appropriately-dimensioned array class. This is easiest * to do iteratively, using the array class found by the current round * as the element type for the next round. */ @@ -4431,8 +4433,8 @@ DexVerifier::RegType DexVerifier::MergeTypes(RegType type1, RegType type2, * from the table with a reference type. * * Uninitialized references are composed of the enum ORed with an - * index value. The uninitialized table entry at index zero *will* - * show up as a simple kRegTypeUninit value. Since this cannot be + * index value. The uninitialized table entry at index zero *will* + * show up as a simple kRegTypeUninit value. Since this cannot be * merged with anything but itself, the rules do the right thing. */ if (type1 < kRegTypeMAX) { @@ -4491,8 +4493,8 @@ bool DexVerifier::UpdateRegisters(InsnFlags* insn_flags, if (!InsnIsVisitedOrChanged(insn_flags, next_insn)) { /* * We haven't processed this instruction before, and we haven't - * touched the registers here, so there's nothing to "merge". Copy - * the registers over and mark it as changed. (This is the only + * touched the registers here, so there's nothing to "merge". Copy + * the registers over and mark it as changed. (This is the only * way a register can transition out of "unknown", so this is not * just an optimization.) */ @@ -4651,7 +4653,7 @@ void DexVerifier::CheckArrayIndexType(const Method* method, RegType reg_type, VerifyError* failure) { if (*failure == VERIFY_ERROR_NONE) { /* - * The 1nr types are interchangeable at this level. We could + * The 1nr types are interchangeable at this level. We could * do something special if we can definitively identify it as a * float, but there's no real value in doing so. */ @@ -4909,8 +4911,8 @@ void DexVerifier::VerifyFilledNewArrayRegs(const Method* method, } /* - * Verify each register. If "arg_count" is bad, VerifyRegisterType() - * will run off the end of the list and fail. It's legal, if silly, + * Verify each register. If "arg_count" is bad, VerifyRegisterType() + * will run off the end of the list and fail. It's legal, if silly, * for arg_count to be zero. */ for (ui = 0; ui < arg_count; ui++) { @@ -4965,7 +4967,7 @@ Method* DexVerifier::VerifyInvocationArgs(VerifierData* vdata, int actual_args; /* - * Resolve the method. This could be an abstract or concrete method + * Resolve the method. This could be an abstract or concrete method * depending on what sort of call we're making. */ res_method = class_linker->ResolveMethod(*dex_file, dec_insn->vB_, dex_cache, @@ -4985,7 +4987,7 @@ Method* DexVerifier::VerifyInvocationArgs(VerifierData* vdata, /* * Only time you can explicitly call a method starting with '<' is when - * making a "direct" invocation on "<init>". There are additional + * making a "direct" invocation on "<init>". There are additional * restrictions but we don't enforce them here. */ if (res_method->GetName()->Equals("<init>")) { @@ -5039,7 +5041,7 @@ Method* DexVerifier::VerifyInvocationArgs(VerifierData* vdata, /* * We use vAA as our expected arg count, rather than res_method->insSize, - * because we need to match the call to the signature. Also, we might + * because we need to match the call to the signature. Also, we might * might be calling through an abstract method definition (which doesn't * have register count values). */ @@ -5064,7 +5066,7 @@ Method* DexVerifier::VerifyInvocationArgs(VerifierData* vdata, /* * Check the "this" argument, which must be an instance of the class - * that declared the method. For an interface class, we don't do the + * that declared the method. For an interface class, we don't do the * full interface merge, so we can't do a rigorous check here (which * is okay since we have to do it at runtime). */ @@ -5098,7 +5100,7 @@ Method* DexVerifier::VerifyInvocationArgs(VerifierData* vdata, } /* - * Process the target method's signature. This signature may or may not + * Process the target method's signature. This signature may or may not * have been verified, so we can't assume it's properly formed. */ for (sig_offset = 1; sig_offset < sig.size(); sig_offset++) { @@ -5220,4 +5222,595 @@ bad_sig: return NULL; } +DexVerifier::RegisterMap* DexVerifier::GenerateRegisterMapV(VerifierData* vdata) +{ + const DexFile::CodeItem* code_item = vdata->code_item_; + int i, bytes_for_addr, gc_point_count; + + if (code_item->registers_size_ >= 2048) { + LOG(ERROR) << "ERROR: register map can't handle " + << code_item->registers_size_ << " registers"; + return NULL; + } + uint8_t reg_width = (code_item->registers_size_ + 7) / 8; + + /* + * Decide if we need 8 or 16 bits to hold the address. Strictly speaking + * we only need 16 bits if we actually encode an address >= 256 -- if + * the method has a section at the end without GC points (e.g. array + * data) we don't need to count it. The situation is unusual, and + * detecting it requires scanning the entire method, so we don't bother. + */ + RegisterMapFormat format; + if (code_item->insns_size_ < 256) { + format = kRegMapFormatCompact8; + bytes_for_addr = 1; + } else { + format = kRegMapFormatCompact16; + bytes_for_addr = 2; + } + + /* + * Count up the number of GC point instructions. + * + * NOTE: this does not automatically include the first instruction, + * since we don't count method entry as a GC point. + */ + gc_point_count = 0; + for (i = 0; i < (int) code_item->insns_size_; i++) { + if (InsnIsGcPoint(vdata->insn_flags_.get(), i)) + gc_point_count++; + } + if (gc_point_count >= 65536) { + /* We could handle this, but in practice we don't get near this. */ + LOG(ERROR) << "ERROR: register map can't handle " << gc_point_count + << " gc points in one method"; + return NULL; + } + + /* Calculate size of buffer to hold the map data. */ + uint32_t data_size = gc_point_count * (bytes_for_addr + reg_width); + + RegisterMap* map = new RegisterMap(format, reg_width, gc_point_count, + true, data_size); + + /* Populate it. */ + uint8_t* map_data = map->data_.get(); + for (i = 0; i < (int) vdata->code_item_->insns_size_; i++) { + if (InsnIsGcPoint(vdata->insn_flags_.get(), i)) { + assert(vdata->register_lines_[i].reg_types_.get() != NULL); + if (format == kRegMapFormatCompact8) { + *map_data++ = i; + } else /*kRegMapFormatCompact16*/ { + *map_data++ = i & 0xff; + *map_data++ = i >> 8; + } + OutputTypeVector(vdata->register_lines_[i].reg_types_.get(), + code_item->registers_size_, map_data); + map_data += reg_width; + } + } + + assert((uint32_t) map_data - (uint32_t) map->data_.get() == data_size); + + // TODO: Remove this check when it's really running... +#if 1 + if (!VerifyMap(vdata, map)) { + LOG(ERROR) << "Map failed to verify"; + return NULL; + } +#endif + + /* Try to compress the map. */ + RegisterMap* compress_map = CompressMapDifferential(map); + if (compress_map != NULL) { + // TODO: Remove this check when it's really running... +#if 1 + /* + * Expand the compressed map we just created, and compare it + * to the original. Abort the VM if it doesn't match up. + */ + UniquePtr<RegisterMap> uncompressed_map(UncompressMapDifferential(compress_map)); + if (uncompressed_map.get() == NULL) { + LOG(ERROR) << "Map failed to uncompress - " + << vdata->method_->GetDeclaringClass()->GetDescriptor()->ToModifiedUtf8() + << "." << vdata->method_->GetName()->ToModifiedUtf8(); + delete map; + delete compress_map; + /* bad - compression is broken or we're out of memory */ + return NULL; + } else { + if (!CompareMaps(map, uncompressed_map.get())) { + LOG(ERROR) << "Map comparison failed - " + << vdata->method_->GetDeclaringClass()->GetDescriptor()->ToModifiedUtf8() + << "." << vdata->method_->GetName()->ToModifiedUtf8(); + delete map; + delete compress_map; + /* bad - compression is broken */ + return NULL; + } + } +#endif + delete map; + map = compress_map; + } + + return map; +} + +void DexVerifier::OutputTypeVector(const RegType* regs, int insn_reg_count, + uint8_t* data) { + uint8_t val = 0; + int i; + + for (i = 0; i < insn_reg_count; i++) { + RegType type = *regs++; + val >>= 1; + if (IsReferenceType(type)) + val |= 0x80; /* set hi bit */ + + if ((i & 0x07) == 7) + *data++ = val; + } + if ((i & 0x07) != 0) { + /* Flush bits from last byte. */ + val >>= 8 - (i & 0x07); + *data++ = val; + } +} + +bool DexVerifier::VerifyMap(VerifierData* vdata, const RegisterMap* map) { + const uint8_t* raw_map = map->data_.get(); + uint8_t format = map->format_; + const int num_entries = map->num_entries_; + int ent; + + if ((vdata->code_item_->registers_size_ + 7) / 8 != map->reg_width_) { + LOG(ERROR) << "GLITCH: registersSize=" << vdata->code_item_->registers_size_ + << ", reg_width=" << map->reg_width_; + return false; + } + + for (ent = 0; ent < num_entries; ent++) { + int addr; + + switch (format) { + case kRegMapFormatCompact8: + addr = *raw_map++; + break; + case kRegMapFormatCompact16: + addr = *raw_map++; + addr |= (*raw_map++) << 8; + break; + default: + LOG(FATAL) << "GLITCH: bad format (" << format << ")"; + return false; + } + + const RegType* regs = vdata->register_lines_[addr].reg_types_.get(); + if (regs == NULL) { + LOG(ERROR) << "GLITCH: addr " << addr << " has no data"; + return false; + } + + uint8_t val = 0; + int i; + + for (i = 0; i < vdata->code_item_->registers_size_; i++) { + bool bit_is_ref, reg_is_ref; + + val >>= 1; + if ((i & 0x07) == 0) { + /* Load next byte of data. */ + val = *raw_map++; + } + + bit_is_ref = val & 0x01; + + RegType type = regs[i]; + reg_is_ref = IsReferenceType(type); + + if (bit_is_ref != reg_is_ref) { + LOG(ERROR) << "GLITCH: addr " << addr << " reg " << i << ": bit=" + << bit_is_ref << " reg=" << reg_is_ref << "(" << type << ")"; + return false; + } + } + /* Raw_map now points to the address field of the next entry. */ + } + + return true; +} + +bool DexVerifier::CompareMaps(const RegisterMap* map1, const RegisterMap* map2) +{ + size_t size1, size2; + + size1 = ComputeRegisterMapSize(map1); + size2 = ComputeRegisterMapSize(map2); + if (size1 != size2) { + LOG(ERROR) << "CompareMaps: size mismatch (" << size1 << " vs " << size2 + << ")"; + return false; + } + + if (map1->format_ != map2->format_ || map1->reg_width_ != map2->reg_width_ || + map1->num_entries_ != map2->num_entries_ || + map1->format_on_heap_ != map2->format_on_heap_) { + LOG(ERROR) << "CompareMaps: fields mismatch"; + } + if (memcmp(map1->data_.get(), map2->data_.get(), size1) != 0) { + LOG(ERROR) << "CompareMaps: data mismatch"; + return false; + } + + return true; +} + +size_t DexVerifier::ComputeRegisterMapSize(const RegisterMap* map) { + uint8_t format = map->format_; + uint16_t num_entries = map->num_entries_; + + assert(map != NULL); + + switch (format) { + case kRegMapFormatNone: + return 1; + case kRegMapFormatCompact8: + return (1 + map->reg_width_) * num_entries; + case kRegMapFormatCompact16: + return (2 + map->reg_width_) * num_entries; + case kRegMapFormatDifferential: + { + /* Decoded ULEB128 length. */ + const uint8_t* ptr = map->data_.get(); + return DecodeUnsignedLeb128(&ptr); + } + default: + LOG(FATAL) << "Bad register map format " << format; + return 0; + } +} + +int DexVerifier::ComputeBitDiff(const uint8_t* bits1, const uint8_t* bits2, + int byte_width, int* first_bit_changed_ptr, int* num_bits_changed_ptr, + uint8_t* leb_out_buf) { + int num_bits_changed = 0; + int first_bit_changed = -1; + int leb_size = 0; + int byte_num; + + /* + * Run through the vectors, first comparing them at the byte level. This + * will yield a fairly quick result if nothing has changed between them. + */ + for (byte_num = 0; byte_num < byte_width; byte_num++) { + uint8_t byte1 = *bits1++; + uint8_t byte2 = *bits2++; + if (byte1 != byte2) { + /* Walk through the byte, identifying the changed bits. */ + int bit_num; + for (bit_num = 0; bit_num < 8; bit_num++) { + if (((byte1 >> bit_num) & 0x01) != ((byte2 >> bit_num) & 0x01)) { + int bit_offset = (byte_num << 3) + bit_num; + + if (first_bit_changed < 0) + first_bit_changed = bit_offset; + num_bits_changed++; + + if (leb_out_buf == NULL) { + leb_size += UnsignedLeb128Size(bit_offset); + } else { + uint8_t* cur_buf = leb_out_buf; + leb_out_buf = WriteUnsignedLeb128(leb_out_buf, bit_offset); + leb_size += leb_out_buf - cur_buf; + } + } + } + } + } + + if (num_bits_changed > 0) + assert(first_bit_changed >= 0); + + if (first_bit_changed_ptr != NULL) + *first_bit_changed_ptr = first_bit_changed; + if (num_bits_changed_ptr != NULL) + *num_bits_changed_ptr = num_bits_changed; + + return leb_size; +} + +DexVerifier::RegisterMap* DexVerifier::CompressMapDifferential( + const RegisterMap* map) { + int orig_size = ComputeRegisterMapSize(map); + uint8_t* tmp_ptr; + int addr_width; + + uint8_t format = map->format_; + switch (format) { + case kRegMapFormatCompact8: + addr_width = 1; + break; + case kRegMapFormatCompact16: + addr_width = 2; + break; + default: + LOG(ERROR) << "ERROR: can't compress map with format=" << format; + return NULL; + } + + int reg_width = map->reg_width_; + int num_entries = map->num_entries_; + + if (num_entries <= 1) { + return NULL; + } + + /* + * We don't know how large the compressed data will be. It's possible + * for it to expand and become larger than the original. The header + * itself is variable-sized, so we generate everything into a temporary + * buffer and then copy it to form-fitting storage once we know how big + * it will be (and that it's smaller than the original). + * + * If we use a size that is equal to the size of the input map plus + * a value longer than a single entry can possibly expand to, we need + * only check for overflow at the end of each entry. The worst case + * for a single line is (1 + <ULEB8 address> + <full copy of vector>). + * Addresses are 16 bits, so that's (1 + 3 + reg_width). + * + * The initial address offset and bit vector will take up less than + * or equal to the amount of space required when uncompressed -- large + * initial offsets are rejected. + */ + UniquePtr<uint8_t[]> tmp_buf(new uint8_t[orig_size + (1 + 3 + reg_width)]); + + tmp_ptr = tmp_buf.get(); + + const uint8_t* map_data = map->data_.get(); + const uint8_t* prev_bits; + uint16_t addr, prev_addr; + + addr = *map_data++; + if (addr_width > 1) + addr |= (*map_data++) << 8; + + if (addr >= 128) { + LOG(ERROR) << "Can't compress map with starting address >= 128"; + return NULL; + } + + /* + * Start by writing the initial address and bit vector data. The high + * bit of the initial address is used to indicate the required address + * width (which the decoder can't otherwise determine without parsing + * the compressed data). + */ + *tmp_ptr++ = addr | (addr_width > 1 ? 0x80 : 0x00); + memcpy(tmp_ptr, map_data, reg_width); + + prev_bits = map_data; + prev_addr = addr; + + tmp_ptr += reg_width; + map_data += reg_width; + + /* Loop over all following entries. */ + for (int entry = 1; entry < num_entries; entry++) { + int addr_diff; + uint8_t key; + + /* Pull out the address and figure out how to encode it. */ + addr = *map_data++; + if (addr_width > 1) + addr |= (*map_data++) << 8; + + addr_diff = addr - prev_addr; + assert(addr_diff > 0); + if (addr_diff < 8) { + /* Small difference, encode in 3 bits. */ + key = addr_diff -1; /* set 00000AAA */ + } else { + /* Large difference, output escape code. */ + key = 0x07; /* escape code for AAA */ + } + + int num_bits_changed, first_bit_changed, leb_size; + + leb_size = ComputeBitDiff(prev_bits, map_data, reg_width, + &first_bit_changed, &num_bits_changed, NULL); + + if (num_bits_changed == 0) { + /* set B to 1 and CCCC to zero to indicate no bits were changed */ + key |= 0x08; + } else if (num_bits_changed == 1 && first_bit_changed < 16) { + /* set B to 0 and CCCC to the index of the changed bit */ + key |= first_bit_changed << 4; + } else if (num_bits_changed < 15 && leb_size < reg_width) { + /* set B to 1 and CCCC to the number of bits */ + key |= 0x08 | (num_bits_changed << 4); + } else { + /* set B to 1 and CCCC to 0x0f so we store the entire vector */ + key |= 0x08 | 0xf0; + } + + /* + * Encode output. Start with the key, follow with the address + * diff (if it didn't fit in 3 bits), then the changed bit info. + */ + *tmp_ptr++ = key; + if ((key & 0x07) == 0x07) + tmp_ptr = WriteUnsignedLeb128(tmp_ptr, addr_diff); + + if ((key & 0x08) != 0) { + int bit_count = key >> 4; + if (bit_count == 0) { + /* nothing changed, no additional output required */ + } else if (bit_count == 15) { + /* full vector is most compact representation */ + memcpy(tmp_ptr, map_data, reg_width); + tmp_ptr += reg_width; + } else { + /* write bit indices in ULEB128 format */ + (void) ComputeBitDiff(prev_bits, map_data, reg_width, + NULL, NULL, tmp_ptr); + tmp_ptr += leb_size; + } + } else { + /* single-bit changed, value encoded in key byte */ + } + + prev_bits = map_data; + prev_addr = addr; + map_data += reg_width; + + /* See if we've run past the original size. */ + if (tmp_ptr - tmp_buf.get() >= orig_size) { + return NULL; + } + } + + /* + * Create a RegisterMap with the contents. + * + * TODO: consider using a threshold other than merely ">=". We would + * get poorer compression but potentially use less native heap space. + */ + int new_data_size = tmp_ptr - tmp_buf.get(); + int new_map_size = new_data_size + UnsignedLeb128Size(new_data_size); + + if (new_map_size >= orig_size) { + return NULL; + } + + RegisterMap* new_map = new RegisterMap(kRegMapFormatDifferential, reg_width, + num_entries, true, new_map_size); + + tmp_ptr = new_map->data_.get(); + tmp_ptr = WriteUnsignedLeb128(tmp_ptr, new_data_size); + memcpy(tmp_ptr, tmp_buf.get(), new_data_size); + + return new_map; +} + +DexVerifier::RegisterMap* DexVerifier::UncompressMapDifferential( + const RegisterMap* map) { + uint8_t format = map->format_; + RegisterMapFormat new_format; + int reg_width, num_entries, new_addr_width, new_data_size; + + if (format != kRegMapFormatDifferential) { + LOG(ERROR) << "Not differential (" << format << ")"; + return NULL; + } + + reg_width = map->reg_width_; + num_entries = map->num_entries_; + + /* Get the data size; we can check this at the end. */ + const uint8_t* src_ptr = map->data_.get(); + int expected_src_len = DecodeUnsignedLeb128(&src_ptr); + const uint8_t* src_start = src_ptr; + + /* Get the initial address and the 16-bit address flag. */ + int addr = *src_ptr & 0x7f; + if ((*src_ptr & 0x80) == 0) { + new_format = kRegMapFormatCompact8; + new_addr_width = 1; + } else { + new_format = kRegMapFormatCompact16; + new_addr_width = 2; + } + src_ptr++; + + /* Now we know enough to allocate the new map. */ + new_data_size = (new_addr_width + reg_width) * num_entries; + RegisterMap* new_map = new RegisterMap(new_format, reg_width, num_entries, + true, new_data_size); + + /* Write the start address and initial bits to the new map. */ + uint8_t* dst_ptr = new_map->data_.get(); + + *dst_ptr++ = addr & 0xff; + if (new_addr_width > 1) + *dst_ptr++ = (uint8_t) (addr >> 8); + + memcpy(dst_ptr, src_ptr, reg_width); + + int prev_addr = addr; + const uint8_t* prev_bits = dst_ptr; /* point at uncompressed data */ + + dst_ptr += reg_width; + src_ptr += reg_width; + + /* Walk through, uncompressing one line at a time. */ + int entry; + for (entry = 1; entry < num_entries; entry++) { + int addr_diff; + uint8_t key; + + key = *src_ptr++; + + /* Get the address. */ + if ((key & 0x07) == 7) { + /* Address diff follows in ULEB128. */ + addr_diff = DecodeUnsignedLeb128(&src_ptr); + } else { + addr_diff = (key & 0x07) +1; + } + + addr = prev_addr + addr_diff; + *dst_ptr++ = addr & 0xff; + if (new_addr_width > 1) + *dst_ptr++ = (uint8_t) (addr >> 8); + + /* Unpack the bits. */ + if ((key & 0x08) != 0) { + int bit_count = (key >> 4); + if (bit_count == 0) { + /* No bits changed, just copy previous. */ + memcpy(dst_ptr, prev_bits, reg_width); + } else if (bit_count == 15) { + /* Full copy of bit vector is present; ignore prev_bits. */ + memcpy(dst_ptr, src_ptr, reg_width); + src_ptr += reg_width; + } else { + /* Copy previous bits and modify listed indices. */ + memcpy(dst_ptr, prev_bits, reg_width); + while (bit_count--) { + int bit_index = DecodeUnsignedLeb128(&src_ptr); + ToggleBit(dst_ptr, bit_index); + } + } + } else { + /* Copy previous bits and modify the specified one. */ + memcpy(dst_ptr, prev_bits, reg_width); + + /* One bit, from 0-15 inclusive, was changed. */ + ToggleBit(dst_ptr, key >> 4); + } + + prev_addr = addr; + prev_bits = dst_ptr; + dst_ptr += reg_width; + } + + if (dst_ptr - new_map->data_.get() != new_data_size) { + LOG(ERROR) << "ERROR: output " << dst_ptr - new_map->data_.get() + << " bytes, expected " << new_data_size; + free(new_map); + return NULL; + } + + if (src_ptr - src_start != expected_src_len) { + LOG(ERROR) << "ERROR: consumed " << src_ptr - src_start + << " bytes, expected " << expected_src_len; + free(new_map); + return NULL; + } + + return new_map; +} + } // namespace art diff --git a/src/dex_verifier.h b/src/dex_verifier.h index c89dfaf412..a8351dfc0f 100644 --- a/src/dex_verifier.h +++ b/src/dex_verifier.h @@ -14,7 +14,7 @@ namespace art { #define kMaxMonitorStackDepth (sizeof(MonitorEntries) * 8) /* - * Set this to enable dead code scanning. This is not required, but it's + * Set this to enable dead code scanning. This is not required, but it's * very useful when testing changes to the verifier (to make sure we're not * skipping over stuff). The only reason not to do it is that it slightly * increases the time required to perform verification. @@ -26,7 +26,7 @@ namespace art { #endif /* - * We need an extra "pseudo register" to hold the return type briefly. It + * We need an extra "pseudo register" to hold the return type briefly. It * can be category 1 or 2, so we need two slots. */ #define kExtraRegs 2 @@ -36,7 +36,7 @@ class DexVerifier { public: /* * RegType holds information about the type of data held in a register. - * For most types it's a simple enum. For reference types it holds a + * For most types it's a simple enum. For reference types it holds a * pointer to the ClassObject, and for uninitialized references it holds * an index into the UninitInstanceMap. */ @@ -44,7 +44,7 @@ class DexVerifier { /* * A bit vector indicating which entries in the monitor stack are - * associated with this register. The low bit corresponds to the stack's + * associated with this register. The low bit corresponds to the stack's * bottom-most entry. */ typedef uint32_t MonitorEntries; @@ -71,12 +71,12 @@ class DexVerifier { }; /* - * "Direct" and "virtual" methods are stored independently. The type of call + * "Direct" and "virtual" methods are stored independently. The type of call * used to invoke the method determines which list we search, and whether * we travel up into superclasses. * * (<clinit>, <init>, and methods declared "private" or "static" are stored - * in the "direct" list. All others are stored in the "virtual" list.) + * in the "direct" list. All others are stored in the "virtual" list.) */ enum MethodType { METHOD_UNKNOWN = 0, @@ -98,7 +98,7 @@ class DexVerifier { }; /* - * Enumeration for register type values. The "hi" piece of a 64-bit value + * Enumeration for register type values. The "hi" piece of a 64-bit value * MUST immediately follow the "lo" piece in the enumeration, so we can check * that hi==lo+1. * @@ -125,7 +125,7 @@ class DexVerifier { * * In addition, all of the above can convert to "float". * - * We're more careful with integer values than the spec requires. The + * We're more careful with integer values than the spec requires. The * motivation is to restrict byte/char/short to the correct range of values. * For example, if a method takes a byte argument, we don't want to allow * the code to load the constant "1024" and pass it in. @@ -136,7 +136,7 @@ class DexVerifier { kRegTypeConflict, /* merge clash makes this reg's type unknowable */ /* - * Category-1nr types. The order of these is chiseled into a couple + * Category-1nr types. The order of these is chiseled into a couple * of tables, so don't add, remove, or reorder if you can avoid it. */ #define kRegType1nrSTART kRegTypeZero @@ -167,9 +167,9 @@ class DexVerifier { /* * Enumeration max; this is used with "full" (32-bit) RegType values. * - * Anything larger than this is a ClassObject or uninit ref. Mask off + * Anything larger than this is a ClassObject or uninit ref. Mask off * all but the low 8 bits; if you're left with kRegTypeUninit, pull - * the uninit index out of the high 24. Because kRegTypeUninit has an + * the uninit index out of the high 24. Because kRegTypeUninit has an * odd value, there is no risk of a particular ClassObject pointer bit * pattern being confused for it (assuming our class object allocator * uses word alignment). @@ -183,9 +183,9 @@ class DexVerifier { * Register type categories, for type checking. * * The spec says category 1 includes boolean, byte, char, short, int, float, - * reference, and returnAddress. Category 2 includes long and double. + * reference, and returnAddress. Category 2 includes long and double. * - * We treat object references separately, so we have "category1nr". We + * We treat object references separately, so we have "category1nr". We * don't support jsr/ret, so there is no "returnAddress" type. */ enum TypeCategory { @@ -225,13 +225,24 @@ class DexVerifier { #define kVerifyErrorRefTypeShift 6 /* + * Format enumeration for RegisterMap data area. + */ + enum RegisterMapFormat { + kRegMapFormatUnknown = 0, + kRegMapFormatNone, /* indicates no map data follows */ + kRegMapFormatCompact8, /* compact layout, 8-bit addresses */ + kRegMapFormatCompact16, /* compact layout, 16-bit addresses */ + kRegMapFormatDifferential, /* compressed, differential encoding */ + }; + + /* * During verification, we associate one of these with every "interesting" - * instruction. We track the status of all registers, and (if the method + * instruction. We track the status of all registers, and (if the method * has any monitor-enter instructions) maintain a stack of entered monitors * (identified by code unit offset). * * If live-precise register maps are enabled, the "liveRegs" vector will - * be populated. Unlike the other lists of registers here, we do not + * be populated. Unlike the other lists of registers here, we do not * track the liveness of the method result register (which is not visible * to the GC). */ @@ -242,7 +253,8 @@ class DexVerifier { uint32_t monitor_stack_top_; RegisterLine() - : reg_types_(NULL), monitor_entries_(NULL), monitor_stack_(NULL), monitor_stack_top_(0) { + : reg_types_(NULL), monitor_entries_(NULL), monitor_stack_(NULL), + monitor_stack_top_(0) { } /* Allocate space for the fields. */ @@ -258,14 +270,14 @@ class DexVerifier { /* Big fat collection of register data. */ struct RegisterTable { /* - * Array of RegisterLine structs, one per address in the method. We only + * Array of RegisterLine structs, one per address in the method. We only * set the pointers for certain addresses, based on instruction widths * and what we're trying to accomplish. */ UniquePtr<RegisterLine[]> register_lines_; /* - * Number of registers we track for each instruction. This is equal + * Number of registers we track for each instruction. This is equal * to the method's declared "registersSize" plus kExtraRegs (2). */ size_t insn_reg_count_plus_; @@ -291,7 +303,7 @@ class DexVerifier { /* * Table that maps uninitialized instances to classes, based on the - * address of the new-instance instruction. One per method. + * address of the new-instance instruction. One per method. */ struct UninitInstanceMap { int num_entries_; @@ -326,9 +338,9 @@ class DexVerifier { UniquePtr<UninitInstanceMap> uninit_map_; /* - * Array of RegisterLine structs, one entry per code unit. We only need + * Array of RegisterLine structs, one entry per code unit. We only need * entries for code units that hold the start of an "interesting" - * instruction. For register map generation, we're only interested + * instruction. For register map generation, we're only interested * in GC points. */ RegisterLine* register_lines_; @@ -341,15 +353,45 @@ class DexVerifier { const DexFile::CodeItem* code_item) : method_(method), dex_file_(dex_file), code_item_(code_item), insn_flags_(NULL), uninit_map_(NULL), register_lines_(NULL), - new_instance_count_(0), monitor_enter_count_(0) { } + new_instance_count_(0), monitor_enter_count_(0) { + } + }; + + /* + * This is a single variable-size structure. It may be allocated on the + * heap or mapped out of a (post-dexopt) DEX file. + * + * 32-bit alignment of the structure is NOT guaranteed. This makes it a + * little awkward to deal with as a structure; to avoid accidents we use + * only byte types. Multi-byte values are little-endian. + * + * Size of (format==FormatNone): 1 byte + * Size of (format==FormatCompact8): 4 + (1 + reg_width) * num_entries + * Size of (format==FormatCompact16): 4 + (2 + reg_width) * num_entries + */ + struct RegisterMap { + /* header */ + uint8_t format_; /* enum RegisterMapFormat; MUST be first entry */ + uint8_t reg_width_; /* bytes per register line, 1+ */ + uint16_t num_entries_; /* number of entries */ + bool format_on_heap_; /* indicates allocation on heap */ + + /* raw data starts here; need not be aligned */ + UniquePtr<uint8_t[]> data_; + + RegisterMap(uint8_t format, uint8_t reg_width, uint16_t num_entries, + bool format_on_heap, uint32_t data_size) + : format_(format), reg_width_(reg_width), num_entries_(num_entries), + format_on_heap_(format_on_heap), data_(new uint8_t[data_size]()) { + } }; /* - * Merge result table for primitive values. The table is symmetric along + * Merge result table for primitive values. The table is symmetric along * the diagonal. * - * Note that 32-bit int/float do not merge into 64-bit long/double. This - * is a register merge, not a widening conversion. Only the "implicit" + * Note that 32-bit int/float do not merge into 64-bit long/double. This + * is a register merge, not a widening conversion. Only the "implicit" * widening within a category, e.g. byte to short, is allowed. * * Dalvik does not draw a distinction between int and float, but we enforce @@ -357,11 +399,11 @@ class DexVerifier { * versa. We do not allow free exchange between 32-bit int/float and 64-bit * long/double. * - * Note that Uninit+Uninit=Uninit. This holds true because we only + * Note that Uninit+Uninit=Uninit. This holds true because we only * use this when the RegType value is exactly equal to kRegTypeUninit, which * can only happen for the zeroeth entry in the table. * - * "Unknown" never merges with anything known. The only time a register + * "Unknown" never merges with anything known. The only time a register * transitions from "unknown" to "known" is when we're executing code * for the first time, and we handle that with a simple copy. */ @@ -510,7 +552,7 @@ class DexVerifier { * (3) Iterate through the method, checking type safety and looking * for code flow problems. * - * Some checks may be bypassed depending on the verification mode. We can't + * Some checks may be bypassed depending on the verification mode. We can't * turn this stuff off completely if we want to do "exact" GC. * * Confirmed here: @@ -571,7 +613,7 @@ class DexVerifier { /* * Compute the width of the instruction at each address in the instruction - * stream, and store it in vdata->insn_flags. Addresses that are in the + * stream, and store it in vdata->insn_flags. Addresses that are in the * middle of an instruction, or that are part of switch table data, are not * touched (so the caller should probably initialize "insn_flags" to zero). * @@ -609,14 +651,14 @@ class DexVerifier { bool* pConditional, bool* selfOkay); /* - * Verify an array data table. "cur_offset" is the offset of the + * Verify an array data table. "cur_offset" is the offset of the * fill-array-data instruction. */ static bool CheckArrayData(const DexFile::CodeItem* code_item, uint32_t cur_offset); /* - * Perform static checks on a "new-instance" instruction. Specifically, + * Perform static checks on a "new-instance" instruction. Specifically, * make sure the class reference isn't for an array class. * * We don't need the actual class, just a pointer to the class name. @@ -624,7 +666,7 @@ class DexVerifier { static bool CheckNewInstance(const DexFile* dex_file, uint32_t idx); /* - * Perform static checks on a "new-array" instruction. Specifically, make + * Perform static checks on a "new-array" instruction. Specifically, make * sure they aren't creating an array of arrays that causes the number of * dimensions to exceed 255. */ @@ -637,13 +679,13 @@ class DexVerifier { static bool CheckTypeIndex(const DexFile* dex_file, uint32_t idx); /* - * Perform static checks on a field get or set instruction. All we do + * Perform static checks on a field get or set instruction. All we do * here is ensure that the field index is in the valid range. */ static bool CheckFieldIndex(const DexFile* dex_file, uint32_t idx); /* - * Perform static checks on a method invocation instruction. All we do + * Perform static checks on a method invocation instruction. All we do * here is ensure that the method index is in the valid range. */ static bool CheckMethodIndex(const DexFile* dex_file, uint32_t idx); @@ -667,7 +709,7 @@ class DexVerifier { * * There are some tests we don't do here, e.g. we don't try to verify * that invoking a method that takes a double is done with consecutive - * registers. This requires parsing the target method signature, which + * registers. This requires parsing the target method signature, which * we will be doing later on during the code flow analysis. */ static bool CheckVarArgRegs(const DexFile::CodeItem* code_item, uint32_t vA, @@ -696,7 +738,7 @@ class DexVerifier { * * We don't expect code to jump directly into an exception handler, but * it's valid to do so as long as the target isn't a "move-exception" - * instruction. We verify that in a later stage. + * instruction. We verify that in a later stage. * * The dex format forbids certain instructions from branching to itself. * @@ -762,7 +804,7 @@ class DexVerifier { #ifndef NDEBUG /* - * Compare two register lines. Returns 0 if they match. + * Compare two register lines. Returns 0 if they match. * * Using this for a sort is unwise, since the value can change based on * machine endianness. @@ -801,11 +843,11 @@ class DexVerifier { /* * Create a new uninitialized instance map. * - * The map is allocated and populated with address entries. The addresses + * The map is allocated and populated with address entries. The addresses * appear in ascending order to allow binary searching. * * Very few methods have 10 or more new-instance instructions; the - * majority have 0 or 1. Occasionally a static initializer will have 200+. + * majority have 0 or 1. Occasionally a static initializer will have 200+. * * TODO: merge this into the static pass or initRegisterTable; want to * avoid walking through the instructions yet again just to set up this table @@ -824,7 +866,7 @@ class DexVerifier { const char* descriptor, VerifyError* failure); /* - * Look up a class reference in a signature. Could be an arg or the + * Look up a class reference in a signature. Could be an arg or the * return value. * * Advances "*sig" to the last character in the signature (that is, to @@ -836,7 +878,7 @@ class DexVerifier { VerifyError* failure); /* - * Look up an array class reference in a signature. Could be an arg or the + * Look up an array class reference in a signature. Could be an arg or the * return value. * * Advances "*sig" to the last character in the signature. @@ -896,14 +938,14 @@ class DexVerifier { * because it's easier to do them here.) * * We need an array of RegType values, one per register, for every - * instruction. If the method uses monitor-enter, we need extra data + * instruction. If the method uses monitor-enter, we need extra data * for every register, and a stack for every "interesting" instruction. * In theory this could become quite large -- up to several megabytes for * a monster function. * * NOTE: * The spec forbids backward branches when there's an uninitialized reference - * in a register. The idea is to prevent something like this: + * in a register. The idea is to prevent something like this: * loop: * move r1, r0 * new-instance r0, MyClass @@ -912,9 +954,9 @@ class DexVerifier { * initialize r0 * * This leaves us with two different instances, both allocated by the - * same instruction, but only one is initialized. The scheme outlined in + * same instruction, but only one is initialized. The scheme outlined in * v3 4.11.1.4 wouldn't catch this, so they work around it by preventing - * backward branches. We achieve identical results without restricting + * backward branches. We achieve identical results without restricting * code reordering by specifying that you can't execute the new-instance * instruction if a register contains an uninitialized instance created * by that same instrutcion. @@ -929,24 +971,24 @@ class DexVerifier { * it has on registers. * * Finds zero or more following instructions and sets the "changed" flag - * if execution at that point needs to be (re-)evaluated. Register changes - * are merged into "reg_types_" at the target addresses. Does not set or + * if execution at that point needs to be (re-)evaluated. Register changes + * are merged into "reg_types_" at the target addresses. Does not set or * clear any other flags in "insn_flags". */ static bool CodeFlowVerifyInstruction(VerifierData* vdata, RegisterTable* reg_table, uint32_t insn_idx, size_t* start_guess); /* - * Replace an instruction with "throw-verification-error". This allows us to + * Replace an instruction with "throw-verification-error". This allows us to * defer error reporting until the code path is first used. * * This is expected to be called during "just in time" verification, not - * from within dexopt. (Verification failures in dexopt will result in + * from within dexopt. (Verification failures in dexopt will result in * postponement of verification to first use of the class.) * - * The throw-verification-error instruction requires two code units. Some + * The throw-verification-error instruction requires two code units. Some * of the replaced instructions require three; the third code unit will - * receive a "nop". The instruction's length will be left unchanged + * receive a "nop". The instruction's length will be left unchanged * in "insn_flags". * * The VM postpones setting of debugger breakpoints in unverified classes, @@ -967,15 +1009,15 @@ class DexVerifier { /* * Look up an instance field, specified by "field_idx", that is going to be - * accessed in object "obj_type". This resolves the field and then verifies + * accessed in object "obj_type". This resolves the field and then verifies * that the class containing the field is an instance of the reference in * "obj_type". * * It is possible for "obj_type" to be kRegTypeZero, meaning that we might - * have a null reference. This is a runtime problem, so we allow it, + * have a null reference. This is a runtime problem, so we allow it, * skipping some of the type checks. * - * In general, "obj_type" must be an initialized reference. However, we + * In general, "obj_type" must be an initialized reference. However, we * allow it to be uninitialized if this is an "<init>" method and the field * is declared within the "obj_type" class. * @@ -995,7 +1037,7 @@ class DexVerifier { /* * For the "move-exception" instruction at "insn_idx", which must be at an * exception handler address, determine the first common superclass of - * all exceptions that can land here. (For javac output, we're probably + * all exceptions that can land here. (For javac output, we're probably * looking at multiple spans of bytecode covered by one "try" that lands * at an exception-specific "catch", but in general the handler could be * shared for multiple exceptions.) @@ -1018,7 +1060,7 @@ class DexVerifier { } /* - * Return the register type for the method. We can't just use the + * Return the register type for the method. We can't just use the * already-computed DalvikJniReturnType, because if it's a reference type * we need to do the class lookup. * @@ -1030,7 +1072,7 @@ class DexVerifier { const Method* method); /* - * Get the value from a register, and cast it to a Class. Sets + * Get the value from a register, and cast it to a Class. Sets * "*failure" if something fails. * * This fails if the register holds an uninitialized class. @@ -1041,20 +1083,20 @@ class DexVerifier { uint32_t vsrc, VerifyError* failure); /* - * Get the "this" pointer from a non-static method invocation. This + * Get the "this" pointer from a non-static method invocation. This * returns the RegType so the caller can decide whether it needs the - * reference to be initialized or not. (Can also return kRegTypeZero + * reference to be initialized or not. (Can also return kRegTypeZero * if the reference can only be zero at this point.) * * The argument count is in vA, and the first argument is in vC, for both - * "simple" and "range" versions. We just need to make sure vA is >= 1 + * "simple" and "range" versions. We just need to make sure vA is >= 1 * and then return vC. */ static RegType GetInvocationThis(const RegisterLine* register_line, const Instruction::DecodedInstruction* dec_insn, VerifyError* failure); /* - * Set the type of register N, verifying that the register is valid. If + * Set the type of register N, verifying that the register is valid. If * "new_type" is the "Lo" part of a 64-bit value, register N+1 will be * set to "new_type+1". * @@ -1074,7 +1116,7 @@ class DexVerifier { * derived from a constant to prevent mixing of int/float and long/double. * * If "vsrc" is a reference, both it and the "vsrc" register must be - * initialized ("vsrc" may be Zero). This will verify that the value in + * initialized ("vsrc" may be Zero). This will verify that the value in * the register is an instance of check_type, or if check_type is an * interface, verify that the register implements check_type. */ @@ -1087,7 +1129,7 @@ class DexVerifier { /* * Update all registers holding "uninit_type" to instead hold the - * corresponding initialized reference type. This is called when an + * corresponding initialized reference type. This is called when an * appropriate <init> method is invoked -- all copies of the reference * must be marked as initialized. */ @@ -1096,21 +1138,21 @@ class DexVerifier { VerifyError* failure); /* - * Implement category-1 "move" instructions. Copy a 32-bit value from + * Implement category-1 "move" instructions. Copy a 32-bit value from * "vsrc" to "vdst". */ static void CopyRegister1(RegisterLine* register_line, uint32_t vdst, uint32_t vsrc, TypeCategory cat, VerifyError* failure); /* - * Implement category-2 "move" instructions. Copy a 64-bit value from - * "vsrc" to "vdst". This copies both halves of the register. + * Implement category-2 "move" instructions. Copy a 64-bit value from + * "vsrc" to "vdst". This copies both halves of the register. */ static void CopyRegister2(RegisterLine* register_line, uint32_t vdst, uint32_t vsrc, VerifyError* failure); /* - * Implement "move-result". Copy the category-1 value from the result + * Implement "move-result". Copy the category-1 value from the result * register to another register, and reset the result register. */ static void CopyResultRegister1(RegisterLine* register_line, @@ -1118,22 +1160,22 @@ class DexVerifier { VerifyError* failure); /* - * Implement "move-result-wide". Copy the category-2 value from the result + * Implement "move-result-wide". Copy the category-2 value from the result * register to another register, and reset the result register. */ static void CopyResultRegister2(RegisterLine* register_line, const int insn_reg_count, uint32_t vdst, VerifyError* failure); /* - * Compute the "class depth" of a class. This is the distance from the - * class to the top of the tree, chasing superclass links. java.lang.Object + * Compute the "class depth" of a class. This is the distance from the + * class to the top of the tree, chasing superclass links. java.lang.Object * has a class depth of 0. */ static int GetClassDepth(Class* klass); /* * Given two classes, walk up the superclass tree to find a common - * ancestor. (Called from findCommonSuperclass().) + * ancestor. (Called from findCommonSuperclass().) * * TODO: consider caching the class depth in the class object so we don't * have to search for it here. @@ -1141,9 +1183,9 @@ class DexVerifier { static Class* DigForSuperclass(Class* c1, Class* c2); /* - * Merge two array classes. We can't use the general "walk up to the + * Merge two array classes. We can't use the general "walk up to the * superclass" merge because the superclass of an array is always Object. - * We want String[] + Integer[] = Object[]. This works for higher dimensions + * We want String[] + Integer[] = Object[]. This works for higher dimensions * as well, e.g. String[][] + Integer[][] = Object[][]. * * If Foo1 and Foo2 are subclasses of Foo, Foo1[] + Foo2[] = Foo[]. @@ -1154,19 +1196,19 @@ class DexVerifier { * with the least dimension, e.g. String[][] + String[][][][] = Object[][]. * * Arrays of primitive types effectively have one less dimension when - * merging. int[] + float[] = Object, int[] + String[] = Object, - * int[][] + float[][] = Object[], int[][] + String[] = Object[]. (The + * merging. int[] + float[] = Object, int[] + String[] = Object, + * int[][] + float[][] = Object[], int[][] + String[] = Object[]. (The * only time this function doesn't return an array class is when one of * the arguments is a 1-dimensional primitive array.) * * This gets a little awkward because we may have to ask the VM to create - * a new array type with the appropriate element and dimensions. However, we + * a new array type with the appropriate element and dimensions. However, we * shouldn't be doing this often. */ static Class* FindCommonArraySuperclass(Class* c1, Class* c2); /* - * Find the first common superclass of the two classes. We're not + * Find the first common superclass of the two classes. We're not * interested in common interfaces. * * The easiest way to do this for concrete classes is to compute the "class @@ -1177,21 +1219,21 @@ class DexVerifier { * element type. * * If one class is an interface, we check to see if the other class/interface - * (or one of its predecessors) implements the interface. If so, we return + * (or one of its predecessors) implements the interface. If so, we return * the interface; otherwise, we return Object. * - * NOTE: we continue the tradition of "lazy interface handling". To wit, + * NOTE: we continue the tradition of "lazy interface handling". To wit, * suppose we have three classes: * One implements Fancy, Free * Two implements Fancy, Free * Three implements Free - * where Fancy and Free are unrelated interfaces. The code requires us - * to merge One into Two. Ideally we'd use a common interface, which + * where Fancy and Free are unrelated interfaces. The code requires us + * to merge One into Two. Ideally we'd use a common interface, which * gives us a choice between Fancy and Free, and no guidance on which to - * use. If we use Free, we'll be okay when Three gets merged in, but if - * we choose Fancy, we're hosed. The "ideal" solution is to create a + * use. If we use Free, we'll be okay when Three gets merged in, but if + * we choose Fancy, we're hosed. The "ideal" solution is to create a * set of common interfaces and carry that around, merging further references - * into it. This is a pain. The easy solution is to simply boil them + * into it. This is a pain. The easy solution is to simply boil them * down to Objects and let the runtime invokeinterface call fail, which * is what we do. */ @@ -1216,9 +1258,9 @@ class DexVerifier { MonitorEntries ents2, bool* changed); /* - * We're creating a new instance of class C at address A. Any registers + * We're creating a new instance of class C at address A. Any registers * holding instances previously created at address A must be initialized - * by now. If not, we mark them as "conflict" to prevent them from being + * by now. If not, we mark them as "conflict" to prevent them from being * used (otherwise, MarkRefsAsInitialized would mark the old ones and the * new ones at the same time). */ @@ -1284,11 +1326,11 @@ class DexVerifier { VerifyError* failure); /* - * Check constraints on constructor return. Specifically, make sure that + * Check constraints on constructor return. Specifically, make sure that * the "this" argument got initialized. * * The "this" argument to <init> uses code offset kUninitThisArgAddr, which - * puts it at the start of the list in slot 0. If we see a register with + * puts it at the start of the list in slot 0. If we see a register with * an uninitialized slot 0 reference, we know it somehow didn't get * initialized. * @@ -1298,7 +1340,7 @@ class DexVerifier { const RegisterLine* register_line, const int insn_reg_count); /* - * Verify that the target instruction is not "move-exception". It's important + * Verify that the target instruction is not "move-exception". It's important * that the only way to execute a move-exception is as the first instruction * of an exception handler. * @@ -1308,11 +1350,11 @@ class DexVerifier { static bool CheckMoveException(const uint16_t* insns, int insn_idx); /* - * See if "type" matches "cat". All we're really looking for here is that + * See if "type" matches "cat". All we're really looking for here is that * we're not mixing and matching 32-bit and 64-bit quantities, and we're - * not mixing references with numerics. (For example, the arguments to + * not mixing references with numerics. (For example, the arguments to * "a < b" could be integers of different sizes, but they must both be - * integers. Dalvik is less specific about int vs. float, so we treat them + * integers. Dalvik is less specific about int vs. float, so we treat them * as equivalent here.) * * For category 2 values, "type" must be the "low" half of the value. @@ -1351,7 +1393,7 @@ class DexVerifier { VerifyError* failure); /* - * Verify types for a binary "2addr" operation. "src_type1"/"src_type2" + * Verify types for a binary "2addr" operation. "src_type1"/"src_type2" * are verified against vA/vB, then "dst_type" is stored into vA. */ static void CheckBinop2addr(RegisterLine* register_line, @@ -1365,26 +1407,26 @@ class DexVerifier { * For example, right-shifting an int 24 times results in a value that can * be treated as a byte. * - * Things get interesting when contemplating sign extension. Right- + * Things get interesting when contemplating sign extension. Right- * shifting an integer by 16 yields a value that can be represented in a * "short" but not a "char", but an unsigned right shift by 16 yields a - * value that belongs in a char rather than a short. (Consider what would + * value that belongs in a char rather than a short. (Consider what would * happen if the result of the shift were cast to a char or short and then - * cast back to an int. If sign extension, or the lack thereof, causes + * cast back to an int. If sign extension, or the lack thereof, causes * a change in the 32-bit representation, then the conversion was lossy.) * - * A signed right shift by 17 on an integer results in a short. An unsigned + * A signed right shift by 17 on an integer results in a short. An unsigned * right shfit by 17 on an integer results in a posshort, which can be * assigned to a short or a char. * * An unsigned right shift on a short can actually expand the result into - * a 32-bit integer. For example, 0xfffff123 >>> 8 becomes 0x00fffff1, + * a 32-bit integer. For example, 0xfffff123 >>> 8 becomes 0x00fffff1, * which can't be represented in anything smaller than an int. * * javac does not generate code that takes advantage of this, but some - * of the code optimizers do. It's generally a peephole optimization + * of the code optimizers do. It's generally a peephole optimization * that replaces a particular sequence, e.g. (bipush 24, ishr, i2b) is - * replaced by (bipush 24, ishr). Knowing that shifting a short 8 times + * replaced by (bipush 24, ishr). Knowing that shifting a short 8 times * to the right yields a byte is really more than we need to handle the * code that's out there, but support is not much more complex than just * handling integer. @@ -1398,16 +1440,16 @@ class DexVerifier { /* * We're performing an operation like "and-int/2addr" that can be - * performed on booleans as well as integers. We get no indication of + * performed on booleans as well as integers. We get no indication of * boolean-ness, but we can infer it from the types of the arguments. * * Assumes we've already validated reg1/reg2. * - * TODO: consider generalizing this. The key principle is that the + * TODO: consider generalizing this. The key principle is that the * result of a bitwise operation can only be as wide as the widest of - * the operands. You can safely AND/OR/XOR two chars together and know + * the operands. You can safely AND/OR/XOR two chars together and know * you still have a char, so it's reasonable for the compiler or "dx" - * to skip the int-to-char instruction. (We need to do this for boolean + * to skip the int-to-char instruction. (We need to do this for boolean * because there is no int-to-boolean operation.) * * Returns true if both args are Boolean, Zero, or One. @@ -1417,7 +1459,7 @@ class DexVerifier { /* * Verify types for A two-register instruction with a literal constant - * (e.g. "add-int/lit8"). "dst_type" is stored into vA, and "src_type" is + * (e.g. "add-int/lit8"). "dst_type" is stored into vA, and "src_type" is * verified against vB. * * If "check_boolean_op" is set, we use the constant value in vC. @@ -1440,18 +1482,18 @@ class DexVerifier { static bool IsCorrectInvokeKind(MethodType method_type, Method* res_method); /* - * Verify the arguments to a method. We're executing in "method", making + * Verify the arguments to a method. We're executing in "method", making * a call to the method reference in vB. * - * If this is a "direct" invoke, we allow calls to <init>. For calls to - * <init>, the first argument may be an uninitialized reference. Otherwise, + * If this is a "direct" invoke, we allow calls to <init>. For calls to + * <init>, the first argument may be an uninitialized reference. Otherwise, * calls to anything starting with '<' will be rejected, as will any * uninitialized reference arguments. * * For non-static method calls, this will verify that the method call is * appropriate for the "this" argument. * - * The method reference is in vBBBB. The "is_range" parameter determines + * The method reference is in vBBBB. The "is_range" parameter determines * whether we use 0-4 "args" values or a range of registers defined by * vAA and vCCCC. * @@ -1466,6 +1508,95 @@ class DexVerifier { const Instruction::DecodedInstruction* dec_insn, MethodType method_type, bool is_range, bool is_super, VerifyError* failure); + /* + * Generate the register map for a method that has just been verified + * (i.e. we're doing this as part of verification). + * + * For type-precise determination we have all the data we need, so we + * just need to encode it in some clever fashion. + * + * Returns a pointer to a newly-allocated RegisterMap, or NULL on failure. + */ + static RegisterMap* GenerateRegisterMapV(VerifierData* vdata); + + /* + * Determine if the RegType value is a reference type. + * + * Ordinarily we include kRegTypeZero in the "is it a reference" + * check. There's no value in doing so here, because we know + * the register can't hold anything but zero. + */ + static inline bool IsReferenceType(RegType type) { + return (type > kRegTypeMAX || type == kRegTypeUninit); + } + + /* Toggle the value of the "idx"th bit in "ptr". */ + static inline void ToggleBit(uint8_t* ptr, int idx) { + ptr[idx >> 3] ^= 1 << (idx & 0x07); + } + + /* + * Given a line of registers, output a bit vector that indicates whether + * or not the register holds a reference type (which could be null). + * + * We use '1' to indicate it's a reference, '0' for anything else (numeric + * value, uninitialized data, merge conflict). Register 0 will be found + * in the low bit of the first byte. + */ + static void OutputTypeVector(const RegType* regs, int insn_reg_count, + uint8_t* data); + + /* + * Double-check the map. + * + * We run through all of the data in the map, and compare it to the original. + * Only works on uncompressed data. + */ + static bool VerifyMap(VerifierData* vdata, const RegisterMap* map); + + /* Compare two register maps. Returns true if they're equal, false if not. */ + static bool CompareMaps(const RegisterMap* map1, const RegisterMap* map2); + + /* Compute the size, in bytes, of a register map. */ + static size_t ComputeRegisterMapSize(const RegisterMap* map); + + /* + * Compute the difference between two bit vectors. + * + * If "leb_out_buf" is non-NULL, we output the bit indices in ULEB128 format + * as we go. Otherwise, we just generate the various counts. + * + * The bit vectors are compared byte-by-byte, so any unused bits at the + * end must be zero. + * + * Returns the number of bytes required to hold the ULEB128 output. + * + * If "first_bit_changed_ptr" or "num_bits_changed_ptr" are non-NULL, they + * will receive the index of the first changed bit and the number of changed + * bits, respectively. + */ + static int ComputeBitDiff(const uint8_t* bits1, const uint8_t* bits2, + int byte_width, int* first_bit_changed_ptr, int* num_bits_changed_ptr, + uint8_t* leb_out_buf); + + /* + * Compress the register map with differential encoding. + * + * On success, returns a newly-allocated RegisterMap. If the map is not + * compatible for some reason, or fails to get smaller, this will return NULL. + */ + static RegisterMap* CompressMapDifferential(const RegisterMap* map); + + /* + * Expand a compressed map to an uncompressed form. + * + * Returns a newly-allocated RegisterMap on success, or NULL on failure. + * + * TODO: consider using the linear allocator or a custom allocator with + * LRU replacement for these instead of the native heap. + */ + static RegisterMap* UncompressMapDifferential(const RegisterMap* map); + DISALLOW_COPY_AND_ASSIGN(DexVerifier); }; diff --git a/src/leb128.h b/src/leb128.h index bc5dd1a61a..ad551990bf 100644 --- a/src/leb128.h +++ b/src/leb128.h @@ -79,6 +79,32 @@ static inline int32_t DecodeSignedLeb128(const byte** data) { return result; } +// Returns the number of bytes needed to encode the value in unsigned LEB128. +static inline uint32_t UnsignedLeb128Size(uint32_t data) { + uint32_t count = 0; + do { + data >>= 7; + count++; + } while (data != 0); + return count; +} + +// Writes a 32-bit value in unsigned ULEB128 format. +// Returns the updated pointer. +static inline uint8_t* WriteUnsignedLeb128(uint8_t* ptr, uint32_t data) { + while (true) { + uint8_t out = data & 0x7f; + if (out != data) { + *ptr++ = out | 0x80; + data >>= 7; + } else { + *ptr++ = out; + break; + } + } + return ptr; +} + } // namespace art #endif // ART_SRC_LEB128_H_ |