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 "leveldb/cache.h" 6 7 #include <vector> 8 #include "util/coding.h" 9 #include "util/testharness.h" 10 11 namespace leveldb { 12 13 // Conversions between numeric keys/values and the types expected by Cache. 14 static std::string EncodeKey(int k) { 15 std::string result; 16 PutFixed32(&result, k); 17 return result; 18 } 19 static int DecodeKey(const Slice& k) { 20 assert(k.size() == 4); 21 return DecodeFixed32(k.data()); 22 } 23 static void* EncodeValue(uintptr_t v) { return reinterpret_cast<void*>(v); } 24 static int DecodeValue(void* v) { return reinterpret_cast<uintptr_t>(v); } 25 26 class CacheTest { 27 public: 28 static CacheTest* current_; 29 30 static void Deleter(const Slice& key, void* v) { 31 current_->deleted_keys_.push_back(DecodeKey(key)); 32 current_->deleted_values_.push_back(DecodeValue(v)); 33 } 34 35 static const int kCacheSize = 1000; 36 std::vector<int> deleted_keys_; 37 std::vector<int> deleted_values_; 38 Cache* cache_; 39 40 CacheTest() : cache_(NewLRUCache(kCacheSize)) { 41 current_ = this; 42 } 43 44 ~CacheTest() { 45 delete cache_; 46 } 47 48 int Lookup(int key) { 49 Cache::Handle* handle = cache_->Lookup(EncodeKey(key)); 50 const int r = (handle == NULL) ? -1 : DecodeValue(cache_->Value(handle)); 51 if (handle != NULL) { 52 cache_->Release(handle); 53 } 54 return r; 55 } 56 57 void Insert(int key, int value, int charge = 1) { 58 cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge, 59 &CacheTest::Deleter)); 60 } 61 62 void Erase(int key) { 63 cache_->Erase(EncodeKey(key)); 64 } 65 }; 66 CacheTest* CacheTest::current_; 67 68 TEST(CacheTest, HitAndMiss) { 69 ASSERT_EQ(-1, Lookup(100)); 70 71 Insert(100, 101); 72 ASSERT_EQ(101, Lookup(100)); 73 ASSERT_EQ(-1, Lookup(200)); 74 ASSERT_EQ(-1, Lookup(300)); 75 76 Insert(200, 201); 77 ASSERT_EQ(101, Lookup(100)); 78 ASSERT_EQ(201, Lookup(200)); 79 ASSERT_EQ(-1, Lookup(300)); 80 81 Insert(100, 102); 82 ASSERT_EQ(102, Lookup(100)); 83 ASSERT_EQ(201, Lookup(200)); 84 ASSERT_EQ(-1, Lookup(300)); 85 86 ASSERT_EQ(1, deleted_keys_.size()); 87 ASSERT_EQ(100, deleted_keys_[0]); 88 ASSERT_EQ(101, deleted_values_[0]); 89 } 90 91 TEST(CacheTest, Erase) { 92 Erase(200); 93 ASSERT_EQ(0, deleted_keys_.size()); 94 95 Insert(100, 101); 96 Insert(200, 201); 97 Erase(100); 98 ASSERT_EQ(-1, Lookup(100)); 99 ASSERT_EQ(201, Lookup(200)); 100 ASSERT_EQ(1, deleted_keys_.size()); 101 ASSERT_EQ(100, deleted_keys_[0]); 102 ASSERT_EQ(101, deleted_values_[0]); 103 104 Erase(100); 105 ASSERT_EQ(-1, Lookup(100)); 106 ASSERT_EQ(201, Lookup(200)); 107 ASSERT_EQ(1, deleted_keys_.size()); 108 } 109 110 TEST(CacheTest, EntriesArePinned) { 111 Insert(100, 101); 112 Cache::Handle* h1 = cache_->Lookup(EncodeKey(100)); 113 ASSERT_EQ(101, DecodeValue(cache_->Value(h1))); 114 115 Insert(100, 102); 116 Cache::Handle* h2 = cache_->Lookup(EncodeKey(100)); 117 ASSERT_EQ(102, DecodeValue(cache_->Value(h2))); 118 ASSERT_EQ(0, deleted_keys_.size()); 119 120 cache_->Release(h1); 121 ASSERT_EQ(1, deleted_keys_.size()); 122 ASSERT_EQ(100, deleted_keys_[0]); 123 ASSERT_EQ(101, deleted_values_[0]); 124 125 Erase(100); 126 ASSERT_EQ(-1, Lookup(100)); 127 ASSERT_EQ(1, deleted_keys_.size()); 128 129 cache_->Release(h2); 130 ASSERT_EQ(2, deleted_keys_.size()); 131 ASSERT_EQ(100, deleted_keys_[1]); 132 ASSERT_EQ(102, deleted_values_[1]); 133 } 134 135 TEST(CacheTest, EvictionPolicy) { 136 Insert(100, 101); 137 Insert(200, 201); 138 139 // Frequently used entry must be kept around 140 for (int i = 0; i < kCacheSize + 100; i++) { 141 Insert(1000+i, 2000+i); 142 ASSERT_EQ(2000+i, Lookup(1000+i)); 143 ASSERT_EQ(101, Lookup(100)); 144 } 145 ASSERT_EQ(101, Lookup(100)); 146 ASSERT_EQ(-1, Lookup(200)); 147 } 148 149 TEST(CacheTest, HeavyEntries) { 150 // Add a bunch of light and heavy entries and then count the combined 151 // size of items still in the cache, which must be approximately the 152 // same as the total capacity. 153 const int kLight = 1; 154 const int kHeavy = 10; 155 int added = 0; 156 int index = 0; 157 while (added < 2*kCacheSize) { 158 const int weight = (index & 1) ? kLight : kHeavy; 159 Insert(index, 1000+index, weight); 160 added += weight; 161 index++; 162 } 163 164 int cached_weight = 0; 165 for (int i = 0; i < index; i++) { 166 const int weight = (i & 1 ? kLight : kHeavy); 167 int r = Lookup(i); 168 if (r >= 0) { 169 cached_weight += weight; 170 ASSERT_EQ(1000+i, r); 171 } 172 } 173 ASSERT_LE(cached_weight, kCacheSize + kCacheSize/10); 174 } 175 176 TEST(CacheTest, NewId) { 177 uint64_t a = cache_->NewId(); 178 uint64_t b = cache_->NewId(); 179 ASSERT_NE(a, b); 180 } 181 182 } // namespace leveldb 183 184 int main(int argc, char** argv) { 185 return leveldb::test::RunAllTests(); 186 } 187
