/Users/deen/code/yugabyte-db/src/yb/rocksdb/util/arena_test.cc
Line | Count | Source |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | |
24 | | #include <string> |
25 | | |
26 | | #include <gtest/gtest.h> |
27 | | |
28 | | #include "yb/rocksdb/util/arena.h" |
29 | | #include "yb/rocksdb/util/random.h" |
30 | | |
31 | | #include "yb/rocksdb/util/testutil.h" |
32 | | |
33 | | namespace rocksdb { |
34 | | |
35 | | namespace { |
36 | | const size_t kHugePageSize = 2 * 1024 * 1024; |
37 | | } // namespace |
38 | | class ArenaTest : public RocksDBTest {}; |
39 | | |
40 | 1 | TEST_F(ArenaTest, Empty) { Arena arena0; } |
41 | | |
42 | | namespace { |
43 | 10 | bool CheckMemoryAllocated(size_t allocated, size_t expected) { |
44 | | // The value returned by Arena::MemoryAllocatedBytes() may be greater than |
45 | | // the requested memory. We choose a somewhat arbitrary upper bound of |
46 | | // max_expected = expected * 1.1 to detect critical overallocation. |
47 | 10 | size_t max_expected = expected + expected / 10; |
48 | 10 | return allocated >= expected && allocated <= max_expected; |
49 | 10 | } |
50 | | |
51 | 2 | void MemoryAllocatedBytesTest(size_t huge_page_size) { |
52 | 2 | const int N = 17; |
53 | 2 | size_t req_sz; // requested size |
54 | 2 | size_t bsz = 32 * 1024; // block size |
55 | 2 | size_t expected_memory_allocated; |
56 | | |
57 | 2 | Arena arena(bsz, huge_page_size); |
58 | | |
59 | | // requested size > quarter of a block: |
60 | | // allocate requested size separately |
61 | 2 | req_sz = 12 * 1024; |
62 | 36 | for (int i = 0; i < N; i++) { |
63 | 34 | arena.Allocate(req_sz); |
64 | 34 | } |
65 | 2 | expected_memory_allocated = req_sz * N + Arena::kInlineSize; |
66 | 2 | ASSERT_PRED2(CheckMemoryAllocated, arena.MemoryAllocatedBytes(), |
67 | 2 | expected_memory_allocated); |
68 | | |
69 | 2 | arena.Allocate(Arena::kInlineSize - 1); |
70 | | |
71 | | // requested size < quarter of a block: |
72 | | // allocate a block with the default size, then try to use unused part |
73 | | // of the block. So one new block will be allocated for the first |
74 | | // Allocate(99) call. All the remaining calls won't lead to new allocation. |
75 | 2 | req_sz = 99; |
76 | 36 | for (int i = 0; i < N; i++) { |
77 | 34 | arena.Allocate(req_sz); |
78 | 34 | } |
79 | 2 | if (huge_page_size) { |
80 | 1 | ASSERT_TRUE( |
81 | 1 | CheckMemoryAllocated(arena.MemoryAllocatedBytes(), |
82 | 1 | expected_memory_allocated + bsz) || |
83 | 1 | CheckMemoryAllocated(arena.MemoryAllocatedBytes(), |
84 | 1 | expected_memory_allocated + huge_page_size)); |
85 | 1 | } else { |
86 | 1 | expected_memory_allocated += bsz; |
87 | 1 | ASSERT_PRED2(CheckMemoryAllocated, arena.MemoryAllocatedBytes(), |
88 | 1 | expected_memory_allocated); |
89 | 1 | } |
90 | | |
91 | | // requested size > size of a block: |
92 | | // allocate requested size separately |
93 | 2 | expected_memory_allocated = arena.MemoryAllocatedBytes(); |
94 | 2 | req_sz = 8 * 1024 * 1024; |
95 | 36 | for (int i = 0; i < N; i++) { |
96 | 34 | arena.Allocate(req_sz); |
97 | 34 | } |
98 | 2 | expected_memory_allocated += req_sz * N; |
99 | 2 | ASSERT_PRED2(CheckMemoryAllocated, arena.MemoryAllocatedBytes(), |
100 | 2 | expected_memory_allocated); |
101 | 2 | } |
102 | | |
103 | | // Make sure we didn't count the allocate but not used memory space in |
104 | | // Arena::ApproximateMemoryUsage() |
105 | 2 | static void ApproximateMemoryUsageTest(size_t huge_page_size) { |
106 | 2 | const size_t kBlockSize = 4096; |
107 | 2 | const size_t kEntrySize = kBlockSize / 8; |
108 | 2 | const size_t kZero = 0; |
109 | 2 | Arena arena(kBlockSize, huge_page_size); |
110 | 2 | ASSERT_EQ(kZero, arena.ApproximateMemoryUsage()); |
111 | | |
112 | | // allocate inline bytes |
113 | 2 | arena.AllocateAligned(8); |
114 | 2 | arena.AllocateAligned(Arena::kInlineSize / 2 - 16); |
115 | 2 | arena.AllocateAligned(Arena::kInlineSize / 2); |
116 | 2 | ASSERT_EQ(arena.ApproximateMemoryUsage(), Arena::kInlineSize - 8); |
117 | 2 | ASSERT_PRED2(CheckMemoryAllocated, arena.MemoryAllocatedBytes(), |
118 | 2 | Arena::kInlineSize); |
119 | | |
120 | 2 | auto num_blocks = kBlockSize / kEntrySize; |
121 | | |
122 | | // first allocation |
123 | 2 | arena.AllocateAligned(kEntrySize); |
124 | 2 | auto mem_usage = arena.MemoryAllocatedBytes(); |
125 | 2 | if (huge_page_size) { |
126 | 1 | ASSERT_TRUE( |
127 | 1 | CheckMemoryAllocated(mem_usage, kBlockSize + Arena::kInlineSize) || |
128 | 1 | CheckMemoryAllocated(mem_usage, huge_page_size + Arena::kInlineSize)); |
129 | 1 | } else { |
130 | 1 | ASSERT_PRED2(CheckMemoryAllocated, mem_usage, |
131 | 1 | kBlockSize + Arena::kInlineSize); |
132 | 1 | } |
133 | 2 | auto usage = arena.ApproximateMemoryUsage(); |
134 | 2 | ASSERT_LT(usage, mem_usage); |
135 | 16 | for (size_t i = 1; i < num_blocks; ++i) { |
136 | 14 | arena.AllocateAligned(kEntrySize); |
137 | 14 | ASSERT_EQ(mem_usage, arena.MemoryAllocatedBytes()); |
138 | 14 | ASSERT_EQ(arena.ApproximateMemoryUsage(), usage + kEntrySize); |
139 | 14 | usage = arena.ApproximateMemoryUsage(); |
140 | 14 | } |
141 | 2 | if (huge_page_size) { |
142 | 1 | ASSERT_TRUE(usage > mem_usage || |
143 | 1 | usage + huge_page_size - kBlockSize == mem_usage); |
144 | 1 | } else { |
145 | 1 | ASSERT_GT(usage, mem_usage); |
146 | 1 | } |
147 | 2 | } |
148 | | |
149 | 2 | static void SimpleTest(size_t huge_page_size) { |
150 | 2 | std::vector<std::pair<size_t, char*>> allocated; |
151 | 2 | Arena arena(Arena::kMinBlockSize, huge_page_size); |
152 | 2 | const int N = 100000; |
153 | 2 | size_t bytes = 0; |
154 | 2 | Random rnd(301); |
155 | 200k | for (int i = 0; i < N; i++) { |
156 | 200k | size_t s; |
157 | 200k | if (i % (N / 10) == 0) { |
158 | 20 | s = i; |
159 | 199k | } else { |
160 | 199k | s = rnd.OneIn(4000) |
161 | 52 | ? rnd.Uniform(6000) |
162 | 199k | : (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20)); |
163 | 199k | } |
164 | 200k | if (s == 0) { |
165 | | // Our arena disallows size 0 allocations. |
166 | 9.32k | s = 1; |
167 | 9.32k | } |
168 | 200k | char* r; |
169 | 200k | if (rnd.OneIn(10)) { |
170 | 20.3k | r = arena.AllocateAligned(s); |
171 | 179k | } else { |
172 | 179k | r = arena.Allocate(s); |
173 | 179k | } |
174 | | |
175 | 3.94M | for (unsigned int b = 0; b < s; b++) { |
176 | | // Fill the "i"th allocation with a known bit pattern |
177 | 3.74M | r[b] = i % 256; |
178 | 3.74M | } |
179 | 200k | bytes += s; |
180 | 200k | allocated.push_back(std::make_pair(s, r)); |
181 | 200k | ASSERT_GE(arena.ApproximateMemoryUsage(), bytes); |
182 | 200k | if (i > N / 10) { |
183 | 179k | ASSERT_LE(arena.ApproximateMemoryUsage(), bytes * 1.10); |
184 | 179k | } |
185 | 200k | } |
186 | 200k | for (unsigned int i = 0; i < allocated.size(); i++) { |
187 | 200k | size_t num_bytes = allocated[i].first; |
188 | 200k | const char* p = allocated[i].second; |
189 | 3.94M | for (unsigned int b = 0; b < num_bytes; b++) { |
190 | | // Check the "i"th allocation for the known bit pattern |
191 | 3.74M | ASSERT_EQ(static_cast<int>(p[b]) & 0xff, static_cast<int>(i % 256)); |
192 | 3.74M | } |
193 | 200k | } |
194 | 2 | } |
195 | | } // namespace |
196 | | |
197 | 1 | TEST_F(ArenaTest, MemoryAllocatedBytes) { |
198 | 1 | MemoryAllocatedBytesTest(0); |
199 | 1 | MemoryAllocatedBytesTest(kHugePageSize); |
200 | 1 | } |
201 | | |
202 | 1 | TEST_F(ArenaTest, ApproximateMemoryUsage) { |
203 | 1 | ApproximateMemoryUsageTest(0); |
204 | 1 | ApproximateMemoryUsageTest(kHugePageSize); |
205 | 1 | } |
206 | | |
207 | 1 | TEST_F(ArenaTest, Simple) { |
208 | 1 | SimpleTest(0); |
209 | 1 | SimpleTest(kHugePageSize); |
210 | 1 | } |
211 | | } // namespace rocksdb |
212 | | |
213 | 13.2k | int main(int argc, char** argv) { |
214 | 13.2k | ::testing::InitGoogleTest(&argc, argv); |
215 | 13.2k | return RUN_ALL_TESTS(); |
216 | 13.2k | } |