2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-2014 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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_RUNTIME_VM_NAMEVALUETABLE_H_
18 #define incl_HPHP_RUNTIME_VM_NAMEVALUETABLE_H_
20 #include <boost/noncopyable.hpp>
24 #include "folly/Bits.h"
26 #include "hphp/util/exp-arena.h"
27 #include "hphp/runtime/base/complex-types.h"
31 //////////////////////////////////////////////////////////////////////
34 * This class implements a name to TypedValue map. Basically a
35 * hashtable from StringData* to TypedValue.
37 * This is for use in variable environments in bytecode.cpp, and is
38 * also used for the global variable environment. It also ends up
39 * used (via NameValueTableWrapper) for initialization of class
40 * properties (see class.cpp).
44 * - All elements are guaranteed to have a fixed address for the
45 * lifetime of the table. (However this address may at some times
46 * contain a TypedValue with KindOfIndirect, see next point.) The
47 * lookupRaw* functions access this address.
49 * - Supports migrating storage for values outside of the table.
50 * This currently has a few uses:
52 * o Keeps storage for locals in functions with a VarEnv in
53 * their normal location, but still accessible by name
56 * o When invoking 86pinit or 86sinit on classes, this is used
57 * to provide a name to value mapping to these generated
58 * functions, although the storage lives elsewhere.
60 * o Some special global variables have storage outside of the
61 * NameValueTable. (This is currently because the runtime
62 * accesses these values by raw pointer in several
63 * extensions, and might be removable (#1158383).)
65 * - Adding and then unsetting an element will still leave its space
66 * allocated for the lifetime of the NameValueTable (with the type
67 * set to KindOfUninit). This is because of the first note: we
68 * hand out pointers that need to be valid for the lifetime of the
69 * table, so we can't really reclaim any of the KindOfUninit
73 struct NameValueTable
: private boost::noncopyable
{
75 * Create a NameValueTable with room for `size' elements before
76 * rehash is necessary.
78 explicit NameValueTable(size_t size
)
85 * Reserve space for size * 4 / 3 because we limit our max load
88 * Add one because the way we compute whether there is enough
89 * space on lookupAdd will look at m_elms + 1, and this
90 * constructor is sometimes used with an exact final size count so
91 * we'd like to avoid reallocation in that case.
93 * Finally, never allocate less than 4 slots. In the case of a
94 * NameValueTable created with an exact size of a single element
95 * (not uncommon for a VarEnv), this avoids reallocation when
96 * someone does a lookupAdd() on the single element.
98 allocate(std::max(folly::nextPowTwo(size
* 4 / 3 + 1), 4ul));
105 * Map a name via KindOfIndirect to a specific storage location.
107 * This is for use when we want a name to be possible to look up in
108 * this table, but the actual storage to exist somewhere else
109 * (e.g. the execution stack or an instance property slot).
111 * The `migrateSet' version will retain the value currently at
112 * `loc': we set the mapping in this table to point at `loc' but
113 * don't change the current contents of loc. The `migrate' version
114 * also copies whatever current value is in the table to `loc', and
115 * assumes `loc' is currently dead.
117 * Both functions return a pointer to the previous storage location
118 * mapped for this name. If the previous storage location was
119 * inside this NameValueTable, they return null. This is to support
120 * nesting of migrate/resettle pairs in a scoped fashion.
122 TypedValue
* migrate(const StringData
* name
, TypedValue
* loc
) {
123 return migrateImpl
<true>(name
, loc
);
125 TypedValue
* migrateSet(const StringData
* name
, TypedValue
* loc
) {
126 return migrateImpl
<false>(name
, loc
);
130 * Explicitly request letting go of all elements in the
131 * NameValueTable without decrefing them.
133 * This is intended for use when destroying the global scope, where
134 * we shouldn't be running destructors.
145 * Opposite of migrate. Remaps `name' to point at `origLoc', or if
146 * `origLoc' is null copies from the current external storage back
149 * It is illegal to call resettle for a name that hasn't been
152 void resettle(const StringData
* name
, TypedValue
* origLoc
) {
153 Elm
* e
= findElm(name
);
155 TypedValue
* tv
= e
->m_tv
;
156 assert(tv
->m_type
== KindOfIndirect
);
158 *tv
= *tv
->m_data
.pind
;
160 *origLoc
= *tv
->m_data
.pind
;
161 tv
->m_data
.pind
= origLoc
;
166 * Set the slot for the supplied name to `val', allocating it if
169 TypedValue
* set(const StringData
* name
, const TypedValue
* val
) {
170 TypedValue
* target
= findTypedValue(name
);
171 tvSet(*(val
->m_type
== KindOfRef
? val
->m_data
.pref
->tv() : val
),
177 * Bind the slot for the supplied name to `val', allocating it and
178 * boxing it first if necessary.
180 TypedValue
* bind(const StringData
* name
, TypedValue
* val
) {
181 TypedValue
* target
= findTypedValue(name
);
182 if (val
->m_type
!= KindOfRef
) {
190 * Remove an element from this table. All elements added always
191 * occupy storage, so this is done by setting the element to
194 void unset(const StringData
* name
) {
195 TypedValue
* tv
= lookupRawPointer(name
);
197 tvUnset(tvDerefIndirect(tv
));
202 * Look up the actual storage for this name in this table, returning
203 * null if it doesn't exist.
205 * The returned TypedValue might have KindOfIndirect if this name
206 * has been used with migrate/resettle.
208 * The returned pointer is guaranteed to remain valid for the
209 * lifetime of this NameValueTable.
211 TypedValue
* lookupRawPointer(const StringData
* name
) {
212 Elm
* elm
= findElm(name
);
219 * Same as lookupRawPointer, but add an entry with a null value if
220 * it didn't already exist.
222 TypedValue
* lookupAddRawPointer(const StringData
* name
) {
223 Elm
* elm
= insert(name
);
226 tvWriteNull(elm
->m_tv
);
232 * Lookup a name, returning null if it doesn't exist in this table.
234 TypedValue
* lookup(const StringData
* name
) {
235 Elm
* elm
= findElm(name
);
237 TypedValue
* tv
= elm
->m_tv
;
238 tv
= tvDerefIndirect(tv
);
239 return tv
->m_type
== KindOfUninit
? 0 : tv
;
243 * Insert a name to value entry with KindOfNull for the value, or
244 * return what is already there if the key already exists in the
247 TypedValue
* lookupAdd(const StringData
* name
) {
248 Elm
* elm
= insert(name
);
251 tvWriteNull(elm
->m_tv
);
254 TypedValue
* ret
= tvDerefIndirect(elm
->m_tv
);
255 if (ret
->m_type
== KindOfUninit
) {
263 const StringData
* m_name
;
268 void reserve(size_t desiredSize
) {
269 const size_t curCapac
= m_tabMask
+ 1;
270 if (desiredSize
< curCapac
* 3 / 4) { // .75 load factor
273 allocate(folly::nextPowTwo(curCapac
+ 1));
276 void allocate(const size_t newCapac
) {
277 assert(folly::isPowTwo(newCapac
));
278 const size_t newMask
= newCapac
- 1;
279 assert(newMask
<= std::numeric_limits
<uint32_t>::max());
280 Elm
* newTab
= static_cast<Elm
*>(calloc(sizeof(Elm
), newCapac
));
282 rehash(newTab
, newMask
);
286 m_tabMask
= uint32_t(newMask
);
289 TypedValue
* findTypedValue(const StringData
* name
) {
290 return tvDerefIndirect(lookupAddRawPointer(name
));
293 static Elm
* insertImpl(Elm
* const table
,
294 const size_t tabMask
,
295 const StringData
* name
) {
296 Elm
* elm
= &table
[name
->hash() & tabMask
];
297 UNUSED
size_t numProbes
= 0;
299 assert(numProbes
++ < tabMask
+ 1);
300 if (0 == elm
->m_name
) {
304 if (name
->same(elm
->m_name
)) {
307 if (UNLIKELY(++elm
== &table
[tabMask
+ 1])) {
313 Elm
* insert(const StringData
* name
) {
315 Elm
* e
= insertImpl(m_table
, m_tabMask
, name
);
323 template<bool retainValue
>
324 TypedValue
* migrateImpl(const StringData
* name
, TypedValue
* loc
) {
325 Elm
* elm
= insert(name
);
328 tvWriteUninit(elm
->m_tv
);
329 tvBindIndirect(elm
->m_tv
, loc
);
333 TypedValue
* ours
= elm
->m_tv
;
334 if (ours
->m_type
== KindOfIndirect
) {
335 TypedValue
* old
= ours
->m_data
.pind
;
336 ours
->m_data
.pind
= loc
;
343 // Current value is actually stored inside the array.
345 // loc is assumed dead; no need for a decRef.
348 tvBindIndirect(ours
, loc
);
352 void rehash(Elm
* const target
, const size_t targetMask
) {
353 for (size_t i
= 0; i
<= m_tabMask
; ++i
) {
354 if (const StringData
* sd
= m_table
[i
].m_name
) {
355 Elm
* targetElm
= insertImpl(target
, targetMask
, sd
);
356 targetElm
->m_name
= sd
;
357 targetElm
->m_tv
= m_table
[i
].m_tv
;
362 Elm
* findElm(const StringData
* name
) const {
363 Elm
* elm
= &m_table
[name
->hash() & m_tabMask
];
364 UNUSED
size_t numProbes
= 0;
366 assert(numProbes
++ < m_tabMask
+ 1);
367 if (UNLIKELY(0 == elm
->m_name
)) {
370 if (name
->same(elm
->m_name
)) return elm
;
371 if (UNLIKELY(++elm
== &m_table
[m_tabMask
+ 1])) {
377 void addStorage(Elm
* elm
) {
379 elm
->m_tv
= static_cast<TypedValue
*>(
380 m_storage
.alloc(sizeof(TypedValue
)));
381 // Require 16-byte alignment so we can access globals with movdqa.
382 assert(reinterpret_cast<uintptr_t>(elm
->m_tv
) % 16 == 0);
386 // Power of two sized hashtable.
393 //////////////////////////////////////////////////////////////////////
395 struct NameValueTable::Iterator
{
396 explicit Iterator(const NameValueTable
* tab
)
400 if (!valid()) next();
403 static Iterator
getEnd(const NameValueTable
* tab
) {
406 it
.m_idx
= tab
->m_tabMask
+ 1;
412 * The following two constructors are primarily for using this with
413 * the ArrayData interface (see NameValueTableWrapper), which
414 * expects iterators to be represented by a ssize_t.
416 * The constructor taking `pos' must be given a value previously
417 * returned from toInteger().
419 * The constructor taking a const StringData* starts iteration at
420 * the key given, or returns an invalid iterator if that key does
424 explicit Iterator(const NameValueTable
* tab
, ssize_t pos
)
429 if (!valid()) next();
432 explicit Iterator(const NameValueTable
* tab
, const StringData
* start
)
435 Elm
* e
= m_tab
->findElm(start
);
436 m_idx
= e
? e
- m_tab
->m_table
: (m_tab
->m_tabMask
+ 1);
439 ssize_t
toInteger() const {
440 const ssize_t invalid
= ArrayData::invalid_index
;
441 return valid() ? m_idx
: invalid
;
445 return m_idx
>= 0 && size_t(m_idx
) < m_tab
->m_tabMask
+ 1 && !atEmpty();
448 const StringData
* curKey() const {
450 return m_tab
->m_table
[m_idx
].m_name
;
453 const TypedValue
* curVal() const {
455 return tvDerefIndirect(m_tab
->m_table
[m_idx
].m_tv
);
458 const TypedValue
* curValRaw() const {
460 return m_tab
->m_table
[m_idx
].m_tv
;
464 size_t const sz
= m_tab
->m_tabMask
+ 1;
467 } while (size_t(m_idx
) < sz
&& atEmpty());
473 } while (m_idx
>= 0 && atEmpty());
479 bool atEmpty() const {
480 if (!m_tab
->m_table
[m_idx
].m_name
) {
483 const TypedValue
* tv
= m_tab
->m_table
[m_idx
].m_tv
;
484 tv
= tvDerefIndirect(tv
);
485 return tv
->m_type
== KindOfUninit
;
489 const NameValueTable
* m_tab
;
493 //////////////////////////////////////////////////////////////////////
495 inline NameValueTable::~NameValueTable() {
496 if (!m_table
) return;
498 for (Iterator
iter(this); iter
.valid(); iter
.next()) {
499 decRefStr(const_cast<StringData
*>(iter
.curKey()));
500 const TypedValue
* tv
= iter
.curValRaw();
501 if (tv
->m_type
!= KindOfIndirect
) {
502 tvRefcountedDecRef(const_cast<TypedValue
*>(tv
));
508 //////////////////////////////////////////////////////////////////////