MB-24151: Implement general range read iterator in seqlist
[ep-engine.git] / 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         const std::string val("data");
124
125         /* Get a fake sequence lock */
126         std::mutex fakeSeqLock;
127         std::lock_guard<std::mutex> lg(fakeSeqLock);
128
129         OrderedStoredValue* osv = ht.find(makeStoredDocKey(key),
130                                           TrackReference::No,
131                                           WantsDeleted::Yes)
132                                           ->toOrderedStoredValue();
133
134         EXPECT_EQ(SequenceList::UpdateStatus::Append,
135                   basicLL->updateListElem(lg, *osv));
136
137         /* Release the current sv from the HT */
138         StoredDocKey sKey = makeStoredDocKey(key);
139         auto hbl = ht.getLockedBucket(sKey);
140         auto ownedSv = ht.unlocked_release(hbl, osv->getKey());
141         basicLL->markItemStale(std::move(ownedSv));
142
143         /* Add a new storedvalue for the append */
144         Item itm(sKey,
145                  0,
146                  0,
147                  val.data(),
148                  val.length(),
149                  /*ext_meta*/ nullptr,
150                  /*ext_len*/ 0,
151                  /*theCas*/ 0,
152                  /*bySeqno*/ highSeqno + 1);
153         auto newSv = ht.unlocked_addNewStoredValue(hbl, itm);
154
155         basicLL->appendToList(lg, *(newSv->toOrderedStoredValue()));
156         std::lock_guard<std::mutex> highSeqnoLh(basicLL->getHighSeqnosLock());
157         basicLL->updateHighSeqno(highSeqnoLh, *(newSv->toOrderedStoredValue()));
158     }
159
160     /**
161      * Deletes an existing item with key == key, puts it onto the linked list
162      * and assigns it a seqno of highSeqno + 1.
163      * To be called when there is no range read.
164      */
165     void softDeleteItem(seqno_t highSeqno, const std::string& key) {
166         { /* hbl lock scope */
167             auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
168             StoredValue* sv = ht.unlocked_find(makeStoredDocKey(key),
169                                                hbl.getBucketNum(),
170                                                WantsDeleted::Yes,
171                                                TrackReference::No);
172
173             ht.unlocked_softDelete(
174                     hbl.getHTLock(), *sv, /* onlyMarkDeleted */ false);
175         }
176
177         updateItem(highSeqno, key);
178     }
179
180     /**
181      * Release a StoredValue with 'key' from the hash table
182      */
183     StoredValue::UniquePtr releaseFromHashTable(const std::string& key) {
184         auto hbl = ht.getLockedBucket(makeStoredDocKey(key));
185         return ht.unlocked_release(hbl, makeStoredDocKey(key));
186     }
187
188     /* We need a HashTable because StoredValue is created only in the HashTable
189        and then put onto the sequence list */
190     HashTable ht;
191     std::unique_ptr<MockBasicLinkedList> basicLL;
192 };
193
194 TEST_F(BasicLinkedListTest, SetItems) {
195     const int numItems = 3;
196
197     /* Add 3 new items */
198     std::vector<seqno_t> expectedSeqno =
199             addNewItemsToList(1, std::string("key"), numItems);
200
201     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
202 }
203
204 TEST_F(BasicLinkedListTest, TestRangeRead) {
205     const int numItems = 3;
206
207     /* Add 3 new items */
208     addNewItemsToList(1, std::string("key"), numItems);
209
210     /* Now do a range read */
211     ENGINE_ERROR_CODE status;
212     std::vector<UniqueItemPtr> items;
213     seqno_t endSeqno;
214     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems);
215
216     EXPECT_EQ(ENGINE_SUCCESS, status);
217     EXPECT_EQ(numItems, items.size());
218     EXPECT_EQ(numItems, items.back()->getBySeqno());
219     EXPECT_EQ(numItems, endSeqno);
220 }
221
222 TEST_F(BasicLinkedListTest, TestRangeReadTillInf) {
223     const int numItems = 3;
224
225     /* Add 3 new items */
226     addNewItemsToList(1, std::string("key"), numItems);
227
228     /* Now do a range read */
229     ENGINE_ERROR_CODE status;
230     std::vector<UniqueItemPtr> items;
231     seqno_t endSeqno;
232     std::tie(status, items, endSeqno) =
233             basicLL->rangeRead(1, std::numeric_limits<seqno_t>::max());
234
235     EXPECT_EQ(ENGINE_SUCCESS, status);
236     EXPECT_EQ(numItems, items.size());
237     EXPECT_EQ(numItems, items.back()->getBySeqno());
238     EXPECT_EQ(numItems, endSeqno);
239 }
240
241 TEST_F(BasicLinkedListTest, TestRangeReadFromMid) {
242     const int numItems = 3;
243
244     /* Add 3 new items */
245     addNewItemsToList(1, std::string("key"), numItems);
246
247     /* Now do a range read */
248     ENGINE_ERROR_CODE status;
249     std::vector<UniqueItemPtr> items;
250     seqno_t endSeqno;
251     std::tie(status, items, endSeqno) = basicLL->rangeRead(2, numItems);
252
253     EXPECT_EQ(ENGINE_SUCCESS, status);
254     EXPECT_EQ(numItems - 1, items.size());
255     EXPECT_EQ(numItems, items.back()->getBySeqno());
256     EXPECT_EQ(numItems, endSeqno);
257 }
258
259 TEST_F(BasicLinkedListTest, TestRangeReadStopBeforeEnd) {
260     const int numItems = 3;
261
262     /* Add 3 new items */
263     addNewItemsToList(1, std::string("key"), numItems);
264
265     /* Now request for a range read of just 2 items */
266     ENGINE_ERROR_CODE status;
267     std::vector<UniqueItemPtr> items;
268     seqno_t endSeqno;
269     std::tie(status, items, endSeqno) = basicLL->rangeRead(1, numItems - 1);
270
271     EXPECT_EQ(ENGINE_SUCCESS, status);
272     EXPECT_EQ(numItems - 1, items.size());
273     EXPECT_EQ(numItems - 1, items.back()->getBySeqno());
274     EXPECT_EQ(numItems - 1, endSeqno);
275 }
276
277 TEST_F(BasicLinkedListTest, TestRangeReadNegatives) {
278     const int numItems = 3;
279
280     /* Add 3 new items */
281     addNewItemsToList(1, std::string("key"), numItems);
282
283     ENGINE_ERROR_CODE status;
284     std::vector<UniqueItemPtr> items;
285
286     /* Now do a range read with start > end */
287     std::tie(status, items, std::ignore) = basicLL->rangeRead(2, 1);
288     EXPECT_EQ(ENGINE_ERANGE, status);
289
290     /* Now do a range read with start > highSeqno */
291     std::tie(status, items, std::ignore) =
292             basicLL->rangeRead(numItems + 1, numItems + 2);
293     EXPECT_EQ(ENGINE_ERANGE, status);
294 }
295
296 TEST_F(BasicLinkedListTest, UpdateFirstElem) {
297     const int numItems = 3;
298     const std::string keyPrefix("key");
299
300     /* Add 3 new items */
301     addNewItemsToList(1, keyPrefix, numItems);
302
303     /* Update the first item in the list */
304     updateItem(numItems, keyPrefix + std::to_string(1));
305
306     /* Check if the updated element has moved to the end */
307     std::vector<seqno_t> expectedSeqno = {2, 3, 4};
308     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
309 }
310
311 TEST_F(BasicLinkedListTest, UpdateMiddleElem) {
312     const int numItems = 3;
313     const std::string keyPrefix("key");
314
315     /* Add 3 new items */
316     addNewItemsToList(1, keyPrefix, numItems);
317
318     /* Update a middle item in the list */
319     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
320
321     /* Check if the updated element has moved to the end */
322     std::vector<seqno_t> expectedSeqno = {1, 3, 4};
323     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
324 }
325
326 TEST_F(BasicLinkedListTest, UpdateLastElem) {
327     const int numItems = 3;
328     const std::string keyPrefix("key");
329
330     /* Add 3 new items */
331     addNewItemsToList(1, keyPrefix, numItems);
332
333     /* Update the last item in the list */
334     updateItem(numItems, keyPrefix + std::to_string(numItems));
335
336     /* Check if the updated element has moved to the end */
337     std::vector<seqno_t> expectedSeqno = {1, 2, 4};
338     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
339 }
340
341 TEST_F(BasicLinkedListTest, WriteNewAfterUpdate) {
342     const int numItems = 3;
343     const std::string keyPrefix("key");
344
345     /* Add 3 new items */
346     addNewItemsToList(1, keyPrefix, numItems);
347
348     /* Update an item in the list */
349     updateItem(numItems, keyPrefix + std::to_string(numItems - 1));
350
351     /* Add a new item after update */
352     addNewItemsToList(
353             numItems + /* +1 is update, another +1 for next */ 2, keyPrefix, 1);
354
355     /* Check if the new element is added correctly */
356     std::vector<seqno_t> expectedSeqno = {1, 3, 4, 5};
357     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
358 }
359
360 TEST_F(BasicLinkedListTest, UpdateDuringRangeRead) {
361     const int numItems = 3;
362     const std::string keyPrefix("key");
363
364     /* Add 3 new items */
365     addNewItemsToList(1, keyPrefix, numItems);
366
367     basicLL->registerFakeReadRange(1, numItems);
368
369     /* Update an item in the list when a fake range read is happening */
370     updateItemDuringRangeRead(numItems,
371                               keyPrefix + std::to_string(numItems - 1));
372
373     /* Check if the new element is added correctly */
374     std::vector<seqno_t> expectedSeqno = {1, 2, 3, 4};
375     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
376 }
377
378 TEST_F(BasicLinkedListTest, DeletedItem) {
379     const std::string keyPrefix("key");
380     const int numItems = 1;
381
382     int numDeleted = basicLL->getNumDeletedItems();
383
384     /* Add an item */
385     addNewItemsToList(numItems, keyPrefix, 1);
386
387     /* Delete the item */
388     softDeleteItem(numItems, keyPrefix + std::to_string(numItems));
389     basicLL->updateNumDeletedItems(false, true);
390
391     /* Check if the delete is added correctly */
392     std::vector<seqno_t> expectedSeqno = {numItems + 1};
393     EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
394     EXPECT_EQ(numDeleted + 1, basicLL->getNumDeletedItems());
395 }
396
397 TEST_F(BasicLinkedListTest, MarkStale) {
398     const std::string keyPrefix("key");
399     const int numItems = 1;
400
401     /* To begin with we expect 0 stale items */
402     EXPECT_EQ(0, basicLL->getNumStaleItems());
403
404     /* Add an item */
405     addNewItemsToList(numItems, keyPrefix, 1);
406
407     /* Release the item from the hash table */
408     auto ownedSv = releaseFromHashTable(keyPrefix + std::to_string(numItems));
409     OrderedStoredValue* nonOwnedSvPtr = ownedSv.get()->toOrderedStoredValue();
410     size_t svSize = ownedSv->size();
411     size_t svMetaDataSize = ownedSv->metaDataSize();
412
413     /* Mark the item stale */
414     basicLL->markItemStale(std::move(ownedSv));
415
416     /* Check if the StoredValue is marked stale */
417     {
418         std::lock_guard<std::mutex> writeGuard(basicLL->getWriteLock());
419         EXPECT_TRUE(nonOwnedSvPtr->isStale(writeGuard));
420     }
421
422     /* Check if the stale count incremented to 1 */
423     EXPECT_EQ(1, basicLL->getNumStaleItems());
424
425     /* Check if the total item count in the linked list is 1 */
426     EXPECT_EQ(1, basicLL->getNumItems());
427
428     /* Check memory usage of the list as it owns the stale item */
429     EXPECT_EQ(svSize, basicLL->getStaleValueBytes());
430     EXPECT_EQ(svMetaDataSize, basicLL->getStaleMetadataBytes());
431 }
432
433 TEST_F(BasicLinkedListTest, RangeIterator) {
434     const int numItems = 3;
435
436     /* Add 3 new items */
437     std::vector<seqno_t> expectedSeqno =
438             addNewItemsToList(1, std::string("key"), numItems);
439
440     auto itr = basicLL->makeRangeIterator();
441
442     std::vector<seqno_t> actualSeqno;
443
444     /* Read all the items with the iterator */
445     while (itr.curr() != itr.end()) {
446         actualSeqno.push_back((*itr).getBySeqno());
447         ++itr;
448     }
449     EXPECT_EQ(expectedSeqno, actualSeqno);
450 }
451
452 TEST_F(BasicLinkedListTest, RangeIteratorNoItems) {
453     auto itr = basicLL->makeRangeIterator();
454     /* Since there are no items in the list to iterate over, we expect itr start
455        to be end */
456     EXPECT_EQ(itr.curr(), itr.end());
457 }
458
459 TEST_F(BasicLinkedListTest, RangeIteratorSingleItem) {
460     /* Add an item */
461     std::vector<seqno_t> expectedSeqno =
462             addNewItemsToList(1, std::string("key"), 1);
463
464     auto itr = basicLL->makeRangeIterator();
465
466     std::vector<seqno_t> actualSeqno;
467     /* Read all the items with the iterator */
468     while (itr.curr() != itr.end()) {
469         actualSeqno.push_back((*itr).getBySeqno());
470         ++itr;
471     }
472     EXPECT_EQ(expectedSeqno, actualSeqno);
473 }
474
475 TEST_F(BasicLinkedListTest, RangeIteratorOverflow) {
476     const int numItems = 1;
477     bool caughtOutofRangeExcp = false;
478
479     /* Add an item */
480     addNewItemsToList(1, std::string("key"), numItems);
481
482     auto itr = basicLL->makeRangeIterator();
483
484     /* Iterator till end */
485     while (itr.curr() != itr.end()) {
486         ++itr;
487     }
488
489     /* Try iterating beyond the end and expect exception to be thrown */
490     try {
491         ++itr;
492     } catch (std::out_of_range& e) {
493         caughtOutofRangeExcp = true;
494     }
495     EXPECT_TRUE(caughtOutofRangeExcp);
496 }
497
498 TEST_F(BasicLinkedListTest, RangeIteratorDeletion) {
499     const int numItems = 3;
500
501     /* Add 3 new items */
502     std::vector<seqno_t> expectedSeqno =
503             addNewItemsToList(1, std::string("key"), numItems);
504
505     /* Check if second range reader can read items after the first one is
506        deleted */
507     for (int i = 0; i < 2; ++i) {
508         auto itr = basicLL->makeRangeIterator();
509         std::vector<seqno_t> actualSeqno;
510
511         /* Read all the items with the iterator */
512         while (itr.curr() != itr.end()) {
513             actualSeqno.push_back((*itr).getBySeqno());
514             ++itr;
515         }
516         EXPECT_EQ(expectedSeqno, actualSeqno);
517
518         /* itr is deleted as each time we loop */
519     }
520 }
521
522 TEST_F(BasicLinkedListTest, RangeIteratorAddNewItemDuringRead) {
523     const int numItems = 3;
524
525     /* Add 3 new items */
526     std::vector<seqno_t> expectedSeqno =
527             addNewItemsToList(1, std::string("key"), numItems);
528
529     {
530         auto itr = basicLL->makeRangeIterator();
531
532         std::vector<seqno_t> actualSeqno;
533
534         /* Read one item */
535         actualSeqno.push_back((*itr).getBySeqno());
536         ++itr;
537
538         /* Add a new item */
539         addNewItemsToList(numItems + 1 /* start */, std::string("key"), 1);
540
541         /* Read the other items */
542         while (itr.curr() != itr.end()) {
543             actualSeqno.push_back((*itr).getBySeqno());
544             ++itr;
545         }
546         EXPECT_EQ(expectedSeqno, actualSeqno);
547
548         /* itr is deleted */
549     }
550
551     /* Now create new iterator and if we can read all elements */
552     expectedSeqno.push_back(numItems + 1);
553
554     {
555         auto itr = basicLL->makeRangeIterator();
556         std::vector<seqno_t> actualSeqno;
557
558         /* Read the other items */
559         while (itr.curr() != itr.end()) {
560             actualSeqno.push_back((*itr).getBySeqno());
561             ++itr;
562         }
563         EXPECT_EQ(expectedSeqno, actualSeqno);
564     }
565 }
566
567 TEST_F(BasicLinkedListTest, RangeIteratorUpdateItemDuringRead) {
568     const int numItems = 3;
569     const std::string keyPrefix("key");
570
571     /* Add 3 new items */
572     std::vector<seqno_t> expectedSeqno =
573             addNewItemsToList(1, keyPrefix, numItems);
574
575     {
576         auto itr = basicLL->makeRangeIterator();
577
578         std::vector<seqno_t> actualSeqno;
579
580         /* Read one item */
581         actualSeqno.push_back((*itr).getBySeqno());
582         ++itr;
583
584         /* Update an item */
585         updateItemDuringRangeRead(numItems /*highSeqno*/,
586                                   keyPrefix + std::to_string(2));
587
588         /* Read the other items */
589         while (itr.curr() != itr.end()) {
590             actualSeqno.push_back((*itr).getBySeqno());
591             ++itr;
592         }
593         EXPECT_EQ(expectedSeqno, actualSeqno);
594
595         /* itr is deleted */
596     }
597
598     /* Now create new iterator and if we can read all elements */
599     expectedSeqno.push_back(numItems + 1);
600
601     {
602         auto itr = basicLL->makeRangeIterator();
603         std::vector<seqno_t> actualSeqno;
604
605         /* Read the other items */
606         while (itr.curr() != itr.end()) {
607             actualSeqno.push_back((*itr).getBySeqno());
608             ++itr;
609         }
610         EXPECT_EQ(expectedSeqno, actualSeqno);
611     }
612 }