Branch data Line data Source code
# 1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
# 2 : : // Use of this source code is governed by a BSD-style license that can be
# 3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors.
# 4 : :
# 5 : : #include <assert.h>
# 6 : : #include <stdio.h>
# 7 : : #include <stdlib.h>
# 8 : :
# 9 : : #include "leveldb/cache.h"
# 10 : : #include "port/port.h"
# 11 : : #include "port/thread_annotations.h"
# 12 : : #include "util/hash.h"
# 13 : : #include "util/mutexlock.h"
# 14 : :
# 15 : : namespace leveldb {
# 16 : :
# 17 : 4384 : Cache::~Cache() {}
# 18 : :
# 19 : : namespace {
# 20 : :
# 21 : : // LRU cache implementation
# 22 : : //
# 23 : : // Cache entries have an "in_cache" boolean indicating whether the cache has a
# 24 : : // reference on the entry. The only ways that this can become false without the
# 25 : : // entry being passed to its "deleter" are via Erase(), via Insert() when
# 26 : : // an element with a duplicate key is inserted, or on destruction of the cache.
# 27 : : //
# 28 : : // The cache keeps two linked lists of items in the cache. All items in the
# 29 : : // cache are in one list or the other, and never both. Items still referenced
# 30 : : // by clients but erased from the cache are in neither list. The lists are:
# 31 : : // - in-use: contains the items currently referenced by clients, in no
# 32 : : // particular order. (This list is used for invariant checking. If we
# 33 : : // removed the check, elements that would otherwise be on this list could be
# 34 : : // left as disconnected singleton lists.)
# 35 : : // - LRU: contains the items not currently referenced by clients, in LRU order
# 36 : : // Elements are moved between these lists by the Ref() and Unref() methods,
# 37 : : // when they detect an element in the cache acquiring or losing its only
# 38 : : // external reference.
# 39 : :
# 40 : : // An entry is a variable length heap-allocated structure. Entries
# 41 : : // are kept in a circular doubly linked list ordered by access time.
# 42 : : struct LRUHandle {
# 43 : : void* value;
# 44 : : void (*deleter)(const Slice&, void* value);
# 45 : : LRUHandle* next_hash;
# 46 : : LRUHandle* next;
# 47 : : LRUHandle* prev;
# 48 : : size_t charge; // TODO(opt): Only allow uint32_t?
# 49 : : size_t key_length;
# 50 : : bool in_cache; // Whether entry is in the cache.
# 51 : : uint32_t refs; // References, including cache reference, if present.
# 52 : : uint32_t hash; // Hash of key(); used for fast sharding and comparisons
# 53 : : char key_data[1]; // Beginning of key
# 54 : :
# 55 : 3474036 : Slice key() const {
# 56 : : // next_ is only equal to this if the LRU handle is the list head of an
# 57 : : // empty list. List heads never have meaningful keys.
# 58 : 3474036 : assert(next != this);
# 59 : :
# 60 : 0 : return Slice(key_data, key_length);
# 61 : 3474036 : }
# 62 : : };
# 63 : :
# 64 : : // We provide our own simple hash table since it removes a whole bunch
# 65 : : // of porting hacks and is also faster than some of the built-in hash
# 66 : : // table implementations in some of the compiler/runtime combinations
# 67 : : // we have tested. E.g., readrandom speeds up by ~5% over the g++
# 68 : : // 4.4.3's builtin hashtable.
# 69 : : class HandleTable {
# 70 : : public:
# 71 : 70176 : HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
# 72 : 70144 : ~HandleTable() { delete[] list_; }
# 73 : :
# 74 : 3492147 : LRUHandle* Lookup(const Slice& key, uint32_t hash) {
# 75 : 3492147 : return *FindPointer(key, hash);
# 76 : 3492147 : }
# 77 : :
# 78 : 2407 : LRUHandle* Insert(LRUHandle* h) {
# 79 : 2407 : LRUHandle** ptr = FindPointer(h->key(), h->hash);
# 80 : 2407 : LRUHandle* old = *ptr;
# 81 [ + + ]: 2407 : h->next_hash = (old == nullptr ? nullptr : old->next_hash);
# 82 : 2407 : *ptr = h;
# 83 [ + + ]: 2407 : if (old == nullptr) {
# 84 : 2395 : ++elems_;
# 85 [ + + ]: 2395 : if (elems_ > length_) {
# 86 : : // Since each cache entry is fairly large, we aim for a small
# 87 : : // average linked list length (<= 1).
# 88 : 74 : Resize();
# 89 : 74 : }
# 90 : 2395 : }
# 91 : 2407 : return old;
# 92 : 2407 : }
# 93 : :
# 94 : 403 : LRUHandle* Remove(const Slice& key, uint32_t hash) {
# 95 : 403 : LRUHandle** ptr = FindPointer(key, hash);
# 96 : 403 : LRUHandle* result = *ptr;
# 97 [ + + ]: 403 : if (result != nullptr) {
# 98 : 394 : *ptr = result->next_hash;
# 99 : 394 : --elems_;
# 100 : 394 : }
# 101 : 403 : return result;
# 102 : 403 : }
# 103 : :
# 104 : : private:
# 105 : : // The table consists of an array of buckets where each bucket is
# 106 : : // a linked list of cache entries that hash into the bucket.
# 107 : : uint32_t length_;
# 108 : : uint32_t elems_;
# 109 : : LRUHandle** list_;
# 110 : :
# 111 : : // Return a pointer to slot that points to a cache entry that
# 112 : : // matches key/hash. If there is no such cache entry, return a
# 113 : : // pointer to the trailing slot in the corresponding linked list.
# 114 : 3494957 : LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
# 115 : 3494957 : LRUHandle** ptr = &list_[hash & (length_ - 1)];
# 116 [ + + ][ + + ]: 3519588 : while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
# [ + + ][ - + ]
# 117 : 24631 : ptr = &(*ptr)->next_hash;
# 118 : 24631 : }
# 119 : 3494957 : return ptr;
# 120 : 3494957 : }
# 121 : :
# 122 : 70250 : void Resize() {
# 123 : 70250 : uint32_t new_length = 4;
# 124 [ + + ]: 70376 : while (new_length < elems_) {
# 125 : 126 : new_length *= 2;
# 126 : 126 : }
# 127 : 70250 : LRUHandle** new_list = new LRUHandle*[new_length];
# 128 : 70250 : memset(new_list, 0, sizeof(new_list[0]) * new_length);
# 129 : 70250 : uint32_t count = 0;
# 130 [ + + ]: 70794 : for (uint32_t i = 0; i < length_; i++) {
# 131 : 544 : LRUHandle* h = list_[i];
# 132 [ + + ]: 1162 : while (h != nullptr) {
# 133 : 618 : LRUHandle* next = h->next_hash;
# 134 : 618 : uint32_t hash = h->hash;
# 135 : 618 : LRUHandle** ptr = &new_list[hash & (new_length - 1)];
# 136 : 618 : h->next_hash = *ptr;
# 137 : 618 : *ptr = h;
# 138 : 618 : h = next;
# 139 : 618 : count++;
# 140 : 618 : }
# 141 : 544 : }
# 142 : 70250 : assert(elems_ == count);
# 143 : 0 : delete[] list_;
# 144 : 70250 : list_ = new_list;
# 145 : 70250 : length_ = new_length;
# 146 : 70250 : }
# 147 : : };
# 148 : :
# 149 : : // A single shard of sharded cache.
# 150 : : class LRUCache {
# 151 : : public:
# 152 : : LRUCache();
# 153 : : ~LRUCache();
# 154 : :
# 155 : : // Separate from constructor so caller can easily make an array of LRUCache
# 156 : 70176 : void SetCapacity(size_t capacity) { capacity_ = capacity; }
# 157 : :
# 158 : : // Like Cache methods, but with an extra "hash" parameter.
# 159 : : Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
# 160 : : size_t charge,
# 161 : : void (*deleter)(const Slice& key, void* value));
# 162 : : Cache::Handle* Lookup(const Slice& key, uint32_t hash);
# 163 : : void Release(Cache::Handle* handle);
# 164 : : void Erase(const Slice& key, uint32_t hash);
# 165 : : void Prune();
# 166 : 0 : size_t TotalCharge() const {
# 167 : 0 : MutexLock l(&mutex_);
# 168 : 0 : return usage_;
# 169 : 0 : }
# 170 : :
# 171 : : private:
# 172 : : void LRU_Remove(LRUHandle* e);
# 173 : : void LRU_Append(LRUHandle* list, LRUHandle* e);
# 174 : : void Ref(LRUHandle* e);
# 175 : : void Unref(LRUHandle* e);
# 176 : : bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
# 177 : :
# 178 : : // Initialized before use.
# 179 : : size_t capacity_;
# 180 : :
# 181 : : // mutex_ protects the following state.
# 182 : : mutable port::Mutex mutex_;
# 183 : : size_t usage_ GUARDED_BY(mutex_);
# 184 : :
# 185 : : // Dummy head of LRU list.
# 186 : : // lru.prev is newest entry, lru.next is oldest entry.
# 187 : : // Entries have refs==1 and in_cache==true.
# 188 : : LRUHandle lru_ GUARDED_BY(mutex_);
# 189 : :
# 190 : : // Dummy head of in-use list.
# 191 : : // Entries are in use by clients, and have refs >= 2 and in_cache==true.
# 192 : : LRUHandle in_use_ GUARDED_BY(mutex_);
# 193 : :
# 194 : : HandleTable table_ GUARDED_BY(mutex_);
# 195 : : };
# 196 : :
# 197 : 70176 : LRUCache::LRUCache() : capacity_(0), usage_(0) {
# 198 : : // Make empty circular linked lists.
# 199 : 70176 : lru_.next = &lru_;
# 200 : 70176 : lru_.prev = &lru_;
# 201 : 70176 : in_use_.next = &in_use_;
# 202 : 70176 : in_use_.prev = &in_use_;
# 203 : 70176 : }
# 204 : :
# 205 : 70144 : LRUCache::~LRUCache() {
# 206 : 70144 : assert(in_use_.next == &in_use_); // Error if caller has an unreleased handle
# 207 [ + + ]: 72145 : for (LRUHandle* e = lru_.next; e != &lru_;) {
# 208 : 2001 : LRUHandle* next = e->next;
# 209 : 2001 : assert(e->in_cache);
# 210 : 0 : e->in_cache = false;
# 211 : 2001 : assert(e->refs == 1); // Invariant of lru_ list.
# 212 : 0 : Unref(e);
# 213 : 2001 : e = next;
# 214 : 2001 : }
# 215 : 70144 : }
# 216 : :
# 217 : 3468816 : void LRUCache::Ref(LRUHandle* e) {
# 218 [ + + ][ + - ]: 3468816 : if (e->refs == 1 && e->in_cache) { // If on lru_ list, move to in_use_ list.
# 219 : 3463680 : LRU_Remove(e);
# 220 : 3463680 : LRU_Append(&in_use_, e);
# 221 : 3463680 : }
# 222 : 3468816 : e->refs++;
# 223 : 3468816 : }
# 224 : :
# 225 : 3473630 : void LRUCache::Unref(LRUHandle* e) {
# 226 : 3473630 : assert(e->refs > 0);
# 227 : 0 : e->refs--;
# 228 [ + + ]: 3473630 : if (e->refs == 0) { // Deallocate.
# 229 : 2407 : assert(!e->in_cache);
# 230 : 0 : (*e->deleter)(e->key(), e->value);
# 231 : 2407 : free(e);
# 232 [ + + ][ + + ]: 3471223 : } else if (e->in_cache && e->refs == 1) {
# 233 : : // No longer in use; move to lru_ list.
# 234 : 3466075 : LRU_Remove(e);
# 235 : 3466075 : LRU_Append(&lru_, e);
# 236 : 3466075 : }
# 237 : 3473630 : }
# 238 : :
# 239 : 6930161 : void LRUCache::LRU_Remove(LRUHandle* e) {
# 240 : 6930161 : e->next->prev = e->prev;
# 241 : 6930161 : e->prev->next = e->next;
# 242 : 6930161 : }
# 243 : :
# 244 : 6932162 : void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
# 245 : : // Make "e" newest entry by inserting just before *list
# 246 : 6932162 : e->next = list;
# 247 : 6932162 : e->prev = list->prev;
# 248 : 6932162 : e->prev->next = e;
# 249 : 6932162 : e->next->prev = e;
# 250 : 6932162 : }
# 251 : :
# 252 : 3492145 : Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
# 253 : 3492145 : MutexLock l(&mutex_);
# 254 : 3492145 : LRUHandle* e = table_.Lookup(key, hash);
# 255 [ + + ]: 3492145 : if (e != nullptr) {
# 256 : 3468816 : Ref(e);
# 257 : 3468816 : }
# 258 : 3492145 : return reinterpret_cast<Cache::Handle*>(e);
# 259 : 3492145 : }
# 260 : :
# 261 : 3471223 : void LRUCache::Release(Cache::Handle* handle) {
# 262 : 3471223 : MutexLock l(&mutex_);
# 263 : 3471223 : Unref(reinterpret_cast<LRUHandle*>(handle));
# 264 : 3471223 : }
# 265 : :
# 266 : : Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
# 267 : : size_t charge,
# 268 : : void (*deleter)(const Slice& key,
# 269 : 2407 : void* value)) {
# 270 : 2407 : MutexLock l(&mutex_);
# 271 : :
# 272 : 2407 : LRUHandle* e =
# 273 : 2407 : reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
# 274 : 2407 : e->value = value;
# 275 : 2407 : e->deleter = deleter;
# 276 : 2407 : e->charge = charge;
# 277 : 2407 : e->key_length = key.size();
# 278 : 2407 : e->hash = hash;
# 279 : 2407 : e->in_cache = false;
# 280 : 2407 : e->refs = 1; // for the returned handle.
# 281 : 2407 : memcpy(e->key_data, key.data(), key.size());
# 282 : :
# 283 [ + - ]: 2407 : if (capacity_ > 0) {
# 284 : 2407 : e->refs++; // for the cache's reference.
# 285 : 2407 : e->in_cache = true;
# 286 : 2407 : LRU_Append(&in_use_, e);
# 287 : 2407 : usage_ += charge;
# 288 : 2407 : FinishErase(table_.Insert(e));
# 289 : 2407 : } else { // don't cache. (capacity_==0 is supported and turns off caching.)
# 290 : : // next is read by key() in an assert, so it must be initialized
# 291 : 0 : e->next = nullptr;
# 292 : 0 : }
# 293 [ - + ][ # # ]: 2407 : while (usage_ > capacity_ && lru_.next != &lru_) {
# 294 : 0 : LRUHandle* old = lru_.next;
# 295 : 0 : assert(old->refs == 1);
# 296 : 0 : bool erased = FinishErase(table_.Remove(old->key(), old->hash));
# 297 [ # # ]: 0 : if (!erased) { // to avoid unused variable when compiled NDEBUG
# 298 : 0 : assert(erased);
# 299 : 0 : }
# 300 : 0 : }
# 301 : :
# 302 : 2407 : return reinterpret_cast<Cache::Handle*>(e);
# 303 : 2407 : }
# 304 : :
# 305 : : // If e != nullptr, finish removing *e from the cache; it has already been
# 306 : : // removed from the hash table. Return whether e != nullptr.
# 307 : 2810 : bool LRUCache::FinishErase(LRUHandle* e) {
# 308 [ + + ]: 2810 : if (e != nullptr) {
# 309 : 406 : assert(e->in_cache);
# 310 : 0 : LRU_Remove(e);
# 311 : 406 : e->in_cache = false;
# 312 : 406 : usage_ -= e->charge;
# 313 : 406 : Unref(e);
# 314 : 406 : }
# 315 : 0 : return e != nullptr;
# 316 : 2810 : }
# 317 : :
# 318 : 403 : void LRUCache::Erase(const Slice& key, uint32_t hash) {
# 319 : 403 : MutexLock l(&mutex_);
# 320 : 403 : FinishErase(table_.Remove(key, hash));
# 321 : 403 : }
# 322 : :
# 323 : 0 : void LRUCache::Prune() {
# 324 : 0 : MutexLock l(&mutex_);
# 325 [ # # ]: 0 : while (lru_.next != &lru_) {
# 326 : 0 : LRUHandle* e = lru_.next;
# 327 : 0 : assert(e->refs == 1);
# 328 : 0 : bool erased = FinishErase(table_.Remove(e->key(), e->hash));
# 329 [ # # ]: 0 : if (!erased) { // to avoid unused variable when compiled NDEBUG
# 330 : 0 : assert(erased);
# 331 : 0 : }
# 332 : 0 : }
# 333 : 0 : }
# 334 : :
# 335 : : static const int kNumShardBits = 4;
# 336 : : static const int kNumShards = 1 << kNumShardBits;
# 337 : :
# 338 : : class ShardedLRUCache : public Cache {
# 339 : : private:
# 340 : : LRUCache shard_[kNumShards];
# 341 : : port::Mutex id_mutex_;
# 342 : : uint64_t last_id_;
# 343 : :
# 344 : 3494956 : static inline uint32_t HashSlice(const Slice& s) {
# 345 : 3494956 : return Hash(s.data(), s.size(), 0);
# 346 : 3494956 : }
# 347 : :
# 348 : 6966178 : static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }
# 349 : :
# 350 : : public:
# 351 : 4386 : explicit ShardedLRUCache(size_t capacity) : last_id_(0) {
# 352 : 4386 : const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
# 353 [ + + ]: 74562 : for (int s = 0; s < kNumShards; s++) {
# 354 : 70176 : shard_[s].SetCapacity(per_shard);
# 355 : 70176 : }
# 356 : 4386 : }
# 357 : 4384 : ~ShardedLRUCache() override {}
# 358 : : Handle* Insert(const Slice& key, void* value, size_t charge,
# 359 : 2407 : void (*deleter)(const Slice& key, void* value)) override {
# 360 : 2407 : const uint32_t hash = HashSlice(key);
# 361 : 2407 : return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
# 362 : 2407 : }
# 363 : 3492146 : Handle* Lookup(const Slice& key) override {
# 364 : 3492146 : const uint32_t hash = HashSlice(key);
# 365 : 3492146 : return shard_[Shard(hash)].Lookup(key, hash);
# 366 : 3492146 : }
# 367 : 3471223 : void Release(Handle* handle) override {
# 368 : 3471223 : LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
# 369 : 3471223 : shard_[Shard(h->hash)].Release(handle);
# 370 : 3471223 : }
# 371 : 403 : void Erase(const Slice& key) override {
# 372 : 403 : const uint32_t hash = HashSlice(key);
# 373 : 403 : shard_[Shard(hash)].Erase(key, hash);
# 374 : 403 : }
# 375 : 3470739 : void* Value(Handle* handle) override {
# 376 : 3470739 : return reinterpret_cast<LRUHandle*>(handle)->value;
# 377 : 3470739 : }
# 378 : 1923 : uint64_t NewId() override {
# 379 : 1923 : MutexLock l(&id_mutex_);
# 380 : 1923 : return ++(last_id_);
# 381 : 1923 : }
# 382 : 0 : void Prune() override {
# 383 [ # # ]: 0 : for (int s = 0; s < kNumShards; s++) {
# 384 : 0 : shard_[s].Prune();
# 385 : 0 : }
# 386 : 0 : }
# 387 : 0 : size_t TotalCharge() const override {
# 388 : 0 : size_t total = 0;
# 389 [ # # ]: 0 : for (int s = 0; s < kNumShards; s++) {
# 390 : 0 : total += shard_[s].TotalCharge();
# 391 : 0 : }
# 392 : 0 : return total;
# 393 : 0 : }
# 394 : : };
# 395 : :
# 396 : : } // end anonymous namespace
# 397 : :
# 398 : 4386 : Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }
# 399 : :
# 400 : : } // namespace leveldb
|
