2 * Copyright 2017-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include <type_traits>
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 {};
36 void unsafeStringSetLargerSize(std::string& s, std::size_t n);
38 void unsafeVectorSetLargerSize(std::vector<T>& v, std::size_t n);
42 * This file provides helper functions resizeWithoutInitialization()
43 * that can resize std::string or std::vector without constructing or
44 * initializing new elements.
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.
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.
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
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().
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.
84 * IMPORTANT: Read the warning at the top of this header file.
86 inline void resizeWithoutInitialization(std::string& s, std::size_t n) {
90 // careful not to call reserve unless necessary, as it causes
91 // shrink_to_fit on many platforms
92 if (n > s.capacity()) {
95 detail::unsafeStringSetLargerSize(s, n);
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.
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.
116 * std::vector<bool> has specialized internals and is not supported.
118 * IMPORTANT: Read the warning at the top of this header file.
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) {
129 if (n > v.capacity()) {
132 detail::unsafeVectorSetLargerSize(v, n);
138 #if defined(_LIBCPP_STRING)
141 } // namespace detail
143 template void std::string::__set_size(std::size_t);
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,
153 (s.*Ptr__set_size)(n);
157 template struct MakeUnsafeStringSetLargerSize<
158 FollyMemoryDetailTranslationUnitTag,
160 void (std::string::*)(std::size_t),
161 &std::string::__set_size>;
163 #elif defined(_GLIBCXX_USE_FB)
166 template <typename Tag, typename T, typename A, A Ptrstore_>
167 struct MakeUnsafeStringSetLargerSize {
168 friend void unsafeStringSetLargerSize(
169 std::basic_string<T>& s,
171 // s.store_.expandNoinit(n - s.size(), false);
172 (s.*Ptrstore_).expandNoinit(n - s.size(), false);
175 template struct MakeUnsafeStringSetLargerSize<
176 FollyMemoryDetailTranslationUnitTag,
178 std::fbstring_core<char>(std::string::*),
179 &std::string::store_>;
181 #elif defined(_GLIBCXX_STRING) && _GLIBCXX_USE_CXX11_ABI
182 // libstdc++ new implementation with SSO
184 } // namespace detail
186 template void std::string::_M_set_length(std::size_t);
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,
195 // s._M_set_length(n);
196 (s.*Ptr_M_set_length)(n);
199 template struct MakeUnsafeStringSetLargerSize<
200 FollyMemoryDetailTranslationUnitTag,
202 void (std::string::*)(std::size_t),
203 &std::string::_M_set_length>;
205 #elif defined(_GLIBCXX_STRING)
206 // libstdc++ old implementation
208 } // namespace detail
210 template std::string::_Rep* std::string::_M_rep() const;
211 template void std::string::_Rep::_M_set_length_and_sharable(std::size_t);
221 B Ptr_M_set_length_and_sharable>
222 struct MakeUnsafeStringSetLargerSize {
223 friend void unsafeStringSetLargerSize(
224 std::basic_string<T>& s,
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);
231 template struct MakeUnsafeStringSetLargerSize<
232 FollyMemoryDetailTranslationUnitTag,
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>;
239 #elif defined(_MSC_VER)
242 inline void unsafeStringSetLargerSize(std::string& s, std::size_t n) {
247 #warning "No implementation for resizeWithoutInitialization of std::string"
250 // This machinery bridges template expansion and macro expansion
251 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE) \
254 void unsafeVectorSetLargerSizeImpl(std::vector<TYPE>& v, std::size_t); \
256 inline void unsafeVectorSetLargerSize<TYPE>( \
257 std::vector<TYPE> & v, \
259 unsafeVectorSetLargerSizeImpl(v, n); \
264 #if defined(_LIBCPP_VECTOR)
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>>;
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());
280 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE) \
281 template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
282 FollyMemoryDetailTranslationUnitTag, \
284 TYPE*(std::__vector_base<TYPE, std::allocator<TYPE>>::*), \
285 &std::vector<TYPE>::__end_>; \
286 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
288 #elif defined(_GLIBCXX_VECTOR)
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());
305 #define FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(TYPE) \
306 template struct folly::detail::MakeUnsafeVectorSetLargerSize< \
307 FollyMemoryDetailTranslationUnitTag, \
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)
316 #elif defined(_MSC_VER)
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()); \
324 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT_IMPL(TYPE)
327 #warning "No implementation for resizeWithoutInitialization of std::vector"
330 } // namespace detail
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)