f9eea91b9b0948b7cd27db8494ea627ebbae78f4
[ep-engine.git] / src / hash_table.h
1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2016 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17
18 #pragma once
19
20 #include "config.h"
21 #include "storeddockey.h"
22 #include "stored-value.h"
23 #include <platform/non_negative_counter.h>
24
25 class AbstractStoredValueFactory;
26 class HashTableStatVisitor;
27 class HashTableVisitor;
28 class HashTableDepthVisitor;
29 class PauseResumeHashTableVisitor;
30
31 /**
32  * Mutation types as returned by store commands.
33  */
34 enum class MutationStatus : uint16_t {
35     NotFound, //!< The item was not found for update
36     InvalidCas, //!< The wrong CAS identifier was sent for a CAS update
37     WasClean, //!< The item was clean before this mutation
38     WasDirty, //!< This item was already dirty before this mutation
39     IsLocked, //!< The item is locked and can't be updated.
40     NoMem, //!< Insufficient memory to store this item.
41     NeedBgFetch //!< Require a bg fetch to process SET op
42 };
43
44 /**
45  * Result from add operation.
46  */
47 enum class AddStatus : uint16_t {
48     Success, //!< Add was successful.
49     NoMem, //!< No memory for operation
50     Exists, //!< Did not update -- item exists with this key
51     UnDel, //!< Undeletes an existing dirty item
52     AddTmpAndBgFetch, //!< Create a tmp item and schedule a bg metadata fetch
53     BgFetch //!< Schedule a bg metadata fetch to process ADD op
54 };
55
56 /**
57  * A container of StoredValue instances.
58  *
59  * The HashTable class is an unordered, associative array which maps
60  * StoredDocKeys to StoredValue.
61  *
62  * It supports a limited degree of concurrent access - the underlying
63  * HashTable buckets are guarded by N ht_locks; where N is typically of the
64  * order of the number of CPUs. Essentially ht bucket B is guarded by
65  * mutex B mod N.
66  *
67  * StoredValue objects can have their value (Blob object) ejected, making the
68  * value non-resident. Such StoredValues are still in the HashTable, and their
69  * metadata (CAS, revSeqno, bySeqno, etc) is still accessible, but the value
70  * cannot be accessed until it is fetched from disk. This is value eviction.
71  *
72  * Additionally, we can eject the whole StoredValue from the HashTable.
73  * We no longer know if the item even exists from the HashTable, and need to go
74  * to disk to definitively know if it exists or not. Note that even though the
75  * HashTable has no direct knowledge of the item now, it /does/ track the total
76  * number of items which exist but are not resident (see numNonResidentItems).
77  * This is full eviction.
78  *
79  * The HashTable can hold StoredValues which are either 'valid' (i.e. represent
80  * the current state of that key), or which are logically deleted. Typically
81  * StoredValues which are deleted are only held in the HashTable for a short
82  * period of time - until the deletion is recorded on disk by the Flusher, at
83  * which point they are removed from the HashTable by PersistenceCallback (we
84  * don't want to unnecessarily spend memory on items which have been deleted).
85  */
86 class HashTable {
87 public:
88
89     /**
90      * Represents a position within the hashtable.
91      *
92      * Currently opaque (and constant), clients can pass them around but
93      * cannot reposition the iterator.
94      */
95     class Position {
96     public:
97         // Allow default construction positioned at the start,
98         // but nothing else.
99         Position() : ht_size(0), lock(0), hash_bucket(0) {}
100
101         bool operator==(const Position& other) const {
102             return (ht_size == other.ht_size) &&
103                    (lock == other.lock) &&
104                    (hash_bucket == other.hash_bucket);
105         }
106
107         bool operator!=(const Position& other) const {
108             return ! (*this == other);
109         }
110
111     private:
112         Position(size_t ht_size_, int lock_, int hash_bucket_)
113           : ht_size(ht_size_),
114             lock(lock_),
115             hash_bucket(hash_bucket_) {}
116
117         // Size of the hashtable when the position was created.
118         size_t ht_size;
119         // Lock ID we are up to.
120         size_t lock;
121         // hash bucket ID (under the given lock) we are up to.
122         size_t hash_bucket;
123
124         friend class HashTable;
125         friend std::ostream& operator<<(std::ostream& os, const Position& pos);
126     };
127
128     /**
129      * Represents a locked hash bucket that provides RAII semantics for the lock
130      *
131      * A simple container which holds a lock and the bucket_num of the
132      * hashtable bucket it has the lock for.
133      */
134     class HashBucketLock {
135     public:
136         HashBucketLock()
137             : bucketNum(-1) {}
138
139         HashBucketLock(int bucketNum, std::mutex& mutex)
140             : bucketNum(bucketNum), htLock(mutex) {
141         }
142
143         HashBucketLock(HashBucketLock&& other)
144             : bucketNum(other.bucketNum), htLock(std::move(other.htLock)) {
145         }
146
147         HashBucketLock(const HashBucketLock& other) = delete;
148
149         int getBucketNum() const {
150             return bucketNum;
151         }
152
153         const std::unique_lock<std::mutex>& getHTLock() const {
154             return htLock;
155         }
156
157         std::unique_lock<std::mutex>& getHTLock() {
158             return htLock;
159         }
160
161     private:
162         int bucketNum;
163         std::unique_lock<std::mutex> htLock;
164     };
165
166     /**
167      * Create a HashTable.
168      *
169      * @param st the global stats reference
170      * @param svFactory Factory to use for constructing stored values
171      * @param initialSize the number of hash table buckets to initially create.
172      * @param locks the number of locks in the hash table
173      */
174     HashTable(EPStats& st,
175               std::unique_ptr<AbstractStoredValueFactory> svFactory,
176               size_t initialSize,
177               size_t locks);
178
179     ~HashTable();
180
181     size_t memorySize() {
182         return sizeof(HashTable)
183             + (size * sizeof(StoredValue*))
184             + (n_locks * sizeof(std::mutex));
185     }
186
187     /**
188      * Get the number of hash table buckets this hash table has.
189      */
190     size_t getSize(void) { return size; }
191
192     /**
193      * Get the number of locks in this hash table.
194      */
195     size_t getNumLocks(void) { return n_locks; }
196
197     /**
198      * Get the number of in-memory non-resident and resident items within
199      * this hash table.
200      */
201     size_t getNumInMemoryItems() const {
202         return numItems;
203     }
204
205     /**
206      * Get the number of deleted items in the hash table.
207      */
208     size_t getNumDeletedItems() const {
209         return numDeletedItems;
210     }
211
212     /**
213      * Get the number of in-memory non-resident items within this hash table.
214      */
215     size_t getNumInMemoryNonResItems() const { return numNonResidentItems; }
216
217     /**
218      * Get the number of non-resident and resident items managed by
219      * this hash table. Includes items marked as deleted.
220      * Note that this will be equal to numItems if
221      * VALUE_ONLY_EVICTION is chosen as a cache management.
222      */
223     size_t getNumItems(void) const {
224         return numTotalItems;
225     }
226
227     void setNumTotalItems(size_t totalItems) {
228         numTotalItems = totalItems;
229     }
230
231     void decrNumItems() {
232         --numItems;
233     }
234
235     void decrNumTotalItems() {
236         --numTotalItems;
237     }
238
239     void decrNumNonResidentItems() {
240         --numNonResidentItems;
241     }
242
243     /**
244      * Get the number of items whose values are ejected from this hash table.
245      */
246     size_t getNumEjects(void) { return numEjects; }
247
248     /**
249      * Get the total item memory size in this hash table.
250      */
251     size_t getItemMemory(void) { return memSize; }
252
253     /**
254      * Clear the hash table.
255      *
256      * @param deactivate true when this hash table is being destroyed completely
257      */
258     void clear(bool deactivate = false);
259
260     /**
261      * Get the number of times this hash table has been resized.
262      */
263     size_t getNumResizes() { return numResizes; }
264
265     /**
266      * Get the number of temp. items within this hash table.
267      */
268     size_t getNumTempItems(void) { return numTempItems; }
269
270     /**
271      * Automatically resize to fit the current data.
272      */
273     void resize();
274
275     /**
276      * Resize to the specified size.
277      */
278     void resize(size_t to);
279
280     /**
281      * Find the item with the given key.
282      *
283      * @param key the key to find
284      * @param trackReference whether to track the reference or not
285      * @param wantsDeleted whether a deleted value needs to be returned
286      *                     or not
287      * @return a pointer to a StoredValue -- NULL if not found
288      */
289     StoredValue* find(const DocKey& key,
290                       TrackReference trackReference,
291                       WantsDeleted wantsDeleted);
292
293     /**
294      * Find a resident item
295      *
296      * @param rnd a randomization input
297      * @return an item -- NULL if not fount
298      */
299     std::unique_ptr<Item> getRandomKey(long rnd);
300
301     /**
302      * Set an Item into the this hashtable
303      *
304      * @param val the Item to store
305      *
306      * @return a result indicating the status of the store
307      */
308     MutationStatus set(Item& val);
309
310     /**
311      * Updates an existing StoredValue in the HT.
312      * Assumes that HT bucket lock is grabbed.
313      *
314      * @param htLock Hash table lock that must be held.
315      * @param v Reference to the StoredValue to be updated.
316      * @param itm Item to be updated.
317      *
318      * @return Result indicating the status of the operation
319      */
320     MutationStatus unlocked_updateStoredValue(
321             const std::unique_lock<std::mutex>& htLock,
322             StoredValue& v,
323             const Item& itm);
324
325     /**
326      * Adds a new StoredValue in the HT.
327      * Assumes that HT bucket lock is grabbed.
328      *
329      * @param hbl Hash table bucket lock that must be held.
330      * @param itm Item to be added.
331      *
332      * @return Ptr of the StoredValue added. This function always succeeds and
333      *         returns non-null ptr
334      */
335     StoredValue* unlocked_addNewStoredValue(const HashBucketLock& hbl,
336                                             const Item& itm);
337
338     /**
339      * Replaces a StoredValue in the HT with its copy, and releases the
340      * ownership of the StoredValue.
341      * We need this when we want to update (or soft delete) the StoredValue
342      * without an item for the update (or soft delete) and still keep around
343      * stale StoredValue.
344      * Assumes that HT bucket lock is grabbed.
345      *
346      * @param hbl Hash table bucket lock that must be held.
347      * @param vToCopy StoredValue to be replaced by its copy.
348      *
349      * @return Ptr of the copy of the StoredValue added. This is owned by the
350      *         hash table.
351      *         UniquePtr to the StoredValue replaced by its copy. This is NOT
352      *         owned by the hash table anymore.
353      */
354     std::pair<StoredValue*, StoredValue::UniquePtr> unlocked_replaceByCopy(
355             const HashBucketLock& hbl, const StoredValue& vToCopy);
356     /**
357      * Logically (soft) delete the item in ht
358      * Assumes that HT bucket lock is grabbed.
359      * Also assumes that v is in the hash table.
360      *
361      * @param htLock Hash table lock that must be held
362      * @param v Reference to the StoredValue to be soft deleted
363      * @param onlyMarkDeleted indicates if we must reset the StoredValue or
364      *                        just mark deleted
365      */
366     void unlocked_softDelete(const std::unique_lock<std::mutex>& htLock,
367                              StoredValue& v,
368                              bool onlyMarkDeleted);
369
370     /**
371      * Find an item within a specific bucket assuming you already
372      * locked the bucket.
373      *
374      * @param key the key of the item to find
375      * @param bucket_num the bucket number
376      * @param wantsDeleted true if soft deleted items should be returned
377      *
378      * @return a pointer to a StoredValue -- NULL if not found
379      */
380     StoredValue* unlocked_find(const DocKey& key,
381                                int bucket_num,
382                                WantsDeleted wantsDeleted,
383                                TrackReference trackReference);
384
385     /**
386      * Get a lock holder holding a lock for the given bucket
387      *
388      * @param bucket the bucket number to lock
389      * @return HashBucektLock which contains a lock and the hash bucket number
390      */
391     inline HashBucketLock getLockedBucket(int bucket) {
392         return HashBucketLock(bucket, mutexes[mutexForBucket(bucket)]);
393     }
394
395     /**
396      * Get a lock holder holding a lock for the bucket for the given
397      * hash.
398      *
399      * @param h the input hash
400      * @return HashBucketLock which contains a lock and the hash bucket number
401      */
402     inline HashBucketLock getLockedBucketForHash(int h) {
403         while (true) {
404             if (!isActive()) {
405                 throw std::logic_error("HashTable::getLockedBucket: "
406                         "Cannot call on a non-active object");
407             }
408             int bucket = getBucketForHash(h);
409             HashBucketLock rv(bucket, mutexes[mutexForBucket(bucket)]);
410             if (bucket == getBucketForHash(h)) {
411                 return rv;
412             }
413         }
414     }
415
416     /**
417      * Get a lock holder holding a lock for the bucket for the hash of
418      * the given key.
419      *
420      * @param s the key
421      * @return HashBucektLock which contains a lock and the hash bucket number
422      */
423     inline HashBucketLock getLockedBucket(const DocKey& key) {
424         if (!isActive()) {
425             throw std::logic_error("HashTable::getLockedBucket: Cannot call on a "
426                     "non-active object");
427         }
428         return getLockedBucketForHash(key.hash());
429     }
430
431     /**
432      * Delete a key from the cache without trying to lock the cache first
433      * (Please note that you <b>MUST</b> acquire the mutex before calling
434      * this function!!!
435      *
436      * @param hbl HashBucketLock that must be held
437      * @param key the key to delete
438      */
439     void unlocked_del(const HashBucketLock& hbl, const DocKey& key);
440
441     /**
442      * Visit all items within this hashtable.
443      */
444     void visit(HashTableVisitor &visitor);
445
446     /**
447      * Visit all items within this call with a depth visitor.
448      */
449     void visitDepth(HashTableDepthVisitor &visitor);
450
451     /**
452      * Visit the items in this hashtable, starting the iteration from the
453      * given startPosition and allowing the visit to be paused at any point.
454      *
455      * During visitation, the visitor object can request that the visit
456      * is stopped after the current item. The position passed to the
457      * visitor can then be used to restart visiting at the *APPROXIMATE*
458      * same position as it paused.
459      * This is approximate as hashtable locks are released when the
460      * function returns, so any changes to the hashtable may cause the
461      * visiting to restart at the slightly different place.
462      *
463      * As a consequence, *DO NOT USE THIS METHOD* if you need to guarantee
464      * that all items are visited!
465      *
466      * @param visitor The visitor object to use.
467      * @param start_pos At what position to start in the hashtable.
468      * @return The final HashTable position visited; equal to
469      *         HashTable::end() if all items were visited otherwise the
470      *         position to resume from.
471      */
472     Position pauseResumeVisit(PauseResumeHashTableVisitor& visitor,
473                               Position& start_pos);
474
475     /**
476      * Return a position at the end of the hashtable. Has similar semantics
477      * as STL end() (i.e. one past the last element).
478      */
479     Position endPosition() const;
480
481     /**
482      * Get the number of buckets that should be used for initialization.
483      *
484      * @param s if 0, return the default number of buckets, else return s
485      */
486     static size_t getNumBuckets(size_t s = 0);
487
488     /**
489      * Get the number of locks that should be used for initialization.
490      *
491      * @param s if 0, return the default number of locks, else return s
492      */
493     static size_t getNumLocks(size_t s);
494
495     /**
496      * Get the max deleted revision seqno seen so far.
497      */
498     uint64_t getMaxDeletedRevSeqno() const {
499         return maxDeletedRevSeqno.load();
500     }
501
502     /**
503      * Set the max deleted seqno (required during warmup).
504      */
505     void setMaxDeletedRevSeqno(const uint64_t seqno) {
506         maxDeletedRevSeqno.store(seqno);
507     }
508
509     /**
510      * Update maxDeletedRevSeqno to a (possibly) new value.
511      */
512     void updateMaxDeletedRevSeqno(const uint64_t seqno) {
513         atomic_setIfBigger(maxDeletedRevSeqno, seqno);
514     }
515
516     /**
517      * Eject an item meta data and value from memory.
518      * @param vptr the reference to the pointer to the StoredValue instance.
519      *             This is passed as a reference as it may be modified by this
520      *             function (see note below).
521      * @param policy item eviction policy
522      * @return true if an item is ejected.
523      *
524      * NOTE: Upon a successful ejection (and if full eviction is enabled)
525      *       the StoredValue will be deleted, therefore it is *not* safe to
526      *       access vptr after calling this function if it returned true.
527      */
528     bool unlocked_ejectItem(StoredValue*& vptr, item_eviction_policy_t policy);
529
530     /**
531      * Restore the value for the item.
532      * Assumes that HT bucket lock is grabbed.
533      *
534      * @param htLock Hash table lock that must be held
535      * @param itm the item to be restored
536      * @param v corresponding StoredValue
537      *
538      * @return true if restored; else false
539      */
540     bool unlocked_restoreValue(const std::unique_lock<std::mutex>& htLock,
541                                const Item& itm,
542                                StoredValue& v);
543
544     /**
545      * Restore the metadata of of a temporary item upon completion of a
546      * background fetch.
547      * Assumes that HT bucket lock is grabbed.
548      *
549      * @param htLock Hash table lock that must be held
550      * @param itm the Item whose metadata is being restored
551      * @param v corresponding StoredValue
552      */
553     void unlocked_restoreMeta(const std::unique_lock<std::mutex>& htLock,
554                               const Item& itm,
555                               StoredValue& v);
556
557     /**
558      * Releases an item(StoredValue) in the hash table, but does not delete it.
559      * It will pass out the removed item to the caller who can decide whether to
560      * delete it or not.
561      * Once removed the item will not be found if we look in the HT later, even
562      * if the item is not deleted. Hence the deletion of this
563      * removed StoredValue must be handled by another (maybe calling) module.
564      * Assumes that the hash bucket lock is already held.
565      *
566      * @param hbl HashBucketLock that must be held
567      * @param key the key to delete
568      *
569      * @return the StoredValue that is removed from the HT
570      */
571     StoredValue::UniquePtr unlocked_release(const HashBucketLock& hbl,
572                                                   const DocKey& key);
573
574     std::atomic<uint64_t>     maxDeletedRevSeqno;
575     std::atomic<size_t>       numTotalItems;
576     cb::NonNegativeCounter<size_t> numNonResidentItems;
577     cb::NonNegativeCounter<size_t> numDeletedItems;
578     std::array<cb::NonNegativeCounter<size_t>, mcbp::datatype::highest + 1>
579             datatypeCounts;
580     std::atomic<size_t>       numEjects;
581     //! Memory consumed by items in this hashtable.
582     std::atomic<size_t>       memSize;
583     //! Cache size.
584     std::atomic<size_t>       cacheSize;
585     //! Meta-data size.
586     std::atomic<size_t>       metaDataMemory;
587
588 private:
589     // The container for actually holding the StoredValues.
590     using table_type = std::vector<StoredValue::UniquePtr>;
591
592     friend class StoredValue;
593     friend std::ostream& operator<<(std::ostream& os, const HashTable& ht);
594
595     inline bool isActive() const { return activeState; }
596     inline void setActiveState(bool newv) { activeState = newv; }
597
598     // The initial (and minimum) size of the HashTable.
599     const size_t initialSize;
600
601     std::atomic<size_t> size;
602     size_t               n_locks;
603     table_type values;
604     std::mutex               *mutexes;
605     EPStats&             stats;
606     std::unique_ptr<AbstractStoredValueFactory> valFact;
607     std::atomic<size_t>       visitors;
608     cb::NonNegativeCounter<size_t> numItems;
609     std::atomic<size_t>       numResizes;
610     std::atomic<size_t>       numTempItems;
611     bool                 activeState;
612
613     int getBucketForHash(int h) {
614         return abs(h % static_cast<int>(size));
615     }
616
617     inline size_t mutexForBucket(size_t bucket_num) {
618         if (!isActive()) {
619             throw std::logic_error("HashTable::mutexForBucket: Cannot call on a "
620                     "non-active object");
621         }
622         return bucket_num % n_locks;
623     }
624
625     std::unique_ptr<Item> getRandomKeyFromSlot(int slot);
626
627     /** Searches for the first element in the specified hashChain which matches
628      * predicate p, and unlinks it from the chain.
629      *
630      * @param chain Linked list of StoredValues to scan.
631      * @param p Predicate to test each element against.
632      *          The signature of the predicate function should be equivalent
633      *          to the following:
634      *               bool pred(const StoredValue* a);
635      *
636      * @return The removed element, or NULL if no matching element was found.
637      */
638     template <typename Pred>
639     StoredValue::UniquePtr hashChainRemoveFirst(StoredValue::UniquePtr& chain,
640                                                 Pred p) {
641         if (p(chain.get())) {
642             // Head element:
643             auto removed = std::move(chain);
644             chain = std::move(removed->getNext());
645             return removed;
646         }
647
648         // Not head element, start searching.
649         for (StoredValue::UniquePtr* curr = &chain; curr->get()->getNext();
650              curr = &curr->get()->getNext()) {
651             if (p(curr->get()->getNext().get())) {
652                 // next element matches predicate - splice it out of the list.
653                 auto removed = std::move(curr->get()->getNext());
654                 curr->get()->setNext(std::move(removed->getNext()));
655                 return removed;
656             }
657         }
658
659         // No match found.
660         return nullptr;
661     }
662
663     void clear_UNLOCKED(bool deactivate);
664
665     DISALLOW_COPY_AND_ASSIGN(HashTable);
666 };
667
668 std::ostream& operator<<(std::ostream& os, const HashTable& ht);
669
670 /**
671  * Base class for visiting a hash table.
672  */
673 class HashTableVisitor {
674 public:
675     virtual ~HashTableVisitor() {}
676
677     /**
678      * Visit an individual item within a hash table. Note that the item is
679      * locked while visited (the appropriate hashTable lock is held).
680      *
681      * @param v a pointer to a value in the hash table
682      */
683     virtual void visit(const HashTable::HashBucketLock& lh, StoredValue* v) = 0;
684
685     /**
686      * True if the visiting should continue.
687      *
688      * This is called periodically to ensure the visitor still wants
689      * to visit items.
690      */
691     virtual bool shouldContinue() { return true; }
692 };
693
694 /**
695  * Base class for visiting a hash table with pause/resume support.
696  */
697 class PauseResumeHashTableVisitor {
698 public:
699     /**
700      * Visit an individual item within a hash table.
701      *
702      * @param v a pointer to a value in the hash table.
703      * @return True if visiting should continue, otherwise false.
704      */
705     virtual bool visit(StoredValue& v) = 0;
706 };
707
708 /**
709  * Hash table visitor that reports the depth of each hashtable bucket.
710  */
711 class HashTableDepthVisitor {
712 public:
713     virtual ~HashTableDepthVisitor() {}
714
715     /**
716      * Called once for each hashtable bucket with its depth.
717      *
718      * @param bucket the index of the hashtable bucket
719      * @param depth the number of entries in this hashtable bucket
720      * @param mem counted memory used by this hash table
721      */
722     virtual void visit(int bucket, int depth, size_t mem) = 0;
723 };
724
725 /**
726  * Hash table visitor that finds the min and max bucket depths.
727  */
728 class HashTableDepthStatVisitor : public HashTableDepthVisitor {
729 public:
730
731     HashTableDepthStatVisitor()
732         : depthHisto(GrowingWidthGenerator<unsigned int>(1, 1, 1.3), 10),
733           size(0),
734           memUsed(0),
735           min(-1),
736           max(0) {}
737
738     void visit(int bucket, int depth, size_t mem) {
739         (void)bucket;
740         // -1 is a special case for min.  If there's a value other than
741         // -1, we prefer that.
742         min = std::min(min == -1 ? depth : min, depth);
743         max = std::max(max, depth);
744         depthHisto.add(depth);
745         size += depth;
746         memUsed += mem;
747     }
748
749     Histogram<unsigned int> depthHisto;
750     size_t                  size;
751     size_t                  memUsed;
752     int                     min;
753     int                     max;
754 };
755
756 /**
757  * Track the current number of hashtable visitors.
758  *
759  * This class is a pretty generic counter holder that increments on
760  * entry and decrements on return providing RAII guarantees around an
761  * atomic counter.
762  */
763 class VisitorTracker {
764 public:
765
766     /**
767      * Mark a visitor as visiting.
768      *
769      * @param c the counter that should be incremented (and later
770      * decremented).
771      */
772     explicit VisitorTracker(std::atomic<size_t> *c) : counter(c) {
773         counter->fetch_add(1);
774     }
775     ~VisitorTracker() {
776         counter->fetch_sub(1);
777     }
778 private:
779     std::atomic<size_t> *counter;
780 };