hphp/runtime/base/apc-gc-manager.cpp

   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 #include "hphp/runtime/base/apc-gc-manager.h"
  17 #include "hphp/runtime/base/apc-typed-value.h"
  18 #include "hphp/runtime/base/memory-manager.h"
  19 #include "hphp/runtime/base/mixed-array.h"
  20 #include "hphp/runtime/base/packed-array.h"
  21 #include "hphp/runtime/base/set-array.h"
  22 #include "hphp/runtime/base/string-data.h"
  23 #include "hphp/runtime/base/surprise-flags.h"
  24 #include "hphp/util/lock.h"
  25
  26 namespace HPHP {
  27
  28 TRACE_SET_MOD(apc);
  29
  30 //////////////////////////////////////////////////////////////////////
  31
  32 void APCGCManager::registerAllocation(void* start, void* end, APCHandle* root) {
  33   assertx(RuntimeOption::EvalGCForAPC);
  34   if (RuntimeOption::ServerExecutionMode()) {
  35     return; // Doesn't support server mode yet
  36   }
  37
  38   insert(std::pair<void*, void*>(start,end), root);
  39 }
  40
  41 void APCGCManager::registerPendingDeletion(APCHandle* root, const size_t size) {
  42   assertx(RuntimeOption::EvalGCForAPC);
  43   if (RuntimeOption::ServerExecutionMode()) {
  44     return; // Doesn't support server mode yet
  45   }
  46   if (RuntimeOption::ServerExecutionMode()) {
  47     // Root should be visible by default to implement asynchronous mark-sweep
  48     // But we don't need to do this in script mode
  49     WriteLock l3(visibleFromHeapLock);
  50     visibleFromHeap.insert(root);
  51   }
  52   // Recursively register all allocations belong to this root handle
  53   APCTypedValue::fromHandle(root)->registerUncountedAllocations();
  54   // Add root APCHandle into to-free list
  55   {
  56     WriteLock l1(candidateListLock);
  57     pendingSize.fetch_add(size, std::memory_order_relaxed);
  58     assertx(candidateList.count(root) == 0);
  59     candidateList.emplace(root, size);
  60   }
  61   FTRACE(1, "APCGCManager: increase used memory:{} by size:{}\n",
  62                                                 pendingSize.load(), size);
  63   /* TODO Task #20074509: API for global GC invoke */
  64   if (pendingSize.load() > someBar()) {
  65     // Bar is -vEval.GCForAPCBar, 10^9 by default
  66     invokeGlobalGC();
  67     FTRACE(2, "APCGCManager: GC flag set up!\n");
  68   }
  69 }
  70
  71 bool APCGCManager::excessedGCTriggerBar() {
  72   return pendingSize.load() > someBar();
  73 }
  74
  75 void APCGCManager::sweep() {
  76   assertx(RuntimeOption::EvalGCForAPC);
  77   if (RuntimeOption::ServerExecutionMode()) {
  78     return; // Doesn't support server mode yet
  79   }
  80   FTRACE(1, "Sweep! Pending size:{}\n", apcgcPendingSize());
  81   WriteLock l1(candidateListLock);
  82   WriteLock l2(rootMapLock);
  83   WriteLock l3(visibleFromHeapLock);
  84
  85   for (auto it = rootMap.begin() ; it != rootMap.end() ;) {
  86     auto cur = it++;
  87     APCHandle* root = cur->second;
  88     // If root is not visible from any heap
  89     if (visibleFromHeap.count(root) == 0) {
  90       auto candidate = candidateList.find(root);
  91       // If root haven't been freed before, free it
  92       if (candidate != candidateList.end()) {
  93         pendingSize.fetch_add(-candidate->second, std::memory_order_relaxed);
  94         // Remove the root from list, so we won't free it twice
  95         candidateList.erase(candidate);
  96         FTRACE(4, "Sweep! root:{}\n", (void*)root);
  97         // Free the root
  98         APCTypedValue::fromHandle(root)->deleteUncounted();
  99       }
 100       // Remove {allocation, root}
 101       rootMap.erase(cur);
 102     }
 103   }
 104   visibleFromHeap.clear();
 105 }
 106
 107 void APCGCManager::invokeGlobalGC() {
 108   /* TODO Task #20074509: API for global GC invoke */
 109   // For now, only schedule a GC for this thread
 110   setSurpriseFlag(PendingGCFlag);
 111 }
 112
 113 bool APCGCManager::mark(const void* ptr) {
 114   assertx(RuntimeOption::EvalGCForAPC);
 115   if (RuntimeOption::ServerExecutionMode()) {
 116     return false; // Doesn't support server mode yet
 117   }
 118
 119   if (ptr == nullptr) return false;
 120   auto root = getRootAPCHandle(ptr); // Required l2 here
 121   if (root != nullptr) {
 122     // Require lock only when root has been found
 123     WriteLock l3(visibleFromHeapLock); // Require l3 after require l2
 124     visibleFromHeap.insert(root);
 125     FTRACE(4, "Mark root {} for ptr: {}\n", (const void*)root, ptr);
 126     return true;
 127   } else {
 128     FTRACE(4, "Root for ptr: {} not found\n", ptr);
 129     return false;
 130   }
 131 }
 132
 133 void APCGCManager::freeAPCHandles(const std::vector<APCHandle*>& v) {
 134   assertx(RuntimeOption::EvalGCForAPC);
 135   if (RuntimeOption::ServerExecutionMode()) {
 136     // Doesn't support server mode yet
 137     // But it still needs to finish the Treadmill's job because Treadmill
 138     // won't free the handles now
 139     for (auto handle : v) {
 140       APCTypedValue::fromHandle(handle)->deleteUncounted();
 141     }
 142     return;
 143   }
 144   // This lock will be blocked by current sweeping
 145   WriteLock l1(candidateListLock);
 146   FTRACE(4, "Treadmill asks APCGCManager to free! size: {}\n",v.size());
 147   for (auto handle : v) {
 148     auto it = candidateList.find(handle);
 149     // If root haven't been freed before, free it
 150     if (it != candidateList.end()) {
 151       pendingSize.fetch_add(-it->second, std::memory_order_relaxed);
 152       // Remove the root from list, so we won't free it twice
 153       candidateList.erase(it);
 154       FTRACE(4, "Sweep! root:{}\n", (void*)handle);
 155       APCTypedValue::fromHandle(handle)->deleteUncounted();
 156     }
 157   }
 158 }
 159
 160 void APCGCManager::insert(Allocation r, APCHandle* root) {
 161   WriteLock l2(rootMapLock);
 162   FTRACE(4, "Insert {} {} with root {}\n",
 163                             (void*)r.first, (void*)r.second, (void*)root);
 164   rootMap.emplace(r, root);
 165 }
 166
 167 /*
 168  * Find a [stAddress,edAddress) contains ptr, return the root
 169 */
 170 APCHandle* APCGCManager::getRootAPCHandle(const void* ptr) {
 171   ReadLock l2(rootMapLock);
 172   auto it = rootMap.upper_bound(Allocation(ptr, ptr));
 173   // it and (it-1) both possibly contain ptr
 174   if (ptr >= it->first.first && ptr < it->first.second) return it->second;
 175   if (it == rootMap.begin()) return nullptr;
 176   --it;
 177   return (ptr >= it->first.first && ptr < it->first.second)
 178     ? it->second
 179     : nullptr;
 180 }
 181
 182 APCGCManager& APCGCManager::getInstance() {
 183   static APCGCManager mm;
 184   return mm;
 185 }
 186 //////////////////////////////////////////////////////////////////////
 187 // All gc-apc related traverse functions here
 188
 189 /*
 190  * Recursively register {allocation, rootAPCHandle} with APCGCManager
 191  * according to the type of tv
 192 */
 193 ALWAYS_INLINE
 194 void RegisterUncountedTvAllocations(TypedValue& tv, APCHandle* rootAPCHandle) {
 195   if (isStringType(tv.m_type)) {
 196     assert(!tv.m_data.pstr->isRefCounted());
 197     if (tv.m_data.pstr->isUncounted()) {
 198       tv.m_data.pstr->registerUncountedAllocation(rootAPCHandle);
 199     }
 200     return;
 201   }
 202   if (isArrayLikeType(tv.m_type)) {
 203     auto arr = tv.m_data.parr;
 204     assert(!arr->isRefCounted());
 205     if (!arr->isStatic()) {
 206       if (arr->hasPackedLayout()) {
 207         PackedArray::RegisterUncountedAllocations(arr, rootAPCHandle);
 208       } else {
 209         MixedArray::RegisterUncountedAllocations(arr, rootAPCHandle);
 210       }
 211     }
 212     return;
 213   }
 214   assertx(!isRefcountedType(tv.m_type));
 215 }
 216
 217 /*
 218  * Treadmill call this method when apc_delete()/apc_store() is trying to
 219  * delete/overwrite an APC uncounted data.
 220  * According to the type, StringData/ArrayData::registerUncountedAllocations()
 221  * will be called to recursively register all {allocation, root}
 222  * with APCGCManager
 223 */
 224 void APCTypedValue::registerUncountedAllocations() {
 225   assert(m_handle.isUncounted());
 226   assert(RuntimeOption::EvalGCForAPC);
 227   auto kind = m_handle.kind();
 228
 229   assert(kind == APCKind::UncountedString ||
 230          kind == APCKind::UncountedArray ||
 231          kind == APCKind::UncountedVec ||
 232          kind == APCKind::UncountedDict ||
 233          kind == APCKind::UncountedKeyset);
 234    if (kind == APCKind::UncountedString) {
 235      m_data.str->registerUncountedAllocation(&m_handle);
 236    } else if (kind == APCKind::UncountedArray) {
 237      assert(m_data.arr->isPHPArray());
 238      if (m_data.arr->hasPackedLayout()) {
 239        auto arr = m_data.arr;
 240        PackedArray::RegisterUncountedAllocations(arr, &m_handle);
 241        return;
 242      } else {
 243        auto arr = m_data.arr;
 244        MixedArray::RegisterUncountedAllocations(arr, &m_handle);
 245        return;
 246      }
 247    } else if (kind == APCKind::UncountedVec) {
 248      auto vec = m_data.vec;
 249      assert(vec->isVecArray());
 250      PackedArray::RegisterUncountedAllocations(vec, &m_handle);
 251      return;
 252    } else if (kind == APCKind::UncountedDict) {
 253      auto dict = m_data.dict;
 254      assert(dict->isDict());
 255      MixedArray::RegisterUncountedAllocations(dict, &m_handle);
 256      return;
 257    } else if (kind == APCKind::UncountedKeyset) {
 258      auto keyset = m_data.keyset;
 259      assert(keyset->isKeyset());
 260      SetArray::RegisterUncountedAllocations(keyset, &m_handle);
 261      return;
 262    }
 263 }
 264
 265
 266 // Register {allocation, rootAPCHandle} with APCGCManager
 267 void StringData::registerUncountedAllocation(APCHandle* rootAPCHandle) {
 268   assert(checkSane() && isUncounted());
 269   assert(isFlat());
 270   assert(RuntimeOption::EvalGCForAPC);
 271   // [this, this + 1) doesn't give us address of the string
 272   // But we assume reference point only at the header of a StringData
 273   APCGCManager::getInstance().registerAllocation(this,
 274                                         (char*)this + this->heapSize(),
 275                                         rootAPCHandle);
 276 }
 277
 278 /*
 279  * Recursively register {allocation, rootAPCHandle} with APCGCManager
 280  * for all allocations in ad
 281  */
 282 void PackedArray::RegisterUncountedAllocations(ArrayData* ad,
 283                                           APCHandle* rootAPCHandle) {
 284   assert(checkInvariants(ad));
 285   assert(ad->isUncounted());
 286
 287   auto const data = packedData(ad);
 288   auto const stop = data + ad->m_size;
 289   for (auto ptr = data; ptr != stop; ++ptr) {
 290     RegisterUncountedTvAllocations(*ptr, rootAPCHandle);
 291   }
 292   assert(!has_strong_iterator(ad));
 293   assert(RuntimeOption::EvalGCForAPC);
 294   APCGCManager::getInstance().registerAllocation(ad,
 295                                         (char*)ad + PackedArray::heapSize(ad),
 296                                         rootAPCHandle);
 297 }
 298
 299 /*
 300  * Recursively register {allocation, rootAPCHandle} with APCGCManager
 301  * for all allocations in ad
 302  */
 303 void MixedArray::RegisterUncountedAllocations(ArrayData* in,
 304                                           APCHandle* rootAPCHandle) {
 305   auto const ad = asMixed(in);
 306   assert(ad->isUncounted());
 307   if (!ad->isZombie()) {
 308     auto const data = ad->data();
 309     auto const stop = data + ad->m_used;
 310
 311     for (auto ptr = data; ptr != stop; ++ptr) {
 312       if (isTombstone(ptr->data.m_type)) continue;
 313       if (ptr->hasStrKey()) {
 314         assert(!ptr->skey->isRefCounted());
 315         if (ptr->skey->isUncounted()) {
 316           ptr->skey->registerUncountedAllocation(rootAPCHandle);
 317         }
 318       }
 319       RegisterUncountedTvAllocations(ptr->data, rootAPCHandle);
 320     }
 321     assert(!has_strong_iterator(ad));
 322   }
 323   assert(RuntimeOption::EvalGCForAPC);
 324   APCGCManager::getInstance().registerAllocation(ad,
 325                                         (char*)ad + ad->heapSize(),
 326                                         rootAPCHandle);
 327 }
 328
 329 /*
 330  * Recursively register {allocation, rootAPCHandle} with APCGCManager
 331  * for all allocations in ad
 332  */
 333 void SetArray::RegisterUncountedAllocations(ArrayData* in,
 334                                         APCHandle* rootAPCHandle) {
 335   assert(in->isUncounted());
 336   auto const ad = asSet(in);
 337
 338   if (!ad->isZombie()) {
 339     auto const elms = ad->data();
 340     auto const used = ad->m_used;
 341     for (uint32_t i = 0; i < used; ++i) {
 342       auto& elm = elms[i];
 343       if (UNLIKELY(elm.isTombstone())) continue;
 344       assert(!elm.isEmpty());
 345       if (elm.hasStrKey()) {
 346         auto const skey = elm.strKey();
 347         assert(!skey->isRefCounted());
 348         if (skey->isUncounted()) {
 349           skey->registerUncountedAllocation(rootAPCHandle);
 350         }
 351       }
 352     }
 353     assert(!has_strong_iterator(ad));
 354   }
 355   assert(RuntimeOption::EvalGCForAPC);
 356   APCGCManager::getInstance().registerAllocation(ad,
 357                                         (char*)ad + ad->heapSize(),
 358                                         rootAPCHandle);
 359 }
 360 //////////////////////////////////////////////////////////////////////
 361 }