Fully implement string interning.
Also, more const.
Change-Id: I09cae88d677e8e6e42d0fa9b5d1093c79d225e66
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 01abc440..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;
