String hashing cleanup in `InternTable`.
Keep the hash code in `String` as `int32_t` but work with
unsigned hash in `InternTable` and add `static_cast<>`s
where needed. Make sure that the hash code is stored in the
`String` before inserting it in the `InternTable` and avoid
the check whether it's calculated in the hash function. Add
`DCHECK()`s to verify that the stored hash code is correct.
Pass the hash code between `InternTable` functions to avoid
repeatedly retrieving it from the string if the compiler is
unable to prove that the memory location did not change.
Remove unnecessary `*FromTransaction` helper functions that
were just doing a `DCHECK()` and then forwarding to other
functions. Update `Transaction` to do that DCHECK() and call
the needed functions directly.
Make an explicit decision to calculate hash code for all
image strings, including those that are not interned. We
previously calculated hash code for all app image strings
by accident while collecting interned string references.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 181943478
Change-Id: I7cec91e797fdb98ae52f9666620d7b311d465422
diff --git a/dex2oat/linker/image_writer.cc b/dex2oat/linker/image_writer.cc
index 795d621..51daa30 100644
--- a/dex2oat/linker/image_writer.cc
+++ b/dex2oat/linker/image_writer.cc
@@ -353,9 +353,14 @@
// NO_THREAD_SAFETY_ANALYSIS: Avoid locking the `Locks::intern_table_lock_` while single-threaded.
bool ImageWriter::IsStronglyInternedString(ObjPtr<mirror::String> str) NO_THREAD_SAFETY_ANALYSIS {
+ uint32_t hash = static_cast<uint32_t>(str->GetStoredHashCode());
+ if (hash == 0u && str->ComputeHashCode() != 0) {
+ // A string with uninitialized hash code cannot be interned.
+ return false;
+ }
InternTable* intern_table = Runtime::Current()->GetInternTable();
for (InternTable::Table::InternalTable& table : intern_table->strong_interns_.tables_) {
- auto it = table.set_.find(GcRoot<mirror::String>(str));
+ auto it = table.set_.FindWithHash(GcRoot<mirror::String>(str), hash);
if (it != table.set_.end()) {
return it->Read<kWithoutReadBarrier>() == str;
}
@@ -1227,8 +1232,10 @@
MutexLock mu(self, *Locks::intern_table_lock_);
DCHECK_EQ(intern_table->weak_interns_.tables_.size(), 1u);
for (GcRoot<mirror::String>& entry : intern_table->weak_interns_.tables_.front().set_) {
- DCHECK(!IsStronglyInternedString(entry.Read<kWithoutReadBarrier>()));
- intern_table->InsertStrong(entry.Read<kWithoutReadBarrier>());
+ ObjPtr<mirror::String> s = entry.Read<kWithoutReadBarrier>();
+ DCHECK(!IsStronglyInternedString(s));
+ uint32_t hash = static_cast<uint32_t>(s->GetStoredHashCode());
+ intern_table->InsertStrong(s, hash);
}
intern_table->weak_interns_.tables_.front().set_.clear();
}
@@ -2019,8 +2026,9 @@
uint32_t utf16_length;
const char* utf8_data = dex_file->StringDataAndUtf16LengthByIdx(dex::StringIndex(i),
&utf16_length);
- int32_t hash = InternTable::Utf8String::Hash(utf16_length, utf8_data);
- auto intern_it = intern_set.find(InternTable::Utf8String(utf16_length, utf8_data, hash));
+ uint32_t hash = InternTable::Utf8String::Hash(utf16_length, utf8_data);
+ auto intern_it =
+ intern_set.FindWithHash(InternTable::Utf8String(utf16_length, utf8_data), hash);
if (intern_it != intern_set.end()) {
mirror::String* string = intern_it->Read<kWithoutReadBarrier>();
DCHECK(string != nullptr);
@@ -3221,7 +3229,10 @@
} else {
ObjPtr<mirror::ObjectArray<mirror::Class>> class_roots =
Runtime::Current()->GetClassLinker()->GetClassRoots<kWithoutReadBarrier>();
- if (klass == GetClassRoot<mirror::Method, kWithoutReadBarrier>(class_roots) ||
+ if (klass == GetClassRoot<mirror::String, kWithoutReadBarrier>(class_roots)) {
+ // Make sure all image strings have the hash code calculated, even if they are not interned.
+ down_cast<mirror::String*>(copy)->GetHashCode();
+ } else if (klass == GetClassRoot<mirror::Method, kWithoutReadBarrier>(class_roots) ||
klass == GetClassRoot<mirror::Constructor, kWithoutReadBarrier>(class_roots)) {
// Need to update the ArtMethod.
auto* dest = down_cast<mirror::Executable*>(copy);
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 56ede67..580ae03 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1382,7 +1382,10 @@
space_.HasAddress(referred_obj.Ptr()) &&
referred_obj->IsString()) {
ObjPtr<mirror::String> referred_str = referred_obj->AsString();
- auto it = image_interns_.find(GcRoot<mirror::String>(referred_str));
+ uint32_t hash = static_cast<uint32_t>(referred_str->GetStoredHashCode());
+ // All image strings have the hash code calculated, even if they are not interned.
+ DCHECK_EQ(hash, static_cast<uint32_t>(referred_str->ComputeHashCode()));
+ auto it = image_interns_.FindWithHash(GcRoot<mirror::String>(referred_str), hash);
if (it != image_interns_.end() && it->Read() == referred_str) {
++count_;
}
diff --git a/runtime/gc/space/image_space_test.cc b/runtime/gc/space/image_space_test.cc
index 86048bd..3a6d0e1 100644
--- a/runtime/gc/space/image_space_test.cc
+++ b/runtime/gc/space/image_space_test.cc
@@ -151,16 +151,16 @@
const char test_string[] = "SharedBootImageExtensionTestString";
size_t test_string_length = std::size(test_string) - 1u; // Equals UTF-16 length.
- uint32_t hash = ComputeUtf16HashFromModifiedUtf8(test_string, test_string_length);
- InternTable::Utf8String utf8_test_string(test_string_length, test_string, hash);
- auto contains_test_string = [utf8_test_string](ImageSpace* space)
+ uint32_t hash = InternTable::Utf8String::Hash(test_string_length, test_string);
+ InternTable::Utf8String utf8_test_string(test_string_length, test_string);
+ auto contains_test_string = [utf8_test_string, hash](ImageSpace* space)
REQUIRES_SHARED(Locks::mutator_lock_) {
const ImageHeader& image_header = space->GetImageHeader();
if (image_header.GetInternedStringsSection().Size() != 0u) {
const uint8_t* data = space->Begin() + image_header.GetInternedStringsSection().Offset();
size_t read_count;
InternTable::UnorderedSet temp_set(data, /*make_copy_of_data=*/ false, &read_count);
- return temp_set.find(utf8_test_string) != temp_set.end();
+ return temp_set.FindWithHash(utf8_test_string, hash) != temp_set.end();
} else {
return false;
}
diff --git a/runtime/intern_table-inl.h b/runtime/intern_table-inl.h
index a1319f1..a332eae 100644
--- a/runtime/intern_table-inl.h
+++ b/runtime/intern_table-inl.h
@@ -28,7 +28,7 @@
namespace art {
-inline int32_t InternTable::Utf8String::Hash(uint32_t utf16_length, const char* utf8_data) {
+inline uint32_t InternTable::Utf8String::Hash(uint32_t utf16_length, const char* utf8_data) {
DCHECK_EQ(utf16_length, CountModifiedUtf8Chars(utf8_data));
if (LIKELY(utf8_data[utf16_length] == 0)) {
int32_t hash = ComputeUtf16Hash(utf8_data, utf16_length);
@@ -39,13 +39,15 @@
}
}
-inline std::size_t InternTable::StringHash::operator()(const GcRoot<mirror::String>& root) const {
+inline size_t InternTable::StringHash::operator()(const GcRoot<mirror::String>& root) const {
if (kIsDebugBuild) {
Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
}
+ ObjPtr<mirror::String> s = root.Read<kWithoutReadBarrier>();
+ int32_t hash = s->GetStoredHashCode();
+ DCHECK_EQ(hash, s->ComputeHashCode());
// An additional cast to prevent undesired sign extension.
- return static_cast<size_t>(
- static_cast<uint32_t>(root.Read<kWithoutReadBarrier>()->GetHashCode()));
+ return static_cast<uint32_t>(hash);
}
inline bool InternTable::StringEquals::operator()(const GcRoot<mirror::String>& a,
@@ -115,32 +117,35 @@
inline void InternTable::Table::AddInternStrings(UnorderedSet&& intern_strings,
bool is_boot_image) {
- static constexpr bool kCheckDuplicates = kIsDebugBuild;
- if (kCheckDuplicates) {
+ if (kIsDebugBuild) {
// Avoid doing read barriers since the space might not yet be added to the heap.
// See b/117803941
for (GcRoot<mirror::String>& string : intern_strings) {
- CHECK(Find(string.Read<kWithoutReadBarrier>()) == nullptr)
+ ObjPtr<mirror::String> s = string.Read<kWithoutReadBarrier>();
+ uint32_t hash = static_cast<uint32_t>(s->GetStoredHashCode());
+ CHECK_EQ(hash, static_cast<uint32_t>(s->ComputeHashCode()));
+ CHECK(Find(s, hash) == nullptr)
<< "Already found " << string.Read<kWithoutReadBarrier>()->ToModifiedUtf8()
<< " in the intern table";
}
}
+
// Insert at the front since we add new interns into the back.
- tables_.insert(tables_.begin(),
- InternalTable(std::move(intern_strings), is_boot_image));
+ // TODO: Instead, insert before the last unfrozen table since we add new interns into the back.
+ // We want to keep the order of previous frozen tables unchanged, so that we can
+ // can remember the number of searched frozen tables and not search them again.
+ tables_.insert(tables_.begin(), InternalTable(std::move(intern_strings), is_boot_image));
}
template <typename Visitor>
inline void InternTable::VisitInterns(const Visitor& visitor,
bool visit_boot_images,
bool visit_non_boot_images) {
- auto visit_tables = [&](std::vector<Table::InternalTable>& tables)
+ auto visit_tables = [&](dchecked_vector<Table::InternalTable>& tables)
NO_THREAD_SAFETY_ANALYSIS {
for (Table::InternalTable& table : tables) {
- // Determine if we want to visit the table based on the flags..
- const bool visit =
- (visit_boot_images && table.IsBootImage()) ||
- (visit_non_boot_images && !table.IsBootImage());
+ // Determine if we want to visit the table based on the flags.
+ const bool visit = table.IsBootImage() ? visit_boot_images : visit_non_boot_images;
if (visit) {
for (auto& intern : table.set_) {
visitor(intern);
@@ -152,16 +157,13 @@
visit_tables(weak_interns_.tables_);
}
-inline size_t InternTable::CountInterns(bool visit_boot_images,
- bool visit_non_boot_images) const {
+inline size_t InternTable::CountInterns(bool visit_boot_images, bool visit_non_boot_images) const {
size_t ret = 0u;
- auto visit_tables = [&](const std::vector<Table::InternalTable>& tables)
+ auto visit_tables = [&](const dchecked_vector<Table::InternalTable>& tables)
NO_THREAD_SAFETY_ANALYSIS {
for (const Table::InternalTable& table : tables) {
- // Determine if we want to visit the table based on the flags..
- const bool visit =
- (visit_boot_images && table.IsBootImage()) ||
- (visit_non_boot_images && !table.IsBootImage());
+ // Determine if we want to visit the table based on the flags.
+ const bool visit = table.IsBootImage() ? visit_boot_images : visit_non_boot_images;
if (visit) {
ret += table.set_.size();
}
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index e5d4e33..3c11282 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -74,8 +74,20 @@
// The GC moved a root in the log. Need to search the strong interns and update the
// corresponding object. This is slow, but luckily for us, this may only happen with a
// concurrent moving GC.
- strong_interns_.Remove(old_ref);
- strong_interns_.Insert(new_ref);
+ DCHECK(new_ref != nullptr);
+ uint32_t hash = static_cast<uint32_t>(old_ref->GetStoredHashCode());
+ DCHECK_EQ(hash, static_cast<uint32_t>(new_ref->GetStoredHashCode()));
+ DCHECK(new_ref->Equals(old_ref));
+ bool found = false;
+ for (Table::InternalTable& table : strong_interns_.tables_) {
+ auto it = table.set_.FindWithHash(GcRoot<mirror::String>(old_ref), hash);
+ if (it != table.set_.end()) {
+ *it = GcRoot<mirror::String>(new_ref);
+ found = true;
+ break;
+ }
+ }
+ DCHECK(found);
}
}
}
@@ -91,29 +103,41 @@
}
ObjPtr<mirror::String> InternTable::LookupWeak(Thread* self, ObjPtr<mirror::String> s) {
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
MutexLock mu(self, *Locks::intern_table_lock_);
- return LookupWeakLocked(s);
+ return weak_interns_.Find(s, hash);
}
ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self, ObjPtr<mirror::String> s) {
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
MutexLock mu(self, *Locks::intern_table_lock_);
- return LookupStrongLocked(s);
+ return strong_interns_.Find(s, hash);
}
ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self,
uint32_t utf16_length,
const char* utf8_data) {
- int32_t hash = Utf8String::Hash(utf16_length, utf8_data);
+ uint32_t hash = Utf8String::Hash(utf16_length, utf8_data);
MutexLock mu(self, *Locks::intern_table_lock_);
- return strong_interns_.Find(Utf8String(utf16_length, utf8_data, hash));
+ return strong_interns_.Find(Utf8String(utf16_length, utf8_data), hash);
}
ObjPtr<mirror::String> InternTable::LookupWeakLocked(ObjPtr<mirror::String> s) {
- return weak_interns_.Find(s);
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
+ return weak_interns_.Find(s, hash);
}
ObjPtr<mirror::String> InternTable::LookupStrongLocked(ObjPtr<mirror::String> s) {
- return strong_interns_.Find(s);
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
+ return strong_interns_.Find(s, hash);
}
void InternTable::AddNewTable() {
@@ -122,7 +146,7 @@
strong_interns_.AddNewTable();
}
-ObjPtr<mirror::String> InternTable::InsertStrong(ObjPtr<mirror::String> s) {
+ObjPtr<mirror::String> InternTable::InsertStrong(ObjPtr<mirror::String> s, uint32_t hash) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
runtime->RecordStrongStringInsertion(s);
@@ -130,50 +154,29 @@
if (log_new_roots_) {
new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
}
- strong_interns_.Insert(s);
+ strong_interns_.Insert(s, hash);
return s;
}
-ObjPtr<mirror::String> InternTable::InsertWeak(ObjPtr<mirror::String> s) {
+ObjPtr<mirror::String> InternTable::InsertWeak(ObjPtr<mirror::String> s, uint32_t hash) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
runtime->RecordWeakStringInsertion(s);
}
- weak_interns_.Insert(s);
+ weak_interns_.Insert(s, hash);
return s;
}
-void InternTable::RemoveStrong(ObjPtr<mirror::String> s) {
- strong_interns_.Remove(s);
+void InternTable::RemoveStrong(ObjPtr<mirror::String> s, uint32_t hash) {
+ strong_interns_.Remove(s, hash);
}
-void InternTable::RemoveWeak(ObjPtr<mirror::String> s) {
+void InternTable::RemoveWeak(ObjPtr<mirror::String> s, uint32_t hash) {
Runtime* runtime = Runtime::Current();
if (runtime->IsActiveTransaction()) {
runtime->RecordWeakStringRemoval(s);
}
- weak_interns_.Remove(s);
-}
-
-// Insert/remove methods used to undo changes made during an aborted transaction.
-ObjPtr<mirror::String> InternTable::InsertStrongFromTransaction(ObjPtr<mirror::String> s) {
- DCHECK(!Runtime::Current()->IsActiveTransaction());
- return InsertStrong(s);
-}
-
-ObjPtr<mirror::String> InternTable::InsertWeakFromTransaction(ObjPtr<mirror::String> s) {
- DCHECK(!Runtime::Current()->IsActiveTransaction());
- return InsertWeak(s);
-}
-
-void InternTable::RemoveStrongFromTransaction(ObjPtr<mirror::String> s) {
- DCHECK(!Runtime::Current()->IsActiveTransaction());
- RemoveStrong(s);
-}
-
-void InternTable::RemoveWeakFromTransaction(ObjPtr<mirror::String> s) {
- DCHECK(!Runtime::Current()->IsActiveTransaction());
- RemoveWeak(s);
+ weak_interns_.Remove(s, hash);
}
void InternTable::BroadcastForNewInterns() {
@@ -195,10 +198,10 @@
Locks::intern_table_lock_->ExclusiveLock(self);
}
-ObjPtr<mirror::String> InternTable::Insert(ObjPtr<mirror::String> s, bool is_strong) {
- if (s == nullptr) {
- return nullptr;
- }
+ObjPtr<mirror::String> InternTable::Insert(ObjPtr<mirror::String> s, uint32_t hash, bool is_strong) {
+ DCHECK(s != nullptr);
+ DCHECK_EQ(hash, static_cast<uint32_t>(s->GetStoredHashCode()));
+ DCHECK_IMPLIES(hash == 0u, s->ComputeHashCode() == 0);
Thread* const self = Thread::Current();
MutexLock mu(self, *Locks::intern_table_lock_);
if (kDebugLocking) {
@@ -207,7 +210,7 @@
}
while (true) {
// Check the strong table for a match.
- ObjPtr<mirror::String> strong = LookupStrongLocked(s);
+ ObjPtr<mirror::String> strong = strong_interns_.Find(s, hash);
if (strong != nullptr) {
return strong;
}
@@ -228,28 +231,28 @@
CHECK(self->GetWeakRefAccessEnabled());
}
// There is no match in the strong table, check the weak table.
- ObjPtr<mirror::String> weak = LookupWeakLocked(s);
+ ObjPtr<mirror::String> weak = weak_interns_.Find(s, hash);
if (weak != nullptr) {
if (is_strong) {
// A match was found in the weak table. Promote to the strong table.
- RemoveWeak(weak);
- return InsertStrong(weak);
+ RemoveWeak(weak, hash);
+ return InsertStrong(weak, hash);
}
return weak;
}
// No match in the strong table or the weak table. Insert into the strong / weak table.
- return is_strong ? InsertStrong(s) : InsertWeak(s);
+ return is_strong ? InsertStrong(s, hash) : InsertWeak(s, hash);
}
ObjPtr<mirror::String> InternTable::InternStrong(uint32_t utf16_length, const char* utf8_data) {
DCHECK(utf8_data != nullptr);
- int32_t hash = Utf8String::Hash(utf16_length, utf8_data);
+ uint32_t hash = Utf8String::Hash(utf16_length, utf8_data);
Thread* self = Thread::Current();
ObjPtr<mirror::String> s;
{
// Try to avoid allocation. If we need to allocate, release the mutex before the allocation.
MutexLock mu(self, *Locks::intern_table_lock_);
- s = strong_interns_.Find(Utf8String(utf16_length, utf8_data, hash));
+ s = strong_interns_.Find(Utf8String(utf16_length, utf8_data), hash);
}
if (s != nullptr) {
return s;
@@ -262,35 +265,44 @@
self->AssertPendingOOMException();
return nullptr;
}
- if (kIsDebugBuild) {
- int32_t string_hash = s->GetHashCode(); // Implicitly sets the hash code.
- CHECK_EQ(hash, string_hash);
- } else {
- s->SetHashCode(hash);
- }
- return Insert(s, /*is_strong=*/ true);
+ s->SetHashCode(static_cast<int32_t>(hash));
+ return Insert(s, hash, /*is_strong=*/ true);
}
ObjPtr<mirror::String> InternTable::InternStrong(const char* utf8_data) {
DCHECK(utf8_data != nullptr);
- return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
+ Thread* self = Thread::Current();
+ ObjPtr<mirror::String> s = mirror::String::AllocFromModifiedUtf8(self, utf8_data);
+ if (UNLIKELY(s == nullptr)) {
+ self->AssertPendingOOMException();
+ return nullptr;
+ }
+ return InternStrong(s);
}
ObjPtr<mirror::String> InternTable::InternStrong(ObjPtr<mirror::String> s) {
- return Insert(s, /*is_strong=*/ true);
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
+ return Insert(s, hash, /*is_strong=*/ true);
}
ObjPtr<mirror::String> InternTable::InternWeak(const char* utf8_data) {
DCHECK(utf8_data != nullptr);
- return InternWeak(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
+ Thread* self = Thread::Current();
+ ObjPtr<mirror::String> s = mirror::String::AllocFromModifiedUtf8(self, utf8_data);
+ if (UNLIKELY(s == nullptr)) {
+ self->AssertPendingOOMException();
+ return nullptr;
+ }
+ return InternWeak(s);
}
ObjPtr<mirror::String> InternTable::InternWeak(ObjPtr<mirror::String> s) {
- return Insert(s, /*is_strong=*/ false);
-}
-
-bool InternTable::ContainsWeak(ObjPtr<mirror::String> s) {
- return LookupWeak(Thread::Current(), s) == s;
+ DCHECK(s != nullptr);
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ uint32_t hash = static_cast<uint32_t>(s->GetHashCode());
+ return Insert(s, hash, /*is_strong=*/ false);
}
void InternTable::SweepInternTableWeaks(IsMarkedVisitor* visitor) {
@@ -298,9 +310,11 @@
weak_interns_.SweepWeaks(visitor);
}
-void InternTable::Table::Remove(ObjPtr<mirror::String> s) {
+void InternTable::Table::Remove(ObjPtr<mirror::String> s, uint32_t hash) {
+ // Note: We can remove weak interns even from frozen tables when promoting to strong interns.
+ // We can remove strong interns only for a transaction rollback.
for (InternalTable& table : tables_) {
- auto it = table.set_.find(GcRoot<mirror::String>(s));
+ auto it = table.set_.FindWithHash(GcRoot<mirror::String>(s), hash);
if (it != table.set_.end()) {
table.set_.erase(it);
return;
@@ -309,10 +323,10 @@
LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
}
-ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s) {
+ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s, uint32_t hash) {
Locks::intern_table_lock_->AssertHeld(Thread::Current());
for (InternalTable& table : tables_) {
- auto it = table.set_.find(GcRoot<mirror::String>(s));
+ auto it = table.set_.FindWithHash(GcRoot<mirror::String>(s), hash);
if (it != table.set_.end()) {
return it->Read();
}
@@ -320,10 +334,10 @@
return nullptr;
}
-ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string) {
+ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string, uint32_t hash) {
Locks::intern_table_lock_->AssertHeld(Thread::Current());
for (InternalTable& table : tables_) {
- auto it = table.set_.find(string);
+ auto it = table.set_.FindWithHash(string, hash);
if (it != table.set_.end()) {
return it->Read();
}
@@ -340,11 +354,11 @@
tables_.push_back(std::move(new_table));
}
-void InternTable::Table::Insert(ObjPtr<mirror::String> s) {
+void InternTable::Table::Insert(ObjPtr<mirror::String> s, uint32_t hash) {
// Always insert the last table, the image tables are before and we avoid inserting into these
// to prevent dirty pages.
DCHECK(!tables_.empty());
- tables_.back().set_.insert(GcRoot<mirror::String>(s));
+ tables_.back().set_.PutWithHash(GcRoot<mirror::String>(s), hash);
}
void InternTable::Table::VisitRoots(RootVisitor* visitor) {
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index ad1b68e..c0c761a 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -18,6 +18,7 @@
#define ART_RUNTIME_INTERN_TABLE_H_
#include "base/allocator.h"
+#include "base/dchecked_vector.h"
#include "base/hash_set.h"
#include "base/mutex.h"
#include "gc/weak_root_state.h"
@@ -59,38 +60,41 @@
// Modified UTF-8-encoded string treated as UTF16.
class Utf8String {
public:
- Utf8String(uint32_t utf16_length, const char* utf8_data, int32_t hash)
- : hash_(hash), utf16_length_(utf16_length), utf8_data_(utf8_data) { }
+ Utf8String(uint32_t utf16_length, const char* utf8_data)
+ : utf16_length_(utf16_length), utf8_data_(utf8_data) { }
- int32_t GetHash() const { return hash_; }
+ uint32_t GetHash() const { return Hash(utf16_length_, utf8_data_); }
uint32_t GetUtf16Length() const { return utf16_length_; }
const char* GetUtf8Data() const { return utf8_data_; }
- static int32_t Hash(uint32_t utf16_length, const char* utf8_data);
+ static uint32_t Hash(uint32_t utf16_length, const char* utf8_data);
private:
- int32_t hash_;
uint32_t utf16_length_;
const char* utf8_data_;
};
class StringHash {
public:
- std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
+ // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions.
+ size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
- // Utf8String can be used for lookup.
- std::size_t operator()(const Utf8String& key) const {
- // A cast to prevent undesired sign extension.
- return static_cast<uint32_t>(key.GetHash());
+ // Utf8String can be used for lookup. While we're passing the hash explicitly to all
+ // `HashSet<>` functions, they `DCHECK()` the supplied hash against the hash we provide here.
+ size_t operator()(const Utf8String& key) const {
+ static_assert(std::is_same_v<uint32_t, decltype(key.GetHash())>);
+ return key.GetHash();
}
};
class StringEquals {
public:
+ // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions.
bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
NO_THREAD_SAFETY_ANALYSIS;
// Utf8String can be used for lookup.
+ // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions.
bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const
NO_THREAD_SAFETY_ANALYSIS;
};
@@ -137,9 +141,6 @@
void SweepInternTableWeaks(IsMarkedVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_)
REQUIRES(!Locks::intern_table_lock_);
- bool ContainsWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!Locks::intern_table_lock_);
-
// Lookup a strong intern, returns null if not found.
ObjPtr<mirror::String> LookupStrong(Thread* self, ObjPtr<mirror::String> s)
REQUIRES(!Locks::intern_table_lock_)
@@ -235,13 +236,13 @@
};
Table();
- ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(Locks::intern_table_lock_);
- ObjPtr<mirror::String> Find(const Utf8String& string) REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(Locks::intern_table_lock_);
- void Insert(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(Locks::intern_table_lock_);
- void Remove(ObjPtr<mirror::String> s)
+ ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s, uint32_t hash)
+ REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
+ ObjPtr<mirror::String> Find(const Utf8String& string, uint32_t hash)
+ REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
+ void Insert(ObjPtr<mirror::String> s, uint32_t hash)
+ REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
+ void Remove(ObjPtr<mirror::String> s, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
void VisitRoots(RootVisitor* visitor)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
@@ -268,7 +269,7 @@
// We call AddNewTable when we create the zygote to reduce private dirty pages caused by
// modifying the zygote intern table. The back of table is modified when strings are interned.
- std::vector<InternalTable> tables_;
+ dchecked_vector<InternalTable> tables_;
friend class InternTable;
friend class linker::ImageWriter;
@@ -276,7 +277,7 @@
};
// Insert if non null, otherwise return null. Must be called holding the mutator lock.
- ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, bool is_strong)
+ ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, uint32_t hash, bool is_strong)
REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_);
// Add a table from memory to the strong interns.
@@ -284,23 +285,14 @@
size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image)
REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_);
- ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s)
+ // Note: Transaction rollback calls these helper functions directly.
+ ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s)
+ ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- void RemoveStrong(ObjPtr<mirror::String> s)
+ void RemoveStrong(ObjPtr<mirror::String> s, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- void RemoveWeak(ObjPtr<mirror::String> s)
- REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
-
- // Transaction rollback access.
- ObjPtr<mirror::String> InsertStrongFromTransaction(ObjPtr<mirror::String> s)
- REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- ObjPtr<mirror::String> InsertWeakFromTransaction(ObjPtr<mirror::String> s)
- REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- void RemoveStrongFromTransaction(ObjPtr<mirror::String> s)
- REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
- void RemoveWeakFromTransaction(ObjPtr<mirror::String> s)
+ void RemoveWeak(ObjPtr<mirror::String> s, uint32_t hash)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
// Change the weak root state. May broadcast to waiters.
@@ -318,7 +310,7 @@
// directly access the strings in it. Use functions that contain
// read barriers.
Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_);
- std::vector<GcRoot<mirror::String>> new_strong_intern_roots_
+ dchecked_vector<GcRoot<mirror::String>> new_strong_intern_roots_
GUARDED_BY(Locks::intern_table_lock_);
// Since this contains (weak) roots, they need a read barrier. Do
// not directly access the strings in it. Use functions that contain
diff --git a/runtime/intern_table_test.cc b/runtime/intern_table_test.cc
index e4eed55..9900c2a 100644
--- a/runtime/intern_table_test.cc
+++ b/runtime/intern_table_test.cc
@@ -75,12 +75,15 @@
InternTable t;
// A string that has a negative hash value.
- GcRoot<mirror::String> str(mirror::String::AllocFromModifiedUtf8(soa.Self(), "00000000"));
+ ObjPtr<mirror::String> str = mirror::String::AllocFromModifiedUtf8(soa.Self(), "00000000");
+ // `String::GetHashCode()` ensures that the stored hash is calculated.
+ int32_t hash = str->GetHashCode();
+ ASSERT_LT(hash, 0);
MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
for (InternTable::Table::InternalTable& table : t.strong_interns_.tables_) {
// The negative hash value shall be 32-bit wide on every host.
- ASSERT_TRUE(IsUint<32>(table.set_.hashfn_(str)));
+ ASSERT_TRUE(IsUint<32>(table.set_.hashfn_(GcRoot<mirror::String>(str))));
}
}
@@ -146,14 +149,19 @@
TEST_F(InternTableTest, ContainsWeak) {
ScopedObjectAccess soa(Thread::Current());
+ auto ContainsWeak = [&](InternTable& t, ObjPtr<mirror::String> s)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ return t.LookupWeak(soa.Self(), s) == s;
+ };
+
{
// Strongs are never weak.
InternTable t;
StackHandleScope<2> hs(soa.Self());
Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternStrong(3, "foo")));
- EXPECT_FALSE(t.ContainsWeak(interned_foo_1.Get()));
+ EXPECT_FALSE(ContainsWeak(t, interned_foo_1.Get()));
Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternStrong(3, "foo")));
- EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get()));
+ EXPECT_FALSE(ContainsWeak(t, interned_foo_2.Get()));
EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get());
}
@@ -168,7 +176,7 @@
EXPECT_NE(foo_1.Get(), foo_2.Get());
Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternWeak(foo_1.Get())));
Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternWeak(foo_2.Get())));
- EXPECT_TRUE(t.ContainsWeak(interned_foo_2.Get()));
+ EXPECT_TRUE(ContainsWeak(t, interned_foo_2.Get()));
EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get());
}
@@ -179,9 +187,9 @@
Handle<mirror::String> foo(
hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo")));
Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternWeak(foo.Get())));
- EXPECT_TRUE(t.ContainsWeak(interned_foo_1.Get()));
+ EXPECT_TRUE(ContainsWeak(t, interned_foo_1.Get()));
Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternStrong(3, "foo")));
- EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get()));
+ EXPECT_FALSE(ContainsWeak(t, interned_foo_2.Get()));
EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get());
}
@@ -190,11 +198,11 @@
InternTable t;
StackHandleScope<3> hs(soa.Self());
Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternStrong(3, "foo")));
- EXPECT_FALSE(t.ContainsWeak(interned_foo_1.Get()));
+ EXPECT_FALSE(ContainsWeak(t, interned_foo_1.Get()));
Handle<mirror::String> foo(
hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo")));
Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternWeak(foo.Get())));
- EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get()));
+ EXPECT_FALSE(ContainsWeak(t, interned_foo_2.Get()));
EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get());
}
}
@@ -234,4 +242,20 @@
EXPECT_TRUE(lookup_foobbS == nullptr);
}
+TEST_F(InternTableTest, InternStrongFrozenWeak) {
+ ScopedObjectAccess soa(Thread::Current());
+ InternTable intern_table;
+ StackHandleScope<1> hs(soa.Self());
+ Handle<mirror::String> foo(
+ hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo")));
+ ASSERT_TRUE(foo != nullptr);
+ ObjPtr<mirror::String> weak_foo = intern_table.InternWeak(foo.Get());
+ ASSERT_TRUE(weak_foo == foo.Get());
+
+ intern_table.AddNewTable();
+
+ ObjPtr<mirror::String> strong_foo = intern_table.InternStrong(foo.Get());
+ ASSERT_TRUE(strong_foo == foo.Get());
+}
+
} // namespace art
diff --git a/runtime/mirror/string-inl.h b/runtime/mirror/string-inl.h
index 8c1d13b..5903872 100644
--- a/runtime/mirror/string-inl.h
+++ b/runtime/mirror/string-inl.h
@@ -67,20 +67,19 @@
return -1;
}
+inline int32_t String::ComputeHashCode() {
+ uint32_t hash = IsCompressed()
+ ? ComputeUtf16Hash(GetValueCompressed(), GetLength())
+ : ComputeUtf16Hash(GetValue(), GetLength());
+ return static_cast<int32_t>(hash);
+}
+
inline int32_t String::GetHashCode() {
- int32_t result = GetField32(OFFSET_OF_OBJECT_MEMBER(String, hash_code_));
+ int32_t result = GetStoredHashCode();
if (UNLIKELY(result == 0)) {
- result = ComputeHashCode();
+ result = ComputeAndSetHashCode();
}
- if (kIsDebugBuild) {
- if (IsCompressed()) {
- DCHECK_IMPLIES(result == 0, ComputeUtf16Hash(GetValueCompressed(), GetLength()) == 0)
- << ToModifiedUtf8() << " " << result;
- } else {
- DCHECK_IMPLIES(result == 0, ComputeUtf16Hash(GetValue(), GetLength()) == 0)
- << ToModifiedUtf8() << " " << result;
- }
- }
+ DCHECK_IMPLIES(result == 0, ComputeHashCode() == 0) << ToModifiedUtf8();
return result;
}
diff --git a/runtime/mirror/string.cc b/runtime/mirror/string.cc
index 75282aa..d059278 100644
--- a/runtime/mirror/string.cc
+++ b/runtime/mirror/string.cc
@@ -48,15 +48,10 @@
}
}
-int String::ComputeHashCode() {
- int32_t hash_code = 0;
- if (IsCompressed()) {
- hash_code = ComputeUtf16Hash(GetValueCompressed(), GetLength());
- } else {
- hash_code = ComputeUtf16Hash(GetValue(), GetLength());
- }
- SetHashCode(hash_code);
- return hash_code;
+int32_t String::ComputeAndSetHashCode() {
+ int32_t new_hash_code = ComputeHashCode();
+ SetHashCode(new_hash_code);
+ return new_hash_code;
}
inline bool String::AllASCIIExcept(const uint16_t* chars, int32_t length, uint16_t non_ascii) {
diff --git a/runtime/mirror/string.h b/runtime/mirror/string.h
index 66e0151..2eb8e0a 100644
--- a/runtime/mirror/string.h
+++ b/runtime/mirror/string.h
@@ -105,9 +105,13 @@
SetField32<false, false>(OFFSET_OF_OBJECT_MEMBER(String, count_), new_count);
}
+ int32_t GetStoredHashCode() REQUIRES_SHARED(Locks::mutator_lock_) {
+ return GetField32(OFFSET_OF_OBJECT_MEMBER(String, hash_code_));
+ }
+
int32_t GetHashCode() REQUIRES_SHARED(Locks::mutator_lock_);
- // Computes, stores, and returns the hash code.
+ // Computes and returns the hash code.
int32_t ComputeHashCode() REQUIRES_SHARED(Locks::mutator_lock_);
int32_t GetUtfLength() REQUIRES_SHARED(Locks::mutator_lock_);
@@ -257,11 +261,21 @@
private:
static bool AllASCIIExcept(const uint16_t* chars, int32_t length, uint16_t non_ascii);
+ // Computes, stores, and returns the hash code.
+ int32_t ComputeAndSetHashCode() REQUIRES_SHARED(Locks::mutator_lock_);
+
void SetHashCode(int32_t new_hash_code) REQUIRES_SHARED(Locks::mutator_lock_) {
- // Hash code is invariant so use non-transactional mode. Also disable check as we may run inside
- // a transaction.
- DCHECK_EQ(0, GetField32(OFFSET_OF_OBJECT_MEMBER(String, hash_code_)));
- SetField32<false, false>(OFFSET_OF_OBJECT_MEMBER(String, hash_code_), new_hash_code);
+ if (kIsDebugBuild) {
+ CHECK_EQ(new_hash_code, ComputeHashCode());
+ int32_t old_hash_code = GetStoredHashCode();
+ // Another thread could have raced this one and set the hash code.
+ CHECK(old_hash_code == 0 || old_hash_code == new_hash_code)
+ << "old: " << old_hash_code << " new: " << new_hash_code;
+ }
+ // Hash code is invariant so use non-transactional mode, allowing a failed transaction
+ // to set the hash code anyway. Also disable check as we may run inside a transaction.
+ SetField32</*kTransactionActive=*/ false, /*kCheckTransaction=*/ false>(
+ OFFSET_OF_OBJECT_MEMBER(String, hash_code_), new_hash_code);
}
// Field order required by test "ValidateFieldOrderOfJavaCppUnionClasses".
diff --git a/runtime/transaction.cc b/runtime/transaction.cc
index 193c111..006aa56 100644
--- a/runtime/transaction.cc
+++ b/runtime/transaction.cc
@@ -600,15 +600,18 @@
}
void Transaction::InternStringLog::Undo(InternTable* intern_table) const {
+ DCHECK(!Runtime::Current()->IsActiveTransaction());
DCHECK(intern_table != nullptr);
+ ObjPtr<mirror::String> s = str_.Read();
+ uint32_t hash = static_cast<uint32_t>(s->GetStoredHashCode());
switch (string_op_) {
case InternStringLog::kInsert: {
switch (string_kind_) {
case InternStringLog::kStrongString:
- intern_table->RemoveStrongFromTransaction(str_.Read());
+ intern_table->RemoveStrong(s, hash);
break;
case InternStringLog::kWeakString:
- intern_table->RemoveWeakFromTransaction(str_.Read());
+ intern_table->RemoveWeak(s, hash);
break;
default:
LOG(FATAL) << "Unknown interned string kind";
@@ -619,10 +622,10 @@
case InternStringLog::kRemove: {
switch (string_kind_) {
case InternStringLog::kStrongString:
- intern_table->InsertStrongFromTransaction(str_.Read());
+ intern_table->InsertStrong(s, hash);
break;
case InternStringLog::kWeakString:
- intern_table->InsertWeakFromTransaction(str_.Read());
+ intern_table->InsertWeak(s, hash);
break;
default:
LOG(FATAL) << "Unknown interned string kind";