runtime/intern_table.cc - SHIFTPHONES/android_art - Gitiles

 /*
  * Copyright (C) 2011 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "intern_table-inl.h"

 #include <memory>

 #include "dex/utf.h"
 #include "gc/collector/garbage_collector.h"
 #include "gc/space/image_space.h"
 #include "gc/weak_root_state.h"
 #include "gc_root-inl.h"
 #include "handle_scope-inl.h"
 #include "image-inl.h"
 #include "mirror/dex_cache-inl.h"
 #include "mirror/object-inl.h"
 #include "mirror/object_array-inl.h"
 #include "mirror/string-inl.h"
 #include "object_callbacks.h"
 #include "scoped_thread_state_change-inl.h"
 #include "thread.h"
 #include "thread-inl.h"

 namespace art {

 InternTable::InternTable()
     : log_new_roots_(false),
       weak_intern_condition_("New intern condition", *Locks::intern_table_lock_),
       weak_root_state_(gc::kWeakRootStateNormal) {
 }

 size_t InternTable::Size() const {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   return strong_interns_.Size() + weak_interns_.Size();
 }

 size_t InternTable::StrongSize() const {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   return strong_interns_.Size();
 }

 size_t InternTable::WeakSize() const {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   return weak_interns_.Size();
 }

 void InternTable::DumpForSigQuit(std::ostream& os) const {
   os << "Intern table: " << StrongSize() << " strong; " << WeakSize() << " weak\n";
 }

 void InternTable::VisitRoots(RootVisitor* visitor, VisitRootFlags flags) {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   if ((flags & kVisitRootFlagAllRoots) != 0) {
     strong_interns_.VisitRoots(visitor);
   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
     for (auto& root : new_strong_intern_roots_) {
       ObjPtr<mirror::String> old_ref = root.Read<kWithoutReadBarrier>();
       root.VisitRoot(visitor, RootInfo(kRootInternedString));
       ObjPtr<mirror::String> new_ref = root.Read<kWithoutReadBarrier>();
       if (new_ref != old_ref) {
         // 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.
         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);
       }
     }
   }
   if ((flags & kVisitRootFlagClearRootLog) != 0) {
     new_strong_intern_roots_.clear();
   }
   if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
     log_new_roots_ = true;
   } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
     log_new_roots_ = false;
   }
   // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
 }

 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 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 strong_interns_.Find(s, hash);
 }

 ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self,
                                                  uint32_t utf16_length,
                                                  const char* 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);
 }

 ObjPtr<mirror::String> InternTable::LookupWeakLocked(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());
   return weak_interns_.Find(s, hash);
 }

 ObjPtr<mirror::String> InternTable::LookupStrongLocked(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());
   return strong_interns_.Find(s, hash);
 }

 void InternTable::AddNewTable() {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   weak_interns_.AddNewTable();
   strong_interns_.AddNewTable();
 }

 ObjPtr<mirror::String> InternTable::InsertStrong(ObjPtr<mirror::String> s, uint32_t hash) {
   Runtime* runtime = Runtime::Current();
   if (runtime->IsActiveTransaction()) {
     runtime->RecordStrongStringInsertion(s);
   }
   if (log_new_roots_) {
     new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
   }
   strong_interns_.Insert(s, hash);
   return 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, hash);
   return s;
 }

 void InternTable::RemoveStrong(ObjPtr<mirror::String> s, uint32_t hash) {
   strong_interns_.Remove(s, hash);
 }

 void InternTable::RemoveWeak(ObjPtr<mirror::String> s, uint32_t hash) {
   Runtime* runtime = Runtime::Current();
   if (runtime->IsActiveTransaction()) {
     runtime->RecordWeakStringRemoval(s);
   }
   weak_interns_.Remove(s, hash);
 }

 void InternTable::BroadcastForNewInterns() {
   Thread* self = Thread::Current();
   MutexLock mu(self, *Locks::intern_table_lock_);
   weak_intern_condition_.Broadcast(self);
 }

 void InternTable::WaitUntilAccessible(Thread* self) {
   Locks::intern_table_lock_->ExclusiveUnlock(self);
   {
     ScopedThreadSuspension sts(self, ThreadState::kWaitingWeakGcRootRead);
     MutexLock mu(self, *Locks::intern_table_lock_);
     while ((!kUseReadBarrier && weak_root_state_ == gc::kWeakRootStateNoReadsOrWrites) ||
            (kUseReadBarrier && !self->GetWeakRefAccessEnabled())) {
       weak_intern_condition_.Wait(self);
     }
   }
   Locks::intern_table_lock_->ExclusiveLock(self);
 }

 ObjPtr<mirror::String> InternTable::Insert(ObjPtr<mirror::String> s,
                                            uint32_t hash,
                                            bool is_strong,
                                            size_t num_searched_strong_frozen_tables) {
   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) {
     Locks::mutator_lock_->AssertSharedHeld(self);
     CHECK_EQ(2u, self->NumberOfHeldMutexes()) << "may only safely hold the mutator lock";
   }
   while (true) {
     // Check the strong table for a match.
     ObjPtr<mirror::String> strong =
         strong_interns_.Find(s, hash, num_searched_strong_frozen_tables);
     if (strong != nullptr) {
       return strong;
     }
     if (kUseReadBarrier ? self->GetWeakRefAccessEnabled()
                         : weak_root_state_ != gc::kWeakRootStateNoReadsOrWrites) {
       break;
     }
     num_searched_strong_frozen_tables = strong_interns_.tables_.size() - 1u;
     // weak_root_state_ is set to gc::kWeakRootStateNoReadsOrWrites in the GC pause but is only
     // cleared after SweepSystemWeaks has completed. This is why we need to wait until it is
     // cleared.
     StackHandleScope<1> hs(self);
     auto h = hs.NewHandleWrapper(&s);
     WaitUntilAccessible(self);
   }
   if (!kUseReadBarrier) {
     CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
   } else {
     CHECK(self->GetWeakRefAccessEnabled());
   }
   // There is no match in the strong table, check the weak table.
   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, 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, hash) : InsertWeak(s, hash);
 }

 ObjPtr<mirror::String> InternTable::InternStrong(uint32_t utf16_length, const char* utf8_data) {
   DCHECK(utf8_data != nullptr);
   uint32_t hash = Utf8String::Hash(utf16_length, utf8_data);
   Thread* self = Thread::Current();
   ObjPtr<mirror::String> s;
   size_t num_searched_strong_frozen_tables;
   {
     // Try to avoid allocation. If we need to allocate, release the mutex before the allocation.
     MutexLock mu(self, *Locks::intern_table_lock_);
     DCHECK(!strong_interns_.tables_.empty());
     num_searched_strong_frozen_tables = strong_interns_.tables_.size() - 1u;
     s = strong_interns_.Find(Utf8String(utf16_length, utf8_data), hash);
   }
   if (s != nullptr) {
     return s;
   }
   bool is_ascii = (utf8_data[utf16_length] == 0);
   int32_t utf8_length = utf16_length + (LIKELY(is_ascii) ? 0 : strlen(utf8_data + utf16_length));
   DCHECK_EQ(static_cast<size_t>(utf8_length), strlen(utf8_data));
   s = mirror::String::AllocFromModifiedUtf8(self, utf16_length, utf8_data, utf8_length);
   if (UNLIKELY(s == nullptr)) {
     self->AssertPendingOOMException();
     return nullptr;
   }
   s->SetHashCode(static_cast<int32_t>(hash));
   return Insert(s, hash, /*is_strong=*/ true, num_searched_strong_frozen_tables);
 }

 ObjPtr<mirror::String> InternTable::InternStrong(const char* utf8_data) {
   DCHECK(utf8_data != nullptr);
   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) {
   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);
   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) {
   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) {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   weak_interns_.SweepWeaks(visitor);
 }

 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_.FindWithHash(GcRoot<mirror::String>(s), hash);
     if (it != table.set_.end()) {
       table.set_.erase(it);
       return;
     }
   }
   LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
 }

 FLATTEN
 ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s,
                                                 uint32_t hash,
                                                 size_t num_searched_frozen_tables) {
   Locks::intern_table_lock_->AssertHeld(Thread::Current());
   auto mid = tables_.begin() + num_searched_frozen_tables;
   for (Table::InternalTable& table : MakeIterationRange(tables_.begin(), mid)) {
     DCHECK(table.set_.FindWithHash(GcRoot<mirror::String>(s), hash) == table.set_.end());
   }
   // Search from the last table, assuming that apps shall search for their own
   // strings more often than for boot image strings.
   for (Table::InternalTable& table : ReverseRange(MakeIterationRange(mid, tables_.end()))) {
     auto it = table.set_.FindWithHash(GcRoot<mirror::String>(s), hash);
     if (it != table.set_.end()) {
       return it->Read();
     }
   }
   return nullptr;
 }

 FLATTEN
 ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string, uint32_t hash) {
   Locks::intern_table_lock_->AssertHeld(Thread::Current());
   // Search from the last table, assuming that apps shall search for their own
   // strings more often than for boot image strings.
   for (InternalTable& table : ReverseRange(tables_)) {
     auto it = table.set_.FindWithHash(string, hash);
     if (it != table.set_.end()) {
       return it->Read();
     }
   }
   return nullptr;
 }

 void InternTable::Table::AddNewTable() {
   // Propagate the min/max load factor from the old active set.
   DCHECK(!tables_.empty());
   const UnorderedSet& last_set = tables_.back().set_;
   InternalTable new_table;
   new_table.set_.SetLoadFactor(last_set.GetMinLoadFactor(), last_set.GetMaxLoadFactor());
   tables_.push_back(std::move(new_table));
 }

 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_.PutWithHash(GcRoot<mirror::String>(s), hash);
 }

 void InternTable::Table::VisitRoots(RootVisitor* visitor) {
   BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(
       visitor, RootInfo(kRootInternedString));
   for (InternalTable& table : tables_) {
     for (auto& intern : table.set_) {
       buffered_visitor.VisitRoot(intern);
     }
   }
 }

 void InternTable::Table::SweepWeaks(IsMarkedVisitor* visitor) {
   for (InternalTable& table : tables_) {
     SweepWeaks(&table.set_, visitor);
   }
 }

 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) {
   for (auto it = set->begin(), end = set->end(); it != end;) {
     // This does not need a read barrier because this is called by GC.
     mirror::Object* object = it->Read<kWithoutReadBarrier>();
     mirror::Object* new_object = visitor->IsMarked(object);
     if (new_object == nullptr) {
       it = set->erase(it);
     } else {
       *it = GcRoot<mirror::String>(new_object->AsString());
       ++it;
     }
   }
 }

 size_t InternTable::Table::Size() const {
   return std::accumulate(tables_.begin(),
                          tables_.end(),
                          0U,
                          [](size_t sum, const InternalTable& table) {
                            return sum + table.Size();
                          });
 }

 void InternTable::ChangeWeakRootState(gc::WeakRootState new_state) {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   ChangeWeakRootStateLocked(new_state);
 }

 void InternTable::ChangeWeakRootStateLocked(gc::WeakRootState new_state) {
   CHECK(!kUseReadBarrier);
   weak_root_state_ = new_state;
   if (new_state != gc::kWeakRootStateNoReadsOrWrites) {
     weak_intern_condition_.Broadcast(Thread::Current());
   }
 }

 InternTable::Table::Table() {
   Runtime* const runtime = Runtime::Current();
   InternalTable initial_table;
   initial_table.set_.SetLoadFactor(runtime->GetHashTableMinLoadFactor(),
                                    runtime->GetHashTableMaxLoadFactor());
   tables_.push_back(std::move(initial_table));
 }

 }  // namespace art
	/*
	* Copyright (C) 2011 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "intern_table-inl.h"

	#include <memory>

	#include "dex/utf.h"
	#include "gc/collector/garbage_collector.h"
	#include "gc/space/image_space.h"
	#include "gc/weak_root_state.h"
	#include "gc_root-inl.h"
	#include "handle_scope-inl.h"
	#include "image-inl.h"
	#include "mirror/dex_cache-inl.h"
	#include "mirror/object-inl.h"
	#include "mirror/object_array-inl.h"
	#include "mirror/string-inl.h"
	#include "object_callbacks.h"
	#include "scoped_thread_state_change-inl.h"
	#include "thread.h"
	#include "thread-inl.h"

	namespace art {

	InternTable::InternTable()
	: log_new_roots_(false),
	weak_intern_condition_("New intern condition", *Locks::intern_table_lock_),
	weak_root_state_(gc::kWeakRootStateNormal) {
	}

	size_t InternTable::Size() const {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	return strong_interns_.Size() + weak_interns_.Size();
	}

	size_t InternTable::StrongSize() const {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	return strong_interns_.Size();
	}

	size_t InternTable::WeakSize() const {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	return weak_interns_.Size();
	}

	void InternTable::DumpForSigQuit(std::ostream& os) const {
	os << "Intern table: " << StrongSize() << " strong; " << WeakSize() << " weak\n";
	}

	void InternTable::VisitRoots(RootVisitor* visitor, VisitRootFlags flags) {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	if ((flags & kVisitRootFlagAllRoots) != 0) {
	strong_interns_.VisitRoots(visitor);
	} else if ((flags & kVisitRootFlagNewRoots) != 0) {
	for (auto& root : new_strong_intern_roots_) {
	ObjPtr<mirror::String> old_ref = root.Read<kWithoutReadBarrier>();
	root.VisitRoot(visitor, RootInfo(kRootInternedString));
	ObjPtr<mirror::String> new_ref = root.Read<kWithoutReadBarrier>();
	if (new_ref != old_ref) {
	// 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.
	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);
	}
	}
	}
	if ((flags & kVisitRootFlagClearRootLog) != 0) {
	new_strong_intern_roots_.clear();
	}
	if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
	log_new_roots_ = true;
	} else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
	log_new_roots_ = false;
	}
	// Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
	}

	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 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 strong_interns_.Find(s, hash);
	}

	ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self,
	uint32_t utf16_length,
	const char* 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);
	}

	ObjPtr<mirror::String> InternTable::LookupWeakLocked(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());
	return weak_interns_.Find(s, hash);
	}

	ObjPtr<mirror::String> InternTable::LookupStrongLocked(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());
	return strong_interns_.Find(s, hash);
	}

	void InternTable::AddNewTable() {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	weak_interns_.AddNewTable();
	strong_interns_.AddNewTable();
	}

	ObjPtr<mirror::String> InternTable::InsertStrong(ObjPtr<mirror::String> s, uint32_t hash) {
	Runtime* runtime = Runtime::Current();
	if (runtime->IsActiveTransaction()) {
	runtime->RecordStrongStringInsertion(s);
	}
	if (log_new_roots_) {
	new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
	}
	strong_interns_.Insert(s, hash);
	return 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, hash);
	return s;
	}

	void InternTable::RemoveStrong(ObjPtr<mirror::String> s, uint32_t hash) {
	strong_interns_.Remove(s, hash);
	}

	void InternTable::RemoveWeak(ObjPtr<mirror::String> s, uint32_t hash) {
	Runtime* runtime = Runtime::Current();
	if (runtime->IsActiveTransaction()) {
	runtime->RecordWeakStringRemoval(s);
	}
	weak_interns_.Remove(s, hash);
	}

	void InternTable::BroadcastForNewInterns() {
	Thread* self = Thread::Current();
	MutexLock mu(self, *Locks::intern_table_lock_);
	weak_intern_condition_.Broadcast(self);
	}

	void InternTable::WaitUntilAccessible(Thread* self) {
	Locks::intern_table_lock_->ExclusiveUnlock(self);
	{
	ScopedThreadSuspension sts(self, ThreadState::kWaitingWeakGcRootRead);
	MutexLock mu(self, *Locks::intern_table_lock_);
	while ((!kUseReadBarrier && weak_root_state_ == gc::kWeakRootStateNoReadsOrWrites) \|\|
	(kUseReadBarrier && !self->GetWeakRefAccessEnabled())) {
	weak_intern_condition_.Wait(self);
	}
	}
	Locks::intern_table_lock_->ExclusiveLock(self);
	}

	ObjPtr<mirror::String> InternTable::Insert(ObjPtr<mirror::String> s,
	uint32_t hash,
	bool is_strong,
	size_t num_searched_strong_frozen_tables) {
	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) {
	Locks::mutator_lock_->AssertSharedHeld(self);
	CHECK_EQ(2u, self->NumberOfHeldMutexes()) << "may only safely hold the mutator lock";
	}
	while (true) {
	// Check the strong table for a match.
	ObjPtr<mirror::String> strong =
	strong_interns_.Find(s, hash, num_searched_strong_frozen_tables);
	if (strong != nullptr) {
	return strong;
	}
	if (kUseReadBarrier ? self->GetWeakRefAccessEnabled()
	: weak_root_state_ != gc::kWeakRootStateNoReadsOrWrites) {
	break;
	}
	num_searched_strong_frozen_tables = strong_interns_.tables_.size() - 1u;
	// weak_root_state_ is set to gc::kWeakRootStateNoReadsOrWrites in the GC pause but is only
	// cleared after SweepSystemWeaks has completed. This is why we need to wait until it is
	// cleared.
	StackHandleScope<1> hs(self);
	auto h = hs.NewHandleWrapper(&s);
	WaitUntilAccessible(self);
	}
	if (!kUseReadBarrier) {
	CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
	} else {
	CHECK(self->GetWeakRefAccessEnabled());
	}
	// There is no match in the strong table, check the weak table.
	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, 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, hash) : InsertWeak(s, hash);
	}

	ObjPtr<mirror::String> InternTable::InternStrong(uint32_t utf16_length, const char* utf8_data) {
	DCHECK(utf8_data != nullptr);
	uint32_t hash = Utf8String::Hash(utf16_length, utf8_data);
	Thread* self = Thread::Current();
	ObjPtr<mirror::String> s;
	size_t num_searched_strong_frozen_tables;
	{
	// Try to avoid allocation. If we need to allocate, release the mutex before the allocation.
	MutexLock mu(self, *Locks::intern_table_lock_);
	DCHECK(!strong_interns_.tables_.empty());
	num_searched_strong_frozen_tables = strong_interns_.tables_.size() - 1u;
	s = strong_interns_.Find(Utf8String(utf16_length, utf8_data), hash);
	}
	if (s != nullptr) {
	return s;
	}
	bool is_ascii = (utf8_data[utf16_length] == 0);
	int32_t utf8_length = utf16_length + (LIKELY(is_ascii) ? 0 : strlen(utf8_data + utf16_length));
	DCHECK_EQ(static_cast<size_t>(utf8_length), strlen(utf8_data));
	s = mirror::String::AllocFromModifiedUtf8(self, utf16_length, utf8_data, utf8_length);
	if (UNLIKELY(s == nullptr)) {
	self->AssertPendingOOMException();
	return nullptr;
	}
	s->SetHashCode(static_cast<int32_t>(hash));
	return Insert(s, hash, /is_strong=/ true, num_searched_strong_frozen_tables);
	}

	ObjPtr<mirror::String> InternTable::InternStrong(const char* utf8_data) {
	DCHECK(utf8_data != nullptr);
	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) {
	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);
	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) {
	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) {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	weak_interns_.SweepWeaks(visitor);
	}

	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_.FindWithHash(GcRoot<mirror::String>(s), hash);
	if (it != table.set_.end()) {
	table.set_.erase(it);
	return;
	}
	}
	LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
	}

	FLATTEN
	ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s,
	uint32_t hash,
	size_t num_searched_frozen_tables) {
	Locks::intern_table_lock_->AssertHeld(Thread::Current());
	auto mid = tables_.begin() + num_searched_frozen_tables;
	for (Table::InternalTable& table : MakeIterationRange(tables_.begin(), mid)) {
	DCHECK(table.set_.FindWithHash(GcRoot<mirror::String>(s), hash) == table.set_.end());
	}
	// Search from the last table, assuming that apps shall search for their own
	// strings more often than for boot image strings.
	for (Table::InternalTable& table : ReverseRange(MakeIterationRange(mid, tables_.end()))) {
	auto it = table.set_.FindWithHash(GcRoot<mirror::String>(s), hash);
	if (it != table.set_.end()) {
	return it->Read();
	}
	}
	return nullptr;
	}

	FLATTEN
	ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string, uint32_t hash) {
	Locks::intern_table_lock_->AssertHeld(Thread::Current());
	// Search from the last table, assuming that apps shall search for their own
	// strings more often than for boot image strings.
	for (InternalTable& table : ReverseRange(tables_)) {
	auto it = table.set_.FindWithHash(string, hash);
	if (it != table.set_.end()) {
	return it->Read();
	}
	}
	return nullptr;
	}

	void InternTable::Table::AddNewTable() {
	// Propagate the min/max load factor from the old active set.
	DCHECK(!tables_.empty());
	const UnorderedSet& last_set = tables_.back().set_;
	InternalTable new_table;
	new_table.set_.SetLoadFactor(last_set.GetMinLoadFactor(), last_set.GetMaxLoadFactor());
	tables_.push_back(std::move(new_table));
	}

	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_.PutWithHash(GcRoot<mirror::String>(s), hash);
	}

	void InternTable::Table::VisitRoots(RootVisitor* visitor) {
	BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(
	visitor, RootInfo(kRootInternedString));
	for (InternalTable& table : tables_) {
	for (auto& intern : table.set_) {
	buffered_visitor.VisitRoot(intern);
	}
	}
	}

	void InternTable::Table::SweepWeaks(IsMarkedVisitor* visitor) {
	for (InternalTable& table : tables_) {
	SweepWeaks(&table.set_, visitor);
	}
	}

	void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) {
	for (auto it = set->begin(), end = set->end(); it != end;) {
	// This does not need a read barrier because this is called by GC.
	mirror::Object* object = it->Read<kWithoutReadBarrier>();
	mirror::Object* new_object = visitor->IsMarked(object);
	if (new_object == nullptr) {
	it = set->erase(it);
	} else {
	*it = GcRoot<mirror::String>(new_object->AsString());
	++it;
	}
	}
	}

	size_t InternTable::Table::Size() const {
	return std::accumulate(tables_.begin(),
	tables_.end(),
	0U,
	[](size_t sum, const InternalTable& table) {
	return sum + table.Size();
	});
	}

	void InternTable::ChangeWeakRootState(gc::WeakRootState new_state) {
	MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
	ChangeWeakRootStateLocked(new_state);
	}

	void InternTable::ChangeWeakRootStateLocked(gc::WeakRootState new_state) {
	CHECK(!kUseReadBarrier);
	weak_root_state_ = new_state;
	if (new_state != gc::kWeakRootStateNoReadsOrWrites) {
	weak_intern_condition_.Broadcast(Thread::Current());
	}
	}

	InternTable::Table::Table() {
	Runtime* const runtime = Runtime::Current();
	InternalTable initial_table;
	initial_table.set_.SetLoadFactor(runtime->GetHashTableMinLoadFactor(),
	runtime->GetHashTableMaxLoadFactor());
	tables_.push_back(std::move(initial_table));
	}

	} // namespace art