• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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;
103 // the hash function simply takes the low bits of the key.
104 // So, we don't have to store the low bits of the key in the entries.
105 // Instead, an entry is the high bits of a key and a value, packed
106 // together.  E.g., a 20 bit key and a 7 bit value only require
107 // a uint16 for each 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 #ifndef WTF_CHANGES
115 #include "base/basictypes.h"  // for COMPILE_ASSERT
116 #include "base/logging.h"     // for DCHECK
117 #endif
118 
119 #ifndef DCHECK_EQ
120 #define DCHECK_EQ(val1, val2) ASSERT((val1) == (val2))
121 #endif
122 
123 // A safe way of doing "(1 << n) - 1" -- without worrying about overflow
124 // Note this will all be resolved to a constant expression at compile-time
125 #define N_ONES_(IntType, N)                                     \
126   ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 +    \
127                     (static_cast<IntType>(1) << ((N)-1))) )
128 
129 // The types K and V provide upper bounds on the number of valid keys
130 // and values, but we explicitly require the keys to be less than
131 // 2^kKeybits and the values to be less than 2^kValuebits.  The size of
132 // the table is controlled by kHashbits, and the type of each entry in
133 // the cache is T.  See also the big comment at the top of the file.
134 template <int kKeybits, typename T>
135 class PackedCache {
136  public:
137   typedef uintptr_t K;
138   typedef size_t V;
139   static const size_t kHashbits = 12;
140   static const size_t kValuebits = 8;
141 
PackedCache(V initial_value)142   explicit PackedCache(V initial_value) {
143     COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size);
144     COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size);
145     COMPILE_ASSERT(kHashbits <= kKeybits, hash_function);
146     COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits,
147                    entry_size_must_be_big_enough);
148     Clear(initial_value);
149   }
150 
Put(K key,V value)151   void Put(K key, V value) {
152     DCHECK_EQ(key, key & kKeyMask);
153     DCHECK_EQ(value, value & kValueMask);
154     array_[Hash(key)] = static_cast<T>(KeyToUpper(key) | value);
155   }
156 
Has(K key)157   bool Has(K key) const {
158     DCHECK_EQ(key, key & kKeyMask);
159     return KeyMatch(array_[Hash(key)], key);
160   }
161 
GetOrDefault(K key,V default_value)162   V GetOrDefault(K key, V default_value) const {
163     // As with other code in this class, we touch array_ as few times
164     // as we can.  Assuming entries are read atomically (e.g., their
165     // type is uintptr_t on most hardware) then certain races are
166     // harmless.
167     DCHECK_EQ(key, key & kKeyMask);
168     T entry = array_[Hash(key)];
169     return KeyMatch(entry, key) ? EntryToValue(entry) : default_value;
170   }
171 
Clear(V value)172   void Clear(V value) {
173     DCHECK_EQ(value, value & kValueMask);
174     for (int i = 0; i < 1 << kHashbits; i++) {
175       array_[i] = static_cast<T>(value);
176     }
177   }
178 
179  private:
180   // We are going to pack a value and the upper part of a key into
181   // an entry of type T.  The UPPER type is for the upper part of a key,
182   // after the key has been masked and shifted for inclusion in an entry.
183   typedef T UPPER;
184 
EntryToValue(T t)185   static V EntryToValue(T t) { return t & kValueMask; }
186 
EntryToUpper(T t)187   static UPPER EntryToUpper(T t) { return t & kUpperMask; }
188 
189   // If v is a V and u is an UPPER then you can create an entry by
190   // doing u | v.  kHashbits determines where in a K to find the upper
191   // part of the key, and kValuebits determines where in the entry to put
192   // it.
KeyToUpper(K k)193   static UPPER KeyToUpper(K k) {
194     const int shift = kHashbits - kValuebits;
195     // Assume kHashbits >= kValuebits. It would be easy to lift this assumption.
196     return static_cast<T>(k >> shift) & kUpperMask;
197   }
198 
199   // This is roughly the inverse of KeyToUpper().  Some of the key has been
200   // thrown away, since KeyToUpper() masks off the low bits of the key.
UpperToPartialKey(UPPER u)201   static K UpperToPartialKey(UPPER u) {
202     DCHECK_EQ(u, u & kUpperMask);
203     const int shift = kHashbits - kValuebits;
204     // Assume kHashbits >= kValuebits. It would be easy to lift this assumption.
205     return static_cast<K>(u) << shift;
206   }
207 
Hash(K key)208   static size_t Hash(K key) {
209     return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits);
210   }
211 
212   // Does the entry's partial key match the relevant part of the given key?
KeyMatch(T entry,K key)213   static bool KeyMatch(T entry, K key) {
214     return ((KeyToUpper(key) ^ entry) & kUpperMask) == 0;
215   }
216 
217   static const size_t kTbits = 8 * sizeof(T);
218   static const int kUpperbits = kKeybits - kHashbits;
219 
220   // For masking a K.
221   static const K kKeyMask = N_ONES_(K, kKeybits);
222 
223   // For masking a T.
224   static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits;
225 
226   // For masking a V or a T.
227   static const V kValueMask = N_ONES_(V, kValuebits);
228 
229   T array_[1 << kHashbits];
230 };
231 
232 #undef N_ONES_
233 
234 #endif  // TCMALLOC_PACKED_CACHE_INL_H__
235