From d638ae7a87538e30014a37ba8941f0cec51198a0 Mon Sep 17 00:00:00 2001
From: Den Raskovalov <denplusplus@fb.com>
Date: Fri, 5 Feb 2016 21:31:32 -0800
Subject: [PATCH] Call destructor for non-trivial destructors if arena
 allocator is used in ConcurrentSkipList.

Reviewed By: philippv

Differential Revision: D2900534

fb-gh-sync-id: c711a160d541d937ada24f2b524016dbceb40ee2
---
 folly/ConcurrentSkipList-inl.h        |   4 +-
 folly/ConcurrentSkipList.h            |  27 +++++--
 folly/test/ConcurrentSkipListTest.cpp | 108 ++++++++++++++++++++++++++
 3 files changed, 131 insertions(+), 8 deletions(-)

diff --git a/folly/ConcurrentSkipList-inl.h b/folly/ConcurrentSkipList-inl.h
index befa0c95..48e3f63f 100644
--- a/folly/ConcurrentSkipList-inl.h
+++ b/folly/ConcurrentSkipList-inl.h
@@ -73,7 +73,7 @@ class SkipListNode : private boost::noncopyable {
   template<typename NodeAlloc>
   static constexpr bool destroyIsNoOp() {
     return IsArenaAllocator<NodeAlloc>::value &&
-           boost::has_trivial_destructor<std::atomic<SkipListNode*>>::value;
+           boost::has_trivial_destructor<SkipListNode>::value;
   }
 
   // copy the head node to a new head node assuming lock acquired
@@ -236,6 +236,8 @@ class NodeRecycler<NodeType, NodeAlloc, typename std::enable_if<
   explicit NodeRecycler(const NodeAlloc& alloc)
     : refs_(0), dirty_(false), alloc_(alloc) { lock_.init(); }
 
+  explicit NodeRecycler() : refs_(0), dirty_(false) { lock_.init(); }
+
   ~NodeRecycler() {
     CHECK_EQ(refs(), 0);
     if (nodes_) {
diff --git a/folly/ConcurrentSkipList.h b/folly/ConcurrentSkipList.h
index 0cf05f19..cdb71010 100644
--- a/folly/ConcurrentSkipList.h
+++ b/folly/ConcurrentSkipList.h
@@ -161,22 +161,35 @@ class ConcurrentSkipList {
   class Accessor;
   class Skipper;
 
-  explicit ConcurrentSkipList(int height, const NodeAlloc& alloc = NodeAlloc())
-    : recycler_(alloc),
-      head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
-      size_(0) { }
+  explicit ConcurrentSkipList(int height, const NodeAlloc& alloc)
+      : recycler_(alloc),
+        head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
+        size_(0) {}
+
+  explicit ConcurrentSkipList(int height)
+      : recycler_(),
+        head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
+        size_(0) {}
 
   // Convenient function to get an Accessor to a new instance.
-  static Accessor create(int height = 1, const NodeAlloc& alloc = NodeAlloc()) {
+  static Accessor create(int height, const NodeAlloc& alloc) {
     return Accessor(createInstance(height, alloc));
   }
 
+  static Accessor create(int height = 1) {
+    return Accessor(createInstance(height));
+  }
+
   // Create a shared_ptr skiplist object with initial head height.
-  static std::shared_ptr<SkipListType> createInstance(
-      int height = 1, const NodeAlloc& alloc = NodeAlloc()) {
+  static std::shared_ptr<SkipListType> createInstance(int height,
+                                                      const NodeAlloc& alloc) {
     return std::make_shared<ConcurrentSkipList>(height, alloc);
   }
 
+  static std::shared_ptr<SkipListType> createInstance(int height = 1) {
+    return std::make_shared<ConcurrentSkipList>(height);
+  }
+
   //===================================================================
   // Below are implementation details.
   // Please see ConcurrentSkipList::Accessor for stdlib-like APIs.
diff --git a/folly/test/ConcurrentSkipListTest.cpp b/folly/test/ConcurrentSkipListTest.cpp
index 2a26ae36..f99b00ec 100644
--- a/folly/test/ConcurrentSkipListTest.cpp
+++ b/folly/test/ConcurrentSkipListTest.cpp
@@ -16,6 +16,7 @@
 
 // @author: Xin Liu <xliux@fb.com>
 
+#include <atomic>
 #include <memory>
 #include <set>
 #include <vector>
@@ -24,15 +25,48 @@
 
 #include <glog/logging.h>
 #include <gflags/gflags.h>
+
+#include <folly/Arena.h>
 #include <folly/ConcurrentSkipList.h>
 #include <folly/Foreach.h>
+#include <folly/Memory.h>
 #include <folly/String.h>
+
 #include <gtest/gtest.h>
 
 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
 
 namespace {
 
+template <typename ParentAlloc>
+struct ParanoidArenaAlloc {
+  explicit ParanoidArenaAlloc(ParentAlloc* arena) : arena_(arena) {}
+
+  void* allocate(size_t size) {
+    void* result = arena_->allocate(size);
+    allocated_.insert(result);
+    return result;
+  }
+
+  void deallocate(void* ptr) {
+    EXPECT_EQ(1, allocated_.erase(ptr));
+    arena_->deallocate(ptr);
+  }
+
+  bool isEmpty() const { return allocated_.empty(); }
+
+  ParentAlloc* arena_;
+  std::set<void*> allocated_;
+};
+}
+
+namespace folly {
+template <>
+struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
+}
+
+namespace {
+
 using namespace folly;
 using std::vector;
 
@@ -384,6 +418,80 @@ TEST(ConcurrentSkipList, ConcurrentAccess) {
   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() {
+  using Alloc = ParanoidArenaAlloc<ParentAlloc>;
+  using SkipListType =
+      ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
+  ParentAlloc parentAlloc;
+  Alloc paranoidAlloc(&parentAlloc);
+  auto list = SkipListType::createInstance(10, paranoidAlloc);
+  TestNonTrivialDeallocation(list);
+  EXPECT_TRUE(paranoidAlloc.isEmpty());
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
+  NonTrivialDeallocationWithParanoid<SysAlloc>();
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
+  NonTrivialDeallocationWithParanoid<SysArena>();
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
+  using SkipListType =
+      ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, SysArena>;
+  auto list = SkipListType::createInstance(10);
+  TestNonTrivialDeallocation(list);
+}
+
 }  // namespace
 
 int main(int argc, char* argv[]) {
-- 
2.34.1