diff --git a/src/class_linker.cc b/src/class_linker.cc
index 89b425f..da87a97 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -12,6 +12,7 @@
 #include "dex_file.h"
 #include "dex_verifier.h"
 #include "heap.h"
+#include "intern_table.h"
 #include "logging.h"
 #include "monitor.h"
 #include "object.h"
@@ -53,8 +54,9 @@
   "[Ljava/lang/StackTraceElement;",
 };
 
-ClassLinker* ClassLinker::Create(const std::vector<const DexFile*>& boot_class_path, Space* space) {
-  UniquePtr<ClassLinker> class_linker(new ClassLinker);
+ClassLinker* ClassLinker::Create(const std::vector<const DexFile*>& boot_class_path,
+    InternTable* intern_table, Space* space) {
+  UniquePtr<ClassLinker> class_linker(new ClassLinker(intern_table));
   if (space == NULL) {
     class_linker->Init(boot_class_path);
   } else {
@@ -64,10 +66,11 @@
   return class_linker.release();
 }
 
-ClassLinker::ClassLinker()
+ClassLinker::ClassLinker(InternTable* intern_table)
     : classes_lock_(Mutex::Create("ClassLinker::Lock")),
       class_roots_(NULL),
-      init_done_(false) {
+      init_done_(false),
+      intern_table_(intern_table) {
 }
 
 void ClassLinker::Init(const std::vector<const DexFile*>& boot_class_path) {
@@ -344,11 +347,11 @@
     SetClassRoot(class_root, state.class_roots[class_root]);
   }
 
-  // reinit intern_table_
+  // reinit intern table
   ObjectArray<Object>* interned_array = space->GetImageHeader().GetInternedArray();
   for (int32_t i = 0; i < interned_array->GetLength(); i++) {
     String* string = interned_array->Get(i)->AsString();
-    intern_table_.Register(string);
+    intern_table_->RegisterStrong(string);
   }
 
   // reinit array_interfaces_ from any array class instance, they should all be ==
@@ -439,7 +442,7 @@
     }
   }
 
-  intern_table_.VisitRoots(root_visitor, arg);
+  intern_table_->VisitRoots(root_visitor, arg);
 
   root_visitor(array_interfaces_, arg);
 }
@@ -1375,7 +1378,7 @@
         break;
       case DexFile::kString: {
         uint32_t string_idx = value.i;
-        String* resolved = ResolveString(dex_file, string_idx, klass->GetDexCache());
+        const String* resolved = ResolveString(dex_file, string_idx, klass->GetDexCache());
         field->SetObject(NULL, resolved);
         break;
       }
@@ -1891,17 +1894,16 @@
   }
 }
 
-String* ClassLinker::ResolveString(const DexFile& dex_file,
-                                   uint32_t string_idx,
-                                   DexCache* dex_cache) {
-  String* resolved = dex_cache->GetResolvedString(string_idx);
+const String* ClassLinker::ResolveString(const DexFile& dex_file,
+    uint32_t string_idx, DexCache* dex_cache) {
+  const String* resolved = dex_cache->GetResolvedString(string_idx);
   if (resolved != NULL) {
     return resolved;
   }
   const DexFile::StringId& string_id = dex_file.GetStringId(string_idx);
   int32_t utf16_length = dex_file.GetStringLength(string_id);
   const char* utf8_data = dex_file.GetStringData(string_id);
-  String* string = intern_table_.Intern(utf16_length, utf8_data);
+  const String* string = intern_table_->InternStrong(utf16_length, utf8_data);
   dex_cache->SetResolvedString(string_idx, string);
   return string;
 }
diff --git a/src/class_linker.h b/src/class_linker.h
index 1f233b0..4702a57 100644
--- a/src/class_linker.h
+++ b/src/class_linker.h
@@ -9,7 +9,6 @@
 
 #include "dex_file.h"
 #include "heap.h"
-#include "intern_table.h"
 #include "macros.h"
 #include "object.h"
 #include "thread.h"
@@ -18,14 +17,16 @@
 
 #include "gtest/gtest.h"
 
-class ClassLoader;
-
 namespace art {
 
+class ClassLoader;
+class InternTable;
+
 class ClassLinker {
  public:
   // Initializes the class linker using DexFile and an optional boot Space.
-  static ClassLinker* Create(const std::vector<const DexFile*>& boot_class_path, Space* boot_space);
+  static ClassLinker* Create(const std::vector<const DexFile*>& boot_class_path,
+      InternTable* intern_table, Space* boot_space);
 
   ~ClassLinker();
 
@@ -44,9 +45,7 @@
 
   // Resolve a String with the given index from the DexFile, storing the
   // result in the DexCache.
-  String* ResolveString(const DexFile& dex_file,
-                        uint32_t string_idx,
-                        DexCache* dex_cache);
+  const String* ResolveString(const DexFile& dex_file, uint32_t string_idx, DexCache* dex_cache);
 
   // Resolve a Type with the given index from the DexFile, storing the
   // result in the DexCache. The referrer is used to identity the
@@ -123,10 +122,6 @@
     return boot_class_path_;
   }
 
-  const InternTable& GetInternTable() {
-    return intern_table_;
-  }
-
   void VisitRoots(Heap::RootVistor* root_visitor, void* arg) const;
 
   const DexFile& FindDexFile(const DexCache* dex_cache) const;
@@ -140,7 +135,7 @@
   ObjectArray<StackTraceElement>* AllocStackTraceElementArray(size_t length);
 
  private:
-  ClassLinker();
+  ClassLinker(InternTable*);
 
   // Initialize class linker from DexFile instances.
   void Init(const std::vector<const DexFile*>& boot_class_path_);
@@ -257,8 +252,6 @@
   Table classes_;
   Mutex* classes_lock_;
 
-  InternTable intern_table_;
-
   // indexes into class_roots_.
   // needs to be kept in sync with class_roots_descriptors_.
   enum ClassRoot {
@@ -327,6 +320,8 @@
 
   bool init_done_;
 
+  InternTable* intern_table_;
+
   friend class CommonTest;
   FRIEND_TEST(DexCacheTest, Open);
   friend class ObjectTest;
diff --git a/src/class_linker_test.cc b/src/class_linker_test.cc
index c403065..a34f180 100644
--- a/src/class_linker_test.cc
+++ b/src/class_linker_test.cc
@@ -262,7 +262,7 @@
     class_linker_->VisitRoots(TestRootVisitor, NULL);
   }
 
-  static void TestRootVisitor(Object* root, void* arg) {
+  static void TestRootVisitor(const Object* root, void* arg) {
     EXPECT_TRUE(root != NULL);
   }
 };
diff --git a/src/compiler/codegen/arm/Thumb2/Gen.cc b/src/compiler/codegen/arm/Thumb2/Gen.cc
index 3da5aaa..258b57b 100644
--- a/src/compiler/codegen/arm/Thumb2/Gen.cc
+++ b/src/compiler/codegen/arm/Thumb2/Gen.cc
@@ -512,7 +512,7 @@
 static void genConstString(CompilationUnit* cUnit, MIR* mir,
                            RegLocation rlDest, RegLocation rlSrc)
 {
-    String* strPtr = cUnit->method->GetDeclaringClass()->GetDexCache()->
+    const String* strPtr = cUnit->method->GetDeclaringClass()->GetDexCache()->
         GetResolvedString(mir->dalvikInsn.vB);
 
     if (strPtr == NULL) {
diff --git a/src/compiler_test.cc b/src/compiler_test.cc
index 63881fd..eca5b2a 100644
--- a/src/compiler_test.cc
+++ b/src/compiler_test.cc
@@ -128,7 +128,7 @@
   DexCache* dex_cache = class_linker_->FindDexCache(*dex);
   EXPECT_EQ(dex->NumStringIds(), dex_cache->NumStrings());
   for (size_t i = 0; i < dex_cache->NumStrings(); i++) {
-    String* string = dex_cache->GetResolvedString(i);
+    const String* string = dex_cache->GetResolvedString(i);
     EXPECT_TRUE(string != NULL);
   }
   EXPECT_EQ(dex->NumTypeIds(), dex_cache->NumResolvedTypes());
diff --git a/src/dex_cache.h b/src/dex_cache.h
index 137f267..f2cfcc7 100644
--- a/src/dex_cache.h
+++ b/src/dex_cache.h
@@ -109,11 +109,11 @@
     return GetInitializedStaticStorage()->GetLength();
   }
 
-  String* GetResolvedString(uint32_t string_idx) const {
+  const String* GetResolvedString(uint32_t string_idx) const {
     return GetStrings()->Get(string_idx);
   }
 
-  void SetResolvedString(uint32_t string_idx, String* resolved) {
+  void SetResolvedString(uint32_t string_idx, const String* resolved) {
     GetStrings()->Set(string_idx, resolved);
   }
 
@@ -141,8 +141,8 @@
     GetResolvedFields()->Set(field_idx, resolved);
   }
 
-  ObjectArray<String>* GetStrings() const {
-    return static_cast<ObjectArray<String>*>(GetNonNull(kStrings));
+  ObjectArray<const String>* GetStrings() const {
+    return static_cast<ObjectArray<const String>*>(GetNonNull(kStrings));
   }
   ObjectArray<Class>* GetResolvedTypes() const {
     return static_cast<ObjectArray<Class>*>(GetNonNull(kResolvedTypes));
diff --git a/src/heap.cc b/src/heap.cc
index 58588ef..1682cc5 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -118,7 +118,7 @@
   return obj;
 }
 
-void Heap::VerifyObject(Object* obj) {
+void Heap::VerifyObject(const Object* obj) {
   if (!IsAligned(obj, kObjectAlignment)) {
     LOG(FATAL) << "Object isn't aligned: " << obj;
   } else if (!live_bitmap_->Test(obj)) {
@@ -130,7 +130,7 @@
   }
 }
 
-bool Heap::IsHeapAddress(Object* obj) {
+bool Heap::IsHeapAddress(const Object* obj) {
   if (!IsAligned(obj, kObjectAlignment)) {
     return false;
   }
diff --git a/src/heap.h b/src/heap.h
index 72ceffa..c3ea080 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -22,7 +22,7 @@
 
   static const size_t kMaximumSize = 64 * MB;
 
-  typedef void (RootVistor)(Object* root, void* arg);
+  typedef void (RootVistor)(const Object* root, void* arg);
 
   // Create a heap with the requested sizes. optional boot image may
   // be NULL, otherwise it is an image filename created by ImageWriter.
@@ -34,12 +34,12 @@
   static Object* AllocObject(Class* klass, size_t num_bytes);
 
   // Check sanity of given reference. Requires the heap lock.
-  static void VerifyObject(Object *obj);
+  static void VerifyObject(const Object *obj);
 
   // A weaker test than VerifyObject that doesn't require the heap lock,
   // and doesn't abort on error, allowing the caller to report more
   // meaningful diagnostics.
-  static bool IsHeapAddress(Object* obj);
+  static bool IsHeapAddress(const Object* obj);
 
   // Initiates an explicit garbage collection.
   static void CollectGarbage();
diff --git a/src/image.h b/src/image.h
index c567880..94824d7 100644
--- a/src/image.h
+++ b/src/image.h
@@ -49,7 +49,7 @@
   // required base address for mapping the image.
   uint32_t base_addr_;
 
-  // absolute address of an Object[] of Strings to InternTable::Register
+  // absolute address of an Object[] of Strings to InternTable::RegisterStrong.
   uint32_t intern_addr_;
 };
 
diff --git a/src/image_writer.cc b/src/image_writer.cc
index fd3ec4d..887be66 100644
--- a/src/image_writer.cc
+++ b/src/image_writer.cc
@@ -53,24 +53,25 @@
 
 struct InternTableVisitorState {
   int index;
-  ObjectArray<Object>* interned_array;
+  ObjectArray<const Object>* interned_array;
 };
 
-void InternTableVisitor(Object* obj, void* arg) {
+void InternTableVisitor(const Object* obj, void* arg) {
   InternTableVisitorState* state = reinterpret_cast<InternTableVisitorState*>(arg);
   state->interned_array->Set(state->index++, obj);
 }
 
-ObjectArray<Object>* CreateInternedArray() {
+ObjectArray<const Object>* CreateInternedArray() {
   // build a Object[] of the interned strings for reinit
   // TODO: avoid creating this future garbage
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  const InternTable& intern_table = class_linker->GetInternTable();
+  Runtime* runtime = Runtime::Current();
+  ClassLinker* class_linker = runtime->GetClassLinker();
+  const InternTable& intern_table = *runtime->GetInternTable();
   size_t size = intern_table.Size();
   CHECK_NE(0U, size);
 
   Class* object_array_class = class_linker->FindSystemClass("[Ljava/lang/Object;");
-  ObjectArray<Object>* interned_array = ObjectArray<Object>::Alloc(object_array_class, size);
+  ObjectArray<const Object>* interned_array = ObjectArray<const Object>::Alloc(object_array_class, size);
 
   InternTableVisitorState state;
   state.index = 0;
@@ -93,7 +94,7 @@
 }
 
 void ImageWriter::CalculateNewObjectOffsets() {
-  ObjectArray<Object>* interned_array = CreateInternedArray();
+  ObjectArray<const Object>* interned_array = CreateInternedArray();
 
   HeapBitmap* heap_bitmap = Heap::GetLiveBits();
   DCHECK(heap_bitmap != NULL);
diff --git a/src/indirect_reference_table.cc b/src/indirect_reference_table.cc
index 083a499..32d942f 100644
--- a/src/indirect_reference_table.cc
+++ b/src/indirect_reference_table.cc
@@ -39,10 +39,10 @@
   CHECK_LE(initialCount, maxCount);
   CHECK_NE(desiredKind, kSirtOrInvalid);
 
-  table_ = reinterpret_cast<Object**>(malloc(initialCount * sizeof(Object*)));
+  table_ = reinterpret_cast<const Object**>(malloc(initialCount * sizeof(const Object*)));
   CHECK(table_ != NULL);
 #ifndef NDEBUG
-  memset(table_, 0xd1, initialCount * sizeof(Object*));
+  memset(table_, 0xd1, initialCount * sizeof(const Object*));
 #endif
 
   slot_data_ = reinterpret_cast<IndirectRefSlot*>(calloc(initialCount, sizeof(IndirectRefSlot)));
@@ -66,7 +66,7 @@
  * Make sure that the entry at "idx" is correctly paired with "iref".
  */
 bool IndirectReferenceTable::CheckEntry(const char* what, IndirectRef iref, int idx) const {
-  Object* obj = table_[idx];
+  const Object* obj = table_[idx];
   IndirectRef checkRef = ToIndirectRef(obj, idx);
   if (checkRef != iref) {
     LOG(ERROR) << "JNI ERROR (app bug): attempt to " << what
@@ -78,7 +78,7 @@
   return true;
 }
 
-IndirectRef IndirectReferenceTable::Add(uint32_t cookie, Object* obj) {
+IndirectRef IndirectReferenceTable::Add(uint32_t cookie, const Object* obj) {
   IRTSegmentState prevState;
   prevState.all = cookie;
   size_t topIndex = segmentState.parts.topIndex;
@@ -105,7 +105,7 @@
     }
     DCHECK_GT(newSize, alloc_entries_);
 
-    table_ = (Object**) realloc(table_, newSize * sizeof(Object*));
+    table_ = (const Object**) realloc(table_, newSize * sizeof(const Object*));
     slot_data_ = (IndirectRefSlot*) realloc(slot_data_, newSize * sizeof(IndirectRefSlot));
     if (table_ == NULL || slot_data_ == NULL) {
       LOG(ERROR) << "JNI ERROR (app bug): unable to expand "
@@ -132,7 +132,7 @@
   if (numHoles > 0) {
     DCHECK_GT(topIndex, 1U);
     /* find the first hole; likely to be near the end of the list */
-    Object** pScan = &table_[topIndex - 1];
+    const Object** pScan = &table_[topIndex - 1];
     DCHECK(*pScan != NULL);
     while (*--pScan != NULL) {
       DCHECK_GE(pScan, table_ + prevState.parts.topIndex);
@@ -191,9 +191,9 @@
   return true;
 }
 
-static int LinearScan(IndirectRef iref, int bottomIndex, int topIndex, Object** table) {
+static int LinearScan(IndirectRef iref, int bottomIndex, int topIndex, const Object** table) {
   for (int i = bottomIndex; i < topIndex; ++i) {
-    if (table[i] == reinterpret_cast<Object*>(iref)) {
+    if (table[i] == reinterpret_cast<const Object*>(iref)) {
       return i;
     }
   }
diff --git a/src/indirect_reference_table.h b/src/indirect_reference_table.h
index 86c1293..da5f955 100644
--- a/src/indirect_reference_table.h
+++ b/src/indirect_reference_table.h
@@ -126,7 +126,7 @@
 static const size_t kIRTPrevCount = 4;
 struct IndirectRefSlot {
   uint32_t serial;
-  Object* previous[kIRTPrevCount];
+  const Object* previous[kIRTPrevCount];
 };
 
 /* use as initial value for "cookie", and when table has only one segment */
@@ -209,7 +209,7 @@
 
 class IrtIterator {
  public:
-  explicit IrtIterator(Object** table, size_t i, size_t capacity)
+  explicit IrtIterator(const Object** table, size_t i, size_t capacity)
       : table_(table), i_(i), capacity_(capacity) {
     SkipNullsAndTombstones();
   }
@@ -220,7 +220,7 @@
     return *this;
   }
 
-  Object** operator*() {
+  const Object** operator*() {
     return &table_[i_];
   }
 
@@ -236,7 +236,7 @@
     }
   }
 
-  Object** table_;
+  const Object** table_;
   size_t i_;
   size_t capacity_;
 };
@@ -261,14 +261,14 @@
    * Returns NULL if the table is full (max entries reached, or alloc
    * failed during expansion).
    */
-  IndirectRef Add(uint32_t cookie, Object* obj);
+  IndirectRef Add(uint32_t cookie, const Object* obj);
 
   /*
    * Given an IndirectRef in the table, return the Object it refers to.
    *
    * Returns kInvalidIndirectRefObject if iref is invalid.
    */
-  Object* Get(IndirectRef iref) const {
+  const Object* Get(IndirectRef iref) const {
     if (!GetChecked(iref)) {
       return kInvalidIndirectRefObject;
     }
@@ -320,7 +320,7 @@
    * The object pointer itself is subject to relocation in some GC
    * implementations, so we shouldn't really be using it here.
    */
-  IndirectRef ToIndirectRef(Object* obj, uint32_t tableIndex) const {
+  IndirectRef ToIndirectRef(const Object* obj, uint32_t tableIndex) const {
     DCHECK_LT(tableIndex, 65536U);
     uint32_t serialChunk = slot_data_[tableIndex].serial;
     uint32_t uref = serialChunk << 20 | (tableIndex << 2) | kind_;
@@ -333,7 +333,7 @@
    * We advance the serial number, invalidating any outstanding references to
    * this slot.
    */
-  void UpdateSlotAdd(Object* obj, int slot) {
+  void UpdateSlotAdd(const Object* obj, int slot) {
     if (slot_data_ != NULL) {
       IndirectRefSlot* pSlot = &slot_data_[slot];
       pSlot->serial++;
@@ -349,7 +349,7 @@
   IRTSegmentState segmentState;
 
   /* bottom of the stack */
-  Object** table_;
+  const Object** table_;
   /* bit mask, ORed into all irefs */
   IndirectRefKind kind_;
   /* extended debugging info */
diff --git a/src/intern_table.cc b/src/intern_table.cc
index 7e3a2f6..7d5be29 100644
--- a/src/intern_table.cc
+++ b/src/intern_table.cc
@@ -16,38 +16,116 @@
 }
 
 size_t InternTable::Size() const {
-  return intern_table_.size();
+  MutexLock mu(intern_table_lock_);
+  return strong_interns_.size() + weak_interns_.size();
 }
 
 void InternTable::VisitRoots(Heap::RootVistor* root_visitor, void* arg) const {
   MutexLock mu(intern_table_lock_);
   typedef Table::const_iterator It; // TODO: C++0x auto
-  for (It it = intern_table_.begin(), end = intern_table_.end(); it != end; ++it) {
+  for (It it = strong_interns_.begin(), end = strong_interns_.end(); it != end; ++it) {
     root_visitor(it->second, arg);
   }
+  // Note: we deliberately don't visit the weak_interns_ table.
 }
 
-String* InternTable::Intern(int32_t utf16_length, const char* utf8_data_in) {
-  UniquePtr<uint16_t[]> utf16_data_out(new uint16_t[utf16_length]);
-  ConvertModifiedUtf8ToUtf16(utf16_data_out.get(), utf8_data_in);
-  int32_t hash_code = ComputeUtf16Hash(utf16_data_out.get(), utf16_length);
-  {
-    MutexLock mu(intern_table_lock_);
-    typedef Table::const_iterator It; // TODO: C++0x auto
-    for (It it = intern_table_.find(hash_code), end = intern_table_.end(); it != end; ++it) {
-      String* string = it->second;
-      if (string->Equals(utf16_data_out.get(), 0, utf16_length)) {
-        return string;
-      }
+const String* InternTable::Lookup(Table& table, const String* s, uint32_t hash_code) {
+  // Requires the intern_table_lock_.
+  typedef Table::const_iterator It; // TODO: C++0x auto
+  for (It it = table.find(hash_code), end = table.end(); it != end; ++it) {
+    const String* existing_string = it->second;
+    if (existing_string->Equals(s)) {
+      return existing_string;
     }
-    String* new_string = String::AllocFromUtf16(utf16_length, utf16_data_out.get(), hash_code);
-    Register(new_string);
-    return new_string;
+  }
+  return NULL;
+}
+
+const String* InternTable::Insert(Table& table, const String* s, uint32_t hash_code) {
+  // Requires the intern_table_lock_.
+  table.insert(std::make_pair(hash_code, s));
+  return s;
+}
+
+void InternTable::RegisterStrong(const String* s) {
+  MutexLock mu(intern_table_lock_);
+  Insert(strong_interns_, s, s->GetHashCode());
+}
+
+void InternTable::Remove(Table& table, const String* s, uint32_t hash_code) {
+  // Requires the intern_table_lock_.
+  typedef Table::const_iterator It; // TODO: C++0x auto
+  for (It it = table.find(hash_code), end = table.end(); it != end; ++it) {
+    if (it->second == s) {
+      table.erase(it);
+      return;
+    }
   }
 }
 
-void InternTable::Register(String* string) {
-  intern_table_.insert(std::make_pair(string->GetHashCode(), string));
+const String* InternTable::Insert(const String* s, bool is_strong) {
+  MutexLock mu(intern_table_lock_);
+
+  DCHECK(s != NULL);
+  uint32_t hash_code = s->GetHashCode();
+
+  if (is_strong) {
+    // Check the strong table for a match.
+    const String* strong = Lookup(strong_interns_, s, hash_code);
+    if (strong != NULL) {
+      return strong;
+    }
+
+    // There is no match in the strong table, check the weak table.
+    const String* weak = Lookup(weak_interns_, s, hash_code);
+    if (weak != NULL) {
+      // A match was found in the weak table. Promote to the strong table.
+      Remove(weak_interns_, weak, hash_code);
+      return Insert(strong_interns_, weak, hash_code);
+    }
+
+    // No match in the strong table or the weak table. Insert into the strong table.
+    return Insert(strong_interns_, s, hash_code);
+  }
+
+  // Check the strong table for a match.
+  const String* strong = Lookup(strong_interns_, s, hash_code);
+  if (strong != NULL) {
+    return strong;
+  }
+  // Check the weak table for a match.
+  const String* weak = Lookup(weak_interns_, s, hash_code);
+  if (weak != NULL) {
+    return weak;
+  }
+  // Insert into the weak table.
+  return Insert(weak_interns_, s, hash_code);
+}
+
+const String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
+  return Insert(String::AllocFromModifiedUtf8(utf16_length, utf8_data), true);
+}
+
+const String* InternTable::InternWeak(const String* s) {
+  return Insert(s, false);
+}
+
+bool InternTable::ContainsWeak(const String* s) {
+  MutexLock mu(intern_table_lock_);
+  const String* found = Lookup(weak_interns_, s, s->GetHashCode());
+  return found == s;
+}
+
+void InternTable::RemoveWeakIf(bool (*predicate)(const String*)) {
+  MutexLock mu(intern_table_lock_);
+  typedef Table::const_iterator It; // TODO: C++0x auto
+  for (It it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
+    if (predicate(it->second)) {
+      weak_interns_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
 }
 
 }  // namespace art
diff --git a/src/intern_table.h b/src/intern_table.h
index 46e0e05..d7e9839 100644
--- a/src/intern_table.h
+++ b/src/intern_table.h
@@ -10,24 +10,51 @@
 
 namespace art {
 
+/**
+ * Used to intern strings.
+ *
+ * There are actually two tables: one that holds strong references to its strings, and one that
+ * holds weak references. The former is used for string literals, for which there is an effective
+ * reference from the constant pool. The latter is used for strings interned at runtime via
+ * String.intern. Some code (XML parsers being a prime example) relies on being able to intern
+ * arbitrarily many strings for the duration of a parse without permanently increasing the memory
+ * footprint.
+ */
 class InternTable {
  public:
   InternTable();
   ~InternTable();
 
-  // intern a potentially new string
-  String* Intern(int32_t utf16_length, const char* utf8_data);
+  // Interns a potentially new string in the 'strong' table. (See above.)
+  const String* InternStrong(int32_t utf16_length, const char* utf8_data);
 
-  // register a String trusting that it is safe to intern.
-  // used when reinitializing InternTable from an image.
-  void Register(String* string);
+  // Interns a potentially new string in the 'weak' table. (See above.)
+  const String* InternWeak(const String* s);
+
+  // Register a String trusting that it is safe to intern.
+  // Used when reinitializing InternTable from an image.
+  void RegisterStrong(const String* s);
+
+  // Removes all weak interns for which 'predicate' is true.
+  void RemoveWeakIf(bool (*predicate)(const String*));
+
+  bool ContainsWeak(const String* s);
 
   size_t Size() const;
+
   void VisitRoots(Heap::RootVistor* root_visitor, void* arg) const;
 
  private:
-  typedef std::tr1::unordered_multimap<int32_t, String*> Table;
-  Table intern_table_;
+  typedef std::tr1::unordered_multimap<int32_t, const String*> Table;
+
+  const String* Insert(const String* s, bool is_strong);
+
+  const String* Lookup(Table& table, const String* s, uint32_t hash_code);
+  const String* Insert(Table& table, const String* s, uint32_t hash_code);
+  void Remove(Table& table, const String* s, uint32_t hash_code);
+
+  Table strong_interns_;
+  Table weak_interns_;
   Mutex* intern_table_lock_;
 };
 
diff --git a/src/intern_table_test.cc b/src/intern_table_test.cc
index a01c6dd..d230a01 100644
--- a/src/intern_table_test.cc
+++ b/src/intern_table_test.cc
@@ -11,10 +11,10 @@
 
 TEST_F(InternTableTest, Intern) {
   InternTable intern_table;
-  String* foo_1 = intern_table.Intern(3, "foo");
-  String* foo_2 = intern_table.Intern(3, "foo");
-  String* foo_3 = String::AllocFromModifiedUtf8("foo");
-  String* bar = intern_table.Intern(3, "bar");
+  const String* foo_1 = intern_table.InternStrong(3, "foo");
+  const String* foo_2 = intern_table.InternStrong(3, "foo");
+  const String* foo_3 = String::AllocFromModifiedUtf8("foo");
+  const String* bar = intern_table.InternStrong(3, "bar");
   EXPECT_TRUE(foo_1->Equals("foo"));
   EXPECT_TRUE(foo_2->Equals("foo"));
   EXPECT_TRUE(foo_3->Equals("foo"));
@@ -26,4 +26,94 @@
   EXPECT_NE(foo_3, bar);
 }
 
+TEST_F(InternTableTest, Size) {
+  InternTable t;
+  EXPECT_EQ(0U, t.Size());
+  t.InternStrong(3, "foo");
+  t.InternWeak(String::AllocFromModifiedUtf8("foo"));
+  EXPECT_EQ(1U, t.Size());
+  t.InternStrong(3, "bar");
+  EXPECT_EQ(2U, t.Size());
+}
+
+std::vector<const String*> gExpectedWeakStrings;
+bool TestPredicate(const String* s) {
+  bool erased = false;
+  typedef std::vector<const String*>::iterator It; // TODO: C++0x auto
+  for (It it = gExpectedWeakStrings.begin(), end = gExpectedWeakStrings.end(); it != end; ++it) {
+    if (*it == s) {
+      gExpectedWeakStrings.erase(it);
+      erased = true;
+      break;
+    }
+  }
+  EXPECT_TRUE(erased);
+  return true;
+}
+
+TEST_F(InternTableTest, RemoveWeakIf) {
+  InternTable t;
+  t.InternStrong(3, "foo");
+  t.InternStrong(3, "bar");
+  const String* s0 = t.InternWeak(String::AllocFromModifiedUtf8("hello"));
+  const String* s1 = t.InternWeak(String::AllocFromModifiedUtf8("world"));
+
+  EXPECT_EQ(4U, t.Size());
+
+  // We should traverse only the weaks...
+  gExpectedWeakStrings.clear();
+  gExpectedWeakStrings.push_back(s0);
+  gExpectedWeakStrings.push_back(s1);
+  t.RemoveWeakIf(TestPredicate);
+  EXPECT_EQ(0U, gExpectedWeakStrings.size());
+
+  EXPECT_EQ(2U, t.Size());
+
+  // Just check that we didn't corrupt the unordered_multimap.
+  t.InternWeak(String::AllocFromModifiedUtf8("still here"));
+  EXPECT_EQ(3U, t.Size());
+}
+
+TEST_F(InternTableTest, ContainsWeak) {
+  {
+    // Strongs are never weak.
+    InternTable t;
+    const String* foo_1 = t.InternStrong(3, "foo");
+    EXPECT_FALSE(t.ContainsWeak(foo_1));
+    const String* foo_2 = t.InternStrong(3, "foo");
+    EXPECT_FALSE(t.ContainsWeak(foo_2));
+    EXPECT_EQ(foo_1, foo_2);
+  }
+
+  {
+    // Weaks are always weak.
+    InternTable t;
+    const String* foo_1 = t.InternWeak(String::AllocFromModifiedUtf8("foo"));
+    EXPECT_TRUE(t.ContainsWeak(foo_1));
+    const String* foo_2 = t.InternWeak(String::AllocFromModifiedUtf8("foo"));
+    EXPECT_TRUE(t.ContainsWeak(foo_2));
+    EXPECT_EQ(foo_1, foo_2);
+  }
+
+  {
+    // A weak can be promoted to a strong.
+    InternTable t;
+    const String* foo_1 = t.InternWeak(String::AllocFromModifiedUtf8("foo"));
+    EXPECT_TRUE(t.ContainsWeak(foo_1));
+    const String* foo_2 = t.InternStrong(3, "foo");
+    EXPECT_FALSE(t.ContainsWeak(foo_2));
+    EXPECT_EQ(foo_1, foo_2);
+  }
+
+  {
+    // Interning a weak after a strong gets you the strong.
+    InternTable t;
+    const String* foo_1 = t.InternStrong(3, "foo");
+    EXPECT_FALSE(t.ContainsWeak(foo_1));
+    const String* foo_2 = t.InternWeak(String::AllocFromModifiedUtf8("foo"));
+    EXPECT_FALSE(t.ContainsWeak(foo_2));
+    EXPECT_EQ(foo_1, foo_2);
+  }
+}
+
 }  // namespace art
diff --git a/src/java_lang_String.cc b/src/java_lang_String.cc
index 9aa5221..fbabd43 100644
--- a/src/java_lang_String.cc
+++ b/src/java_lang_String.cc
@@ -148,8 +148,8 @@
 }
 
 jstring String_intern(JNIEnv* env, jobject javaThis) {
-  String* s = Decode<String*>(env, javaThis);
-  String* result = s->Intern();
+  const String* s = Decode<String*>(env, javaThis);
+  const String* result = s->Intern();
   return AddLocalReference<jstring>(env, result);
 }
 
diff --git a/src/jni_internal.cc b/src/jni_internal.cc
index b222b94..685ac2e 100644
--- a/src/jni_internal.cc
+++ b/src/jni_internal.cc
@@ -63,7 +63,10 @@
  * passed in), or NULL on failure.
  */
 template<typename T>
-T AddLocalReference(JNIEnv* public_env, Object* obj) {
+T AddLocalReference(JNIEnv* public_env, const Object* const_obj) {
+  // The jobject type hierarchy has no notion of const, so it's not worth carrying through.
+  Object* obj = const_cast<Object*>(const_obj);
+
   if (obj == NULL) {
     return NULL;
   }
diff --git a/src/jni_internal.h b/src/jni_internal.h
index 63be779..74c107c 100644
--- a/src/jni_internal.h
+++ b/src/jni_internal.h
@@ -23,7 +23,7 @@
 void JniAbort(const char* jni_function_name);
 
 template<typename T> T Decode(JNIEnv*, jobject);
-template<typename T> T AddLocalReference(JNIEnv*, Object*);
+template<typename T> T AddLocalReference(JNIEnv*, const Object*);
 
 struct JavaVMExt : public JavaVM {
   JavaVMExt(Runtime* runtime, bool check_jni, bool verbose_jni);
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index b803c48..0b61b9a 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -61,7 +61,7 @@
   }
 }
 
-void MarkSweep::MarkObjectVisitor(Object* root, void* arg) {
+void MarkSweep::MarkObjectVisitor(const Object* root, void* arg) {
   DCHECK(root != NULL);
   DCHECK(arg != NULL);
   MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
@@ -108,7 +108,10 @@
 }
 
 void MarkSweep::SweepSystemWeaks() {
+  //Runtime::Current()->GetInternTable().RemoveWeakIf(isUnmarkedObject);
   UNIMPLEMENTED(FATAL);
+  //dvmSweepMonitorList(&gDvm.monitorList, isUnmarkedObject);
+  //sweepWeakJniGlobals();
 }
 
 void MarkSweep::SweepCallback(size_t num_ptrs, void **ptrs, void *arg) {
diff --git a/src/mark_sweep.h b/src/mark_sweep.h
index 00bfc4c..047e357 100644
--- a/src/mark_sweep.h
+++ b/src/mark_sweep.h
@@ -54,7 +54,7 @@
     return mark_bitmap_->Test(object);
   }
 
-  static void MarkObjectVisitor(Object* root, void* arg);
+  static void MarkObjectVisitor(const Object* root, void* arg);
 
   // Marks an object.
   void MarkObject(const Object* obj);
diff --git a/src/object.cc b/src/object.cc
index 6bc3021..b71707f 100644
--- a/src/object.cc
+++ b/src/object.cc
@@ -9,6 +9,7 @@
 #include "class_loader.h"
 #include "globals.h"
 #include "heap.h"
+#include "intern_table.h"
 #include "logging.h"
 #include "dex_cache.h"
 #include "dex_file.h"
@@ -304,7 +305,7 @@
   return object->GetFieldObject(GetOffset());
 }
 
-void Field::SetObj(Object* object, Object* new_value) const {
+void Field::SetObj(Object* object, const Object* new_value) const {
   CHECK((object == NULL) == IsStatic());
   if (IsStatic()) {
     object = declaring_class_;
@@ -406,7 +407,7 @@
   return GetObj(object);
 }
 
-void Field::SetObject(Object* object, Object* l) const {
+void Field::SetObject(Object* object, const Object* l) const {
   CHECK(GetType() == 'L' || GetType() == '[');
   SetObj(object, l);
 }
@@ -680,6 +681,10 @@
   java_lang_String_ = NULL;
 }
 
+const String* String::Intern() const {
+  return Runtime::Current()->GetInternTable()->InternWeak(this);
+}
+
 Class* StackTraceElement::java_lang_StackTraceElement_ = NULL;
 
 void StackTraceElement::SetClass(Class* java_lang_StackTraceElement) {
diff --git a/src/object.h b/src/object.h
index 506e39c..5ae90c9 100644
--- a/src/object.h
+++ b/src/object.h
@@ -222,9 +222,9 @@
     return *reinterpret_cast<Object* const *>(raw_addr);
   }
 
-  void SetFieldObject(size_t offset, Object* new_value) {
+  void SetFieldObject(size_t offset, const Object* new_value) {
     byte* raw_addr = reinterpret_cast<byte*>(this) + offset;
-    *reinterpret_cast<Object**>(raw_addr) = new_value;
+    *reinterpret_cast<const Object**>(raw_addr) = new_value;
     // TODO: write barrier
   }
 
@@ -413,7 +413,7 @@
   double GetDouble(const Object* object) const;
   void SetDouble(Object* object, double d) const;
   Object* GetObject(const Object* object) const;
-  void SetObject(Object* object, Object* l) const;
+  void SetObject(Object* object, const Object* l) const;
 
   // slow path routines for static field access when field was unresolved at compile time
   static uint32_t Get32StaticFromCode(uint32_t field_idx, const Method* referrer);
@@ -425,20 +425,20 @@
 
  public:  // TODO: private
 
-  // private implemention of field access using raw data
+  // private implementation of field access using raw data
   uint32_t Get32(const Object* object) const;
   void Set32(Object* object, uint32_t new_value) const;
   uint64_t Get64(const Object* object) const;
   void Set64(Object* object, uint64_t new_value) const;
   Object* GetObj(const Object* object) const;
-  void SetObj(Object* object, Object* new_value) const;
+  void SetObj(Object* object, const Object* new_value) const;
 
   // Field order required by test "ValidateFieldOrderOfJavaCppUnionClasses".
   // The class in which this field is declared.
   Class* declaring_class_;
   Object* generic_type_;
   uint32_t generic_types_are_initialized_;
-  String* name_;
+  const String* name_;
   uint32_t offset_;
   Class* type_;
 
@@ -559,7 +559,7 @@
   Object* java_generic_parameter_types_;
   Object* java_generic_return_type_;
   Class* java_return_type_;
-  String* name_;
+  const String* name_;
   ObjectArray<Class>* java_parameter_types_;
   uint32_t java_generic_types_are_initialized_;
   uint32_t java_slot_;
@@ -765,7 +765,7 @@
 
   // short cuts to declaring_class_->dex_cache_ members for fast compiled code
   // access
-  ObjectArray<String>* dex_cache_strings_;
+  ObjectArray<const String>* dex_cache_strings_;
   ObjectArray<Class>* dex_cache_resolved_types_;
   ObjectArray<Method>* dex_cache_resolved_methods_;
   ObjectArray<Field>* dex_cache_resolved_fields_;
@@ -1699,10 +1699,7 @@
     return result;
   }
 
-  String* Intern() const {
-    UNIMPLEMENTED(FATAL);
-    return NULL;
-  }
+  const String* Intern() const;
 
  private:
   // Field order required by test "ValidateFieldOrderOfJavaCppUnionClasses".
diff --git a/src/runtime.cc b/src/runtime.cc
index 01abc44..985cdf6 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -10,6 +10,7 @@
 #include "UniquePtr.h"
 #include "class_linker.h"
 #include "heap.h"
+#include "intern_table.h"
 #include "jni_internal.h"
 #include "signal_catcher.h"
 #include "thread.h"
@@ -27,6 +28,7 @@
   Heap::Destroy();
   delete signal_catcher_;
   delete thread_list_;
+  delete intern_table_;
   delete java_vm_;
   Thread::Shutdown();
   // TODO: acquire a static mutex on Runtime to avoid racing.
@@ -316,6 +318,8 @@
   stack_size_ = options->stack_size_;
   thread_list_ = ThreadList::Create();
 
+  intern_table_ = new InternTable;
+
   if (!Heap::Init(options->heap_initial_size_,
                   options->heap_maximum_size_,
                   options->boot_image_)) {
@@ -333,7 +337,7 @@
   Thread* current_thread = Thread::Attach(this);
   thread_list_->Register(current_thread);
 
-  class_linker_ = ClassLinker::Create(options->boot_class_path_, Heap::GetBootSpace());
+  class_linker_ = ClassLinker::Create(options->boot_class_path_, intern_table_, Heap::GetBootSpace());
 
   return true;
 }
@@ -387,7 +391,7 @@
 void Runtime::DumpStatistics(std::ostream& os) {
   // TODO: dump other runtime statistics?
   os << "Loaded classes: " << class_linker_->NumLoadedClasses() << "\n";
-  os << "Intern table size: " << class_linker_->GetInternTable().Size() << "\n";
+  os << "Intern table size: " << GetInternTable()->Size() << "\n";
   // LOGV("VM stats: meth=%d ifld=%d sfld=%d linear=%d",
   //    gDvm.numDeclaredMethods,
   //    gDvm.numDeclaredInstFields,
diff --git a/src/runtime.h b/src/runtime.h
index 2717843..922eeab 100644
--- a/src/runtime.h
+++ b/src/runtime.h
@@ -23,6 +23,7 @@
 class ClassLinker;
 class DexFile;
 class Heap;
+class InternTable;
 class JavaVMExt;
 class SignalCatcher;
 class String;
@@ -92,6 +93,10 @@
     return class_linker_;
   }
 
+  InternTable* GetInternTable() const {
+    return intern_table_;
+  }
+
   JavaVMExt* GetJavaVM() const {
     return java_vm_;
   }
@@ -101,7 +106,7 @@
  private:
   static void PlatformAbort(const char*, int);
 
-  Runtime() : stack_size_(0), thread_list_(NULL), class_linker_(NULL) {}
+  Runtime() : stack_size_(0), thread_list_(NULL), intern_table_(NULL), class_linker_(NULL) {}
 
   void BlockSignals();
 
@@ -114,6 +119,8 @@
 
   ThreadList* thread_list_;
 
+  InternTable* intern_table_;
+
   ClassLinker* class_linker_;
 
   SignalCatcher* signal_catcher_;
diff --git a/src/thread.cc b/src/thread.cc
index cddb429..e3157f8 100644
--- a/src/thread.cc
+++ b/src/thread.cc
@@ -266,7 +266,7 @@
   case kLocal:
     {
       IndirectReferenceTable& locals = jni_env_->locals;
-      result = locals.Get(ref);
+      result = const_cast<Object*>(locals.Get(ref));
       break;
     }
   case kGlobal:
@@ -274,7 +274,7 @@
       JavaVMExt* vm = Runtime::Current()->GetJavaVM();
       IndirectReferenceTable& globals = vm->globals;
       MutexLock mu(vm->globals_lock);
-      result = globals.Get(ref);
+      result = const_cast<Object*>(globals.Get(ref));
       break;
     }
   case kWeakGlobal:
@@ -282,7 +282,7 @@
       JavaVMExt* vm = Runtime::Current()->GetJavaVM();
       IndirectReferenceTable& weak_globals = vm->weak_globals;
       MutexLock mu(vm->weak_globals_lock);
-      result = weak_globals.Get(ref);
+      result = const_cast<Object*>(weak_globals.Get(ref));
       if (result == kClearedJniWeakGlobal) {
         // This is a special case where it's okay to return NULL.
         return NULL;