1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/cache.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <vector> 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/coding.h" 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/testharness.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Conversions between numeric keys/values and the types expected by Cache. 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic std::string EncodeKey(int k) { 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string result; 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org PutFixed32(&result, k); 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic int DecodeKey(const Slice& k) { 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(k.size() == 4); 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return DecodeFixed32(k.data()); 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void* EncodeValue(uintptr_t v) { return reinterpret_cast<void*>(v); } 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic int DecodeValue(void* v) { return reinterpret_cast<uintptr_t>(v); } 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass CacheTest { 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org static CacheTest* current_; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org static void Deleter(const Slice& key, void* v) { 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_->deleted_keys_.push_back(DecodeKey(key)); 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_->deleted_values_.push_back(DecodeValue(v)); 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 35d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com static const int kCacheSize = 1000; 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<int> deleted_keys_; 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<int> deleted_values_; 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache* cache_; 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org CacheTest() : cache_(NewLRUCache(kCacheSize)) { 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_ = this; 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~CacheTest() { 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete cache_; 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int Lookup(int key) { 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache::Handle* handle = cache_->Lookup(EncodeKey(key)); 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int r = (handle == NULL) ? -1 : DecodeValue(cache_->Value(handle)); 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (handle != NULL) { 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_->Release(handle); 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return r; 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Insert(int key, int value, int charge = 1) { 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge, 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org &CacheTest::Deleter)); 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Erase(int key) { 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_->Erase(EncodeKey(key)); 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCacheTest* CacheTest::current_; 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(CacheTest, HitAndMiss) { 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(100)); 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 101); 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, Lookup(100)); 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(200)); 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(300)); 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(200, 201); 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, Lookup(100)); 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(201, Lookup(200)); 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(300)); 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 102); 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(102, Lookup(100)); 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(201, Lookup(200)); 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(300)); 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(1, deleted_keys_.size()); 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(100, deleted_keys_[0]); 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, deleted_values_[0]); 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(CacheTest, Erase) { 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Erase(200); 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(0, deleted_keys_.size()); 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 101); 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(200, 201); 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Erase(100); 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(100)); 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(201, Lookup(200)); 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(1, deleted_keys_.size()); 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(100, deleted_keys_[0]); 102179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, deleted_values_[0]); 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Erase(100); 105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(100)); 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(201, Lookup(200)); 107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(1, deleted_keys_.size()); 108179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 109179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(CacheTest, EntriesArePinned) { 111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 101); 112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache::Handle* h1 = cache_->Lookup(EncodeKey(100)); 113179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, DecodeValue(cache_->Value(h1))); 114179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 115179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 102); 116179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache::Handle* h2 = cache_->Lookup(EncodeKey(100)); 117179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(102, DecodeValue(cache_->Value(h2))); 118179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(0, deleted_keys_.size()); 119179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 120179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_->Release(h1); 121179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(1, deleted_keys_.size()); 122179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(100, deleted_keys_[0]); 123179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, deleted_values_[0]); 124179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 125179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Erase(100); 126179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(-1, Lookup(100)); 127179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(1, deleted_keys_.size()); 128179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 129179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_->Release(h2); 130179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(2, deleted_keys_.size()); 131179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(100, deleted_keys_[1]); 132179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(102, deleted_values_[1]); 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(CacheTest, EvictionPolicy) { 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(100, 101); 137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(200, 201); 138179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Frequently used entry must be kept around 140d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com for (int i = 0; i < kCacheSize + 100; i++) { 141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Insert(1000+i, 2000+i); 142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(2000+i, Lookup(1000+i)); 143179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, Lookup(100)); 144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(101, Lookup(100)); 146d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com ASSERT_EQ(-1, Lookup(200)); 147179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 148179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 149d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.comTEST(CacheTest, HeavyEntries) { 150d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // Add a bunch of light and heavy entries and then count the combined 151d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // size of items still in the cache, which must be approximately the 152d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com // same as the total capacity. 153d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const int kLight = 1; 154d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const int kHeavy = 10; 155d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com int added = 0; 156d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com int index = 0; 157d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com while (added < 2*kCacheSize) { 158d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const int weight = (index & 1) ? kLight : kHeavy; 159d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com Insert(index, 1000+index, weight); 160d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com added += weight; 161d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com index++; 162d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 163d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com 164d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com int cached_weight = 0; 165d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com for (int i = 0; i < index; i++) { 166d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com const int weight = (i & 1 ? kLight : kHeavy); 167d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com int r = Lookup(i); 168d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com if (r >= 0) { 169d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com cached_weight += weight; 170d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com ASSERT_EQ(1000+i, r); 171d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 172d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com } 173d36ce84e66c7d3cee978fbeb52721c30dfb842a5gabor@google.com ASSERT_LE(cached_weight, kCacheSize + kCacheSize/10); 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(CacheTest, NewId) { 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t a = cache_->NewId(); 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t b = cache_->NewId(); 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_NE(a, b); 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 18245b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint main(int argc, char** argv) { 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return leveldb::test::RunAllTests(); 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 187