Drop a dead include of FBString.h from MemoryMapping.h
[folly.git] / folly / test / IndexedMemPoolTest.cpp
1 /*
2  * Copyright 2017 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
17 #include <folly/IndexedMemPool.h>
18 #include <folly/test/DeterministicSchedule.h>
19 #include <folly/portability/GTest.h>
20 #include <folly/portability/Unistd.h>
21
22 #include <string>
23 #include <thread>
24 #include <semaphore.h>
25
26 using namespace folly;
27 using namespace folly::test;
28
29 TEST(IndexedMemPool, unique_ptr) {
30   typedef IndexedMemPool<size_t> Pool;
31   Pool pool(100);
32
33   for (size_t i = 0; i < 100000; ++i) {
34     auto ptr = pool.allocElem();
35     EXPECT_TRUE(!!ptr);
36     *ptr = i;
37   }
38
39   std::vector<Pool::UniquePtr> leak;
40   while (true) {
41     auto ptr = pool.allocElem();
42     if (!ptr) {
43       // good, we finally ran out
44       break;
45     }
46     leak.emplace_back(std::move(ptr));
47     EXPECT_LT(leak.size(), 10000u);
48   }
49 }
50
51 TEST(IndexedMemPool, no_starvation) {
52   const int count = 1000;
53   const uint32_t poolSize = 100;
54
55   typedef DeterministicSchedule Sched;
56   Sched sched(Sched::uniform(0));
57
58   typedef IndexedMemPool<int,8,8,DeterministicAtomic> Pool;
59   Pool pool(poolSize);
60
61   for (auto pass = 0; pass < 10; ++pass) {
62     int fd[2];
63     EXPECT_EQ(pipe(fd), 0);
64
65     // makes sure we wait for available nodes, rather than fail allocIndex
66     sem_t allocSem;
67     sem_init(&allocSem, 0, poolSize);
68
69     // this semaphore is only needed for deterministic replay, so that we
70     // always block in an Sched:: operation rather than in a read() syscall
71     sem_t readSem;
72     sem_init(&readSem, 0, 0);
73
74     std::thread produce = Sched::thread([&]() {
75       for (auto i = 0; i < count; ++i) {
76         Sched::wait(&allocSem);
77         uint32_t idx = pool.allocIndex();
78         EXPECT_NE(idx, 0u);
79         EXPECT_LE(idx,
80             poolSize + (pool.NumLocalLists - 1) * pool.LocalListLimit);
81         pool[idx] = i;
82         EXPECT_EQ(write(fd[1], &idx, sizeof(idx)), sizeof(idx));
83         Sched::post(&readSem);
84       }
85     });
86
87     std::thread consume = Sched::thread([&]() {
88       for (auto i = 0; i < count; ++i) {
89         uint32_t idx;
90         Sched::wait(&readSem);
91         EXPECT_EQ(read(fd[0], &idx, sizeof(idx)), sizeof(idx));
92         EXPECT_NE(idx, 0);
93         EXPECT_GE(idx, 1u);
94         EXPECT_LE(idx,
95             poolSize + (Pool::NumLocalLists - 1) * Pool::LocalListLimit);
96         EXPECT_EQ(pool[idx], i);
97         pool.recycleIndex(idx);
98         Sched::post(&allocSem);
99       }
100     });
101
102     Sched::join(produce);
103     Sched::join(consume);
104     close(fd[0]);
105     close(fd[1]);
106   }
107 }
108
109 TEST(IndexedMemPool, st_capacity) {
110   // only one local list => capacity is exact
111   typedef IndexedMemPool<int,1,32> Pool;
112   Pool pool(10);
113
114   EXPECT_EQ(pool.capacity(), 10u);
115   EXPECT_EQ(Pool::maxIndexForCapacity(10), 10u);
116   for (auto i = 0; i < 10; ++i) {
117     EXPECT_NE(pool.allocIndex(), 0u);
118   }
119   EXPECT_EQ(pool.allocIndex(), 0u);
120 }
121
122 TEST(IndexedMemPool, mt_capacity) {
123   typedef IndexedMemPool<int,16,32> Pool;
124   Pool pool(1000);
125
126   std::thread threads[10];
127   for (auto i = 0; i < 10; ++i) {
128     threads[i] = std::thread([&]() {
129       for (auto j = 0; j < 100; ++j) {
130         uint32_t idx = pool.allocIndex();
131         EXPECT_NE(idx, 0u);
132       }
133     });
134   }
135
136   for (auto i = 0; i < 10; ++i) {
137     threads[i].join();
138   }
139
140   for (auto i = 0; i < 16 * 32; ++i) {
141     pool.allocIndex();
142   }
143   EXPECT_EQ(pool.allocIndex(), 0u);
144 }
145
146 TEST(IndexedMemPool, locate_elem) {
147   IndexedMemPool<int> pool(1000);
148
149   for (auto i = 0; i < 1000; ++i) {
150     auto idx = pool.allocIndex();
151     EXPECT_FALSE(idx == 0);
152     int* elem = &pool[idx];
153     EXPECT_TRUE(idx == pool.locateElem(elem));
154   }
155
156   EXPECT_EQ(pool.locateElem(nullptr), 0);
157 }
158
159 struct NonTrivialStruct {
160   static FOLLY_TLS size_t count;
161
162   size_t elem_;
163
164   NonTrivialStruct() {
165     elem_ = 0;
166     ++count;
167   }
168
169   NonTrivialStruct(std::unique_ptr<std::string>&& arg1, size_t arg2) {
170     elem_ = arg1->length() + arg2;
171     ++count;
172   }
173
174   ~NonTrivialStruct() {
175     --count;
176   }
177 };
178
179 FOLLY_TLS size_t NonTrivialStruct::count;
180
181 TEST(IndexedMemPool, eager_recycle) {
182   typedef IndexedMemPool<NonTrivialStruct> Pool;
183   Pool pool(100);
184
185   EXPECT_EQ(NonTrivialStruct::count, 0);
186
187   for (size_t i = 0; i < 10; ++i) {
188     {
189       std::unique_ptr<std::string> arg{ new std::string{ "abc" } };
190       auto ptr = pool.allocElem(std::move(arg), 100);
191       EXPECT_EQ(NonTrivialStruct::count, 1);
192       EXPECT_EQ(ptr->elem_, 103);
193       EXPECT_TRUE(!!ptr);
194     }
195     EXPECT_EQ(NonTrivialStruct::count, 0);
196   }
197 }
198
199 TEST(IndexedMemPool, late_recycle) {
200   {
201     typedef IndexedMemPool<NonTrivialStruct, 8, 8, std::atomic, false, false>
202         Pool;
203     Pool pool(100);
204
205     EXPECT_EQ(NonTrivialStruct::count, 0);
206
207     for (size_t i = 0; i < 10; ++i) {
208       {
209         auto ptr = pool.allocElem();
210         EXPECT_TRUE(NonTrivialStruct::count > 0);
211         EXPECT_TRUE(!!ptr);
212         ptr->elem_ = i;
213       }
214       EXPECT_TRUE(NonTrivialStruct::count > 0);
215     }
216   }
217   EXPECT_EQ(NonTrivialStruct::count, 0);
218 }
219
220 TEST(IndexedMemPool, no_data_races) {
221   const int count = 1000;
222   const uint32_t poolSize = 100;
223   const int nthreads = 10;
224
225   using Pool = IndexedMemPool<int, 8, 8>;
226   Pool pool(poolSize);
227
228   std::vector<std::thread> thr(nthreads);
229   for (auto i = 0; i < nthreads; ++i) {
230     thr[i] = std::thread([&]() {
231       for (auto j = 0; j < count; ++j) {
232         uint32_t idx = pool.allocIndex();
233         EXPECT_NE(idx, 0u);
234         EXPECT_LE(
235             idx, poolSize + (pool.NumLocalLists - 1) * pool.LocalListLimit);
236         pool[idx] = j;
237         pool.recycleIndex(idx);
238       }
239     });
240   }
241   for (auto& t : thr) {
242     t.join();
243   }
244 }
245
246 std::atomic<int> cnum{0};
247 std::atomic<int> dnum{0};
248
249 TEST(IndexedMemPool, construction_destruction) {
250   struct Foo {
251     Foo() {
252       cnum.fetch_add(1);
253     }
254     ~Foo() {
255       dnum.fetch_add(1);
256     }
257   };
258
259   std::atomic<bool> start{false};
260   std::atomic<int> started{0};
261
262   using Pool = IndexedMemPool<Foo, 1, 1, std::atomic, false, false>;
263   int nthreads = 20;
264   int count = 1000;
265
266   {
267     Pool pool(2);
268     std::vector<std::thread> thr(nthreads);
269     for (auto i = 0; i < nthreads; ++i) {
270       thr[i] = std::thread([&]() {
271         started.fetch_add(1);
272         while (!start.load())
273           ;
274         for (auto j = 0; j < count; ++j) {
275           uint32_t idx = pool.allocIndex();
276           if (idx != 0) {
277             pool.recycleIndex(idx);
278           }
279         }
280       });
281     }
282
283     while (started.load() < nthreads)
284       ;
285     start.store(true);
286
287     for (auto& t : thr) {
288       t.join();
289     }
290   }
291
292   CHECK_EQ(cnum.load(), dnum.load());
293 }