folly/memory/UninitializedMemoryHacks.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <string>
  20 #include <type_traits>
  21 #include <vector>
  22
  23 namespace {
  24 // This struct is different in every translation unit.  We use template
  25 // instantiations to define inline freestanding methods.  Since the
  26 // methods are inline it is fine to define them in multiple translation
  27 // units, but the instantiation itself would be an ODR violation if it is
  28 // present in the program more than once.  By tagging the instantiations
  29 // with this struct, we avoid ODR problems for the instantiation while
  30 // allowing the resulting methods to be inline-able.  If you think that
  31 // seems hacky keep reading...
  32 struct FollyMemoryDetailTranslationUnitTag {};
  33 } // anon namespace
  34 namespace folly {
  35 namespace detail {
  36 void unsafeStringSetLargerSize(std::string& s, std::size_t n);
  37 template <typename T>
  38 void unsafeVectorSetLargerSize(std::vector<T>& v, std::size_t n);
  39 } // namespace detail
  40
  41 /*
  42  * This file provides helper functions resizeWithoutInitialization()
  43  * that can resize std::string or std::vector without constructing or
  44  * initializing new elements.
  45  *
  46  * IMPORTANT: These functions can be unsafe if used improperly.  If you
  47  * don't write to an element with index >= oldSize and < newSize, reading
  48  * the element can expose arbitrary memory contents to the world, including
  49  * the contents of old strings.  Use ASAN in your tests, and pay extra
  50  * attention to failure paths.
  51  *
  52  * You should only use this if you have profiling data from production
  53  * that shows that this is not a premature optimization.  This code is
  54  * designed for retroactively optimizing code where touching every element
  55  * twice (or touching never-used elements once) shows up in profiling,
  56  * and where restructuring the code to use fixed-length arrays or IOBuf-s
  57  * would be difficult.
  58  *
  59  * NOTE: Just because .resize() shows up in your profile (probably
  60  * via one of the intrinsic memset implementations) doesn't mean that
  61  * these functions will make your program faster.  Most of the cost
  62  * of memset comes from cache misses, so avoiding the memset means
  63  * that the cache miss cost just gets pushed to the following code.
  64  * resizeWithoutInitialization can be a win when the contents are bigger
  65  * than a cache level, because the second access isn't free in that case.
  66  * It can also be a win if the final length of the string or vector isn't
  67  * actually known, so the suffix will be chopped off with a second call
  68  * to .resize().
  69  */
  70
  71 /**
  72  * Like calling s.resize(n), but when growing the string does not
  73  * initialize new elements.  It is undefined behavior to read from
  74  * any element added to the string by this method unless it has been
  75  * written to by an operation that follows this call.
  76  *
  77  * IMPORTANT: Read the warning at the top of this header file.
  78  */
  79 inline void resizeWithoutInitialization(std::string& s, std::size_t n) {
  80   if (n <= s.size()) {
  81     s.resize(n);
  82   } else {
  83     // careful not to call reserve unless necessary, as it causes
  84     // shrink_to_fit on many platforms
  85     if (n > s.capacity()) {
  86       s.reserve(n);
  87     }
  88     detail::unsafeStringSetLargerSize(s, n);
  89   }
  90 }
  91
  92 /**
  93  * Like calling v.resize(n), but when growing the vector does not construct
  94  * or initialize new elements.  It is undefined behavior to read from any
  95  * element added to the vector by this method unless it has been written
  96  * to by an operation that follows this call.
  97  *
  98  * Use the FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(T) macro to
  99  * declare (and inline define) the internals required to call
 100  * resizeWithoutInitialization for a std::vector<T>.  This must
 101  * be done exactly once in each translation unit that wants to call
 102  * resizeWithoutInitialization(std::vector<T>&,size_t).  char and unsigned
 103  * char are provided by default.  If you don't do this you will get linker
 104  * errors about folly::detail::unsafeVectorSetLargerSize.  Requiring that
 105  * T be trivially_destructible is only an approximation of the property
 106  * required of T.  In fact what is required is that any random sequence of
 107  * bytes may be safely reinterpreted as a T and passed to T's destructor.
 108  *
 109  * std::vector<bool> has specialized internals and is not supported.
 110  *
 111  * IMPORTANT: Read the warning at the top of this header file.
 112  */
 113 template <
 114     typename T,
 115     typename = typename std::enable_if<
 116         std::is_trivially_destructible<T>::value &&
 117         !std::is_same<T, bool>::value>::type>
 118 void resizeWithoutInitialization(std::vector<T>& v, std::size_t n) {
 119   if (n <= v.size()) {
 120     v.resize(n);
 121   } else {
 122     if (n > v.capacity()) {
 123       v.reserve(n);
 124     }
 125     detail::unsafeVectorSetLargerSize(v, n);
 126   }
 127 }
 128
 129 namespace detail {
 130
 131 #if defined(_LIBCPP_STRING)
 132 // libc++
 133
 134 } // namespace detail
 135 } // namespace folly
 136 template void std::string::__set_size(std::size_t);
 137 namespace folly {
 138 namespace detail {
 139
 140 template <typename Tag, typename T, typename A, A Ptr__set_size>
 141 struct MakeUnsafeStringSetLargerSize {
 142   friend void unsafeStringSetLargerSize(
 143       std::basic_string<T>& s,
 144       std::size_t n) {
 145     // s.__set_size(n);
 146     (s.*Ptr__set_size)(n);
 147     (&s[0])[n] = '\0';
 148   }
 149 };
 150 template struct MakeUnsafeStringSetLargerSize<
 151     FollyMemoryDetailTranslationUnitTag,
 152     char,
 153     void (std::string::*)(std::size_t),
 154     &std::string::__set_size>;
 155
 156 #elif defined(_GLIBCXX_USE_FB)
 157 // FBString
 158
 159 template <typename Tag, typename T, typename A, A Ptrstore_>
 160 struct MakeUnsafeStringSetLargerSize {
 161   friend void unsafeStringSetLargerSize(
 162       std::basic_string<T>& s,
 163       std::size_t n) {
 164     // s.store_.expandNoinit(n - s.size(), false);
 165     (s.*Ptrstore_).expandNoinit(n - s.size(), false);
 166   }
 167 };
 168 template struct MakeUnsafeStringSetLargerSize<
 169     FollyMemoryDetailTranslationUnitTag,
 170     char,
 171     std::fbstring_core<char>(std::string::*),
 172     &std::string::store_>;
 173
 174 #elif defined(_GLIBCXX_STRING) && _GLIBCXX_USE_CXX11_ABI
 175 // libstdc++ new implementation with SSO
 176
 177 } // namespace detail
 178 } // namespace folly
 179 template void std::string::_M_set_length(std::size_t);
 180 namespace folly {
 181 namespace detail {
 182
 183 template <typename Tag, typename T, typename A, A Ptr_M_set_length>
 184 struct MakeUnsafeStringSetLargerSize {
 185   friend void unsafeStringSetLargerSize(
 186       std::basic_string<T>& s,
 187       std::size_t n) {
 188     // s._M_set_length(n);
 189     (s.*Ptr_M_set_length)(n);
 190   }
 191 };
 192 template struct MakeUnsafeStringSetLargerSize<
 193     FollyMemoryDetailTranslationUnitTag,
 194     char,
 195     void (std::string::*)(std::size_t),
 196     &std::string::_M_set_length>;
 197
 198 #elif defined(_GLIBCXX_STRING)
 199 // libstdc++ old implementation
 200
 201 } // namespace detail
 202 } // namespace folly
 203 template std::string::_Rep* std::string::_M_rep() const;
 204 template void std::string::_Rep::_M_set_length_and_sharable(std::size_t);
 205 namespace folly {
 206 namespace detail {
 207
 208 template <
 209     typename Tag,
 210     typename T,
 211     typename A,
 212     A Ptr_M_rep,
 213     typename B,
 214     B Ptr_M_set_length_and_sharable>
 215 struct MakeUnsafeStringSetLargerSize {
 216   friend void unsafeStringSetLargerSize(
 217       std::basic_string<T>& s,
 218       std::size_t n) {
 219     // s._M_rep()->_M_set_length_and_sharable(n);
 220     auto rep = (s.*Ptr_M_rep)();
 221     (rep->*Ptr_M_set_length_and_sharable)(n);
 222   }
 223 };
 224 template struct MakeUnsafeStringSetLargerSize<
 225     FollyMemoryDetailTranslationUnitTag,
 226     char,
 227     std::string::_Rep* (std::string::*)() const,
 228     &std::string::_M_rep,
 229     void (std::string::_Rep::*)(std::size_t),
 230     &std::string::_Rep::_M_set_length_and_sharable>;
 231
 232 #elif defined(_MSC_VER)
 233 // MSVC
 234
 235 inline void unsafeStringSetLargerSize(std::string& s, std::size_t n) {
 236   s._Eos(n);
 237 }
 238
 239 #else
 240 #warn "No implementation for resizeWithoutInitialization of std::string"
 241 #endif
 242
 243 // This machinery bridges template expansion and macro expansion
 244 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)              \
 245   namespace folly {                                                      \
 246   namespace detail {                                                     \
 247   void unsafeVectorSetLargerSizeImpl(std::vector<TYPE>& v, std::size_t); \
 248   template <>                                                            \
 249   inline void unsafeVectorSetLargerSize<TYPE>(                           \
 250       std::vector<TYPE> & v,                                             \
 251       std::size_t n) {                                                   \
 252     unsafeVectorSetLargerSizeImpl(v, n);                                 \
 253   }                                                                      \
 254   }                                                                      \
 255   }
 256
 257 #if defined(_LIBCPP_VECTOR)
 258 // libc++
 259
 260 template <typename Tag, typename T, typename A, A Ptr__end_>
 261 struct MakeUnsafeVectorSetLargerSize {
 262   friend void unsafeVectorSetLargerSizeImpl(std::vector<T>& v, std::size_t n) {
 263     // v.__end_ += (n - v.size());
 264     using Base = std::__vector_base<T, std::allocator<T>>;
 265     static_assert(
 266         std::is_standard_layout<std::vector<T>>::value &&
 267             sizeof(std::vector<T>) == sizeof(Base),
 268         "reinterpret_cast safety conditions not met");
 269     reinterpret_cast<Base&>(v).*Ptr__end_ += (n - v.size());
 270   }
 271 };
 272
 273 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE)          \
 274   template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
 275       FollyMemoryDetailTranslationUnitTag,                      \
 276       TYPE,                                                     \
 277       TYPE*(std::__vector_base<TYPE, std::allocator<TYPE>>::*), \
 278       &std::vector<TYPE>::__end_>;                              \
 279   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 280
 281 #elif defined(_GLIBCXX_VECTOR)
 282 // libstdc++
 283
 284 template <
 285     typename Tag,
 286     typename T,
 287     typename A,
 288     A Ptr_M_impl,
 289     typename B,
 290     B Ptr_M_finish>
 291 struct MakeUnsafeVectorSetLargerSize : std::vector<T> {
 292   friend void unsafeVectorSetLargerSizeImpl(std::vector<T>& v, std::size_t n) {
 293     // v._M_impl._M_finish += (n - v.size());
 294     (v.*Ptr_M_impl).*Ptr_M_finish += (n - v.size());
 295   }
 296 };
 297
 298 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE)          \
 299   template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
 300       FollyMemoryDetailTranslationUnitTag,                      \
 301       TYPE,                                                     \
 302       std::vector<TYPE>::_Vector_impl(                          \
 303           std::_Vector_base<TYPE, std::allocator<TYPE>>::*),    \
 304       &std::vector<TYPE>::_M_impl,                              \
 305       TYPE*(std::vector<TYPE>::_Vector_impl::*),                \
 306       &std::vector<TYPE>::_Vector_impl::_M_finish>;             \
 307   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 308
 309 #elif defined(_MSC_VER)
 310 // MSVC
 311
 312 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE) \
 313   extern inline void unsafeVectorSetLargerSizeImpl(    \
 314       std::vector<TYPE>& v, std::size_t n) {           \
 315     v._Mylast() += (n - v.size());                     \
 316   }                                                    \
 317   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 318
 319 #else
 320 #warn "No implementation for resizeWithoutInitialization of std::vector"
 321 #endif
 322
 323 } // namespace detail
 324 } // namespace folly
 325
 326 #if defined(FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT)
 327 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(char)
 328 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(unsigned char)
 329 #endif