hphp/runtime/vm/memo-cache.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_RUNTIME_VM_MEMO_CACHE_H_
  18 #define incl_HPHP_RUNTIME_VM_MEMO_CACHE_H_
  19
  20 #include "hphp/runtime/vm/func.h"
  21
  22 /*
  23  * Memoization cache support
  24  *
  25  * Memoization caches are used to support functions marked <<__Memoize>> and can
  26  * either be in RDS (for static functions) or hung-off ObjectData* (for
  27  * methods).
  28  *
  29  * All memo caches map some set of keys (which are only integers or strings) to
  30  * a particular Cell value. Caches can either be non-shared or shared. A
  31  * non-shared cache is for exactly one function, and the keys (corresponding to
  32  * the parameters) is all that's necessary to lookup the value. Non-shared
  33  * caches are used for static functions, and (as an optimization) on methods for
  34  * classes with few memoized functions. A shared cache can be used by different
  35  * functions, and therefore stores an additional key value distinguishing that
  36  * function (the form of this key varies by the cache type).
  37  *
  38  * Memo caches are only manipulated via their associated getter and setter
  39  * functions. Getter functions receive a pointer to MemoCacheBase, a pointer to
  40  * an array of Cells (which must be integers or strings) representing the
  41  * parameters, and, if shared, some additional value distinguishing that
  42  * function. If the value is found, a pointer to it is returned. If not, or if
  43  * the pointer to the cache is null, null is returned. No ref-count manipulation
  44  * is done in the returned value. Setter functions receive a *reference* to a
  45  * pointer to MemoCacheBase, a pointer to an array of Cells, if shared, an
  46  * additional value distinguishing that function, and a Cell to store in the
  47  * cache. The Cell is stored in the cache, and its ref-count is incremented
  48  * (with any previous value being dec-reffed and overwritten). If the pointer to
  49  * the cache was null, a new cache is allocated, and the pointer is updated to
  50  * point at it.
  51  *
  52  * For optimization, there's a number of specialized memo-caches. These are
  53  * specialized on a specific number of keys, and perhaps the types of
  54  * keys. These specializations are not exposed directly, but instead you call a
  55  * function to obtain the appropriate getter and setter. For a particular memo
  56  * cache, the same specialized get/set function must always be used! It is not
  57  * legal to sometimes use a specialized get/set function it, and a generic one
  58  * elesewhere.
  59  */
  60
  61 namespace HPHP {
  62
  63 /*
  64  * The actual implementation of the memo-caches are private to memo-cache.cpp
  65  * (since they involve a lot of templates). The rest of the runtime interacts
  66  * with them via a pointer to this base class. The set functions will create a
  67  * new memo-cache if the pointer is null, and update the pointer. We can destroy
  68  * them polymorphically when releasing an ObjectData, so the destructor must be
  69  * virtual.
  70  */
  71 struct MemoCacheBase {
  72   virtual ~MemoCacheBase() = default;
  73 };
  74
  75 ////////////////////////////////////////////////////////////
  76
  77 /*
  78  * Specialized getters and setters
  79  *
  80  * Up to certain limits, we have specialized caches for specific key counts and
  81  * key types. The exact nature of these specializations is an implementation
  82  * detail, so instead of enumerating the all appropriate get/set functions here,
  83  * we provide an interface to get the appropriate function pointer.
  84  *
  85  * Each "flavor" has a "GetForKeyTypes" and "GetForKeyCount" lookup
  86  * function. The first is for when you know the specific types of the keys. Keys
  87  * can only be integers or strings, and the types are represented by an array of
  88  * booleans, where true means string. If you don't know the specific types, one
  89  * can use "GetForKeyCount" to obtain a function specialized on just the key
  90  * count (Key type specialized and key count specialized get/set functions can
  91  * be interchanged freely on the same memo cache). If the function returns null,
  92  * there's no specialization available and one has to use a generic cache.
  93  *
  94  * For the shared-case, a FuncId is used to distinguish functions. A key-count
  95  * of zero never has a specialized representation here. It makes no sense for
  96  * the non-shared case, and the shared case should just use "shared-only"
  97  * caches.
  98  */
  99
 100 // Non-shared getter
 101 using MemoCacheGetter =
 102   const Cell* (*)(const MemoCacheBase*, const Cell*);
 103 MemoCacheGetter memoCacheGetForKeyTypes(const bool* types, size_t count);
 104 MemoCacheGetter memoCacheGetForKeyCount(size_t count);
 105
 106 // Non-shared setter
 107 using MemoCacheSetter =
 108   void (*)(MemoCacheBase*&, const Cell*, Cell);
 109 MemoCacheSetter memoCacheSetForKeyTypes(const bool* types, size_t count);
 110 MemoCacheSetter memoCacheSetForKeyCount(size_t count);
 111
 112 // Shared getter
 113 using SharedMemoCacheGetter =
 114   const Cell* (*)(const MemoCacheBase*, FuncId, const Cell*);
 115 SharedMemoCacheGetter sharedMemoCacheGetForKeyTypes(const bool* types,
 116                                                     size_t count);
 117 SharedMemoCacheGetter sharedMemoCacheGetForKeyCount(size_t count);
 118
 119 // Shared setter
 120 using SharedMemoCacheSetter =
 121   void (*)(MemoCacheBase*&, FuncId, const Cell*, Cell);
 122 SharedMemoCacheSetter sharedMemoCacheSetForKeyTypes(const bool* types,
 123                                                     size_t count);
 124 SharedMemoCacheSetter sharedMemoCacheSetForKeyCount(size_t count);
 125
 126 ////////////////////////////////////////////////////////////
 127
 128 /*
 129  * Generic getter and setter
 130  *
 131  * Generic memo caches can handle keys of any type or length (but are
 132  * slower). They are used when we don't have a specialized representation for a
 133  * particular key count.
 134  *
 135  * The generic cache get/set functions all take GenericMemoId::Param, which
 136  * serves the dual purpose of distinguishing different functions (since generic
 137  * caches can be shared), and encoding the number of keys.
 138  */
 139 struct GenericMemoId {
 140   GenericMemoId(FuncId funcId, uint32_t keyCount)
 141     : funcId{funcId}
 142     , keyCount{keyCount} {}
 143
 144   using Param = uint64_t;
 145
 146   explicit GenericMemoId(Param combined)
 147     : combined{combined} {}
 148
 149   FuncId getFuncId() const { return funcId; }
 150   uint32_t getKeyCount() const { return keyCount; }
 151
 152   Param asParam() const { return combined; }
 153
 154   void setKeyCount(uint32_t c) { keyCount = c; }
 155
 156 private:
 157   union {
 158     struct {
 159       FuncId funcId;
 160       uint32_t keyCount;
 161     };
 162     uint64_t combined;
 163   };
 164 };
 165
 166 const Cell* memoCacheGetGeneric(MemoCacheBase* base,
 167                                 GenericMemoId::Param id,
 168                                 const Cell* keys);
 169 void memoCacheSetGeneric(MemoCacheBase*& base,
 170                          GenericMemoId::Param id,
 171                          const Cell* keys,
 172                          Cell val);
 173
 174 ////////////////////////////////////////////////////////////
 175
 176 /*
 177  * Shared-only caches
 178  *
 179  * Specialization for a shared cache with no keys. In that case, the "key" is
 180  * just the function's id. As an optimization, we can pre-hash this key and pass
 181  * it in as a parameter to the getters/setters (the JIT can burn the hashed key
 182  * into the TC since the FuncId is always statically known).
 183  */
 184 using SharedOnlyKey = uint64_t;
 185
 186 inline SharedOnlyKey makeSharedOnlyKey(FuncId funcId) {
 187   static_assert(sizeof(FuncId) == sizeof(uint32_t), "");
 188   // This is a pseudo-random permutation, so it can be used as both a hash and a
 189   // key (different FuncIds will never map to the same SharedOnlyKey).
 190   return folly::hash::twang_mix64(
 191     (static_cast<uint64_t>(funcId) << 32) + funcId
 192   );
 193 }
 194
 195 const Cell* memoCacheGetSharedOnly(const MemoCacheBase* base,
 196                                    SharedOnlyKey key);
 197 void memoCacheSetSharedOnly(MemoCacheBase*& base,
 198                             SharedOnlyKey key,
 199                             Cell val);
 200
 201 ////////////////////////////////////////////////////////////
 202
 203 // We only have key-count specialized caches for key-counts up to and including
 204 // this. Most of the time you don't need to check this and instead using the
 205 // getter/setter lookup functions defined above.
 206 static constexpr size_t kMemoCacheMaxSpecializedKeys = 6;
 207
 208 }
 209
 210 #endif