hphp/util/data-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
  17 #ifndef incl_HPHP_DATA_BLOCK_H
  18 #define incl_HPHP_DATA_BLOCK_H
  19
  20 #include <cstdint>
  21 #include <cstring>
  22 #include <map>
  23 #include <set>
  24
  25 #include <folly/Bits.h>
  26 #include <folly/Format.h>
  27 #include <folly/portability/SysMman.h>
  28
  29 #include "hphp/util/assertions.h"
  30
  31 namespace HPHP {
  32
  33 namespace sz {
  34   constexpr int nosize = 0;
  35   constexpr int byte  = 1;
  36   constexpr int word  = 2;
  37   constexpr int dword = 4;
  38   constexpr int qword = 8;
  39 }
  40
  41 using Address          = uint8_t*;
  42 using CodeAddress      = uint8_t*;
  43 using ConstCodeAddress = const uint8_t*;
  44
  45 struct DataBlockFull : std::runtime_error {
  46   std::string name;
  47
  48   DataBlockFull(const std::string& blockName, const std::string msg)
  49       : std::runtime_error(msg)
  50       , name(blockName)
  51     {}
  52
  53   ~DataBlockFull() noexcept override {}
  54 };
  55
  56 /**
  57  * DataBlock is a simple bump-allocating wrapper around a chunk of memory, with
  58  * basic tracking for unused memory and a simple interface to allocate it.
  59  *
  60  * Memory is allocated from the end of the block unless specifically allocated
  61  * using allocInner.
  62  *
  63  * Unused memory can be freed using free(). If the memory is at the end of the
  64  * block, the frontier will be moved back.
  65  *
  66  * Free memory is coalesced and allocation is done by best-fit.
  67  */
  68 struct DataBlock {
  69   DataBlock() = default;
  70
  71   DataBlock(DataBlock&& other) = default;
  72   DataBlock& operator=(DataBlock&& other) = default;
  73
  74   /**
  75    * Uses an existing chunk of memory.
  76    *
  77    * Addresses returned by DataBlock will be in the range [start, start + sz),
  78    * while writes and reads will happen from the range [dest, dest + sz).
  79    */
  80   void init(Address start, Address dest, size_t sz, size_t maxGrow,
  81             const char* name) {
  82     assertx(dest != start || sz == maxGrow);
  83
  84     m_base = m_frontier = start;
  85     m_destBase = dest;
  86     m_size = sz;
  87     m_maxGrow = maxGrow;
  88     m_name = name;
  89   }
  90
  91   void init(Address start, Address dest, size_t sz, const char* name) {
  92     init(start, dest, sz, sz, name);
  93   }
  94
  95   void init(Address start, size_t sz, const char* name) {
  96     init(start, start, sz, sz, name);
  97   }
  98
  99   /*
 100    * allocRaw
 101    * alloc
 102    *
 103    * Simple bump allocator, supporting power-of-two alignment. alloc<T>() is a
 104    * simple typed wrapper around allocRaw().
 105    */
 106   void* allocRaw(size_t sz, size_t align = 16) {
 107     // Round frontier up to a multiple of align
 108     align = folly::nextPowTwo(align) - 1;
 109     auto const nf = (uint8_t*)(((uintptr_t)m_frontier + align) & ~align);
 110     assertCanEmit(nf - m_frontier + sz);
 111     setFrontier(nf);
 112     auto data = m_frontier;
 113     m_frontier += sz;
 114     assertx(m_frontier <= m_base + m_size);
 115     return data;
 116   }
 117
 118   template<typename T> T* alloc(size_t align = 16, int n = 1) {
 119     return (T*)allocRaw(sizeof(T) * n, align);
 120   }
 121
 122   bool canEmit(size_t nBytes) {
 123     assert(m_frontier >= m_base);
 124     assert(m_frontier <= m_base + m_size);
 125     return m_frontier + nBytes <= m_base + m_size;
 126   }
 127
 128   bool grow(size_t nBytes) {
 129     if (m_maxGrow == m_size) return false;
 130     assertx(m_destBase != m_base);
 131
 132     auto const need = nBytes - available();
 133     auto const amt = std::min(std::max(m_size + need, 2 * m_size), m_maxGrow);
 134     if (amt < m_size + need) return false;
 135     if (!m_destBuf) {
 136       m_destBuf.reset((Address)::malloc(amt));
 137       ::memcpy(m_destBuf.get(), m_destBase, used());
 138     } else {
 139       m_destBuf.reset((Address)::realloc(m_destBuf.release(), amt));
 140     }
 141     if (!m_destBuf) reportMallocError(amt);
 142     m_destBase = m_destBuf.get();
 143     m_size = amt;
 144     return true;
 145   }
 146
 147   void assertCanEmit(size_t nBytes) {
 148     if (!canEmit(nBytes) && !grow(nBytes)) reportFull(nBytes);
 149   }
 150
 151   [[noreturn]]
 152   void reportFull(size_t nbytes) const;
 153
 154   [[noreturn]]
 155   void reportMallocError(size_t nbytes) const;
 156
 157   bool isValidAddress(const CodeAddress tca) const {
 158     return tca >= m_base && tca < (m_base + m_size);
 159   }
 160
 161   void byte(const uint8_t byte) {
 162     assertCanEmit(sz::byte);
 163     *dest() = byte;
 164     m_frontier += sz::byte;
 165   }
 166   void word(const uint16_t word) {
 167     assertCanEmit(sz::word);
 168     *(uint16_t*)dest() = word;
 169     m_frontier += sz::word;
 170   }
 171   void dword(const uint32_t dword) {
 172     assertCanEmit(sz::dword);
 173     *(uint32_t*)dest() = dword;
 174     m_frontier += sz::dword;
 175   }
 176   void qword(const uint64_t qword) {
 177     assertCanEmit(sz::qword);
 178     *(uint64_t*)dest() = qword;
 179     m_frontier += sz::qword;
 180   }
 181
 182   void bytes(size_t n, const uint8_t *bs) {
 183     assertCanEmit(n);
 184     if (n <= 8 && m_destBase == m_base) {
 185       // If it is a modest number of bytes, try executing in one machine
 186       // store. This allows control-flow edges, including nop, to be
 187       // appear idempotent on other CPUs. If m_destBase != m_base then the
 188       // current block is a temporary buffer and this write is neither required
 189       // nor safe, as we may override an adjacent buffer or write off the end
 190       // of an allocation.
 191       union {
 192         uint64_t qword;
 193         uint8_t bytes[8];
 194       } u;
 195       u.qword = *(uint64_t*)dest();
 196       for (size_t i = 0; i < n; ++i) {
 197         u.bytes[i] = bs[i];
 198       }
 199
 200       // If this address spans cache lines, on x64 this is not an atomic store.
 201       // This being the case, use caution when overwriting code that is
 202       // reachable by multiple threads: make sure it doesn't span cache lines.
 203       *reinterpret_cast<uint64_t*>(dest()) = u.qword;
 204     } else {
 205       memcpy(dest(), bs, n);
 206     }
 207     m_frontier += n;
 208   }
 209
 210   void skip(size_t nbytes) {
 211     alloc<uint8_t>(1, nbytes);
 212   }
 213
 214   Address base() const { return m_base; }
 215   Address frontier() const { return m_frontier; }
 216   std::string name() const { return m_name; }
 217
 218   /*
 219    * DataBlock can emit into a range [A, B] while returning addresses in range
 220    * [A', B']. This function  will map an address in [A', B'] into [A, B], and
 221    * it must be used before writing or reading from any address returned by
 222    * DataBlock.
 223    */
 224   Address toDestAddress(CodeAddress addr) {
 225     assertx(m_base <= addr && addr <= (m_base + m_size));
 226     return Address(m_destBase + (addr - m_base));
 227   }
 228
 229   void setFrontier(Address addr) {
 230     assertx(m_base <= addr && addr <= (m_base + m_size));
 231     m_frontier = addr;
 232   }
 233
 234   size_t capacity() const {
 235     return m_size;
 236   }
 237
 238   size_t used() const {
 239     return m_frontier - m_base;
 240   }
 241
 242   size_t available() const {
 243     return m_size - (m_frontier - m_base);
 244   }
 245
 246   bool contains(ConstCodeAddress addr) const {
 247     return addr >= m_base && addr < (m_base + m_size);
 248   }
 249
 250   bool empty() const {
 251     return m_base == m_frontier;
 252   }
 253
 254   void clear() {
 255     setFrontier(m_base);
 256   }
 257
 258   void zero() {
 259     memset(m_destBase, 0, m_frontier - m_base);
 260     clear();
 261   }
 262
 263   // Append address range to free list
 264   void free(void* addr, size_t len);
 265
 266   // Attempt to allocate a range from within the free list
 267   void* allocInner(size_t len);
 268
 269   size_t numFrees()   const { return m_nfree; }
 270   size_t numAllocs()  const { return m_nalloc; }
 271   size_t bytesFree()  const { return m_bytesFree; }
 272   size_t blocksFree() const { return m_freeRanges.size(); }
 273
 274 private:
 275
 276   using Offset = uint32_t;
 277   using Size = uint32_t;
 278
 279   // DataBlock can optionally be growable. The initial expansion of DataBlock
 280   // will allocate a new buffer that is owned by the DataBlock, subsequent
 281   // expansions will use realloc to expand this block until m_maxGrow has been
 282   // reached. Only DataBlocks which have a different m_base from m_destBase may
 283   // be grown, as expansion may move the location of m_destBase.
 284   struct Deleter final { void operator()(uint8_t* a) const { ::free(a); } };
 285   std::unique_ptr<uint8_t, Deleter> m_destBuf{nullptr};
 286
 287   Address dest() const { return m_destBase + (m_frontier - m_base); }
 288
 289   // DataBlock can track an alternate pseudo-frontier to support clients that
 290   // wish to emit code to one location while keeping memory references relative
 291   // to a separate location. The actual writes will be to m_dest.
 292   Address m_destBase{nullptr};
 293
 294   Address m_base{nullptr};
 295   Address m_frontier{nullptr};
 296   size_t  m_size{0};
 297   size_t  m_maxGrow{0};
 298   std::string m_name;
 299
 300   size_t m_nfree{0};
 301   size_t m_nalloc{0};
 302
 303   size_t m_bytesFree{0};
 304   std::unordered_map<Offset, int64_t> m_freeRanges;
 305   std::map<Size, std::unordered_set<Offset>> m_freeLists;
 306 };
 307
 308 using CodeBlock = DataBlock;
 309
 310 //////////////////////////////////////////////////////////////////////
 311
 312 struct UndoMarker {
 313   explicit UndoMarker(CodeBlock& cb)
 314     : m_cb(cb)
 315     , m_oldFrontier(cb.frontier()) {
 316   }
 317
 318   void undo() {
 319     m_cb.setFrontier(m_oldFrontier);
 320   }
 321
 322 private:
 323   CodeBlock& m_cb;
 324   CodeAddress m_oldFrontier;
 325 };
 326
 327 /*
 328  * RAII bookmark for scoped rewinding of frontier.
 329  */
 330 struct CodeCursor : UndoMarker {
 331   CodeCursor(CodeBlock& cb, CodeAddress newFrontier) : UndoMarker(cb) {
 332     cb.setFrontier(newFrontier);
 333   }
 334
 335   ~CodeCursor() { undo(); }
 336 };
 337 }
 338
 339 #endif