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