2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
25 #include <folly/SharedMutex.h>
27 #include <tbb/concurrent_hash_map.h>
28 #include <tbb/concurrent_priority_queue.h>
30 #include "hphp/util/either.h"
31 #include "hphp/util/smalllocks.h"
33 #include "hphp/runtime/base/apc-handle.h"
34 #include "hphp/runtime/base/apc-stats.h"
35 #include "hphp/runtime/server/server-stats.h"
36 #include "hphp/runtime/vm/treadmill.h"
40 //////////////////////////////////////////////////////////////////////
43 * This is the in-APC representation of a value, in ConcurrentTableSharedStore.
47 * Index into cache layer. Valid indices are >= 0 and never invalidated.
49 using HotCacheIdx
= int32_t;
51 StoreValue() = default;
52 StoreValue(const StoreValue
& o
)
53 : m_data
{o
.m_data
.load(std::memory_order_acquire
)}
54 , expireTime
{o
.expireTime
.load(std::memory_order_relaxed
)}
55 , dataSize
{o
.dataSize
}
57 , bumpTTL
{o
.bumpTTL
.load(std::memory_order_relaxed
)}
59 , maxExpireTime
{o
.maxExpireTime
.load(std::memory_order_relaxed
)}
61 hotIndex
.store(o
.hotIndex
.load(std::memory_order_relaxed
),
62 std::memory_order_relaxed
);
65 APCHandle
* data() const {
66 auto data
= m_data
.load(std::memory_order_acquire
);
67 assertx(data
!= nullptr);
70 void setHandle(APCHandle
* v
) {
72 m_data
.store(v
, std::memory_order_release
);
74 APCKind
getKind() const {
76 assertx(data()->kind() == kind
);
79 Variant
toLocal() const {
80 return data()->toLocal();
82 void set(APCHandle
* v
, int64_t expireTTL
, int64_t maxTTL
, int64_t bumpTTL
);
84 uint32_t rawExpire() const {
85 return expireTime
.load(std::memory_order_acquire
);
87 uint32_t queueExpire() const;
89 /* Special invalid indices; used to classify cache lookup misses. */
90 static constexpr HotCacheIdx kHotCacheUnknown
= -1;
91 static constexpr HotCacheIdx kHotCacheKnownIneligible
= -2;
93 // Mutable fields here are so that we can deserialize the object from disk
94 // while holding a const pointer to the StoreValue, or remember a cache entry.
97 * Each entry in APC is an APCHandle*
99 * Note also that 'expire' may not be safe to read even if data is
100 * valid, due to non-atomicity of updates; use 'expired()'.
102 * Note: expiration, creation, and modification times are stored unsigned
103 * in 32-bits as seconds since the Epoch to save cache-line space.
104 * HHVM might get confused after 2106 :)
106 mutable std::atomic
<APCHandle
*> m_data
;
107 mutable std::atomic
<uint32_t> expireTime
{};
108 int32_t dataSize
{0}; // For file storage, negative means serialized object
109 // Reference to any HotCache entry to be cleared if the value is treadmilled.
110 mutable std::atomic
<HotCacheIdx
> hotIndex
{kHotCacheUnknown
};
112 mutable std::atomic
<uint16_t> bumpTTL
{0};
113 mutable std::atomic
<int64_t> expireRequestIdx
{Treadmill::kIdleGenCount
};
114 uint32_t c_time
{0}; // Creation time; 0 for primed values
115 mutable std::atomic
<uint32_t> maxExpireTime
{};
118 //////////////////////////////////////////////////////////////////////
121 * Hold info about an entry in APC. Used as a temporary holder to expose
122 * information about APC entries.
146 EntryInfo(const char* apckey
,
161 , inHotCache(inHotCache
)
164 static Type
getAPCType(const APCHandle
* handle
);
176 //////////////////////////////////////////////////////////////////////
179 * This is the backing store for APC. Maintains a key to value mapping, where
180 * each value optionally has a time-to-live.
182 * After a value reaches its TTL, it's considered "expired", and most
183 * operations on the table will act like it's not present (exceptions to this
184 * should be documented below). TTL function arguments to this module are
185 * specified in seconds.
187 struct ConcurrentTableSharedStore
{
188 ConcurrentTableSharedStore() = default;
189 ConcurrentTableSharedStore(const ConcurrentTableSharedStore
&) = delete;
190 ConcurrentTableSharedStore
&
191 operator=(const ConcurrentTableSharedStore
&) = delete;
194 * Retrieve a value from the store. Returns false if the value wasn't
195 * contained in the table (or was expired).
197 bool get(const String
& key
, Variant
& value
);
200 * Add a value to the store if no (unexpired) value with this key is already
203 * The requested ttl is limited by the ApcTTLLimit.
205 * Returns: true if the value was added, including if we've replaced an
208 bool add(const String
& key
, const Variant
& val
, int64_t max_ttl
, int64_t bump_ttl
);
211 * Set the value for `key' to `val'. If there was an existing value, it is
214 * The requested ttl is limited by the ApcTTLLimit.
216 void set(const String
& key
, const Variant
& val
, int64_t max_ttl
, int64_t bump_ttl
);
219 * Increment the value for the key `key' by step, iff it is present,
220 * non-expired, and a numeric (KindOfInt64 or KindOfDouble) value. Sets
221 * `found' to true if the increment is performed, false otherwise.
223 * Returns: the new value for the key, or zero if the key was not found.
225 int64_t inc(const String
& key
, int64_t step
, bool& found
);
228 * Attempt to atomically compare and swap the value for the key `key' from
229 * `oldVal' to `newVal'. If the key is present, non-expired, and has the
230 * same value as `oldVal' (after conversions), set it to `newVal' and return
231 * true. Otherwise returns false.
233 bool cas(const String
& key
, int64_t oldVal
, int64_t newVal
);
236 * Returns: true if this key exists in the store, and is not expired.
238 bool exists(const String
& key
);
241 * Extend the expiration time to now + new_ttl if that is longer than
242 * the current TTL (or to infinity if new_ttl is zero). Returns true if
243 * it succeeds (the key exists in apc, is unexpired, and the expiration
244 * was actually adjusted), false otherwise.
246 bool extendTTL(const String
& key
, int64_t new_ttl
);
249 * Returns the size of an entry if it exists. Sets `found` to true if it
250 * exists and false if not.
252 int64_t size(const String
& key
, bool& found
);
255 * Remove the specified key, if it exists in the table.
257 * Returns: false if the key was not in the table, true if the key was in the
258 * table **even if it was expired**.
260 bool eraseKey(const String
& key
);
263 * Schedule deletion of expired entries.
266 void purgeDeferred(req::vector
<StringData
*>&&);
269 * Clear the entire APC table.
279 * Debugging. Dump information about the table to an output stream.
281 * This is extremely expensive and not recommended for use outside of
282 * development scenarios.
284 enum class DumpMode
{
289 void dump(std::ostream
& out
, DumpMode dumpMode
);
291 * Dump up to count keys that begin with the given prefix. This is a subset
292 * of what the dump `KeyAndValue` command would do.
294 void dumpPrefix(std::ostream
& out
, const std::string
&prefix
, uint32_t count
);
296 * Dump all non-primed keys that begin with one of the prefixes. Different
297 * keys are separated by \n in the output stream. Keys containing \r or \n
298 * will not be included.
300 void dumpKeysWithPrefixes(std::ostream
& out
,
301 const std::vector
<std::string
>& prefixes
);
303 * Dump random key and entry size to output stream
305 void dumpRandomKeys(std::ostream
& out
, uint32_t count
);
308 * Return 'count' randomly chosen entries, possibly with duplicates. If the
309 * store is empty or this operation is not supported, returns an empty vector.
311 std::vector
<EntryInfo
> sampleEntriesInfo(uint32_t count
);
313 * Return a list of entries with consideration of memory usage. Roughly one
314 * sample every 'bytes' of memory is used.
316 std::vector
<EntryInfo
> sampleEntriesInfoBySize(uint32_t bytes
);
319 * Debugging. Access information about all the entries in this table.
321 * This is extremely expensive and not recommended for use outside of
322 * development scenarios.
324 std::vector
<EntryInfo
> getEntriesInfo();
327 // Fake a StringData as a char* with the high bit set. charHashCompare below
328 // will properly handle the value and reuse the hash value of the StringData.
330 static char* tagStringData(StringData
* s
) {
331 return reinterpret_cast<char*>(-reinterpret_cast<intptr_t>(s
));
334 static StringData
* getStringData(const char* s
) {
335 assertx(reinterpret_cast<intptr_t>(s
) < 0);
336 return reinterpret_cast<StringData
*>(-reinterpret_cast<intptr_t>(s
));
339 inline static bool isTaggedStringData(const char* s
) {
340 return reinterpret_cast<intptr_t>(s
) < 0;
344 struct CharHashCompare
{
345 bool equal(const char* s1
, const char* s2
) const {
347 // tbb implementation call equal with the second pointer being the
348 // value in the table and thus not a StringData*. We are asserting
349 // to make sure that is the case
350 assertx(!isTaggedStringData(s2
));
351 if (isTaggedStringData(s1
)) {
352 s1
= getStringData(s1
)->data();
354 return strcmp(s1
, s2
) == 0;
356 size_t hash(const char* s
) const {
358 return isTaggedStringData(s
) ? getStringData(s
)->hash() :
359 StringData::hash(s
, strlen(s
));
364 template<typename Key
, typename T
, typename HashCompare
>
366 tbb::concurrent_hash_map
<Key
,T
,HashCompare
,APCAllocator
<char>> {
367 // Append a random entry to 'entries'. The map must be non-empty and not
368 // concurrently accessed. Returns false if this operation is not supported.
369 bool getRandomAPCEntry(std::vector
<EntryInfo
>& entries
);
371 using node
= typename
tbb::concurrent_hash_map
<Key
,T
,HashCompare
,
372 APCAllocator
<char>>::node
;
373 static_assert(sizeof(node
) == 64, "Node should be cache-line sized");
376 using Map
= APCMap
<const char*,StoreValue
,CharHashCompare
>;
377 using ExpirationPair
= std::pair
<intptr_t,time_t>;
378 enum class ExpNil
{};
379 using ExpSet
= tbb::concurrent_hash_map
<intptr_t,ExpNil
>;
381 struct ExpirationCompare
{
382 bool operator()(const ExpirationPair
& p1
, const ExpirationPair
& p2
) const {
383 return p1
.second
> p2
.second
;
388 bool checkExpire(const String
& keyStr
, Map::const_accessor
& acc
);
389 bool eraseImpl(const char*, bool, int64_t, ExpSet::accessor
* expAcc
);
390 bool storeImpl(const String
&, const Variant
&, int64_t, int64_t, bool);
391 bool handlePromoteObj(const String
&, APCHandle
*, const Variant
&);
392 void dumpKeyAndValue(std::ostream
&);
393 static EntryInfo
makeEntryInfo(const char*, StoreValue
*, int64_t curr_time
);
397 folly::SharedMutex m_lock
;
399 * m_expQueue is a queue of keys to be expired. We purge items from
400 * it every n (configurable) apc_stores.
402 * We can't (easily) remove items from m_expQueue, so if we add a
403 * new entry every time an item is updated we could end up with a
404 * lot of copies of the same key in the queue. To avoid that, we use
405 * m_expSet, and only add an entry to the queue if there isn't one
408 * In the current implementation, that means that if an element is
409 * updated before it expires, when its entry in m_expQueue is
410 * processed, it does nothing; except being put back into the queue
411 * again with the new expiry time.
413 * This implementation uses the apc key's address as the key into
414 * m_expSet, and as the identifier in ExpirationPair. We ensure that
415 * the m_expSet entry is removed before the apc key is freed, and
416 * guarantee that the key is valid as a char* if it exists in
417 * m_expSet. If the entry subsequently pops off m_expQueue, we check
418 * to see if its in m_expSet, and only try to purge it from apc if
421 * Note that its possible that the apc key was freed and
422 * reallocated, and the entry in m_expQueue doesn't correspond to
423 * the new key; but thats fine - if the key really has expired, it
424 * will be purged, and if not, nothing will happen.
426 tbb::concurrent_priority_queue
<ExpirationPair
,
427 ExpirationCompare
> m_expQueue
;
429 std::atomic
<time_t> m_lastPurgeTime
{0};
432 //////////////////////////////////////////////////////////////////////