folly/memory/UninitializedMemoryHacks.h

   1 /*
   2  * Copyright 2017-present 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 } // 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.  If you're lucky you'll get a segfault,
  50  * because the kernel is only required to fault in new pages on write
  51  * access.  MSAN should be able to catch problems in the common case that
  52  * the string or vector wasn't previously shrunk.
  53  *
  54  * Pay extra attention to your failure paths.  For example, if you try
  55  * to read directly into a caller-provided string, make sure to clear
  56  * the string when you get an I/O error.
  57  *
  58  * You should only use this if you have profiling data from production
  59  * that shows that this is not a premature optimization.  This code is
  60  * designed for retroactively optimizing code where touching every element
  61  * twice (or touching never-used elements once) shows up in profiling,
  62  * and where restructuring the code to use fixed-length arrays or IOBuf-s
  63  * would be difficult.
  64  *
  65  * NOTE: Just because .resize() shows up in your profile (probably
  66  * via one of the intrinsic memset implementations) doesn't mean that
  67  * these functions will make your program faster.  A lot of the cost
  68  * of memset comes from cache misses, so avoiding the memset can mean
  69  * that the cache miss cost just gets pushed to the following code.
  70  * resizeWithoutInitialization can be a win when the contents are bigger
  71  * than a cache level, because the second access isn't free in that case.
  72  * It can be a win when the memory is already cached, so touching it
  73  * doesn't help later code.  It can also be a win if the final length
  74  * of the string or vector isn't actually known, so the suffix will be
  75  * chopped off with a second call to .resize().
  76  */
  77
  78 /**
  79  * Like calling s.resize(n), but when growing the string does not
  80  * initialize new elements.  It is undefined behavior to read from
  81  * any element added to the string by this method unless it has been
  82  * written to by an operation that follows this call.
  83  *
  84  * IMPORTANT: Read the warning at the top of this header file.
  85  */
  86 inline void resizeWithoutInitialization(std::string& s, std::size_t n) {
  87   if (n <= s.size()) {
  88     s.resize(n);
  89   } else {
  90     // careful not to call reserve unless necessary, as it causes
  91     // shrink_to_fit on many platforms
  92     if (n > s.capacity()) {
  93       s.reserve(n);
  94     }
  95     detail::unsafeStringSetLargerSize(s, n);
  96   }
  97 }
  98
  99 /**
 100  * Like calling v.resize(n), but when growing the vector does not construct
 101  * or initialize new elements.  It is undefined behavior to read from any
 102  * element added to the vector by this method unless it has been written
 103  * to by an operation that follows this call.
 104  *
 105  * Use the FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(T) macro to
 106  * declare (and inline define) the internals required to call
 107  * resizeWithoutInitialization for a std::vector<T>.  This must
 108  * be done exactly once in each translation unit that wants to call
 109  * resizeWithoutInitialization(std::vector<T>&,size_t).  char and unsigned
 110  * char are provided by default.  If you don't do this you will get linker
 111  * errors about folly::detail::unsafeVectorSetLargerSize.  Requiring that
 112  * T be trivially_destructible is only an approximation of the property
 113  * required of T.  In fact what is required is that any random sequence of
 114  * bytes may be safely reinterpreted as a T and passed to T's destructor.
 115  *
 116  * std::vector<bool> has specialized internals and is not supported.
 117  *
 118  * IMPORTANT: Read the warning at the top of this header file.
 119  */
 120 template <
 121     typename T,
 122     typename = typename std::enable_if<
 123         std::is_trivially_destructible<T>::value &&
 124         !std::is_same<T, bool>::value>::type>
 125 void resizeWithoutInitialization(std::vector<T>& v, std::size_t n) {
 126   if (n <= v.size()) {
 127     v.resize(n);
 128   } else {
 129     if (n > v.capacity()) {
 130       v.reserve(n);
 131     }
 132     detail::unsafeVectorSetLargerSize(v, n);
 133   }
 134 }
 135
 136 namespace detail {
 137
 138 #if defined(_LIBCPP_STRING)
 139 // libc++
 140
 141 } // namespace detail
 142 } // namespace folly
 143 template void std::string::__set_size(std::size_t);
 144 namespace folly {
 145 namespace detail {
 146
 147 template <typename Tag, typename T, typename A, A Ptr__set_size>
 148 struct MakeUnsafeStringSetLargerSize {
 149   friend void unsafeStringSetLargerSize(
 150       std::basic_string<T>& s,
 151       std::size_t n) {
 152     // s.__set_size(n);
 153     (s.*Ptr__set_size)(n);
 154     (&s[0])[n] = '\0';
 155   }
 156 };
 157 template struct MakeUnsafeStringSetLargerSize<
 158     FollyMemoryDetailTranslationUnitTag,
 159     char,
 160     void (std::string::*)(std::size_t),
 161     &std::string::__set_size>;
 162
 163 #elif defined(_GLIBCXX_USE_FB)
 164 // FBString
 165
 166 template <typename Tag, typename T, typename A, A Ptrstore_>
 167 struct MakeUnsafeStringSetLargerSize {
 168   friend void unsafeStringSetLargerSize(
 169       std::basic_string<T>& s,
 170       std::size_t n) {
 171     // s.store_.expandNoinit(n - s.size(), false);
 172     (s.*Ptrstore_).expandNoinit(n - s.size(), false);
 173   }
 174 };
 175 template struct MakeUnsafeStringSetLargerSize<
 176     FollyMemoryDetailTranslationUnitTag,
 177     char,
 178     std::fbstring_core<char>(std::string::*),
 179     &std::string::store_>;
 180
 181 #elif defined(_GLIBCXX_STRING) && _GLIBCXX_USE_CXX11_ABI
 182 // libstdc++ new implementation with SSO
 183
 184 } // namespace detail
 185 } // namespace folly
 186 template void std::string::_M_set_length(std::size_t);
 187 namespace folly {
 188 namespace detail {
 189
 190 template <typename Tag, typename T, typename A, A Ptr_M_set_length>
 191 struct MakeUnsafeStringSetLargerSize {
 192   friend void unsafeStringSetLargerSize(
 193       std::basic_string<T>& s,
 194       std::size_t n) {
 195     // s._M_set_length(n);
 196     (s.*Ptr_M_set_length)(n);
 197   }
 198 };
 199 template struct MakeUnsafeStringSetLargerSize<
 200     FollyMemoryDetailTranslationUnitTag,
 201     char,
 202     void (std::string::*)(std::size_t),
 203     &std::string::_M_set_length>;
 204
 205 #elif defined(_GLIBCXX_STRING)
 206 // libstdc++ old implementation
 207
 208 } // namespace detail
 209 } // namespace folly
 210 template std::string::_Rep* std::string::_M_rep() const;
 211 template void std::string::_Rep::_M_set_length_and_sharable(std::size_t);
 212 namespace folly {
 213 namespace detail {
 214
 215 template <
 216     typename Tag,
 217     typename T,
 218     typename A,
 219     A Ptr_M_rep,
 220     typename B,
 221     B Ptr_M_set_length_and_sharable>
 222 struct MakeUnsafeStringSetLargerSize {
 223   friend void unsafeStringSetLargerSize(
 224       std::basic_string<T>& s,
 225       std::size_t n) {
 226     // s._M_rep()->_M_set_length_and_sharable(n);
 227     auto rep = (s.*Ptr_M_rep)();
 228     (rep->*Ptr_M_set_length_and_sharable)(n);
 229   }
 230 };
 231 template struct MakeUnsafeStringSetLargerSize<
 232     FollyMemoryDetailTranslationUnitTag,
 233     char,
 234     std::string::_Rep* (std::string::*)() const,
 235     &std::string::_M_rep,
 236     void (std::string::_Rep::*)(std::size_t),
 237     &std::string::_Rep::_M_set_length_and_sharable>;
 238
 239 #elif defined(_MSC_VER)
 240 // MSVC
 241
 242 inline void unsafeStringSetLargerSize(std::string& s, std::size_t n) {
 243   s._Eos(n);
 244 }
 245
 246 #else
 247 #warning "No implementation for resizeWithoutInitialization of std::string"
 248 #endif
 249
 250 // This machinery bridges template expansion and macro expansion
 251 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)              \
 252   namespace folly {                                                      \
 253   namespace detail {                                                     \
 254   void unsafeVectorSetLargerSizeImpl(std::vector<TYPE>& v, std::size_t); \
 255   template <>                                                            \
 256   inline void unsafeVectorSetLargerSize<TYPE>(                           \
 257       std::vector<TYPE> & v,                                             \
 258       std::size_t n) {                                                   \
 259     unsafeVectorSetLargerSizeImpl(v, n);                                 \
 260   }                                                                      \
 261   }                                                                      \
 262   }
 263
 264 #if defined(_LIBCPP_VECTOR)
 265 // libc++
 266
 267 template <typename Tag, typename T, typename A, A Ptr__end_>
 268 struct MakeUnsafeVectorSetLargerSize {
 269   friend void unsafeVectorSetLargerSizeImpl(std::vector<T>& v, std::size_t n) {
 270     // v.__end_ += (n - v.size());
 271     using Base = std::__vector_base<T, std::allocator<T>>;
 272     static_assert(
 273         std::is_standard_layout<std::vector<T>>::value &&
 274             sizeof(std::vector<T>) == sizeof(Base),
 275         "reinterpret_cast safety conditions not met");
 276     reinterpret_cast<Base&>(v).*Ptr__end_ += (n - v.size());
 277   }
 278 };
 279
 280 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE)          \
 281   template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
 282       FollyMemoryDetailTranslationUnitTag,                      \
 283       TYPE,                                                     \
 284       TYPE*(std::__vector_base<TYPE, std::allocator<TYPE>>::*), \
 285       &std::vector<TYPE>::__end_>;                              \
 286   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 287
 288 #elif defined(_GLIBCXX_VECTOR)
 289 // libstdc++
 290
 291 template <
 292     typename Tag,
 293     typename T,
 294     typename A,
 295     A Ptr_M_impl,
 296     typename B,
 297     B Ptr_M_finish>
 298 struct MakeUnsafeVectorSetLargerSize : std::vector<T> {
 299   friend void unsafeVectorSetLargerSizeImpl(std::vector<T>& v, std::size_t n) {
 300     // v._M_impl._M_finish += (n - v.size());
 301     (v.*Ptr_M_impl).*Ptr_M_finish += (n - v.size());
 302   }
 303 };
 304
 305 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE)          \
 306   template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
 307       FollyMemoryDetailTranslationUnitTag,                      \
 308       TYPE,                                                     \
 309       std::vector<TYPE>::_Vector_impl(                          \
 310           std::_Vector_base<TYPE, std::allocator<TYPE>>::*),    \
 311       &std::vector<TYPE>::_M_impl,                              \
 312       TYPE*(std::vector<TYPE>::_Vector_impl::*),                \
 313       &std::vector<TYPE>::_Vector_impl::_M_finish>;             \
 314   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 315
 316 #elif defined(_MSC_VER)
 317 // MSVC
 318
 319 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE) \
 320   extern inline void unsafeVectorSetLargerSizeImpl(    \
 321       std::vector<TYPE>& v, std::size_t n) {           \
 322     v._Mylast() += (n - v.size());                     \
 323   }                                                    \
 324   FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
 325
 326 #else
 327 #warning "No implementation for resizeWithoutInitialization of std::vector"
 328 #endif
 329
 330 } // namespace detail
 331 } // namespace folly
 332
 333 #if defined(FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT)
 334 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(char)
 335 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(unsigned char)
 336 #endif