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:
BasicLinkedListTest()38     BasicLinkedListTest() : ht(global_stats, makeFactory(), 2, 1) {
39     }
40 
makeFactory()41     static std::unique_ptr<AbstractStoredValueFactory> makeFactory() {
42         return std::make_unique<OrderedStoredValueFactory>(global_stats);
43     }
44 
45 protected:
SetUp()46     void SetUp() {
47         basicLL = std::make_unique<MockBasicLinkedList>(global_stats);
48     }
49 
TearDown()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      */
addNewItemsToList(seqno_t startSeqno, const std::string& keyPrefix, const int numItems)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                       PROTOCOL_BINARY_RAW_BYTES,
82                       /*theCas*/ 0,
83                       /*bySeqno*/ i);
84             EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
85 
86             sv = ht.find(key, TrackReference::Yes, WantsDeleted::No)
87                          ->toOrderedStoredValue();
88 
89             std::lock_guard<std::mutex> listWriteLg(
90                     basicLL->getListWriteLock());
91             basicLL->appendToList(lg, listWriteLg, *sv);
92             basicLL->updateHighSeqno(listWriteLg, *sv);
93             expectedSeqno.push_back(i);
94         }
95         return expectedSeqno;
96     }
97 
98     /**
99      * Adds one item without a seqno to the linked list
100      */
addItemWithoutSeqno(const std::string& key)101     void addItemWithoutSeqno(const std::string& key) {
102         const std::string val("data");
103 
104         /* Get a fake sequence lock */
105         std::mutex fakeSeqLock;
106         std::lock_guard<std::mutex> lg(fakeSeqLock);
107 
108         StoredDocKey sKey = makeStoredDocKey(key);
109         Item item(sKey, 0, 0, sKey.data(), sKey.size());
110 
111         EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
112 
113         OrderedStoredValue* sv =
114                 ht.find(sKey, TrackReference::Yes, WantsDeleted::No)
115                         ->toOrderedStoredValue();
116 
117         std::lock_guard<std::mutex> listWriteLg(basicLL->getListWriteLock());
118         basicLL->appendToList(lg, listWriteLg, *sv);
119     }
120 
addStaleItem(const std::string& key, seqno_t seqno)121     void addStaleItem(const std::string& key, seqno_t seqno) {
122         const std::string val("data");
123 
124         /* Get a fake sequence lock */
125         std::mutex fakeSeqLock;
126         std::lock_guard<std::mutex> lg(fakeSeqLock);
127 
128         /* add an item */
129         StoredDocKey sKey = makeStoredDocKey(key);
130         Item item(sKey,
131                   0,
132                   0,
133                   val.data(),
134                   val.length(),
135                   PROTOCOL_BINARY_RAW_BYTES,
136                   /*theCas*/ 0,
137                   /*bySeqno*/ seqno);
138         EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
139 
140         OrderedStoredValue* sv =
141                 ht.find(sKey, TrackReference::Yes, WantsDeleted::No)
142                         ->toOrderedStoredValue();
143         std::lock_guard<std::mutex> listWriteLg(basicLL->getListWriteLock());
144         basicLL->appendToList(lg, listWriteLg, *sv);
145         basicLL->updateHighSeqno(listWriteLg, *sv);
146 
147         /* Mark stale */
148         {
149             auto hbl = ht.getLockedBucket(item.getKey());
150             auto ownedSV = ht.unlocked_release(hbl, item.getKey());
151             basicLL->markItemStale(listWriteLg, std::move(ownedSV), nullptr);
152         }
153     }
154 
155     /**
156      * Updates an existing item with key == key and assigns it a seqno of
157      * highSeqno + 1. To be called when there is no range read.
158      */
updateItem(seqno_t highSeqno, const std::string& key)159     void updateItem(seqno_t highSeqno, const std::string& key) {
160         /* Get a fake sequence lock */
161         std::mutex fakeSeqLock;
162         std::lock_guard<std::mutex> lg(fakeSeqLock);
163 
164         OrderedStoredValue* osv = ht.find(makeStoredDocKey(key),
165                                           TrackReference::No,
166                                           WantsDeleted::Yes)
167                                           ->toOrderedStoredValue();
168 
169         std::lock_guard<std::mutex> listWriteLg(basicLL->getListWriteLock());
170         EXPECT_EQ(SequenceList::UpdateStatus::Success,
171                   basicLL->updateListElem(lg, listWriteLg, *osv));
172         osv->setBySeqno(highSeqno + 1);
173         basicLL->updateHighSeqno(listWriteLg, *osv);
174     }
175 
176     /**
177      * Updates an existing item with key == key.
178      * To be called when there is range read.
179      */
updateItemDuringRangeRead(seqno_t highSeqno, const std::string& key)180     void updateItemDuringRangeRead(seqno_t highSeqno, const std::string& key) {
181         const std::string val("data");
182 
183         /* Get a fake sequence lock */
184         std::mutex fakeSeqLock;
185         std::lock_guard<std::mutex> lg(fakeSeqLock);
186 
187         OrderedStoredValue* osv = ht.find(makeStoredDocKey(key),
188                                           TrackReference::No,
189                                           WantsDeleted::Yes)
190                                           ->toOrderedStoredValue();
191 
192         std::lock_guard<std::mutex> listWriteLg(basicLL->getListWriteLock());
193         EXPECT_EQ(SequenceList::UpdateStatus::Append,
194                   basicLL->updateListElem(lg, listWriteLg, *osv));
195 
196         /* Release the current sv from the HT */
197         StoredDocKey sKey = makeStoredDocKey(key);
198         auto hbl = ht.getLockedBucket(sKey);
199         auto ownedSv = ht.unlocked_release(hbl, osv->getKey());
200 
201         /* Add a new storedvalue for the append */
202         Item itm(sKey,
203                  0,
204                  0,
205                  val.data(),
206                  val.length(),
207                  PROTOCOL_BINARY_RAW_BYTES,
208                  /*theCas*/ 0,
209                  /*bySeqno*/ highSeqno + 1);
210         auto* newSv = ht.unlocked_addNewStoredValue(hbl, itm);
211         basicLL->markItemStale(listWriteLg, std::move(ownedSv), newSv);
212 
213         basicLL->appendToList(
214                 lg, listWriteLg, *(newSv->toOrderedStoredValue()));
215         basicLL->updateHighSeqno(listWriteLg, *(newSv->toOrderedStoredValue()));
216     }
217 
218     /**
219      * Deletes an existing item with key == key, puts it onto the linked list
220      * and assigns it a seqno of highSeqno + 1.
221      * To be called when there is no range read.
222      */
softDeleteItem(seqno_t highSeqno, const std::string& key)223     void softDeleteItem(seqno_t highSeqno, const std::string& key) {
224         { /* hbl lock scope */
225             auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
226             StoredValue* sv = ht.unlocked_find(makeStoredDocKey(key),
227                                                hbl.getBucketNum(),
228                                                WantsDeleted::Yes,
229                                                TrackReference::No);
230 
231             ht.unlocked_softDelete(
232                     hbl.getHTLock(), *sv, /* onlyMarkDeleted */ false);
233         }
234 
235         updateItem(highSeqno, key);
236     }
237 
238     /**
239      * Release a StoredValue with 'key' from the hash table
240      */
releaseFromHashTable(const std::string& key)241     StoredValue::UniquePtr releaseFromHashTable(const std::string& key) {
242         auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
243         return ht.unlocked_release(hbl, makeStoredDocKey(key));
244     }
245 
246     /**
247      * Creates an optional 'RangeIterator'. Expected to create the optional
248      * one always.
249      */
getRangeIterator()250     SequenceList::RangeIterator getRangeIterator() {
251         auto itrOptional = basicLL->makeRangeIterator(true /*isBackfill*/);
252         EXPECT_TRUE(itrOptional);
253         return std::move(*itrOptional);
254     }
255 
256     /* We need a HashTable because StoredValue is created only in the HashTable
257        and then put onto the sequence list */
258     HashTable ht;
259     std::unique_ptr<MockBasicLinkedList> basicLL;
260 };
261 
TEST_F(BasicLinkedListTest, SetItems)262 TEST_F(BasicLinkedListTest, SetItems) {
263     const int numItems = 3;
264 
265     /* Add 3 new items */
266     std::vector<seqno_t> expectedSeqno =
267             addNewItemsToList(1, std::string("key"), numItems);
268 
269     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
270 }
271 
TEST_F(BasicLinkedListTest, TestRangeRead)272 TEST_F(BasicLinkedListTest, TestRangeRead) {
273     const int numItems = 3;
274 
275     /* Add 3 new items */
276     addNewItemsToList(1, std::string("key"), numItems);
277 
278     /* Now do a range read */
279     ENGINE_ERROR_CODE status;
280     std::vector<UniqueItemPtr> items;
281     seqno_t endSeqno;
282     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems);
283 
284     EXPECT_EQ(ENGINE_SUCCESS, status);
285     EXPECT_EQ(numItems, items.size());
286     EXPECT_EQ(numItems, items.back()->getBySeqno());
287     EXPECT_EQ(numItems, endSeqno);
288 }
289 
TEST_F(BasicLinkedListTest, TestRangeReadTillInf)290 TEST_F(BasicLinkedListTest, TestRangeReadTillInf) {
291     const int numItems = 3;
292 
293     /* Add 3 new items */
294     addNewItemsToList(1, std::string("key"), numItems);
295 
296     /* Now do a range read */
297     ENGINE_ERROR_CODE status;
298     std::vector<UniqueItemPtr> items;
299     seqno_t endSeqno;
300     std::tie(status, items, endSeqno) =
301             basicLL->rangeRead(1, std::numeric_limits<seqno_t>::max());
302 
303     EXPECT_EQ(ENGINE_SUCCESS, status);
304     EXPECT_EQ(numItems, items.size());
305     EXPECT_EQ(numItems, items.back()->getBySeqno());
306     EXPECT_EQ(numItems, endSeqno);
307 }
308 
TEST_F(BasicLinkedListTest, TestRangeReadFromMid)309 TEST_F(BasicLinkedListTest, TestRangeReadFromMid) {
310     const int numItems = 3;
311 
312     /* Add 3 new items */
313     addNewItemsToList(1, std::string("key"), numItems);
314 
315     /* Now do a range read */
316     ENGINE_ERROR_CODE status;
317     std::vector<UniqueItemPtr> items;
318     seqno_t endSeqno;
319     std::tie(status, items, endSeqno) = basicLL->rangeRead(2, numItems);
320 
321     EXPECT_EQ(ENGINE_SUCCESS, status);
322     EXPECT_EQ(numItems - 1, items.size());
323     EXPECT_EQ(numItems, items.back()->getBySeqno());
324     EXPECT_EQ(numItems, endSeqno);
325 }
326 
TEST_F(BasicLinkedListTest, TestRangeReadStopBeforeEnd)327 TEST_F(BasicLinkedListTest, TestRangeReadStopBeforeEnd) {
328     const int numItems = 3;
329 
330     /* Add 3 new items */
331     addNewItemsToList(1, std::string("key"), numItems);
332 
333     /* Now request for a range read of just 2 items */
334     ENGINE_ERROR_CODE status;
335     std::vector<UniqueItemPtr> items;
336     seqno_t endSeqno;
337     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems - 1);
338 
339     EXPECT_EQ(ENGINE_SUCCESS, status);
340     EXPECT_EQ(numItems - 1, items.size());
341     EXPECT_EQ(numItems - 1, items.back()->getBySeqno());
342     EXPECT_EQ(numItems - 1, endSeqno);
343 }
344 
TEST_F(BasicLinkedListTest, TestRangeReadNegatives)345 TEST_F(BasicLinkedListTest, TestRangeReadNegatives) {
346     const int numItems = 3;
347 
348     /* Add 3 new items */
349     addNewItemsToList(1, std::string("key"), numItems);
350 
351     ENGINE_ERROR_CODE status;
352     std::vector<UniqueItemPtr> items;
353 
354     /* Now do a range read with start > end */
355     std::tie(status, items, std::ignore) = basicLL->rangeRead(2, 1);
356     EXPECT_EQ(ENGINE_ERANGE, status);
357 
358     /* Now do a range read with start > highSeqno */
359     std::tie(status, items, std::ignore) =
360             basicLL->rangeRead(numItems + 1, numItems + 2);
361     EXPECT_EQ(ENGINE_ERANGE, status);
362 }
363 
TEST_F(BasicLinkedListTest, UpdateFirstElem)364 TEST_F(BasicLinkedListTest, UpdateFirstElem) {
365     const int numItems = 3;
366     const std::string keyPrefix("key");
367 
368     /* Add 3 new items */
369     addNewItemsToList(1, keyPrefix, numItems);
370 
371     /* Update the first item in the list */
372     updateItem(numItems, keyPrefix + std::to_string(1));
373 
374     /* Check if the updated element has moved to the end */
375     std::vector<seqno_t> expectedSeqno = {2, 3, 4};
376     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
377 }
378 
TEST_F(BasicLinkedListTest, UpdateMiddleElem)379 TEST_F(BasicLinkedListTest, UpdateMiddleElem) {
380     const int numItems = 3;
381     const std::string keyPrefix("key");
382 
383     /* Add 3 new items */
384     addNewItemsToList(1, keyPrefix, numItems);
385 
386     /* Update a middle item in the list */
387     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
388 
389     /* Check if the updated element has moved to the end */
390     std::vector<seqno_t> expectedSeqno = {1, 3, 4};
391     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
392 }
393 
TEST_F(BasicLinkedListTest, UpdateLastElem)394 TEST_F(BasicLinkedListTest, UpdateLastElem) {
395     const int numItems = 3;
396     const std::string keyPrefix("key");
397 
398     /* Add 3 new items */
399     addNewItemsToList(1, keyPrefix, numItems);
400 
401     /* Update the last item in the list */
402     updateItem(numItems, keyPrefix + std::to_string(numItems));
403 
404     /* Check if the updated element has moved to the end */
405     std::vector<seqno_t> expectedSeqno = {1, 2, 4};
406     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
407 }
408 
TEST_F(BasicLinkedListTest, WriteNewAfterUpdate)409 TEST_F(BasicLinkedListTest, WriteNewAfterUpdate) {
410     const int numItems = 3;
411     const std::string keyPrefix("key");
412 
413     /* Add 3 new items */
414     addNewItemsToList(1, keyPrefix, numItems);
415 
416     /* Update an item in the list */
417     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
418 
419     /* Add a new item after update */
420     addNewItemsToList(
421             numItems + /* +1 is update, another +1 for next */ 2, keyPrefix, 1);
422 
423     /* Check if the new element is added correctly */
424     std::vector<seqno_t> expectedSeqno = {1, 3, 4, 5};
425     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
426 }
427 
TEST_F(BasicLinkedListTest, UpdateDuringRangeRead)428 TEST_F(BasicLinkedListTest, UpdateDuringRangeRead) {
429     const int numItems = 3;
430     const std::string keyPrefix("key");
431 
432     /* Add 3 new items */
433     addNewItemsToList(1, keyPrefix, numItems);
434 
435     basicLL->registerFakeReadRange(1, numItems);
436 
437     /* Update an item in the list when a fake range read is happening */
438     updateItemDuringRangeRead(numItems,
439                               keyPrefix + std::to_string(numItems - 1));
440 
441     /* Check if the new element is added correctly */
442     std::vector<seqno_t> expectedSeqno = {1, 2, 3, 4};
443     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
444 }
445 
TEST_F(BasicLinkedListTest, DeletedItem)446 TEST_F(BasicLinkedListTest, DeletedItem) {
447     const std::string keyPrefix("key");
448     const int numItems = 1;
449 
450     int numDeleted = basicLL->getNumDeletedItems();
451 
452     /* Add an item */
453     addNewItemsToList(numItems, keyPrefix, 1);
454 
455     /* Delete the item */
456     softDeleteItem(numItems, keyPrefix + std::to_string(numItems));
457     basicLL->updateNumDeletedItems(false, true);
458 
459     /* Check if the delete is added correctly */
460     std::vector<seqno_t> expectedSeqno = {numItems + 1};
461     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
462     EXPECT_EQ(numDeleted + 1, basicLL->getNumDeletedItems());
463 }
464 
TEST_F(BasicLinkedListTest, MarkStale)465 TEST_F(BasicLinkedListTest, MarkStale) {
466     const std::string keyPrefix("key");
467     const int numItems = 1;
468 
469     /* To begin with we expect 0 stale items */
470     EXPECT_EQ(0, basicLL->getNumStaleItems());
471 
472     /* Add an item */
473     addNewItemsToList(numItems, keyPrefix, 1);
474 
475     /* Release the item from the hash table */
476     auto ownedSv = releaseFromHashTable(keyPrefix + std::to_string(numItems));
477     OrderedStoredValue* nonOwnedSvPtr = ownedSv->toOrderedStoredValue();
478     size_t svSize = ownedSv->size();
479     size_t svMetaDataSize = ownedSv->metaDataSize();
480 
481     // obtain a replacement SV
482     addNewItemsToList(numItems + 1, keyPrefix, 1);
483     OrderedStoredValue* replacement =
484             ht.find(makeStoredDocKey(keyPrefix + std::to_string(numItems + 1)),
485                     TrackReference::No,
486                     WantsDeleted::Yes)
487                     ->toOrderedStoredValue();
488 
489     /* Mark the item stale */
490     {
491         std::lock_guard<std::mutex> writeGuard(basicLL->getListWriteLock());
492         basicLL->markItemStale(writeGuard, std::move(ownedSv), replacement);
493     }
494 
495     /* Check if the StoredValue is marked stale */
496     {
497         std::lock_guard<std::mutex> writeGuard(basicLL->getListWriteLock());
498         EXPECT_TRUE(nonOwnedSvPtr->isStale(writeGuard));
499     }
500 
501     /* Check if the stale count incremented to 1 */
502     EXPECT_EQ(1, basicLL->getNumStaleItems());
503 
504     /* Check if the total item count in the linked list is 2 */
505     EXPECT_EQ(2, basicLL->getNumItems());
506 
507     /* Check memory usage of the list as it owns the stale item */
508     EXPECT_EQ(svSize, basicLL->getStaleValueBytes());
509     EXPECT_EQ(svMetaDataSize, basicLL->getStaleMetadataBytes());
510 }
511 
TEST_F(BasicLinkedListTest, RangeIterator)512 TEST_F(BasicLinkedListTest, RangeIterator) {
513     const int numItems = 3;
514 
515     /* Add 3 new items */
516     std::vector<seqno_t> expectedSeqno =
517             addNewItemsToList(1, std::string("key"), numItems);
518 
519     auto itr = getRangeIterator();
520 
521     std::vector<seqno_t> actualSeqno;
522 
523     /* Read all the items with the iterator */
524     while (itr.curr() != itr.end()) {
525         actualSeqno.push_back((*itr).getBySeqno());
526         ++itr;
527     }
528     EXPECT_EQ(expectedSeqno, actualSeqno);
529 }
530 
TEST_F(BasicLinkedListTest, RangeIteratorNoItems)531 TEST_F(BasicLinkedListTest, RangeIteratorNoItems) {
532     auto itr = getRangeIterator();
533     /* Since there are no items in the list to iterate over, we expect itr start
534        to be end */
535     EXPECT_EQ(itr.curr(), itr.end());
536 }
537 
TEST_F(BasicLinkedListTest, RangeIteratorSingleItem)538 TEST_F(BasicLinkedListTest, RangeIteratorSingleItem) {
539     /* Add an item */
540     std::vector<seqno_t> expectedSeqno =
541             addNewItemsToList(1, std::string("key"), 1);
542 
543     auto itr = getRangeIterator();
544 
545     std::vector<seqno_t> actualSeqno;
546     /* Read all the items with the iterator */
547     while (itr.curr() != itr.end()) {
548         actualSeqno.push_back((*itr).getBySeqno());
549         ++itr;
550     }
551     EXPECT_EQ(expectedSeqno, actualSeqno);
552 }
553 
TEST_F(BasicLinkedListTest, RangeIteratorOverflow)554 TEST_F(BasicLinkedListTest, RangeIteratorOverflow) {
555     const int numItems = 1;
556     bool caughtOutofRangeExcp = false;
557 
558     /* Add an item */
559     addNewItemsToList(1, std::string("key"), numItems);
560 
561     auto itr = getRangeIterator();
562 
563     /* Iterator till end */
564     while (itr.curr() != itr.end()) {
565         ++itr;
566     }
567 
568     /* Try iterating beyond the end and expect exception to be thrown */
569     try {
570         ++itr;
571     } catch (std::out_of_range&) {
572         caughtOutofRangeExcp = true;
573     }
574     EXPECT_TRUE(caughtOutofRangeExcp);
575 }
576 
TEST_F(BasicLinkedListTest, RangeIteratorDeletion)577 TEST_F(BasicLinkedListTest, RangeIteratorDeletion) {
578     const int numItems = 3;
579 
580     /* Add 3 new items */
581     std::vector<seqno_t> expectedSeqno =
582             addNewItemsToList(1, std::string("key"), numItems);
583 
584     /* Check if second range reader can read items after the first one is
585        deleted */
586     for (int i = 0; i < 2; ++i) {
587         auto itr = getRangeIterator();
588 
589         std::vector<seqno_t> actualSeqno;
590 
591         /* Read all the items with the iterator */
592         while (itr.curr() != itr.end()) {
593             actualSeqno.push_back((*itr).getBySeqno());
594             ++itr;
595         }
596         EXPECT_EQ(expectedSeqno, actualSeqno);
597 
598         /* itr is deleted as each time we loop */
599     }
600 }
601 
TEST_F(BasicLinkedListTest, RangeIteratorAddNewItemDuringRead)602 TEST_F(BasicLinkedListTest, RangeIteratorAddNewItemDuringRead) {
603     const int numItems = 3;
604 
605     /* Add 3 new items */
606     std::vector<seqno_t> expectedSeqno =
607             addNewItemsToList(1, std::string("key"), numItems);
608 
609     {
610         auto itr = getRangeIterator();
611 
612         std::vector<seqno_t> actualSeqno;
613 
614         /* Read one item */
615         actualSeqno.push_back((*itr).getBySeqno());
616         ++itr;
617 
618         /* Add a new item */
619         addNewItemsToList(numItems + 1 /* start */, std::string("key"), 1);
620 
621         /* Read the other items */
622         while (itr.curr() != itr.end()) {
623             actualSeqno.push_back((*itr).getBySeqno());
624             ++itr;
625         }
626         EXPECT_EQ(expectedSeqno, actualSeqno);
627 
628         /* itr is deleted */
629     }
630 
631     /* Now create new iterator and if we can read all elements */
632     expectedSeqno.push_back(numItems + 1);
633 
634     {
635         auto itr = getRangeIterator();
636 
637         std::vector<seqno_t> actualSeqno;
638 
639         /* Read the other items */
640         while (itr.curr() != itr.end()) {
641             actualSeqno.push_back((*itr).getBySeqno());
642             ++itr;
643         }
644         EXPECT_EQ(expectedSeqno, actualSeqno);
645     }
646 }
647 
TEST_F(BasicLinkedListTest, RangeIteratorUpdateItemDuringRead)648 TEST_F(BasicLinkedListTest, RangeIteratorUpdateItemDuringRead) {
649     const int numItems = 3;
650     const std::string keyPrefix("key");
651 
652     /* Add 3 new items */
653     std::vector<seqno_t> expectedSeqno =
654             addNewItemsToList(1, keyPrefix, numItems);
655 
656     {
657         auto itr = getRangeIterator();
658 
659         std::vector<seqno_t> actualSeqno;
660 
661         /* Read one item */
662         actualSeqno.push_back((*itr).getBySeqno());
663         ++itr;
664 
665         /* Update an item */
666         updateItemDuringRangeRead(numItems /*highSeqno*/,
667                                   keyPrefix + std::to_string(2));
668 
669         /* Read the other items */
670         while (itr.curr() != itr.end()) {
671             actualSeqno.push_back((*itr).getBySeqno());
672             ++itr;
673         }
674         EXPECT_EQ(expectedSeqno, actualSeqno);
675 
676         /* itr is deleted */
677     }
678 
679     /* Now create new iterator and if we can read all but duplicate elements */
680     seqno_t exp[] = {1, 3, 4};
681     expectedSeqno =
682             std::vector<seqno_t>(exp, exp + sizeof(exp) / sizeof(seqno_t));
683 
684     {
685         auto itr = getRangeIterator();
686         std::vector<seqno_t> actualSeqno;
687 
688         /* Read the other items */
689         while (itr.curr() != itr.end()) {
690             actualSeqno.push_back((*itr).getBySeqno());
691             ++itr;
692         }
693         EXPECT_EQ(expectedSeqno, actualSeqno);
694     }
695 }
696 
697 /* Creates 2 range iterators such that iterator2 is created after iterator1
698    has read all items, and has hence released the rangeReadLock, but before
699    iterator1 is deleted */
TEST_F(BasicLinkedListTest, MultipleRangeIterator_MB24474)700 TEST_F(BasicLinkedListTest, MultipleRangeIterator_MB24474) {
701     const int numItems = 3;
702     const std::string keyPrefix("key");
703 
704     /* Add 3 items */
705     std::vector<seqno_t> expectedSeqno =
706             addNewItemsToList(1, keyPrefix, numItems);
707 
708     /* Create a 'RangeIterator' on the heap so that it can be deleted before
709        the function scope ends */
710     auto itr1Optional =
711             std::make_unique<boost::optional<SequenceList::RangeIterator>>(
712                     basicLL->makeRangeIterator(true /*isBackfill*/));
713     auto itr1 = std::move(**itr1Optional);
714 
715     /* Read all items */
716     std::vector<seqno_t> actualSeqno;
717     for (; itr1.curr() != itr1.end(); ++(itr1)) {
718         actualSeqno.push_back((*itr1).getBySeqno());
719     }
720     EXPECT_EQ(expectedSeqno, actualSeqno);
721 
722     /* Create another 'RangeIterator' after all items are read from itr1, but
723        before itr1 is deleted */
724     auto itr2 = getRangeIterator();
725     itr1Optional.reset();
726 
727     /* Now read the items after itr1 is deleted */
728     actualSeqno.clear();
729     while (itr2.curr() != itr2.end()) {
730         actualSeqno.push_back((*itr2).getBySeqno());
731         ++itr2;
732     }
733     EXPECT_EQ(expectedSeqno, actualSeqno);
734 }
735 
TEST_F(BasicLinkedListTest, NonBlockingRangeIterators)736 TEST_F(BasicLinkedListTest, NonBlockingRangeIterators) {
737     const int numItems = 3;
738     const std::string keyPrefix("key");
739 
740     /* Add 3 items */
741     std::vector<seqno_t> expectedSeqno =
742             addNewItemsToList(1, keyPrefix, numItems);
743 
744     {
745         auto itr1 = getRangeIterator();
746         auto itr2 = basicLL->makeRangeIterator(true /*isBackfill*/);
747         /* itr1 is already using the list, we cannot have another iterator */
748         EXPECT_FALSE(itr2);
749 
750         /* itr1 goes out of scope and releases the read lock on the list */
751     }
752 
753     /* Iterator created now, should be able to read all items */
754     auto itr = getRangeIterator();
755     std::vector<seqno_t> actualSeqno;
756 
757     /* Read all the items with the iterator */
758     while (itr.curr() != itr.end()) {
759         actualSeqno.push_back((*itr).getBySeqno());
760         ++itr;
761     }
762     EXPECT_EQ(expectedSeqno, actualSeqno);
763 }
764 
TEST_F(BasicLinkedListTest, RangeReadStopsOnInvalidSeqno)765 TEST_F(BasicLinkedListTest, RangeReadStopsOnInvalidSeqno) {
766     /* MB-24376: rangeRead has to stop if it encounters an OSV with a seqno of
767      * -1; this item is definitely past the end of the rangeRead, and has not
768      * yet had its seqno updated in queueDirty */
769     const int numItems = 2;
770     const std::string keyPrefix("key");
771 
772     /* Add 2 new items */
773     addNewItemsToList(1, keyPrefix, numItems);
774 
775     /* Add a key that does not yet have a vaild seqno (say -1) */
776     addItemWithoutSeqno("key3");
777 
778     EXPECT_EQ(-1, basicLL->getSeqList().back().getBySeqno());
779 
780     auto res = basicLL->rangeRead(1, std::numeric_limits<seqno_t>::max());
781 
782     EXPECT_EQ(ENGINE_SUCCESS, std::get<0>(res));
783     EXPECT_EQ(numItems, std::get<1>(res).size());
784     EXPECT_EQ(numItems, std::get<2>(res));
785 }
786 
787 /* 'EphemeralVBucket' (class that has the list) never calls the purge of last
788    element, but the list must support generic purge (that is purge until any
789    element). */
TEST_F(BasicLinkedListTest, PurgeTillLast)790 TEST_F(BasicLinkedListTest, PurgeTillLast) {
791     const int numItems = 2;
792     const std::string keyPrefix("key");
793 
794     /* Add 2 new items */
795     addNewItemsToList(1, keyPrefix, numItems);
796 
797     /* Add a stale item */
798     addStaleItem("stale", numItems + 1);
799     EXPECT_EQ(numItems + 1, basicLL->getNumItems());
800     EXPECT_EQ(1, basicLL->getNumStaleItems());
801 
802     /* Purge the last item */
803     EXPECT_EQ(1, basicLL->purgeTombstones(numItems + 1));
804     EXPECT_EQ(numItems, basicLL->getNumItems());
805     EXPECT_EQ(0, basicLL->getNumStaleItems());
806 
807     /* Should be able to add elements to the list after the purger has run */
808     addNewItemsToList(
809             numItems + 2 /*startseqno*/, keyPrefix, 1 /*add one element*/);
810     std::vector<seqno_t> expectedSeqno = {1, 2, 4};
811     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
812 }
813 
814 /* 'EphemeralVBucket' (class that has the list) never calls the purge of the
815    only element, but the list must support generic purge (that is purge until
816    any element). */
TEST_F(BasicLinkedListTest, PurgeTheOnlyElement)817 TEST_F(BasicLinkedListTest, PurgeTheOnlyElement) {
818     /* Add a stale item */
819     addStaleItem("stale", 1);
820     EXPECT_EQ(1, basicLL->getNumItems());
821     EXPECT_EQ(1, basicLL->getNumStaleItems());
822 
823     /* Purge the only item */
824     EXPECT_EQ(1, basicLL->purgeTombstones(1));
825     EXPECT_EQ(0, basicLL->getNumItems());
826     EXPECT_EQ(0, basicLL->getNumStaleItems());
827 
828     /* Should be able to add elements to the list after the purger has run */
829     addNewItemsToList(2 /*startseqno*/, "key", 1 /*add one element*/);
830     EXPECT_EQ(1, basicLL->getNumItems());
831 }
832 
833 /* 'EphemeralVBucket' (class that has the list) never calls the purge of
834    elements beyond the last element, but the list must support generic purge
835    (that is purge until any element).
836    This is a negative test case which checks that 'purgeTombstones' completes
837    correctly even in the case of a wrong input */
TEST_F(BasicLinkedListTest, PurgeBeyondLast)838 TEST_F(BasicLinkedListTest, PurgeBeyondLast) {
839     const int numItems = 2;
840     const std::string keyPrefix("key");
841 
842     /* Add 2 new items */
843     addNewItemsToList(1, keyPrefix, numItems);
844 
845     /* Add a stale item */
846     addStaleItem("stale", numItems + 1);
847     EXPECT_EQ(numItems + 1, basicLL->getNumItems());
848     EXPECT_EQ(1, basicLL->getNumStaleItems());
849 
850     /* Purge beyond the last item */
851     EXPECT_EQ(1, basicLL->purgeTombstones(numItems + 1000));
852     EXPECT_EQ(numItems, basicLL->getNumItems());
853     EXPECT_EQ(0, basicLL->getNumStaleItems());
854 
855     /* Should be able to add elements to the list after the purger has run */
856     addNewItemsToList(
857             numItems + 2 /*startseqno*/, keyPrefix, 1 /*add one element*/);
858     std::vector<seqno_t> expectedSeqno = {1, 2, 4};
859     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
860 }
861 
TEST_F(BasicLinkedListTest, UpdateDuringPurge)862 TEST_F(BasicLinkedListTest, UpdateDuringPurge) {
863     const int numItems = 2;
864     const std::string keyPrefix("key");
865 
866     /* Add 2 new items */
867     addNewItemsToList(1, keyPrefix, numItems);
868 
869     /* Start the purger, in between send an update. Update is done at a point
870        (first key here) in the linked list that is already visited by
871        the purger, hence we do not expect the update to create a stale copy of
872        the updated item */
873     bool sendUpdateOnce = true;
874     bool afterFirst = false;
875     basicLL->purgeTombstones(numItems, [&]() {
876         /* By sending the update in the callback, we are simulating a
877            scenario where an update happens in between the purge */
878         if (sendUpdateOnce && afterFirst) {
879             sendUpdateOnce = false;
880             /* update first key */
881             updateItem(numItems, keyPrefix + std::to_string(1));
882         }
883         afterFirst = true;
884         return false;
885     });
886 
887     /* Update should succeed */
888     EXPECT_EQ(numItems + 1, basicLL->getHighSeqno());
889     /* Update should not create stale items */
890     EXPECT_EQ(0, basicLL->getNumStaleItems());
891 }
892 
893 /* Run purge when the last item in the list does not yet have a seqno */
TEST_F(BasicLinkedListTest, PurgeWithItemWithoutSeqno)894 TEST_F(BasicLinkedListTest, PurgeWithItemWithoutSeqno) {
895     const int numItems = 2;
896     int expItems = numItems;
897     const std::string keyPrefix("key");
898 
899     /* Add 2 new items */
900     addNewItemsToList(1, keyPrefix, numItems);
901 
902     /* Add a stale item */
903     addStaleItem("stale", numItems + 1);
904     ++expItems;
905     ASSERT_EQ(expItems, basicLL->getNumItems());
906     ASSERT_EQ(1, basicLL->getNumStaleItems());
907 
908     /* Add an item which doesn't yet have a seqno. Such a scenario is possible
909        when an item is added to the list, but seqno for it is yet to be
910        generated */
911     addItemWithoutSeqno("itemInMetaState");
912     ++expItems;
913     ASSERT_EQ(expItems, basicLL->getNumItems());
914 
915     /* Run purge */
916     EXPECT_EQ(1, basicLL->purgeTombstones(numItems + 1));
917     --expItems;
918     EXPECT_EQ(expItems, basicLL->getNumItems());
919     EXPECT_EQ(0, basicLL->getNumStaleItems());
920 }
921 
TEST_F(BasicLinkedListTest, PurgePauseResume)922 TEST_F(BasicLinkedListTest, PurgePauseResume) {
923     const int numItems = 4, numPurgeItems = 2;
924     const std::string keyPrefix("key");
925 
926     /* Add some (numItems/2) new items */
927     addNewItemsToList(1, keyPrefix, numItems / 2);
928 
929     /* Add a stale item */
930     addStaleItem("stale", numItems / 2 + 1);
931 
932     /* Add some more (numItems/2) new items */
933     addNewItemsToList(
934             1 + 1 /* one stale item */ + numItems / 2, keyPrefix, numItems / 2);
935 
936     /* Add another stale item at the end */
937     addStaleItem("stale", 1 + numItems + 1 /* one stale item */);
938 
939     ASSERT_EQ(numItems + numPurgeItems, basicLL->getNumItems());
940     ASSERT_EQ(numPurgeItems, basicLL->getNumStaleItems());
941 
942     /* Purge the list. Set the max purge duration to 0 so that tombstone
943      purging will pause */
944     int purged = 0, numPaused = -1;
945 
946     /* Expect all items to be purged and atleast one pause-resume */
947     while (purged != numPurgeItems) {
948         purged += basicLL->purgeTombstones(numItems + numPurgeItems,
949                                            []() { return true; });
950         ++numPaused;
951     }
952     EXPECT_EQ(0, basicLL->getNumStaleItems());
953     EXPECT_GE(numPaused, 1);
954     EXPECT_EQ(numItems, basicLL->getNumItems());
955 
956     /* Should be able to add elements to the list after the purger has run */
957     addNewItemsToList(numItems + numPurgeItems + 1 /*startseqno*/,
958                       keyPrefix,
959                       1 /*add one element*/);
960     std::vector<seqno_t> expectedSeqno = {1, 2, 4, 5, 7};
961     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
962 }
963 
TEST_F(BasicLinkedListTest, PurgePauseResumeWithUpdate)964 TEST_F(BasicLinkedListTest, PurgePauseResumeWithUpdate) {
965     const int numItems = 2, numPurgeItems = 1;
966     const std::string keyPrefix("key");
967 
968     /* Add a new item */
969     addNewItemsToList(1 /*seqno*/, keyPrefix, 1);
970 
971     /* Add a stale item */
972     addStaleItem("stale", 2 /*seqno*/);
973 
974     /* Add another item */
975     addNewItemsToList(3 /*seqno*/, keyPrefix, 1);
976 
977     ASSERT_EQ(numItems + numPurgeItems, basicLL->getNumItems());
978     ASSERT_EQ(numPurgeItems, basicLL->getNumStaleItems());
979 
980     /* Purge the list. Set the max purge duration to 0 so that tombstone
981      purging will pause */
982     int purged = 0, numPaused = -1;
983 
984     /* Expect all items to be purged and atleast one pause-resume */
985     while (purged != numPurgeItems) {
986         purged += basicLL->purgeTombstones(numItems + numPurgeItems,
987                                            []() { return true; });
988         if (numPaused == -1) {
989             /* During one pause, update some list element (last element here) */
990             updateItem(numItems + numPurgeItems /*high seqno*/,
991                        std::string("key3"));
992         }
993         ++numPaused;
994     }
995     EXPECT_EQ(0, basicLL->getNumStaleItems());
996     EXPECT_GE(numPaused, 1);
997     EXPECT_EQ(numItems, basicLL->getNumItems());
998 }
999 
TEST_F(BasicLinkedListTest, PurgePauseResumeWithUpdateAtPausedPoint)1000 TEST_F(BasicLinkedListTest, PurgePauseResumeWithUpdateAtPausedPoint) {
1001     const int numItems = 4, numPurgeItems = 2;
1002     const std::string keyPrefix("key");
1003 
1004     /* Add some (numItems/2) new items */
1005     addNewItemsToList(1, keyPrefix, numItems / 2);
1006 
1007     /* Add a stale item */
1008     addStaleItem("stale", numItems / 2 + 1);
1009 
1010     /* Add some more (numItems/2) new items */
1011     addNewItemsToList(
1012             1 + 1 /* one stale item */ + numItems / 2, keyPrefix, numItems / 2);
1013 
1014     /* Add another stale item at the end */
1015     addStaleItem("stale", 1 + numItems + 1 /* one stale item */);
1016 
1017     ASSERT_EQ(numItems + numPurgeItems, basicLL->getNumItems());
1018     ASSERT_EQ(numPurgeItems, basicLL->getNumStaleItems());
1019 
1020     /* Purge the list. Set the max purge duration to 0 so that tombstone
1021      purging will pause */
1022     int purged = 0, numPaused = -1;
1023 
1024     /* Expect all items to be purged and atleast one pause-resume */
1025     while (purged != numPurgeItems) {
1026         purged += basicLL->purgeTombstones(numItems + numPurgeItems,
1027                                            []() { return true; });
1028         if (numPaused == -1) {
1029             /* After first call to purgeTombstones() we know that the list is
1030              paused at seqno 2. Update that element */
1031             updateItem(numItems + numPurgeItems /*high seqno*/,
1032                        std::string("key2"));
1033         }
1034         ++numPaused;
1035     }
1036     EXPECT_EQ(0, basicLL->getNumStaleItems());
1037     EXPECT_GE(numPaused, 1);
1038     EXPECT_EQ(numItems, basicLL->getNumItems());
1039 }
1040