1/*
2 * Copyright 2012-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/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
26using namespace folly;
27
28static_assert(AllocatorHasTrivialDeallocate<SysArena>::value, "");
29
30TEST(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 +=
63 10 * goodMallocSize(requestedBlockSize + 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 +=
74 goodMallocSize(10 * requestedBlockSize + 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, 0 /* unused */);
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
91TEST(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
131TEST(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, SysArenaAllocator<size_t>> vec{
138 {}, SysArenaAllocator<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
149TEST(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
160int main(int argc, char* argv[]) {
161 testing::InitGoogleTest(&argc, argv);
162 gflags::ParseCommandLineFlags(&argc, &argv, true);
163 auto ret = RUN_ALL_TESTS();
164 return ret;
165}
166