123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515 |
- /*
- * Copyright 2011-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- // @author: Xin Liu <xliux@fb.com>
- #include <folly/ConcurrentSkipList.h>
- #include <atomic>
- #include <memory>
- #include <set>
- #include <system_error>
- #include <thread>
- #include <vector>
- #include <glog/logging.h>
- #include <folly/Memory.h>
- #include <folly/String.h>
- #include <folly/container/Foreach.h>
- #include <folly/memory/Arena.h>
- #include <folly/portability/GFlags.h>
- #include <folly/portability/GTest.h>
- DEFINE_int32(num_threads, 12, "num concurrent threads to test");
- namespace {
- template <typename ParentAlloc>
- struct ParanoidArenaAlloc {
- explicit ParanoidArenaAlloc(ParentAlloc& arena) : arena_(arena) {}
- ParanoidArenaAlloc(ParanoidArenaAlloc const&) = delete;
- ParanoidArenaAlloc(ParanoidArenaAlloc&&) = delete;
- ParanoidArenaAlloc& operator=(ParanoidArenaAlloc const&) = delete;
- ParanoidArenaAlloc& operator=(ParanoidArenaAlloc&&) = delete;
- void* allocate(size_t size) {
- void* result = arena_.get().allocate(size);
- allocated_.insert(result);
- return result;
- }
- void deallocate(void* ptr, size_t n) {
- EXPECT_EQ(1, allocated_.erase(ptr));
- arena_.get().deallocate(ptr, n);
- }
- bool isEmpty() const {
- return allocated_.empty();
- }
- std::reference_wrapper<ParentAlloc> arena_;
- std::set<void*> allocated_;
- };
- } // namespace
- namespace folly {
- template <typename ParentAlloc>
- struct AllocatorHasTrivialDeallocate<ParanoidArenaAlloc<ParentAlloc>>
- : AllocatorHasTrivialDeallocate<ParentAlloc> {};
- } // namespace folly
- namespace {
- using namespace folly;
- using std::vector;
- typedef int ValueType;
- typedef detail::SkipListNode<ValueType> SkipListNodeType;
- typedef ConcurrentSkipList<ValueType> SkipListType;
- typedef SkipListType::Accessor SkipListAccessor;
- typedef vector<ValueType> VectorType;
- typedef std::set<ValueType> SetType;
- static const int kHeadHeight = 2;
- static const int kMaxValue = 5000;
- static void randomAdding(
- int size,
- SkipListAccessor skipList,
- SetType* verifier,
- int maxValue = kMaxValue) {
- for (int i = 0; i < size; ++i) {
- int32_t r = rand() % maxValue;
- verifier->insert(r);
- skipList.add(r);
- }
- }
- static void randomRemoval(
- int size,
- SkipListAccessor skipList,
- SetType* verifier,
- int maxValue = kMaxValue) {
- for (int i = 0; i < size; ++i) {
- int32_t r = rand() % maxValue;
- verifier->insert(r);
- skipList.remove(r);
- }
- }
- static void sumAllValues(SkipListAccessor skipList, int64_t* sum) {
- *sum = 0;
- FOR_EACH (it, skipList) { *sum += *it; }
- VLOG(20) << "sum = " << sum;
- }
- static void concurrentSkip(
- const vector<ValueType>* values,
- SkipListAccessor skipList) {
- int64_t sum = 0;
- SkipListAccessor::Skipper skipper(skipList);
- FOR_EACH (it, *values) {
- if (skipper.to(*it)) {
- sum += *it;
- }
- }
- VLOG(20) << "sum = " << sum;
- }
- bool verifyEqual(SkipListAccessor skipList, const SetType& verifier) {
- EXPECT_EQ(verifier.size(), skipList.size());
- FOR_EACH (it, verifier) {
- CHECK(skipList.contains(*it)) << *it;
- SkipListType::const_iterator iter = skipList.find(*it);
- CHECK(iter != skipList.end());
- EXPECT_EQ(*iter, *it);
- }
- EXPECT_TRUE(std::equal(verifier.begin(), verifier.end(), skipList.begin()));
- return true;
- }
- TEST(ConcurrentSkipList, SequentialAccess) {
- {
- LOG(INFO) << "nodetype size=" << sizeof(SkipListNodeType);
- auto skipList(SkipListType::create(kHeadHeight));
- EXPECT_TRUE(skipList.first() == nullptr);
- EXPECT_TRUE(skipList.last() == nullptr);
- skipList.add(3);
- EXPECT_TRUE(skipList.contains(3));
- EXPECT_FALSE(skipList.contains(2));
- EXPECT_EQ(3, *skipList.first());
- EXPECT_EQ(3, *skipList.last());
- EXPECT_EQ(3, *skipList.find(3));
- EXPECT_FALSE(skipList.find(3) == skipList.end());
- EXPECT_TRUE(skipList.find(2) == skipList.end());
- {
- SkipListAccessor::Skipper skipper(skipList);
- skipper.to(3);
- CHECK_EQ(3, *skipper);
- }
- skipList.add(2);
- EXPECT_EQ(2, *skipList.first());
- EXPECT_EQ(3, *skipList.last());
- skipList.add(5);
- EXPECT_EQ(5, *skipList.last());
- skipList.add(3);
- EXPECT_EQ(5, *skipList.last());
- auto ret = skipList.insert(9);
- EXPECT_EQ(9, *ret.first);
- EXPECT_TRUE(ret.second);
- ret = skipList.insert(5);
- EXPECT_EQ(5, *ret.first);
- EXPECT_FALSE(ret.second);
- EXPECT_EQ(2, *skipList.first());
- EXPECT_EQ(9, *skipList.last());
- EXPECT_TRUE(skipList.pop_back());
- EXPECT_EQ(5, *skipList.last());
- EXPECT_TRUE(skipList.pop_back());
- EXPECT_EQ(3, *skipList.last());
- skipList.add(9);
- skipList.add(5);
- CHECK(skipList.contains(2));
- CHECK(skipList.contains(3));
- CHECK(skipList.contains(5));
- CHECK(skipList.contains(9));
- CHECK(!skipList.contains(4));
- // lower_bound
- auto it = skipList.lower_bound(5);
- EXPECT_EQ(5, *it);
- it = skipList.lower_bound(4);
- EXPECT_EQ(5, *it);
- it = skipList.lower_bound(9);
- EXPECT_EQ(9, *it);
- it = skipList.lower_bound(12);
- EXPECT_FALSE(it.good());
- it = skipList.begin();
- EXPECT_EQ(2, *it);
- // skipper test
- SkipListAccessor::Skipper skipper(skipList);
- skipper.to(3);
- EXPECT_EQ(3, skipper.data());
- skipper.to(5);
- EXPECT_EQ(5, skipper.data());
- CHECK(!skipper.to(7));
- skipList.remove(5);
- skipList.remove(3);
- CHECK(skipper.to(9));
- EXPECT_EQ(9, skipper.data());
- CHECK(!skipList.contains(3));
- skipList.add(3);
- CHECK(skipList.contains(3));
- int pos = 0;
- for (auto entry : skipList) {
- LOG(INFO) << "pos= " << pos++ << " value= " << entry;
- }
- }
- {
- auto skipList(SkipListType::create(kHeadHeight));
- SetType verifier;
- randomAdding(10000, skipList, &verifier);
- verifyEqual(skipList, verifier);
- // test skipper
- SkipListAccessor::Skipper skipper(skipList);
- int num_skips = 1000;
- for (int i = 0; i < num_skips; ++i) {
- int n = i * kMaxValue / num_skips;
- bool found = skipper.to(n);
- EXPECT_EQ(found, (verifier.find(n) != verifier.end()));
- }
- }
- }
- static std::string makeRandomeString(int len) {
- std::string s;
- for (int j = 0; j < len; j++) {
- s.push_back((rand() % 26) + 'A');
- }
- return s;
- }
- TEST(ConcurrentSkipList, TestStringType) {
- typedef folly::ConcurrentSkipList<std::string> SkipListT;
- std::shared_ptr<SkipListT> skip = SkipListT::createInstance();
- SkipListT::Accessor accessor(skip);
- {
- for (int i = 0; i < 100000; i++) {
- std::string s = makeRandomeString(7);
- accessor.insert(s);
- }
- }
- EXPECT_TRUE(std::is_sorted(accessor.begin(), accessor.end()));
- }
- struct UniquePtrComp {
- bool operator()(const std::unique_ptr<int>& x, const std::unique_ptr<int>& y)
- const {
- if (!x) {
- return false;
- }
- if (!y) {
- return true;
- }
- return *x < *y;
- }
- };
- TEST(ConcurrentSkipList, TestMovableData) {
- typedef folly::ConcurrentSkipList<std::unique_ptr<int>, UniquePtrComp>
- SkipListT;
- auto sl = SkipListT::createInstance();
- SkipListT::Accessor accessor(sl);
- static const int N = 10;
- for (int i = 0; i < N; ++i) {
- accessor.insert(std::make_unique<int>(i));
- }
- for (int i = 0; i < N; ++i) {
- EXPECT_TRUE(
- accessor.find(std::unique_ptr<int>(new int(i))) != accessor.end());
- }
- EXPECT_TRUE(
- accessor.find(std::unique_ptr<int>(new int(N))) == accessor.end());
- }
- void testConcurrentAdd(int numThreads) {
- auto skipList(SkipListType::create(kHeadHeight));
- vector<std::thread> threads;
- vector<SetType> verifiers(numThreads);
- try {
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(
- std::thread(&randomAdding, 100, skipList, &verifiers[i], kMaxValue));
- }
- } catch (const std::system_error& e) {
- LOG(WARNING) << "Caught " << exceptionStr(e) << ": could only create "
- << threads.size() << " threads out of " << numThreads;
- }
- for (size_t i = 0; i < threads.size(); ++i) {
- threads[i].join();
- }
- SetType all;
- FOR_EACH (s, verifiers) { all.insert(s->begin(), s->end()); }
- verifyEqual(skipList, all);
- }
- TEST(ConcurrentSkipList, ConcurrentAdd) {
- // test it many times
- for (int numThreads = 10; numThreads < 10000; numThreads += 1000) {
- testConcurrentAdd(numThreads);
- }
- }
- void testConcurrentRemoval(int numThreads, int maxValue) {
- auto skipList = SkipListType::create(kHeadHeight);
- for (int i = 0; i < maxValue; ++i) {
- skipList.add(i);
- }
- vector<std::thread> threads;
- vector<SetType> verifiers(numThreads);
- try {
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(
- std::thread(&randomRemoval, 100, skipList, &verifiers[i], maxValue));
- }
- } catch (const std::system_error& e) {
- LOG(WARNING) << "Caught " << exceptionStr(e) << ": could only create "
- << threads.size() << " threads out of " << numThreads;
- }
- FOR_EACH (t, threads) { (*t).join(); }
- SetType all;
- FOR_EACH (s, verifiers) { all.insert(s->begin(), s->end()); }
- CHECK_EQ(maxValue, all.size() + skipList.size());
- for (int i = 0; i < maxValue; ++i) {
- if (all.find(i) != all.end()) {
- CHECK(!skipList.contains(i)) << i;
- } else {
- CHECK(skipList.contains(i)) << i;
- }
- }
- }
- TEST(ConcurrentSkipList, ConcurrentRemove) {
- for (int numThreads = 10; numThreads < 1000; numThreads += 100) {
- testConcurrentRemoval(numThreads, 100 * numThreads);
- }
- }
- static void
- testConcurrentAccess(int numInsertions, int numDeletions, int maxValue) {
- auto skipList = SkipListType::create(kHeadHeight);
- vector<SetType> verifiers(FLAGS_num_threads);
- vector<int64_t> sums(FLAGS_num_threads);
- vector<vector<ValueType>> skipValues(FLAGS_num_threads);
- for (int i = 0; i < FLAGS_num_threads; ++i) {
- for (int j = 0; j < numInsertions; ++j) {
- skipValues[i].push_back(rand() % (maxValue + 1));
- }
- std::sort(skipValues[i].begin(), skipValues[i].end());
- }
- vector<std::thread> threads;
- for (int i = 0; i < FLAGS_num_threads; ++i) {
- switch (i % 8) {
- case 0:
- case 1:
- threads.push_back(std::thread(
- randomAdding, numInsertions, skipList, &verifiers[i], maxValue));
- break;
- case 2:
- threads.push_back(std::thread(
- randomRemoval, numDeletions, skipList, &verifiers[i], maxValue));
- break;
- case 3:
- threads.push_back(
- std::thread(concurrentSkip, &skipValues[i], skipList));
- break;
- default:
- threads.push_back(std::thread(sumAllValues, skipList, &sums[i]));
- break;
- }
- }
- FOR_EACH (t, threads) { (*t).join(); }
- // just run through it, no need to verify the correctness.
- }
- TEST(ConcurrentSkipList, ConcurrentAccess) {
- testConcurrentAccess(10000, 100, kMaxValue);
- testConcurrentAccess(100000, 10000, kMaxValue * 10);
- testConcurrentAccess(1000000, 100000, kMaxValue);
- }
- struct NonTrivialValue {
- static std::atomic<int> InstanceCounter;
- static const int kBadPayLoad;
- NonTrivialValue() : payload_(kBadPayLoad) {
- ++InstanceCounter;
- }
- explicit NonTrivialValue(int payload) : payload_(payload) {
- ++InstanceCounter;
- }
- NonTrivialValue(const NonTrivialValue& rhs) : payload_(rhs.payload_) {
- ++InstanceCounter;
- }
- NonTrivialValue& operator=(const NonTrivialValue& rhs) {
- payload_ = rhs.payload_;
- return *this;
- }
- ~NonTrivialValue() {
- --InstanceCounter;
- }
- bool operator<(const NonTrivialValue& rhs) const {
- EXPECT_NE(kBadPayLoad, payload_);
- EXPECT_NE(kBadPayLoad, rhs.payload_);
- return payload_ < rhs.payload_;
- }
- private:
- int payload_;
- };
- std::atomic<int> NonTrivialValue::InstanceCounter(0);
- const int NonTrivialValue::kBadPayLoad = 0xDEADBEEF;
- template <typename SkipListPtrType>
- void TestNonTrivialDeallocation(SkipListPtrType& list) {
- {
- auto accessor = typename SkipListPtrType::element_type::Accessor(list);
- static const size_t N = 10000;
- for (size_t i = 0; i < N; ++i) {
- accessor.add(NonTrivialValue(i));
- }
- list.reset();
- }
- EXPECT_EQ(0, NonTrivialValue::InstanceCounter);
- }
- template <typename ParentAlloc>
- void NonTrivialDeallocationWithParanoid(ParentAlloc& parentAlloc) {
- using ParanoidAlloc = ParanoidArenaAlloc<ParentAlloc>;
- using Alloc = CxxAllocatorAdaptor<void, ParanoidAlloc>;
- using ParanoidSkipListType =
- ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
- ParanoidAlloc paranoidAlloc(parentAlloc);
- Alloc alloc(paranoidAlloc);
- auto list = ParanoidSkipListType::createInstance(10, alloc);
- TestNonTrivialDeallocation(list);
- EXPECT_TRUE(paranoidAlloc.isEmpty());
- }
- TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
- SysAllocator<void> alloc;
- NonTrivialDeallocationWithParanoid(alloc);
- }
- TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
- SysArena arena;
- SysArenaAllocator<void> alloc(arena);
- NonTrivialDeallocationWithParanoid(alloc);
- }
- TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
- using SysArenaSkipListType = ConcurrentSkipList<
- NonTrivialValue,
- std::less<NonTrivialValue>,
- SysArenaAllocator<void>>;
- SysArena arena;
- SysArenaAllocator<void> alloc(arena);
- auto list = SysArenaSkipListType::createInstance(10, alloc);
- TestNonTrivialDeallocation(list);
- }
- } // namespace
- int main(int argc, char* argv[]) {
- testing::InitGoogleTest(&argc, argv);
- google::InitGoogleLogging(argv[0]);
- gflags::ParseCommandLineFlags(&argc, &argv, true);
- return RUN_ALL_TESTS();
- }
|