tests/module_tests/basic_ll_test.cc

   1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /*
   3  *     Copyright 2017 Couchbase, Inc
   4  *
   5  *   Licensed under the Apache License, Version 2.0 (the "License");
   6  *   you may not use this file except in compliance with the License.
   7  *   You may obtain a copy of the License at
   8  *
   9  *       http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *   Unless required by applicable law or agreed to in writing, software
  12  *   distributed under the License is distributed on an "AS IS" BASIS,
  13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *   See the License for the specific language governing permissions and
  15  *   limitations under the License.
  16  */
  17
  18 #include "config.h"
  19
  20 #include <gtest/gtest.h>
  21 #include <platform/cb_malloc.h>
  22
  23 #include "../mock/mock_basic_ll.h"
  24 #include "hash_table.h"
  25 #include "item.h"
  26 #include "linked_list.h"
  27 #include "stats.h"
  28 #include "stored_value_factories.h"
  29 #include "tests/module_tests/test_helpers.h"
  30
  31 #include <limits>
  32 #include <vector>
  33
  34 static EPStats global_stats;
  35
  36 class BasicLinkedListTest : public ::testing::Test {
  37 public:
  38     BasicLinkedListTest() : ht(global_stats, makeFactory(), 2, 1) {
  39     }
  40
  41     static std::unique_ptr<AbstractStoredValueFactory> makeFactory() {
  42         return std::make_unique<OrderedStoredValueFactory>(global_stats);
  43     }
  44
  45 protected:
  46     void SetUp() {
  47         basicLL = std::make_unique<MockBasicLinkedList>(global_stats);
  48     }
  49
  50     void TearDown() {
  51         /* Like in a vbucket we want the list to be erased before HashTable is
  52            is destroyed. */
  53         basicLL.reset();
  54     }
  55
  56     /**
  57      * Adds 'numItems' number of new items to the linked list, from startSeqno.
  58      * Items to have key as keyPrefixXX, XX being the seqno.
  59      *
  60      * Returns the vector of seqnos added.
  61      */
  62     std::vector<seqno_t> addNewItemsToList(seqno_t startSeqno,
  63                                            const std::string& keyPrefix,
  64                                            const int numItems) {
  65         const seqno_t last = startSeqno + numItems;
  66         const std::string val("data");
  67         OrderedStoredValue* sv;
  68         std::vector<seqno_t> expectedSeqno;
  69
  70         /* Get a fake sequence lock */
  71         std::mutex fakeSeqLock;
  72         std::lock_guard<std::mutex> lg(fakeSeqLock);
  73
  74         for (seqno_t i = startSeqno; i < last; ++i) {
  75             StoredDocKey key = makeStoredDocKey(keyPrefix + std::to_string(i));
  76             Item item(key,
  77                       0,
  78                       0,
  79                       val.data(),
  80                       val.length(),
  81                       /*ext_meta*/ nullptr,
  82                       /*ext_len*/ 0,
  83                       /*theCas*/ 0,
  84                       /*bySeqno*/ i);
  85             EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
  86
  87             sv = ht.find(key, TrackReference::Yes, WantsDeleted::No)
  88                          ->toOrderedStoredValue();
  89             basicLL->appendToList(lg, *sv);
  90             std::lock_guard<std::mutex> highSeqnoLh(
  91                     basicLL->getHighSeqnosLock());
  92             basicLL->updateHighSeqno(highSeqnoLh, *sv);
  93             expectedSeqno.push_back(i);
  94         }
  95         return expectedSeqno;
  96     }
  97
  98     /**
  99      * Updates an existing item with key == key and assigns it a seqno of
 100      * highSeqno + 1. To be called when there is no range read.
 101      */
 102     void updateItem(seqno_t highSeqno, const std::string& key) {
 103         /* Get a fake sequence lock */
 104         std::mutex fakeSeqLock;
 105         std::lock_guard<std::mutex> lg(fakeSeqLock);
 106
 107         OrderedStoredValue* osv = ht.find(makeStoredDocKey(key),
 108                                           TrackReference::No,
 109                                           WantsDeleted::Yes)
 110                                           ->toOrderedStoredValue();
 111         EXPECT_EQ(SequenceList::UpdateStatus::Success,
 112                   basicLL->updateListElem(lg, *osv));
 113         osv->setBySeqno(highSeqno + 1);
 114         std::lock_guard<std::mutex> highSeqnoLh(basicLL->getHighSeqnosLock());
 115         basicLL->updateHighSeqno(highSeqnoLh, *osv);
 116     }
 117
 118     /**
 119      * Updates an existing item with key == key.
 120      * To be called when there is range read.
 121      */
 122     void updateItemDuringRangeRead(seqno_t highSeqno, const std::string& key) {
 123         /* Get a fake sequence lock */
 124         std::mutex fakeSeqLock;
 125         std::lock_guard<std::mutex> lg(fakeSeqLock);
 126
 127         OrderedStoredValue* osv = ht.find(makeStoredDocKey(key),
 128                                           TrackReference::No,
 129                                           WantsDeleted::Yes)
 130                                           ->toOrderedStoredValue();
 131
 132         EXPECT_EQ(SequenceList::UpdateStatus::Append,
 133                   basicLL->updateListElem(lg, *osv));
 134     }
 135
 136     /**
 137      * Deletes an existing item with key == key, puts it onto the linked list
 138      * and assigns it a seqno of highSeqno + 1.
 139      * To be called when there is no range read.
 140      */
 141     void softDeleteItem(seqno_t highSeqno, const std::string& key) {
 142         { /* hbl lock scope */
 143             auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
 144             StoredValue* sv = ht.unlocked_find(makeStoredDocKey(key),
 145                                                hbl.getBucketNum(),
 146                                                WantsDeleted::Yes,
 147                                                TrackReference::No);
 148
 149             ht.unlocked_softDelete(
 150                     hbl.getHTLock(), *sv, /* onlyMarkDeleted */ false);
 151         }
 152
 153         updateItem(highSeqno, key);
 154     }
 155
 156     /**
 157      * Release a StoredValue with 'key' from the hash table
 158      */
 159     StoredValue::UniquePtr releaseFromHashTable(const std::string& key) {
 160         auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
 161         return ht.unlocked_release(hbl, makeStoredDocKey(key));
 162     }
 163
 164     /* We need a HashTable because StoredValue is created only in the HashTable
 165        and then put onto the sequence list */
 166     HashTable ht;
 167     std::unique_ptr<MockBasicLinkedList> basicLL;
 168 };
 169
 170 TEST_F(BasicLinkedListTest, SetItems) {
 171     const int numItems = 3;
 172
 173     /* Add 3 new items */
 174     std::vector<seqno_t> expectedSeqno =
 175             addNewItemsToList(1, std::string("key"), numItems);
 176
 177     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 178 }
 179
 180 TEST_F(BasicLinkedListTest, TestRangeRead) {
 181     const int numItems = 3;
 182
 183     /* Add 3 new items */
 184     addNewItemsToList(1, std::string("key"), numItems);
 185
 186     /* Now do a range read */
 187     ENGINE_ERROR_CODE status;
 188     std::vector<UniqueItemPtr> items;
 189     seqno_t endSeqno;
 190     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems);
 191
 192     EXPECT_EQ(ENGINE_SUCCESS, status);
 193     EXPECT_EQ(numItems, items.size());
 194     EXPECT_EQ(numItems, items.back()->getBySeqno());
 195     EXPECT_EQ(numItems, endSeqno);
 196 }
 197
 198 TEST_F(BasicLinkedListTest, TestRangeReadTillInf) {
 199     const int numItems = 3;
 200
 201     /* Add 3 new items */
 202     addNewItemsToList(1, std::string("key"), numItems);
 203
 204     /* Now do a range read */
 205     ENGINE_ERROR_CODE status;
 206     std::vector<UniqueItemPtr> items;
 207     seqno_t endSeqno;
 208     std::tie(status, items, endSeqno) =
 209             basicLL->rangeRead(1, std::numeric_limits<seqno_t>::max());
 210
 211     EXPECT_EQ(ENGINE_SUCCESS, status);
 212     EXPECT_EQ(numItems, items.size());
 213     EXPECT_EQ(numItems, items.back()->getBySeqno());
 214     EXPECT_EQ(numItems, endSeqno);
 215 }
 216
 217 TEST_F(BasicLinkedListTest, TestRangeReadFromMid) {
 218     const int numItems = 3;
 219
 220     /* Add 3 new items */
 221     addNewItemsToList(1, std::string("key"), numItems);
 222
 223     /* Now do a range read */
 224     ENGINE_ERROR_CODE status;
 225     std::vector<UniqueItemPtr> items;
 226     seqno_t endSeqno;
 227     std::tie(status, items, endSeqno) = basicLL->rangeRead(2, numItems);
 228
 229     EXPECT_EQ(ENGINE_SUCCESS, status);
 230     EXPECT_EQ(numItems - 1, items.size());
 231     EXPECT_EQ(numItems, items.back()->getBySeqno());
 232     EXPECT_EQ(numItems, endSeqno);
 233 }
 234
 235 TEST_F(BasicLinkedListTest, TestRangeReadStopBeforeEnd) {
 236     const int numItems = 3;
 237
 238     /* Add 3 new items */
 239     addNewItemsToList(1, std::string("key"), numItems);
 240
 241     /* Now request for a range read of just 2 items */
 242     ENGINE_ERROR_CODE status;
 243     std::vector<UniqueItemPtr> items;
 244     seqno_t endSeqno;
 245     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems - 1);
 246
 247     EXPECT_EQ(ENGINE_SUCCESS, status);
 248     EXPECT_EQ(numItems - 1, items.size());
 249     EXPECT_EQ(numItems - 1, items.back()->getBySeqno());
 250     EXPECT_EQ(numItems - 1, endSeqno);
 251 }
 252
 253 TEST_F(BasicLinkedListTest, TestRangeReadNegatives) {
 254     const int numItems = 3;
 255
 256     /* Add 3 new items */
 257     addNewItemsToList(1, std::string("key"), numItems);
 258
 259     ENGINE_ERROR_CODE status;
 260     std::vector<UniqueItemPtr> items;
 261
 262     /* Now do a range read with start > end */
 263     std::tie(status, items, std::ignore) = basicLL->rangeRead(2, 1);
 264     EXPECT_EQ(ENGINE_ERANGE, status);
 265
 266     /* Now do a range read with start > highSeqno */
 267     std::tie(status, items, std::ignore) =
 268             basicLL->rangeRead(numItems + 1, numItems + 2);
 269     EXPECT_EQ(ENGINE_ERANGE, status);
 270 }
 271
 272 TEST_F(BasicLinkedListTest, UpdateFirstElem) {
 273     const int numItems = 3;
 274     const std::string keyPrefix("key");
 275
 276     /* Add 3 new items */
 277     addNewItemsToList(1, keyPrefix, numItems);
 278
 279     /* Update the first item in the list */
 280     updateItem(numItems, keyPrefix + std::to_string(1));
 281
 282     /* Check if the updated element has moved to the end */
 283     std::vector<seqno_t> expectedSeqno = {2, 3, 4};
 284     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 285 }
 286
 287 TEST_F(BasicLinkedListTest, UpdateMiddleElem) {
 288     const int numItems = 3;
 289     const std::string keyPrefix("key");
 290
 291     /* Add 3 new items */
 292     addNewItemsToList(1, keyPrefix, numItems);
 293
 294     /* Update a middle item in the list */
 295     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
 296
 297     /* Check if the updated element has moved to the end */
 298     std::vector<seqno_t> expectedSeqno = {1, 3, 4};
 299     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 300 }
 301
 302 TEST_F(BasicLinkedListTest, UpdateLastElem) {
 303     const int numItems = 3;
 304     const std::string keyPrefix("key");
 305
 306     /* Add 3 new items */
 307     addNewItemsToList(1, keyPrefix, numItems);
 308
 309     /* Update the last item in the list */
 310     updateItem(numItems, keyPrefix + std::to_string(numItems));
 311
 312     /* Check if the updated element has moved to the end */
 313     std::vector<seqno_t> expectedSeqno = {1, 2, 4};
 314     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 315 }
 316
 317 TEST_F(BasicLinkedListTest, WriteNewAfterUpdate) {
 318     const int numItems = 3;
 319     const std::string keyPrefix("key");
 320
 321     /* Add 3 new items */
 322     addNewItemsToList(1, keyPrefix, numItems);
 323
 324     /* Update an item in the list */
 325     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
 326
 327     /* Add a new item after update */
 328     addNewItemsToList(
 329             numItems + /* +1 is update, another +1 for next */ 2, keyPrefix, 1);
 330
 331     /* Check if the new element is added correctly */
 332     std::vector<seqno_t> expectedSeqno = {1, 3, 4, 5};
 333     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 334 }
 335
 336 TEST_F(BasicLinkedListTest, UpdateDuringRangeRead) {
 337     const int numItems = 3;
 338     const std::string keyPrefix("key");
 339
 340     /* Add 3 new items */
 341     addNewItemsToList(1, keyPrefix, numItems);
 342
 343     basicLL->registerFakeReadRange(1, numItems);
 344
 345     /* Update an item in the list when a fake range read is happening */
 346     updateItemDuringRangeRead(numItems,
 347                               keyPrefix + std::to_string(numItems - 1));
 348 }
 349
 350 TEST_F(BasicLinkedListTest, DeletedItem) {
 351     const std::string keyPrefix("key");
 352     const int numItems = 1;
 353
 354     int numDeleted = basicLL->getNumDeletedItems();
 355
 356     /* Add an item */
 357     addNewItemsToList(numItems, keyPrefix, 1);
 358
 359     /* Delete the item */
 360     softDeleteItem(numItems, keyPrefix + std::to_string(numItems));
 361     basicLL->updateNumDeletedItems(false, true);
 362
 363     /* Check if the delete is added correctly */
 364     std::vector<seqno_t> expectedSeqno = {numItems + 1};
 365     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 366     EXPECT_EQ(numDeleted + 1, basicLL->getNumDeletedItems());
 367 }
 368
 369 TEST_F(BasicLinkedListTest, MarkStale) {
 370     const std::string keyPrefix("key");
 371     const int numItems = 1;
 372
 373     /* To begin with we expect 0 stale items */
 374     EXPECT_EQ(0, basicLL->getNumStaleItems());
 375
 376     /* Add an item */
 377     addNewItemsToList(numItems, keyPrefix, 1);
 378
 379     /* Release the item from the hash table */
 380     auto ownedSv = releaseFromHashTable(keyPrefix + std::to_string(numItems));
 381     OrderedStoredValue* nonOwnedSvPtr = ownedSv.get()->toOrderedStoredValue();
 382     size_t svSize = ownedSv->size();
 383     size_t svMetaDataSize = ownedSv->metaDataSize();
 384
 385     /* Mark the item stale */
 386     basicLL->markItemStale(std::move(ownedSv));
 387
 388     /* Check if the StoredValue is marked stale */
 389     {
 390         std::lock_guard<std::mutex> writeGuard(basicLL->getWriteLock());
 391         EXPECT_TRUE(nonOwnedSvPtr->isStale(writeGuard));
 392     }
 393
 394     /* Check if the stale count incremented to 1 */
 395     EXPECT_EQ(1, basicLL->getNumStaleItems());
 396
 397     /* Check if the total item count in the linked list is 1 */
 398     EXPECT_EQ(1, basicLL->getNumItems());
 399
 400     /* Check memory usage of the list as it owns the stale item */
 401     EXPECT_EQ(svSize, basicLL->getStaleValueBytes());
 402     EXPECT_EQ(svMetaDataSize, basicLL->getStaleMetadataBytes());
 403 }