hphp/runtime/base/concurrent-shared-store.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
  17 #include "hphp/runtime/base/concurrent-shared-store.h"
  18
  19 #include <mutex>
  20 #include <set>
  21 #include <string>
  22 #include <vector>
  23 #include <folly/Format.h>
  24
  25 #include "hphp/util/logger.h"
  26 #include "hphp/util/timer.h"
  27 #include "hphp/util/trace.h"
  28
  29 #include "hphp/runtime/base/variable-serializer.h"
  30 #include "hphp/runtime/base/variable-unserializer.h"
  31 #include "hphp/runtime/base/apc-handle-defs.h"
  32 #include "hphp/runtime/base/apc-object.h"
  33 #include "hphp/runtime/base/apc-stats.h"
  34 #include "hphp/runtime/base/apc-file-storage.h"
  35 #include "hphp/runtime/ext/apc/ext_apc.h"
  36 #include "hphp/runtime/ext/apc/snapshot.h"
  37 #include "hphp/runtime/vm/treadmill.h"
  38
  39 using folly::SharedMutex;
  40
  41 namespace HPHP {
  42
  43 TRACE_SET_MOD(apc);
  44
  45 //////////////////////////////////////////////////////////////////////
  46
  47 namespace {
  48
  49 //////////////////////////////////////////////////////////////////////
  50
  51 bool check_noTTL(const char* key, size_t keyLen) {
  52   for (auto& listElem : apcExtension::NoTTLPrefix) {
  53     auto const prefix = listElem.c_str();
  54     auto const prefixLen = listElem.size();
  55     if (keyLen >= prefixLen && memcmp(key, prefix, prefixLen) == 0) {
  56       return true;
  57     }
  58   }
  59   return false;
  60 }
  61
  62 #ifdef HPHP_TRACE
  63 std::string show(const StoreValue& sval) {
  64   return sval.data().left() ?
  65     folly::sformat("size {} kind {}", sval.dataSize, (int)sval.getKind()) :
  66     folly::sformat("size {} serialized", std::abs(sval.dataSize));
  67 }
  68 #endif
  69
  70 //////////////////////////////////////////////////////////////////////
  71
  72 }
  73
  74 //////////////////////////////////////////////////////////////////////
  75
  76 void StoreValue::set(APCHandle* v, int64_t ttl) {
  77   setHandle(v);
  78   mtime = time(nullptr);
  79   if (c_time == 0)  c_time = mtime;
  80   expire = ttl ? mtime + ttl : 0;
  81 }
  82
  83 bool StoreValue::expired() const {
  84   // For primed values, 'expire' is not valid to read.
  85   if (c_time == 0) return false;
  86   return expire && time(nullptr) >= expire;
  87 }
  88
  89 //////////////////////////////////////////////////////////////////////
  90
  91 EntryInfo::Type EntryInfo::getAPCType(const APCHandle* handle) {
  92   switch (handle->kind()) {
  93     case APCKind::Uninit:
  94     case APCKind::Null:
  95     case APCKind::Bool:
  96     case APCKind::Int:
  97     case APCKind::Double:
  98     case APCKind::StaticString:
  99     case APCKind::StaticArray:
 100     case APCKind::StaticVec:
 101     case APCKind::StaticDict:
 102     case APCKind::StaticKeyset:
 103       return EntryInfo::Type::Uncounted;
 104     case APCKind::UncountedString:
 105       return EntryInfo::Type::UncountedString;
 106     case APCKind::SharedString:
 107       return EntryInfo::Type::APCString;
 108     case APCKind::UncountedArray:
 109       return EntryInfo::Type::UncountedArray;
 110     case APCKind::UncountedVec:
 111       return EntryInfo::Type::UncountedVec;
 112     case APCKind::UncountedDict:
 113       return EntryInfo::Type::UncountedDict;
 114     case APCKind::UncountedKeyset:
 115       return EntryInfo::Type::UncountedKeyset;
 116     case APCKind::SerializedArray:
 117       return EntryInfo::Type::SerializedArray;
 118     case APCKind::SerializedVec:
 119       return EntryInfo::Type::SerializedVec;
 120     case APCKind::SerializedDict:
 121       return EntryInfo::Type::SerializedDict;
 122     case APCKind::SerializedKeyset:
 123       return EntryInfo::Type::SerializedKeyset;
 124     case APCKind::SharedVec:
 125       return EntryInfo::Type::APCVec;
 126     case APCKind::SharedDict:
 127       return EntryInfo::Type::APCDict;
 128     case APCKind::SharedKeyset:
 129       return EntryInfo::Type::APCKeyset;
 130     case APCKind::SharedArray:
 131     case APCKind::SharedPackedArray:
 132     case APCKind::SharedVArray:
 133     case APCKind::SharedDArray:
 134       return EntryInfo::Type::APCArray;
 135     case APCKind::SerializedObject:
 136       return EntryInfo::Type::SerializedObject;
 137     case APCKind::SharedObject:
 138     case APCKind::SharedCollection:
 139       return EntryInfo::Type::APCObject;
 140   }
 141   not_reached();
 142 }
 143
 144 //////////////////////////////////////////////////////////////////////
 145
 146 /*
 147  * Read cache layer for frequently accessed but rarely updated APC entries.
 148  * Doesn't support APC values that require refcounting, i.e., it supports
 149  * the 'singletons' null, true, false and the uncounted array/string types.
 150  * Designed to be used to replicate a subset of ConcurrentTableSharedStore.
 151  * Keys can be filtered based on prefixes (apcExtension::HotKeyPrefix).
 152  * Lock-free; if a stored entry is cleared, its value must be kept alive for
 153  * duration of any requests in flight at that time (treadmill).
 154  *
 155  * Capacity is fixed at initialization. Does not check expiration on 'get',
 156  * so best used with periodic purge enabled (apcExtension::ExpireOnSets).
 157  *
 158  * TODO(11228222): Upper-bound the time between periodic purges.
 159  */
 160 struct HotCache {
 161   /*
 162    * Indices are never invalidated once assigned to a key (clearing an entry
 163    * does not actually erase the key from underlying array, just hides it).
 164    */
 165   using Idx = StoreValue::HotCacheIdx;
 166
 167   void initialize();
 168
 169   /*
 170    * If 'key' has an associated value in the cache, returns true and
 171    * sets 'value' (but leaves 'idx' in an undefined state).
 172    * Else, returns false, leaves 'value' unchanged, but fills 'idx' with
 173    * information about the failure to be passed to 'store'.
 174    */
 175   bool get(const StringData* key, Variant& value, Idx& idx) const;
 176
 177   /*
 178    * Try to add or update an entry (key, svar), if they both are eligible
 179    * and there is still room. 'idx' must be the result of a failed call
 180    * to 'get' for the same key. On success, updates sval->hotIndex to reference
 181    * the added/updated entry and returns true.
 182    */
 183   bool store(Idx idx, const StringData* key,
 184              APCHandle* svar, const StoreValue* sval);
 185
 186   /*
 187    * Clear the entry referenced by 'sval' (set by a call to 'store') if any.
 188    * Return false and do nothing if 'sval' does not reference any entry.
 189    * Safe to call concurrently and repeatedly (idempotent). The caller must
 190    * ensure the effects of any previous call to 'store' for this key are visible
 191    * before this methods reads from 'sval' (e.g., by only calling these methods
 192    * under read/write locks like ConcurrentTableSharedStore::get/store/erase).
 193    */
 194   bool clearValue(const StoreValue& sval) {
 195     return clearValueIdx(sval.hotIndex.load(std::memory_order_relaxed));
 196   }
 197
 198   /*
 199    * Consistent with 'get', only less output.
 200    */
 201   bool hasValue(const StringData* key) const;
 202
 203  private:
 204   // Uncounted ArrayData is stored 'unwrapped' to save one dereference.
 205   using HotValue = Either<APCHandle*,ArrayData*,either_policy::high_bit>;
 206   using HotValueRaw = HotValue::Opaque;
 207
 208   // Keys stored are char*, but lookup/insert always use StringData*.
 209   struct EqualityTester {
 210     bool operator()(const char* a, const StringData* b) const {
 211       // AtomicHashArray magic keys are < 0; valid pointers are > 0 and aligned.
 212       return reinterpret_cast<intptr_t>(a) > 0 &&
 213         wordsame(a, b->data(), b->size() + 1);
 214     }
 215   };
 216   struct Hasher {
 217     size_t operator()(const StringData* a) const { return a->hash(); }
 218   };
 219
 220   // Allocates keys on successful insertion. They are never erased/freed.
 221   struct KeyConverter {
 222     const char* operator()(const StringData* sd) const {
 223       if (sd->isStatic()) return sd->data();
 224       auto const nbytes = sd->size() + 1;
 225       auto const dst = malloc_huge(nbytes);
 226       assertx((reinterpret_cast<uintptr_t>(dst) & 7) == 0);
 227       memcpy(dst, sd->data(), nbytes);
 228       return reinterpret_cast<const char*>(dst);
 229     }
 230   };
 231   using HotMap = folly::AtomicHashArray<const char*, std::atomic<HotValueRaw>,
 232                                         Hasher, EqualityTester,
 233                                         HugeAllocator<char>,
 234                                         folly::AtomicHashArrayLinearProbeFcn,
 235                                         KeyConverter>;
 236
 237   static bool supportedKind(const APCHandle* h) {
 238     return h->isSingletonKind() || h->isUncounted();
 239   }
 240
 241   static HotValueRaw makeRawValue(APCHandle* h) {
 242     assertx(h != nullptr && supportedKind(h));
 243     HotValue v = [&] {
 244       switch (h->kind()) {
 245         case APCKind::UncountedArray:
 246           return HotValue{APCTypedValue::fromHandle(h)->getArrayData()};
 247         case APCKind::UncountedVec:
 248           return HotValue{APCTypedValue::fromHandle(h)->getVecData()};
 249         case APCKind::UncountedDict:
 250           return HotValue{APCTypedValue::fromHandle(h)->getDictData()};
 251         case APCKind::UncountedKeyset:
 252           return HotValue{APCTypedValue::fromHandle(h)->getKeysetData()};
 253         default:
 254           return HotValue{h};
 255       }
 256     }();
 257     return v.toOpaque();
 258   }
 259
 260   static bool rawValueToLocal(HotValueRaw vraw, Variant& value) {
 261     HotValue v = HotValue::fromOpaque(vraw);
 262     if (ArrayData* ad = v.right()) {
 263       value = Variant{
 264         ad, ad->toPersistentDataType(), Variant::PersistentArrInit{}
 265       };
 266       return true;
 267     }
 268     if (APCHandle* h = v.left()) {
 269       value = h->toLocal();
 270       return true;
 271     }
 272     return false;
 273   }
 274
 275   bool clearValueIdx(Idx idx);
 276
 277   // True iff the given key string is eligible to be considered hot.
 278   bool maybeHot(const char* key) const {
 279     for (auto p : apcExtension::HotPrefix) {
 280       if (strncmp(key, p.data(), p.size()) == 0) {
 281         return true;
 282       }
 283     }
 284     return false;
 285   }
 286
 287   // True if the key *might* be eligible (with false positives).
 288   bool maybeHotFast(const StringData* sd) const {
 289     // TODO(11227362): Avoid size check if we can assume zero-padding.
 290     return sd->size() >= sizeof(uint64_t) &&
 291       (readPrefix64(sd->data()) & m_hotPrefixMask) == 0;
 292   }
 293
 294   // Return the bits that were *not* set in any of the prefixes' first 8 chars.
 295   static uint64_t computeFastPrefixMask(std::vector<std::string> prefs) {
 296     uint64_t any = 0;
 297     for (auto& p : prefs) {
 298       while (p.size() < sizeof(uint64_t)) p += '\xff';
 299       any |= readPrefix64(p.data());
 300     }
 301     return ~any;
 302   }
 303
 304   static uint64_t readPrefix64(const char* s) {
 305     uint64_t result;
 306     memcpy(&result, s, sizeof(result));
 307     return result;
 308   }
 309
 310   HotMap::SmartPtr m_hotMap;
 311   uint64_t m_hotPrefixMask{~0ull};
 312   std::atomic<bool> m_isFull{false};
 313 };
 314 HotCache s_hotCache;
 315
 316 void HotCache::initialize() {
 317   if (!m_hotMap) {
 318     HotMap::Config config;
 319     config.maxLoadFactor = apcExtension::HotLoadFactor;
 320     /*
 321      * Ensure we detect a fully loaded map in time. (AHA's default of
 322      * 1000 * hundreds of homogeneous writers => O(100,000) entries before
 323      * first real check.)
 324      *
 325      * TODO(11227990): Use maxSize/(actual thread count), or make AHA dynamic.
 326      */
 327     config.entryCountThreadCacheSize = 100;
 328     auto const maxSize = apcExtension::HotSize;
 329     m_hotMap = HotMap::create(maxSize, config);
 330
 331     auto const& prefs = apcExtension::HotPrefix;
 332     m_hotPrefixMask = computeFastPrefixMask(prefs);
 333   }
 334 }
 335
 336 bool HotCache::hasValue(const StringData* key) const {
 337   if (!maybeHotFast(key)) return false;
 338   HotMap::const_iterator it = m_hotMap->find(key);
 339   return it != m_hotMap->end() &&
 340     !HotValue::fromOpaque(it->second.load(std::memory_order_relaxed)).isNull();
 341 }
 342
 343 bool HotCache::get(const StringData* key, Variant& value, Idx& idx) const {
 344   if (!maybeHotFast(key)) {
 345     idx = StoreValue::kHotCacheKnownIneligible;
 346     return false;
 347   }
 348   auto it = m_hotMap->find(key);
 349   if (it == m_hotMap->end()) {
 350     idx = StoreValue::kHotCacheUnknown;
 351     return false;
 352   }
 353   if (rawValueToLocal(it->second.load(std::memory_order_relaxed), value)) {
 354     return true;
 355   }
 356   idx = it.getIndex();
 357   return false;
 358 }
 359
 360 bool HotCache::store(Idx idx, const StringData* key,
 361                      APCHandle* svar, const StoreValue* sval) {
 362   if (idx == StoreValue::kHotCacheKnownIneligible) return false;
 363   if (!svar || !supportedKind(svar)) return false;
 364   auto raw = makeRawValue(svar);
 365   if (idx == StoreValue::kHotCacheUnknown) {
 366     if (!maybeHot(key->data())) return false;
 367     if (m_isFull.load(std::memory_order_relaxed)) return false;
 368     auto p = m_hotMap->emplace(key, raw);
 369     if (p.first == m_hotMap->end()) {
 370       m_isFull.store(true, std::memory_order_relaxed);
 371       return false;
 372     }
 373     idx = p.first.getIndex();
 374   }
 375   assertx(idx >= 0);
 376   sval->hotIndex.store(idx, std::memory_order_relaxed);
 377   m_hotMap->findAt(idx)->second.store(raw, std::memory_order_relaxed);
 378   return true;
 379 }
 380
 381 bool HotCache::clearValueIdx(Idx idx) {
 382   if (idx == StoreValue::kHotCacheUnknown) return false;
 383   assertx(idx >= 0);
 384   auto it = m_hotMap->findAt(idx);
 385   it->second.store(HotValue(nullptr).toOpaque(), std::memory_order_relaxed);
 386   return true;
 387 }
 388
 389 //////////////////////////////////////////////////////////////////////
 390
 391 bool ConcurrentTableSharedStore::clear() {
 392   SharedMutex::WriteHolder l(m_lock);
 393   for (Map::iterator iter = m_vars.begin(); iter != m_vars.end();
 394        ++iter) {
 395     s_hotCache.clearValue(iter->second);
 396     iter->second.data().match(
 397       [&] (APCHandle* handle) {
 398         handle->unreferenceRoot(iter->second.dataSize);
 399       },
 400       [&] (char*) {}
 401     );
 402     const void* vpKey = iter->first;
 403     free(const_cast<void*>(vpKey));
 404   }
 405   m_vars.clear();
 406   return true;
 407 }
 408
 409 bool ConcurrentTableSharedStore::eraseKey(const String& key) {
 410   assertx(!key.isNull());
 411   return eraseImpl(tagStringData(key.get()), false, 0, nullptr);
 412 }
 413
 414 /*
 415  * The Map::accessor here establishes a write lock, which means that other
 416  * threads, protected by read locks through Map::const_accessor, will not
 417  * read erased values from APC.
 418  *
 419  * The ReadLock here is to sync with clear(), which only has a WriteLock,
 420  * not a specific accessor.
 421  */
 422 bool ConcurrentTableSharedStore::eraseImpl(const char* key,
 423                                            bool expired,
 424                                            int64_t oldestLive,
 425                                            ExpMap::accessor* expAcc) {
 426   assertx(key);
 427
 428   SharedMutex::ReadHolder l(m_lock);
 429   Map::accessor acc;
 430   if (!m_vars.find(acc, key)) {
 431     return false;
 432   }
 433   if (expired && !acc->second.expired()) {
 434     return false;
 435   }
 436
 437   auto& storeVal = acc->second;
 438   bool wasCached = s_hotCache.clearValue(storeVal);
 439
 440   if (auto const var = storeVal.data().left()) {
 441     APCStats::getAPCStats().removeAPCValue(storeVal.dataSize, var,
 442                                            storeVal.expire == 0, expired);
 443     /*
 444      * As an optimization, we eagerly delete uncounted values that expired
 445      * long ago. But HotCache does not check expiration on every 'get', so
 446      * any values previously cached there must take the usual treadmill route.
 447      */
 448     if (expired && storeVal.expire < oldestLive &&
 449         var->isUncounted() && !wasCached) {
 450       APCTypedValue::fromHandle(var)->deleteUncounted();
 451     } else {
 452       var->unreferenceRoot(storeVal.dataSize);
 453     }
 454   } else {
 455     assertx(!expired);  // primed keys never say true to expired()
 456   }
 457
 458   FTRACE(2, "Remove {} {}\n", acc->first, show(acc->second));
 459   APCStats::getAPCStats().removeKey(strlen(acc->first));
 460   const void* vpkey = acc->first;
 461   /*
 462    * Note that we have a delicate situation here; purgeExpired obtains
 463    * the ExpMap accessor, and then the Map accessor, while eraseImpl
 464    * (called from other sites) apparently obtains the Map accessor
 465    * followed by the ExpMap accessor.
 466    *
 467    * This does not result in deadlock, because the Map accessor is
 468    * released by m_vars.erase. But we need this ordering to ensure
 469    * that as long as you hold an accessor to m_expMap, its key
 470    * converted to a char* will be a valid c-string.
 471    */
 472   m_vars.erase(acc);
 473   if (expAcc) {
 474     m_expMap.erase(*expAcc);
 475   } else {
 476     /*
 477      * Note that we can't just call m_expMap.erase(intptr_t(vpkey))
 478      * here. That will remove the element and not block, even if
 479      * we hold an ExpMap::accessor to the element in another thread,
 480      * which would allow us to proceed and free vpkey.
 481      */
 482     ExpMap::accessor eAcc;
 483     if (m_expMap.find(eAcc, intptr_t(vpkey))) {
 484       m_expMap.erase(eAcc);
 485     }
 486   }
 487   free(const_cast<void*>(vpkey));
 488   return true;
 489 }
 490
 491 // Should be called outside m_lock
 492 void ConcurrentTableSharedStore::purgeExpired() {
 493   if (m_purgeCounter.fetch_add(1, std::memory_order_relaxed) %
 494       apcExtension::PurgeFrequency != 0) {
 495     return;
 496   }
 497   time_t now = time(nullptr);
 498   int64_t oldestLive = apcExtension::UseUncounted ?
 499       HPHP::Treadmill::getOldestStartTime() : 0;
 500   ExpirationPair tmp;
 501   int i = 0;
 502   while (apcExtension::PurgeRate < 0 || i < apcExtension::PurgeRate) {
 503     if (!m_expQueue.try_pop(tmp)) {
 504       break;
 505     }
 506     if (tmp.second > now) {
 507       m_expQueue.push(tmp);
 508       break;
 509     }
 510     if (UNLIKELY(tmp.first ==
 511                  intptr_t(apcExtension::FileStorageFlagKey.c_str()))) {
 512       adviseOut();
 513       tmp.second = time(nullptr) + apcExtension::FileStorageAdviseOutPeriod;
 514       m_expQueue.push(tmp);
 515       continue;
 516     }
 517     ExpMap::accessor acc;
 518     if (m_expMap.find(acc, tmp.first)) {
 519       eraseImpl((char*)tmp.first, true, oldestLive, &acc);
 520     }
 521     ++i;
 522   }
 523   FTRACE(1, "Expired {} entries", i);
 524 }
 525
 526 bool ConcurrentTableSharedStore::handlePromoteObj(const String& key,
 527                                                   APCHandle* svar,
 528                                                   const Variant& value) {
 529   auto const pair = APCObject::MakeAPCObject(svar, value);
 530   if (!pair.handle) return false;
 531   auto const converted = pair.handle;
 532   auto const size = pair.size;
 533
 534   Map::accessor acc;
 535   if (!m_vars.find(acc, tagStringData(key.get()))) {
 536     // There is a chance another thread deletes the key when this thread is
 537     // converting the object. In that case, we just bail
 538     converted->unreferenceRoot(size);
 539     return false;
 540   }
 541
 542   // Our handle may not be same as `svar' here because some other thread may
 543   // have updated it already, check before updating.
 544   auto& sval = acc->second;
 545   auto const handle = sval.data().left();
 546   if (handle == svar && handle->kind() == APCKind::SerializedObject) {
 547     sval.setHandle(converted);
 548     APCStats::getAPCStats().updateAPCValue(
 549       converted, size, handle, sval.dataSize, sval.expire == 0, false);
 550     handle->unreferenceRoot(sval.dataSize);
 551     sval.dataSize = size;
 552     return true;
 553   }
 554
 555   converted->unreferenceRoot(size);
 556   return false;
 557 }
 558
 559 APCHandle* ConcurrentTableSharedStore::unserialize(const String& key,
 560                                                    StoreValue* sval) {
 561   auto const sAddr = sval->data().right();
 562   assertx(sAddr != nullptr);
 563   /*
 564     This method is special, since another thread T may concurrently
 565     attempt to 'get' this entry while we're unserializing it. If T
 566     observes sval->data with a cleared tag, it will proceed without
 567     any further locking (it only has a const_accessor).
 568
 569     Thus, this method must ensure that the tag of sval->data is cleared
 570     only *after* sval is in a fully consistent unserialized state.
 571    */
 572
 573   try {
 574     auto const sType =
 575       apcExtension::EnableApcSerialize
 576         ? VariableUnserializer::Type::APCSerialize
 577         : VariableUnserializer::Type::Internal;
 578
 579     VariableUnserializer vu(sAddr, sval->getSerializedSize(), sType);
 580     if (sval->readOnly) vu.setReadOnly();
 581     Variant v = vu.unserialize();
 582     auto const pair = APCHandle::Create(v, sval->isSerializedObj(),
 583       APCHandleLevel::Outer, false);
 584     sval->dataSize = pair.size;
 585     sval->setHandle(pair.handle);  // Publish unserialized value (see 'get').
 586     APCStats::getAPCStats().addAPCValue(pair.handle, pair.size, true);
 587     return pair.handle;
 588   } catch (ResourceExceededException&) {
 589     throw;
 590   } catch (Exception& e) {
 591     raise_notice("APC Primed fetch failed: key %s (%s).",
 592                  key.c_str(), e.getMessage().c_str());
 593     return nullptr;
 594   }
 595 }
 596
 597 bool ConcurrentTableSharedStore::get(const String& keyStr, Variant& value) {
 598   FTRACE(3, "Get {}\n", keyStr.get()->data());
 599   HotCache::Idx hotIdx;
 600   if (s_hotCache.get(keyStr.get(), value, hotIdx)) return true;
 601   const StoreValue *sval;
 602   APCHandle *svar = nullptr;
 603   SharedMutex::ReadHolder l(m_lock);
 604   bool expired = false;
 605   bool promoteObj = false;
 606   auto tag = tagStringData(keyStr.get());
 607   {
 608     Map::const_accessor acc;
 609     if (!m_vars.find(acc, tag)) {
 610       return false;
 611     }
 612     sval = &acc->second;
 613     if (sval->expired()) {
 614       // Because it only has a read lock on the data, deletion from
 615       // expiration has to happen after the lock is released
 616       expired = true;
 617     } else {
 618       if (auto const handle = sval->data().left()) {
 619         svar = handle;
 620       } else {
 621         std::lock_guard<SmallLock> sval_lock(sval->lock);
 622
 623         if (auto const handle = sval->data().left()) {
 624           svar = handle;
 625         } else {
 626           /*
 627            * Note that unserialize can run arbitrary php code via a __wakeup
 628            * routine, which could try to access this same key, and we're
 629            * holding various locks here.  This is only for promoting primed
 630            * values to in-memory values, so it's basically not a real
 631            * problem, but ... :)
 632            */
 633           svar = unserialize(keyStr, const_cast<StoreValue*>(sval));
 634           if (!svar) return false;
 635         }
 636       }
 637       assertx(sval->data().left() == svar);
 638       APCKind kind = sval->getKind();
 639       if (apcExtension::AllowObj &&
 640           (kind == APCKind::SerializedObject ||
 641            kind == APCKind::SharedObject ||
 642            kind == APCKind::SharedCollection) &&
 643           !svar->objAttempted()) {
 644         // Hold ref here for later promoting the object
 645         svar->referenceNonRoot();
 646         promoteObj = true;
 647       }
 648       value = sval->toLocal();
 649       if (!promoteObj) {
 650         /*
 651          * Successful slow-case lookup => add value to cache (if key and kind
 652          * are eligible and there is still room for it). Another thread may be
 653          * updating the same key concurrently, but ConcurrentTableSharedStore's
 654          * per-entry lock ensures it will agree on the value.
 655          */
 656         s_hotCache.store(hotIdx, keyStr.get(), svar, sval);
 657       }
 658     }
 659   }
 660   if (expired) {
 661     eraseImpl(tag, true,
 662               apcExtension::UseUncounted ?
 663               HPHP::Treadmill::getOldestStartTime() : 0, nullptr);
 664     return false;
 665   }
 666
 667   if (promoteObj)  {
 668     handlePromoteObj(keyStr, svar, value);
 669     // release the extra ref
 670     svar->unreferenceNonRoot();
 671   }
 672   return true;
 673 }
 674
 675 int64_t ConcurrentTableSharedStore::inc(const String& key, int64_t step,
 676                                         bool& found) {
 677   found = false;
 678   SharedMutex::ReadHolder l(m_lock);
 679
 680   Map::accessor acc;
 681   if (!m_vars.find(acc, tagStringData(key.get()))) {
 682     return 0;
 683   }
 684   auto& sval = acc->second;
 685   if (sval.expired()) return 0;
 686   /*
 687    * Inc only works on KindOfDouble or KindOfInt64, which are never kept in
 688    * file-backed storage from priming.  So we don't need to try to deserialize
 689    * anything or handle the case that sval.data is file-backed.
 690    */
 691   auto const oldHandle = sval.data().left();
 692   if (oldHandle == nullptr) return 0;
 693   if (oldHandle->kind() != APCKind::Int &&
 694       oldHandle->kind() != APCKind::Double) {
 695     return 0;
 696   }
 697
 698   // Currently a no-op, since HotCache doesn't store int/double.
 699   assertx(sval.hotIndex == StoreValue::kHotCacheUnknown);
 700   s_hotCache.clearValue(sval);
 701
 702   auto const ret = oldHandle->toLocal().toInt64() + step;
 703   auto const pair = APCHandle::Create(Variant(ret), false,
 704     APCHandleLevel::Outer, false);
 705   APCStats::getAPCStats().updateAPCValue(pair.handle, pair.size,
 706                                          oldHandle, sval.dataSize,
 707                                          sval.expire == 0, false);
 708   oldHandle->unreferenceRoot(sval.dataSize);
 709   sval.setHandle(pair.handle);
 710   sval.dataSize = pair.size;
 711   found = true;
 712   return ret;
 713 }
 714
 715 bool ConcurrentTableSharedStore::cas(const String& key, int64_t old,
 716                                      int64_t val) {
 717   SharedMutex::ReadHolder l(m_lock);
 718
 719   Map::accessor acc;
 720   if (!m_vars.find(acc, tagStringData(key.get()))) {
 721     return false;
 722   }
 723
 724   auto& sval = acc->second;
 725   if (sval.expired()) return false;
 726   s_hotCache.clearValue(sval);
 727   auto const oldHandle =
 728     sval.data().match([&](APCHandle* h) { return h; },
 729                       [&](char* /*file*/) { return unserialize(key, &sval); });
 730   if (!oldHandle || oldHandle->toLocal().toInt64() != old) {
 731     return false;
 732   }
 733
 734   auto const pair = APCHandle::Create(Variant(val), false,
 735     APCHandleLevel::Outer, false);
 736   APCStats::getAPCStats().updateAPCValue(pair.handle, pair.size,
 737                                          oldHandle, sval.dataSize,
 738                                          sval.expire == 0, false);
 739   oldHandle->unreferenceRoot(sval.dataSize);
 740   sval.setHandle(pair.handle);
 741   sval.dataSize = pair.size;
 742   return true;
 743 }
 744
 745 bool ConcurrentTableSharedStore::exists(const String& keyStr) {
 746   if (s_hotCache.hasValue(keyStr.get())) return true;
 747   const StoreValue *sval;
 748   SharedMutex::ReadHolder l(m_lock);
 749   bool expired = false;
 750   auto tag = tagStringData(keyStr.get());
 751   {
 752     Map::const_accessor acc;
 753     if (!m_vars.find(acc, tag)) {
 754       return false;
 755     } else {
 756       sval = &acc->second;
 757       if (sval->expired()) {
 758         // Because it only has a read lock on the data, deletion from
 759         // expiration has to happen after the lock is released
 760         expired = true;
 761       }
 762     }
 763   }
 764   if (expired) {
 765     eraseImpl(tag, true,
 766               apcExtension::UseUncounted ?
 767               HPHP::Treadmill::getOldestStartTime() : 0, nullptr);
 768     return false;
 769   }
 770   return true;
 771 }
 772
 773 static int64_t adjust_ttl(int64_t ttl, bool overwritePrime) {
 774   if (apcExtension::TTLLimit > 0 && !overwritePrime) {
 775     if (ttl == 0 || ttl > apcExtension::TTLLimit) {
 776       return apcExtension::TTLLimit;
 777     }
 778   }
 779   return ttl;
 780 }
 781
 782 bool ConcurrentTableSharedStore::add(const String& key,
 783                                      const Variant& val,
 784                                      int64_t ttl) {
 785   return storeImpl(key, val, ttl, false, true);
 786 }
 787
 788 void ConcurrentTableSharedStore::set(const String& key,
 789                                      const Variant& val,
 790                                      int64_t ttl) {
 791   storeImpl(key, val, ttl, true, true);
 792 }
 793
 794 void ConcurrentTableSharedStore::setWithoutTTL(const String& key,
 795                                                const Variant& val) {
 796   storeImpl(key, val, 0, true, false);
 797 }
 798
 799 bool ConcurrentTableSharedStore::storeImpl(const String& key,
 800                                            const Variant& value,
 801                                            int64_t ttl,
 802                                            bool overwrite,
 803                                            bool limit_ttl) {
 804   StoreValue *sval;
 805   auto keyLen = key.size();
 806   char* const kcp = strdup(key.data());
 807   {
 808   SharedMutex::ReadHolder l(m_lock);
 809   bool present;
 810   time_t expiry = 0;
 811   bool overwritePrime = false;
 812   {
 813     Map::accessor acc;
 814     APCHandle* current = nullptr;
 815     present = !m_vars.insert(acc, kcp);
 816     sval = &acc->second;
 817     if (present) {
 818       free(kcp);
 819       if (!overwrite && !sval->expired()) {
 820         return false;
 821       }
 822       /*
 823        * Simply clear the entry --- if it's truly hot, a successful non-cache
 824        * 'get' will soon update the entry with the new value.
 825        */
 826       s_hotCache.clearValue(*sval);
 827       sval->data().match(
 828         [&] (APCHandle* handle) {
 829           current = handle;
 830           // If ApcTTLLimit is set, then only primed keys can have
 831           // expire == 0.
 832           overwritePrime = sval->expire == 0;
 833         },
 834         [&] (char*) {
 835           // Was inFile, but won't be anymore.
 836           sval->clearData();
 837           sval->dataSize = 0;
 838           overwritePrime = true;
 839         }
 840       );
 841       FTRACE(2, "Update {} {}\n", acc->first, show(acc->second));
 842     } else {
 843       FTRACE(2, "Add {} {}\n", acc->first, show(acc->second));
 844       APCStats::getAPCStats().addKey(keyLen);
 845     }
 846
 847     int64_t adjustedTtl = adjust_ttl(ttl, overwritePrime || !limit_ttl);
 848     if (adjustedTtl > apcExtension::TTLMaxFinite ||
 849         check_noTTL(key.data(), key.size())) {
 850       adjustedTtl = 0;
 851     }
 852
 853     auto svar = APCHandle::Create(value, false, APCHandleLevel::Outer, false);
 854     if (current) {
 855       if (sval->expire == 0 && adjustedTtl != 0) {
 856         APCStats::getAPCStats().removeAPCValue(
 857           sval->dataSize, current, true, sval->expired());
 858         APCStats::getAPCStats().addAPCValue(svar.handle, svar.size, false);
 859       } else {
 860         APCStats::getAPCStats().updateAPCValue(
 861           svar.handle, svar.size, current, sval->dataSize,
 862           sval->expire == 0, sval->expired());
 863       }
 864       current->unreferenceRoot(sval->dataSize);
 865     } else {
 866       APCStats::getAPCStats().addAPCValue(svar.handle, svar.size, present);
 867     }
 868
 869     sval->set(svar.handle, adjustedTtl);
 870     sval->dataSize = svar.size;
 871     expiry = sval->expire;
 872     if (expiry) {
 873       auto ikey = intptr_t(acc->first);
 874       if (m_expMap.insert({ ikey, 0 })) {
 875         m_expQueue.push({ ikey, expiry });
 876       }
 877     }
 878   }
 879   }  // m_lock
 880   if (apcExtension::ExpireOnSets) {
 881     purgeExpired();
 882   }
 883
 884   return true;
 885 }
 886
 887 void ConcurrentTableSharedStore::prime(std::vector<KeyValuePair>&& vars) {
 888   SharedMutex::ReadHolder l(m_lock);
 889   // we are priming, so we are not checking existence or expiration
 890   for (unsigned int i = 0; i < vars.size(); i++) {
 891     const KeyValuePair &item = vars[i];
 892     Map::accessor acc;
 893     auto const keyLen = strlen(item.key);
 894     auto const copy = strdup(item.key);
 895     if (m_vars.insert(acc, copy)) {
 896       APCStats::getAPCStats().addPrimedKey(keyLen);
 897     } else {
 898       free(copy);
 899
 900       // We're going to overwrite what was there.
 901       auto& sval = acc->second;
 902       sval.data().match(
 903         [&] (APCHandle* handle) {
 904           handle->unreferenceRoot(sval.dataSize);
 905         },
 906         [&] (char*) {}
 907       );
 908       sval.clearData();
 909       sval.dataSize = 0;
 910       sval.expire   = 0;
 911     }
 912
 913     acc->second.readOnly = apcExtension::EnableConstLoad && item.readOnly;
 914     if (item.inMem()) {
 915       APCStats::getAPCStats().addAPCValue(item.value, item.sSize, true);
 916       acc->second.set(item.value, 0);
 917       acc->second.dataSize = item.sSize;
 918     } else {
 919       acc->second.tagged_data.store(item.sAddr, std::memory_order_release);
 920       acc->second.dataSize = item.sSize;
 921       APCStats::getAPCStats().addInFileValue(std::abs(acc->second.dataSize));
 922     }
 923     FTRACE(2, "Primed key {} {}\n", acc->first, show(acc->second));
 924   }
 925 }
 926
 927 bool ConcurrentTableSharedStore::constructPrime(const String& v,
 928                                                 KeyValuePair& item,
 929                                                 bool serialized) {
 930   if (s_apc_file_storage.getState() !=
 931       APCFileStorage::StorageState::Invalid &&
 932       (!v.get()->isStatic() || serialized)) {
 933     // StaticString for non-object should consume limited amount of space,
 934     // not worth going through the file storage
 935
 936     // TODO: currently we double serialize string for uniform handling later,
 937     // hopefully the unserialize won't be called often. We could further
 938     // optimize by storing more type info.
 939     String s = apc_serialize(v);
 940     char *sAddr = s_apc_file_storage.put(s.data(), s.size());
 941     if (sAddr) {
 942       item.sAddr = sAddr;
 943       item.sSize = serialized ? 0 - s.size() : s.size();
 944       return false;
 945     }
 946   }
 947   auto pair = APCHandle::Create(v, serialized, APCHandleLevel::Outer, false);
 948   item.value = pair.handle;
 949   item.sSize = pair.size;
 950   return true;
 951 }
 952
 953 bool ConcurrentTableSharedStore::constructPrime(const Variant& v,
 954                                                 KeyValuePair& item) {
 955   if (s_apc_file_storage.getState() !=
 956       APCFileStorage::StorageState::Invalid &&
 957       (isRefcountedType(v.getType()))) {
 958     // Only do the storage for ref-counted type
 959     String s = apc_serialize(v);
 960     char *sAddr = s_apc_file_storage.put(s.data(), s.size());
 961     if (sAddr) {
 962       item.sAddr = sAddr;
 963       item.sSize = s.size();
 964       return false;
 965     }
 966   }
 967   auto pair = APCHandle::Create(v, false, APCHandleLevel::Outer, false);
 968   item.value = pair.handle;
 969   item.sSize = pair.size;
 970   return true;
 971 }
 972
 973 void ConcurrentTableSharedStore::primeDone() {
 974   s_hotCache.initialize();
 975   if (s_apc_file_storage.getState() !=
 976       APCFileStorage::StorageState::Invalid) {
 977     s_apc_file_storage.seal();
 978     s_apc_file_storage.hashCheck();
 979   }
 980   // Schedule the adviseOut instead of doing it immediately, so that the
 981   // initial accesses to the primed keys are not too bad. Still, for
 982   // the keys in file, a deserialization from memory is required on first
 983   // access.
 984   ExpirationPair p(intptr_t(apcExtension::FileStorageFlagKey.c_str()),
 985                    time(nullptr) + apcExtension::FileStorageAdviseOutPeriod);
 986   m_expQueue.push(p);
 987
 988   for (auto iter = apcExtension::CompletionKeys.begin();
 989        iter != apcExtension::CompletionKeys.end(); ++iter) {
 990     Map::accessor acc;
 991     auto const copy = strdup(iter->c_str());
 992     if (!m_vars.insert(acc, copy)) {
 993       free(copy);
 994       return;
 995     }
 996     auto const pair =
 997       APCHandle::Create(Variant(1), false, APCHandleLevel::Outer, false);
 998     acc->second.set(pair.handle, 0);
 999     acc->second.dataSize = pair.size;
1000     APCStats::getAPCStats().addAPCValue(pair.handle, pair.size, true);
1001   }
1002 }
1003
1004 bool ConcurrentTableSharedStore::primeFromSnapshot(const char* filename) {
1005   m_snapshotLoader = std::make_unique<SnapshotLoader>();
1006   if (!m_snapshotLoader->tryInitializeFromFile(filename)) {
1007     m_snapshotLoader.reset();
1008     return false;
1009   }
1010   // TODO(9755815): APCFileStorage is redundant when using snapshot;
1011   // disable it at module loading time in this case.
1012   Logger::Info("Loading from snapshot file %s", filename);
1013   m_snapshotLoader->load(*this);
1014   primeDone();
1015   return true;
1016 }
1017
1018 void ConcurrentTableSharedStore::adviseOut() {
1019   if (s_apc_file_storage.getState() !=
1020       APCFileStorage::StorageState::Invalid) {
1021     s_apc_file_storage.adviseOut();
1022   }
1023   if (m_snapshotLoader.get()) {
1024     m_snapshotLoader->adviseOut();
1025   }
1026 }
1027
1028 ///////////////////////////////////////////////////////////////////////////////
1029 // debugging and info/stats support
1030
1031 EntryInfo ConcurrentTableSharedStore::makeEntryInfo(const char* key,
1032                                                     StoreValue* sval,
1033                                                     int64_t curr_time) {
1034   int32_t size;
1035   auto type = EntryInfo::Type::Unknown;
1036   auto const inMem = sval->data().match(
1037       [&](APCHandle* handle) {
1038         size = sval->dataSize;
1039         type = EntryInfo::getAPCType(handle);
1040         return true;
1041       },
1042       [&](char*) {
1043         size = sval->getSerializedSize();
1044         return false;
1045       });
1046
1047   int64_t ttl = 0;
1048   if (inMem && sval->expire) {
1049     ttl = sval->expire - curr_time;
1050     if (ttl == 0) ttl = 1; // don't want to confuse with primed keys
1051   }
1052
1053   return EntryInfo(key, inMem, size, ttl, type, sval->c_time, sval->mtime);
1054 }
1055
1056 std::vector<EntryInfo> ConcurrentTableSharedStore::getEntriesInfo() {
1057   auto entries = std::vector<EntryInfo>{};
1058
1059   int64_t curr_time = time(nullptr);
1060   entries.reserve(m_vars.size() + 1000);
1061
1062   {
1063     SharedMutex::WriteHolder l(m_lock);
1064     for (Map::iterator iter = m_vars.begin(); iter != m_vars.end(); ++iter) {
1065       entries.push_back(
1066           makeEntryInfo(iter->first, &iter->second, curr_time));
1067     }
1068   }
1069   std::sort(entries.begin(), entries.end(),
1070             [] (const EntryInfo& e1, const EntryInfo& e2) {
1071               return e1.key < e2.key; });
1072   return entries;
1073 }
1074
1075 void ConcurrentTableSharedStore::dumpKeyAndValue(std::ostream & out) {
1076   SharedMutex::WriteHolder l(m_lock);
1077   out << "Total " << m_vars.size() << std::endl;
1078   for (Map::iterator iter = m_vars.begin(); iter != m_vars.end(); ++iter) {
1079     const char *key = iter->first;
1080     out << key;
1081     out << " #### ";
1082     const StoreValue *sval = &iter->second;
1083     if (!sval->expired()) {
1084       auto const value = sval->data().match(
1085         [&] (APCHandle* handle) {
1086           return handle->toLocal();
1087         },
1088         [&] (char* sAddr) {
1089           // we need unserialize and serialize again because the format was
1090           // APCSerialize
1091           return apc_unserialize(sAddr, sval->getSerializedSize());
1092         }
1093       );
1094
1095       try {
1096         auto valS = internal_serialize(value);
1097         out << valS.toCppString();
1098       } catch (const Exception& e) {
1099         out << "Exception: " << e.what();
1100       }
1101     }
1102
1103     out << std::endl;
1104   }
1105 }
1106
1107 static void dumpEntriesInfo(std::vector<EntryInfo> entries, std::ostream& out) {
1108   out << "key inmem size ttl type\n";
1109   for (auto entry : entries) {
1110     out << entry.key << " "
1111         << static_cast<int32_t>(entry.inMem) << " "
1112         << entry.size << " "
1113         << entry.ttl << " "
1114         << static_cast<int32_t>(entry.type) << '\n';
1115   }
1116 }
1117
1118 void ConcurrentTableSharedStore::dump(std::ostream& out, DumpMode dumpMode) {
1119   Logger::Info("dumping apc");
1120
1121   switch (dumpMode) {
1122   case DumpMode::KeyAndValue:
1123     dumpKeyAndValue(out);
1124     break;
1125
1126   case DumpMode::KeyOnly:
1127     for (auto& e : getEntriesInfo()) {
1128       out << e.key << '\n';
1129     }
1130     break;
1131
1132   case DumpMode::KeyAndMeta:
1133     dumpEntriesInfo(getEntriesInfo(), out);
1134     break;
1135   }
1136
1137   Logger::Info("dumping apc done");
1138 }
1139
1140 void ConcurrentTableSharedStore::dumpRandomKeys(std::ostream& out,
1141                                                 uint32_t count) {
1142   dumpEntriesInfo(sampleEntriesInfo(count), out);
1143 }
1144
1145 std::vector<EntryInfo>
1146 ConcurrentTableSharedStore::sampleEntriesInfo(uint32_t count) {
1147   SharedMutex::WriteHolder l(m_lock);
1148   if (m_vars.empty()) {
1149     Logger::Warning("No APC entries sampled (empty store)");
1150     return std::vector<EntryInfo>();
1151   }
1152   std::vector<EntryInfo> samples;
1153   for (; count > 0; count--) {
1154     if (!m_vars.getRandomAPCEntry(samples)) {
1155       Logger::Warning("No APC entries sampled (incompatible TBB library)");
1156       return std::vector<EntryInfo>();
1157     }
1158   }
1159   return samples;
1160 }
1161
1162 template<typename Key, typename T, typename HashCompare>
1163 bool ConcurrentTableSharedStore
1164       ::APCMap<Key,T,HashCompare>
1165       ::getRandomAPCEntry(std::vector<EntryInfo>& entries) {
1166   assertx(!this->empty());
1167 #if TBB_VERSION_MAJOR >= 4
1168   auto current = this->range();
1169   for (auto rnd = rand(); rnd > 0 && current.is_divisible(); rnd >>= 1) {
1170     // Split the range 'current' into two halves: 'current' and 'otherHalf'.
1171     decltype(current) otherHalf(current, tbb::split());
1172     // Randomly choose which half to keep.
1173     if (rnd & 1) {
1174       current = otherHalf;
1175     }
1176   }
1177   auto apcPair = *current.begin();
1178   int64_t curr_time = time(nullptr);
1179   entries.push_back(makeEntryInfo(apcPair.first, &apcPair.second, curr_time));
1180   return true;
1181 #else
1182   return false;
1183 #endif
1184 }
1185
1186 //////////////////////////////////////////////////////////////////////
1187 }