hphp/runtime/vm/name-value-table.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2015 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/vm/name-value-table.h"
  18
  19 #include <limits>
  20 #include <folly/Bits.h>
  21
  22 #include "hphp/runtime/vm/bytecode.h"
  23 #include "hphp/runtime/vm/runtime.h"
  24
  25 namespace HPHP {
  26
  27 //////////////////////////////////////////////////////////////////////
  28
  29 NameValueTable::NameValueTable() {
  30   allocate(folly::nextPowTwo(RuntimeOption::EvalVMInitialGlobalTableSize));
  31 }
  32
  33 NameValueTable::NameValueTable(ActRec* fp)
  34   : m_fp(fp)
  35 {
  36   assert(m_fp);
  37   const auto func = m_fp->m_func;
  38   const Id numNames = func->numNamedLocals();
  39
  40   /**
  41    * Reserve space for all named locals plus one additional variable
  42    * to avoid reallocations if one extra dynamic variable is used.
  43    */
  44   reserve(numNames + 1);
  45
  46   for (Id i = 0; i < numNames; ++i) {
  47     assert(func->lookupVarId(func->localVarName(i)) == i);
  48
  49     auto elm = insert(func->localVarName(i));
  50     assert(elm && elm->m_tv.m_type == kInvalidDataType);
  51     elm->m_tv.m_type = kNamedLocalDataType;
  52     elm->m_tv.m_data.num = i;
  53   }
  54 }
  55
  56 NameValueTable::NameValueTable(const NameValueTable& nvTable, ActRec* fp)
  57   : m_fp(fp)
  58   , m_elms(nvTable.m_elms)
  59 {
  60   allocate(nvTable.m_tabMask + 1);
  61   assert(m_tabMask == nvTable.m_tabMask);
  62
  63   for (int i = 0; i <= m_tabMask; ++i) {
  64     Elm& src = nvTable.m_table[i];
  65     Elm& dst = m_table[i];
  66
  67     dst.m_name = src.m_name;
  68     if (dst.m_name) {
  69       dst.m_name->incRefCount();
  70       if (src.m_tv.m_type == kNamedLocalDataType) {
  71         dst.m_tv.m_type = kNamedLocalDataType;
  72         dst.m_tv.m_data.num = src.m_tv.m_data.num;
  73       } else {
  74         tvDupFlattenVars(&src.m_tv, &dst.m_tv);
  75       }
  76     }
  77   }
  78 }
  79
  80 NameValueTable::~NameValueTable() {
  81   if (leaked()) return;
  82   for (Elm* elm = &m_table[m_tabMask]; elm != &m_table[-1]; --elm) {
  83     if (elm->m_name) {
  84       decRefStr(const_cast<StringData*>(elm->m_name));
  85       if (elm->m_tv.m_type != kNamedLocalDataType) {
  86         tvRefcountedDecRef(elm->m_tv);
  87       }
  88     }
  89   }
  90   req::free(m_table);
  91 }
  92
  93 void NameValueTable::suspend(const ActRec* oldFP, ActRec* newFP) {
  94   assert(m_fp == oldFP);
  95   assert(oldFP->func() == newFP->func());
  96   assert(!oldFP->resumed());
  97   assert(newFP->resumed());
  98
  99   m_fp = newFP;
 100 }
 101
 102 void NameValueTable::attach(ActRec* fp) {
 103   assert(m_fp == nullptr);
 104   m_fp = fp;
 105
 106   const auto func = fp->m_func;
 107   const Id numNames = func->numNamedLocals();
 108   TypedValue* loc = frame_local(fp, 0);
 109
 110   for (Id i = 0; i < numNames; ++i, --loc) {
 111     assert(func->lookupVarId(func->localVarName(i)) == i);
 112
 113     auto elm = insert(func->localVarName(i));
 114     assert(elm);
 115     if (elm->m_tv.m_type != kInvalidDataType) {
 116       assert(elm->m_tv.m_type != kNamedLocalDataType);
 117       tvCopy(elm->m_tv, *loc);
 118     }
 119
 120     elm->m_tv.m_type = kNamedLocalDataType;
 121     elm->m_tv.m_data.num = i;
 122   }
 123 }
 124
 125 void NameValueTable::detach(ActRec* fp) {
 126   assert(m_fp == fp);
 127   m_fp = nullptr;
 128
 129   const auto func = fp->m_func;
 130   const Id numNames = func->numNamedLocals();
 131   TypedValue* loc = frame_local(fp, 0);
 132
 133   for (Id i = 0; i < numNames; ++i, --loc) {
 134     assert(func->lookupVarId(func->localVarName(i)) == i);
 135
 136     auto elm = findElm(func->localVarName(i));
 137     assert(elm && elm->m_tv.m_type == kNamedLocalDataType);
 138     tvCopy(*loc, elm->m_tv);
 139     tvDebugTrash(loc);
 140   }
 141 }
 142
 143 void NameValueTable::leak() {
 144   m_elms = 0;
 145   m_tabMask = 0;
 146   req::free(m_table);
 147   m_table = nullptr;
 148   assert(leaked());
 149 }
 150
 151 TypedValue* NameValueTable::set(const StringData* name, const TypedValue* val) {
 152   TypedValue* target = findTypedValue(name);
 153   tvSet(*tvToCell(val), *target);
 154   return target;
 155 }
 156
 157 TypedValue* NameValueTable::bind(const StringData* name, TypedValue* val) {
 158   TypedValue* target = findTypedValue(name);
 159   if (val->m_type != KindOfRef) {
 160     tvBox(val);
 161   }
 162   tvBind(val, target);
 163   return target;
 164 }
 165
 166 void NameValueTable::unset(const StringData* name) {
 167   Elm* elm = findElm(name);
 168   if (!elm) return;
 169   tvUnset(derefNamedLocal(&elm->m_tv));
 170 }
 171
 172 TypedValue* NameValueTable::lookup(const StringData* name) {
 173   Elm* elm = findElm(name);
 174   if (!elm) return nullptr;
 175   TypedValue* tv = derefNamedLocal(&elm->m_tv);
 176   return tv->m_type == KindOfUninit ? nullptr : tv;
 177 }
 178
 179 TypedValue* NameValueTable::lookupAdd(const StringData* name) {
 180   auto tv = findTypedValue(name);
 181   if (tv->m_type == KindOfUninit) {
 182     tvWriteNull(tv);
 183   }
 184   return tv;
 185 }
 186
 187 void NameValueTable::reserve(size_t desiredSize) {
 188   /*
 189    * Reserve space for size * 4 / 3 because we limit our max load
 190    * factor to .75.
 191    *
 192    * Add one because the way we compute whether there is enough
 193    * space on lookupAdd will look at m_elms + 1.
 194    */
 195   const size_t reqCapac = desiredSize * 4 / 3 + 1;
 196   const size_t curCapac = m_tabMask + 1;
 197
 198   if (reqCapac > curCapac) {
 199     allocate(folly::nextPowTwo(reqCapac));
 200   }
 201 }
 202
 203 void NameValueTable::allocate(const size_t newCapac) {
 204   assert(folly::isPowTwo(newCapac));
 205   assert(newCapac - 1 <= std::numeric_limits<uint32_t>::max());
 206
 207   Elm* oldTab = m_table;
 208   const size_t oldMask = m_tabMask;
 209
 210   m_table = static_cast<Elm*>(req::calloc(sizeof(Elm), newCapac));
 211   m_tabMask = uint32_t(newCapac - 1);
 212
 213   if (oldTab) {
 214     rehash(oldTab, oldMask);
 215     req::free(oldTab);
 216   }
 217 }
 218
 219 TypedValue* NameValueTable::derefNamedLocal(TypedValue* tv) const {
 220   return tv->m_type == kNamedLocalDataType
 221     ? frame_local(m_fp, tv->m_data.num)
 222     : tv;
 223 }
 224
 225 TypedValue* NameValueTable::findTypedValue(const StringData* name) {
 226   Elm* elm = insert(name);
 227   if (elm->m_tv.m_type == kInvalidDataType) {
 228     tvWriteNull(&elm->m_tv);
 229     return &elm->m_tv;
 230   }
 231   return derefNamedLocal(&elm->m_tv);
 232 }
 233
 234 NameValueTable::Elm* NameValueTable::insertImpl(const StringData* name) {
 235   Elm* elm = &m_table[name->hash() & m_tabMask];
 236   UNUSED size_t numProbes = 0;
 237   for (;;) {
 238     assert(numProbes++ < m_tabMask + 1);
 239     if (nullptr == elm->m_name) {
 240       elm->m_name = name;
 241       elm->m_tv.m_type = kInvalidDataType;
 242       return elm;
 243     }
 244     if (name->same(elm->m_name)) {
 245       return elm;
 246     }
 247     if (UNLIKELY(++elm == &m_table[m_tabMask + 1])) {
 248       elm = m_table;
 249     }
 250   }
 251 }
 252
 253 NameValueTable::Elm* NameValueTable::insert(const StringData* name) {
 254   reserve(m_elms + 1);
 255   Elm* elm = insertImpl(name);
 256   if (elm->m_tv.m_type == kInvalidDataType) {
 257     ++m_elms;
 258     name->incRefCount();
 259   }
 260   return elm;
 261 }
 262
 263 void NameValueTable::rehash(Elm* const oldTab, const size_t oldMask) {
 264   for (Elm* srcElm = &oldTab[oldMask]; srcElm != &oldTab[-1]; --srcElm) {
 265     if (srcElm->m_name) {
 266       assert(srcElm->m_tv.m_type == kNamedLocalDataType ||
 267              tvIsPlausible(srcElm->m_tv));
 268       Elm* dstElm = insertImpl(srcElm->m_name);
 269       dstElm->m_name = srcElm->m_name;
 270       dstElm->m_tv = srcElm->m_tv;
 271     }
 272   }
 273 }
 274
 275 NameValueTable::Elm* NameValueTable::findElm(const StringData* name) const {
 276   Elm* elm = &m_table[name->hash() & m_tabMask];
 277   UNUSED size_t numProbes = 0;
 278   for (;;) {
 279     assert(numProbes++ < m_tabMask + 1);
 280     if (UNLIKELY(nullptr == elm->m_name)) {
 281       return nullptr;
 282     }
 283     if (name->same(elm->m_name)) return elm;
 284     if (UNLIKELY(++elm == &m_table[m_tabMask + 1])) {
 285       elm = m_table;
 286     }
 287   }
 288 }
 289
 290 //////////////////////////////////////////////////////////////////////
 291
 292 NameValueTable::Iterator::Iterator(const NameValueTable* tab)
 293   : m_tab(tab)
 294   , m_idx(0)
 295 {
 296   if (!valid()) next();
 297 }
 298
 299 NameValueTable::Iterator
 300 NameValueTable::Iterator::getLast(const NameValueTable* tab) {
 301   Iterator it;
 302   it.m_tab = tab;
 303   it.m_idx = tab->m_tabMask + 1;
 304   it.prev();
 305   return it;
 306 }
 307
 308 NameValueTable::Iterator
 309 NameValueTable::Iterator::getEnd(const NameValueTable* tab) {
 310   Iterator it;
 311   it.m_tab = tab;
 312   it.m_idx = tab->m_tabMask + 1;
 313   return it;
 314 }
 315
 316 NameValueTable::Iterator::Iterator(const NameValueTable* tab, ssize_t pos)
 317   : m_tab(tab)
 318   , m_idx(pos)
 319 {
 320   assert(pos >= 0);
 321   if (!valid()) next();
 322 }
 323
 324 NameValueTable::Iterator::Iterator(const NameValueTable* tab,
 325                                    const StringData* start)
 326   : m_tab(tab)
 327 {
 328   Elm* e = m_tab->findElm(start);
 329   m_idx = e ? e - m_tab->m_table : (m_tab->m_tabMask + 1);
 330 }
 331
 332 ssize_t NameValueTable::Iterator::toInteger() const {
 333   const ssize_t invalid = m_tab->m_tabMask + 1;
 334   return valid() ? m_idx : invalid;
 335 }
 336
 337 bool NameValueTable::Iterator::valid() const {
 338   return m_idx >= 0 && size_t(m_idx) < m_tab->m_tabMask + 1 && !atEmpty();
 339 }
 340
 341 const StringData* NameValueTable::Iterator::curKey() const {
 342   assert(valid());
 343   return m_tab->m_table[m_idx].m_name;
 344 }
 345
 346 const TypedValue* NameValueTable::Iterator::curVal() const {
 347   assert(valid());
 348   return m_tab->derefNamedLocal(&m_tab->m_table[m_idx].m_tv);
 349 }
 350
 351 void NameValueTable::Iterator::next() {
 352   size_t const sz = m_tab->m_tabMask + 1;
 353   if (m_idx + 1 >= sz) {
 354     m_idx = sz;
 355     return;
 356   }
 357   ++m_idx;
 358   if (LIKELY(!atEmpty())) {
 359     return;
 360   }
 361   do {
 362     ++m_idx;
 363   } while (size_t(m_idx) < sz && atEmpty());
 364 }
 365
 366 void NameValueTable::Iterator::prev() {
 367   do {
 368     --m_idx;
 369   } while (m_idx >= 0 && atEmpty());
 370 }
 371
 372 bool NameValueTable::Iterator::atEmpty() const {
 373   if (!m_tab->m_table[m_idx].m_name) {
 374     return true;
 375   }
 376   const auto tv = m_tab->derefNamedLocal(&m_tab->m_table[m_idx].m_tv);
 377   return tv->m_type == KindOfUninit;
 378 }
 379
 380 //////////////////////////////////////////////////////////////////////
 381
 382 }