folly/test/ArenaTest.cpp

   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 #include <folly/Arena.h>
  18 #include <folly/Memory.h>
  19 #include <folly/portability/GTest.h>
  20
  21 #include <set>
  22 #include <vector>
  23
  24 #include <glog/logging.h>
  25
  26 using namespace folly;
  27
  28 static_assert(IsArenaAllocator<SysArena>::value, "");
  29
  30 TEST(Arena, SizeSanity) {
  31   std::set<size_t*> allocatedItems;
  32
  33   static const size_t requestedBlockSize = 64;
  34   SysArena arena(requestedBlockSize);
  35   size_t minimum_size = sizeof(SysArena), maximum_size = minimum_size;
  36   EXPECT_EQ(arena.totalSize(), minimum_size);
  37
  38   // Insert a single small element to get a new block
  39   size_t* ptr = static_cast<size_t*>(arena.allocate(sizeof(long)));
  40   allocatedItems.insert(ptr);
  41   minimum_size += requestedBlockSize;
  42   maximum_size += goodMallocSize(requestedBlockSize + SysArena::kBlockOverhead);
  43   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  44   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  45   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  46           << maximum_size;
  47
  48   // Insert a larger element, size should be the same
  49   ptr = static_cast<size_t*>(arena.allocate(requestedBlockSize / 2));
  50   allocatedItems.insert(ptr);
  51   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  52   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  53   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  54           << maximum_size;
  55
  56   // Insert 10 full block sizes to get 10 new blocks
  57   for (int i = 0; i < 10; i++) {
  58     ptr = static_cast<size_t*>(arena.allocate(requestedBlockSize));
  59     allocatedItems.insert(ptr);
  60   }
  61   minimum_size += 10 * requestedBlockSize;
  62   maximum_size += 10 * goodMallocSize(requestedBlockSize
  63                                       + SysArena::kBlockOverhead);
  64   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  65   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  66   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  67           << maximum_size;
  68
  69   // Insert something huge
  70   ptr = static_cast<size_t*>(arena.allocate(10 * requestedBlockSize));
  71   allocatedItems.insert(ptr);
  72   minimum_size += 10 * requestedBlockSize;
  73   maximum_size += goodMallocSize(10 * requestedBlockSize
  74                                  + SysArena::kBlockOverhead);
  75   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  76   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  77   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  78           << maximum_size;
  79
  80   // Nuke 'em all
  81   for (const auto& item : allocatedItems) {
  82     arena.deallocate(item);
  83   }
  84   //The total size should be the same
  85   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  86   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  87   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  88           << maximum_size;
  89 }
  90
  91 TEST(Arena, BytesUsedSanity) {
  92   static const size_t smallChunkSize = 1024;
  93   static const size_t blockSize = goodMallocSize(16 * smallChunkSize);
  94   const size_t bigChunkSize = blockSize - 4 * smallChunkSize;
  95
  96   size_t bytesUsed = 0;
  97
  98   SysArena arena(blockSize);
  99   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 100
 101   // Insert 2 small chunks
 102   arena.allocate(smallChunkSize);
 103   arena.allocate(smallChunkSize);
 104   bytesUsed += 2 * smallChunkSize;
 105   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 106   EXPECT_TRUE(arena.totalSize() >= blockSize);
 107   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 108
 109   // Insert big chunk, should still fit in one block
 110   arena.allocate(bigChunkSize);
 111   bytesUsed += bigChunkSize;
 112   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 113   EXPECT_TRUE(arena.totalSize() >= blockSize);
 114   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 115
 116   // Insert big chunk once more, should trigger new block allocation
 117   arena.allocate(bigChunkSize);
 118   bytesUsed += bigChunkSize;
 119   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 120   EXPECT_TRUE(arena.totalSize() >= 2 * blockSize);
 121   EXPECT_TRUE(arena.totalSize() <= 3 * blockSize);
 122
 123   // Test that bytesUsed() accounts for alignment
 124   static const size_t tinyChunkSize = 7;
 125   arena.allocate(tinyChunkSize);
 126   EXPECT_TRUE(arena.bytesUsed() >= bytesUsed + tinyChunkSize);
 127   size_t delta = arena.bytesUsed() - bytesUsed;
 128   EXPECT_EQ(delta & (delta - 1), 0);
 129 }
 130
 131 TEST(Arena, Vector) {
 132   static const size_t requestedBlockSize = 64;
 133   SysArena arena(requestedBlockSize);
 134
 135   EXPECT_EQ(arena.totalSize(), sizeof(SysArena));
 136
 137   std::vector<size_t, StlAllocator<SysArena, size_t>>
 138     vec { {}, StlAllocator<SysArena, size_t>(&arena) };
 139
 140   for (size_t i = 0; i < 1000; i++) {
 141     vec.push_back(i);
 142   }
 143
 144   for (size_t i = 0; i < 1000; i++) {
 145     EXPECT_EQ(i, vec[i]);
 146   }
 147 }
 148
 149 TEST(Arena, SizeLimit) {
 150   static const size_t requestedBlockSize = sizeof(size_t);
 151   static const size_t maxSize = 10 * requestedBlockSize;
 152
 153   SysArena arena(requestedBlockSize, maxSize);
 154
 155   void* a = arena.allocate(sizeof(size_t));
 156   EXPECT_TRUE(a != nullptr);
 157   EXPECT_THROW(arena.allocate(maxSize + 1), std::bad_alloc);
 158 }
 159
 160 TEST(Arena, MoveArena) {
 161   SysArena arena(sizeof(size_t) * 2);
 162   arena.allocate(sizeof(size_t));
 163   auto totalSize = arena.totalSize();
 164   auto bytesUsed = arena.bytesUsed();
 165
 166   SysArena moved(std::move(arena));
 167   EXPECT_EQ(totalSize, moved.totalSize());
 168   EXPECT_EQ(bytesUsed, moved.bytesUsed());
 169 }
 170
 171 int main(int argc, char *argv[]) {
 172   testing::InitGoogleTest(&argc, argv);
 173   gflags::ParseCommandLineFlags(&argc, &argv, true);
 174   auto ret = RUN_ALL_TESTS();
 175   return ret;
 176 }