1/*
2 * Copyright 2017-present 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#pragma once
18
19#include <cstddef>
20#include <cstring>
21#include <limits>
22#include <memory>
23#include <ostream>
24#include <vector>
25
26#include <folly/Demangle.h>
27#include <folly/Function.h>
28#include <folly/container/detail/F14Policy.h>
29#include <folly/container/detail/F14Table.h>
30
31namespace folly {
32namespace f14 {
33
34struct Histo {
35 std::vector<std::size_t> const& data;
36};
37
38std::ostream& operator<<(std::ostream& xo, Histo const& histo) {
39 xo << "[";
40 size_t sum = 0;
41 for (auto v : histo.data) {
42 sum += v;
43 }
44 size_t partial = 0;
45 for (size_t i = 0; i < histo.data.size(); ++i) {
46 if (i > 0) {
47 xo << ", ";
48 }
49 partial += histo.data[i];
50 if (histo.data[i] > 0) {
51 xo << i << ": " << histo.data[i] << " ("
52 << (static_cast<double>(partial) * 100.0 / sum) << "%)";
53 }
54 }
55 xo << "]";
56 return xo;
57}
58
59void accumulate(
60 std::vector<std::size_t>& a,
61 std::vector<std::size_t> const& d) {
62 if (a.size() < d.size()) {
63 a.resize(d.size());
64 }
65 for (std::size_t i = 0; i < d.size(); ++i) {
66 a[i] += d[i];
67 }
68}
69
70double expectedProbe(std::vector<std::size_t> const& probeLengths) {
71 std::size_t sum = 0;
72 std::size_t count = 0;
73 for (std::size_t i = 1; i < probeLengths.size(); ++i) {
74 sum += i * probeLengths[i];
75 count += probeLengths[i];
76 }
77 return static_cast<double>(sum) / static_cast<double>(count);
78}
79
80// Returns i such that probeLengths elements 0 to i (inclusive) account
81// for at least 99% of the samples.
82std::size_t p99Probe(std::vector<std::size_t> const& probeLengths) {
83 std::size_t count = 0;
84 for (std::size_t i = 1; i < probeLengths.size(); ++i) {
85 count += probeLengths[i];
86 }
87 std::size_t rv = probeLengths.size();
88 std::size_t suffix = 0;
89 while ((suffix + probeLengths[rv - 1]) * 100 <= count) {
90 --rv;
91 }
92 return rv;
93}
94
95struct MoveOnlyTestInt {
96 int x;
97 bool destroyed{false};
98
99 MoveOnlyTestInt() noexcept : x(0) {}
100 /* implicit */ MoveOnlyTestInt(int x0) : x(x0) {}
101 MoveOnlyTestInt(MoveOnlyTestInt&& rhs) noexcept : x(rhs.x) {}
102 MoveOnlyTestInt(MoveOnlyTestInt const&) = delete;
103 MoveOnlyTestInt& operator=(MoveOnlyTestInt&& rhs) noexcept {
104 x = rhs.x;
105 destroyed = rhs.destroyed;
106 return *this;
107 }
108 MoveOnlyTestInt& operator=(MoveOnlyTestInt const&) = delete;
109
110 ~MoveOnlyTestInt() {
111 destroyed = true;
112 }
113
114 bool operator==(MoveOnlyTestInt const& rhs) const {
115 return x == rhs.x && destroyed == rhs.destroyed;
116 }
117 bool operator!=(MoveOnlyTestInt const& rhs) const {
118 return !(*this == rhs);
119 }
120};
121
122// Tracked is implicitly constructible across tags
123struct Counts {
124 uint64_t copyConstruct{0};
125 uint64_t moveConstruct{0};
126 uint64_t copyConvert{0};
127 uint64_t moveConvert{0};
128 uint64_t copyAssign{0};
129 uint64_t moveAssign{0};
130 uint64_t defaultConstruct{0};
131 uint64_t destroyed{0};
132
133 explicit Counts(
134 uint64_t copConstr = 0,
135 uint64_t movConstr = 0,
136 uint64_t copConv = 0,
137 uint64_t movConv = 0,
138 uint64_t copAssign = 0,
139 uint64_t movAssign = 0,
140 uint64_t def = 0,
141 uint64_t destr = 0)
142 : copyConstruct{copConstr},
143 moveConstruct{movConstr},
144 copyConvert{copConv},
145 moveConvert{movConv},
146 copyAssign{copAssign},
147 moveAssign{movAssign},
148 defaultConstruct{def},
149 destroyed{destr} {}
150
151 int64_t liveCount() const {
152 return copyConstruct + moveConstruct + copyConvert + moveConvert +
153 defaultConstruct - destroyed;
154 }
155
156 // dist ignores destroyed count
157 uint64_t dist(Counts const& rhs) const {
158 auto d = [](uint64_t x, uint64_t y) { return (x - y) * (x - y); };
159 return d(copyConstruct, rhs.copyConstruct) +
160 d(moveConstruct, rhs.moveConstruct) + d(copyConvert, rhs.copyConvert) +
161 d(moveConvert, rhs.moveConvert) + d(copyAssign, rhs.copyAssign) +
162 d(moveAssign, rhs.moveAssign) +
163 d(defaultConstruct, rhs.defaultConstruct);
164 }
165
166 bool operator==(Counts const& rhs) const {
167 return dist(rhs) == 0 && destroyed == rhs.destroyed;
168 }
169 bool operator!=(Counts const& rhs) const {
170 return !(*this == rhs);
171 }
172};
173
174std::ostream& operator<<(std::ostream& xo, Counts const& counts) {
175 xo << "[";
176 std::string glue = "";
177 if (counts.copyConstruct > 0) {
178 xo << glue << counts.copyConstruct << " copy";
179 glue = ", ";
180 }
181 if (counts.moveConstruct > 0) {
182 xo << glue << counts.moveConstruct << " move";
183 glue = ", ";
184 }
185 if (counts.copyConvert > 0) {
186 xo << glue << counts.copyConvert << " copy convert";
187 glue = ", ";
188 }
189 if (counts.moveConvert > 0) {
190 xo << glue << counts.moveConvert << " move convert";
191 glue = ", ";
192 }
193 if (counts.copyAssign > 0) {
194 xo << glue << counts.copyAssign << " copy assign";
195 glue = ", ";
196 }
197 if (counts.moveAssign > 0) {
198 xo << glue << counts.moveAssign << " move assign";
199 glue = ", ";
200 }
201 if (counts.defaultConstruct > 0) {
202 xo << glue << counts.defaultConstruct << " default construct";
203 glue = ", ";
204 }
205 if (counts.destroyed > 0) {
206 xo << glue << counts.destroyed << " destroyed";
207 glue = ", ";
208 }
209 xo << "]";
210 return xo;
211}
212
213thread_local Counts sumCounts{};
214
215template <int Tag>
216struct Tracked {
217 static_assert(Tag <= 5, "Need to extend Tracked<Tag> in F14TestUtil.h");
218
219 static thread_local Counts counts;
220
221 uint64_t val_;
222
223 Tracked() : val_{0} {
224 sumCounts.defaultConstruct++;
225 counts.defaultConstruct++;
226 }
227 /* implicit */ Tracked(uint64_t const& val) : val_{val} {
228 sumCounts.copyConvert++;
229 counts.copyConvert++;
230 }
231 /* implicit */ Tracked(uint64_t&& val) : val_{val} {
232 sumCounts.moveConvert++;
233 counts.moveConvert++;
234 }
235 Tracked(Tracked const& rhs) : val_{rhs.val_} {
236 sumCounts.copyConstruct++;
237 counts.copyConstruct++;
238 }
239 Tracked(Tracked&& rhs) noexcept : val_{rhs.val_} {
240 sumCounts.moveConstruct++;
241 counts.moveConstruct++;
242 }
243 Tracked& operator=(Tracked const& rhs) {
244 val_ = rhs.val_;
245 sumCounts.copyAssign++;
246 counts.copyAssign++;
247 return *this;
248 }
249 Tracked& operator=(Tracked&& rhs) noexcept {
250 val_ = rhs.val_;
251 sumCounts.moveAssign++;
252 counts.moveAssign++;
253 return *this;
254 }
255
256 template <int T>
257 /* implicit */ Tracked(Tracked<T> const& rhs) : val_{rhs.val_} {
258 sumCounts.copyConvert++;
259 counts.copyConvert++;
260 }
261
262 template <int T>
263 /* implicit */ Tracked(Tracked<T>&& rhs) : val_{rhs.val_} {
264 sumCounts.moveConvert++;
265 counts.moveConvert++;
266 }
267
268 ~Tracked() {
269 sumCounts.destroyed++;
270 counts.destroyed++;
271 }
272
273 bool operator==(Tracked const& rhs) const {
274 return val_ == rhs.val_;
275 }
276 bool operator!=(Tracked const& rhs) const {
277 return !(*this == rhs);
278 }
279};
280
281template <int Tag>
282struct TransparentTrackedHash {
283 using is_transparent = void;
284
285 size_t operator()(Tracked<Tag> const& tracked) const {
286 return tracked.val_ ^ Tag;
287 }
288 size_t operator()(uint64_t v) const {
289 return v ^ Tag;
290 }
291};
292
293template <int Tag>
294struct TransparentTrackedEqual {
295 using is_transparent = void;
296
297 uint64_t unwrap(Tracked<Tag> const& v) const {
298 return v.val_;
299 }
300 uint64_t unwrap(uint64_t v) const {
301 return v;
302 }
303
304 template <typename A, typename B>
305 bool operator()(A const& lhs, B const& rhs) const {
306 return unwrap(lhs) == unwrap(rhs);
307 }
308};
309
310template <>
311thread_local Counts Tracked<0>::counts{};
312template <>
313thread_local Counts Tracked<1>::counts{};
314template <>
315thread_local Counts Tracked<2>::counts{};
316template <>
317thread_local Counts Tracked<3>::counts{};
318template <>
319thread_local Counts Tracked<4>::counts{};
320template <>
321thread_local Counts Tracked<5>::counts{};
322
323thread_local size_t testAllocatedMemorySize{0};
324thread_local size_t testAllocatedBlockCount{0};
325thread_local size_t testAllocationCount{0};
326thread_local size_t testAllocationMaxCount{
327 std::numeric_limits<std::size_t>::max()};
328
329inline void limitTestAllocations(std::size_t allocationsBeforeException = 0) {
330 testAllocationMaxCount = testAllocationCount + allocationsBeforeException;
331}
332
333inline void unlimitTestAllocations() {
334 testAllocationMaxCount = std::numeric_limits<std::size_t>::max();
335}
336
337inline void resetTracking() {
338 sumCounts = Counts{};
339 Tracked<0>::counts = Counts{};
340 Tracked<1>::counts = Counts{};
341 Tracked<2>::counts = Counts{};
342 Tracked<3>::counts = Counts{};
343 Tracked<4>::counts = Counts{};
344 Tracked<5>::counts = Counts{};
345 testAllocatedMemorySize = 0;
346 testAllocatedBlockCount = 0;
347 testAllocationCount = 0;
348 testAllocationMaxCount = std::numeric_limits<std::size_t>::max();
349}
350
351template <class T>
352class SwapTrackingAlloc {
353 public:
354 using Alloc = std::allocator<T>;
355 using value_type = typename Alloc::value_type;
356
357 using pointer = typename Alloc::pointer;
358 using const_pointer = typename Alloc::const_pointer;
359 using reference = typename Alloc::reference;
360 using const_reference = typename Alloc::const_reference;
361 using size_type = typename Alloc::size_type;
362
363 using propagate_on_container_swap = std::true_type;
364 using propagate_on_container_copy_assignment = std::true_type;
365 using propagate_on_container_move_assignment = std::true_type;
366
367 SwapTrackingAlloc() {}
368
369 template <class U>
370 SwapTrackingAlloc(SwapTrackingAlloc<U> const& other) noexcept
371 : a_(other.a_), t_(other.t_) {}
372
373 template <class U>
374 SwapTrackingAlloc& operator=(SwapTrackingAlloc<U> const& other) noexcept {
375 a_ = other.a_;
376 t_ = other.t_;
377 return *this;
378 }
379
380 template <class U>
381 SwapTrackingAlloc(SwapTrackingAlloc<U>&& other) noexcept
382 : a_(std::move(other.a_)), t_(std::move(other.t_)) {}
383
384 template <class U>
385 SwapTrackingAlloc& operator=(SwapTrackingAlloc<U>&& other) noexcept {
386 a_ = std::move(other.a_);
387 t_ = std::move(other.t_);
388 return *this;
389 }
390
391 T* allocate(size_t n) {
392 if (testAllocationCount >= testAllocationMaxCount) {
393 throw std::bad_alloc();
394 }
395 ++testAllocationCount;
396 testAllocatedMemorySize += n * sizeof(T);
397 ++testAllocatedBlockCount;
398 std::size_t extra =
399 std::max<std::size_t>(1, sizeof(std::size_t) / sizeof(T));
400 T* p = a_.allocate(extra + n);
401 std::memcpy(p, &n, sizeof(std::size_t));
402 return p + extra;
403 }
404 void deallocate(T* p, size_t n) {
405 testAllocatedMemorySize -= n * sizeof(T);
406 --testAllocatedBlockCount;
407 std::size_t extra =
408 std::max<std::size_t>(1, sizeof(std::size_t) / sizeof(T));
409 std::size_t check;
410 std::memcpy(&check, p - extra, sizeof(std::size_t));
411 FOLLY_SAFE_CHECK(check == n, "");
412 a_.deallocate(p - extra, n + extra);
413 }
414
415 private:
416 std::allocator<T> a_;
417 folly::f14::Tracked<0> t_;
418
419 template <class U>
420 friend class SwapTrackingAlloc;
421};
422
423template <class T>
424void swap(SwapTrackingAlloc<T>&, SwapTrackingAlloc<T>&) {
425 // For argument dependent lookup:
426 // This function will be called if the custom swap functions of F14 containers
427 // are used. Otherwise, std::swap() will do 1 move construct and 2 move
428 // assigns which will get tracked by t_.
429}
430
431template <class T1, class T2>
432bool operator==(SwapTrackingAlloc<T1> const&, SwapTrackingAlloc<T2> const&) {
433 return true;
434}
435
436template <class T1, class T2>
437bool operator!=(SwapTrackingAlloc<T1> const&, SwapTrackingAlloc<T2> const&) {
438 return false;
439}
440
441std::ostream& operator<<(std::ostream& xo, F14TableStats const& stats) {
442 using f14::Histo;
443
444 xo << "{ " << std::endl;
445 xo << " policy: "
446#if FOLLY_HAS_RTTI
447 << folly::demangle(stats.policy)
448#else
449 << "unknown (RTTI not availabe)"
450#endif
451 << std::endl;
452 xo << " size: " << stats.size << std::endl;
453 xo << " valueSize: " << stats.valueSize << std::endl;
454 xo << " bucketCount: " << stats.bucketCount << std::endl;
455 xo << " chunkCount: " << stats.chunkCount << std::endl;
456 xo << " chunkOccupancyHisto" << Histo{stats.chunkOccupancyHisto}
457 << std::endl;
458 xo << " chunkOutboundOverflowHisto"
459 << Histo{stats.chunkOutboundOverflowHisto} << std::endl;
460 xo << " chunkHostedOverflowHisto" << Histo{stats.chunkHostedOverflowHisto}
461 << std::endl;
462 xo << " keyProbeLengthHisto" << Histo{stats.keyProbeLengthHisto}
463 << std::endl;
464 xo << " missProbeLengthHisto" << Histo{stats.missProbeLengthHisto}
465 << std::endl;
466 xo << " totalBytes: " << stats.totalBytes << std::endl;
467 xo << " valueBytes: " << (stats.size * stats.valueSize) << std::endl;
468 xo << " overheadBytes: " << stats.overheadBytes << std::endl;
469 if (stats.size > 0) {
470 xo << " overheadBytesPerKey: "
471 << (static_cast<double>(stats.overheadBytes) /
472 static_cast<double>(stats.size))
473 << std::endl;
474 }
475 xo << "}";
476 return xo;
477}
478
479template <class T>
480class GenericAlloc {
481 public:
482 using value_type = T;
483
484 using pointer = T*;
485 using const_pointer = T const*;
486 using reference = T&;
487 using const_reference = T const&;
488 using size_type = std::size_t;
489
490 using propagate_on_container_swap = std::true_type;
491 using propagate_on_container_copy_assignment = std::true_type;
492 using propagate_on_container_move_assignment = std::true_type;
493
494 using AllocBytesFunc = folly::Function<void*(std::size_t)>;
495 using DeallocBytesFunc = folly::Function<void(void*, std::size_t)>;
496
497 GenericAlloc() = delete;
498
499 template <typename A, typename D>
500 GenericAlloc(A&& alloc, D&& dealloc)
501 : alloc_{std::make_shared<AllocBytesFunc>(std::forward<A>(alloc))},
502 dealloc_{std::make_shared<DeallocBytesFunc>(std::forward<D>(dealloc))} {
503 }
504
505 template <class U>
506 GenericAlloc(GenericAlloc<U> const& other) noexcept
507 : alloc_{other.alloc_}, dealloc_{other.dealloc_} {}
508
509 template <class U>
510 GenericAlloc& operator=(GenericAlloc<U> const& other) noexcept {
511 alloc_ = other.alloc_;
512 dealloc_ = other.dealloc_;
513 return *this;
514 }
515
516 template <class U>
517 GenericAlloc(GenericAlloc<U>&& other) noexcept
518 : alloc_(std::move(other.alloc_)), dealloc_(std::move(other.dealloc_)) {}
519
520 template <class U>
521 GenericAlloc& operator=(GenericAlloc<U>&& other) noexcept {
522 alloc_ = std::move(other.alloc_);
523 dealloc_ = std::move(other.dealloc_);
524 return *this;
525 }
526
527 T* allocate(size_t n) {
528 return static_cast<T*>((*alloc_)(n * sizeof(T)));
529 }
530 void deallocate(T* p, size_t n) {
531 (*dealloc_)(static_cast<void*>(p), n * sizeof(T));
532 }
533
534 template <typename U>
535 bool operator==(GenericAlloc<U> const& rhs) const {
536 return alloc_ == rhs.alloc_;
537 }
538
539 template <typename U>
540 bool operator!=(GenericAlloc<U> const& rhs) const {
541 return !(*this == rhs);
542 }
543
544 private:
545 std::shared_ptr<AllocBytesFunc> alloc_;
546 std::shared_ptr<DeallocBytesFunc> dealloc_;
547
548 template <class U>
549 friend class GenericAlloc;
550};
551
552template <typename T>
553class GenericEqual {
554 public:
555 using EqualFunc = folly::Function<bool(T const&, T const&)>;
556
557 GenericEqual() = delete;
558
559 template <typename E>
560 GenericEqual(E&& equal)
561 : equal_{std::make_shared<EqualFunc>(std::forward<E>(equal))} {}
562
563 bool operator()(T const& lhs, T const& rhs) const {
564 return (*equal_)(lhs, rhs);
565 }
566
567 private:
568 std::shared_ptr<EqualFunc> equal_;
569};
570
571template <typename T>
572class GenericHasher {
573 public:
574 using HasherFunc = folly::Function<std::size_t(T const&)>;
575
576 GenericHasher() = delete;
577
578 template <typename H>
579 GenericHasher(H&& hasher)
580 : hasher_{std::make_shared<HasherFunc>(std::forward<H>(hasher))} {}
581
582 std::size_t operator()(T const& val) const {
583 return (*hasher_)(val);
584 }
585
586 private:
587 std::shared_ptr<HasherFunc> hasher_;
588};
589
590} // namespace f14
591} // namespace folly
592
593namespace std {
594template <>
595struct hash<folly::f14::MoveOnlyTestInt> {
596 std::size_t operator()(folly::f14::MoveOnlyTestInt const& val) const {
597 return val.x;
598 }
599};
600
601template <int Tag>
602struct hash<folly::f14::Tracked<Tag>> {
603 size_t operator()(folly::f14::Tracked<Tag> const& tracked) const {
604 return tracked.val_ ^ Tag;
605 }
606};
607
608} // namespace std
609