folly/test/ArenaTest.cpp

   1 /*
   2  * Copyright 2014 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
  20 #include <set>
  21 #include <vector>
  22
  23 #include <glog/logging.h>
  24 #include <gtest/gtest.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 + 1);
  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 + 1);
  63   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  64   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  65   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  66           << maximum_size;
  67
  68   // Insert something huge
  69   ptr = static_cast<size_t*>(arena.allocate(10 * requestedBlockSize));
  70   allocatedItems.insert(ptr);
  71   minimum_size += 10 * requestedBlockSize;
  72   maximum_size += goodMallocSize(10 * requestedBlockSize + 1);
  73   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  74   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  75   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  76           << maximum_size;
  77
  78   // Nuke 'em all
  79   for (const auto& item : allocatedItems) {
  80     arena.deallocate(item);
  81   }
  82   //The total size should be the same
  83   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  84   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  85   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  86           << maximum_size;
  87 }
  88
  89 TEST(Arena, BytesUsedSanity) {
  90   static const size_t smallChunkSize = 1024;
  91   static const size_t blockSize = goodMallocSize(16 * smallChunkSize);
  92   const size_t bigChunkSize = blockSize - 4 * smallChunkSize;
  93
  94   size_t bytesUsed = 0;
  95
  96   SysArena arena(blockSize);
  97   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
  98
  99   // Insert 2 small chunks
 100   arena.allocate(smallChunkSize);
 101   arena.allocate(smallChunkSize);
 102   bytesUsed += 2 * smallChunkSize;
 103   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 104   EXPECT_TRUE(arena.totalSize() >= blockSize);
 105   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 106
 107   // Insert big chunk, should still fit in one block
 108   arena.allocate(bigChunkSize);
 109   bytesUsed += bigChunkSize;
 110   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 111   EXPECT_TRUE(arena.totalSize() >= blockSize);
 112   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 113
 114   // Insert big chunk once more, should trigger new block allocation
 115   arena.allocate(bigChunkSize);
 116   bytesUsed += bigChunkSize;
 117   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 118   EXPECT_TRUE(arena.totalSize() >= 2 * blockSize);
 119   EXPECT_TRUE(arena.totalSize() <= 3 * blockSize);
 120
 121   // Test that bytesUsed() accounts for alignment
 122   static const size_t tinyChunkSize = 7;
 123   arena.allocate(tinyChunkSize);
 124   EXPECT_TRUE(arena.bytesUsed() >= bytesUsed + tinyChunkSize);
 125   size_t delta = arena.bytesUsed() - bytesUsed;
 126   EXPECT_EQ(delta & (delta - 1), 0);
 127 }
 128
 129 TEST(Arena, Vector) {
 130   static const size_t requestedBlockSize = 64;
 131   SysArena arena(requestedBlockSize);
 132
 133   EXPECT_EQ(arena.totalSize(), sizeof(SysArena));
 134
 135   std::vector<size_t, StlAllocator<SysArena, size_t>>
 136     vec { {}, StlAllocator<SysArena, size_t>(&arena) };
 137
 138   for (size_t i = 0; i < 1000; i++) {
 139     vec.push_back(i);
 140   }
 141
 142   for (size_t i = 0; i < 1000; i++) {
 143     EXPECT_EQ(i, vec[i]);
 144   }
 145 }
 146
 147 TEST(Arena, SizeLimit) {
 148   static const size_t requestedBlockSize = sizeof(size_t);
 149   static const size_t maxSize = 10 * requestedBlockSize;
 150
 151   SysArena arena(requestedBlockSize, maxSize);
 152
 153   void* a = arena.allocate(sizeof(size_t));
 154   EXPECT_TRUE(a != nullptr);
 155   EXPECT_THROW(arena.allocate(maxSize + 1), std::bad_alloc);
 156 }
 157
 158 int main(int argc, char *argv[]) {
 159   testing::InitGoogleTest(&argc, argv);
 160   google::ParseCommandLineFlags(&argc, &argv, true);
 161   auto ret = RUN_ALL_TESTS();
 162   return ret;
 163 }