From 4bb932773e47b1ce04602d81ffa5a8a7d863eb10 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Thu, 7 Aug 2014 18:07:18 +0100 Subject: [PATCH] Fix performance regression in OatFile::GetOatDexFile(). Try to avoid calculating the canonical location of the dex file if possible and when we have to calculate it, cache the lookup result for subsequent lookups. Bug: 16828525 Bug: 16859671 (cherry picked from commit 3f5838d7d0b9fc63db0ccc35c2ea05ed29264986) Change-Id: Ifd9a45dada2cc724382fd03c10f6437a6b71e666 --- runtime/base/mutex.h | 1 + runtime/oat_file.cc | 76 ++++++++++++++++++++++++++++++++++++++-------------- runtime/oat_file.h | 39 ++++++++++++++++++++++++--- 3 files changed, 92 insertions(+), 24 deletions(-) diff --git a/runtime/base/mutex.h b/runtime/base/mutex.h index 818f9d990..d898e49df 100644 --- a/runtime/base/mutex.h +++ b/runtime/base/mutex.h @@ -70,6 +70,7 @@ enum LockLevel { kMarkSweepMarkStackLock, kTransactionLogLock, kInternTableLock, + kOatFileSecondaryLookupLock, kDefaultMutexLevel, kMarkSweepLargeObjectLock, kPinTableLock, diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc index c4c6b10a7..971daf8bb 100644 --- a/runtime/oat_file.cc +++ b/runtime/oat_file.cc @@ -121,14 +121,12 @@ OatFile* OatFile::OpenElfFile(File* file, } OatFile::OatFile(const std::string& location) - : location_(location), begin_(NULL), end_(NULL), dlopen_handle_(NULL) { + : location_(location), begin_(NULL), end_(NULL), dlopen_handle_(NULL), + secondary_lookup_lock_("OatFile secondary lookup lock", kOatFileSecondaryLookupLock) { CHECK(!location_.empty()); } OatFile::~OatFile() { - for (auto it : oat_dex_files_) { - delete it.first.data(); - } STLDeleteValues(&oat_dex_files_); if (dlopen_handle_ != NULL) { dlclose(dlopen_handle_); @@ -304,19 +302,13 @@ bool OatFile::Setup(std::string* error_msg) { return false; } + // Create the OatDexFile and add it to the owning map indexed by the dex file location. OatDexFile* oat_dex_file = new OatDexFile(this, dex_file_location, dex_file_checksum, dex_file_pointer, methods_offsets_pointer); - - std::string dex_canonical_location_str = DexFile::GetDexCanonicalLocation(dex_file_location.c_str()); - // make a copy since we need to persist it as a key in the object's field. - int location_size = dex_canonical_location_str.size() + 1; - char* dex_canonical_location = new char[location_size ]; - strncpy(dex_canonical_location, dex_canonical_location_str.c_str(), location_size); - - StringPiece key(dex_canonical_location); + StringPiece key(oat_dex_file->GetDexFileLocation()); oat_dex_files_.Put(key, oat_dex_file); } return true; @@ -339,18 +331,62 @@ const byte* OatFile::End() const { const OatFile::OatDexFile* OatFile::GetOatDexFile(const char* dex_location, const uint32_t* dex_location_checksum, bool warn_if_not_found) const { - std::string dex_canonical_location = DexFile::GetDexCanonicalLocation(dex_location); - - Table::const_iterator it = oat_dex_files_.find(dex_canonical_location); - if (it != oat_dex_files_.end()) { - const OatFile::OatDexFile* oat_dex_file = it->second; - if (dex_location_checksum == NULL || - oat_dex_file->GetDexFileLocationChecksum() == *dex_location_checksum) { - return oat_dex_file; + // NOTE: We assume here that the canonical location for a given dex_location never + // changes. If it does (i.e. some symlink used by the filename changes) we may return + // an incorrect OatDexFile. As long as we have a checksum to check, we shall return + // an identical file or fail; otherwise we may see some unpredictable failures. + + // TODO: Additional analysis of usage patterns to see if this can be simplified + // without any performance loss, for example by not doing the first lock-free lookup. + + const OatFile::OatDexFile* oat_dex_file = nullptr; + StringPiece key(dex_location); + // Try to find the key cheaply in the oat_dex_files_ map which holds dex locations + // directly mentioned in the oat file and doesn't require locking. + auto primary_it = oat_dex_files_.find(key); + if (primary_it != oat_dex_files_.end()) { + oat_dex_file = primary_it->second; + DCHECK(oat_dex_file != nullptr); + } else { + // This dex_location is not one of the dex locations directly mentioned in the + // oat file. The correct lookup is via the canonical location but first see in + // the secondary_oat_dex_files_ whether we've looked up this location before. + MutexLock mu(Thread::Current(), secondary_lookup_lock_); + auto secondary_lb = secondary_oat_dex_files_.lower_bound(key); + if (secondary_lb != secondary_oat_dex_files_.end() && key == secondary_lb->first) { + oat_dex_file = secondary_lb->second; // May be nullptr. + } else { + // We haven't seen this dex_location before, we must check the canonical location. + if (UNLIKELY(oat_dex_files_by_canonical_location_.empty())) { + // Lazily fill in the oat_dex_files_by_canonical_location_. + for (const auto& entry : oat_dex_files_) { + const std::string& dex_location = entry.second->GetDexFileLocation(); + string_cache_.emplace_back(DexFile::GetDexCanonicalLocation(dex_location.c_str())); + StringPiece canonical_location_key(string_cache_.back()); + oat_dex_files_by_canonical_location_.Put(canonical_location_key, entry.second); + } + } + std::string dex_canonical_location = DexFile::GetDexCanonicalLocation(dex_location); + StringPiece canonical_key(dex_canonical_location); + auto canonical_it = oat_dex_files_by_canonical_location_.find(canonical_key); + if (canonical_it != oat_dex_files_by_canonical_location_.end()) { + oat_dex_file = canonical_it->second; + } // else keep nullptr. + + // Copy the key to the string_cache_ and store the result in secondary map. + string_cache_.emplace_back(key.data(), key.length()); + StringPiece key_copy(string_cache_.back()); + secondary_oat_dex_files_.PutBefore(secondary_lb, key_copy, oat_dex_file); } } + if (oat_dex_file != nullptr && + (dex_location_checksum == nullptr || + oat_dex_file->GetDexFileLocationChecksum() == *dex_location_checksum)) { + return oat_dex_file; + } if (warn_if_not_found) { + std::string dex_canonical_location = DexFile::GetDexCanonicalLocation(dex_location); std::string checksum(""); if (dex_location_checksum != NULL) { checksum = StringPrintf("0x%08x", *dex_location_checksum); diff --git a/runtime/oat_file.h b/runtime/oat_file.h index 3ec2e8434..9710a2add 100644 --- a/runtime/oat_file.h +++ b/runtime/oat_file.h @@ -17,9 +17,11 @@ #ifndef ART_RUNTIME_OAT_FILE_H_ #define ART_RUNTIME_OAT_FILE_H_ +#include #include #include +#include "base/mutex.h" #include "base/stringpiece.h" #include "dex_file.h" #include "invoke_type.h" @@ -227,7 +229,8 @@ class OatFile { const OatDexFile* GetOatDexFile(const char* dex_location, const uint32_t* const dex_location_checksum, - bool exception_if_not_found = true) const; + bool exception_if_not_found = true) const + LOCKS_EXCLUDED(secondary_lookup_lock_); std::vector GetOatDexFiles() const; @@ -279,10 +282,38 @@ class OatFile { // dlopen handle during runtime. void* dlopen_handle_; - // NOTE: We use a StringPiece as the key type to avoid a memory allocation on every lookup - // with a const char* key. + // NOTE: We use a StringPiece as the key type to avoid a memory allocation on every + // lookup with a const char* key. The StringPiece doesn't own its backing storage, + // therefore we're using the OatDexFile::dex_file_location_ as the backing storage + // for keys in oat_dex_files_ and the string_cache_ entries for the backing storage + // of keys in secondary_oat_dex_files_ and oat_dex_files_by_canonical_location_. typedef SafeMap Table; - Table oat_dex_files_; + + // Map each plain dex file location retrieved from the oat file to its OatDexFile. + // This map doesn't change after it's constructed in Setup() and therefore doesn't + // need any locking and provides the cheapest dex file lookup for GetOatDexFile() + // for a very frequent use case. Never contains a nullptr value. + Table oat_dex_files_; // Owns the OatDexFile* values. + + // Lock guarding all members needed for secondary lookup in GetOatDexFile(). + mutable Mutex secondary_lookup_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; + + // If the primary oat_dex_files_ lookup fails, use a secondary map. This map stores + // the results of all previous secondary lookups, whether successful (non-null) or + // failed (null). If it doesn't contain an entry we need to calculate the canonical + // location and use oat_dex_files_by_canonical_location_. + mutable Table secondary_oat_dex_files_ GUARDED_BY(secondary_lookup_lock_); + + // Map the canonical location to an OatDexFile. This lazily constructed map is used + // when we're doing the secondary lookup for a given location for the first time. + mutable Table oat_dex_files_by_canonical_location_ GUARDED_BY(secondary_lookup_lock_); + + // Cache of strings. Contains the backing storage for keys in the secondary_oat_dex_files_ + // and the lazily initialized oat_dex_files_by_canonical_location_. + // NOTE: We're keeping references to contained strings in form of StringPiece and adding + // new strings to the end. The adding of a new element must not touch any previously stored + // elements. std::list<> and std::deque<> satisfy this requirement, std::vector<> doesn't. + mutable std::list string_cache_ GUARDED_BY(secondary_lookup_lock_); friend class OatClass; friend class OatDexFile; -- 2.11.0