Fix locking on string init map (again).

Follow-up to
    https://android-review.googlesource.com/172036 ,
    https://android-review.googlesource.com/171621 .

Don't overwrite existing values, only insert new ones.
(Also improve performance by using move semantics.)

This prevents the following race: Thread 1 looks for string
init map for a method but doesn't find it, so it starts to
construct a new map. Thread 2 is doing the same but it's
faster and actually inserts the new map and keeps a pointer
to it. After Thread 2 releases the lock, Thread 1 acquires
it and starts to Overwrite() the element that the Thread 2
is currently using, so Thread 2 ends up looking at a map
that's being actively modified.

Change-Id: I135571af644363ea7bb282969a1bc7287b34f9b2

3 files changed, 19 insertions, 3 deletions

diff --git a/runtime/interpreter/interpreter_common.cc b/runtime/interpreter/interpreter_common.cc
index 68d56f5198..5fbd687452 100644
--- a/runtime/interpreter/interpreter_common.cc
+++ b/runtime/interpreter/interpreter_common.cc
@@ -709,7 +709,11 @@ static inline bool DoCallCommon(ArtMethod* called_method,
       SafeMap<uint32_t, std::set<uint32_t>> string_init_map =
           verifier::MethodVerifier::FindStringInitMap(method);
       MutexLock mu(self, *Locks::interpreter_string_init_map_lock_);
-      auto it = method_to_string_init_map.Overwrite(method_ref, string_init_map);
+      auto it = method_to_string_init_map.lower_bound(method_ref);
+      if (it == method_to_string_init_map.end() ||
+          method_to_string_init_map.key_comp()(method_ref, it->first)) {
+        it = method_to_string_init_map.PutBefore(it, method_ref, std::move(string_init_map));
+      }
       string_init_map_ptr = &it->second;
     }
     if (string_init_map_ptr->size() != 0) {
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index 04549c7889..7ac17b60d6 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -92,6 +92,11 @@ class SafeMap {
     DCHECK(result.second);  // Check we didn't accidentally overwrite an existing value.
     return result.first;
   }
+  iterator Put(const K& k, const V&& v) {
+    std::pair<iterator, bool> result = map_.emplace(k, std::move(v));
+    DCHECK(result.second);  // Check we didn't accidentally overwrite an existing value.
+    return result.first;
+  }
 
   // Used to insert a new mapping at a known position for better performance.
   iterator PutBefore(iterator pos, const K& k, const V& v) {
@@ -100,10 +105,16 @@ class SafeMap {
     DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
     return map_.emplace_hint(pos, k, v);
   }
+  iterator PutBefore(iterator pos, const K& k, const V&& v) {
+    // Check that we're using the correct position and the key is not in the map.
+    DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
+    DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
+    return map_.emplace_hint(pos, k, std::move(v));
+  }
 
   // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type
   // of this container is a pointer, any overwritten pointer will be lost and if this container
-  // was the owner, you have a leak.
+  // was the owner, you have a leak. Returns iterator pointing to the new or overwritten entry.
   iterator Overwrite(const K& k, const V& v) {
     std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v));
     if (!result.second) {
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index 3d4f04c70c..9938e907e9 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -548,7 +548,8 @@ SafeMap<uint32_t, std::set<uint32_t>> MethodVerifier::FindStringInitMap(ArtMetho
   MethodVerifier verifier(self, m->GetDexFile(), dex_cache, class_loader, &m->GetClassDef(),
                           m->GetCodeItem(), m->GetDexMethodIndex(), m, m->GetAccessFlags(),
                           true, true, false, true);
-  return verifier.FindStringInitMap();
+  // Avoid copying: The map is moved out of the verifier before the verifier is destroyed.
+  return std::move(verifier.FindStringInitMap());
 }
 
 SafeMap<uint32_t, std::set<uint32_t>>& MethodVerifier::FindStringInitMap() {