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

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