Remove incorrect DCHECKS
[folly.git] / folly / concurrency / test / ConcurrentHashMapTest.cpp
1 /*
2  * Copyright 2017-present Facebook, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 #include <atomic>
17 #include <memory>
18 #include <thread>
19
20 #include <folly/concurrency/ConcurrentHashMap.h>
21 #include <folly/hash/Hash.h>
22 #include <folly/portability/GTest.h>
23 #include <folly/test/DeterministicSchedule.h>
24
25 using namespace folly::test;
26 using namespace folly;
27 using namespace std;
28
29 DEFINE_int64(seed, 0, "Seed for random number generators");
30
31 TEST(ConcurrentHashMap, MapTest) {
32   ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
33   foomap.max_load_factor(1.05);
34   EXPECT_TRUE(foomap.empty());
35   EXPECT_EQ(foomap.find(1), foomap.cend());
36   auto r = foomap.insert(1, 0);
37   EXPECT_TRUE(r.second);
38   auto r2 = foomap.insert(1, 0);
39   EXPECT_EQ(r.first->second, 0);
40   EXPECT_EQ(r.first->first, 1);
41   EXPECT_EQ(r2.first->second, 0);
42   EXPECT_EQ(r2.first->first, 1);
43   EXPECT_EQ(r.first, r2.first);
44   EXPECT_TRUE(r.second);
45   EXPECT_FALSE(r2.second);
46   EXPECT_FALSE(foomap.empty());
47   EXPECT_TRUE(foomap.insert(std::make_pair(2, 0)).second);
48   EXPECT_TRUE(foomap.insert_or_assign(2, 0).second);
49   EXPECT_TRUE(foomap.assign_if_equal(2, 0, 3));
50   EXPECT_TRUE(foomap.insert(3, 0).second);
51   EXPECT_NE(foomap.find(1), foomap.cend());
52   EXPECT_NE(foomap.find(2), foomap.cend());
53   EXPECT_EQ(foomap.find(2)->second, 3);
54   EXPECT_EQ(foomap[2], 3);
55   EXPECT_EQ(foomap[20], 0);
56   EXPECT_EQ(foomap.at(20), 0);
57   EXPECT_FALSE(foomap.insert(1, 0).second);
58   auto l = foomap.find(1);
59   foomap.erase(l);
60   EXPECT_FALSE(foomap.erase(1));
61   EXPECT_EQ(foomap.find(1), foomap.cend());
62   auto res = foomap.find(2);
63   EXPECT_NE(res, foomap.cend());
64   EXPECT_EQ(3, res->second);
65   EXPECT_FALSE(foomap.empty());
66   foomap.clear();
67   EXPECT_TRUE(foomap.empty());
68 }
69
70 TEST(ConcurrentHashMap, MaxSizeTest) {
71   ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
72   bool insert_failed = false;
73   for (int i = 0; i < 32; i++) {
74     auto res = foomap.insert(0, 0);
75     if (!res.second) {
76       insert_failed = true;
77     }
78   }
79   EXPECT_TRUE(insert_failed);
80 }
81
82 TEST(ConcurrentHashMap, MoveTest) {
83   ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
84   auto other = std::move(foomap);
85   auto other2 = std::move(other);
86   other = std::move(other2);
87 }
88
89 struct foo {
90   static int moved;
91   static int copied;
92   foo(foo&& o) noexcept {
93     (void*)&o;
94     moved++;
95   }
96   foo& operator=(foo&& o) {
97     (void*)&o;
98     moved++;
99     return *this;
100   }
101   foo& operator=(const foo& o) {
102     (void*)&o;
103     copied++;
104     return *this;
105   }
106   foo(const foo& o) {
107     (void*)&o;
108     copied++;
109   }
110   foo() {}
111 };
112 int foo::moved{0};
113 int foo::copied{0};
114
115 TEST(ConcurrentHashMap, EmplaceTest) {
116   ConcurrentHashMap<uint64_t, foo> foomap(200);
117   foomap.insert(1, foo());
118   EXPECT_EQ(foo::moved, 0);
119   EXPECT_EQ(foo::copied, 1);
120   foo::copied = 0;
121   // The difference between emplace and try_emplace:
122   // If insertion fails, try_emplace does not move its argument
123   foomap.try_emplace(1, foo());
124   EXPECT_EQ(foo::moved, 0);
125   EXPECT_EQ(foo::copied, 0);
126   foomap.emplace(1, foo());
127   EXPECT_EQ(foo::moved, 1);
128   EXPECT_EQ(foo::copied, 0);
129 }
130
131 TEST(ConcurrentHashMap, MapResizeTest) {
132   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
133   EXPECT_EQ(foomap.find(1), foomap.cend());
134   EXPECT_TRUE(foomap.insert(1, 0).second);
135   EXPECT_TRUE(foomap.insert(2, 0).second);
136   EXPECT_TRUE(foomap.insert(3, 0).second);
137   EXPECT_TRUE(foomap.insert(4, 0).second);
138   foomap.reserve(512);
139   EXPECT_NE(foomap.find(1), foomap.cend());
140   EXPECT_NE(foomap.find(2), foomap.cend());
141   EXPECT_FALSE(foomap.insert(1, 0).second);
142   EXPECT_TRUE(foomap.erase(1));
143   EXPECT_EQ(foomap.find(1), foomap.cend());
144   auto res = foomap.find(2);
145   EXPECT_NE(res, foomap.cend());
146   if (res != foomap.cend()) {
147     EXPECT_EQ(0, res->second);
148   }
149 }
150
151 // Ensure we can insert objects without copy constructors.
152 TEST(ConcurrentHashMap, MapNoCopiesTest) {
153   struct Uncopyable {
154     Uncopyable(int i) {
155       (void*)&i;
156     }
157     Uncopyable(const Uncopyable& that) = delete;
158   };
159   ConcurrentHashMap<uint64_t, Uncopyable> foomap(2);
160   EXPECT_TRUE(foomap.try_emplace(1, 1).second);
161   EXPECT_TRUE(foomap.try_emplace(2, 2).second);
162   auto res = foomap.find(2);
163   EXPECT_NE(res, foomap.cend());
164
165   EXPECT_TRUE(foomap.try_emplace(3, 3).second);
166
167   auto res2 = foomap.find(2);
168   EXPECT_NE(res2, foomap.cend());
169   EXPECT_EQ(&(res->second), &(res2->second));
170 }
171
172 TEST(ConcurrentHashMap, MapUpdateTest) {
173   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
174   EXPECT_TRUE(foomap.insert(1, 10).second);
175   EXPECT_TRUE(bool(foomap.assign(1, 11)));
176   auto res = foomap.find(1);
177   EXPECT_NE(res, foomap.cend());
178   EXPECT_EQ(11, res->second);
179 }
180
181 TEST(ConcurrentHashMap, MapIterateTest2) {
182   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
183   auto begin = foomap.cbegin();
184   auto end = foomap.cend();
185   EXPECT_EQ(begin, end);
186 }
187
188 TEST(ConcurrentHashMap, MapIterateTest) {
189   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
190   EXPECT_EQ(foomap.cbegin(), foomap.cend());
191   EXPECT_TRUE(foomap.insert(1, 1).second);
192   EXPECT_TRUE(foomap.insert(2, 2).second);
193   auto iter = foomap.cbegin();
194   EXPECT_NE(iter, foomap.cend());
195   EXPECT_EQ(iter->first, 1);
196   EXPECT_EQ(iter->second, 1);
197   iter++;
198   EXPECT_NE(iter, foomap.cend());
199   EXPECT_EQ(iter->first, 2);
200   EXPECT_EQ(iter->second, 2);
201   iter++;
202   EXPECT_EQ(iter, foomap.cend());
203
204   int count = 0;
205   for (auto it = foomap.cbegin(); it != foomap.cend(); it++) {
206     count++;
207   }
208   EXPECT_EQ(count, 2);
209 }
210
211 TEST(ConcurrentHashMap, EraseTest) {
212   ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
213   foomap.insert(1, 0);
214   auto f1 = foomap.find(1);
215   EXPECT_EQ(1, foomap.erase(1));
216   foomap.erase(f1);
217 }
218
219 // TODO: hazptrs must support DeterministicSchedule
220
221 #define Atom std::atomic // DeterministicAtomic
222 #define Mutex std::mutex // DeterministicMutex
223 #define lib std // DeterministicSchedule
224 #define join t.join() // DeterministicSchedule::join(t)
225 // #define Atom DeterministicAtomic
226 // #define Mutex DeterministicMutex
227 // #define lib DeterministicSchedule
228 // #define join DeterministicSchedule::join(t)
229
230 TEST(ConcurrentHashMap, UpdateStressTest) {
231   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
232
233   // size must match iters for this test.
234   unsigned size = 128 * 128;
235   unsigned iters = size;
236   ConcurrentHashMap<
237       unsigned long,
238       unsigned long,
239       std::hash<unsigned long>,
240       std::equal_to<unsigned long>,
241       std::allocator<uint8_t>,
242       8,
243       Atom,
244       Mutex>
245       m(2);
246
247   for (uint i = 0; i < size; i++) {
248     m.insert(i, i);
249   }
250   std::vector<std::thread> threads;
251   unsigned int num_threads = 32;
252   for (uint t = 0; t < num_threads; t++) {
253     threads.push_back(lib::thread([&, t]() {
254       int offset = (iters * t / num_threads);
255       for (uint i = 0; i < iters / num_threads; i++) {
256         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
257         k = k % (iters / num_threads) + offset;
258         unsigned long val = 3;
259         auto res = m.find(k);
260         EXPECT_NE(res, m.cend());
261         EXPECT_EQ(k, res->second);
262         auto r = m.assign(k, res->second);
263         EXPECT_TRUE(r);
264         res = m.find(k);
265         EXPECT_NE(res, m.cend());
266         EXPECT_EQ(k, res->second);
267         // Another random insertion to force table resizes
268         val = size + i + offset;
269         EXPECT_TRUE(m.insert(val, val).second);
270       }
271     }));
272   }
273   for (auto& t : threads) {
274     join;
275   }
276 }
277
278 TEST(ConcurrentHashMap, EraseStressTest) {
279   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
280
281   unsigned size = 2;
282   unsigned iters = size * 128 * 2;
283   ConcurrentHashMap<
284       unsigned long,
285       unsigned long,
286       std::hash<unsigned long>,
287       std::equal_to<unsigned long>,
288       std::allocator<uint8_t>,
289       8,
290       Atom,
291       Mutex>
292       m(2);
293
294   for (uint i = 0; i < size; i++) {
295     unsigned long k = folly::hash::jenkins_rev_mix32(i);
296     m.insert(k, k);
297   }
298   std::vector<std::thread> threads;
299   unsigned int num_threads = 32;
300   for (uint t = 0; t < num_threads; t++) {
301     threads.push_back(lib::thread([&, t]() {
302       int offset = (iters * t / num_threads);
303       for (uint i = 0; i < iters / num_threads; i++) {
304         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
305         auto res = m.insert(k, k).second;
306         if (res) {
307           res = m.erase(k);
308           if (!res) {
309             printf("Faulre to erase thread %i val %li\n", t, k);
310             exit(0);
311           }
312           EXPECT_TRUE(res);
313         }
314         res = m.insert(k, k).second;
315         if (res) {
316           res = bool(m.assign(k, k));
317           if (!res) {
318             printf("Thread %i update fail %li res%i\n", t, k, res);
319             exit(0);
320           }
321           EXPECT_TRUE(res);
322           auto res = m.find(k);
323           if (res == m.cend()) {
324             printf("Thread %i lookup fail %li\n", t, k);
325             exit(0);
326           }
327           EXPECT_EQ(k, res->second);
328         }
329       }
330     }));
331   }
332   for (auto& t : threads) {
333     join;
334   }
335 }
336
337 TEST(ConcurrentHashMap, IterateStressTest) {
338   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
339
340   unsigned size = 2;
341   unsigned iters = size * 128 * 2;
342   ConcurrentHashMap<
343       unsigned long,
344       unsigned long,
345       std::hash<unsigned long>,
346       std::equal_to<unsigned long>,
347       std::allocator<uint8_t>,
348       8,
349       Atom,
350       Mutex>
351       m(2);
352
353   for (uint i = 0; i < size; i++) {
354     unsigned long k = folly::hash::jenkins_rev_mix32(i);
355     m.insert(k, k);
356   }
357   for (uint i = 0; i < 10; i++) {
358     m.insert(i, i);
359   }
360   std::vector<std::thread> threads;
361   unsigned int num_threads = 32;
362   for (uint t = 0; t < num_threads; t++) {
363     threads.push_back(lib::thread([&, t]() {
364       int offset = (iters * t / num_threads);
365       for (uint i = 0; i < iters / num_threads; i++) {
366         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
367         auto res = m.insert(k, k).second;
368         if (res) {
369           res = m.erase(k);
370           if (!res) {
371             printf("Faulre to erase thread %i val %li\n", t, k);
372             exit(0);
373           }
374           EXPECT_TRUE(res);
375         }
376         int count = 0;
377         for (auto it = m.cbegin(); it != m.cend(); it++) {
378           printf("Item is %li\n", it->first);
379           if (it->first < 10) {
380             count++;
381           }
382         }
383         EXPECT_EQ(count, 10);
384       }
385     }));
386   }
387   for (auto& t : threads) {
388     join;
389   }
390 }
391
392 TEST(ConcurrentHashMap, insertStressTest) {
393   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
394
395   unsigned size = 2;
396   unsigned iters = size * 64 * 4;
397   ConcurrentHashMap<
398       unsigned long,
399       unsigned long,
400       std::hash<unsigned long>,
401       std::equal_to<unsigned long>,
402       std::allocator<uint8_t>,
403       8,
404       Atom,
405       Mutex>
406       m(2);
407
408   EXPECT_TRUE(m.insert(0, 0).second);
409   EXPECT_FALSE(m.insert(0, 0).second);
410   std::vector<std::thread> threads;
411   unsigned int num_threads = 32;
412   for (uint t = 0; t < num_threads; t++) {
413     threads.push_back(lib::thread([&, t]() {
414       int offset = (iters * t / num_threads);
415       for (uint i = 0; i < iters / num_threads; i++) {
416         auto var = offset + i + 1;
417         EXPECT_TRUE(m.insert(var, var).second);
418         EXPECT_FALSE(m.insert(0, 0).second);
419       }
420     }));
421   }
422   for (auto& t : threads) {
423     join;
424   }
425 }
426
427 TEST(ConcurrentHashMap, assignStressTest) {
428   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
429
430   unsigned size = 2;
431   unsigned iters = size * 64 * 4;
432   struct big_value {
433     uint64_t v1;
434     uint64_t v2;
435     uint64_t v3;
436     uint64_t v4;
437     uint64_t v5;
438     uint64_t v6;
439     uint64_t v7;
440     uint64_t v8;
441     void set(uint64_t v) {
442       v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
443     }
444     void check() const {
445       auto v = v1;
446       EXPECT_EQ(v, v8);
447       EXPECT_EQ(v, v7);
448       EXPECT_EQ(v, v6);
449       EXPECT_EQ(v, v5);
450       EXPECT_EQ(v, v4);
451       EXPECT_EQ(v, v3);
452       EXPECT_EQ(v, v2);
453     }
454   };
455   ConcurrentHashMap<
456       unsigned long,
457       big_value,
458       std::hash<unsigned long>,
459       std::equal_to<unsigned long>,
460       std::allocator<uint8_t>,
461       8,
462       Atom,
463       Mutex>
464       m(2);
465
466   for (uint i = 0; i < iters; i++) {
467     big_value a;
468     a.set(i);
469     m.insert(i, a);
470   }
471
472   std::vector<std::thread> threads;
473   unsigned int num_threads = 32;
474   for (uint t = 0; t < num_threads; t++) {
475     threads.push_back(lib::thread([&]() {
476       for (uint i = 0; i < iters; i++) {
477         auto res = m.find(i);
478         EXPECT_NE(res, m.cend());
479         res->second.check();
480         big_value b;
481         b.set(res->second.v1 + 1);
482         m.assign(i, b);
483       }
484     }));
485   }
486   for (auto& t : threads) {
487     join;
488   }
489 }