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([threadId, &list, &elements] {
 137       for (size_t id = 0; id < kNumElements; ++id) {
 138         list.insertHead(&elements[threadId + kNumThreads * id]);
 139       }
 140     });
 141   }
 142
 143   std::vector<size_t> ids;
 144   TestIntrusiveObject* prev{nullptr};
 145
 146   while (ids.size() < kNumThreads * kNumElements) {
 147     list.sweep([&](TestIntrusiveObject* current) {
 148       ids.push_back(current->id());
 149
 150       if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
 151         EXPECT_EQ(prev->id() + kNumThreads, current->id());
 152       }
 153
 154       prev = current;
 155     });
 156   }
 157
 158   std::sort(ids.begin(), ids.end());
 159
 160   for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
 161     EXPECT_EQ(i, ids[i]);
 162   }
 163
 164   for (auto& thread : threads) {
 165     thread.join();
 166   }
 167 }
 168
 169 class TestObject {
 170  public:
 171   TestObject(size_t id__, const std::shared_ptr<void>& ptr)
 172       : id_(id__), ptr_(ptr) {}
 173
 174   size_t id() {
 175     return id_;
 176   }
 177
 178  private:
 179   size_t id_;
 180   std::shared_ptr<void> ptr_;
 181 };
 182
 183 TEST(AtomicLinkedList, Basic) {
 184   constexpr size_t kNumElements = 10;
 185
 186   using List = folly::AtomicLinkedList<TestObject>;
 187   List list;
 188
 189   std::shared_ptr<void> ptr = std::make_shared<int>(42);
 190
 191   for (size_t id = 0; id < kNumElements; ++id) {
 192     list.insertHead({id, ptr});
 193   }
 194
 195   size_t counter = 0;
 196
 197   list.sweep([&](TestObject object) {
 198     EXPECT_EQ(counter, object.id());
 199
 200     EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());
 201
 202     ++counter;
 203   });
 204
 205   EXPECT_TRUE(ptr.unique());
 206 }