From 0f5638fe81b9dafd9a222bc5e9b1047692e0326e Mon Sep 17 00:00:00 2001 From: Maged Michael Date: Thu, 29 Jun 2017 07:16:37 -0700 Subject: [PATCH] Hazard pointers: Add support for thread local lists of retired objects and other optimizations Summary: - Add support for private lists of retired objects - Add an option for one domain - More scalable thread cache managemnt - hazptr_rec alignment - FOLLY_ALWAYS_INLINE - Refactor management of retired objects in hazptr_domain - Refactor benchmarks Reviewed By: davidtgoldblatt Differential Revision: D5322646 fbshipit-source-id: 9d31582b9a8216861e7e78e2e1cd08dc11cf7f88 --- .../hazptr/bench/HazptrBench-Amb-NoTc.cpp | 24 +- .../hazptr/bench/HazptrBench-Amb-Tc.cpp | 24 +- .../hazptr/bench/HazptrBench-NoAmb-NoTc.cpp | 24 +- .../hazptr/bench/HazptrBench-NoAmb-Tc.cpp | 24 +- .../hazptr/bench/HazptrBench-OneDomain.cpp | 32 +++ folly/experimental/hazptr/bench/HazptrBench.h | 256 ++++++++++++++---- folly/experimental/hazptr/hazptr-impl.h | 195 ++++++++----- folly/experimental/hazptr/hazptr.h | 16 +- folly/experimental/hazptr/memory_resource.h | 3 +- 9 files changed, 380 insertions(+), 218 deletions(-) create mode 100644 folly/experimental/hazptr/bench/HazptrBench-OneDomain.cpp diff --git a/folly/experimental/hazptr/bench/HazptrBench-Amb-NoTc.cpp b/folly/experimental/hazptr/bench/HazptrBench-Amb-NoTc.cpp index 17fc961e..6022de28 100644 --- a/folly/experimental/hazptr/bench/HazptrBench-Amb-NoTc.cpp +++ b/folly/experimental/hazptr/bench/HazptrBench-Amb-NoTc.cpp @@ -16,6 +16,7 @@ #define HAZPTR_AMB true #define HAZPTR_TC false +#define HAZPTR_PRIV false #include #include @@ -23,29 +24,8 @@ using namespace folly::hazptr; -int nthreads; -int size; - -BENCHMARK(amb, iters) { - run_once(nthreads, size, iters); -} - -BENCHMARK(amb_dup, iters) { - run_once(nthreads, size, iters); -} - int main(int argc, char** argv) { testing::InitGoogleTest(&argc, argv); gflags::ParseCommandLineFlags(&argc, &argv, true); - std::cout << "---------------------------------------------- AMB - No TC\n"; - for (int i : nthr) { - nthreads = i; - for (int j : sizes) { - size = j; - std::cout << i << " threads -- " << j << "-item list" << std::endl; - bench("amb - no tc ", i, j, 0); - bench("amb - no tc - dup ", i, j, 0); - } - } - std::cout << "----------------------------------------------------------\n"; + benches(" amb - no tc"); } diff --git a/folly/experimental/hazptr/bench/HazptrBench-Amb-Tc.cpp b/folly/experimental/hazptr/bench/HazptrBench-Amb-Tc.cpp index dea24c87..95788f2d 100644 --- a/folly/experimental/hazptr/bench/HazptrBench-Amb-Tc.cpp +++ b/folly/experimental/hazptr/bench/HazptrBench-Amb-Tc.cpp @@ -16,6 +16,7 @@ #define HAZPTR_AMB true #define HAZPTR_TC true +#define HAZPTR_PRIV true #include #include @@ -23,29 +24,8 @@ using namespace folly::hazptr; -int nthreads; -int size; - -BENCHMARK(amb, iters) { - run_once(nthreads, size, iters); -} - -BENCHMARK(amb_dup, iters) { - run_once(nthreads, size, iters); -} - int main(int argc, char** argv) { testing::InitGoogleTest(&argc, argv); gflags::ParseCommandLineFlags(&argc, &argv, true); - std::cout << "------------------------------------------------- AMB - TC\n"; - for (int i : nthr) { - nthreads = i; - for (int j : sizes) { - size = j; - std::cout << i << " threads -- " << j << "-item list" << std::endl; - bench("amb - tc ", i, j, 0); - bench("amb - tc - dup ", i, j, 0); - } - } - std::cout << "----------------------------------------------------------\n"; + benches(" amb - tc"); } diff --git a/folly/experimental/hazptr/bench/HazptrBench-NoAmb-NoTc.cpp b/folly/experimental/hazptr/bench/HazptrBench-NoAmb-NoTc.cpp index db82693d..7f1ec1f7 100644 --- a/folly/experimental/hazptr/bench/HazptrBench-NoAmb-NoTc.cpp +++ b/folly/experimental/hazptr/bench/HazptrBench-NoAmb-NoTc.cpp @@ -16,6 +16,7 @@ #define HAZPTR_AMB false #define HAZPTR_TC false +#define HAZPTR_PRIV false #include #include @@ -23,29 +24,8 @@ using namespace folly::hazptr; -int nthreads; -int size; - -BENCHMARK(no_amb, iters) { - run_once(nthreads, size, iters); -} - -BENCHMARK(no_amb_dup, iters) { - run_once(nthreads, size, iters); -} - int main(int argc, char** argv) { testing::InitGoogleTest(&argc, argv); gflags::ParseCommandLineFlags(&argc, &argv, true); - std::cout << "------------------------------------------- No AMB - No Tc\n"; - for (int i : nthr) { - nthreads = i; - for (int j : sizes) { - size = j; - std::cout << i << " threads -- " << j << "-item list" << std::endl; - bench("no amb - no tc ", i, j, 0); - bench("no amb - no tc - dup ", i, j, 0); - } - } - std::cout << "----------------------------------------------------------\n"; + benches("no amb - no tc"); } diff --git a/folly/experimental/hazptr/bench/HazptrBench-NoAmb-Tc.cpp b/folly/experimental/hazptr/bench/HazptrBench-NoAmb-Tc.cpp index 4fb420b2..4c78eaf8 100644 --- a/folly/experimental/hazptr/bench/HazptrBench-NoAmb-Tc.cpp +++ b/folly/experimental/hazptr/bench/HazptrBench-NoAmb-Tc.cpp @@ -16,6 +16,7 @@ #define HAZPTR_AMB false #define HAZPTR_TC true +#define HAZPTR_PRIV true #include #include @@ -23,29 +24,8 @@ using namespace folly::hazptr; -int nthreads; -int size; - -BENCHMARK(no_amb, iters) { - run_once(nthreads, size, iters); -} - -BENCHMARK(no_amb_dup, iters) { - run_once(nthreads, size, iters); -} - int main(int argc, char** argv) { testing::InitGoogleTest(&argc, argv); gflags::ParseCommandLineFlags(&argc, &argv, true); - std::cout << "---------------------------------------------- No AMB - TC\n"; - for (int i : nthr) { - nthreads = i; - for (int j : sizes) { - size = j; - std::cout << i << " threads -- " << j << "-item list" << std::endl; - bench("no amb - tc ", i, j, 0); - bench("no amb - tc - dup ", i, j, 0); - } - } - std::cout << "----------------------------------------------------------\n"; + benches("no amb - tc"); } diff --git a/folly/experimental/hazptr/bench/HazptrBench-OneDomain.cpp b/folly/experimental/hazptr/bench/HazptrBench-OneDomain.cpp new file mode 100644 index 00000000..ae8f366c --- /dev/null +++ b/folly/experimental/hazptr/bench/HazptrBench-OneDomain.cpp @@ -0,0 +1,32 @@ +/* + * Copyright 2017 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. + */ + +#define HAZPTR_AMB true +#define HAZPTR_TC true +#define HAZPTR_PRIV true +#define HAZPTR_ONE_DOMAIN true + +#include +#include +#include + +using namespace folly::hazptr; + +int main(int argc, char** argv) { + testing::InitGoogleTest(&argc, argv); + gflags::ParseCommandLineFlags(&argc, &argv, true); + benches(" one domain"); +} diff --git a/folly/experimental/hazptr/bench/HazptrBench.h b/folly/experimental/hazptr/bench/HazptrBench.h index 097cd7f1..2e49e348 100644 --- a/folly/experimental/hazptr/bench/HazptrBench.h +++ b/folly/experimental/hazptr/bench/HazptrBench.h @@ -27,17 +27,17 @@ namespace folly { namespace hazptr { -inline uint64_t run_once(int nthreads, int size, int ops) { +template +inline uint64_t run_once( + int nthreads, + const InitFunc& init, + const Func& fn, + const EndFunc& endFn) { folly::BenchmarkSuspender susp; - SWMRListSet s; std::atomic start{false}; std::atomic started{0}; - hazptr_holder dummy_hptr[100]; - - for (int i = 0; i < size; ++i) { - s.add(i); - } + init(); std::vector threads(nthreads); for (int tid = 0; tid < nthreads; ++tid) { @@ -45,10 +45,7 @@ inline uint64_t run_once(int nthreads, int size, int ops) { started.fetch_add(1); while (!start.load()) /* spin */; - - for (int j = tid; j < ops; j += nthreads) { - s.contains(j); - } + fn(tid); }); } @@ -67,20 +64,21 @@ inline uint64_t run_once(int nthreads, int size, int ops) { susp.rehire(); // end time measurement auto tend = std::chrono::steady_clock::now(); + endFn(); return std::chrono::duration_cast(tend - tbegin) .count(); } -inline uint64_t bench(std::string name, int nthreads, int size, uint64_t base) { +template +inline uint64_t bench(std::string name, int ops, const RepFunc& repFn) { int reps = 10; - int ops = 100000; uint64_t min = UINTMAX_MAX; uint64_t max = 0; uint64_t sum = 0; - run_once(nthreads, size, ops); // sometimes first run is outlier + repFn(); // sometimes first run is outlier for (int r = 0; r < reps; ++r) { - uint64_t dur = run_once(nthreads, size, ops); + uint64_t dur = repFn(); sum += dur; min = std::min(min, dur); max = std::max(max, dur); @@ -93,75 +91,221 @@ inline uint64_t bench(std::string name, int nthreads, int size, uint64_t base) { std::cout << " " << std::setw(4) << max / ops << unit; std::cout << " " << std::setw(4) << avg / ops << unit; std::cout << " " << std::setw(4) << res / ops << unit; - if (base) { - std::cout << " " << std::setw(3) << 100 * base / res << "%"; - } std::cout << std::endl; return res; } +inline uint64_t listBench(std::string name, int nthreads, int size) { + int ops = 100000; + auto repFn = [&] { + hazptr_holder dummy[100]; + SWMRListSet s; + auto init = [&] { + for (int i = 0; i < size; ++i) { + s.add(i); + } + }; + auto fn = [&](int tid) { + for (int j = tid; j < ops; j += nthreads) { + s.contains(size); + } + }; + auto endFn = [] {}; + return run_once(nthreads, init, fn, endFn); + }; + return bench(name, ops, repFn); +} + +inline uint64_t holderBench(std::string name, int nthreads) { + int ops = 100000; + auto repFn = [&] { + hazptr_holder dummy[100]; + auto init = [] {}; + auto fn = [&](int tid) { + for (int j = tid; j < ops; j += nthreads) { + hazptr_holder a[10]; + } + }; + auto endFn = [] {}; + return run_once(nthreads, init, fn, endFn); + }; + return bench(name, ops, repFn); +} + +inline uint64_t retireBench(std::string name, int nthreads) { + struct Foo : hazptr_obj_base { + int x; + }; + int ops = 100000; + auto repFn = [&] { + hazptr_holder dummy[100]; + auto init = [] {}; + auto fn = [&](int tid) { + for (int j = tid; j < ops; j += nthreads) { + Foo* p = new Foo; + p->retire(); + } + }; + auto endFn = [] {}; + return run_once(nthreads, init, fn, endFn); + }; + return bench(name, ops, repFn); +} + const int nthr[] = {1, 10}; const int sizes[] = {10, 100}; -const std::string header = "Test_name, Max time, Avg time, Min time"; -} // namespace folly { +inline void benches(std::string name) { + std::cout << "------------------------------------------- " << name << "\n"; + for (int i : nthr) { + std::cout << i << " threads -- construct/destruct 10 hazptr_holder-s" + << std::endl; + holderBench(name + " ", i); + holderBench(name + " - dup ", i); + std::cout << i << " threads -- allocate/retire/reclaim object" << std::endl; + retireBench(name + " ", i); + retireBench(name + " - dup ", i); + for (int j : sizes) { + std::cout << i << " threads -- " << j << "-item list" << std::endl; + listBench(name + " ", i, j); + listBench(name + " - dup ", i, j); + } + } + std::cout << "----------------------------------------------------------\n"; +} + } // namespace hazptr { +} // namespace folly { /* -------------------------------------------- No AMB - No Tc +------------------------------------------- no amb - no tc +1 threads -- construct/destruct 10 hazptr_holder-s +no amb - no tc 2518 ns 2461 ns 2431 ns +no amb - no tc - dup 2499 ns 2460 ns 2420 ns +1 threads -- allocate/retire/reclaim object +no amb - no tc 85 ns 83 ns 81 ns +no amb - no tc - dup 83 ns 82 ns 81 ns +1 threads -- 10-item list +no amb - no tc 655 ns 644 ns 639 ns +no amb - no tc - dup 658 ns 645 ns 641 ns +1 threads -- 100-item list +no amb - no tc 2175 ns 2142 ns 2124 ns +no amb - no tc - dup 2294 ns 2228 ns 2138 ns +10 threads -- construct/destruct 10 hazptr_holder-s +no amb - no tc 3893 ns 2932 ns 1391 ns +no amb - no tc - dup 3157 ns 2927 ns 2726 ns +10 threads -- allocate/retire/reclaim object +no amb - no tc 152 ns 134 ns 127 ns +no amb - no tc - dup 141 ns 133 ns 128 ns +10 threads -- 10-item list +no amb - no tc 532 ns 328 ns 269 ns +no amb - no tc - dup 597 ns 393 ns 271 ns +10 threads -- 100-item list +no amb - no tc 757 ns 573 ns 412 ns +no amb - no tc - dup 819 ns 643 ns 420 ns +---------------------------------------------------------- +------------------------------------------- amb - no tc +1 threads -- construct/destruct 10 hazptr_holder-s + amb - no tc 2590 ns 2481 ns 2422 ns + amb - no tc - dup 2519 ns 2468 ns 2424 ns +1 threads -- allocate/retire/reclaim object + amb - no tc 69 ns 68 ns 67 ns + amb - no tc - dup 69 ns 68 ns 67 ns 1 threads -- 10-item list -no amb - no tc 713 ns 672 ns 648 ns -no amb - no tc - dup 692 ns 660 ns 648 ns + amb - no tc 524 ns 510 ns 492 ns + amb - no tc - dup 514 ns 507 ns 496 ns 1 threads -- 100-item list -no amb - no tc 2167 ns 2146 ns 2133 ns -no amb - no tc - dup 2210 ns 2153 ns 2133 ns + amb - no tc 761 ns 711 ns 693 ns + amb - no tc - dup 717 ns 694 ns 684 ns +10 threads -- construct/destruct 10 hazptr_holder-s + amb - no tc 3302 ns 2908 ns 1612 ns + amb - no tc - dup 3220 ns 2909 ns 1641 ns +10 threads -- allocate/retire/reclaim object + amb - no tc 129 ns 123 ns 110 ns + amb - no tc - dup 135 ns 127 ns 120 ns 10 threads -- 10-item list -no amb - no tc 716 ns 614 ns 285 ns -no amb - no tc - dup 750 ns 546 ns 285 ns + amb - no tc 512 ns 288 ns 256 ns + amb - no tc - dup 275 ns 269 ns 263 ns 10 threads -- 100-item list -no amb - no tc 1923 ns 1482 ns 862 ns -no amb - no tc - dup 1978 ns 1614 ns 1112 ns + amb - no tc 297 ns 289 ns 284 ns + amb - no tc - dup 551 ns 358 ns 282 ns ---------------------------------------------------------- ----------------------------------------------- AMB - No TC +------------------------------------------- no amb - tc +1 threads -- construct/destruct 10 hazptr_holder-s +no amb - tc 56 ns 55 ns 55 ns +no amb - tc - dup 56 ns 54 ns 54 ns +1 threads -- allocate/retire/reclaim object +no amb - tc 63 ns 62 ns 62 ns +no amb - tc - dup 64 ns 63 ns 62 ns 1 threads -- 10-item list -amb - no tc 519 ns 504 ns 501 ns -amb - no tc - dup 533 ns 511 ns 500 ns +no amb - tc 190 ns 188 ns 187 ns +no amb - tc - dup 193 ns 186 ns 182 ns 1 threads -- 100-item list -amb - no tc 721 ns 696 ns 689 ns -amb - no tc - dup 786 ns 718 ns 688 ns +no amb - tc 1859 ns 1698 ns 1666 ns +no amb - tc - dup 1770 ns 1717 ns 1673 ns +10 threads -- construct/destruct 10 hazptr_holder-s +no amb - tc 19 ns 11 ns 7 ns +no amb - tc - dup 11 ns 8 ns 7 ns +10 threads -- allocate/retire/reclaim object +no amb - tc 9 ns 8 ns 8 ns +no amb - tc - dup 10 ns 9 ns 8 ns 10 threads -- 10-item list -amb - no tc 695 ns 565 ns 380 ns -amb - no tc - dup 710 ns 450 ns 242 ns +no amb - tc 40 ns 25 ns 21 ns +no amb - tc - dup 24 ns 23 ns 21 ns 10 threads -- 100-item list -amb - no tc 921 ns 773 ns 573 ns -amb - no tc - dup 594 ns 441 ns 409 ns +no amb - tc 215 ns 208 ns 188 ns +no amb - tc - dup 215 ns 209 ns 197 ns ---------------------------------------------------------- ----------------------------------------------- No AMB - TC +------------------------------------------- amb - tc +1 threads -- construct/destruct 10 hazptr_holder-s + amb - tc 56 ns 54 ns 54 ns + amb - tc - dup 55 ns 54 ns 53 ns +1 threads -- allocate/retire/reclaim object + amb - tc 62 ns 61 ns 61 ns + amb - tc - dup 62 ns 61 ns 61 ns 1 threads -- 10-item list -no amb - tc 182 ns 180 ns 178 ns -no amb - tc - dup 205 ns 183 ns 178 ns + amb - tc 36 ns 35 ns 33 ns + amb - tc - dup 37 ns 35 ns 34 ns 1 threads -- 100-item list -no amb - tc 1756 ns 1697 ns 1670 ns -no amb - tc - dup 1718 ns 1681 ns 1666 ns + amb - tc 262 ns 247 ns 230 ns + amb - tc - dup 249 ns 238 ns 230 ns +10 threads -- construct/destruct 10 hazptr_holder-s + amb - tc 14 ns 12 ns 11 ns + amb - tc - dup 12 ns 11 ns 11 ns +10 threads -- allocate/retire/reclaim object + amb - tc 18 ns 17 ns 15 ns + amb - tc - dup 18 ns 17 ns 15 ns 10 threads -- 10-item list -no amb - tc 174 ns 120 ns 55 ns -no amb - tc - dup 174 ns 143 ns 114 ns + amb - tc 9 ns 8 ns 8 ns + amb - tc - dup 8 ns 8 ns 7 ns 10 threads -- 100-item list -no amb - tc 1480 ns 1058 ns 565 ns -no amb - tc - dup 1834 ns 1327 ns 1065 ns + amb - tc 52 ns 42 ns 28 ns + amb - tc - dup 44 ns 37 ns 28 ns ---------------------------------------------------------- -------------------------------------------------- AMB - TC +------------------------------------------- one domain +1 threads -- construct/destruct 10 hazptr_holder-s + one domain 57 ns 56 ns 55 ns + one domain - dup 56 ns 54 ns 53 ns +1 threads -- allocate/retire/reclaim object + one domain 87 ns 71 ns 64 ns + one domain - dup 69 ns 68 ns 68 ns 1 threads -- 10-item list -amb - tc 32 ns 32 ns 31 ns -amb - tc - dup 32 ns 32 ns 31 ns + one domain 32 ns 30 ns 29 ns + one domain - dup 31 ns 30 ns 29 ns 1 threads -- 100-item list -amb - tc 238 ns 229 ns 221 ns -amb - tc - dup 224 ns 222 ns 221 ns + one domain 269 ns 238 ns 226 ns + one domain - dup 237 ns 232 ns 227 ns +10 threads -- construct/destruct 10 hazptr_holder-s + one domain 16 ns 12 ns 10 ns + one domain - dup 11 ns 10 ns 10 ns +10 threads -- allocate/retire/reclaim object + one domain 19 ns 17 ns 16 ns + one domain - dup 19 ns 17 ns 15 ns 10 threads -- 10-item list -amb - tc 27 ns 20 ns 13 ns -amb - tc - dup 28 ns 22 ns 18 ns + one domain 6 ns 5 ns 5 ns + one domain - dup 6 ns 5 ns 5 ns 10 threads -- 100-item list -amb - tc 221 ns 165 ns 116 ns -amb - tc - dup 277 ns 169 ns 120 ns + one domain 40 ns 39 ns 35 ns + one domain - dup 40 ns 39 ns 35 ns ---------------------------------------------------------- */ diff --git a/folly/experimental/hazptr/hazptr-impl.h b/folly/experimental/hazptr/hazptr-impl.h index 34166873..6b19bd8a 100644 --- a/folly/experimental/hazptr/hazptr-impl.h +++ b/folly/experimental/hazptr/hazptr-impl.h @@ -34,7 +34,15 @@ #endif #ifndef HAZPTR_TC_SIZE -#define HAZPTR_TC_SIZE 2 +#define HAZPTR_TC_SIZE 10 +#endif + +#ifndef HAZPTR_PRIV +#define HAZPTR_PRIV true +#endif + +#ifndef HAZPTR_ONE_DOMAIN +#define HAZPTR_ONE_DOMAIN false #endif #ifndef HAZPTR_SCAN_MULT @@ -50,6 +58,7 @@ #define HAZPTR_STATS false #endif +#include #include #include @@ -82,7 +91,9 @@ class hazptr_mb { static void heavy(); }; -/** hazptr_tc */ +/** hazptr_tc + * Thread caching of hazptr_rec-s that belong to the default domain. + */ class hazptr_tc_entry { friend class hazptr_tc; @@ -95,18 +106,39 @@ class hazptr_tc_entry { }; class hazptr_tc { - hazptr_domain* domain_{&default_hazptr_domain()}; hazptr_tc_entry tc_[HAZPTR_TC_SIZE]; + int count_{0}; public: hazptr_tc(); ~hazptr_tc(); - hazptr_rec* get(hazptr_domain* domain); - bool put(hazptr_rec* hprec, hazptr_domain* domain); + hazptr_rec* get(); + bool put(hazptr_rec* hprec); }; hazptr_tc& hazptr_tc(); +/** hazptr_priv + * Thread private lists of retired objects that belong to the default domain. + */ + +class hazptr_priv { + hazptr_domain* domain_{&default_hazptr_domain()}; + hazptr_obj* head_{nullptr}; + hazptr_obj* tail_{nullptr}; + int rcount_{0}; + + public: + hazptr_priv(); + ~hazptr_priv(); + void push(hazptr_obj* obj); + + private: + void pushAllToDomain(); +}; + +hazptr_priv& hazptr_priv(); + /** * public functions */ @@ -127,7 +159,12 @@ inline void hazptr_obj_base::retire(hazptr_domain& domain, D deleter) { auto obj = static_cast(hobp); hobp->deleter_(obj); }; - domain.objRetire(this); + if (HAZPTR_PRIV && + (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) { + hazptr_priv().push(this); + } else { + domain.objRetire(this); + } } /** hazptr_rec */ @@ -137,6 +174,7 @@ class hazptr_rec { friend class hazptr_holder; friend class hazptr_tc_entry; + FOLLY_ALIGN_TO_AVOID_FALSE_SHARING std::atomic hazptr_{nullptr}; hazptr_rec* next_{nullptr}; std::atomic active_{false}; @@ -151,7 +189,7 @@ class hazptr_rec { /** hazptr_holder */ -inline hazptr_holder::hazptr_holder(hazptr_domain& domain) { +FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) { domain_ = &domain; hazptr_ = domain_->hazptrAcquire(); DEBUG_PRINT(this << " " << domain_ << " " << hazptr_); @@ -164,21 +202,22 @@ inline hazptr_holder::hazptr_holder(std::nullptr_t) { DEBUG_PRINT(this << " " << domain_ << " " << hazptr_); } -hazptr_holder::~hazptr_holder() { +FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() { DEBUG_PRINT(this); if (domain_) { + hazptr_->clear(); domain_->hazptrRelease(hazptr_); } } -hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept { +inline hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept { domain_ = rhs.domain_; hazptr_ = rhs.hazptr_; rhs.domain_ = nullptr; rhs.hazptr_ = nullptr; } -hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept { +inline hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept { /* Self-move is a no-op. */ if (this != &rhs) { this->~hazptr_holder(); @@ -188,7 +227,7 @@ hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept { } template -inline bool hazptr_holder::try_protect( +FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect( T*& ptr, const std::atomic& src) noexcept { DEBUG_PRINT(this << " " << ptr << " " << &src); @@ -204,7 +243,8 @@ inline bool hazptr_holder::try_protect( } template -inline T* hazptr_holder::get_protected(const std::atomic& src) noexcept { +FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected( + const std::atomic& src) noexcept { T* p = src.load(std::memory_order_relaxed); while (!try_protect(p, src)) {} DEBUG_PRINT(this << " " << p << " " << &src); @@ -212,38 +252,40 @@ inline T* hazptr_holder::get_protected(const std::atomic& src) noexcept { } template -inline void hazptr_holder::reset(const T* ptr) noexcept { +FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept { auto p = static_cast(const_cast(ptr)); DEBUG_PRINT(this << " " << ptr << " p:" << p); DCHECK(hazptr_); // UB if *this is empty hazptr_->set(p); } -inline void hazptr_holder::reset(std::nullptr_t) noexcept { +FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept { DEBUG_PRINT(this); DCHECK(hazptr_); // UB if *this is empty hazptr_->clear(); } -inline void hazptr_holder::swap(hazptr_holder& rhs) noexcept { +FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept { DEBUG_PRINT( this << " " << this->hazptr_ << " " << this->domain_ << " -- " << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_); - std::swap(this->domain_, rhs.domain_); + if (!HAZPTR_ONE_DOMAIN) { + std::swap(this->domain_, rhs.domain_); + } std::swap(this->hazptr_, rhs.hazptr_); } -inline void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept { +FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept { lhs.swap(rhs); } //////////////////////////////////////////////////////////////////////////////// // [TODO]: -// - Private storage of retired objects // - Control of reclamation (when and by whom) // - End-to-end lock-free implementation /** Definition of default_hazptr_domain() */ + inline hazptr_domain& default_hazptr_domain() { static hazptr_domain d; DEBUG_PRINT(&d); @@ -285,7 +327,6 @@ inline bool hazptr_rec::tryAcquire() noexcept { inline void hazptr_rec::release() noexcept { DEBUG_PRINT(this); - clear(); active_.store(false, std::memory_order_release); } @@ -321,9 +362,9 @@ inline hazptr_domain::~hazptr_domain() { } } -inline hazptr_rec* hazptr_domain::hazptrAcquire() { - if (HAZPTR_TC) { - hazptr_rec* hprec = hazptr_tc().get(this); +FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_domain::hazptrAcquire() { + if (HAZPTR_TC && (HAZPTR_ONE_DOMAIN || this == &default_hazptr_domain())) { + auto hprec = hazptr_tc().get(); if (hprec) { return hprec; } @@ -350,8 +391,9 @@ inline hazptr_rec* hazptr_domain::hazptrAcquire() { return p; } -inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept { - if (HAZPTR_TC && hazptr_tc().put(p, this)) { +FOLLY_ALWAYS_INLINE void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept { + if (HAZPTR_TC && (HAZPTR_ONE_DOMAIN || this == &default_hazptr_domain()) && + hazptr_tc().put(p)) { return; } DEBUG_PRINT(this << " " << p); @@ -368,13 +410,18 @@ hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) { std::memory_order_release, std::memory_order_acquire)) { } - return rcount_.fetch_add(count); + return rcount_.fetch_add(count) + count; +} + +inline bool hazptr_domain::reachedThreshold(int rcount) { + return ( + rcount >= HAZPTR_SCAN_THRESHOLD && + rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)); } inline void hazptr_domain::objRetire(hazptr_obj* p) { - auto rcount = pushRetired(p, p, 1) + 1; - if (rcount >= HAZPTR_SCAN_THRESHOLD && - rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)) { + auto rcount = pushRetired(p, p, 1); + if (reachedThreshold(rcount)) { tryBulkReclaim(); } } @@ -448,7 +495,7 @@ inline hazptr_stats::~hazptr_stats() { DEBUG_PRINT(this << " seq_cst " << seq_cst_.load()); } -inline void hazptr_stats::light() { +FOLLY_ALWAYS_INLINE void hazptr_stats::light() { if (HAZPTR_STATS) { /* atomic */ ++light_; } @@ -505,20 +552,15 @@ inline void hazptr_tc_entry::fill(hazptr_rec* hprec) { inline hazptr_rec* hazptr_tc_entry::get() { auto hprec = hprec_; - if (hprec) { - hprec_ = nullptr; - DEBUG_PRINT(this << " " << hprec); - return hprec; - } - return nullptr; + hprec_ = nullptr; + DEBUG_PRINT(this << " " << hprec); + return hprec; } inline void hazptr_tc_entry::evict() { auto hprec = hprec_; - if (hprec) { - hprec_ = nullptr; - hprec->release(); - } + hprec_ = nullptr; + hprec->release(); DEBUG_PRINT(this << " " << hprec); } @@ -528,36 +570,26 @@ inline hazptr_tc::hazptr_tc() { inline hazptr_tc::~hazptr_tc() { DEBUG_PRINT(this); - for (int i = 0; i < HAZPTR_TC_SIZE; ++i) { + for (int i = 0; i < count_; ++i) { tc_[i].evict(); } } -inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) { - if (domain != domain_) { - return nullptr; - } - for (int i = 0; i < HAZPTR_TC_SIZE; ++i) { - auto hprec = tc_[i].get(); - if (hprec) { - DEBUG_PRINT(this << " " << hprec); - return hprec; - } +inline hazptr_rec* hazptr_tc::get() { + if (count_ > 0) { + auto hprec = tc_[--count_].get(); + DEBUG_PRINT(this << " " << hprec); + return hprec; } DEBUG_PRINT(this << " nullptr"); return nullptr; } -inline bool hazptr_tc::put(hazptr_rec* hprec, hazptr_domain* domain) { - if (domain != domain_) { - return false; - } - for (int i = 0; i < HAZPTR_TC_SIZE; ++i) { - if (tc_[i].hprec_ == nullptr) { - tc_[i].fill(hprec); - DEBUG_PRINT(this << " " << i); - return true; - } +inline bool hazptr_tc::put(hazptr_rec* hprec) { + if (count_ < HAZPTR_TC_SIZE) { + tc_[count_++].fill(hprec); + DEBUG_PRINT(this << " " << count_ - 1); + return true; } return false; } @@ -568,10 +600,45 @@ inline class hazptr_tc& hazptr_tc() { return tc; } -inline std::mutex& hazptr_tc_lock() { - static std::mutex m; - DEBUG_PRINT(&m); - return m; +/** hazptr_priv - functions */ + +inline hazptr_priv::hazptr_priv() { + DEBUG_PRINT(this); +} + +inline hazptr_priv::~hazptr_priv() { + DEBUG_PRINT(this); + if (tail_) { + pushAllToDomain(); + } +} + +inline void hazptr_priv::push(hazptr_obj* obj) { + obj->next_ = nullptr; + if (tail_) { + tail_->next_ = obj; + } else { + head_ = obj; + } + tail_ = obj; + ++rcount_; + if (domain_->reachedThreshold(rcount_)) { + pushAllToDomain(); + } +} + +inline void hazptr_priv::pushAllToDomain() { + domain_->pushRetired(head_, tail_, rcount_); + head_ = nullptr; + tail_ = nullptr; + rcount_ = 0; + domain_->tryBulkReclaim(); +} + +inline class hazptr_priv& hazptr_priv() { + static thread_local class hazptr_priv priv; + DEBUG_PRINT(&priv); + return priv; } } // namespace folly diff --git a/folly/experimental/hazptr/hazptr.h b/folly/experimental/hazptr/hazptr.h index 35d40113..d5944adf 100644 --- a/folly/experimental/hazptr/hazptr.h +++ b/folly/experimental/hazptr/hazptr.h @@ -17,9 +17,6 @@ #define HAZPTR_H #include -#include -#include -#include /* Stand-in for C++17 std::pmr::memory_resource */ #include @@ -51,9 +48,10 @@ class hazptr_domain { hazptr_domain& operator=(hazptr_domain&&) = delete; private: + friend class hazptr_holder; template friend class hazptr_obj_base; - friend class hazptr_holder; + friend class hazptr_priv; memory_resource* mr_; std::atomic hazptrs_ = {nullptr}; @@ -65,6 +63,7 @@ class hazptr_domain { hazptr_rec* hazptrAcquire(); void hazptrRelease(hazptr_rec*) noexcept; int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count); + bool reachedThreshold(int rcount); void tryBulkReclaim(); void bulkReclaim(); }; @@ -77,6 +76,7 @@ class hazptr_obj { friend class hazptr_domain; template friend class hazptr_obj_base; + friend class hazptr_priv; void (*reclaim_)(hazptr_obj*); hazptr_obj* next_; @@ -84,17 +84,15 @@ class hazptr_obj { }; /** Definition of hazptr_obj_base */ -template > +template > class hazptr_obj_base : public hazptr_obj { public: /* Retire a removed object and pass the responsibility for * reclaiming it to the hazptr library */ - void retire( - hazptr_domain& domain = default_hazptr_domain(), - Deleter reclaim = {}); + void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {}); private: - Deleter deleter_; + D deleter_; }; /** hazptr_holder: Class for automatic acquisition and release of diff --git a/folly/experimental/hazptr/memory_resource.h b/folly/experimental/hazptr/memory_resource.h index 952c8397..8a855685 100644 --- a/folly/experimental/hazptr/memory_resource.h +++ b/folly/experimental/hazptr/memory_resource.h @@ -15,6 +15,8 @@ */ #pragma once +#include + //////////////////////////////////////////////////////////////////////////////// /// Disclaimer: This is intended only as a partial stand-in for /// std::pmr::memory_resource (C++17) as needed for developing a @@ -45,7 +47,6 @@ memory_resource* new_delete_resource(); //////////////////////////////////////////////////////////////////////////////// /// Implementation //////////////////////////////////////////////////////////////////////////////// -#include inline memory_resource** default_mr_ptr() { /* library-local */ static memory_resource* default_mr = -- 2.34.1