hphp/util/tls-pod-bag.h

   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 #ifndef incl_HPHP_TLS_POD_BAG_H_
  17 #define incl_HPHP_TLS_POD_BAG_H_
  18
  19 #include <cstdint>
  20 #include <cstring>
  21 #include <type_traits>
  22 #include <cassert>
  23
  24 #include "hphp/util/assertions.h"
  25
  26 namespace HPHP {
  27
  28 //////////////////////////////////////////////////////////////////////
  29
  30 /*
  31  * This class implements a small vector that is suitable for direct
  32  * placement into thread local storage, to maintain small sets of POD
  33  * data.
  34  *
  35  * The motivating case for this was the strong iterator association in
  36  * tl_miter_table, so it's got a fairly specialized API.  It has a
  37  * concept of "unpopulated" slots of the vector, and has methods for
  38  * finding slots that are currently unpopulated.  This was pulled out
  39  * in a separate class to it testable, not really to make it reusable.
  40  *
  41  * To work with this class, T must be at least 8 bytes, and whatever
  42  * state the user of this class wants to put into T must involve
  43  * having a non-zero initial 8 bytes, since this is how we decide
  44  * whether a slot is populated.
  45  */
  46 template<class T, class Allocator>
  47 struct TlsPodBag {
  48   static_assert(
  49     sizeof(T) >= sizeof(uint64_t),
  50     "TlsPodBag expects at least 8 bytes per entry"
  51   );
  52
  53   static constexpr uint32_t kInitialCap = 4;
  54
  55   /*
  56    * No constructor or destructor.  This is a POD, intended to be
  57    * allocated by value in TLS.  You have to destruct its elements
  58    * yourself.
  59    *
  60    * Zeroing memory and then casting it to a TlsPodBag is guaranteed
  61    * to produce a TLS vec where empty() is true.
  62    */
  63
  64   /*
  65    * Query the population of the TlsPodBag.
  66    */
  67   bool empty() const { return !m_population; }
  68   uint32_t population() const { return m_population; }
  69
  70   /*
  71    * Return a pointer to an unpopulated slot, growing if necessary.
  72    * Before returning the pointer, this increments the population
  73    * count---the caller must make some change to this element to cause
  74    * its first uint64_t bytes to be non-zero.
  75    */
  76   T* find_unpopulated() {
  77     if (m_population == m_capacity) {
  78       return realloc_find();
  79     }
  80     for (auto i = uint32_t{0}; i < m_capacity; ++i) {
  81       if (unpopulated(&m_data[i])) {
  82         ++m_population;
  83         return &m_data[i];
  84       }
  85     }
  86     not_reached();
  87   }
  88
  89   /*
  90    * Find a populated slot, call a function on it, and then remove it.
  91    */
  92   template<class Fn>
  93   void visit_to_remove(Fn fn) {
  94     assert(!empty());
  95     for (auto i = uint32_t{0}; i < m_capacity; ++i) {
  96       if (!unpopulated(&m_data[i])) {
  97         fn(m_data[i]);
  98         std::memset(&m_data[i], 0, sizeof m_data[i]);
  99         --m_population;
 100         if (!m_population) deallocate();
 101         return;
 102       }
 103     }
 104     not_reached();
 105   }
 106
 107   /*
 108    * Call a function for each slot in the container, regardless of
 109    * whether it is populated or not.
 110    */
 111   template<class Fn>
 112   void for_each(Fn fn) {
 113     for (auto i = uint32_t{0}; i < m_capacity; ++i) {
 114       fn(m_data[i]);
 115     }
 116   }
 117
 118   /*
 119    * Mark all slots that match a predicate as unpopulated.  If the
 120    * population count goes to zero after this, free the memory.
 121    *
 122    * Cond must not return true for an unpopulated slot, but it is
 123    * called for unpopulated slots.
 124    */
 125   template<class Cond>
 126   void release_if(Cond cond) {
 127     for (auto i = uint32_t{0}; i < m_capacity; ++i) {
 128       if (cond(m_data[i])) {
 129         std::memset(&m_data[i], 0, sizeof m_data[i]);
 130         --m_population;
 131       }
 132     }
 133
 134     if (!m_population) deallocate();
 135   }
 136
 137 private:
 138   bool unpopulated(const T* t) const {
 139     return *reinterpret_cast<const uint64_t*>(t) == 0;
 140   }
 141
 142   T* allocate() {
 143     assert(empty());
 144     m_data = Allocator{}.allocate(kInitialCap);
 145     std::memset(m_data, 0, sizeof *m_data * kInitialCap);
 146     m_capacity = kInitialCap;
 147     m_population = 1;
 148     return m_data;
 149   }
 150
 151   void deallocate() {
 152     assert(m_population == 0 && m_data != 0);
 153     Allocator{}.deallocate(m_data, m_capacity);
 154     m_capacity = 0;
 155     m_data = nullptr;
 156   }
 157
 158   T* realloc_find() {
 159     if (!m_capacity) return allocate();
 160
 161     auto const oldcap = m_capacity;
 162     auto const newcap = oldcap * 2;
 163     auto const newdat = Allocator{}.allocate(newcap);
 164     std::copy(m_data, m_data + oldcap, newdat);
 165     std::memset(newdat + oldcap, 0, oldcap * sizeof *newdat);
 166     Allocator{}.deallocate(m_data, oldcap);
 167     m_data = newdat;
 168     m_capacity = newcap;
 169     ++m_population;
 170     return newdat + oldcap;
 171   }
 172
 173 private:
 174   T* m_data;
 175   uint32_t m_population;
 176   uint32_t m_capacity;
 177 };
 178
 179 //////////////////////////////////////////////////////////////////////
 180
 181 }
 182
 183 #endif