hphp/runtime/base/packed-block.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 #ifndef incl_HPHP_PACKED_BLOCK_H_
  17 #define incl_HPHP_PACKED_BLOCK_H_
  18
  19 #include <cstddef>
  20 #include <cstdint>
  21 #include <sys/types.h>
  22
  23 #include "hphp/runtime/base/array-common.h"
  24 #include "hphp/runtime/base/array-data.h"
  25 #include "hphp/runtime/base/data-walker.h"
  26 #include "hphp/runtime/base/header-kind.h"
  27 #include "hphp/runtime/base/memory-manager.h"
  28 #include "hphp/runtime/base/sort-flags.h"
  29 #include "hphp/runtime/base/tv-val.h"
  30 #include "hphp/runtime/base/typed-value.h"
  31 #include "hphp/runtime/base/vanilla-vec.h"
  32
  33 #include "hphp/util/type-scan.h"
  34
  35 namespace HPHP {
  36
  37 //////////////////////////////////////////////////////////////////////
  38
  39 /*
  40  * If VanillaVec::stores_unaligned_typed_values is false, the entries of a VanillaVec
  41  * will be stored in a PackedBlock format. Each block consists of 8 DataTypes
  42  * followed by 8 Values, for a total size of 72 bytes.
  43  *
  44  * The extra types and values in the last PackedBlock are uninitialized.
  45  *
  46  * The easiest way to access entries in this layout is to use LvalAt. However,
  47  * if you are iterating over the array, you may want to use a pair of nested
  48  * loops to iterate first over blocks and second over items in the block.
  49  */
  50 struct PackedBlock final {
  51   static_assert(sizeof(Value) == 8);
  52   static_assert(sizeof(DataType) == 1);
  53   static constexpr size_t kNumItems = 8;
  54   static constexpr size_t kByteSize = kNumItems * 9;
  55
  56   // Each block contains up to 8 items, so i must be less than 8 here.
  57   tv_lval operator[](size_t i);
  58   bool operator<(const PackedBlock& other);
  59
  60   // Advance to the next block.
  61   PackedBlock& operator++();
  62   PackedBlock operator+(int64_t i);
  63   PackedBlock& operator+=(int64_t i);
  64
  65   // For the fast type predicates, n must be the number of items in the block.
  66   // In particular, it must be greater than 0 and less than or equal to 8.
  67   bool AllTypesEqual(size_t n);
  68   bool AllTypesMatch(size_t n, DataType expected);
  69   bool AllTypesAreUncounted(size_t n);
  70
  71   // Get a pointer to a given block by index in a packed array.
  72   static PackedBlock BlockAt(ArrayData* ad, size_t b);
  73   static tv_lval LvalAt(ArrayData* ad, size_t k);
  74
  75   // Get the type and data offsets for an known index. Used by the JIT.
  76   static VanillaVec::EntryOffset EntryOffset(size_t i);
  77
  78   // Turn a pointer in an array into the index it points to. -1 on failure.
  79   static int64_t PointerToIndex(const ArrayData* ad, const void* ptr);
  80
  81   // Always points to the 8-byte type block at the start of a block.
  82   Value* m_base;
  83 };
  84
  85 //////////////////////////////////////////////////////////////////////
  86
  87 constexpr uint64_t kTypecheckEqualityMasks[8] = {
  88   0x0,
  89   0x11,
  90   0x1111,
  91   0x111111,
  92   0x11111111,
  93   0x1111111111,
  94   0x111111111111,
  95   0x11111111111111,
  96 };
  97
  98 constexpr uint64_t kTypecheckRefcountMasks[8] = {
  99   0x01,
 100   0x0101,
 101   0x010101,
 102   0x01010101,
 103   0x0101010101,
 104   0x010101010101,
 105   0x01010101010101,
 106   0x0101010101010101,
 107 };
 108
 109 ALWAYS_INLINE tv_lval PackedBlock::operator[](size_t i) {
 110   assertx(i < kNumItems);
 111   auto* type = reinterpret_cast<DataType*>(this->m_base);
 112   return tv_lval(type + i, this->m_base + i + 1);
 113 }
 114
 115 ALWAYS_INLINE bool PackedBlock::operator<(const PackedBlock& other) {
 116   return this->m_base < other.m_base;
 117 }
 118
 119 ALWAYS_INLINE PackedBlock& PackedBlock::operator++() {
 120   return *this += 1;
 121 }
 122
 123 ALWAYS_INLINE PackedBlock PackedBlock::operator+(int64_t i) {
 124   return PackedBlock { this->m_base + 9 * i };
 125 }
 126
 127 ALWAYS_INLINE PackedBlock& PackedBlock::operator+=(int64_t i) {
 128   this->m_base += 9 * i;
 129   return *this;
 130 }
 131
 132 ALWAYS_INLINE bool PackedBlock::AllTypesEqual(size_t n) {
 133   assertx(0 < n && n <= kNumItems);
 134   auto const types = *reinterpret_cast<uint64_t*>(this->m_base);
 135   return ((types ^ (types >> 8)) & kTypecheckEqualityMasks[n - 1]) == 0;
 136 }
 137
 138 ALWAYS_INLINE bool PackedBlock::AllTypesMatch(size_t n, DataType type) {
 139   assertx(0 < n && n <= kNumItems);
 140   return AllTypesEqual(n) && *reinterpret_cast<DataType*>(m_base) == type;
 141 }
 142
 143 ALWAYS_INLINE bool PackedBlock::AllTypesAreUncounted(size_t n) {
 144   assertx(0 < n && n <= kNumItems);
 145   auto const types = *reinterpret_cast<uint64_t*>(this->m_base);
 146   return (types & kTypecheckRefcountMasks[n - 1]) == 0;
 147 }
 148
 149 ALWAYS_INLINE PackedBlock PackedBlock::BlockAt(ArrayData* ad, size_t b) {
 150   assertx(!VanillaVec::stores_unaligned_typed_values);
 151   return PackedBlock { reinterpret_cast<Value*>(ad + 1) } + b;
 152 }
 153
 154 ALWAYS_INLINE tv_lval PackedBlock::LvalAt(ArrayData* ad, size_t k) {
 155   // Given an index k = x + y, where y = k % 8, we want to index into ad at:
 156   //   type: ad + VanillaVec::entriesOffset + 9 * x + y
 157   //   data: ad + VanillaVec::entriesOffset + 9 * x + 8 * y + 8
 158   //
 159   // One way to compute these offsets is to compute the "base block pointer"
 160   // at ad + VanillaVec::entriesOffset + 9 * x, then use that to compute the
 161   // two pointers. This approach uses 6 arithmetic instructions:
 162   //
 163   //   x = k & -8          # AND
 164   //   y = k & 7           # AND
 165   //   z = x + 8 * x       # LEA
 166   //   w = ad + z + eo     # LEA
 167   //   t = w + y           # ADD
 168   //   d = w + 8 * y + 8   # LEA
 169   //
 170   // We can save an instruction by avoiding computing y, as follows:
 171   //
 172   //   x = k & -8          # AND
 173   //   a = ad + 8 * x + eo # LEA
 174   //   b = ad + 8 * k + eo # LEA
 175   //   t = a + k           # ADD
 176   //   d = b + x + 8       # LEA
 177   //
 178   // This method implements the optimization above and checks it against the
 179   // simpler computation using the PackedBlock API.
 180   //
 181   assertx(!VanillaVec::stores_unaligned_typed_values);
 182   auto const x = k & size_t(-8);
 183   auto const a = reinterpret_cast<char*>(ad + 1) + 8 * x;
 184   auto const b = reinterpret_cast<char*>(ad + 1) + 8 * k;
 185   auto const lval = tv_lval(
 186     reinterpret_cast<DataType*>(a + k),
 187     reinterpret_cast<Value*>(b + x + 8)
 188   );
 189   assertx(lval == PackedBlock::BlockAt(ad, k / 8)[k & 7]);
 190   return lval;
 191 }
 192
 193 VanillaVec::EntryOffset PackedBlock::EntryOffset(size_t i) {
 194   assertx(!VanillaVec::stores_unaligned_typed_values);
 195   auto const div = i / kNumItems;
 196   auto const mod = i % kNumItems;
 197   auto const base = sizeof(ArrayData) + kByteSize * div;
 198   return {ptrdiff_t(base + sizeof(DataType) * mod),
 199           ptrdiff_t(base + sizeof(DataType) * kNumItems + sizeof(Value) * mod)};
 200 }
 201
 202 int64_t PackedBlock::PointerToIndex(const ArrayData* ad, const void* ptr) {
 203   // We have three cases to handle here:
 204   //  1. ptr is before the first array entry.
 205   //  2. ptr points into some block's 8-byte DataType prefix.
 206   //  2. ptr points into some block's 64-byte Value suffix.
 207   assertx(!VanillaVec::stores_unaligned_typed_values);
 208   auto const base = reinterpret_cast<const char*>(ad + 1);
 209   auto const diff = reinterpret_cast<const char*>(ptr) - base;
 210   auto const div = diff / kByteSize;
 211   auto const mod = diff % kByteSize;
 212   return diff < 0 ? -1 : mod < 8 ? 8 * div + mod : 8 * div + mod / 8 - 1;
 213 }
 214
 215 } // namespace HPHP
 216
 217 #endif