5e8c4001c01c085a50783df1e2574b23a0a7a740
[ep-engine.git] / src / hash_table.cc
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 #include "hash_table.h"
19
20 #include "stored_value_factories.h"
21
22 #include <cstring>
23
24 #ifndef DEFAULT_HT_SIZE
25 #define DEFAULT_HT_SIZE 1531
26 #endif
27
28 size_t HashTable::defaultNumBuckets = DEFAULT_HT_SIZE;
29 size_t HashTable::defaultNumLocks = 193;
30
31 static ssize_t prime_size_table[] = {
32     3, 7, 13, 23, 47, 97, 193, 383, 769, 1531, 3079, 6143, 12289, 24571, 49157,
33     98299, 196613, 393209, 786433, 1572869, 3145721, 6291449, 12582917,
34     25165813, 50331653, 100663291, 201326611, 402653189, 805306357,
35     1610612741, -1
36 };
37
38
39 std::ostream& operator<<(std::ostream& os, const HashTable::Position& pos) {
40     os << "{lock:" << pos.lock << " bucket:" << pos.hash_bucket << "/" << pos.ht_size << "}";
41     return os;
42 }
43
44 HashTable::HashTable(EPStats& st,
45                      std::unique_ptr<AbstractStoredValueFactory> svFactory,
46                      size_t s, size_t l)
47     : maxDeletedRevSeqno(0),
48       numTotalItems(0),
49       numNonResidentItems(0),
50       numDeletedItems(0),
51       datatypeCounts(),
52       numEjects(0),
53       memSize(0),
54       cacheSize(0),
55       metaDataMemory(0),
56       stats(st),
57       valFact(std::move(svFactory)),
58       visitors(0),
59       numItems(0),
60       numResizes(0),
61       numTempItems(0) {
62     size = HashTable::getNumBuckets(s);
63     n_locks = HashTable::getNumLocks(l);
64     values.resize(size);
65     mutexes = new std::mutex[n_locks];
66     activeState = true;
67 }
68
69 HashTable::~HashTable() {
70     clear(true);
71     // Wait for any outstanding visitors to finish.
72     while (visitors > 0) {
73 #ifdef _MSC_VER
74         Sleep(1);
75 #else
76         usleep(100);
77 #endif
78     }
79     delete []mutexes;
80 }
81
82 void HashTable::clear(bool deactivate) {
83     if (!deactivate) {
84         // If not deactivating, assert we're already active.
85         if (!isActive()) {
86             throw std::logic_error("HashTable::clear: Cannot call on a "
87                     "non-active object");
88         }
89     }
90     MultiLockHolder mlh(mutexes, n_locks);
91     if (deactivate) {
92         setActiveState(false);
93     }
94     size_t clearedMemSize = 0;
95     size_t clearedValSize = 0;
96     for (int i = 0; i < (int)size; i++) {
97         while (values[i]) {
98             // Take ownership of the StoredValue from the vector, update
99             // statistics and release it.
100             auto v = std::move(values[i]);
101             clearedMemSize += v->size();
102             clearedValSize += v->valuelen();
103             values[i] = std::move(v->next);
104         }
105     }
106
107     stats.currentSize.fetch_sub(clearedMemSize - clearedValSize);
108
109     datatypeCounts.fill(0);
110     numTotalItems.store(0);
111     numItems.store(0);
112     numTempItems.store(0);
113     numNonResidentItems.store(0);
114     memSize.store(0);
115     cacheSize.store(0);
116 }
117
118 static size_t distance(size_t a, size_t b) {
119     return std::max(a, b) - std::min(a, b);
120 }
121
122 static size_t nearest(size_t n, size_t a, size_t b) {
123     return (distance(n, a) < distance(b, n)) ? a : b;
124 }
125
126 static bool isCurrently(size_t size, ssize_t a, ssize_t b) {
127     ssize_t current(static_cast<ssize_t>(size));
128     return (current == a || current == b);
129 }
130
131 void HashTable::resize() {
132     size_t ni = getNumInMemoryItems();
133     int i(0);
134     size_t new_size(0);
135
136     // Figure out where in the prime table we are.
137     ssize_t target(static_cast<ssize_t>(ni));
138     for (i = 0; prime_size_table[i] > 0 && prime_size_table[i] < target; ++i) {
139         // Just looking...
140     }
141
142     if (prime_size_table[i] == -1) {
143         // We're at the end, take the biggest
144         new_size = prime_size_table[i-1];
145     } else if (prime_size_table[i] < static_cast<ssize_t>(defaultNumBuckets)) {
146         // Was going to be smaller than the configured ht_size.
147         new_size = defaultNumBuckets;
148     } else if (0 == i) {
149         new_size = prime_size_table[i];
150     }else if (isCurrently(size, prime_size_table[i-1], prime_size_table[i])) {
151         // If one of the candidate sizes is the current size, maintain
152         // the current size in order to remain stable.
153         new_size = size;
154     } else {
155         // Somewhere in the middle, use the one we're closer to.
156         new_size = nearest(ni, prime_size_table[i-1], prime_size_table[i]);
157     }
158
159     resize(new_size);
160 }
161
162 void HashTable::resize(size_t newSize) {
163     if (!isActive()) {
164         throw std::logic_error("HashTable::resize: Cannot call on a "
165                 "non-active object");
166     }
167
168     // Due to the way hashing works, we can't fit anything larger than
169     // an int.
170     if (newSize > static_cast<size_t>(std::numeric_limits<int>::max())) {
171         return;
172     }
173
174     // Don't resize to the same size, either.
175     if (newSize == size) {
176         return;
177     }
178
179     MultiLockHolder mlh(mutexes, n_locks);
180     if (visitors.load() > 0) {
181         // Do not allow a resize while any visitors are actually
182         // processing.  The next attempt will have to pick it up.  New
183         // visitors cannot start doing meaningful work (we own all
184         // locks at this point).
185         return;
186     }
187
188     // Get a place for the new items.
189     table_type newValues(newSize);
190
191     stats.memOverhead->fetch_sub(memorySize());
192     ++numResizes;
193
194     // Set the new size so all the hashy stuff works.
195     size_t oldSize = size;
196     size.store(newSize);
197
198     // Move existing records into the new space.
199     for (size_t i = 0; i < oldSize; i++) {
200         while (values[i]) {
201             // unlink the front element from the hash chain at values[i].
202             auto v = std::move(values[i]);
203             values[i] = std::move(v->next);
204
205             // And re-link it into the correct place in newValues.
206             int newBucket = getBucketForHash(v->getKey().hash());
207             v->next = std::move(newValues[newBucket]);
208             newValues[newBucket] = std::move(v);
209         }
210     }
211
212     // Finally assign the new table to values.
213     values = std::move(newValues);
214
215     stats.memOverhead->fetch_add(memorySize());
216 }
217
218 StoredValue* HashTable::find(const DocKey& key,
219                              TrackReference trackReference,
220                              WantsDeleted wantsDeleted) {
221     if (!isActive()) {
222         throw std::logic_error("HashTable::find: Cannot call on a "
223                 "non-active object");
224     }
225     HashBucketLock hbl = getLockedBucket(key);
226     return unlocked_find(key, hbl.getBucketNum(), wantsDeleted, trackReference);
227 }
228
229 std::unique_ptr<Item> HashTable::getRandomKey(long rnd) {
230     /* Try to locate a partition */
231     size_t start = rnd % size;
232     size_t curr = start;
233     std::unique_ptr<Item> ret;
234
235     do {
236         ret = getRandomKeyFromSlot(curr++);
237         if (curr == size) {
238             curr = 0;
239         }
240     } while (ret == NULL && curr != start);
241
242     return ret;
243 }
244
245 MutationStatus HashTable::set(Item& val) {
246     if (!StoredValue::hasAvailableSpace(stats, val, false)) {
247         return MutationStatus::NoMem;
248     }
249
250     HashBucketLock hbl = getLockedBucket(val.getKey());
251     StoredValue* v = unlocked_find(val.getKey(),
252                                    hbl.getBucketNum(),
253                                    WantsDeleted::Yes,
254                                    TrackReference::No);
255     if (v) {
256         return unlocked_updateStoredValue(hbl.getHTLock(), *v, val);
257     } else {
258         unlocked_addNewStoredValue(hbl, val);
259         return MutationStatus::WasClean;
260     }
261 }
262
263 MutationStatus HashTable::unlocked_updateStoredValue(
264         const std::unique_lock<std::mutex>& htLock,
265         StoredValue& v,
266         const Item& itm) {
267     if (!htLock) {
268         throw std::invalid_argument(
269                 "HashTable::unlocked_updateStoredValue: htLock "
270                 "not held");
271     }
272
273     if (!isActive()) {
274         throw std::logic_error(
275                 "HashTable::unlocked_updateStoredValue: Cannot "
276                 "call on a non-active HT object");
277     }
278
279     MutationStatus status =
280             v.isDirty() ? MutationStatus::WasDirty : MutationStatus::WasClean;
281     if (!v.isResident() && !v.isDeleted() && !v.isTempItem()) {
282         decrNumNonResidentItems();
283     }
284
285     if (v.isTempItem()) {
286         --numTempItems;
287         ++numItems;
288         ++numTotalItems;
289     }
290
291     if (v.isDeleted() && !itm.isDeleted()) {
292         --numDeletedItems;
293     }
294     if (!v.isDeleted() && itm.isDeleted()) {
295         ++numDeletedItems;
296     }
297
298     // If the item we are replacing is resident then we need to make sure we
299     // appropriately alter the datatype stats.
300     if (v.getDatatype() != itm.getDataType()) {
301         --datatypeCounts[v.getDatatype()];
302         ++datatypeCounts[itm.getDataType()];
303     }
304
305     /* setValue() will mark v as undeleted if required */
306     v.setValue(itm, *this);
307     return status;
308 }
309
310 StoredValue* HashTable::unlocked_addNewStoredValue(const HashBucketLock& hbl,
311                                                    const Item& itm) {
312     if (!hbl.getHTLock()) {
313         throw std::invalid_argument(
314                 "HashTable::unlocked_addNewStoredValue: htLock "
315                 "not held");
316     }
317
318     if (!isActive()) {
319         throw std::invalid_argument(
320                 "HashTable::unlocked_addNewStoredValue: Cannot "
321                 "call on a non-active HT object");
322     }
323
324     // Create a new StoredValue and link it into the head of the bucket chain.
325     auto v = (*valFact)(itm, std::move(values[hbl.getBucketNum()]), *this);
326     if (v->isTempItem()) {
327         ++numTempItems;
328     } else {
329         ++numItems;
330         ++numTotalItems;
331         ++datatypeCounts[v->getDatatype()];
332     }
333     if (v->isDeleted()) {
334         ++numDeletedItems;
335     }
336     values[hbl.getBucketNum()] = std::move(v);
337
338     return values[hbl.getBucketNum()].get();
339 }
340
341 std::pair<StoredValue*, StoredValue::UniquePtr>
342 HashTable::unlocked_replaceByCopy(const HashBucketLock& hbl,
343                                   const StoredValue& vToCopy) {
344     if (!hbl.getHTLock()) {
345         throw std::invalid_argument(
346                 "HashTable::unlocked_replaceByCopy: htLock "
347                 "not held");
348     }
349
350     if (!isActive()) {
351         throw std::invalid_argument(
352                 "HashTable::unlocked_replaceByCopy: Cannot "
353                 "call on a non-active HT object");
354     }
355
356     /* Release (remove) the StoredValue from the hash table */
357     auto releasedSv = unlocked_release(hbl, vToCopy.getKey());
358
359     /* Copy the StoredValue and link it into the head of the bucket chain. */
360     auto newSv = valFact->copyStoredValue(
361             vToCopy, std::move(values[hbl.getBucketNum()]), *this);
362     if (newSv->isTempItem()) {
363         ++numTempItems;
364     } else {
365         ++numItems;
366         ++numTotalItems;
367     }
368     values[hbl.getBucketNum()] = std::move(newSv);
369
370     return {values[hbl.getBucketNum()].get(), std::move(releasedSv)};
371 }
372
373 void HashTable::unlocked_softDelete(const std::unique_lock<std::mutex>& htLock,
374                                     StoredValue& v,
375                                     bool onlyMarkDeleted) {
376     const bool alreadyDeleted = v.isDeleted();
377     if (!v.isResident() && !v.isDeleted() && !v.isTempItem()) {
378         decrNumNonResidentItems();
379     }
380
381     --datatypeCounts[v.getDatatype()];
382
383     if (onlyMarkDeleted) {
384         v.markDeleted();
385     } else {
386         if (v.isTempItem()) {
387             --numTempItems;
388             ++numItems;
389             ++numTotalItems;
390         }
391         v.del(*this);
392     }
393     if (!alreadyDeleted) {
394         ++numDeletedItems;
395     }
396 }
397
398 StoredValue* HashTable::unlocked_find(const DocKey& key,
399                                       int bucket_num,
400                                       WantsDeleted wantsDeleted,
401                                       TrackReference trackReference) {
402     for (StoredValue* v = values[bucket_num].get(); v; v = v->next.get()) {
403         if (v->hasKey(key)) {
404             if (trackReference == TrackReference::Yes && !v->isDeleted()) {
405                 v->referenced();
406             }
407             if (wantsDeleted == WantsDeleted::Yes || !v->isDeleted()) {
408                 return v;
409             } else {
410                 return NULL;
411             }
412         }
413     }
414     return NULL;
415 }
416
417 void HashTable::unlocked_del(const HashBucketLock& hbl, const DocKey& key) {
418     unlocked_release(hbl, key).reset();
419 }
420
421 StoredValue::UniquePtr HashTable::unlocked_release(
422         const HashBucketLock& hbl, const DocKey& key) {
423     if (!hbl.getHTLock()) {
424         throw std::invalid_argument(
425                 "HashTable::unlocked_remove: htLock "
426                 "not held");
427     }
428
429     if (!isActive()) {
430         throw std::logic_error(
431                 "HashTable::unlocked_remove: Cannot call on a "
432                 "non-active object");
433     }
434
435     // Remove the first (should only be one) StoredValue with the given key.
436     auto released = hashChainRemoveFirst(
437             values[hbl.getBucketNum()],
438             [key](const StoredValue* v) { return v->hasKey(key); });
439
440     if (!released) {
441         /* We shouldn't reach here, we must delete the StoredValue in the
442            HashTable */
443         throw std::logic_error(
444                 "HashTable::unlocked_del: StoredValue to be deleted "
445                 "not found in HashTable; possibly HashTable leak");
446     }
447
448     // Update statistics now the item has been removed.
449     StoredValue::reduceCacheSize(*this, released->size());
450     StoredValue::reduceMetaDataSize(*this, stats, released->metaDataSize());
451     if (released->isTempItem()) {
452         --numTempItems;
453     } else {
454         decrNumItems();
455         decrNumTotalItems();
456         --datatypeCounts[released->getDatatype()];
457         if (released->isDeleted()) {
458             --numDeletedItems;
459         }
460     }
461     return released;
462 }
463
464 void HashTable::visit(HashTableVisitor &visitor) {
465     if ((numItems.load() + numTempItems.load()) == 0 || !isActive()) {
466         return;
467     }
468
469     // Acquire one (any) of the mutexes before incrementing {visitors}, this
470     // prevents any race between this visitor and the HashTable resizer.
471     // See comments in pauseResumeVisit() for further details.
472     std::unique_lock<std::mutex> lh(mutexes[0]);
473     VisitorTracker vt(&visitors);
474     lh.unlock();
475
476     bool aborted = !visitor.shouldContinue();
477     size_t visited = 0;
478     for (int l = 0; isActive() && !aborted && l < static_cast<int>(n_locks);
479          l++) {
480         for (int i = l; i < static_cast<int>(size); i+= n_locks) {
481             // (re)acquire mutex on each HashBucket, to minimise any impact
482             // on front-end threads.
483             HashBucketLock lh(i, mutexes[l]);
484
485             StoredValue* v = values[i].get();
486             if (v) {
487                 // TODO: Perf: This check seems costly - do we think it's still
488                 // worth keeping?
489                 auto hashbucket = getBucketForHash(v->getKey().hash());
490                 if (i != hashbucket) {
491                     throw std::logic_error("HashTable::visit: inconsistency "
492                             "between StoredValue's calculated hashbucket "
493                             "(which is " + std::to_string(hashbucket) +
494                             ") and bucket is is located in (which is " +
495                             std::to_string(i) + ")");
496                 }
497             }
498             while (v) {
499                 StoredValue* tmp = v->next.get();
500                 visitor.visit(lh, v);
501                 v = tmp;
502             }
503             ++visited;
504         }
505         aborted = !visitor.shouldContinue();
506     }
507 }
508
509 void HashTable::visitDepth(HashTableDepthVisitor &visitor) {
510     if (numItems.load() == 0 || !isActive()) {
511         return;
512     }
513     size_t visited = 0;
514     VisitorTracker vt(&visitors);
515
516     for (int l = 0; l < static_cast<int>(n_locks); l++) {
517         LockHolder lh(mutexes[l]);
518         for (int i = l; i < static_cast<int>(size); i+= n_locks) {
519             size_t depth = 0;
520             StoredValue* p = values[i].get();
521             if (p) {
522                 // TODO: Perf: This check seems costly - do we think it's still
523                 // worth keeping?
524                 auto hashbucket = getBucketForHash(p->getKey().hash());
525                 if (i != hashbucket) {
526                     throw std::logic_error("HashTable::visit: inconsistency "
527                             "between StoredValue's calculated hashbucket "
528                             "(which is " + std::to_string(hashbucket) +
529                             ") and bucket it is located in (which is " +
530                             std::to_string(i) + ")");
531                 }
532             }
533             size_t mem(0);
534             while (p) {
535                 depth++;
536                 mem += p->size();
537                 p = p->next.get();
538             }
539             visitor.visit(i, depth, mem);
540             ++visited;
541         }
542     }
543 }
544
545 HashTable::Position
546 HashTable::pauseResumeVisit(PauseResumeHashTableVisitor& visitor,
547                             Position& start_pos) {
548     if ((numItems.load() + numTempItems.load()) == 0 || !isActive()) {
549         // Nothing to visit
550         return endPosition();
551     }
552
553     bool paused = false;
554
555     // To attempt to minimize the impact the visitor has on normal frontend
556     // operations, we deliberately acquire (and release) the mutex between
557     // each hash_bucket - see `lh` in the inner for() loop below. This means we
558     // hold a given mutex for a large number of short durations, instead of just
559     // one single, long duration.
560     // *However*, there is a potential race with this approach - the {size} of
561     // the HashTable may be changed (by the Resizer task) between us first
562     // reading it to calculate the starting hash_bucket, and then reading it
563     // inside the inner for() loop. To prevent this race, we explicitly acquire
564     // (any) mutex, increment {visitors} and then release the mutex. This
565     //avoids the race as if visitors >0 then Resizer will not attempt to resize.
566     std::unique_lock<std::mutex> lh(mutexes[0]);
567     VisitorTracker vt(&visitors);
568     lh.unlock();
569
570     // Start from the requested lock number if in range.
571     size_t lock = (start_pos.lock < n_locks) ? start_pos.lock : 0;
572     size_t hash_bucket = 0;
573
574     for (; isActive() && !paused && lock < n_locks; lock++) {
575
576         // If the bucket position is *this* lock, then start from the
577         // recorded bucket (as long as we haven't resized).
578         hash_bucket = lock;
579         if (start_pos.lock == lock &&
580             start_pos.ht_size == size &&
581             start_pos.hash_bucket < size) {
582             hash_bucket = start_pos.hash_bucket;
583         }
584
585         // Iterate across all values in the hash buckets owned by this lock.
586         // Note: we don't record how far into the bucket linked-list we
587         // pause at; so any restart will begin from the next bucket.
588         for (; !paused && hash_bucket < size; hash_bucket += n_locks) {
589             LockHolder lh(mutexes[lock]);
590
591             StoredValue* v = values[hash_bucket].get();
592             while (!paused && v) {
593                 StoredValue* tmp = v->next.get();
594                 paused = !visitor.visit(*v);
595                 v = tmp;
596             }
597         }
598
599         // If the visitor paused us before we visited all hash buckets owned
600         // by this lock, we don't want to skip the remaining hash buckets, so
601         // stop the outer for loop from advancing to the next lock.
602         if (paused && hash_bucket < size) {
603             break;
604         }
605
606         // Finished all buckets owned by this lock. Set hash_bucket to 'size'
607         // to give a consistent marker for "end of lock".
608         hash_bucket = size;
609     }
610
611     // Return the *next* location that should be visited.
612     return HashTable::Position(size, lock, hash_bucket);
613 }
614
615 HashTable::Position HashTable::endPosition() const  {
616     return HashTable::Position(size, n_locks, size);
617 }
618
619 static inline size_t getDefault(size_t x, size_t d) {
620     return x == 0 ? d : x;
621 }
622
623 size_t HashTable::getNumBuckets(size_t n) {
624     return getDefault(n, defaultNumBuckets);
625 }
626
627 size_t HashTable::getNumLocks(size_t n) {
628     return getDefault(n, defaultNumLocks);
629 }
630
631 void HashTable::setDefaultNumBuckets(size_t to) {
632     if (to != 0) {
633         defaultNumBuckets = to;
634     }
635 }
636
637 void HashTable::setDefaultNumLocks(size_t to) {
638     if (to != 0) {
639         defaultNumLocks = to;
640     }
641 }
642
643 bool HashTable::unlocked_ejectItem(StoredValue*& vptr,
644                                    item_eviction_policy_t policy) {
645     if (vptr == nullptr) {
646         throw std::invalid_argument("HashTable::unlocked_ejectItem: "
647                 "Unable to delete NULL StoredValue");
648     }
649     if (policy == VALUE_ONLY) {
650         bool rv = vptr->ejectValue(*this, policy);
651         if (rv) {
652             ++stats.numValueEjects;
653             ++numNonResidentItems;
654             ++numEjects;
655             return true;
656         } else {
657             ++stats.numFailedEjects;
658             return false;
659         }
660     } else { // full eviction.
661         if (vptr->eligibleForEviction(policy)) {
662             StoredValue::reduceMetaDataSize(*this, stats,
663                                             vptr->metaDataSize());
664             StoredValue::reduceCacheSize(*this, vptr->size());
665             int bucket_num = getBucketForHash(vptr->getKey().hash());
666
667             // Remove the item from the hash table.
668             auto removed = hashChainRemoveFirst(
669                     values[bucket_num],
670                     [vptr](const StoredValue* v) { return v == vptr; });
671
672             if (removed->isResident()) {
673                 ++stats.numValueEjects;
674             }
675             if (!removed->isResident() && !removed->isTempItem()) {
676                 decrNumNonResidentItems(); // Decrement because the item is
677                                            // fully evicted.
678             }
679             decrNumItems(); // Decrement because the item is fully evicted.
680             --datatypeCounts[vptr->getDatatype()];
681             ++numEjects;
682             updateMaxDeletedRevSeqno(vptr->getRevSeqno());
683
684             return true;
685         } else {
686             ++stats.numFailedEjects;
687             return false;
688         }
689     }
690 }
691
692 std::unique_ptr<Item> HashTable::getRandomKeyFromSlot(int slot) {
693     auto lh = getLockedBucket(slot);
694     for (StoredValue* v = values[slot].get(); v; v = v->next.get()) {
695         if (!v->isTempItem() && !v->isDeleted() && v->isResident()) {
696             return v->toItem(false, 0);
697         }
698     }
699
700     return nullptr;
701 }
702
703 bool HashTable::unlocked_restoreValue(
704         const std::unique_lock<std::mutex>& htLock,
705         const Item& itm,
706         StoredValue& v) {
707     if (!htLock || !isActive() || v.isResident()) {
708         return false;
709     }
710
711     if (v.isTempInitialItem()) { // Regular item with the full eviction
712         --numTempItems;
713         ++numItems;
714         /* set it back to false as we created a temp item by setting it to true
715            when bg fetch is scheduled (full eviction mode). */
716         v.setNewCacheItem(false);
717         ++datatypeCounts[itm.getDataType()];
718     } else {
719         decrNumNonResidentItems();
720     }
721
722     v.restoreValue(itm);
723
724     StoredValue::increaseCacheSize(*this, v.getValue()->length());
725     return true;
726 }
727
728 void HashTable::unlocked_restoreMeta(const std::unique_lock<std::mutex>& htLock,
729                                      const Item& itm,
730                                      StoredValue& v) {
731     if (!htLock) {
732         throw std::invalid_argument(
733                 "HashTable::unlocked_restoreMeta: htLock "
734                 "not held");
735     }
736
737     if (!isActive()) {
738         throw std::logic_error(
739                 "HashTable::unlocked_restoreMeta: Cannot "
740                 "call on a non-active HT object");
741     }
742
743     v.restoreMeta(itm);
744     if (!itm.isDeleted()) {
745         --numTempItems;
746         ++numItems;
747         ++numNonResidentItems;
748         ++datatypeCounts[v.getDatatype()];
749     }
750 }
751
752 std::ostream& operator<<(std::ostream& os, const HashTable& ht) {
753     os << "HashTable[" << &ht << "] with"
754        << " numInMemory:" << ht.getNumInMemoryItems()
755        << " numDeleted:" << ht.getNumDeletedItems()
756        << " values: " << std::endl;
757     for (const auto& chain : ht.values) {
758         if (chain) {
759             for (StoredValue* sv = chain.get(); sv != nullptr;
760                  sv = sv->next.get()) {
761                 os << "    " << *sv << std::endl;
762             }
763         }
764     }
765     return os;
766 }