AutoHCC: fix a bug with "blind" Insert (#12046)

Summary:
I have finally tracked down and fixed a bug affecting AutoHCC that was causing CI crash test assertion failures in AutoHCC when using secondary cache, but I was only able to reproduce locally a couple of times, after very long runs/repetitions.

It turns out that the essential feature used by secondary cache to trigger the bug is Insert without keeping a handle, which is otherwise rarely used in RocksDB and not incorporated into cache_bench (also used for targeted correctness stress testing) until this change (new option `-blind_insert_percent`).

The problem was in copying some logic from FixedHCC that makes the entry "sharable" but unreferenced once populated, if no reference is to be saved. The problem in AutoHCC is that we can only add the entry to a chain after it is in the sharable state, and must be removed from the chain while in the "under (de)construction" state and before it is back in the "empty" state. Also, it is possible for Lookup to find entries that are not connected to any chain, by design for efficiency, and for Release to erase_if_last_ref. Therefore, we could have
* Thread 1 starts to Insert a cache entry without keeping ref, and pauses before adding to the chain.
* Thread 2 finds it with Lookup optimizations, and then does Release with `erase_if_last_ref=true` causing it to trigger erasure on the entry. It successfully locks the home chain for the entry and purges any entries pending erasure. It is OK that this entry is not found on the chain, as another thread is allowed to remove it from the chain before we are able to (but after is it marked for (de)construction). And after the purge of the chain, the entry is marked empty.
* Thread 1 resumes in adding the slot (presumed entry) to the home chain for what was being inserted, but that now violates invariants and sets up a race or double-chain-reference as another thread could insert a new entry in the slot and try to insert into a different chain.

This is easily fixed by holding on to a reference until inserted onto the chain.

Pull Request resolved: https://github.com/facebook/rocksdb/pull/12046

Test Plan:
As I don't have a reliable local reproducer, I triggered 20 runs of internal CI on fbcode_blackbox_crash_test that were previously failing in AutoHCC with about 1/3 probability, and they all passed.

Also re-enabling AutoHCC in the crash test with this change. (Revert https://github.com/facebook/rocksdb/issues/12000)

Reviewed By: jowlyzhang

Differential Revision: D51016979

Pulled By: pdillinger

fbshipit-source-id: 3840fb829d65b97c779d8aed62a4a4a433aeff2b

2 files changed, 26 insertions, 6 deletions

diff --git a/cache/cache_bench_tool.cc b/cache/cache_bench_tool.cc
index 1aff1b8bf..89945abf7 100644
--- a/cache/cache_bench_tool.cc
+++ b/cache/cache_bench_tool.cc
@@ -71,11 +71,14 @@ DEFINE_double(
     "ratio less than full size and full size. If vary_capacity_ratio + "
     "pinned_ratio is close to or exceeds 1.0, the cache might thrash.");
 
-DEFINE_uint32(lookup_insert_percent, 87,
+DEFINE_uint32(lookup_insert_percent, 82,
               "Ratio of lookup (+ insert on not found) to total workload "
               "(expressed as a percentage)");
 DEFINE_uint32(insert_percent, 2,
               "Ratio of insert to total workload (expressed as a percentage)");
+DEFINE_uint32(blind_insert_percent, 5,
+              "Ratio of insert without keeping handle to total workload "
+              "(expressed as a percentage)");
 DEFINE_uint32(lookup_percent, 10,
               "Ratio of lookup to total workload (expressed as a percentage)");
 DEFINE_uint32(erase_percent, 1,
@@ -360,7 +363,9 @@ class CacheBench {
                                  FLAGS_lookup_insert_percent),
         insert_threshold_(lookup_insert_threshold_ +
                           kHundredthUint64 * FLAGS_insert_percent),
-        lookup_threshold_(insert_threshold_ +
+        blind_insert_threshold_(insert_threshold_ +
+                                kHundredthUint64 * FLAGS_blind_insert_percent),
+        lookup_threshold_(blind_insert_threshold_ +
                           kHundredthUint64 * FLAGS_lookup_percent),
         erase_threshold_(lookup_threshold_ +
                          kHundredthUint64 * FLAGS_erase_percent) {
@@ -560,6 +565,7 @@ class CacheBench {
   // Cumulative thresholds in the space of a random uint64_t
   const uint64_t lookup_insert_threshold_;
   const uint64_t insert_threshold_;
+  const uint64_t blind_insert_threshold_;
   const uint64_t lookup_threshold_;
   const uint64_t erase_threshold_;
 
@@ -735,6 +741,12 @@ class CacheBench {
             key, createValue(thread->rnd, cache_->memory_allocator()), &helper3,
             FLAGS_value_bytes, &pinned.emplace_back());
         assert(s.ok());
+      } else if (random_op < blind_insert_threshold_) {
+        // insert without keeping a handle
+        Status s = cache_->Insert(
+            key, createValue(thread->rnd, cache_->memory_allocator()), &helper3,
+            FLAGS_value_bytes);
+        assert(s.ok());
       } else if (random_op < lookup_threshold_) {
         // do lookup
         auto handle = cache_->Lookup(key, &helper2, /*context*/ nullptr,
diff --git a/cache/clock_cache.cc b/cache/clock_cache.cc
index a6d41985a..dfa3c5e1f 100644
--- a/cache/clock_cache.cc
+++ b/cache/clock_cache.cc
@@ -2903,13 +2903,18 @@ AutoHyperClockTable::HandleImpl* AutoHyperClockTable::DoInsert(
   // Approximate average cache lines read to find an existing entry:
   // = 1.65 cache lines
 
+  // Even if we aren't saving a ref to this entry (take_ref == false), we need
+  // to keep a reference while we are inserting the entry into a chain, so that
+  // it is not erased by another thread while trying to insert it on the chain.
+  constexpr bool initial_take_ref = true;
+
   size_t used_length = LengthInfoToUsedLength(state.saved_length_info);
   assert(home < used_length);
 
   size_t idx = home;
   bool already_matches = false;
   bool already_matches_ignore = false;
-  if (TryInsert(proto, arr[idx], initial_countdown, take_ref,
+  if (TryInsert(proto, arr[idx], initial_countdown, initial_take_ref,
                 &already_matches)) {
     assert(idx == home);
   } else if (already_matches) {
@@ -2921,7 +2926,7 @@ AutoHyperClockTable::HandleImpl* AutoHyperClockTable::DoInsert(
     // incorporate logic for here cleanly and efficiently.
   } else if (UNLIKELY(state.likely_empty_slot > 0) &&
              TryInsert(proto, arr[state.likely_empty_slot], initial_countdown,
-                       take_ref, &already_matches_ignore)) {
+                       initial_take_ref, &already_matches_ignore)) {
     idx = state.likely_empty_slot;
   } else {
     // We need to search for an available slot outside of the home.
@@ -2955,7 +2960,7 @@ AutoHyperClockTable::HandleImpl* AutoHyperClockTable::DoInsert(
       if (idx >= used_length) {
         idx -= used_length;
       }
-      if (TryInsert(proto, arr[idx], initial_countdown, take_ref,
+      if (TryInsert(proto, arr[idx], initial_countdown, initial_take_ref,
                     &already_matches)) {
         break;
       }
@@ -3010,7 +3015,7 @@ AutoHyperClockTable::HandleImpl* AutoHyperClockTable::DoInsert(
             }
           }
         }
-        if (TryInsert(proto, arr[idx], initial_countdown, take_ref,
+        if (TryInsert(proto, arr[idx], initial_countdown, initial_take_ref,
                       &already_matches)) {
           break;
         }
@@ -3073,6 +3078,9 @@ AutoHyperClockTable::HandleImpl* AutoHyperClockTable::DoInsert(
     if (arr[home].head_next_with_shift.compare_exchange_weak(
             next_with_shift, head_next_with_shift, std::memory_order_acq_rel)) {
       // Success
+      if (!take_ref) {
+        Unref(arr[idx]);
+      }
       return arr + idx;
     }
   }