Merge remote-tracking branch 'couchbase/3.0.x' into sherlock
[ep-engine.git] / tests / module_tests / hash_table_test.cc
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 <ep.h>
21 #include <item.h>
22 #include <signal.h>
23 #include <stats.h>
24
25 #include <algorithm>
26 #include <limits>
27
28 #include "threadtests.h"
29
30 time_t time_offset;
31
32 extern "C" {
33     static rel_time_t basic_current_time(void) {
34         return 0;
35     }
36
37     rel_time_t (*ep_current_time)() = basic_current_time;
38
39     time_t ep_real_time() {
40         return time(NULL) + time_offset;
41     }
42 }
43
44 EPStats global_stats;
45
46 class Counter : public HashTableVisitor {
47 public:
48
49     size_t count;
50     size_t deleted;
51
52     Counter(bool v) : count(), deleted(), verify(v) {}
53
54     void visit(StoredValue *v) {
55         if (v->isDeleted()) {
56             ++deleted;
57         } else {
58             ++count;
59             if (verify) {
60                 std::string key = v->getKey();
61                 value_t val = v->getValue();
62                 cb_assert(key.compare(val->to_s()) == 0);
63             }
64         }
65     }
66 private:
67     bool verify;
68 };
69
70 static int count(HashTable &h, bool verify=true) {
71     Counter c(verify);
72     h.visit(c);
73     cb_assert(c.count + c.deleted == h.getNumItems());
74     return c.count;
75 }
76
77 static void store(HashTable &h, std::string &k) {
78     Item i(k.data(), k.length(), 0, 0, k.c_str(), k.length());
79     cb_assert(h.set(i) == WAS_CLEAN);
80 }
81
82 static void storeMany(HashTable &h, std::vector<std::string> &keys) {
83     std::vector<std::string>::iterator it;
84     for (it = keys.begin(); it != keys.end(); ++it) {
85         std::string key = *it;
86         store(h, key);
87     }
88 }
89
90 static void addMany(HashTable &h, std::vector<std::string> &keys,
91                     add_type_t expect) {
92     std::vector<std::string>::iterator it;
93     item_eviction_policy_t policy = VALUE_ONLY;
94     for (it = keys.begin(); it != keys.end(); ++it) {
95         std::string k = *it;
96         Item i(k.data(), k.length(), 0, 0, k.c_str(), k.length());
97         add_type_t v = h.add(i, policy);
98         cb_assert(expect == v);
99     }
100 }
101
102 template <typename T>
103 static const char *toString(add_type_t a) {
104     switch(a) {
105     case ADD_SUCCESS: return "add_success";
106     case ADD_NOMEM: return "add_nomem";
107     case ADD_EXISTS: return "add_exists";
108     case ADD_UNDEL: return "add_undel";
109     case ADD_TMP_AND_BG_FETCH: return "add_tmp_and_bg_fetch";
110     case ADD_BG_FETCH: return "add_bg_fetch";
111     }
112     abort();
113     return NULL;
114 }
115
116 template <typename T>
117 void assertEquals(T a, T b) {
118     if (a != b) {
119         std::cerr << "Expected " << toString<T>(a)
120                   << " got " << toString<T>(b) << std::endl;
121         abort();
122     }
123 }
124
125 static void add(HashTable &h, const std::string &k, add_type_t expect,
126                 int expiry=0) {
127     Item i(k.data(), k.length(), 0, expiry, k.c_str(), k.length());
128     item_eviction_policy_t policy = VALUE_ONLY;
129     add_type_t v = h.add(i, policy);
130     assertEquals(expect, v);
131 }
132
133 static std::vector<std::string> generateKeys(int num, int start=0) {
134     std::vector<std::string> rv;
135
136     for (int i = start; i < num; i++) {
137         char buf[64];
138         snprintf(buf, sizeof(buf), "key%d", i);
139         std::string key(buf);
140         rv.push_back(key);
141     }
142
143     return rv;
144 }
145
146 // ----------------------------------------------------------------------
147 // Actual tests below.
148 // ----------------------------------------------------------------------
149
150 static void testHashSize() {
151     HashTable h(global_stats, /*size*/0, /*locks*/1);
152     cb_assert(count(h) == 0);
153
154     std::string k = "testkey";
155     store(h, k);
156
157     cb_assert(count(h) == 1);
158 }
159
160 static void testHashSizeTwo() {
161     HashTable h(global_stats, /*size*/0, /*locks*/1);
162     cb_assert(count(h) == 0);
163
164     std::vector<std::string> keys = generateKeys(5);
165     storeMany(h, keys);
166     cb_assert(count(h) == 5);
167
168     h.clear();
169     cb_assert(count(h) == 0);
170 }
171
172 static void testReverseDeletions() {
173     size_t initialSize = global_stats.currentSize.load();
174     HashTable h(global_stats, 5, 1);
175     cb_assert(count(h) == 0);
176     const int nkeys = 10000;
177
178     std::vector<std::string> keys = generateKeys(nkeys);
179     storeMany(h, keys);
180     cb_assert(count(h) == nkeys);
181
182     std::reverse(keys.begin(), keys.end());
183
184     std::vector<std::string>::iterator it;
185     for (it = keys.begin(); it != keys.end(); ++it) {
186         std::string key = *it;
187         h.del(key);
188     }
189
190     cb_assert(count(h) == 0);
191     cb_assert(global_stats.currentSize.load() == initialSize);
192 }
193
194 static void testForwardDeletions() {
195     size_t initialSize = global_stats.currentSize.load();
196     HashTable h(global_stats, 5, 1);
197     cb_assert(h.getSize() == 5);
198     cb_assert(h.getNumLocks() == 1);
199     cb_assert(count(h) == 0);
200     const int nkeys = 10000;
201
202     std::vector<std::string> keys = generateKeys(nkeys);
203     storeMany(h, keys);
204     cb_assert(count(h) == nkeys);
205
206     std::vector<std::string>::iterator it;
207     for (it = keys.begin(); it != keys.end(); ++it) {
208         std::string key = *it;
209         h.del(key);
210     }
211
212     cb_assert(count(h) == 0);
213     cb_assert(global_stats.currentSize.load() == initialSize);
214 }
215
216 static void verifyFound(HashTable &h, const std::vector<std::string> &keys) {
217     std::string missingKey = "aMissingKey";
218     cb_assert(h.find(missingKey) == NULL);
219
220     std::vector<std::string>::const_iterator it;
221     for (it = keys.begin(); it != keys.end(); ++it) {
222         std::string key = *it;
223         cb_assert(h.find(key));
224     }
225 }
226
227 static void testFind(HashTable &h) {
228     const int nkeys = 5000;
229
230     std::vector<std::string> keys = generateKeys(nkeys);
231     storeMany(h, keys);
232
233     verifyFound(h, keys);
234 }
235
236 static void testFind() {
237     HashTable h(global_stats, 5, 1);
238     testFind(h);
239 }
240
241 static void testAddExpiry() {
242     HashTable h(global_stats, 5, 1);
243     std::string k("aKey");
244
245     add(h, k, ADD_SUCCESS, ep_real_time() + 5);
246     add(h, k, ADD_EXISTS, ep_real_time() + 5);
247
248     StoredValue *v = h.find(k);
249     cb_assert(v);
250     cb_assert(!v->isExpired(ep_real_time()));
251     cb_assert(v->isExpired(ep_real_time() + 6));
252
253     time_offset += 6;
254     cb_assert(v->isExpired(ep_real_time()));
255
256     add(h, k, ADD_UNDEL, ep_real_time() + 5);
257     cb_assert(v);
258     cb_assert(!v->isExpired(ep_real_time()));
259     cb_assert(v->isExpired(ep_real_time() + 6));
260 }
261
262 static void testResize() {
263     HashTable h(global_stats, 5, 3);
264
265     std::vector<std::string> keys = generateKeys(5000);
266     storeMany(h, keys);
267
268     verifyFound(h, keys);
269
270     h.resize(6143);
271     cb_assert(h.getSize() == 6143);
272
273     verifyFound(h, keys);
274
275     h.resize(769);
276     cb_assert(h.getSize() == 769);
277
278     verifyFound(h, keys);
279
280     h.resize(static_cast<size_t>(std::numeric_limits<int>::max()) + 17);
281     cb_assert(h.getSize() == 769);
282
283     verifyFound(h, keys);
284 }
285
286 class AccessGenerator : public Generator<bool> {
287 public:
288
289     AccessGenerator(const std::vector<std::string> &k,
290                     HashTable &h) : keys(k), ht(h), size(10000) {
291         std::random_shuffle(keys.begin(), keys.end());
292     }
293
294     bool operator()() {
295         std::vector<std::string>::iterator it;
296         for (it = keys.begin(); it != keys.end(); ++it) {
297             if (rand() % 111 == 0) {
298                 resize();
299             }
300             ht.del(*it);
301         }
302         return true;
303     }
304
305 private:
306
307     void resize() {
308         ht.resize(size);
309         size = size == 10000 ? 30000 : 10000;
310     }
311
312     std::vector<std::string>  keys;
313     HashTable                &ht;
314     AtomicValue<size_t>       size;
315 };
316
317 static void testConcurrentAccessResize() {
318     HashTable h(global_stats, 5, 3);
319
320     std::vector<std::string> keys = generateKeys(20000);
321     h.resize(keys.size());
322     storeMany(h, keys);
323
324     verifyFound(h, keys);
325
326     srand(918475);
327     AccessGenerator gen(keys, h);
328     getCompletedThreads(16, &gen);
329 }
330
331 static void testAutoResize() {
332     HashTable h(global_stats, 5, 3);
333
334     std::vector<std::string> keys = generateKeys(5000);
335     storeMany(h, keys);
336
337     verifyFound(h, keys);
338
339     h.resize();
340     cb_assert(h.getSize() == 6143);
341     verifyFound(h, keys);
342 }
343
344 static void testAdd() {
345     HashTable h(global_stats, 5, 1);
346     const int nkeys = 5000;
347
348     std::vector<std::string> keys = generateKeys(nkeys);
349     addMany(h, keys, ADD_SUCCESS);
350
351     std::string missingKey = "aMissingKey";
352     cb_assert(h.find(missingKey) == NULL);
353
354     std::vector<std::string>::iterator it;
355     for (it = keys.begin(); it != keys.end(); ++it) {
356         std::string key = *it;
357         cb_assert(h.find(key));
358     }
359
360     addMany(h, keys, ADD_EXISTS);
361     for (it = keys.begin(); it != keys.end(); ++it) {
362         std::string key = *it;
363         cb_assert(h.find(key));
364     }
365
366     // Verify we can readd after a soft deletion.
367     cb_assert(h.softDelete(keys[0], 0) == WAS_DIRTY);
368     cb_assert(h.softDelete(keys[0], 0) == NOT_FOUND);
369     cb_assert(!h.find(keys[0]));
370     cb_assert(count(h) == nkeys - 1);
371
372     Item i(keys[0].data(), keys[0].length(), 0, 0, "newtest", 7);
373     item_eviction_policy_t policy = VALUE_ONLY;
374     cb_assert(h.add(i, policy) == ADD_UNDEL);
375     cb_assert(count(h, false) == nkeys);
376 }
377
378 static void testDepthCounting() {
379     HashTable h(global_stats, 5, 1);
380     const int nkeys = 5000;
381
382     std::vector<std::string> keys = generateKeys(nkeys);
383     storeMany(h, keys);
384
385     HashTableDepthStatVisitor depthCounter;
386     h.visitDepth(depthCounter);
387     // std::cout << "Max depth:  " << depthCounter.maxDepth << std::endl;
388     cb_assert(depthCounter.max > 1000);
389 }
390
391 static void testPoisonKey() {
392     std::string k("A\\NROBs_oc)$zqJ1C.9?XU}Vn^(LW\"`+K/4lykF[ue0{ram;fvId6h=p&Zb3T~SQ]82'ixDP");
393
394     HashTable h(global_stats, 5, 1);
395
396     store(h, k);
397     cb_assert(count(h) == 1);
398 }
399
400 static void testSizeStats() {
401     global_stats.reset();
402     HashTable ht(global_stats, 5, 1);
403     cb_assert(ht.memSize.load() == 0);
404     cb_assert(ht.cacheSize.load() == 0);
405     size_t initialSize = global_stats.currentSize.load();
406
407     const std::string k("somekey");
408     const size_t itemSize(16 * 1024);
409     char *someval(static_cast<char*>(calloc(1, itemSize)));
410     cb_assert(someval);
411
412     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
413
414     cb_assert(ht.set(i) == WAS_CLEAN);
415
416     ht.del(k);
417
418     cb_assert(ht.memSize.load() == 0);
419     cb_assert(ht.cacheSize.load() == 0);
420     cb_assert(initialSize == global_stats.currentSize.load());
421
422     free(someval);
423 }
424
425 static void testSizeStatsFlush() {
426     global_stats.reset();
427     HashTable ht(global_stats, 5, 1);
428     cb_assert(ht.memSize.load() == 0);
429     cb_assert(ht.cacheSize.load() == 0);
430     size_t initialSize = global_stats.currentSize.load();
431
432     const std::string k("somekey");
433     const size_t itemSize(16 * 1024);
434     char *someval(static_cast<char*>(calloc(1, itemSize)));
435     cb_assert(someval);
436
437     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
438
439     cb_assert(ht.set(i) == WAS_CLEAN);
440
441     ht.clear();
442
443     cb_assert(ht.memSize.load() == 0);
444     cb_assert(ht.cacheSize.load() == 0);
445     cb_assert(initialSize == global_stats.currentSize.load());
446
447     free(someval);
448 }
449
450 static void testSizeStatsSoftDel() {
451     global_stats.reset();
452     HashTable ht(global_stats, 5, 1);
453     cb_assert(ht.memSize.load() == 0);
454     cb_assert(ht.cacheSize.load() == 0);
455     size_t initialSize = global_stats.currentSize.load();
456
457     const std::string k("somekey");
458     const size_t itemSize(16 * 1024);
459     char *someval(static_cast<char*>(calloc(1, itemSize)));
460     cb_assert(someval);
461
462     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
463
464     cb_assert(ht.set(i) == WAS_CLEAN);
465
466     cb_assert(ht.softDelete(k, 0) == WAS_DIRTY);
467     ht.del(k);
468
469     cb_assert(ht.memSize.load() == 0);
470     cb_assert(ht.cacheSize.load() == 0);
471     cb_assert(initialSize == global_stats.currentSize.load());
472
473     free(someval);
474 }
475
476 static void testSizeStatsSoftDelFlush() {
477     global_stats.reset();
478     HashTable ht(global_stats, 5, 1);
479     cb_assert(ht.memSize.load() == 0);
480     cb_assert(ht.cacheSize.load() == 0);
481     size_t initialSize = global_stats.currentSize.load();
482
483     const std::string k("somekey");
484     const size_t itemSize(16 * 1024);
485     char *someval(static_cast<char*>(calloc(1, itemSize)));
486     cb_assert(someval);
487
488     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
489
490     cb_assert(ht.set(i) == WAS_CLEAN);
491
492     cb_assert(ht.softDelete(k, 0) == WAS_DIRTY);
493     ht.clear();
494
495     cb_assert(ht.memSize.load() == 0);
496     cb_assert(ht.cacheSize.load() == 0);
497     cb_assert(initialSize == global_stats.currentSize.load());
498
499     free(someval);
500 }
501
502 static void testSizeStatsEject() {
503     global_stats.reset();
504     HashTable ht(global_stats, 5, 1);
505     cb_assert(ht.memSize.load() == 0);
506     cb_assert(ht.cacheSize.load() == 0);
507     size_t initialSize = global_stats.currentSize.load();
508
509     const std::string k("somekey");
510     std::string kstring(k);
511     const size_t itemSize(16 * 1024);
512     char *someval(static_cast<char*>(calloc(1, itemSize)));
513     cb_assert(someval);
514
515     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
516
517     cb_assert(ht.set(i) == WAS_CLEAN);
518
519     item_eviction_policy_t policy = VALUE_ONLY;
520     StoredValue *v(ht.find(kstring));
521     cb_assert(v);
522     v->markClean();
523     cb_assert(ht.unlocked_ejectItem(v, policy));
524
525     ht.del(k);
526
527     cb_assert(ht.memSize.load() == 0);
528     cb_assert(ht.cacheSize.load() == 0);
529     cb_assert(initialSize == global_stats.currentSize.load());
530
531     free(someval);
532 }
533
534 static void testSizeStatsEjectFlush() {
535     global_stats.reset();
536     HashTable ht(global_stats, 5, 1);
537     cb_assert(ht.memSize.load() == 0);
538     cb_assert(ht.cacheSize.load() == 0);
539     size_t initialSize = global_stats.currentSize.load();
540
541     const std::string k("somekey");
542     std::string kstring(k);
543     const size_t itemSize(16 * 1024);
544     char *someval(static_cast<char*>(calloc(1, itemSize)));
545     cb_assert(someval);
546
547     Item i(k.data(), k.length(), 0, 0, someval, itemSize);
548
549     cb_assert(ht.set(i) == WAS_CLEAN);
550
551     item_eviction_policy_t policy = VALUE_ONLY;
552     StoredValue *v(ht.find(kstring));
553     cb_assert(v);
554     v->markClean();
555     cb_assert(ht.unlocked_ejectItem(v, policy));
556
557     ht.clear();
558
559     cb_assert(ht.memSize.load() == 0);
560     cb_assert(ht.cacheSize.load() == 0);
561     cb_assert(initialSize == global_stats.currentSize.load());
562
563     free(someval);
564 }
565
566 static void testItemAge() {
567     // Setup
568     HashTable ht(global_stats, 5, 1);
569     std::string key("key");
570     Item item(key.data(), key.length(), 0, 0, "value", strlen("value"));
571     cb_assert(ht.set(item) == WAS_CLEAN);
572
573     // Test
574     StoredValue* v(ht.find(key));
575     cb_assert(v->getValue()->getAge() == 0);
576     v->getValue()->incrementAge();
577     cb_assert(v->getValue()->getAge() == 1);
578
579     // Check saturation of age.
580     for (int ii = 0; ii < 300; ii++) {
581         v->getValue()->incrementAge();
582     }
583     cb_assert(v->getValue()->getAge() == 0xff);
584
585     // Check reset of age after reallocation.
586     v->reallocate();
587     cb_assert(v->getValue()->getAge() == 0);
588
589     // Check changing age when new value is used.
590     Item item2(key.data(), key.length(), 0, 0, "value2", strlen("value2"));
591     item2.getValue()->incrementAge();
592     v->setValue(item2, ht, false);
593     cb_assert(v->getValue()->getAge() == 1);
594 }
595
596 int main() {
597     putenv(strdup("ALLOW_NO_STATS_UPDATE=yeah"));
598     global_stats.setMaxDataSize(64*1024*1024);
599     HashTable::setDefaultNumBuckets(3);
600     testHashSize();
601     testHashSizeTwo();
602     testReverseDeletions();
603     testForwardDeletions();
604     testFind();
605     testAdd();
606     testAddExpiry();
607     testDepthCounting();
608     testPoisonKey();
609     testResize();
610     testConcurrentAccessResize();
611     testAutoResize();
612     testSizeStats();
613     testSizeStatsFlush();
614     testSizeStatsSoftDel();
615     testSizeStatsSoftDelFlush();
616     testSizeStatsEject();
617     testSizeStatsEjectFlush();
618     testItemAge();
619     exit(0);
620 }