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.
17 #include "folly/memory/UninitializedMemoryHacks.h"
23 #include <folly/Memory.h>
24 #include <folly/Random.h>
25 #include <folly/portability/GTest.h>
26 #include <glog/logging.h>
28 void describePlatform() {
29 LOG(INFO) << "sizeof(void*) = " << sizeof(void*);
31 LOG(INFO) << "sizeof(std::string) = " << sizeof(std::string);
32 #if defined(_LIBCPP_STRING)
33 LOG(INFO) << "std::string from libc++";
34 #elif defined(_STLP_STRING)
35 LOG(INFO) << "std::string from STLport";
36 #elif defined(_GLIBCXX_USE_FB)
37 LOG(INFO) << "std::string from FBString";
38 #elif defined(_GLIBCXX_STRING) && _GLIBCXX_USE_CXX11_ABI
39 LOG(INFO) << "std::string from libstdc++ with SSO";
40 #elif defined(_GLIBCXX_STRING)
41 LOG(INFO) << "std::string from old libstdc++";
42 #elif defined(_MSC_VER)
43 LOG(INFO) << "std::string from MSVC";
45 LOG(INFO) << "UNKNOWN std::string implementation";
48 LOG(INFO) << "sizeof(std::vector<char>) = " << sizeof(std::vector<char>);
49 #if defined(_LIBCPP_VECTOR)
50 LOG(INFO) << "std::vector from libc++";
51 #elif defined(_STLP_VECTOR)
52 LOG(INFO) << "std::vector from STLport";
53 #elif defined(_GLIBCXX_VECTOR)
54 LOG(INFO) << "std::vector from libstdc++";
55 #elif defined(_MSC_VER)
56 LOG(INFO) << "std::vector from MSVC";
58 LOG(INFO) << "UNKNOWN std::vector implementation";
62 // Returns a concatenation of target[i] for those i where valid[i]
64 T validData(T const& target, std::vector<bool> const& valid) {
65 EXPECT_EQ(target.size(), valid.size());
67 for (std::size_t i = 0; i < valid.size(); ++i) {
69 rv.push_back(target[i]);
76 void doResizeWithoutInit(
78 std::vector<bool>& valid,
79 std::size_t newSize) {
80 auto oldSize = target.size();
81 auto before = validData(target, valid);
82 folly::resizeWithoutInitialization(target, newSize);
83 valid.resize(newSize);
84 auto after = validData(target, valid);
85 if (oldSize <= newSize) {
86 EXPECT_EQ(before, after);
88 EXPECT_GE(before.size(), after.size());
89 EXPECT_TRUE(std::equal(after.begin(), after.end(), before.begin()));
96 std::vector<bool>& valid,
99 for (auto i = b; i < e && i < target.size(); ++i) {
100 target[i] = '0' + (i % 10);
105 template <typename T>
106 void doResize(T& target, std::vector<bool>& valid, std::size_t newSize) {
107 auto oldSize = target.size();
108 auto before = validData(target, valid);
109 target.resize(newSize);
110 valid.resize(newSize);
111 for (auto i = oldSize; i < newSize; ++i) {
114 auto after = validData(target, valid);
115 if (oldSize == newSize) {
116 EXPECT_EQ(before, after);
117 } else if (oldSize < newSize) {
118 EXPECT_LT(before.size(), after.size());
119 EXPECT_TRUE(std::equal(before.begin(), before.end(), after.begin()));
121 EXPECT_GE(before.size(), after.size());
122 EXPECT_TRUE(std::equal(after.begin(), after.end(), before.begin()));
126 template <typename T>
127 void doClear(T& target, std::vector<bool>& valid) {
132 template <typename T>
133 void doInsert(T& target, std::vector<bool>& valid, std::size_t i) {
134 target.insert(target.begin() + i, 'I');
135 valid.insert(valid.begin() + i, true);
138 template <typename T>
139 void doErase(T& target, std::vector<bool>& valid, std::size_t i) {
140 target.erase(target.begin() + i);
141 valid.erase(valid.begin() + i);
144 template <typename T>
145 void doPushBack(T& target, std::vector<bool>& valid) {
146 target.push_back('P');
147 valid.push_back(true);
150 template <typename T>
151 void genericCheck(T& target) {
152 EXPECT_LE(target.size(), target.capacity());
153 EXPECT_EQ(target.size() == 0, target.empty());
154 EXPECT_EQ(target.size(), target.end() - target.begin());
155 EXPECT_EQ(target.size(), target.cend() - target.cbegin());
156 if (!target.empty()) {
157 EXPECT_EQ(target.data(), &target[0]);
158 EXPECT_EQ(target.data(), &target.front());
159 EXPECT_EQ(target.data() + target.size() - 1, &target.back());
163 template <typename T>
164 void check(T& target) {
165 genericCheck(target);
169 void check<std::string>(std::string& target) {
170 genericCheck(target);
171 EXPECT_EQ(target.c_str(), target.data());
172 EXPECT_EQ(target.c_str()[target.size()], '\0');
175 template <typename T>
179 auto sizes = {0, 1, 10, 14, 15, 16, 17, 22, 23, 24, 32, 95, 100, 10000};
180 for (auto i : sizes) {
181 for (auto j : sizes) {
184 std::vector<bool> valid;
185 doResize(target, valid, i);
186 doResizeWithoutInit(target, valid, j);
192 std::vector<bool> valid;
193 doResize(target, valid, i);
194 doResizeWithoutInit(target, valid, j);
195 doOverwrite(target, valid, i, j);
201 std::vector<bool> valid;
202 doResizeWithoutInit(target, valid, i);
203 doResize(target, valid, j);
204 doOverwrite(target, valid, i / 2, i / 2);
210 std::vector<bool> valid;
211 doResizeWithoutInit(target, valid, i);
212 doResize(target, valid, j);
213 doOverwrite(target, valid, i, j);
220 template <typename T>
221 void testRandom(size_t numSteps = 10000) {
224 auto target = folly::make_unique<T>();
225 std::vector<bool> valid;
227 for (size_t step = 0; step < numSteps; ++step) {
228 auto pct = folly::Random::rand32(100);
229 auto v = folly::Random::rand32(uint32_t{3} << folly::Random::rand32(14));
232 doClear(*target, valid);
233 } else if (pct < 30) {
235 folly::resizeWithoutInitialization(copy, target->size());
236 for (size_t i = 0; i < copy.size(); ++i) {
238 copy[i] = target->at(i);
242 std::swap(copy, *target);
243 } else if (pct < 15) {
244 *target = std::move(copy);
245 } else if (pct < 20) {
247 } else if (pct < 25) {
248 target = folly::make_unique<T>(std::move(copy));
250 target = folly::make_unique<T>(copy);
252 } else if (pct < 35) {
254 } else if (pct < 40) {
255 target->shrink_to_fit();
256 } else if (pct < 45) {
257 doResize(*target, valid, v);
258 } else if (pct < 50) {
259 doInsert(*target, valid, v % (target->size() + 1));
260 } else if (pct < 55) {
261 if (!target->empty()) {
262 doErase(*target, valid, v % target->size());
264 } else if (pct < 60) {
265 doPushBack(*target, valid);
266 } else if (pct < 65) {
267 target = folly::make_unique<T>();
269 } else if (pct < 80) {
270 auto v2 = folly::Random::rand32(uint32_t{3} << folly::Random::rand32(14));
271 doOverwrite(*target, valid, std::min(v, v2), std::max(v, v2));
273 doResizeWithoutInit(*target, valid, v);
276 // don't check every time in implementation does lazy work
277 if (folly::Random::rand32(100) < 50) {
283 TEST(UninitializedMemoryHacks, simpleString) {
284 testSimple<std::string>();
287 TEST(UninitializedMemoryHacks, simpleVectorChar) {
288 testSimple<std::vector<char>>();
291 TEST(UninitializedMemoryHacks, simpleVectorByte) {
292 testSimple<std::vector<uint8_t>>();
295 TEST(UninitializedMemoryHacks, simpleVectorInt) {
296 testSimple<std::vector<int>>();
299 TEST(UninitializedMemoryHacks, randomString) {
300 testRandom<std::string>();
303 TEST(UninitializedMemoryHacks, randomVectorChar) {
304 testRandom<std::vector<char>>();
307 TEST(UninitializedMemoryHacks, randomVectorByte) {
308 testRandom<std::vector<uint8_t>>();
311 TEST(UninitializedMemoryHacks, randomVectorInt) {
312 testRandom<std::vector<int>>();
315 // We are deliberately putting this at the bottom to make sure it can follow use
316 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(int)