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