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