folly/test/ArenaTest.cpp

   1 /*
   2  * Copyright 2012 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/StlAllocator.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 TEST(Arena, SizeSanity) {
  29   std::set<size_t*> allocatedItems;
  30
  31   static const size_t requestedBlockSize = 64;
  32   SysArena arena(requestedBlockSize);
  33   size_t minimum_size = sizeof(SysArena), maximum_size = minimum_size;
  34   EXPECT_EQ(arena.totalSize(), minimum_size);
  35
  36   // Insert a single small element to get a new block
  37   size_t* ptr = static_cast<size_t*>(arena.allocate(sizeof(long)));
  38   allocatedItems.insert(ptr);
  39   minimum_size += requestedBlockSize;
  40   maximum_size += goodMallocSize(requestedBlockSize + 1);
  41   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  42   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  43   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  44           << maximum_size;
  45
  46   // Insert a larger element, size should be the same
  47   ptr = static_cast<size_t*>(arena.allocate(requestedBlockSize / 2));
  48   allocatedItems.insert(ptr);
  49   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  50   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  51   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  52           << maximum_size;
  53
  54   // Insert 10 full block sizes to get 10 new blocks
  55   for (int i = 0; i < 10; i++) {
  56     ptr = static_cast<size_t*>(arena.allocate(requestedBlockSize));
  57     allocatedItems.insert(ptr);
  58   }
  59   minimum_size += 10 * requestedBlockSize;
  60   maximum_size += 10 * goodMallocSize(requestedBlockSize + 1);
  61   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  62   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  63   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  64           << maximum_size;
  65
  66   // Insert something huge
  67   ptr = static_cast<size_t*>(arena.allocate(10 * requestedBlockSize));
  68   allocatedItems.insert(ptr);
  69   minimum_size += 10 * requestedBlockSize;
  70   maximum_size += goodMallocSize(10 * requestedBlockSize + 1);
  71   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  72   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  73   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  74           << maximum_size;
  75
  76   // Nuke 'em all
  77   for (const auto& item : allocatedItems) {
  78     arena.deallocate(item);
  79   }
  80   //The total size should be the same
  81   EXPECT_TRUE(arena.totalSize() >= minimum_size);
  82   EXPECT_TRUE(arena.totalSize() <= maximum_size);
  83   VLOG(4) << minimum_size << " < " << arena.totalSize() << " < "
  84           << maximum_size;
  85 }
  86
  87 TEST(Arena, BytesUsedSanity) {
  88   static const size_t smallChunkSize = 1024;
  89   static const size_t blockSize = goodMallocSize(16 * smallChunkSize);
  90   const size_t bigChunkSize = blockSize - 4 * smallChunkSize;
  91
  92   size_t bytesUsed = 0;
  93
  94   SysArena arena(blockSize);
  95   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
  96
  97   // Insert 2 small chunks
  98   arena.allocate(smallChunkSize);
  99   arena.allocate(smallChunkSize);
 100   bytesUsed += 2 * smallChunkSize;
 101   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 102   EXPECT_TRUE(arena.totalSize() >= blockSize);
 103   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 104
 105   // Insert big chunk, should still fit in one block
 106   arena.allocate(bigChunkSize);
 107   bytesUsed += bigChunkSize;
 108   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 109   EXPECT_TRUE(arena.totalSize() >= blockSize);
 110   EXPECT_TRUE(arena.totalSize() <= 2 * blockSize);
 111
 112   // Insert big chunk once more, should trigger new block allocation
 113   arena.allocate(bigChunkSize);
 114   bytesUsed += bigChunkSize;
 115   EXPECT_EQ(arena.bytesUsed(), bytesUsed);
 116   EXPECT_TRUE(arena.totalSize() >= 2 * blockSize);
 117   EXPECT_TRUE(arena.totalSize() <= 3 * blockSize);
 118
 119   // Test that bytesUsed() accounts for alignment
 120   static const size_t tinyChunkSize = 7;
 121   arena.allocate(tinyChunkSize);
 122   EXPECT_TRUE(arena.bytesUsed() >= bytesUsed + tinyChunkSize);
 123   size_t delta = arena.bytesUsed() - bytesUsed;
 124   EXPECT_EQ(delta & (delta - 1), 0);
 125 }
 126
 127 TEST(Arena, Vector) {
 128   static const size_t requestedBlockSize = 64;
 129   SysArena arena(requestedBlockSize);
 130
 131   EXPECT_EQ(arena.totalSize(), sizeof(SysArena));
 132
 133   std::vector<size_t, StlAllocator<SysArena, size_t>>
 134     vec { {}, StlAllocator<SysArena, size_t>(&arena) };
 135
 136   for (size_t i = 0; i < 1000; i++) {
 137     vec.push_back(i);
 138   }
 139
 140   for (size_t i = 0; i < 1000; i++) {
 141     EXPECT_EQ(i, vec[i]);
 142   }
 143 }
 144
 145 int main(int argc, char *argv[]) {
 146   testing::InitGoogleTest(&argc, argv);
 147   google::ParseCommandLineFlags(&argc, &argv, true);
 148   auto ret = RUN_ALL_TESTS();
 149   return ret;
 150 }