hphp/runtime/base/memory-manager-defs.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2016 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_MEMORY_MANAGER_DEFS_H
  18 #define incl_HPHP_MEMORY_MANAGER_DEFS_H
  19
  20 #include "hphp/runtime/base/apc-local-array.h"
  21 #include "hphp/runtime/base/proxy-array.h"
  22 #include "hphp/runtime/vm/native-data.h"
  23 #include "hphp/runtime/base/packed-array-defs.h"
  24 #include "hphp/runtime/base/mixed-array-defs.h"
  25 #include "hphp/runtime/vm/globals-array.h"
  26 #include "hphp/runtime/vm/resumable.h"
  27 #include "hphp/runtime/ext/asio/ext_asio.h"
  28 #include "hphp/runtime/ext/asio/ext_await-all-wait-handle.h"
  29 #include "hphp/runtime/ext/collections/ext_collections-pair.h"
  30 #include "hphp/runtime/ext/collections/ext_collections-vector.h"
  31 #include "hphp/runtime/ext/collections/hash-collection.h"
  32
  33 #include <algorithm>
  34
  35 namespace HPHP {
  36
  37 // union of all the possible header types, and some utilities
  38 struct Header {
  39   size_t size() const;
  40   HeaderKind kind() const {
  41     assert(unsigned(hdr_.kind) <= NumHeaderKinds);
  42     return hdr_.kind;
  43   }
  44   union {
  45     struct {
  46       uint64_t q;
  47       HeaderWord<> hdr_;
  48     };
  49     StringData str_;
  50     ArrayData arr_;
  51     MixedArray mixed_;
  52     APCLocalArray apc_;
  53     ProxyArray proxy_;
  54     GlobalsArray globals_;
  55     ObjectData obj_;
  56     c_Pair pair_;
  57     BaseVector vector_;
  58     HashCollection hashcoll_;
  59     ResourceHdr res_;
  60     RefData ref_;
  61     MallocNode malloc_;
  62     FreeNode free_;
  63     ResumableNode resumable_;
  64     NativeNode native_;
  65     c_AwaitAllWaitHandle awaitall_;
  66   };
  67
  68   const Resumable* resumable() const {
  69     assert(kind() == HeaderKind::ResumableFrame);
  70     return reinterpret_cast<const Resumable*>(
  71       (char*)this + sizeof(ResumableNode) + resumable_.framesize
  72     );
  73   }
  74   Resumable* resumable() {
  75     assert(kind() == HeaderKind::ResumableFrame);
  76     return reinterpret_cast<Resumable*>(
  77       (char*)this + sizeof(ResumableNode) + resumable_.framesize
  78     );
  79   }
  80   const ObjectData* resumableObj() const {
  81     DEBUG_ONLY auto const func = resumable()->actRec()->func();
  82     assert(func->isAsyncFunction());
  83     auto obj = reinterpret_cast<const ObjectData*>(resumable() + 1);
  84     assert(obj->headerKind() == HeaderKind::ResumableObj);
  85     return obj;
  86   }
  87   ObjectData* resumableObj() {
  88     DEBUG_ONLY auto const func = resumable()->actRec()->func();
  89     assert(func->isAsyncFunction());
  90     auto obj = reinterpret_cast<ObjectData*>(resumable() + 1);
  91     assert(obj->headerKind() == HeaderKind::ResumableObj);
  92     return obj;
  93   }
  94   const ObjectData* nativeObj() const {
  95     assert(kind() == HeaderKind::NativeData);
  96     auto obj = Native::obj(&native_);
  97     assert(isObjectKind(obj->headerKind()));
  98     return obj;
  99   }
 100   ObjectData* nativeObj() {
 101     assert(kind() == HeaderKind::NativeData);
 102     auto obj = Native::obj(&native_);
 103     assert(isObjectKind(obj->headerKind()));
 104     return obj;
 105   }
 106
 107   // if this header is one of the types that contains an ObjectData,
 108   // return the (possibly inner ptr) ObjectData*
 109   const ObjectData* obj() const {
 110     return isObjectKind(kind()) ? &obj_ :
 111            kind() == HeaderKind::ResumableFrame ? resumableObj() :
 112            kind() == HeaderKind::NativeData ? nativeObj() :
 113            nullptr;
 114   }
 115 };
 116
 117 inline size_t Header::size() const {
 118   switch (kind()) {
 119     case HeaderKind::Packed:
 120     case HeaderKind::VecArray:
 121       return PackedArray::heapSize(&arr_);
 122     case HeaderKind::Mixed:
 123     case HeaderKind::Dict:
 124     case HeaderKind::Keyset:
 125       return mixed_.heapSize();
 126     case HeaderKind::Empty:
 127       return sizeof(ArrayData);
 128     case HeaderKind::Apc:
 129       return sizeof(APCLocalArray);
 130     case HeaderKind::Globals:
 131       return sizeof(GlobalsArray);
 132     case HeaderKind::Proxy:
 133       return sizeof(ProxyArray);
 134     case HeaderKind::String:
 135       return str_.heapSize();
 136     case HeaderKind::Object:
 137     case HeaderKind::ResumableObj:
 138       // [ObjectData][subclass][props]
 139       return obj_.heapSize();
 140     case HeaderKind::Vector:
 141     case HeaderKind::Map:
 142     case HeaderKind::Set:
 143     case HeaderKind::Pair:
 144     case HeaderKind::ImmVector:
 145     case HeaderKind::ImmMap:
 146     case HeaderKind::ImmSet:
 147       // [ObjectData][subclass]
 148       return collections::heapSize(kind());
 149     case HeaderKind::WaitHandle:
 150       // [ObjectData][subclass]
 151       return asio_object_size(&obj_);
 152     case HeaderKind::AwaitAllWH:
 153       // [ObjectData][children...]
 154       return awaitall_.heapSize();
 155     case HeaderKind::Resource:
 156       // [ResourceHdr][ResourceData subclass]
 157       return res_.heapSize();
 158     case HeaderKind::Ref:
 159       return sizeof(RefData);
 160     case HeaderKind::SmallMalloc: // [MallocNode][bytes...]
 161     case HeaderKind::BigMalloc:   // [MallocNode][bytes...]
 162     case HeaderKind::BigObj:      // [MallocNode][Header...]
 163       return malloc_.nbytes;
 164     case HeaderKind::ResumableFrame:
 165       // Async functions -
 166       // [ResumableNode][locals][Resumable][ObjectData<WaitHandle>]
 167       return resumable()->size();
 168     case HeaderKind::NativeData:
 169       // [NativeNode][NativeData][ObjectData][props] is one allocation.
 170       // Generators -
 171       // [NativeNode][NativeData<locals><Resumable><GeneratorData>][ObjectData]
 172       return native_.obj_offset + nativeObj()->heapSize();
 173     case HeaderKind::Free:
 174     case HeaderKind::Hole:
 175       return free_.size();
 176   }
 177   return 0;
 178 }
 179
 180 // Iterate over all the slabs and bigs
 181 template<class Fn> void BigHeap::iterate(Fn fn) {
 182   auto in_slabs = !m_slabs.empty();
 183   auto slab = begin(m_slabs);
 184   auto big = begin(m_bigs);
 185   Header *hdr, *slab_end;
 186   if (in_slabs) {
 187     hdr = (Header*)slab->ptr;
 188     slab_end = (Header*)(static_cast<char*>(slab->ptr) + slab->size);
 189   } else {
 190     hdr = big != end(m_bigs) ? (Header*)*big : nullptr;
 191     slab_end = nullptr;
 192   }
 193   while (in_slabs || big != end(m_bigs)) {
 194     auto h = hdr;
 195     if (in_slabs) {
 196       // move to next header in slab. Hole and Free have exact sizes,
 197       // so don't round them.
 198       auto size = hdr->hdr_.kind == HeaderKind::Hole ||
 199                   hdr->hdr_.kind == HeaderKind::Free ? hdr->free_.size() :
 200                   MemoryManager::smallSizeClass(hdr->size());
 201       assert(size % 16 == 0);
 202       hdr = (Header*)((char*)hdr + size);
 203       if (hdr >= slab_end) {
 204         assert(hdr == slab_end && "hdr > slab_end indicates corruption");
 205         // move to next slab
 206         if (++slab != m_slabs.end()) {
 207           hdr = (Header*)slab->ptr;
 208           slab_end = (Header*)(static_cast<char*>(slab->ptr) + slab->size);
 209         } else {
 210           // move to first big block
 211           in_slabs = false;
 212           if (big != end(m_bigs)) hdr = (Header*)*big;
 213         }
 214       }
 215     } else {
 216       // move to next big block
 217       if (++big != end(m_bigs)) hdr = (Header*)*big;
 218     }
 219     fn(h);
 220   }
 221 }
 222
 223 // Raw iterator loop over the headers of everything in the heap.  Skips BigObj
 224 // because it's just a detail of which sub-heap we used to allocate something
 225 // based on its size, and it can prefix almost any other header kind.  Clients
 226 // can call this directly to avoid unnecessary initFree()s.
 227 template<class Fn> void MemoryManager::iterate(Fn fn) {
 228   m_heap.iterate([&](Header* h) {
 229     if (h->kind() == HeaderKind::BigObj) {
 230       // skip MallocNode
 231       h = reinterpret_cast<Header*>((&h->malloc_)+1);
 232     } else if (h->kind() == HeaderKind::Hole) {
 233       // no valid pointer can point here.
 234       return; // continue iterating
 235     }
 236     fn(h);
 237   });
 238 }
 239
 240 // same as iterate(), but calls initFree first.
 241 template<class Fn> void MemoryManager::forEachHeader(Fn fn) {
 242   initFree();
 243   iterate(fn);
 244 }
 245
 246 // iterate just the ObjectDatas, including the kinds with prefixes.
 247 // (NativeData and ResumableFrame).
 248 template<class Fn> void MemoryManager::forEachObject(Fn fn) {
 249   if (debug) checkHeap("MM::forEachObject");
 250   std::vector<ObjectData*> ptrs;
 251   forEachHeader([&](Header* h) {
 252     switch (h->kind()) {
 253       case HeaderKind::Object:
 254       case HeaderKind::WaitHandle:
 255       case HeaderKind::ResumableObj:
 256       case HeaderKind::AwaitAllWH:
 257       case HeaderKind::Vector:
 258       case HeaderKind::Map:
 259       case HeaderKind::Set:
 260       case HeaderKind::Pair:
 261       case HeaderKind::ImmVector:
 262       case HeaderKind::ImmMap:
 263       case HeaderKind::ImmSet:
 264         ptrs.push_back(&h->obj_);
 265         break;
 266       case HeaderKind::ResumableFrame:
 267         ptrs.push_back(h->resumableObj());
 268         break;
 269       case HeaderKind::NativeData:
 270         ptrs.push_back(h->nativeObj());
 271         break;
 272       case HeaderKind::Packed:
 273       case HeaderKind::Mixed:
 274       case HeaderKind::Dict:
 275       case HeaderKind::Empty:
 276       case HeaderKind::VecArray:
 277       case HeaderKind::Keyset:
 278       case HeaderKind::Apc:
 279       case HeaderKind::Globals:
 280       case HeaderKind::Proxy:
 281       case HeaderKind::String:
 282       case HeaderKind::Resource:
 283       case HeaderKind::Ref:
 284       case HeaderKind::SmallMalloc:
 285       case HeaderKind::BigMalloc:
 286       case HeaderKind::Free:
 287         break;
 288       case HeaderKind::BigObj:
 289       case HeaderKind::Hole:
 290         assert(false && "forEachHeader skips these kinds");
 291         break;
 292     }
 293   });
 294   for (auto ptr : ptrs) {
 295     fn(ptr);
 296   }
 297 }
 298
 299 // information about heap objects, indexed by valid object starts.
 300 struct PtrMap {
 301   using Region = std::pair<const Header*, std::size_t>;
 302   static constexpr auto Mask = 0xffffffffffffULL; // 48 bit address space
 303
 304   void insert(const Header* h) {
 305     assert(!sorted_);
 306     regions_.emplace_back(h, h->size());
 307   }
 308
 309   const Region* region(const void* p) const {
 310     assert(sorted_);
 311     // Find the first region which begins beyond p.
 312     p = reinterpret_cast<void*>(uintptr_t(p) & Mask);
 313     auto it = std::upper_bound(regions_.begin(), regions_.end(), p,
 314       [](const void* p, const Region& region) {
 315         return p < region.first;
 316       });
 317     // If its the first region, p is before any region, so there's no
 318     // header. Otherwise, backup to the previous region.
 319     if (it == regions_.begin()) return nullptr;
 320     --it;
 321     // p can only potentially point within this previous region, so check that.
 322     return (uintptr_t(p) < uintptr_t(it->first) + it->second) ? &*it :
 323            nullptr;
 324   }
 325
 326   const Header* header(const void* p) const {
 327     auto r = region(p);
 328     return r ? r->first : nullptr;
 329   }
 330
 331   bool isHeader(const void* p) const {
 332     auto h = header(p);
 333     return h && h == p;
 334   }
 335
 336   size_t index(const Region* r) const {
 337     return r - &regions_[0];
 338   }
 339
 340   // where does this header sit in the regions_ vector?
 341   size_t index(const Header* h) const {
 342     assert(header(h));
 343     return region(h) - &regions_[0];
 344   }
 345
 346   void prepare() {
 347     assert(!sorted_);
 348     std::sort(regions_.begin(), regions_.end());
 349     assert(sanityCheck());
 350     sorted_ = true;
 351   }
 352
 353   size_t size() const {
 354     return regions_.size();
 355   }
 356
 357   template<class Fn> void iterate(Fn fn) const {
 358     for (auto& r : regions_) {
 359       fn(r.first, r.second);
 360     }
 361   }
 362
 363 private:
 364   bool sanityCheck() const {
 365     // Verify that all the regions are in increasing and non-overlapping order.
 366     void* last = nullptr;
 367     for (const auto& region : regions_) {
 368       if (!last || last <= region.first) {
 369         last = (void*)(uintptr_t(region.first) + region.second);
 370       } else {
 371         return false;
 372       }
 373     }
 374     return true;
 375   }
 376
 377   std::vector<std::pair<const Header*, std::size_t>> regions_;
 378   bool sorted_ = false;
 379 };
 380
 381 }
 382
 383 #endif