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