0fbabcc827dee1a29314b9b8e6ea4128f08be781
[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         /* 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 }