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