Check monitors during bytecode verification
This adds tracking of monitor-enter and monitor-exit instructions
to the bytecode verifier. The idea is to guarantee that all lock
operations in a method are paired with unlock operations, whether
the method completes normally or abnormally.
Because of an issue in "dx", the code only verifies that the operation
stack has the right size at all times. We do not yet confirm that
the correct monitor is being unlocked by monitor-exit (the code is
present but ifdefed out). Also, when monitor verification is enabled,
we do not add the "can throw" path from monitor-exit to the work list,
potentially causing some "dead code" warnings. (Not coincidentally,
"dead code" checking is now only enabled in libdvm_assert.so.)
Overall increase in bootstrap verification time is about 9%, dropping
to 6% when the new checks are disabled.
The feature is currently disabled by default. -Xverifyopt:checkmon
enables it.
Bug 2534655
Change-Id: I0eac54ce2623fb1d48cc80889fcdb4fd69de3231
diff --git a/docs/verifier.html b/docs/verifier.html
index 21bbdf0..4c1f2e6 100644
--- a/docs/verifier.html
+++ b/docs/verifier.html
@@ -100,6 +100,38 @@
[-128, 127] to a function that takes a <code>byte</code> as an argument.
+<h2>Monitor Verification</h2>
+
+<p>
+If a method locks an object with a <code>synchronized</code> statement, the
+object must be unlocked before the method returns. At the bytecode level,
+this means the method must execute a matching <code>monitor-exit</code>
+for every <code>monitor-enter</code> instruction, whether the function
+completes normally or abnormally. The bytecode verifier optionally
+enforces this.
+
+<p>
+The verifier uses a fairly simple-minded model. If you enter a monitor
+held in register N, you can exit the monitor using register N or any
+subsequently-made copies of register N. The verifier does not attempt
+to identify previously-made copies, track loads and stores through
+fields, or recognize identical constant values (e.g. the result of two
+<code>const-class</code> instructions on the same class will always result
+in the same reference).
+
+<p>
+This means that there are a number of situations in which the verifier
+will throw an exception on code that would execute correctly at run time.
+This is not expected to be an issue for compiler-generated bytecode.
+
+<p>
+For implementation convenience, the maximum nesting depth of
+<code>synchronized</code> statements has been set to 32. This is not
+a limitation on the recursion count. The only way to trip this would be
+to have a single method with more than 32 nested <code>synchronized</code>
+statements, something that is unlikely to occur.
+
+
<h2>Verification Failures</h2>
<p>
diff --git a/tests/088-monitor-verification/expected.txt b/tests/088-monitor-verification/expected.txt
new file mode 100644
index 0000000..07f5b0b
--- /dev/null
+++ b/tests/088-monitor-verification/expected.txt
@@ -0,0 +1,7 @@
+recursiveSync ok
+nestedMayThrow ok
+constantLock ok
+excessiveNesting ok
+notNested ok
+twoPath ok
+triplet ok
diff --git a/tests/088-monitor-verification/info.txt b/tests/088-monitor-verification/info.txt
new file mode 100644
index 0000000..c00cb1c
--- /dev/null
+++ b/tests/088-monitor-verification/info.txt
@@ -0,0 +1,2 @@
+Try different arrangements of "synchronized" to exercise the structured
+lock checks in the bytecode verifier.
diff --git a/tests/088-monitor-verification/src/Main.java b/tests/088-monitor-verification/src/Main.java
new file mode 100644
index 0000000..aa90b92
--- /dev/null
+++ b/tests/088-monitor-verification/src/Main.java
@@ -0,0 +1,221 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+/*
+ * Entry point and tests that are expected to succeed.
+ */
+public class Main {
+ /**
+ * Drives tests.
+ */
+ public static void main(String[] args) {
+ Main m = new Main();
+
+ m.recursiveSync(0);
+
+ m.nestedMayThrow(false);
+ try {
+ m.nestedMayThrow(true);
+ System.err.println("nestedThrow(true) did not throw");
+ } catch (MyException me) {}
+ System.out.println("nestedMayThrow ok");
+
+ m.constantLock();
+ System.out.println("constantLock ok");
+
+ m.notExcessiveNesting();
+ if (false) { // TODO: remove when verification is turned on
+ try {
+ TooDeep.excessiveNesting();
+ System.err.println("excessiveNesting did not throw");
+ } catch (VerifyError ve) {}
+ }
+ System.out.println("excessiveNesting ok");
+
+ m.notNested();
+ System.out.println("notNested ok");
+
+ Object obj1 = new Object();
+ Object obj2 = new Object();
+
+ m.twoPath(obj1, obj2, 0);
+ System.out.println("twoPath ok");
+
+ m.triplet(obj1, obj2, 0);
+ System.out.println("triplet ok");
+ }
+
+ /**
+ * Recursive synchronized method.
+ */
+ synchronized void recursiveSync(int iter) {
+ if (iter < 40) {
+ recursiveSync(iter+1);
+ } else {
+ System.out.println("recursiveSync ok");
+ }
+ }
+
+ /**
+ * Tests simple nesting, with and without a throw.
+ */
+ void nestedMayThrow(boolean doThrow) {
+ synchronized (this) {
+ synchronized (Main.class) {
+ synchronized (new Object()) {
+ synchronized(Class.class) {
+ if (doThrow) {
+ throw new MyException();
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Exercises bug 3215458.
+ */
+ void constantLock() {
+ Class thing = Thread.class;
+ synchronized (Thread.class) {}
+ }
+
+ /**
+ * Confirms that we can have 32 nested monitors on one method.
+ */
+ void notExcessiveNesting() {
+ synchronized (this) { // 1
+ synchronized (this) { // 2
+ synchronized (this) { // 3
+ synchronized (this) { // 4
+ synchronized (this) { // 5
+ synchronized (this) { // 6
+ synchronized (this) { // 7
+ synchronized (this) { // 8
+ synchronized (this) { // 9
+ synchronized (this) { // 10
+ synchronized (this) { // 11
+ synchronized (this) { // 12
+ synchronized (this) { // 13
+ synchronized (this) { // 14
+ synchronized (this) { // 15
+ synchronized (this) { // 16
+ synchronized (this) { // 17
+ synchronized (this) { // 18
+ synchronized (this) { // 19
+ synchronized (this) { // 20
+ synchronized (this) { // 21
+ synchronized (this) { // 22
+ synchronized (this) { // 23
+ synchronized (this) { // 24
+ synchronized (this) { // 25
+ synchronized (this) { // 26
+ synchronized (this) { // 27
+ synchronized (this) { // 28
+ synchronized (this) { // 29
+ synchronized (this) { // 30
+ synchronized (this) { // 31
+ synchronized (this) { // 32
+ }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
+ }
+
+ /**
+ * Confirms that we can have more than 32 non-nested monitors in one
+ * method.
+ */
+ void notNested() {
+ synchronized (this) {} // 1
+ synchronized (this) {} // 2
+ synchronized (this) {} // 3
+ synchronized (this) {} // 4
+ synchronized (this) {} // 5
+ synchronized (this) {} // 6
+ synchronized (this) {} // 7
+ synchronized (this) {} // 8
+ synchronized (this) {} // 9
+ synchronized (this) {} // 10
+ synchronized (this) {} // 11
+ synchronized (this) {} // 12
+ synchronized (this) {} // 13
+ synchronized (this) {} // 14
+ synchronized (this) {} // 15
+ synchronized (this) {} // 16
+ synchronized (this) {} // 17
+ synchronized (this) {} // 18
+ synchronized (this) {} // 19
+ synchronized (this) {} // 20
+ synchronized (this) {} // 21
+ synchronized (this) {} // 22
+ synchronized (this) {} // 23
+ synchronized (this) {} // 24
+ synchronized (this) {} // 25
+ synchronized (this) {} // 26
+ synchronized (this) {} // 27
+ synchronized (this) {} // 28
+ synchronized (this) {} // 29
+ synchronized (this) {} // 30
+ synchronized (this) {} // 31
+ synchronized (this) {} // 32
+ synchronized (this) {} // 33
+ synchronized (this) {} // 34
+ }
+
+ /* does nothing but ensure that the compiler doesn't discard an object */
+ private void doNothing(Object obj) {}
+
+ /**
+ * Conditionally uses one of the synchronized objects.
+ */
+ public void twoPath(Object obj1, Object obj2, int x) {
+ Object localObj;
+
+ synchronized (obj1) {
+ synchronized(obj2) {
+ if (x == 0) {
+ localObj = obj2;
+ } else {
+ localObj = obj1;
+ }
+ }
+ }
+
+ doNothing(localObj);
+ }
+
+ /**
+ * Lock the monitor two or three times, and make use of the locked or
+ * unlocked object.
+ */
+ public void triplet(Object obj1, Object obj2, int x) {
+ Object localObj;
+
+ synchronized (obj1) {
+ synchronized(obj1) {
+ if (x == 0) {
+ synchronized(obj1) {
+ localObj = obj2;
+ }
+ } else {
+ localObj = obj1;
+ }
+ }
+ }
+
+ doNothing(localObj);
+ }
+}
diff --git a/tests/088-monitor-verification/src/MyException.java b/tests/088-monitor-verification/src/MyException.java
new file mode 100644
index 0000000..cf65d6d
--- /dev/null
+++ b/tests/088-monitor-verification/src/MyException.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class MyException extends RuntimeException {
+ public MyException() {
+ super();
+ }
+ public MyException(String msg) {
+ super(msg);
+ }
+}
diff --git a/tests/088-monitor-verification/src/TooDeep.java b/tests/088-monitor-verification/src/TooDeep.java
new file mode 100644
index 0000000..76192e5
--- /dev/null
+++ b/tests/088-monitor-verification/src/TooDeep.java
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+/**
+ * The class has a method with too many levels of nested "synchronized"
+ * blocks. The verifier will reject it.
+ *
+ * (It would be perfectly okay if the verifier *didn't* reject this.
+ * The goal here is just to exercise the failure path. It also serves
+ * as a check to see if the monitor checks are enabled.)
+ */
+public class TooDeep {
+
+ public static void excessiveNesting() {
+ synchronized (TooDeep.class) { // 1
+ synchronized (TooDeep.class) { // 2
+ synchronized (TooDeep.class) { // 3
+ synchronized (TooDeep.class) { // 4
+ synchronized (TooDeep.class) { // 5
+ synchronized (TooDeep.class) { // 6
+ synchronized (TooDeep.class) { // 7
+ synchronized (TooDeep.class) { // 8
+ synchronized (TooDeep.class) { // 9
+ synchronized (TooDeep.class) { // 10
+ synchronized (TooDeep.class) { // 11
+ synchronized (TooDeep.class) { // 12
+ synchronized (TooDeep.class) { // 13
+ synchronized (TooDeep.class) { // 14
+ synchronized (TooDeep.class) { // 15
+ synchronized (TooDeep.class) { // 16
+ synchronized (TooDeep.class) { // 17
+ synchronized (TooDeep.class) { // 18
+ synchronized (TooDeep.class) { // 19
+ synchronized (TooDeep.class) { // 20
+ synchronized (TooDeep.class) { // 21
+ synchronized (TooDeep.class) { // 22
+ synchronized (TooDeep.class) { // 23
+ synchronized (TooDeep.class) { // 24
+ synchronized (TooDeep.class) { // 25
+ synchronized (TooDeep.class) { // 26
+ synchronized (TooDeep.class) { // 27
+ synchronized (TooDeep.class) { // 28
+ synchronized (TooDeep.class) { // 29
+ synchronized (TooDeep.class) { // 30
+ synchronized (TooDeep.class) { // 31
+ synchronized (TooDeep.class) { // 32
+ synchronized (TooDeep.class) { // 33
+ }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
+ }
+}
diff --git a/vm/Globals.h b/vm/Globals.h
index f7d69c3..fe36673 100644
--- a/vm/Globals.h
+++ b/vm/Globals.h
@@ -118,6 +118,8 @@
DexOptimizerMode dexOptMode;
DexClassVerifyMode classVerifyMode;
+ bool monitorVerification;
+
bool dexOptForSmp;
/*
diff --git a/vm/Init.c b/vm/Init.c
index b9d3666..e1e7711 100644
--- a/vm/Init.c
+++ b/vm/Init.c
@@ -120,6 +120,7 @@
dvmFprintf(stderr, " -Xgc:[no]concurrent\n");
dvmFprintf(stderr, " -Xgc:[no]verifycardtable\n");
dvmFprintf(stderr, " -Xgenregmap\n");
+ dvmFprintf(stderr, " -Xverifyopt:[no]checkmon\n");
dvmFprintf(stderr, " -Xcheckdexsum\n");
#if defined(WITH_JIT)
dvmFprintf(stderr, " -Xincludeselectedop\n");
@@ -139,16 +140,16 @@
dvmFprintf(stderr, "Configured with:"
" debugger"
" profiler"
+ " hprof"
+#ifdef WITH_HPROF_STACK
+ " hprof_stack"
+#endif
#ifdef WITH_MONITOR_TRACKING
" monitor_tracking"
#endif
#ifdef WITH_DEADLOCK_PREDICTION
" deadlock_prediction"
#endif
- " hprof"
-#ifdef WITH_HPROF_STACK
- " hprof_stack"
-#endif
#ifdef WITH_TRACKREF_CHECKS
" trackref_checks"
#endif
@@ -984,6 +985,11 @@
gDvm.generateRegisterMaps = true;
LOGV("Register maps will be generated during verification\n");
+ } else if (strcmp(argv[i], "Xverifyopt:checkmon") == 0) {
+ gDvm.monitorVerification = true;
+ } else if (strcmp(argv[i], "Xverifyopt:nocheckmon") == 0) {
+ gDvm.monitorVerification = false;
+
} else if (strncmp(argv[i], "-Xgc:", 5) == 0) {
if (strcmp(argv[i] + 5, "precise") == 0)
gDvm.preciseGc = true;
@@ -1076,6 +1082,7 @@
/* default verification and optimization modes */
gDvm.classVerifyMode = VERIFY_MODE_ALL;
gDvm.dexOptMode = OPTIMIZE_MODE_VERIFIED;
+ gDvm.monitorVerification = false;
/*
* Default execution mode.
diff --git a/vm/analysis/CodeVerify.c b/vm/analysis/CodeVerify.c
index 6c30520..e1465b8 100644
--- a/vm/analysis/CodeVerify.c
+++ b/vm/analysis/CodeVerify.c
@@ -55,7 +55,11 @@
* The only reason not to do it is that it slightly increases the time
* required to perform verification.
*/
-#define DEAD_CODE_SCAN true
+#ifndef NDEBUG
+# define DEAD_CODE_SCAN true
+#else
+# define DEAD_CODE_SCAN false
+#endif
static bool gDebugVerbose = false; // TODO: remove this
@@ -73,9 +77,9 @@
static inline bool doVerboseLogging(const Method* meth) {
return false; /* COMMENT OUT to enable verbose debugging */
- const char* cd = "Landroid/net/http/Request;";
- const char* mn = "readResponse";
- const char* sg = "(Landroid/net/http/AndroidHttpClientConnection;)V";
+ const char* cd = "Lcom/android/bluetooth/opp/BluetoothOppService;";
+ const char* mn = "scanFile";
+ const char* sg = "(Landroid/database/Cursor;I)Z";
return (strcmp(meth->clazz->descriptor, cd) == 0 &&
dvmCompareNameDescriptorAndMethod(mn, sg, meth) == 0);
}
@@ -402,8 +406,8 @@
* Very few methods have 10 or more new-instance instructions; the
* majority have 0 or 1. Occasionally a static initializer will have 200+.
*
- * TODO: merge this into the static pass; want to avoid walking through
- * the instructions yet again just to set up this table
+ * TODO: merge this into the static pass or initRegisterTable; want to
+ * avoid walking through the instructions yet again just to set up this table
*/
UninitInstanceMap* dvmCreateUninitInstanceMap(const Method* meth,
const InsnFlags* insnFlags, int newInstanceCount)
@@ -481,6 +485,10 @@
assert(clazz != NULL);
+#ifdef VERIFIER_STATS
+ gDvm.verifierStats.uninitSearches++;
+#endif
+
/* TODO: binary search when numEntries > 8 */
for (idx = uninitMap->numEntries - 1; idx >= 0; idx--) {
if (uninitMap->map[idx].addr == addr) {
@@ -1542,6 +1550,12 @@
dvmAbort();
break;
}
+
+ /*
+ * Clear the monitor entry bits for this register.
+ */
+ if (registerLine->monitorEntries != NULL)
+ registerLine->monitorEntries[vdst] = 0;
}
/*
@@ -1713,8 +1727,6 @@
* 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).
- *
- * TODO: clear mon stack bits
*/
static void markUninitRefsAsInvalid(RegisterLine* registerLine,
int insnRegCount, UninitInstanceMap* uninitMap, RegType uninitType)
@@ -1726,6 +1738,8 @@
for (i = 0; i < insnRegCount; i++) {
if (insnRegs[i] == uninitType) {
insnRegs[i] = kRegTypeConflict;
+ if (registerLine->monitorEntries != NULL)
+ registerLine->monitorEntries[i] = 0;
changed++;
}
}
@@ -1759,6 +1773,7 @@
numRegs * sizeof(MonitorEntries));
memcpy(dst->monitorStack, src->monitorStack,
kMaxMonitorStackDepth * sizeof(u4));
+ dst->monitorStackTop = src->monitorStackTop;
}
}
@@ -1785,6 +1800,7 @@
}
+#ifndef NDEBUG
/*
* Compare two register lines. Returns 0 if they match.
*
@@ -1795,10 +1811,33 @@
int insnIdx, const RegisterLine* line2)
{
const RegisterLine* line1 = getRegisterLine(regTable, insnIdx);
- /* TODO: compare mon stack and stack bits */
+ if (line1->monitorEntries != NULL) {
+ int result;
+
+ if (line2->monitorEntries == NULL)
+ return 1;
+ result = memcmp(line1->monitorEntries, line2->monitorEntries,
+ regTable->insnRegCountPlus * sizeof(MonitorEntries));
+ if (result != 0) {
+ LOG_VFY("monitorEntries mismatch\n");
+ return result;
+ }
+ result = line1->monitorStackTop - line2->monitorStackTop;
+ if (result != 0) {
+ LOG_VFY("monitorStackTop mismatch\n");
+ return result;
+ }
+ result = memcmp(line1->monitorStack, line2->monitorStack,
+ line1->monitorStackTop);
+ if (result != 0) {
+ LOG_VFY("monitorStack mismatch\n");
+ return result;
+ }
+ }
return memcmp(line1->regTypes, line2->regTypes,
regTable->insnRegCountPlus * sizeof(RegType));
}
+#endif
/*
* Register type categories, for type checking.
@@ -1901,7 +1940,10 @@
LOG_VFY("VFY: copy1 v%u<-v%u type=%d cat=%d\n", vdst, vsrc, type, cat);
} else {
setRegisterType(registerLine, vdst, type);
- /* TODO copy mon stack bits for Ref; will be cleared for 1nr */
+ if (cat == kTypeCategoryRef && registerLine->monitorEntries != NULL) {
+ registerLine->monitorEntries[vdst] =
+ registerLine->monitorEntries[vsrc];
+ }
}
}
@@ -2474,13 +2516,32 @@
}
/*
+ * Merge the bits that indicate which monitor entry addresses on the stack
+ * are associated with this register.
+ *
+ * The merge is a simple bitwise AND.
+ *
+ * Sets "*pChanged" to "true" if the result doesn't match "ents1".
+ */
+static MonitorEntries mergeMonitorEntries(MonitorEntries ents1,
+ MonitorEntries ents2, bool* pChanged)
+{
+ MonitorEntries result = ents1 & ents2;
+ if (result != ents1)
+ *pChanged = true;
+ return result;
+}
+
+/*
* Control can transfer to "nextInsn".
*
* Merge the registers from "workLine" into "regTable" at "nextInsn", and
* set the "changed" flag on the target address if any of the registers
* has changed.
+ *
+ * Returns "false" if we detect mis-matched monitor stacks.
*/
-static void updateRegisters(const Method* meth, InsnFlags* insnFlags,
+static bool updateRegisters(const Method* meth, InsnFlags* insnFlags,
RegisterTable* regTable, int nextInsn, const RegisterLine* workLine)
{
const size_t insnRegCountPlus = regTable->insnRegCountPlus;
@@ -2510,16 +2571,41 @@
/* merge registers, set Changed only if different */
RegisterLine* targetLine = getRegisterLine(regTable, nextInsn);
RegType* targetRegs = targetLine->regTypes;
+ MonitorEntries* workMonEnts = workLine->monitorEntries;
+ MonitorEntries* targetMonEnts = targetLine->monitorEntries;
bool changed = false;
unsigned int idx;
assert(targetRegs != NULL);
- /* TODO: check mon stacks are the same; if different, fail somehow */
+ if (targetMonEnts != NULL) {
+ /*
+ * Monitor stacks must be identical.
+ */
+ if (targetLine->monitorStackTop != workLine->monitorStackTop) {
+ LOG_VFY_METH(meth,
+ "VFY: mismatched stack depth %d vs. %d at 0x%04x\n",
+ targetLine->monitorStackTop, workLine->monitorStackTop,
+ nextInsn);
+ return false;
+ }
+ if (memcmp(targetLine->monitorStack, workLine->monitorStack,
+ targetLine->monitorStackTop * sizeof(u4)) != 0)
+ {
+ LOG_VFY_METH(meth, "VFY: mismatched monitor stacks at 0x%04x\n",
+ nextInsn);
+ return false;
+ }
+ }
+
for (idx = 0; idx < insnRegCountPlus; idx++) {
targetRegs[idx] =
mergeTypes(targetRegs[idx], workRegs[idx], &changed);
- /* TODO merge monitorEntries */
+
+ if (targetMonEnts != NULL) {
+ targetMonEnts[idx] = mergeMonitorEntries(targetMonEnts[idx],
+ workMonEnts[idx], &changed);
+ }
}
if (gDebugVerbose) {
@@ -2535,6 +2621,8 @@
if (changed)
dvmInsnSetChanged(insnFlags, nextInsn, true);
}
+
+ return true;
}
@@ -2860,6 +2948,29 @@
}
/*
+ * Helper for initRegisterTable.
+ *
+ * Returns an updated copy of "storage".
+ */
+static u1* assignLineStorage(u1* storage, RegisterLine* line,
+ bool trackMonitors, size_t regTypeSize, size_t monEntSize, size_t stackSize)
+{
+ line->regTypes = (RegType*) storage;
+ storage += regTypeSize;
+
+ if (trackMonitors) {
+ line->monitorEntries = (MonitorEntries*) storage;
+ storage += monEntSize;
+ line->monitorStack = (u4*) storage;
+ storage += stackSize;
+
+ assert(line->monitorStackTop == 0);
+ }
+
+ return storage;
+}
+
+/*
* Initialize the RegisterTable.
*
* Every instruction address can have a different set of information about
@@ -2872,13 +2983,20 @@
* We jump through some hoops here to minimize the total number of
* allocations we have to perform per method verified.
*/
-static bool initRegisterTable(const Method* meth, const InsnFlags* insnFlags,
+static bool initRegisterTable(const VerifierData* vdata,
RegisterTable* regTable, RegisterTrackingMode trackRegsFor)
{
- const int insnsSize = dvmGetMethodInsnsSize(meth);
+ const Method* meth = vdata->method;
+ const int insnsSize = vdata->insnsSize;
+ const InsnFlags* insnFlags = vdata->insnFlags;
const int kExtraLines = 2; /* workLine, savedLine */
int i;
+ /*
+ * Every address gets a RegisterLine struct. This is wasteful, but
+ * not so much that it's worth chasing through an extra level of
+ * indirection.
+ */
regTable->insnRegCountPlus = meth->registersSize + kExtraRegs;
regTable->registerLines =
(RegisterLine*) calloc(insnsSize, sizeof(RegisterLine));
@@ -2926,17 +3044,36 @@
/*
* Allocate storage for the register type arrays.
- * TODO: also allocate and assign storage for monitor tracking
+ * TODO: set trackMonitors based on global config option
*/
- regTable->lineAlloc =
- calloc(regTable->insnRegCountPlus * interestingCount, sizeof(RegType));
+ size_t regTypeSize = regTable->insnRegCountPlus * sizeof(RegType);
+ size_t monEntSize = regTable->insnRegCountPlus * sizeof(MonitorEntries);
+ size_t stackSize = kMaxMonitorStackDepth * sizeof(u4);
+ bool trackMonitors;
+
+ if (gDvm.monitorVerification) {
+ trackMonitors = (vdata->monitorEnterCount != 0);
+ } else {
+ trackMonitors = false;
+ }
+
+ size_t spacePerEntry = regTypeSize +
+ (trackMonitors ? monEntSize + stackSize : 0);
+ regTable->lineAlloc = calloc(interestingCount, spacePerEntry);
if (regTable->lineAlloc == NULL)
return false;
+#ifdef VERIFIER_STATS
+ size_t totalSpace = interestingCount * spacePerEntry +
+ insnsSize * sizeof(RegisterLine);
+ if (gDvm.verifierStats.biggestAlloc < totalSpace)
+ gDvm.verifierStats.biggestAlloc = totalSpace;
+#endif
+
/*
* Populate the sparse register line table.
*/
- RegType* regPtr = regTable->lineAlloc;
+ u1* storage = regTable->lineAlloc;
for (i = 0; i < insnsSize; i++) {
bool interesting;
@@ -2957,29 +3094,28 @@
}
if (interesting) {
- regTable->registerLines[i].regTypes = regPtr;
- regPtr += regTable->insnRegCountPlus;
+ storage = assignLineStorage(storage, ®Table->registerLines[i],
+ trackMonitors, regTypeSize, monEntSize, stackSize);
}
}
/*
* Grab storage for our "temporary" register lines.
*/
- regTable->workLine.regTypes = regPtr;
- regPtr += regTable->insnRegCountPlus;
- regTable->savedLine.regTypes = regPtr;
- regPtr += regTable->insnRegCountPlus;
+ storage = assignLineStorage(storage, ®Table->workLine,
+ trackMonitors, regTypeSize, monEntSize, stackSize);
+ storage = assignLineStorage(storage, ®Table->savedLine,
+ trackMonitors, regTypeSize, monEntSize, stackSize);
//LOGD("Tracking registers for [%d], total %d in %d units\n",
// trackRegsFor, interestingCount-kExtraLines, insnsSize);
- assert(regPtr - (RegType*)regTable->lineAlloc ==
- (int) (regTable->insnRegCountPlus * interestingCount));
+ assert(storage - (u1*)regTable->lineAlloc ==
+ (int) (interestingCount * spacePerEntry));
assert(regTable->registerLines[0].regTypes != NULL);
return true;
}
-
/*
* Verify that the arguments in a filled-new-array instruction are valid.
*
@@ -3153,6 +3289,89 @@
return result;
}
+/*
+ * Handle a monitor-enter instruction.
+ */
+void handleMonitorEnter(RegisterLine* workLine, u4 regIdx, u4 insnIdx,
+ VerifyError* pFailure)
+{
+ /*
+ * This should only be true if structured lock checking is disabled.
+ * TODO: assert that this is the case
+ */
+ if (workLine->monitorEntries == NULL)
+ return;
+
+ if (!regTypeIsReference(getRegisterType(workLine, regIdx))) {
+ LOG_VFY("VFY: monitor-enter on non-object\n");
+ *pFailure = VERIFY_ERROR_GENERIC;
+ return;
+ }
+
+ if (workLine->monitorStackTop == kMaxMonitorStackDepth) {
+ LOG_VFY("VFY: monitor-enter stack overflow (%d)\n",
+ kMaxMonitorStackDepth);
+ *pFailure = VERIFY_ERROR_GENERIC;
+ return;
+ }
+
+ /*
+ * Push an entry on the stack, and set a bit in the register flags to
+ * indicate that it's associated with this register.
+ */
+ workLine->monitorEntries[regIdx] |= 1 << workLine->monitorStackTop;
+ workLine->monitorStack[workLine->monitorStackTop++] = insnIdx;
+}
+
+/*
+ * Handle a monitor-exit instruction.
+ */
+void handleMonitorExit(RegisterLine* workLine, u4 regIdx, u4 insnIdx,
+ VerifyError* pFailure)
+{
+ /*
+ * This should only be true if structured lock checking is disabled.
+ * TODO: assert that this is the case
+ */
+ if (workLine->monitorEntries == NULL)
+ return;
+
+ if (!regTypeIsReference(getRegisterType(workLine, regIdx))) {
+ LOG_VFY("VFY: monitor-exit on non-object\n");
+ *pFailure = VERIFY_ERROR_GENERIC;
+ return;
+ }
+
+ if (workLine->monitorStackTop == 0) {
+ LOG_VFY("VFY: monitor-exit stack underflow\n");
+ *pFailure = VERIFY_ERROR_GENERIC;
+ return;
+ }
+
+ /*
+ * Confirm that the entry at the top of the stack is associated with
+ * the register. Pop the top entry off.
+ */
+ workLine->monitorStackTop--;
+#ifdef BUG_3215458_FIXED
+ if ((workLine->monitorEntries[regIdx] & (1 << workLine->monitorStackTop))
+ == 0)
+ {
+ LOG_VFY("VFY: monitor-exit bit %d not set: addr=0x%04x (bits[%d]=0x%x)\n",
+ workLine->monitorStackTop, insnIdx, regIdx,
+ workLine->monitorEntries[regIdx]);
+ *pFailure = VERIFY_ERROR_GENERIC;
+ return;
+ }
+#endif
+ workLine->monitorStack[workLine->monitorStackTop] = 0;
+
+ /*
+ * Clear the bit from the register flags.
+ */
+ workLine->monitorEntries[regIdx] &= ~(1 << workLine->monitorStackTop);
+}
+
/*
* ===========================================================================
@@ -3207,6 +3426,8 @@
#ifdef VERIFIER_STATS
gDvm.verifierStats.methodsExamined++;
+ if (vdata->monitorEnterCount)
+ gDvm.verifierStats.monEnterMethods++;
#endif
/* TODO: move this elsewhere -- we don't need to do this for every method */
@@ -3224,7 +3445,7 @@
* also going to create the register map, we need to retain the
* register lists for a larger set of addresses.
*/
- if (!initRegisterTable(meth, vdata->insnFlags, ®Table,
+ if (!initRegisterTable(vdata, ®Table,
generateRegisterMap ? kTrackRegsGcPoints : kTrackRegsBranches))
goto bail;
@@ -3669,13 +3890,15 @@
RegType returnType = getMethodReturnType(meth);
checkTypeCategory(returnType, kTypeCategory1nr, &failure);
if (!VERIFY_OK(failure))
- LOG_VFY("VFY: return-32 not expected\n");
+ LOG_VFY("VFY: return-1nr not expected\n");
/* check the register contents */
returnType = getRegisterType(workLine, decInsn.vA);
checkTypeCategory(returnType, kTypeCategory1nr, &failure);
- if (!VERIFY_OK(failure))
- LOG_VFY("VFY: return-32 on invalid register v%d\n", decInsn.vA);
+ if (!VERIFY_OK(failure)) {
+ LOG_VFY("VFY: return-1nr on invalid register v%d\n",
+ decInsn.vA);
+ }
}
break;
case OP_RETURN_WIDE:
@@ -3788,12 +4011,32 @@
break;
case OP_MONITOR_ENTER:
+ handleMonitorEnter(workLine, decInsn.vA, insnIdx, &failure);
+ break;
case OP_MONITOR_EXIT:
- tmpType = getRegisterType(workLine, decInsn.vA);
- if (!regTypeIsReference(tmpType)) {
- LOG_VFY("VFY: monitor op on non-object\n");
- failure = VERIFY_ERROR_GENERIC;
- }
+ /*
+ * 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
+ * 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
+ * exceptions that can be thrown from monitor-exit are for a
+ * 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
+ * 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.
+ */
+ if (workLine->monitorEntries != NULL)
+ nextFlags &= ~kInstrCanThrow;
+ handleMonitorExit(workLine, decInsn.vA, insnIdx, &failure);
break;
case OP_CHECK_CAST:
@@ -5490,8 +5733,9 @@
* Merge registers into what we have for the next instruction,
* and set the "changed" flag if needed.
*/
- updateRegisters(meth, insnFlags, regTable, insnIdx+insnWidth,
- workLine);
+ if (!updateRegisters(meth, insnFlags, regTable, insnIdx+insnWidth,
+ workLine))
+ goto bail;
} else {
/*
* We're not recording register data for the next instruction,
@@ -5531,8 +5775,9 @@
goto bail;
/* update branch target, set "changed" if appropriate */
- updateRegisters(meth, insnFlags, regTable, insnIdx+branchTarget,
- workLine);
+ if (!updateRegisters(meth, insnFlags, regTable, insnIdx+branchTarget,
+ workLine))
+ goto bail;
}
/*
@@ -5570,7 +5815,9 @@
if (!checkMoveException(meth, absOffset, "switch"))
goto bail;
- updateRegisters(meth, insnFlags, regTable, absOffset, workLine);
+ if (!updateRegisters(meth, insnFlags, regTable, absOffset,
+ workLine))
+ goto bail;
}
}
@@ -5583,6 +5830,7 @@
{
const DexCode* pCode = dvmGetMethodCode(meth);
DexCatchIterator iterator;
+ bool hasCatchAll = false;
if (dexFindCatchHandler(&iterator, pCode, insnIdx)) {
for (;;) {
@@ -5592,11 +5840,51 @@
break;
}
- /* note we use savedLine, not workLine */
- updateRegisters(meth, insnFlags, regTable, handler->address,
- ®Table->savedLine);
+ if (handler->typeIdx == kDexNoIndex)
+ hasCatchAll = true;
+
+ /*
+ * Merge registers into the "catch" block. We want to
+ * use the "savedRegs" rather than "workRegs", because
+ * at runtime the exception will be thrown before the
+ * instruction modifies any registers.
+ */
+ if (!updateRegisters(meth, insnFlags, regTable,
+ handler->address, ®Table->savedLine))
+ goto bail;
}
}
+
+ /*
+ * If the monitor stack depth is nonzero, there must be a "catch all"
+ * handler for this instruction. This does apply to monitor-exit
+ * because of async exception handling.
+ */
+ if (workLine->monitorStackTop != 0 && !hasCatchAll) {
+ /*
+ * The state in workLine reflects the post-execution state.
+ * If the current instruction is a monitor-enter and the monitor
+ * stack was empty, we don't need a catch-all (if it throws,
+ * it will do so before grabbing the lock).
+ */
+ if (!(decInsn.opCode == OP_MONITOR_ENTER &&
+ workLine->monitorStackTop == 1))
+ {
+ LOG_VFY_METH(meth,
+ "VFY: no catch-all for instruction at 0x%04x\n", insnIdx);
+ goto bail;
+ }
+ }
+ }
+
+ /*
+ * If we're returning from the method, make sure our monitor stack
+ * is empty.
+ */
+ if ((nextFlags & kInstrCanReturn) != 0 && workLine->monitorStackTop != 0) {
+ LOG_VFY_METH(meth, "VFY: return with stack depth=%d at 0x%04x\n",
+ workLine->monitorStackTop, insnIdx);
+ goto bail;
}
/*
@@ -5702,10 +5990,13 @@
regChars[1 + i + (i/4) + 2] = tch;
}
- if (addr == 0 && addrName != NULL)
- LOGI("%c%s %s\n", branchTarget ? '>' : ' ', addrName, regChars);
- else
- LOGI("%c0x%04x %s\n", branchTarget ? '>' : ' ', addr, regChars);
+ if (addr == 0 && addrName != NULL) {
+ LOGI("%c%s %s mst=%d\n", branchTarget ? '>' : ' ',
+ addrName, regChars, registerLine->monitorStackTop);
+ } else {
+ LOGI("%c0x%04x %s mst=%d\n", branchTarget ? '>' : ' ',
+ addr, regChars, registerLine->monitorStackTop);
+ }
if (displayFlags & DRT_SHOW_REF_TYPES) {
for (i = 0; i < regCount + kExtraRegs; i++) {
diff --git a/vm/analysis/CodeVerify.h b/vm/analysis/CodeVerify.h
index 8069d09..be7231c 100644
--- a/vm/analysis/CodeVerify.h
+++ b/vm/analysis/CodeVerify.h
@@ -181,6 +181,12 @@
* in GC points.
*/
RegisterLine* registerLines;
+
+ /*
+ * The number of occurrences of specific opcodes.
+ */
+ size_t newInstanceCount;
+ size_t monitorEnterCount;
} VerifierData;
diff --git a/vm/analysis/DexPrepare.c b/vm/analysis/DexPrepare.c
index e7106ce..4a17123 100644
--- a/vm/analysis/DexPrepare.c
+++ b/vm/analysis/DexPrepare.c
@@ -917,11 +917,14 @@
#ifdef VERIFIER_STATS
LOGI("Verifier stats:\n");
LOGI(" methods examined : %u\n", gDvm.verifierStats.methodsExamined);
+ LOGI(" monitor-enter methods : %u\n", gDvm.verifierStats.monEnterMethods);
LOGI(" instructions examined : %u\n", gDvm.verifierStats.instrsExamined);
LOGI(" instructions re-examined: %u\n", gDvm.verifierStats.instrsReexamined);
LOGI(" copying of register sets: %u\n", gDvm.verifierStats.copyRegCount);
LOGI(" merging of register sets: %u\n", gDvm.verifierStats.mergeRegCount);
LOGI(" ...that caused changes : %u\n", gDvm.verifierStats.mergeRegChanged);
+ LOGI(" uninit searches : %u\n", gDvm.verifierStats.uninitSearches);
+ LOGI(" max memory required : %u\n", gDvm.verifierStats.biggestAlloc);
#endif
}
diff --git a/vm/analysis/DexVerify.c b/vm/analysis/DexVerify.c
index b33d333..9a07559 100644
--- a/vm/analysis/DexVerify.c
+++ b/vm/analysis/DexVerify.c
@@ -65,12 +65,12 @@
/*
* Compute the width of the instruction at each address in the instruction
- * stream. Addresses that are in the middle of an instruction, or that
- * are part of switch table data, are not set (so the caller should probably
- * initialize "insnFlags" to zero).
+ * stream, and store it in vdata->insnFlags. 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 "insnFlags" to zero).
*
- * If "pNewInstanceCount" is not NULL, it will be set to the number of
- * new-instance instructions in the method.
+ * The "newInstanceCount" and "monitorEnterCount" fields in vdata are
+ * also set.
*
* Performs some static checks, notably:
* - opcode of first instruction begins at index 0
@@ -80,26 +80,28 @@
*
* Logs an error and returns "false" on failure.
*/
-static bool computeCodeWidths(const Method* meth, InsnFlags* insnFlags,
- int* pNewInstanceCount)
+static bool computeWidthsAndCountOps(VerifierData* vdata)
{
- size_t insnCount = dvmGetMethodInsnsSize(meth);
+ const Method* meth = vdata->method;
+ InsnFlags* insnFlags = vdata->insnFlags;
+ size_t insnCount = vdata->insnsSize;
const u2* insns = meth->insns;
bool result = false;
int newInstanceCount = 0;
+ int monitorEnterCount = 0;
int i;
-
for (i = 0; i < (int) insnCount; /**/) {
size_t width = dexGetInstrOrTableWidth(insns);
if (width == 0) {
- LOG_VFY_METH(meth,
- "VFY: invalid post-opt instruction (0x%04x)\n", *insns);
+ LOG_VFY_METH(meth, "VFY: invalid instruction (0x%04x)\n", *insns);
goto bail;
}
if ((*insns & 0xff) == OP_NEW_INSTANCE)
newInstanceCount++;
+ if ((*insns & 0xff) == OP_MONITOR_ENTER)
+ monitorEnterCount++;
if (width > 65535) {
LOG_VFY_METH(meth, "VFY: insane width %d\n", width);
@@ -117,8 +119,8 @@
}
result = true;
- if (pNewInstanceCount != NULL)
- *pNewInstanceCount = newInstanceCount;
+ vdata->newInstanceCount = newInstanceCount;
+ vdata->monitorEnterCount = monitorEnterCount;
bail:
return result;
@@ -227,7 +229,7 @@
* Confirmed here:
* - code array must not be empty
* - (N/A) code_length must be less than 65536
- * Confirmed by computeCodeWidths():
+ * Confirmed by computeWidthsAndCountOps():
* - opcode of first instruction begins at index 0
* - only documented instructions may appear
* - each instruction follows the last
@@ -236,7 +238,6 @@
static bool verifyMethod(Method* meth)
{
bool result = false;
- int newInstanceCount;
/*
* Verifier state blob. Various values will be cached here so we
@@ -292,17 +293,16 @@
/*
* Compute the width of each instruction and store the result in insnFlags.
- * Count up the #of occurrences of new-instance instructions while we're
- * at it.
+ * Count up the #of occurrences of certain opcodes while we're at it.
*/
- if (!computeCodeWidths(meth, vdata.insnFlags, &newInstanceCount))
+ if (!computeWidthsAndCountOps(&vdata))
goto bail;
/*
* Allocate a map to hold the classes of uninitialized instances.
*/
vdata.uninitMap = dvmCreateUninitInstanceMap(meth, vdata.insnFlags,
- newInstanceCount);
+ vdata.newInstanceCount);
if (vdata.uninitMap == NULL)
goto bail;
diff --git a/vm/analysis/DexVerify.h b/vm/analysis/DexVerify.h
index 9ce7672..ae1b557 100644
--- a/vm/analysis/DexVerify.h
+++ b/vm/analysis/DexVerify.h
@@ -45,11 +45,14 @@
/* some verifier counters, for debugging */
typedef struct {
size_t methodsExamined; /* number of methods examined */
+ size_t monEnterMethods; /* number of methods with monitor-enter */
size_t instrsExamined; /* incr on first visit of instruction */
size_t instrsReexamined; /* incr on each repeat visit of instruction */
size_t copyRegCount; /* calls from updateRegisters->copyRegisters */
size_t mergeRegCount; /* calls from updateRegisters->merge */
size_t mergeRegChanged; /* calls from updateRegisters->merge, changed */
+ size_t uninitSearches; /* times we've had to search the uninit table */
+ size_t biggestAlloc; /* largest RegisterLine table alloc */
} VerifierStats;
#endif /*_DALVIK_DEXVERIFY*/
