1// Copyright (c) 2007, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// Author: Geoff Pike 32// 33// This file provides a minimal cache that can hold a <key, value> pair 34// with little if any wasted space. The types of the key and value 35// must be unsigned integral types or at least have unsigned semantics 36// for >>, casting, and similar operations. 37// 38// Synchronization is not provided. However, the cache is implemented 39// as an array of cache entries whose type is chosen at compile time. 40// If a[i] is atomic on your hardware for the chosen array type then 41// raciness will not necessarily lead to bugginess. The cache entries 42// must be large enough to hold a partial key and a value packed 43// together. The partial keys are bit strings of length 44// kKeybits - kHashbits, and the values are bit strings of length kValuebits. 45// 46// In an effort to use minimal space, every cache entry represents 47// some <key, value> pair; the class provides no way to mark a cache 48// entry as empty or uninitialized. In practice, you may want to have 49// reserved keys or values to get around this limitation. For example, in 50// tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as 51// "unknown sizeclass." 52// 53// Usage Considerations 54// -------------------- 55// 56// kHashbits controls the size of the cache. The best value for 57// kHashbits will of course depend on the application. Perhaps try 58// tuning the value of kHashbits by measuring different values on your 59// favorite benchmark. Also remember not to be a pig; other 60// programs that need resources may suffer if you are. 61// 62// The main uses for this class will be when performance is 63// critical and there's a convenient type to hold the cache's 64// entries. As described above, the number of bits required 65// for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose 66// kKeybits + kValuebits is 43. Then it probably makes sense to 67// chose kHashbits >= 11 so that cache entries fit in a uint32. 68// 69// On the other hand, suppose kKeybits = kValuebits = 64. Then 70// using this class may be less worthwhile. You'll probably 71// be using 128 bits for each entry anyway, so maybe just pick 72// a hash function, H, and use an array indexed by H(key): 73// void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); } 74// V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... } 75// etc. 76// 77// Further Details 78// --------------- 79// 80// For caches used only by one thread, the following is true: 81// 1. For a cache c, 82// (c.Put(key, value), c.GetOrDefault(key, 0)) == value 83// and 84// (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value 85// if the elided code contains no c.Put calls. 86// 87// 2. Has(key) will return false if no <key, value> pair with that key 88// has ever been Put. However, a newly initialized cache will have 89// some <key, value> pairs already present. When you create a new 90// cache, you must specify an "initial value." The initialization 91// procedure is equivalent to Clear(initial_value), which is 92// equivalent to Put(k, initial_value) for all keys k from 0 to 93// 2^kHashbits - 1. 94// 95// 3. If key and key' differ then the only way Put(key, value) may 96// cause Has(key') to change is that Has(key') may change from true to 97// false. Furthermore, a Put() call that doesn't change Has(key') 98// doesn't change GetOrDefault(key', ...) either. 99// 100// Implementation details: 101// 102// This is a direct-mapped cache with 2^kHashbits entries; the hash 103// function simply takes the low bits of the key. We store whole keys 104// if a whole key plus a whole value fits in an entry. Otherwise, an 105// entry is the high bits of a key and a value, packed together. 106// E.g., a 20 bit key and a 7 bit value only require a uint16 for each 107// entry if kHashbits >= 11. 108// 109// Alternatives to this scheme will be added as needed. 110 111#ifndef TCMALLOC_PACKED_CACHE_INL_H_ 112#define TCMALLOC_PACKED_CACHE_INL_H_ 113 114#include "config.h" 115#include <stddef.h> // for size_t 116#ifdef HAVE_STDINT_H 117#include <stdint.h> // for uintptr_t 118#endif 119#include "base/basictypes.h" 120#include "internal_logging.h" 121 122// A safe way of doing "(1 << n) - 1" -- without worrying about overflow 123// Note this will all be resolved to a constant expression at compile-time 124#define N_ONES_(IntType, N) \ 125 ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ 126 (static_cast<IntType>(1) << ((N)-1))) ) 127 128// The types K and V provide upper bounds on the number of valid keys 129// and values, but we explicitly require the keys to be less than 130// 2^kKeybits and the values to be less than 2^kValuebits. The size of 131// the table is controlled by kHashbits, and the type of each entry in 132// the cache is T. See also the big comment at the top of the file. 133template <int kKeybits, typename T> 134class PackedCache { 135 public: 136 typedef uintptr_t K; 137 typedef size_t V; 138#ifdef TCMALLOC_SMALL_BUT_SLOW 139 // Decrease the size map cache if running in the small memory mode. 140 static const int kHashbits = 12; 141#else 142 // We don't want the hash map to occupy 512K memory at Chromium, so 143 // kHashbits is decreased from 16 to 12. 144 static const int kHashbits = 12; 145#endif 146 static const int kValuebits = 7; 147 static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T); 148 149 explicit PackedCache(V initial_value) { 150 COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); 151 COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); 152 COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); 153 COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, 154 entry_size_must_be_big_enough); 155 Clear(initial_value); 156 } 157 158 void Put(K key, V value) { 159 ASSERT(key == (key & kKeyMask)); 160 ASSERT(value == (value & kValueMask)); 161 array_[Hash(key)] = KeyToUpper(key) | value; 162 } 163 164 bool Has(K key) const { 165 ASSERT(key == (key & kKeyMask)); 166 return KeyMatch(array_[Hash(key)], key); 167 } 168 169 V GetOrDefault(K key, V default_value) const { 170 // As with other code in this class, we touch array_ as few times 171 // as we can. Assuming entries are read atomically (e.g., their 172 // type is uintptr_t on most hardware) then certain races are 173 // harmless. 174 ASSERT(key == (key & kKeyMask)); 175 T entry = array_[Hash(key)]; 176 return KeyMatch(entry, key) ? EntryToValue(entry) : default_value; 177 } 178 179 void Clear(V value) { 180 ASSERT(value == (value & kValueMask)); 181 for (int i = 0; i < 1 << kHashbits; i++) { 182 ASSERT(kUseWholeKeys || KeyToUpper(i) == 0); 183 array_[i] = kUseWholeKeys ? (value | KeyToUpper(i)) : value; 184 } 185 } 186 187 private: 188 // We are going to pack a value and the upper part of a key (or a 189 // whole key) into an entry of type T. The UPPER type is for the 190 // upper part of a key, after the key has been masked and shifted 191 // for inclusion in an entry. 192 typedef T UPPER; 193 194 static V EntryToValue(T t) { return t & kValueMask; } 195 196 // If we have space for a whole key, we just shift it left. 197 // Otherwise kHashbits determines where in a K to find the upper 198 // part of the key, and kValuebits determines where in the entry to 199 // put it. 200 static UPPER KeyToUpper(K k) { 201 if (kUseWholeKeys) { 202 return static_cast<T>(k) << kValuebits; 203 } else { 204 const int shift = kHashbits - kValuebits; 205 // Assume kHashbits >= kValuebits. It'd be easy to lift this assumption. 206 return static_cast<T>(k >> shift) & kUpperMask; 207 } 208 } 209 210 static size_t Hash(K key) { 211 return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits); 212 } 213 214 // Does the entry match the relevant part of the given key? 215 static bool KeyMatch(T entry, K key) { 216 return kUseWholeKeys ? 217 (entry >> kValuebits == key) : 218 ((KeyToUpper(key) ^ entry) & kUpperMask) == 0; 219 } 220 221 static const int kTbits = 8 * sizeof(T); 222 static const int kUpperbits = kUseWholeKeys ? kKeybits : kKeybits - kHashbits; 223 224 // For masking a K. 225 static const K kKeyMask = N_ONES_(K, kKeybits); 226 227 // For masking a T. 228 static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits; 229 230 // For masking a V or a T. 231 static const V kValueMask = N_ONES_(V, kValuebits); 232 233 // array_ is the cache. Its elements are volatile because any 234 // thread can write any array element at any time. 235 volatile T array_[1 << kHashbits]; 236}; 237 238#undef N_ONES_ 239 240#endif // TCMALLOC_PACKED_CACHE_INL_H_ 241