MB-23795: Move StoredValue::stale to OSV; guard with SeqList::writeLock

The stale flag in (Ordered)StoredValue needs to be read by the
tombstone purger when iterating the sequenceList; however at this
point there is no HashTable lock available - the OSV has been released
from the hashTable and hence we have no way to determine it's bucket
(without reading the key to recalculate - and that's not possible
without first acquiring the lock!).

To allow us to safely access the stale flag, move it from being
protected by the HT locks to the SequenceList::writeLock, and move to
OSV so it doesn't share with the other bitfields in the same
byte. While on the face of it this might seen like a serious
performance degredation having to serialise on a single lock, it
actually doesn't appear to be /that/ bad:

1) The stale flag is only accessed rarely:

   a) Set to false when a StoredValue is initially created (and this
      doesn't need the lock as the item isn't in the SeqList yet)

   b) Set to true when an item becomes stale (result of concurrent
      update & rangeRead, or deleted item is aged out and marked Stale).

   c) Read during tombStone purging.

2) Even when we *do* need to access the stale flag, we have already
   acquired the writeLock in the hot path
   (updateStoredValue/markItemStale).

Note: This will increase contention during a tombstone purge, as it
will need to acquire and release the writeLock for every seqList
element; this is an area which should be looked at for future
performance improvement - for example can the stale flag be made
atomic, or can we add lightweight, per-OSV lock?

Note(2): This increases the size of OSV by 8 bytes, as moving Stale to
it pushes up the alignment requirements (it was previously aligned to
8 bytes), although we've only added 1 bit to it. Better solution would
be to pack this into the boost_list hook, // or introduce per-OSV
microlock to guard the whole object.

Change-Id: If814b966a10c64fada204998410dafc5ad255351
Reviewed-on: http://review.couchbase.org/76715
Reviewed-by: Jim Walker <jim@couchbase.com>
Tested-by: Build Bot <build@couchbase.com>
Reviewed-by: Manu Dhundi <manu@couchbase.com>

diff --git a/src/linked_list.cc b/src/linked_list.cc
index bb2a827..50d5ed8 100644 (file)
--- a/src/linked_list.cc
+++ b/src/linked_list.cc
@@ -34,8 +34,11 @@ BasicLinkedList::BasicLinkedList(uint16_t vbucketId, EPStats& st)
 BasicLinkedList::~BasicLinkedList() {
     /* Delete stale items here, other items are deleted by the hash
        table */
+    std::lock_guard<std::mutex> writeGuard(writeLock);
     seqList.remove_and_dispose_if(
-            [](const OrderedStoredValue& v) { return v.isStale(); },
+            [&writeGuard](const OrderedStoredValue& v) {
+                return v.isStale(writeGuard);
+            },
             [this](OrderedStoredValue* v) {
                 this->st.currentSize.fetch_sub(v->metaDataSize());
                 delete v;
@@ -180,11 +183,11 @@ void BasicLinkedList::markItemStale(StoredValue::UniquePtr ownedSv) {
     staleMetaDataSize.fetch_add(v->metaDataSize());
     st.currentSize.fetch_add(v->metaDataSize());
 
-    /* Safer to serialize with the deletion of stale values */
-    std::lock_guard<std::mutex> lckGd(writeLock);
-
     ++numStaleItems;
-    v->toOrderedStoredValue()->markStale();
+    {
+        std::lock_guard<std::mutex> writeGuard(writeLock);
+        v->toOrderedStoredValue()->markStale(writeGuard);
+    }
 }
 
 uint64_t BasicLinkedList::getNumStaleItems() const {

diff --git a/src/stored-value.cc b/src/stored-value.cc
index 2bb5718..d6d937b 100644 (file)
--- a/src/stored-value.cc
+++ b/src/stored-value.cc
@@ -224,8 +224,8 @@ bool StoredValue::operator==(const StoredValue& other) const {
             exptime == other.exptime && flags == other.flags &&
             _isDirty == other._isDirty && deleted == other.deleted &&
             newCacheItem == other.newCacheItem &&
-            isOrdered == other.isOrdered && stale == other.stale &&
-            nru == other.nru && getKey() == other.getKey());
+            isOrdered == other.isOrdered && nru == other.nru &&
+            getKey() == other.getKey());
 }
 
 void StoredValue::deleteImpl(HashTable& ht) {

diff --git a/src/stored-value.h b/src/stored-value.h
index 338cd81..33636ca 100644 (file)
--- a/src/stored-value.h
+++ b/src/stored-value.h
@@ -642,7 +642,6 @@ protected:
           deleted(itm.isDeleted()),
           newCacheItem(true),
           isOrdered(isOrdered),
-          stale(false),
           nru(itm.getNRUValue()) {
         // Placement-new the key which lives in memory directly after this
         // object.
@@ -699,7 +698,6 @@ protected:
           deleted(other.deleted),
           newCacheItem(other.newCacheItem),
           isOrdered(other.isOrdered),
-          stale(other.stale),
           nru(other.nru) {
         // Placement-new the key which lives in memory directly after this
         // object.
@@ -746,7 +744,6 @@ protected:
     bool               deleted   :  1;
     bool               newCacheItem : 1;
     const bool isOrdered : 1; //!< Is this an instance of OrderedStoredValue?
-    bool stale : 1; //!< indicates if a newer instance of the item is added
     uint8_t            nru       :  2; //!< True if referenced since last sweep
 
     static void increaseMetaDataSize(HashTable &ht, EPStats &st, size_t by);
@@ -768,21 +765,25 @@ std::ostream& operator<<(std::ostream& os, const StoredValue& sv);
 class OrderedStoredValue : public StoredValue {
 public:
     // Intrusive linked-list for sequence number ordering.
+    // Guarded by the SequenceList's writeLock.
     boost::intrusive::list_member_hook<> seqno_hook;
 
     /**
      * True if a newer version of the same key exists in the HashTable.
      * Note: Only true for OrderedStoredValues which are no longer in the
      *       HashTable (and only live in SequenceList)
+     * @param writeGuard The locked SeqList writeLock which guards the stale
+     * param.
      */
-    bool isStale() const {
+    bool isStale(std::lock_guard<std::mutex>& writeGuard) const {
         return stale;
     }
 
     /**
      * Marks that newer instance of this item is added in the HashTable
+     * @param writeLock The SeqList writeLock which guards the stale param.
      */
-    void markStale() {
+    void markStale(std::lock_guard<std::mutex>& writeGuard) {
         stale = true;
     }
 
@@ -829,7 +830,8 @@ private:
                        UniquePtr n,
                        EPStats& stats,
                        HashTable& ht)
-        : StoredValue(itm, std::move(n), stats, ht, /*isOrdered*/ true) {
+        : StoredValue(itm, std::move(n), stats, ht, /*isOrdered*/ true),
+          stale(false) {
     }
 
     // Copy Constructor. Private, as needs to be carefully created via
@@ -842,7 +844,7 @@ private:
                        UniquePtr n,
                        EPStats& stats,
                        HashTable& ht)
-        : StoredValue(other, std::move(n), stats, ht) {
+        : StoredValue(other, std::move(n), stats, ht), stale(false) {
     }
 
     /* Do not allow assignment */
@@ -854,6 +856,10 @@ private:
     // Grant friendship to base class so it can perform flag dispatch to our
     // overridden protected methods.
     friend class StoredValue;
+
+    // indicates if a newer instance of the item is added. Guarded by the
+    // SequenceList's writeLock.
+    bool stale : 1;
 };
 
 SerialisedDocKey* StoredValue::key() {

diff --git a/tests/mock/mock_basic_ll.h b/tests/mock/mock_basic_ll.h
index d0f5178..ef21855 100644 (file)
--- a/tests/mock/mock_basic_ll.h
+++ b/tests/mock/mock_basic_ll.h
@@ -42,6 +42,11 @@ public:
         return allSeqnos;
     }
 
+    /// Expose the writeLock for testins.
+    std::mutex& getWriteLock() {
+        return writeLock;
+    }
+
     /* Register fake read range for testing */
     void registerFakeReadRange(seqno_t start, seqno_t end) {
         std::lock_guard<SpinLock> lh(rangeLock);

diff --git a/tests/module_tests/basic_ll_test.cc b/tests/module_tests/basic_ll_test.cc
index 379ac59..57e3e45 100644 (file)
--- a/tests/module_tests/basic_ll_test.cc
+++ b/tests/module_tests/basic_ll_test.cc
@@ -373,7 +373,10 @@ TEST_F(BasicLinkedListTest, MarkStale) {
     basicLL->markItemStale(std::move(ownedSv));
 
     /* Check if the StoredValue is marked stale */
-    EXPECT_TRUE(nonOwnedSvPtr->isStale());
+    {
+        std::lock_guard<std::mutex> writeGuard(basicLL->getWriteLock());
+        EXPECT_TRUE(nonOwnedSvPtr->isStale(writeGuard));
+    }
 
     /* Check if the stale count incremented to 1 */
     EXPECT_EQ(1, basicLL->getNumStaleItems());

diff --git a/tests/module_tests/stored_value_test.cc b/tests/module_tests/stored_value_test.cc
index 78f10a2..8fd71d9 100644 (file)
--- a/tests/module_tests/stored_value_test.cc
+++ b/tests/module_tests/stored_value_test.cc
@@ -139,10 +139,17 @@ TEST(StoredValueTest, expectedSize) {
 }
 
 TEST(OrderedStoredValueTest, expectedSize) {
-    EXPECT_EQ(72, sizeof(OrderedStoredValue))
+    // TODO-PERF: Ideally should be 72 - this is 63 bits larger than
+    // actually used due to moving {stale} from StoredValue's packed
+    // bitfields to OrderedStoredValue to prevent a race on a bitfield
+    // (TSan reports race between {stale} and {dirty} for example if they
+    // reside in the same byte).
+    // Better solution would be to pack this into the boost_list hook,
+    // or introduce per-OSV microlock to guard the whole object.
+    EXPECT_EQ(80, sizeof(OrderedStoredValue))
             << "Unexpected change in OrderedStoredValue fixed size";
     auto item = make_item(0, makeStoredDocKey("k"), "v");
-    EXPECT_EQ(75, OrderedStoredValue::getRequiredStorage(item))
+    EXPECT_EQ(83, OrderedStoredValue::getRequiredStorage(item))
             << "Unexpected change in OrderedStoredValue storage size for item: "
             << item;
 }