folly/test/AtomicLinkedListTest.cpp

   1 /*
   2  * Copyright 2016 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 <thread>
  18
  19 #include <gtest/gtest.h>
  20
  21 #include <folly/AtomicLinkedList.h>
  22
  23 class TestIntrusiveObject {
  24  public:
  25   explicit TestIntrusiveObject(size_t id__) : id_(id__) {}
  26   size_t id() {
  27     return id_;
  28   }
  29
  30  private:
  31   folly::AtomicIntrusiveLinkedListHook<TestIntrusiveObject> hook_;
  32   size_t id_;
  33
  34  public:
  35   using List = folly::AtomicIntrusiveLinkedList<
  36       TestIntrusiveObject,
  37       &TestIntrusiveObject::hook_>;
  38 };
  39
  40 TEST(AtomicIntrusiveLinkedList, Basic) {
  41   TestIntrusiveObject a(1), b(2), c(3);
  42
  43   TestIntrusiveObject::List list;
  44
  45   EXPECT_TRUE(list.empty());
  46
  47   {
  48     EXPECT_TRUE(list.insertHead(&a));
  49     EXPECT_FALSE(list.insertHead(&b));
  50
  51     EXPECT_FALSE(list.empty());
  52
  53     size_t id = 0;
  54     list.sweep(
  55         [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
  56
  57     EXPECT_TRUE(list.empty());
  58   }
  59
  60   // Try re-inserting the same item (b) and a new item (c)
  61   {
  62     EXPECT_TRUE(list.insertHead(&b));
  63     EXPECT_FALSE(list.insertHead(&c));
  64
  65     EXPECT_FALSE(list.empty());
  66
  67     size_t id = 1;
  68     list.sweep(
  69         [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
  70
  71     EXPECT_TRUE(list.empty());
  72   }
  73
  74   TestIntrusiveObject::List movedList = std::move(list);
  75 }
  76
  77 TEST(AtomicIntrusiveLinkedList, Move) {
  78   TestIntrusiveObject a(1), b(2);
  79
  80   TestIntrusiveObject::List list1;
  81
  82   EXPECT_TRUE(list1.insertHead(&a));
  83   EXPECT_FALSE(list1.insertHead(&b));
  84
  85   EXPECT_FALSE(list1.empty());
  86
  87   TestIntrusiveObject::List list2(std::move(list1));
  88
  89   EXPECT_TRUE(list1.empty());
  90   EXPECT_FALSE(list2.empty());
  91
  92   TestIntrusiveObject::List list3;
  93
  94   EXPECT_TRUE(list3.empty());
  95
  96   list3 = std::move(list2);
  97
  98   EXPECT_TRUE(list2.empty());
  99   EXPECT_FALSE(list3.empty());
 100
 101   size_t id = 0;
 102   list3.sweep(
 103       [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
 104 }
 105
 106 TEST(AtomicIntrusiveLinkedList, Stress) {
 107   constexpr size_t kNumThreads = 32;
 108   constexpr size_t kNumElements = 100000;
 109
 110   std::vector<TestIntrusiveObject> elements;
 111   for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
 112     elements.emplace_back(i);
 113   }
 114
 115   TestIntrusiveObject::List list;
 116
 117   std::vector<std::thread> threads;
 118   for (size_t threadId = 0; threadId < kNumThreads; ++threadId) {
 119     threads.emplace_back(
 120         [threadId, kNumThreads, kNumElements, &list, &elements]() {
 121           for (size_t id = 0; id < kNumElements; ++id) {
 122             list.insertHead(&elements[threadId + kNumThreads * id]);
 123           }
 124         });
 125   }
 126
 127   std::vector<size_t> ids;
 128   TestIntrusiveObject* prev{nullptr};
 129
 130   while (ids.size() < kNumThreads * kNumElements) {
 131     list.sweep([&](TestIntrusiveObject* current) {
 132       ids.push_back(current->id());
 133
 134       if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
 135         EXPECT_EQ(prev->id() + kNumThreads, current->id());
 136       }
 137
 138       prev = current;
 139     });
 140   }
 141
 142   std::sort(ids.begin(), ids.end());
 143
 144   for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
 145     EXPECT_EQ(i, ids[i]);
 146   }
 147
 148   for (auto& thread : threads) {
 149     thread.join();
 150   }
 151 }
 152
 153 class TestObject {
 154  public:
 155   TestObject(size_t id__, std::shared_ptr<void> ptr) : id_(id__), ptr_(ptr) {}
 156
 157   size_t id() {
 158     return id_;
 159   }
 160
 161  private:
 162   size_t id_;
 163   std::shared_ptr<void> ptr_;
 164 };
 165
 166 TEST(AtomicLinkedList, Basic) {
 167   constexpr size_t kNumElements = 10;
 168
 169   using List = folly::AtomicLinkedList<TestObject>;
 170   List list;
 171
 172   std::shared_ptr<void> ptr = std::make_shared<int>(42);
 173
 174   for (size_t id = 0; id < kNumElements; ++id) {
 175     list.insertHead({id, ptr});
 176   }
 177
 178   size_t counter = 0;
 179
 180   list.sweep([&](TestObject object) {
 181     EXPECT_EQ(counter, object.id());
 182
 183     EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());
 184
 185     ++counter;
 186   });
 187
 188   EXPECT_TRUE(ptr.unique());
 189 }