11a62147b7d49e292d63b629e4848bb3322fe433
[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 s the number of hash table buckets
172      * @param l the number of locks in the hash table
173      */
174     HashTable(EPStats& st,
175               std::unique_ptr<AbstractStoredValueFactory> svFactory,
176               size_t s = 0,
177               size_t l = 0);
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      * Set the default number of buckets.
497      */
498     static void setDefaultNumBuckets(size_t);
499
500     /**
501      * Set the default number of locks.
502      */
503     static void setDefaultNumLocks(size_t);
504
505     /**
506      * Get the max deleted revision seqno seen so far.
507      */
508     uint64_t getMaxDeletedRevSeqno() const {
509         return maxDeletedRevSeqno.load();
510     }
511
512     /**
513      * Set the max deleted seqno (required during warmup).
514      */
515     void setMaxDeletedRevSeqno(const uint64_t seqno) {
516         maxDeletedRevSeqno.store(seqno);
517     }
518
519     /**
520      * Update maxDeletedRevSeqno to a (possibly) new value.
521      */
522     void updateMaxDeletedRevSeqno(const uint64_t seqno) {
523         atomic_setIfBigger(maxDeletedRevSeqno, seqno);
524     }
525
526     /**
527      * Eject an item meta data and value from memory.
528      * @param vptr the reference to the pointer to the StoredValue instance.
529      *             This is passed as a reference as it may be modified by this
530      *             function (see note below).
531      * @param policy item eviction policy
532      * @return true if an item is ejected.
533      *
534      * NOTE: Upon a successful ejection (and if full eviction is enabled)
535      *       the StoredValue will be deleted, therefore it is *not* safe to
536      *       access vptr after calling this function if it returned true.
537      */
538     bool unlocked_ejectItem(StoredValue*& vptr, item_eviction_policy_t policy);
539
540     /**
541      * Restore the value for the item.
542      * Assumes that HT bucket lock is grabbed.
543      *
544      * @param htLock Hash table lock that must be held
545      * @param itm the item to be restored
546      * @param v corresponding StoredValue
547      *
548      * @return true if restored; else false
549      */
550     bool unlocked_restoreValue(const std::unique_lock<std::mutex>& htLock,
551                                const Item& itm,
552                                StoredValue& v);
553
554     /**
555      * Restore the metadata of of a temporary item upon completion of a
556      * background fetch.
557      * Assumes that HT bucket lock is grabbed.
558      *
559      * @param htLock Hash table lock that must be held
560      * @param itm the Item whose metadata is being restored
561      * @param v corresponding StoredValue
562      */
563     void unlocked_restoreMeta(const std::unique_lock<std::mutex>& htLock,
564                               const Item& itm,
565                               StoredValue& v);
566
567     /**
568      * Releases an item(StoredValue) in the hash table, but does not delete it.
569      * It will pass out the removed item to the caller who can decide whether to
570      * delete it or not.
571      * Once removed the item will not be found if we look in the HT later, even
572      * if the item is not deleted. Hence the deletion of this
573      * removed StoredValue must be handled by another (maybe calling) module.
574      * Assumes that the hash bucket lock is already held.
575      *
576      * @param hbl HashBucketLock that must be held
577      * @param key the key to delete
578      *
579      * @return the StoredValue that is removed from the HT
580      */
581     StoredValue::UniquePtr unlocked_release(const HashBucketLock& hbl,
582                                                   const DocKey& key);
583
584     std::atomic<uint64_t>     maxDeletedRevSeqno;
585     std::atomic<size_t>       numTotalItems;
586     cb::NonNegativeCounter<size_t> numNonResidentItems;
587     cb::NonNegativeCounter<size_t> numDeletedItems;
588     std::array<cb::NonNegativeCounter<size_t>, mcbp::datatype::highest + 1>
589             datatypeCounts;
590     std::atomic<size_t>       numEjects;
591     //! Memory consumed by items in this hashtable.
592     std::atomic<size_t>       memSize;
593     //! Cache size.
594     std::atomic<size_t>       cacheSize;
595     //! Meta-data size.
596     std::atomic<size_t>       metaDataMemory;
597
598 private:
599     // The container for actually holding the StoredValues.
600     using table_type = std::vector<StoredValue::UniquePtr>;
601
602     friend class StoredValue;
603
604     inline bool isActive() const { return activeState; }
605     inline void setActiveState(bool newv) { activeState = newv; }
606
607     std::atomic<size_t> size;
608     size_t               n_locks;
609     table_type values;
610     std::mutex               *mutexes;
611     EPStats&             stats;
612     std::unique_ptr<AbstractStoredValueFactory> valFact;
613     std::atomic<size_t>       visitors;
614     cb::NonNegativeCounter<size_t> numItems;
615     std::atomic<size_t>       numResizes;
616     std::atomic<size_t>       numTempItems;
617     bool                 activeState;
618
619     static size_t                 defaultNumBuckets;
620     static size_t                 defaultNumLocks;
621
622     int getBucketForHash(int h) {
623         return abs(h % static_cast<int>(size));
624     }
625
626     inline size_t mutexForBucket(size_t bucket_num) {
627         if (!isActive()) {
628             throw std::logic_error("HashTable::mutexForBucket: Cannot call on a "
629                     "non-active object");
630         }
631         return bucket_num % n_locks;
632     }
633
634     std::unique_ptr<Item> getRandomKeyFromSlot(int slot);
635
636     /** Searches for the first element in the specified hashChain which matches
637      * predicate p, and unlinks it from the chain.
638      *
639      * @param chain Linked list of StoredValues to scan.
640      * @param p Predicate to test each element against.
641      *          The signature of the predicate function should be equivalent
642      *          to the following:
643      *               bool pred(const StoredValue* a);
644      *
645      * @return The removed element, or NULL if no matching element was found.
646      */
647     template <typename Pred>
648     StoredValue::UniquePtr hashChainRemoveFirst(StoredValue::UniquePtr& chain,
649                                                 Pred p) {
650         if (p(chain.get())) {
651             // Head element:
652             auto removed = std::move(chain);
653             chain = std::move(removed->next);
654             return removed;
655         }
656
657         // Not head element, start searching.
658         for (StoredValue::UniquePtr* curr = &chain; curr->get()->next;
659              curr = &curr->get()->next) {
660             if (p(curr->get()->next.get())) {
661                 // next element matches predicate - splice it out of the list.
662                 auto removed = std::move(curr->get()->next);
663                 curr->get()->next = std::move(removed->next);
664                 return removed;
665             }
666         }
667
668         // No match found.
669         return nullptr;
670     }
671
672     DISALLOW_COPY_AND_ASSIGN(HashTable);
673 };
674
675 /**
676  * Base class for visiting a hash table.
677  */
678 class HashTableVisitor {
679 public:
680     virtual ~HashTableVisitor() {}
681
682     /**
683      * Visit an individual item within a hash table. Note that the item is
684      * locked while visited (the appropriate hashTable lock is held).
685      *
686      * @param v a pointer to a value in the hash table
687      */
688     virtual void visit(const HashTable::HashBucketLock& lh, StoredValue* v) = 0;
689
690     /**
691      * True if the visiting should continue.
692      *
693      * This is called periodically to ensure the visitor still wants
694      * to visit items.
695      */
696     virtual bool shouldContinue() { return true; }
697 };
698
699 /**
700  * Base class for visiting a hash table with pause/resume support.
701  */
702 class PauseResumeHashTableVisitor {
703 public:
704     /**
705      * Visit an individual item within a hash table.
706      *
707      * @param v a pointer to a value in the hash table.
708      * @return True if visiting should continue, otherwise false.
709      */
710     virtual bool visit(StoredValue& v) = 0;
711 };
712
713 /**
714  * Hash table visitor that reports the depth of each hashtable bucket.
715  */
716 class HashTableDepthVisitor {
717 public:
718     virtual ~HashTableDepthVisitor() {}
719
720     /**
721      * Called once for each hashtable bucket with its depth.
722      *
723      * @param bucket the index of the hashtable bucket
724      * @param depth the number of entries in this hashtable bucket
725      * @param mem counted memory used by this hash table
726      */
727     virtual void visit(int bucket, int depth, size_t mem) = 0;
728 };
729
730 /**
731  * Hash table visitor that finds the min and max bucket depths.
732  */
733 class HashTableDepthStatVisitor : public HashTableDepthVisitor {
734 public:
735
736     HashTableDepthStatVisitor()
737         : depthHisto(GrowingWidthGenerator<unsigned int>(1, 1, 1.3), 10),
738           size(0),
739           memUsed(0),
740           min(-1),
741           max(0) {}
742
743     void visit(int bucket, int depth, size_t mem) {
744         (void)bucket;
745         // -1 is a special case for min.  If there's a value other than
746         // -1, we prefer that.
747         min = std::min(min == -1 ? depth : min, depth);
748         max = std::max(max, depth);
749         depthHisto.add(depth);
750         size += depth;
751         memUsed += mem;
752     }
753
754     Histogram<unsigned int> depthHisto;
755     size_t                  size;
756     size_t                  memUsed;
757     int                     min;
758     int                     max;
759 };
760
761 /**
762  * Track the current number of hashtable visitors.
763  *
764  * This class is a pretty generic counter holder that increments on
765  * entry and decrements on return providing RAII guarantees around an
766  * atomic counter.
767  */
768 class VisitorTracker {
769 public:
770
771     /**
772      * Mark a visitor as visiting.
773      *
774      * @param c the counter that should be incremented (and later
775      * decremented).
776      */
777     explicit VisitorTracker(std::atomic<size_t> *c) : counter(c) {
778         counter->fetch_add(1);
779     }
780     ~VisitorTracker() {
781         counter->fetch_sub(1);
782     }
783 private:
784     std::atomic<size_t> *counter;
785 };