Don't scan image space when starting runtime.

Bug 10432288.
Find Classes and Strings from dex caches lazily rather than when the image is
loaded.
Make class status changes do notifies when there can be waiters.
For Class lookup there's a pathology if we always search dex caches and
so after 1000 failures move all classes into the class table.
Be consistent in using "const char*" for class linker descriptors as this
most easily agrees with the type in the dex file.
Improve the intern run-test so that it has a case of a literal contained in the
image.
Modify image_test to allow any valid lock word rather than expecting 0, ideally
we wouldn't see inflated monitors but we do due to NotifyAll (see bug 6961405).

Change-Id: Ia9bfa748eeccb9b4498784b97c6823141b1f6db8
diff --git a/runtime/monitor.cc b/runtime/monitor.cc
index ff193c9..66c51e6 100644
--- a/runtime/monitor.cc
+++ b/runtime/monitor.cc
@@ -792,6 +792,8 @@
       return;
     }
     // no-op;  there are no waiters to notify.
+    // We inflate here in case the Notify is in a tight loop. Without inflation here the waiter
+    // will struggle to get in. Bug 6961405.
     Inflate(self, obj);
   } else {
     // It's a fat lock.
@@ -811,6 +813,8 @@
       return;
     }
     // no-op;  there are no waiters to notify.
+    // We inflate here in case the NotifyAll is in a tight loop. Without inflation here the waiter
+    // will struggle to get in. Bug 6961405.
     Inflate(self, obj);
   } else {
     // It's a fat lock.
@@ -948,6 +952,27 @@
   }
 }
 
+bool Monitor::IsValidLockWord(int32_t lock_word) {
+  if (lock_word == 0) {
+    return true;
+  } else if (LW_SHAPE(lock_word) == LW_SHAPE_FAT) {
+    Monitor* mon = LW_MONITOR(lock_word);
+    MonitorList* list = Runtime::Current()->GetMonitorList();
+    MutexLock mu(Thread::Current(), list->monitor_list_lock_);
+    bool found = false;
+    for (Monitor* list_mon : list->list_) {
+      if (mon == list_mon) {
+        found = true;
+        break;
+      }
+    }
+    return found;
+  } else {
+    // TODO: thin lock validity checking.
+    return LW_SHAPE(lock_word) == LW_SHAPE_THIN;
+  }
+}
+
 void Monitor::TranslateLocation(const mirror::ArtMethod* method, uint32_t dex_pc,
                                 const char*& source_file, uint32_t& line_number) const {
   // If method is null, location is unknown