1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2010 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 "hash_table_test.h"
19#include "ep_time.h"
20#include "hash_table_stat_visitor.h"
21#include "item.h"
22#include "item_freq_decayer_visitor.h"
23#include "kv_bucket.h"
24#include "programs/engine_testapp/mock_server.h"
25#include "stats.h"
26#include "stored_value_factories.h"
27#include "tests/module_tests/test_helpers.h"
28#include "threadtests.h"
29
30#include <folly/portability/GMock.h>
31#include <folly/portability/GTest.h>
32#include <platform/cb_malloc.h>
33
34#include <signal.h>
35#include <algorithm>
36#include <limits>
37#include <string>
38
39EPStats global_stats;
40
41class Counter : public HashTableVisitor {
42public:
43
44    size_t count;
45    size_t deleted;
46
47    Counter(bool v) : count(), deleted(), verify(v) {}
48
49    bool visit(const HashTable::HashBucketLock& lh, StoredValue& v) {
50        if (v.isDeleted()) {
51            ++deleted;
52        } else {
53            ++count;
54            if (verify) {
55                StoredDocKey key(v.getKey());
56                value_t val = v.getValue();
57                EXPECT_EQ(key.to_string(), val->to_s());
58            }
59        }
60        return true;
61    }
62private:
63    bool verify;
64};
65
66static int count(HashTable &h, bool verify=true) {
67    Counter c(verify);
68    h.visit(c);
69    EXPECT_EQ(h.getNumItems(), c.count + c.deleted);
70    return c.count;
71}
72
73static Item store(HashTable& h, const StoredDocKey& k) {
74    auto value = k.to_string();
75    Item i(k, 0, 0, value.data(), value.size());
76    EXPECT_EQ(MutationStatus::WasClean, h.set(i));
77    return i;
78}
79
80static void storeMany(HashTable &h, std::vector<StoredDocKey> &keys) {
81    for (const auto& key : keys) {
82        store(h, key);
83    }
84}
85
86template <typename T>
87static const char* toString(AddStatus a) {
88    switch(a) {
89    case AddStatus::Success:
90        return "AddStatus::Success";
91    case AddStatus::NoMem:
92        return "AddStatus::NoMem";
93    case AddStatus::Exists:
94        return "AddStatus::Exists";
95    case AddStatus::UnDel:
96        return "AddStatus::UnDel";
97    case AddStatus::AddTmpAndBgFetch:
98        return "AddStatus::AddTmpAndBgFetch";
99    case AddStatus::BgFetch:
100        return "AddStatus::BgFetch";
101    }
102    abort();
103    return NULL;
104}
105
106static std::vector<StoredDocKey> generateKeys(int num, int start=0) {
107    std::vector<StoredDocKey> rv;
108
109    for (int i = start; i < num; i++) {
110        rv.push_back(makeStoredDocKey(std::to_string(i)));
111    }
112
113    return rv;
114}
115
116HashTableTest::HashTableTest() : defaultHtSize(Configuration().getHtSize()) {
117}
118
119bool HashTableTest::del(HashTable& ht, const DocKey& key) {
120    auto htRes = ht.findForWrite(key);
121    if (!htRes.storedValue) {
122        return false;
123    }
124    ht.unlocked_del(htRes.lock, htRes.storedValue);
125    return true;
126}
127
128std::unique_ptr<AbstractStoredValueFactory> HashTableTest::makeFactory(
129        bool isOrdered) {
130    if (isOrdered) {
131        return std::make_unique<OrderedStoredValueFactory>(global_stats);
132    }
133    return std::make_unique<StoredValueFactory>(global_stats);
134}
135
136// ----------------------------------------------------------------------
137// Actual tests below.
138// ----------------------------------------------------------------------
139
140TEST_F(HashTableTest, Size) {
141    HashTable h(global_stats,
142                makeFactory(),
143                defaultHtSize,
144                /*locks*/ 1);
145    ASSERT_EQ(0, count(h));
146
147    store(h, makeStoredDocKey("testkey"));
148
149    EXPECT_EQ(1, count(h));
150}
151
152TEST_F(HashTableTest, SizeTwo) {
153    HashTable h(global_stats,
154                makeFactory(),
155                defaultHtSize,
156                /*locks*/ 1);
157    ASSERT_EQ(0, count(h));
158
159    auto keys = generateKeys(5);
160    storeMany(h, keys);
161    EXPECT_EQ(5, count(h));
162
163    h.clear();
164    EXPECT_EQ(0, count(h));
165}
166
167TEST_F(HashTableTest, ReverseDeletions) {
168    size_t initialSize = global_stats.getCurrentSize();
169    HashTable h(global_stats, makeFactory(), 5, 1);
170    ASSERT_EQ(0, count(h));
171    const int nkeys = 1000;
172
173    auto keys = generateKeys(nkeys);
174    storeMany(h, keys);
175    EXPECT_EQ(nkeys, count(h));
176
177    std::reverse(keys.begin(), keys.end());
178
179    for (const auto& key : keys) {
180        del(h, key);
181    }
182
183    EXPECT_EQ(0, count(h));
184    EXPECT_EQ(initialSize, global_stats.getCurrentSize());
185}
186
187TEST_F(HashTableTest, ForwardDeletions) {
188    size_t initialSize = global_stats.getCurrentSize();
189    HashTable h(global_stats, makeFactory(), 5, 1);
190    ASSERT_EQ(5, h.getSize());
191    ASSERT_EQ(1, h.getNumLocks());
192    ASSERT_EQ(0, count(h));
193    const int nkeys = 1000;
194
195    auto keys = generateKeys(nkeys);
196    storeMany(h, keys);
197    EXPECT_EQ(nkeys, count(h));
198
199    for (const auto& key : keys) {
200        del(h, key);
201    }
202
203    EXPECT_EQ(0, count(h));
204    EXPECT_EQ(initialSize, global_stats.getCurrentSize());
205}
206
207static void verifyFound(HashTable &h, const std::vector<StoredDocKey> &keys) {
208    EXPECT_FALSE(h.findForRead(makeStoredDocKey("aMissingKey")).storedValue);
209
210    for (const auto& key : keys) {
211        EXPECT_TRUE(h.findForRead(key).storedValue);
212    }
213}
214
215static void testFind(HashTable &h) {
216    const int nkeys = 1000;
217
218    auto keys = generateKeys(nkeys);
219    storeMany(h, keys);
220
221    verifyFound(h, keys);
222}
223
224TEST_F(HashTableTest, Find) {
225    HashTable h(global_stats, makeFactory(), 5, 1);
226    testFind(h);
227}
228
229TEST_F(HashTableTest, Resize) {
230    HashTable h(global_stats, makeFactory(), 5, 3);
231
232    auto keys = generateKeys(1000);
233    storeMany(h, keys);
234
235    verifyFound(h, keys);
236
237    h.resize(6143);
238    EXPECT_EQ(6143, h.getSize());
239
240    verifyFound(h, keys);
241
242    h.resize(769);
243    EXPECT_EQ(769, h.getSize());
244
245    verifyFound(h, keys);
246
247    h.resize(static_cast<size_t>(std::numeric_limits<int>::max()) + 17);
248    EXPECT_EQ(769, h.getSize());
249
250    verifyFound(h, keys);
251}
252
253class AccessGenerator : public Generator<bool> {
254public:
255
256    AccessGenerator(const std::vector<StoredDocKey> &k,
257                    HashTable &h) : keys(k), ht(h), size(10000) {
258        std::random_shuffle(keys.begin(), keys.end());
259    }
260
261    bool operator()() {
262        for (const auto& key : keys) {
263            if (rand() % 111 == 0) {
264                resize();
265            }
266            HashTableTest::del(ht, key);
267        }
268        return true;
269    }
270
271private:
272
273    void resize() {
274        ht.resize(size);
275        size = size == 1000 ? 3000 : 1000;
276    }
277
278    std::vector<StoredDocKey>  keys;
279    HashTable                &ht;
280    std::atomic<size_t>       size;
281};
282
283TEST_F(HashTableTest, ConcurrentAccessResize) {
284    HashTable h(global_stats, makeFactory(), 5, 3);
285
286    auto keys = generateKeys(2000);
287    h.resize(keys.size());
288    storeMany(h, keys);
289
290    verifyFound(h, keys);
291
292    srand(918475);
293    AccessGenerator gen(keys, h);
294    getCompletedThreads(4, &gen);
295}
296
297TEST_F(HashTableTest, AutoResize) {
298    HashTable h(global_stats, makeFactory(), 5, 3);
299
300    ASSERT_EQ(5, h.getSize());
301
302    auto keys = generateKeys(1000);
303    storeMany(h, keys);
304
305    verifyFound(h, keys);
306
307    h.resize();
308    EXPECT_EQ(769, h.getSize());
309    verifyFound(h, keys);
310}
311
312TEST_F(HashTableTest, DepthCounting) {
313    HashTable h(global_stats, makeFactory(), 5, 1);
314    const int nkeys = 5000;
315
316    auto keys = generateKeys(nkeys);
317    storeMany(h, keys);
318
319    HashTableDepthStatVisitor depthCounter;
320    h.visitDepth(depthCounter);
321    // std::cout << "Max depth:  " << depthCounter.maxDepth << std::endl;
322    EXPECT_GT(depthCounter.max, 1000);
323}
324
325TEST_F(HashTableTest, PoisonKey) {
326    HashTable h(global_stats, makeFactory(), 5, 1);
327
328    store(h, makeStoredDocKey("A\\NROBs_oc)$zqJ1C.9?XU}Vn^(LW\"`+K/4lykF[ue0{ram;fvId6h=p&Zb3T~SQ]82'ixDP"));
329    EXPECT_EQ(1, count(h));
330}
331
332// Test fixture for HashTable statistics tests.
333class HashTableStatsTest
334    : public HashTableTest,
335      public ::testing::WithParamInterface<std::tuple<EvictionPolicy, bool>> {
336protected:
337    HashTableStatsTest()
338        : ht(stats, makeFactory(), 5, 1),
339          initialSize(0),
340          key(makeStoredDocKey("somekey")),
341          itemSize(16 * 1024),
342          item(key, 0, 0, std::string(itemSize, 'x').data(), itemSize),
343          evictionPolicy(std::get<0>(GetParam())) {
344        // Assign a valid sequence number.
345        item.setBySeqno(10);
346        // Compress if test parameter specifies so
347        if (std::get<1>(GetParam())) {
348            EXPECT_TRUE(item.compressValue());
349        }
350    }
351
352    void SetUp() override {
353        global_stats.reset();
354        ASSERT_EQ(0, ht.getItemMemory());
355        ASSERT_EQ(0, ht.getCacheSize());
356        ASSERT_EQ(0, ht.getUncompressedItemMemory());
357        initialSize = stats.getCurrentSize();
358
359        EXPECT_EQ(0, ht.getNumItems());
360        EXPECT_EQ(0, ht.getNumInMemoryItems());
361        EXPECT_EQ(0, ht.getNumInMemoryNonResItems());
362        EXPECT_EQ(0, ht.getNumTempItems());
363        EXPECT_EQ(0, ht.getNumDeletedItems());
364        EXPECT_EQ(0, ht.getNumSystemItems());
365        EXPECT_EQ(0, ht.getNumPreparedSyncWrites());
366        for (const auto& count : ht.getDatatypeCounts()) {
367            EXPECT_EQ(0, count);
368        }
369    }
370
371    void TearDown() override {
372        EXPECT_EQ(0, ht.getItemMemory());
373        EXPECT_EQ(0, ht.getUncompressedItemMemory());
374        EXPECT_EQ(0, ht.getCacheSize());
375        EXPECT_EQ(initialSize, stats.getCurrentSize());
376
377        if (evictionPolicy == EvictionPolicy::Value) {
378            // Only check is zero for ValueOnly; under full eviction getNumItems
379            // return the total number of items (including those fully evicted).
380            EXPECT_EQ(0, ht.getNumItems());
381        }
382        EXPECT_EQ(0, ht.getNumInMemoryItems());
383        EXPECT_EQ(0, ht.getNumTempItems());
384        EXPECT_EQ(0, ht.getNumDeletedItems());
385        EXPECT_EQ(0, ht.getNumSystemItems());
386        EXPECT_EQ(0, ht.getNumPreparedSyncWrites());
387        for (const auto& datatypeCount : ht.getDatatypeCounts()) {
388            EXPECT_EQ(0, datatypeCount);
389        }
390    }
391
392    StoredValue* addAndEjectItem() {
393        EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
394
395        auto result(ht.findForWrite(key));
396        EXPECT_TRUE(result.storedValue);
397        result.storedValue->markClean();
398        EXPECT_TRUE(ht.unlocked_ejectItem(
399                result.lock, result.storedValue, evictionPolicy));
400        return result.storedValue;
401    }
402
403    EPStats stats;
404    HashTable ht;
405    size_t initialSize;
406    const StoredDocKey key;
407    const size_t itemSize;
408    Item item;
409    const EvictionPolicy evictionPolicy;
410};
411
412TEST_P(HashTableStatsTest, Size) {
413    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
414
415    del(ht, key);
416}
417
418TEST_P(HashTableStatsTest, SizeFlush) {
419    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
420
421    ht.clear();
422}
423
424TEST_P(HashTableStatsTest, SizeEject) {
425    addAndEjectItem();
426
427    del(ht, key);
428}
429
430// Check sizes when ejecting a value and then restoring it.
431TEST_P(HashTableStatsTest, SizeEjectRestoreValue) {
432    auto* v = addAndEjectItem();
433
434    if (evictionPolicy == EvictionPolicy::Value) {
435        // Value-only: expect to have metadata still present.
436        EXPECT_EQ(1, ht.getNumItems());
437        EXPECT_EQ(1, ht.getNumInMemoryNonResItems());
438        EXPECT_EQ(v->metaDataSize(), ht.getUncompressedItemMemory())
439                << "Expected uncompressed memory to be sizeof metadata after "
440                   "evicting";
441        EXPECT_EQ(1, ht.getDatatypeCounts()[item.getDataType()]);
442    }
443
444    if (evictionPolicy == EvictionPolicy::Full) {
445        // ejectItem() will have removed both the value and meta.
446        EXPECT_EQ(0, ht.getNumItems());
447        EXPECT_EQ(0, ht.getNumInMemoryNonResItems());
448        EXPECT_EQ(0, ht.getUncompressedItemMemory());
449        EXPECT_EQ(0, ht.getDatatypeCounts()[item.getDataType()]);
450
451        // Need a new tempItem (metadata) to restore value into.
452        Item temp(key,
453                  0,
454                  0,
455                  nullptr,
456                  0,
457                  PROTOCOL_BINARY_RAW_BYTES,
458                  0,
459                  StoredValue::state_temp_init);
460        auto hbl = ht.getLockedBucket(key);
461        v = ht.unlocked_addNewStoredValue(hbl, temp);
462        EXPECT_EQ(1, ht.getNumTempItems());
463    }
464
465    {
466        auto hbl = ht.getLockedBucket(key);
467        EXPECT_TRUE(ht.unlocked_restoreValue(hbl.getHTLock(), item, *v));
468    }
469
470    EXPECT_EQ(0, ht.getNumInMemoryNonResItems());
471    EXPECT_EQ(1, ht.getDatatypeCounts()[item.getDataType()]);
472
473    del(ht, key);
474}
475
476// Check sizes when ejecting an item and then restoring metadata.
477TEST_P(HashTableStatsTest, SizeEjectRestoreMeta) {
478    if (evictionPolicy == EvictionPolicy::Value) {
479        // restoreMeta only valid for Full eviction - metadata is
480        // unevictable in value-only.
481        return;
482    }
483
484    addAndEjectItem();
485
486    // ejectItem() will have removed both the value and meta. Need
487    // a new tempItem (metadata) to restore metdata into.
488    Item temp(key,
489              0,
490              0,
491              nullptr,
492              0,
493              PROTOCOL_BINARY_RAW_BYTES,
494              0,
495              StoredValue::state_temp_init);
496    {
497        auto hbl = ht.getLockedBucket(key);
498        auto* v = ht.unlocked_addNewStoredValue(hbl, temp);
499        EXPECT_EQ(1, ht.getNumTempItems());
500        ht.unlocked_restoreMeta(hbl.getHTLock(), item, *v);
501        EXPECT_EQ(1, ht.getNumInMemoryNonResItems());
502    }
503
504    del(ht, key);
505}
506
507TEST_P(HashTableStatsTest, EjectFlush) {
508    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
509
510    EXPECT_EQ(1, ht.getNumItems());
511    EXPECT_EQ(1, ht.getNumInMemoryItems());
512    EXPECT_EQ(0, ht.getNumInMemoryNonResItems());
513    EXPECT_EQ(0, ht.getNumTempItems());
514    EXPECT_EQ(0, ht.getNumDeletedItems());
515
516    {
517        auto item(ht.findForWrite(key));
518        EXPECT_TRUE(item.storedValue);
519        item.storedValue->markClean();
520        EXPECT_TRUE(ht.unlocked_ejectItem(
521                item.lock, item.storedValue, evictionPolicy));
522    }
523
524    switch (evictionPolicy) {
525    case EvictionPolicy::Value:
526        EXPECT_EQ(1, ht.getNumItems());
527        EXPECT_EQ(1, ht.getNumInMemoryItems());
528        EXPECT_EQ(1, ht.getNumInMemoryNonResItems());
529        break;
530    case EvictionPolicy::Full:
531        // In full-eviction, ejectItem() also ejects the metadata; hence will
532        // have 0 items in HashTable.
533        EXPECT_EQ(0, ht.getNumItems());
534        EXPECT_EQ(0, ht.getNumInMemoryItems());
535        EXPECT_EQ(0, ht.getNumInMemoryNonResItems());
536        break;
537    }
538    EXPECT_EQ(0, ht.getNumTempItems());
539    EXPECT_EQ(0, ht.getNumDeletedItems());
540
541    ht.clear();
542}
543
544/*
545 * Test that when unlocked_ejectItem returns false indicating that it failed
546 * to eject an item, the stat numFailedEjects increases by one.
547 */
548TEST_P(HashTableStatsTest, numFailedEjects) {
549    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
550    EXPECT_EQ(0, stats.numFailedEjects);
551    {
552        auto item(ht.findForWrite(key));
553        EXPECT_TRUE(item.storedValue);
554        EXPECT_FALSE(ht.unlocked_ejectItem(
555                item.lock, item.storedValue, evictionPolicy));
556        EXPECT_EQ(1, stats.numFailedEjects);
557    }
558    ht.clear();
559}
560
561/**
562 * MB-26126: Check that NumNonResident item counts are correct when restoring
563 * a Deleted value to an metadata-only StoredValue.
564 */
565TEST_P(HashTableStatsTest, TempDeletedRestore) {
566    // Add (deleted) item; then remove from HT.
567    item.setDeleted();
568    ASSERT_EQ(MutationStatus::WasClean, ht.set(item));
569    { // Locking scope.
570        auto item = ht.findForWrite(key);
571        ASSERT_NE(nullptr, item.storedValue);
572        item.storedValue->markClean();
573        ht.unlocked_del(item.lock, item.storedValue);
574    }
575
576    // Restore as temporary initial item (simulating bg_fetch).
577    Item tempInitItem(key,
578                      0,
579                      0,
580                      nullptr,
581                      0,
582                      PROTOCOL_BINARY_RAW_BYTES,
583                      0,
584                      StoredValue::state_temp_init);
585    {
586        // Locking scope.
587        auto hbl = ht.getLockedBucket(key);
588        auto* sv = ht.unlocked_addNewStoredValue(hbl, tempInitItem);
589        ASSERT_NE(nullptr, sv);
590
591        // Restore the metadata for the (deleted) item.
592        ht.unlocked_restoreMeta(hbl.getHTLock(), item, *sv);
593
594        // Check counts:
595        EXPECT_EQ(0, ht.getNumItems())
596                << "Deleted, meta shouldn't be counted in numItems";
597        EXPECT_EQ(0, ht.getNumInMemoryItems())
598                << "Deleted, meta shouldn't be counted as in-memory";
599        EXPECT_EQ(0, ht.getNumInMemoryNonResItems())
600                << "Deleted, meta shouldn't be counted as non-resident";
601        EXPECT_EQ(1, ht.getNumTempItems())
602                << "Deleted, meta should count as temp items";
603        EXPECT_EQ(0, ht.getNumDeletedItems())
604                << "Deleted, meta shouldn't count as deleted items";
605
606        // Now restore the whole (deleted) value.
607        EXPECT_TRUE(ht.unlocked_restoreValue(hbl.getHTLock(), item, *sv));
608    }
609
610    // Check counts:
611    EXPECT_EQ(1, ht.getNumItems())
612            << "Deleted items should be counted in numItems";
613    EXPECT_EQ(1, ht.getNumInMemoryItems())
614            << "Deleted items should be counted as in-memory";
615    EXPECT_EQ(0, ht.getNumInMemoryNonResItems())
616            << "Deleted items shouldn't be counted as non-resident";
617    EXPECT_EQ(0, ht.getNumTempItems())
618            << "Deleted shouldn't count as temp items";
619    EXPECT_EQ(1, ht.getNumDeletedItems())
620            << "Deleted items should count as deleted items";
621
622    // Cleanup, all counts should become zero.
623    del(ht, key);
624}
625
626/// Check counts for a soft-deleted item.
627TEST_P(HashTableStatsTest, SoftDelete) {
628    ASSERT_EQ(MutationStatus::WasClean, ht.set(item));
629
630    {
631        // Mark the item as deleted. Locking scope.
632        auto htRes = ht.findForWrite(key, WantsDeleted::No);
633        ASSERT_NE(nullptr, htRes.storedValue);
634        ht.unlocked_softDelete(htRes.lock,
635                               *htRes.storedValue,
636                               /*onlyMarkDeleted*/ true,
637                               DeleteSource::Explicit);
638    }
639
640    // Check counts:
641    EXPECT_EQ(1, ht.getNumItems())
642            << "Deleted items should be counted in numItems";
643    EXPECT_EQ(1, ht.getNumInMemoryItems())
644            << "Deleted items should be counted as in-memory";
645    EXPECT_EQ(0, ht.getNumInMemoryNonResItems())
646            << "Deleted items shouldn't be counted as non-resident";
647    EXPECT_EQ(0, ht.getNumTempItems())
648            << "Deleted shouldn't count as temp items";
649    EXPECT_EQ(1, ht.getNumDeletedItems())
650            << "Deleted items should count as deleted items";
651
652    // Cleanup, all counts should become zero.
653    del(ht, key);
654}
655
656/**
657 * Test to track if the size of the uncompressed item memory
658 * is updated correctly
659 */
660TEST_P(HashTableStatsTest, UncompressedMemorySizeTest) {
661    HashTable ht(global_stats, makeFactory(true), 2, 1);
662
663    std::string valueData(
664            "{\"product\": \"car\",\"price\": \"100\"},"
665            "{\"product\": \"bus\",\"price\": \"1000\"},"
666            "{\"product\": \"Train\",\"price\": \"100000\"}");
667
668    auto item = makeCompressibleItem(Vbid(0),
669                                     makeStoredDocKey("key0"),
670                                     valueData,
671                                     PROTOCOL_BINARY_DATATYPE_JSON,
672                                     true);
673
674    ASSERT_EQ(MutationStatus::WasClean, ht.set(*item));
675
676    /**
677     * Ensure that length of the value stored is the same as the length
678     * of the compressed item
679     */
680    const auto* v = ht.findForRead(makeStoredDocKey("key0")).storedValue;
681    EXPECT_NE(nullptr, v);
682    EXPECT_EQ(item->getNBytes(), v->valuelen());
683
684    EXPECT_EQ(1, ht.getNumItems());
685    EXPECT_EQ(ht.getUncompressedItemMemory(),
686              v->metaDataSize() + valueData.length());
687
688    ASSERT_TRUE(del(ht, makeStoredDocKey("key0")));
689
690    EXPECT_EQ(0, ht.getNumItems());
691    EXPECT_EQ(0, ht.getUncompressedItemMemory());
692}
693
694TEST_P(HashTableStatsTest, SystemEventItem) {
695    HashTable ht(global_stats, makeFactory(true), 128, 1);
696    StoredDocKey key("key", CollectionID::System);
697    store(ht, key);
698    EXPECT_EQ(1, ht.getNumSystemItems());
699
700    EXPECT_TRUE(del(ht, key));
701    EXPECT_EQ(0, ht.getNumSystemItems());
702}
703
704// Test case for the collections purging path. We mark a system event as deleted
705// so need to be able to deal with deleted system events in stats.
706// In particular, removing a "deleted" system event item from the hash table
707// should not cause us to update the numDeletedItems stat because we do not
708// want to track system events in numDeletedItems
709TEST_P(HashTableStatsTest, DeletedSystemEventItem) {
710    HashTable ht(global_stats, makeFactory(true), 128, 1);
711    StoredDocKey key("key", CollectionID::System);
712    store(ht, key);
713    ASSERT_EQ(1, ht.getNumSystemItems());
714    ASSERT_EQ(0, ht.getNumDeletedItems());
715
716    // Jump through a couple hoops to delete the thing, need the old StoredValue
717    // and a new "deleted" system event item
718    StoredValue* found = ht.findForWrite(key, WantsDeleted::No).storedValue;
719    Item item(key, 0, 0, "", strlen(""));
720    item.setDeleted(DeleteSource::Explicit);
721
722    // Mark our item as deleted
723    { // Scope for hbl so that we can del later
724        auto hbl = ht.getLockedBucket(key);
725        ht.unlocked_updateStoredValue(hbl, *found, item);
726    }
727    ASSERT_EQ(1, ht.getNumSystemItems());
728
729    // We shouldn't throw anything (i.e. underflow stat counters) but we also
730    // need to check the values in case we have turned assertions off.
731    bool delRes = false;
732    ASSERT_NO_THROW(delRes = del(ht, key));
733    EXPECT_TRUE(delRes);
734    EXPECT_EQ(0, ht.getNumSystemItems());
735    EXPECT_EQ(0, ht.getNumDeletedItems());
736}
737
738TEST_P(HashTableStatsTest, PreparedSyncWrite) {
739    // Setup
740    HashTable ht(global_stats, makeFactory(true), 128, 1);
741    auto prepared = makePendingItem(key, "prepared");
742    ASSERT_EQ(MutationStatus::WasClean, ht.set(*prepared));
743
744    // Test
745    EXPECT_EQ(1, ht.getNumPreparedSyncWrites());
746    EXPECT_EQ(1, ht.getNumItems());
747    for (const auto& count : ht.getDatatypeCounts()) {
748        EXPECT_EQ(0, count);
749    }
750
751    // Cleanup
752    EXPECT_TRUE(del(ht, key));
753}
754
755TEST_P(HashTableStatsTest, PreparedSyncDelete) {
756    // Setup
757    HashTable ht(global_stats, makeFactory(true), 128, 1);
758    auto prepared = makePendingItem(key, "prepared");
759    prepared->setDeleted(DeleteSource::Explicit);
760    ASSERT_EQ(MutationStatus::WasClean, ht.set(*prepared));
761
762    // Test
763    EXPECT_EQ(1, ht.getNumPreparedSyncWrites());
764    EXPECT_EQ(1, ht.getNumItems());
765    EXPECT_EQ(0, ht.getNumDeletedItems())
766            << "NumDeletedItems should not include prepared SyncDeletes";
767    for (const auto& count : ht.getDatatypeCounts()) {
768        EXPECT_EQ(0, count);
769    }
770
771    // Cleanup
772    EXPECT_TRUE(del(ht, key));
773}
774
775INSTANTIATE_TEST_CASE_P(
776        ValueAndFullEviction,
777        HashTableStatsTest,
778        ::testing::Combine(::testing::Values(EvictionPolicy::Value,
779                                             EvictionPolicy::Full),
780                           ::testing::Bool()), );
781
782TEST_F(HashTableTest, ItemAge) {
783    // Setup
784    HashTable ht(global_stats, makeFactory(), 5, 1);
785    StoredDocKey key = makeStoredDocKey("key");
786    Item item(key, 0, 0, "value", strlen("value"));
787    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
788
789    // Test
790    StoredValue* v(ht.findForWrite(key).storedValue);
791    EXPECT_EQ(0, v->getValue()->getAge());
792    v->getValue()->incrementAge();
793    EXPECT_EQ(1, v->getValue()->getAge());
794
795    // Check saturation of age.
796    for (int ii = 0; ii < 300; ii++) {
797        v->getValue()->incrementAge();
798    }
799    EXPECT_EQ(0xff, v->getValue()->getAge());
800
801    // Check reset of age after reallocation.
802    v->reallocate();
803    EXPECT_EQ(0, v->getValue()->getAge());
804
805    // Check changing age when new value is used.
806    Item item2(key, 0, 0, "value2", strlen("value2"));
807    item2.getValue()->incrementAge();
808    auto hbl = ht.getLockedBucket(key);
809    auto updated = ht.unlocked_updateStoredValue(hbl, *v, item2);
810    ASSERT_TRUE(updated.storedValue);
811    EXPECT_EQ(1, updated.storedValue->getValue()->getAge());
812}
813
814// Check not specifying results in the INITIAL_NRU_VALUE.
815TEST_F(HashTableTest, NRUDefault) {
816    // Setup
817    HashTable ht(global_stats, makeFactory(), 5, 1);
818    StoredDocKey key = makeStoredDocKey("key");
819
820    Item item(key, 0, 0, "value", strlen("value"));
821    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
822
823    // trackReferenced=false so we don't modify the NRU while validating it.
824    const auto* v(ht.findForRead(key, TrackReference::No).storedValue);
825    EXPECT_NE(nullptr, v);
826    EXPECT_EQ(INITIAL_NRU_VALUE, v->getNRUValue());
827
828    // Check that find() by default /does/ update NRU.
829    v = ht.findForRead(key).storedValue;
830    EXPECT_NE(nullptr, v);
831    EXPECT_EQ(INITIAL_NRU_VALUE - 1, v->getNRUValue());
832}
833
834// Check a specific NRU value (minimum)
835TEST_F(HashTableTest, NRUMinimum) {
836    // Setup
837    HashTable ht(global_stats, makeFactory(), 5, 1);
838    StoredDocKey key = makeStoredDocKey("key");
839
840    Item item(key, 0, 0, "value", strlen("value"));
841    item.setNRUValue(MIN_NRU_VALUE);
842    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
843
844    // trackReferenced=false so we don't modify the NRU while validating it.
845    const auto* v(ht.findForRead(key, TrackReference::No).storedValue);
846    EXPECT_NE(nullptr, v);
847    EXPECT_EQ(MIN_NRU_VALUE, v->getNRUValue());
848}
849
850// MB-27223 Check that NRU value is not modified when we set an already existing
851// item
852TEST_F(HashTableTest, NRUMinimumExistingItem) {
853    // Setup
854    HashTable ht(global_stats, makeFactory(), 5, 1);
855    StoredDocKey key = makeStoredDocKey("key");
856
857    Item item(key, 0, 0, "value", strlen("value"));
858    item.setNRUValue(MIN_NRU_VALUE);
859    EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
860    // Now repeat the set, so the item will be found in the hashtable and
861    // considered an update.
862    EXPECT_EQ(MutationStatus::WasDirty, ht.set(item));
863    // trackReferenced=false so we don't modify the NRU while validating it.
864    const auto* v(ht.findForRead(key, TrackReference::No).storedValue);
865    EXPECT_NE(nullptr, v);
866    EXPECT_EQ(MIN_NRU_VALUE, v->getNRUValue());
867}
868
869/* Test release from HT (but not deletion) of an (HT) element */
870TEST_F(HashTableTest, ReleaseItem) {
871    /* Setup with 2 hash buckets and 1 lock */
872    HashTable ht(global_stats, makeFactory(), 2, 1);
873
874    /* Write 5 items (there are 2 hash buckets, we want to test removing a head
875       element and a non-head element) */
876    const int numItems = 5;
877    std::string val("value");
878
879    for (int i = 0; i < numItems; ++i) {
880        StoredDocKey key =
881                makeStoredDocKey(std::string("key" + std::to_string(i)));
882        Item item(key, 0, 0, val.data(), val.length());
883        EXPECT_EQ(MutationStatus::WasClean, ht.set(item));
884    }
885    EXPECT_EQ(numItems, ht.getNumItems());
886
887    /* Remove the element added first. This is not (most likely because we
888       might have a rare case wherein 4 items are hashed to one bucket and
889       "removeKey1" would be a lone element in the other hash bucket) a head
890       element of a hash bucket */
891    StoredDocKey releaseKey1 =
892            makeStoredDocKey(std::string("key" + std::to_string(0)));
893
894    {
895        // Locking scope.
896        auto vToRelease1 = ht.findForWrite(releaseKey1, WantsDeleted::Yes);
897        auto releasedSv1 =
898                ht.unlocked_release(vToRelease1.lock, vToRelease1.storedValue);
899
900        /* Validate the copied contents */
901        EXPECT_EQ(*vToRelease1.storedValue, *(releasedSv1).get());
902
903        /* Validate the HT element replace (hence released from HT) */
904        EXPECT_EQ(vToRelease1.storedValue, releasedSv1.get().get());
905
906        /* Validate the HT count */
907        EXPECT_EQ(numItems - 1, ht.getNumItems());
908    }
909
910    /* Remove the element added last. This is certainly the head element of a
911       hash bucket */
912    StoredDocKey releaseKey2 =
913            makeStoredDocKey(std::string("key" + std::to_string(numItems - 1)));
914
915    auto vToRelease2 = ht.findForWrite(releaseKey2);
916    auto releasedSv2 =
917            ht.unlocked_release(vToRelease2.lock, vToRelease2.storedValue);
918
919    /* Validate the copied contents */
920    EXPECT_EQ(*vToRelease2.storedValue, *(releasedSv2).get());
921
922    /* Validate the HT element replace (hence released from HT) */
923    EXPECT_EQ(vToRelease2.storedValue, releasedSv2.get().get());
924
925    /* Validate the HT count */
926    EXPECT_EQ(numItems - 2, ht.getNumItems());
927}
928
929/* Test copying an element in HT */
930TEST_F(HashTableTest, CopyItem) {
931    /* Setup with 2 hash buckets and 1 lock. Note: Copying is allowed only on
932       OrderedStoredValues and hence hash table must have
933       OrderedStoredValueFactory */
934    HashTable ht(global_stats, makeFactory(true), 2, 1);
935
936    /* Write 3 items */
937    const int numItems = 3;
938    auto keys = generateKeys(numItems);
939    storeMany(ht, keys);
940
941    /* Replace the StoredValue in the HT by its copy */
942    StoredDocKey copyKey = makeStoredDocKey(std::string(std::to_string(0)));
943    auto replace = ht.findForWrite(copyKey);
944
945    /* Record some stats before 'replace by copy' */
946    auto metaDataMemBeforeCopy = ht.getMetadataMemory();
947    auto datatypeCountsBeforeCopy = ht.getDatatypeCounts();
948    auto cacheSizeBeforeCopy = ht.getCacheSize();
949    auto memSizeBeforeCopy = ht.getItemMemory();
950    auto statsCurrSizeBeforeCopy = global_stats.getCurrentSize();
951
952    auto res = ht.unlocked_replaceByCopy(replace.lock, *replace.storedValue);
953
954    /* Validate the copied contents */
955    EXPECT_EQ(*replace.storedValue, *(res.first));
956
957    /* Validate the HT element replace (hence released from HT) */
958    EXPECT_EQ(replace.storedValue, res.second.get().get());
959
960    /* Validate the HT count */
961    EXPECT_EQ(numItems, ht.getNumItems());
962
963    /* Stats should be equal to that before 'replaceByCopy' */
964    EXPECT_EQ(metaDataMemBeforeCopy, ht.getMetadataMemory());
965    EXPECT_EQ(datatypeCountsBeforeCopy, ht.getDatatypeCounts());
966    EXPECT_EQ(cacheSizeBeforeCopy, ht.getCacheSize());
967    EXPECT_EQ(memSizeBeforeCopy, ht.getItemMemory());
968    EXPECT_EQ(statsCurrSizeBeforeCopy, global_stats.getCurrentSize());
969}
970
971/* Test copying a deleted element in HT */
972TEST_F(HashTableTest, CopyDeletedItem) {
973    /* Setup with 2 hash buckets and 1 lock. Note: Copying is allowed only on
974       OrderedStoredValues and hence hash table must have
975       OrderedStoredValueFactory */
976    HashTable ht(global_stats, makeFactory(true), 2, 1);
977
978    /* Write 3 items */
979    const int numItems = 3;
980    auto keys = generateKeys(numItems);
981    storeMany(ht, keys);
982
983    /* Delete a StoredValue */
984    StoredDocKey copyKey = makeStoredDocKey(std::string(std::to_string(0)));
985    auto replace = ht.findForWrite(copyKey);
986
987    ht.unlocked_softDelete(replace.lock,
988                           *replace.storedValue,
989                           /* onlyMarkDeleted */ false,
990                           DeleteSource::Explicit);
991    EXPECT_EQ(numItems, ht.getNumItems());
992    const int expNumDeletedItems = 1;
993    EXPECT_EQ(expNumDeletedItems, ht.getNumDeletedItems());
994
995    /* Record some stats before 'replace by copy' */
996    auto metaDataMemBeforeCopy = ht.getMetadataMemory();
997    auto datatypeCountsBeforeCopy = ht.getDatatypeCounts();
998    auto cacheSizeBeforeCopy = ht.getCacheSize();
999    auto memSizeBeforeCopy = ht.getItemMemory();
1000    auto statsCurrSizeBeforeCopy = global_stats.getCurrentSize();
1001
1002    /* Replace the StoredValue in the HT by its copy */
1003    auto res = ht.unlocked_replaceByCopy(replace.lock, *replace.storedValue);
1004
1005    /* Validate the copied contents */
1006    EXPECT_EQ(*replace.storedValue, *(res.first));
1007
1008    /* Validate the HT element replace (hence released from HT) */
1009    EXPECT_EQ(replace.storedValue, res.second.get().get());
1010
1011    /* Validate the HT count */
1012    EXPECT_EQ(numItems, ht.getNumItems());
1013    EXPECT_EQ(expNumDeletedItems, ht.getNumDeletedItems());
1014
1015    /* Stats should be equal to that before 'replaceByCopy' */
1016    EXPECT_EQ(metaDataMemBeforeCopy, ht.getMetadataMemory());
1017    EXPECT_EQ(datatypeCountsBeforeCopy, ht.getDatatypeCounts());
1018    EXPECT_EQ(cacheSizeBeforeCopy, ht.getCacheSize());
1019    EXPECT_EQ(memSizeBeforeCopy, ht.getItemMemory());
1020    EXPECT_EQ(statsCurrSizeBeforeCopy, global_stats.getCurrentSize());
1021}
1022
1023// Check that an OSV which was deleted and then made alive again has the
1024// lock expiry correctly reset (lock_expiry is stored in the same place as
1025// deleted time).
1026TEST_F(HashTableTest, LockAfterDelete) {
1027    /* Setup OSVFactory with 2 hash buckets and 1 lock. */
1028    HashTable ht(global_stats, makeFactory(true), 2, 1);
1029
1030    // Delete a key, giving it a non-zero delete time.
1031    auto key = makeStoredDocKey("key");
1032    StoredValue* sv;
1033    store(ht, key);
1034    {
1035        auto toDelete = ht.findForWrite(key);
1036        sv = toDelete.storedValue;
1037        TimeTraveller toTheFuture(1985);
1038        ht.unlocked_softDelete(toDelete.lock,
1039                               *sv,
1040                               /* onlyMarkDeleted */ false,
1041                               DeleteSource::Explicit);
1042    }
1043    ASSERT_EQ(1, ht.getNumItems());
1044    ASSERT_EQ(1, ht.getNumDeletedItems());
1045
1046    // Sanity check - deleted time should be set.
1047    auto* osv = sv->toOrderedStoredValue();
1048    ASSERT_GE(osv->getCompletedOrDeletedTime(), ep_abs_time(1985));
1049
1050    // Now re-create the same key (as alive).
1051    Item i(key, 0, 0, key.data(), key.size());
1052    EXPECT_EQ(MutationStatus::WasDirty, ht.set(i));
1053    EXPECT_FALSE(sv->isLocked(1985));
1054}
1055
1056// Check that pauseResumeVisit calls with the correct Hash bucket.
1057TEST_F(HashTableTest, PauseResumeHashBucket) {
1058    // Two buckets, one lock.
1059    HashTable ht(global_stats, makeFactory(true), 2, 1);
1060
1061    // Store keys to both hash buckets - need keys which hash to bucket 0 and 1.
1062    StoredDocKey key0("c", CollectionID::Default);
1063    ASSERT_EQ(0, ht.getLockedBucket(key0).getBucketNum());
1064    store(ht, key0);
1065
1066    StoredDocKey key1("b", CollectionID::Default);
1067    ASSERT_EQ(1, ht.getLockedBucket(key1).getBucketNum());
1068    store(ht, key1);
1069
1070    class MockHTVisitor : public HashTableVisitor {
1071    public:
1072        MOCK_METHOD2(visit,
1073                     bool(const HashTable::HashBucketLock& lh, StoredValue& v));
1074    } mockVisitor;
1075
1076    // Visit the HashTable; should find two keys, one in each bucket and the
1077    // lockHolder should have the correct hashbucket.
1078    using namespace ::testing;
1079    EXPECT_CALL(mockVisitor,
1080                visit(Property(&HashTable::HashBucketLock::getBucketNum, 0),
1081                      Property(&StoredValue::getKey, Eq(key0))))
1082            .Times(1)
1083            .WillOnce(Return(true));
1084    EXPECT_CALL(mockVisitor,
1085                visit(Property(&HashTable::HashBucketLock::getBucketNum, 1),
1086                      Property(&StoredValue::getKey, Eq(key1))))
1087            .Times(1)
1088            .WillOnce(Return(true));
1089
1090    HashTable::Position start;
1091    ht.pauseResumeVisit(mockVisitor, start);
1092}
1093
1094// Test the itemFreqDecayerVisitor by adding 256 documents to the hash table.
1095// Then set the frequency count of each document in the range 0 to 255.  We
1096// then visit each document and decay it by 50%.  The test checks that the
1097// frequency count of each document has been decayed by 50%.
1098TEST_F(HashTableTest, ItemFreqDecayerVisitorTest) {
1099    HashTable ht(global_stats, makeFactory(true), 128, 1);
1100    auto keys = generateKeys(256);
1101    // Add 256 documents to the hash table
1102    storeMany(ht, keys);
1103    StoredValue* v;
1104
1105    // Set the frequency count of each document in the range 0 to 255.
1106    for (int ii = 0; ii < 256; ii++) {
1107        auto key = makeStoredDocKey(std::to_string(ii));
1108        v = ht.findForWrite(key).storedValue;
1109        v->setFreqCounterValue(ii);
1110       }
1111
1112       ItemFreqDecayerVisitor itemFreqDecayerVisitor(
1113               Configuration().getItemFreqDecayerPercent());
1114       // Decay the frequency count of each document by the configuration
1115       // default of 50%
1116       for (int ii = 0; ii < 256; ii++) {
1117           auto key = makeStoredDocKey(std::to_string(ii));
1118           auto item = ht.findForWrite(key);
1119           itemFreqDecayerVisitor.visit(item.lock, *item.storedValue);
1120       }
1121
1122       // Confirm we visited all the documents
1123       EXPECT_EQ(256, itemFreqDecayerVisitor.getVisitedCount());
1124
1125       // Check the frequency of the docs have been decayed by 50%.
1126       for (int ii = 0; ii < 256; ii++) {
1127           auto key = makeStoredDocKey(std::to_string(ii));
1128           v = ht.findForWrite(key).storedValue;
1129           uint16_t expectVal = ii * 0.5;
1130           EXPECT_EQ(expectVal, v->getFreqCounterValue());
1131       }
1132}
1133
1134// Test the reallocateStoredValue method.
1135// Check it can reallocate and also ignores bogus input
1136TEST_F(HashTableTest, reallocateStoredValue) {
1137    // 3 hash-tables, 2 will be filled, the other left empty
1138    HashTable ht1(global_stats, makeFactory(true), 1, 1);
1139    HashTable ht2(global_stats, makeFactory(true), 2, 2);
1140    HashTable ht3(global_stats, makeFactory(true), 2, 2);
1141
1142    // Fill 1 and 2
1143    auto keys = generateKeys(10);
1144    storeMany(ht1, keys);
1145    storeMany(ht2, keys);
1146
1147    // Test we can reallocate every key
1148    for (int index = 0; index < 10; index++) {
1149        StoredValue* v =
1150                ht1.findForWrite(makeStoredDocKey(std::to_string(index)),
1151                                 WantsDeleted::No)
1152                        .storedValue;
1153        ASSERT_NE(nullptr, v);
1154        EXPECT_TRUE(ht1.reallocateStoredValue(std::forward<StoredValue>(*v)));
1155        EXPECT_EQ(10, ht1.getNumItems());
1156        EXPECT_NE(v,
1157                  ht1.findForWrite(makeStoredDocKey(std::to_string(index)),
1158                                   WantsDeleted::No)
1159                          .storedValue);
1160    }
1161    // Next request ht2 reallocate an sv stored in ht1, should return false
1162    StoredValue* v2 = ht1.findForWrite(makeStoredDocKey(std::to_string(3)),
1163                                       WantsDeleted::No)
1164                              .storedValue;
1165    EXPECT_FALSE(ht2.reallocateStoredValue(std::forward<StoredValue>(*v2)));
1166
1167    // Check the empty hash-table returns false as well
1168    EXPECT_FALSE(ht3.reallocateStoredValue(std::forward<StoredValue>(*v2)));
1169}
1170
1171// MB-33944: Test that calling HashTable::insertFromWarmup() doesn't fail
1172// of the given key is already resident (for example if a BG load already
1173// loaded it).
1174TEST_F(HashTableTest, InsertFromWarmupAlreadyResident) {
1175    // Setup - store a key into HashTable.
1176    HashTable ht(global_stats, makeFactory(), 5, 1);
1177    auto key = makeStoredDocKey("key");
1178    auto item = store(ht, key);
1179    {
1180        // Sanity check - key should be resident.
1181        auto res = ht.findForRead(key);
1182        ASSERT_TRUE(res.storedValue);
1183        ASSERT_TRUE(res.storedValue->isResident());
1184    }
1185
1186    // Test - insertFromWarmup should succesfully skip (re)adding this item.
1187    EXPECT_EQ(MutationStatus::NotFound,
1188              ht.insertFromWarmup(item,
1189                                  /*eject*/ false,
1190                                  /*keyMetaOnly*/ false,
1191                                  EvictionPolicy::Full));
1192}
1193