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