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 

   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 

   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 

   157   bool Has(K key) const {

   158     DCHECK_EQ(key, key & kKeyMask);

   159     return KeyMatch(array_[Hash(key)], key);

   160   }

   161 

   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 

   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 

   185   static V EntryToValue(T t) { return t & kValueMask; }

   186 

   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.

   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.

   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 

   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?

   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__