Home | History | Annotate | Download | only in src
      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.
    133 template <int kKeybits, typename T>
    134 class 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