folly/test/AtomicLinkedListTest.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 <algorithm>
  18 #include <thread>
  19
  20 #include <folly/AtomicLinkedList.h>
  21 #include <folly/portability/GTest.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, ReverseSweep) {
  78   TestIntrusiveObject a(1), b(2), c(3);
  79   TestIntrusiveObject::List list;
  80   list.insertHead(&a);
  81   list.insertHead(&b);
  82   list.insertHead(&c);
  83   size_t next_expected_id = 3;
  84   list.reverseSweep([&](TestIntrusiveObject* obj) {
  85     EXPECT_EQ(next_expected_id--, obj->id());
  86   });
  87   EXPECT_TRUE(list.empty());
  88   // Test that we can still insert
  89   list.insertHead(&a);
  90   EXPECT_FALSE(list.empty());
  91   list.reverseSweep([](TestIntrusiveObject*) {});
  92 }
  93
  94 TEST(AtomicIntrusiveLinkedList, Move) {
  95   TestIntrusiveObject a(1), b(2);
  96
  97   TestIntrusiveObject::List list1;
  98
  99   EXPECT_TRUE(list1.insertHead(&a));
 100   EXPECT_FALSE(list1.insertHead(&b));
 101
 102   EXPECT_FALSE(list1.empty());
 103
 104   TestIntrusiveObject::List list2(std::move(list1));
 105
 106   EXPECT_TRUE(list1.empty());
 107   EXPECT_FALSE(list2.empty());
 108
 109   TestIntrusiveObject::List list3;
 110
 111   EXPECT_TRUE(list3.empty());
 112
 113   list3 = std::move(list2);
 114
 115   EXPECT_TRUE(list2.empty());
 116   EXPECT_FALSE(list3.empty());
 117
 118   size_t id = 0;
 119   list3.sweep(
 120       [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
 121 }
 122
 123 TEST(AtomicIntrusiveLinkedList, Stress) {
 124   constexpr size_t kNumThreads = 32;
 125   constexpr size_t kNumElements = 100000;
 126
 127   std::vector<TestIntrusiveObject> elements;
 128   for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
 129     elements.emplace_back(i);
 130   }
 131
 132   TestIntrusiveObject::List list;
 133
 134   std::vector<std::thread> threads;
 135   for (size_t threadId = 0; threadId < kNumThreads; ++threadId) {
 136     threads.emplace_back(
 137         [threadId, kNumThreads, kNumElements, &list, &elements]() {
 138           for (size_t id = 0; id < kNumElements; ++id) {
 139             list.insertHead(&elements[threadId + kNumThreads * id]);
 140           }
 141         });
 142   }
 143
 144   std::vector<size_t> ids;
 145   TestIntrusiveObject* prev{nullptr};
 146
 147   while (ids.size() < kNumThreads * kNumElements) {
 148     list.sweep([&](TestIntrusiveObject* current) {
 149       ids.push_back(current->id());
 150
 151       if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
 152         EXPECT_EQ(prev->id() + kNumThreads, current->id());
 153       }
 154
 155       prev = current;
 156     });
 157   }
 158
 159   std::sort(ids.begin(), ids.end());
 160
 161   for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
 162     EXPECT_EQ(i, ids[i]);
 163   }
 164
 165   for (auto& thread : threads) {
 166     thread.join();
 167   }
 168 }
 169
 170 class TestObject {
 171  public:
 172   TestObject(size_t id__, const std::shared_ptr<void>& ptr)
 173       : id_(id__), ptr_(ptr) {}
 174
 175   size_t id() {
 176     return id_;
 177   }
 178
 179  private:
 180   size_t id_;
 181   std::shared_ptr<void> ptr_;
 182 };
 183
 184 TEST(AtomicLinkedList, Basic) {
 185   constexpr size_t kNumElements = 10;
 186
 187   using List = folly::AtomicLinkedList<TestObject>;
 188   List list;
 189
 190   std::shared_ptr<void> ptr = std::make_shared<int>(42);
 191
 192   for (size_t id = 0; id < kNumElements; ++id) {
 193     list.insertHead({id, ptr});
 194   }
 195
 196   size_t counter = 0;
 197
 198   list.sweep([&](TestObject object) {
 199     EXPECT_EQ(counter, object.id());
 200
 201     EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());
 202
 203     ++counter;
 204   });
 205
 206   EXPECT_TRUE(ptr.unique());
 207 }