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 }