folly/memory/test/UninitializedMemoryHacksTest.cpp

   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 #include "folly/memory/UninitializedMemoryHacks.h"
  18
  19 #include <algorithm>
  20 #include <string>
  21 #include <vector>
  22
  23 #include <folly/Memory.h>
  24 #include <folly/Random.h>
  25 #include <folly/portability/GTest.h>
  26 #include <glog/logging.h>
  27
  28 void describePlatform() {
  29   LOG(INFO) << "sizeof(void*) = " << sizeof(void*);
  30
  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";
  44 #else
  45   LOG(INFO) << "UNKNOWN std::string implementation";
  46 #endif
  47
  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";
  57 #else
  58   LOG(INFO) << "UNKNOWN std::vector implementation";
  59 #endif
  60 }
  61
  62 // Returns a concatenation of target[i] for those i where valid[i]
  63 template <typename T>
  64 T validData(T const& target, std::vector<bool> const& valid) {
  65   EXPECT_EQ(target.size(), valid.size());
  66   T rv;
  67   for (std::size_t i = 0; i < valid.size(); ++i) {
  68     if (valid[i]) {
  69       rv.push_back(target[i]);
  70     }
  71   }
  72   return rv;
  73 }
  74
  75 template <typename T>
  76 void doResizeWithoutInit(
  77     T& target,
  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);
  87   } else {
  88     EXPECT_GE(before.size(), after.size());
  89     EXPECT_TRUE(std::equal(after.begin(), after.end(), before.begin()));
  90   }
  91 }
  92
  93 template <typename T>
  94 void doOverwrite(
  95     T& target,
  96     std::vector<bool>& valid,
  97     std::size_t b,
  98     std::size_t e) {
  99   for (auto i = b; i < e && i < target.size(); ++i) {
 100     target[i] = '0' + (i % 10);
 101     valid[i] = true;
 102   }
 103 }
 104
 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) {
 112     valid[i] = true;
 113   }
 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()));
 120   } else {
 121     EXPECT_GE(before.size(), after.size());
 122     EXPECT_TRUE(std::equal(after.begin(), after.end(), before.begin()));
 123   }
 124 }
 125
 126 template <typename T>
 127 void doClear(T& target, std::vector<bool>& valid) {
 128   target.clear();
 129   valid.clear();
 130 }
 131
 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);
 136 }
 137
 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);
 142 }
 143
 144 template <typename T>
 145 void doPushBack(T& target, std::vector<bool>& valid) {
 146   target.push_back('P');
 147   valid.push_back(true);
 148 }
 149
 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());
 160   }
 161 }
 162
 163 template <typename T>
 164 void check(T& target) {
 165   genericCheck(target);
 166 }
 167
 168 template <>
 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');
 173 }
 174
 175 template <typename T>
 176 void testSimple() {
 177   describePlatform();
 178
 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) {
 182       {
 183         T target;
 184         std::vector<bool> valid;
 185         doResize(target, valid, i);
 186         doResizeWithoutInit(target, valid, j);
 187         check(target);
 188       }
 189
 190       {
 191         T target;
 192         std::vector<bool> valid;
 193         doResize(target, valid, i);
 194         doResizeWithoutInit(target, valid, j);
 195         doOverwrite(target, valid, i, j);
 196         check(target);
 197       }
 198
 199       {
 200         T target;
 201         std::vector<bool> valid;
 202         doResizeWithoutInit(target, valid, i);
 203         doResize(target, valid, j);
 204         doOverwrite(target, valid, i / 2, i / 2);
 205         check(target);
 206       }
 207
 208       {
 209         T target;
 210         std::vector<bool> valid;
 211         doResizeWithoutInit(target, valid, i);
 212         doResize(target, valid, j);
 213         doOverwrite(target, valid, i, j);
 214         check(target);
 215       }
 216     }
 217   }
 218 }
 219
 220 template <typename T>
 221 void testRandom(size_t numSteps = 10000) {
 222   describePlatform();
 223
 224   auto target = folly::make_unique<T>();
 225   std::vector<bool> valid;
 226
 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));
 230
 231     if (pct < 5) {
 232       doClear(*target, valid);
 233     } else if (pct < 30) {
 234       T copy;
 235       folly::resizeWithoutInitialization(copy, target->size());
 236       for (size_t i = 0; i < copy.size(); ++i) {
 237         if (valid[i]) {
 238           copy[i] = target->at(i);
 239         }
 240       }
 241       if (pct < 10) {
 242         std::swap(copy, *target);
 243       } else if (pct < 15) {
 244         *target = std::move(copy);
 245       } else if (pct < 20) {
 246         *target = copy;
 247       } else if (pct < 25) {
 248         target = folly::make_unique<T>(std::move(copy));
 249       } else {
 250         target = folly::make_unique<T>(copy);
 251       }
 252     } else if (pct < 35) {
 253       target->reserve(v);
 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());
 263       }
 264     } else if (pct < 60) {
 265       doPushBack(*target, valid);
 266     } else if (pct < 65) {
 267       target = folly::make_unique<T>();
 268       valid.clear();
 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));
 272     } else {
 273       doResizeWithoutInit(*target, valid, v);
 274     }
 275
 276     // don't check every time in implementation does lazy work
 277     if (folly::Random::rand32(100) < 50) {
 278       check(*target);
 279     }
 280   }
 281 }
 282
 283 TEST(UninitializedMemoryHacks, simpleString) {
 284   testSimple<std::string>();
 285 }
 286
 287 TEST(UninitializedMemoryHacks, simpleVectorChar) {
 288   testSimple<std::vector<char>>();
 289 }
 290
 291 TEST(UninitializedMemoryHacks, simpleVectorByte) {
 292   testSimple<std::vector<uint8_t>>();
 293 }
 294
 295 TEST(UninitializedMemoryHacks, simpleVectorInt) {
 296   testSimple<std::vector<int>>();
 297 }
 298
 299 TEST(UninitializedMemoryHacks, randomString) {
 300   testRandom<std::string>();
 301 }
 302
 303 TEST(UninitializedMemoryHacks, randomVectorChar) {
 304   testRandom<std::vector<char>>();
 305 }
 306
 307 TEST(UninitializedMemoryHacks, randomVectorByte) {
 308   testRandom<std::vector<uint8_t>>();
 309 }
 310
 311 TEST(UninitializedMemoryHacks, randomVectorInt) {
 312   testRandom<std::vector<int>>();
 313 }
 314
 315 // We are deliberately putting this at the bottom to make sure it can follow use
 316 FOLLY_DECLARE_VECTOR_RESIZE_WITHOUT_INIT(int)