1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of PerconaFT.
6
7
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22 ----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35 ======= */
36
37 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39 #include "test.h"
40
ba_alloc(BlockAllocator * ba,uint64_t size,uint64_t * answer)41 static void ba_alloc(BlockAllocator *ba, uint64_t size, uint64_t *answer) {
42 ba->Validate();
43 uint64_t actual_answer;
44 ba->AllocBlock(512 * size, &actual_answer);
45 ba->Validate();
46
47 invariant(actual_answer % 512 == 0);
48 *answer = actual_answer / 512;
49 }
50
ba_free(BlockAllocator * ba,uint64_t offset,uint64_t size)51 static void ba_free(BlockAllocator *ba, uint64_t offset, uint64_t size) {
52 ba->Validate();
53 ba->FreeBlock(offset * 512, 512 * size);
54 ba->Validate();
55 }
56
ba_check_l(BlockAllocator * ba,uint64_t blocknum_in_layout_order,uint64_t expected_offset,uint64_t expected_size)57 static void ba_check_l(BlockAllocator *ba,
58 uint64_t blocknum_in_layout_order,
59 uint64_t expected_offset,
60 uint64_t expected_size) {
61 uint64_t actual_offset, actual_size;
62 int r = ba->NthBlockInLayoutOrder(
63 blocknum_in_layout_order, &actual_offset, &actual_size);
64 invariant(r == 0);
65 invariant(expected_offset * 512 == actual_offset);
66 invariant(expected_size * 512 == actual_size);
67 }
68
ba_check_none(BlockAllocator * ba,uint64_t blocknum_in_layout_order)69 static void ba_check_none(BlockAllocator *ba,
70 uint64_t blocknum_in_layout_order) {
71 uint64_t actual_offset, actual_size;
72 int r = ba->NthBlockInLayoutOrder(
73 blocknum_in_layout_order, &actual_offset, &actual_size);
74 invariant(r == -1);
75 }
76
77 // Simple block allocator test
test_ba0()78 static void test_ba0() {
79 BlockAllocator allocator;
80 BlockAllocator *ba = &allocator;
81 ba->Create(100 * 512, 1 * 512);
82 invariant(ba->AllocatedLimit() == 100 * 512);
83
84 uint64_t b2, b3, b4, b5, b6, b7;
85 ba_alloc(ba, 100, &b2);
86 ba_alloc(ba, 100, &b3);
87 ba_alloc(ba, 100, &b4);
88 ba_alloc(ba, 100, &b5);
89 ba_alloc(ba, 100, &b6);
90 ba_alloc(ba, 100, &b7);
91 ba_free(ba, b2, 100);
92 ba_alloc(ba, 100, &b2);
93 ba_free(ba, b4, 100);
94 ba_free(ba, b6, 100);
95 uint64_t b8, b9;
96 ba_alloc(ba, 100, &b4);
97 ba_free(ba, b2, 100);
98 ba_alloc(ba, 100, &b6);
99 ba_alloc(ba, 100, &b8);
100 ba_alloc(ba, 100, &b9);
101 ba_free(ba, b6, 100);
102 ba_free(ba, b7, 100);
103 ba_free(ba, b8, 100);
104 ba_alloc(ba, 100, &b6);
105 ba_alloc(ba, 100, &b7);
106 ba_free(ba, b4, 100);
107 ba_alloc(ba, 100, &b4);
108
109 ba->Destroy();
110 }
111
112 // Manually to get coverage of all the code in the block allocator.
test_ba1(int n_initial)113 static void test_ba1(int n_initial) {
114 BlockAllocator allocator;
115 BlockAllocator *ba = &allocator;
116 ba->Create(0 * 512, 1 * 512);
117
118 int n_blocks = 0;
119 uint64_t blocks[1000];
120 for (int i = 0; i < 1000; i++) {
121 if (i < n_initial || random() % 2 == 0) {
122 if (n_blocks < 1000) {
123 ba_alloc(ba, 1, &blocks[n_blocks]);
124 // printf("A[%d]=%ld\n", n_blocks, blocks[n_blocks]);
125 n_blocks++;
126 }
127 } else {
128 if (n_blocks > 0) {
129 int blocknum = random() % n_blocks;
130 // printf("F[%d]=%ld\n", blocknum, blocks[blocknum]);
131 ba_free(ba, blocks[blocknum], 1);
132 blocks[blocknum] = blocks[n_blocks - 1];
133 n_blocks--;
134 }
135 }
136 }
137
138 ba->Destroy();
139 }
140
141 // Check to see if it is first fit or best fit.
test_ba2(void)142 static void test_ba2(void) {
143 BlockAllocator allocator;
144 BlockAllocator *ba = &allocator;
145 uint64_t b[6];
146 enum { BSIZE = 1024 };
147 ba->Create(100 * 512, BSIZE * 512);
148 invariant(ba->AllocatedLimit() == 100 * 512);
149
150 ba_check_l(ba, 0, 0, 100);
151 ba_check_none(ba, 1);
152
153 ba_alloc(ba, 100, &b[0]);
154 ba_check_l(ba, 0, 0, 100);
155 ba_check_l(ba, 1, BSIZE, 100);
156 ba_check_none(ba, 2);
157
158 ba_alloc(ba, BSIZE + 100, &b[1]);
159 ba_check_l(ba, 0, 0, 100);
160 ba_check_l(ba, 1, BSIZE, 100);
161 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
162 ba_check_none(ba, 3);
163
164 ba_alloc(ba, 100, &b[2]);
165 ba_check_l(ba, 0, 0, 100);
166 ba_check_l(ba, 1, BSIZE, 100);
167 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
168 ba_check_l(ba, 3, 4 * BSIZE, 100);
169 ba_check_none(ba, 4);
170
171 ba_alloc(ba, 100, &b[3]);
172 ba_alloc(ba, 100, &b[4]);
173 ba_alloc(ba, 100, &b[5]);
174 ba_check_l(ba, 0, 0, 100);
175 ba_check_l(ba, 1, BSIZE, 100);
176 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
177 ba_check_l(ba, 3, 4 * BSIZE, 100);
178 ba_check_l(ba, 4, 5 * BSIZE, 100);
179 ba_check_l(ba, 5, 6 * BSIZE, 100);
180 ba_check_l(ba, 6, 7 * BSIZE, 100);
181 ba_check_none(ba, 7);
182
183 ba_free(ba, 4 * BSIZE, 100);
184 ba_check_l(ba, 0, 0, 100);
185 ba_check_l(ba, 1, BSIZE, 100);
186 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
187 ba_check_l(ba, 3, 5 * BSIZE, 100);
188 ba_check_l(ba, 4, 6 * BSIZE, 100);
189 ba_check_l(ba, 5, 7 * BSIZE, 100);
190 ba_check_none(ba, 6);
191
192 uint64_t b2;
193 ba_alloc(ba, 100, &b2);
194 invariant(b2 == 4 * BSIZE);
195 ba_check_l(ba, 0, 0, 100);
196 ba_check_l(ba, 1, BSIZE, 100);
197 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
198 ba_check_l(ba, 3, 4 * BSIZE, 100);
199 ba_check_l(ba, 4, 5 * BSIZE, 100);
200 ba_check_l(ba, 5, 6 * BSIZE, 100);
201 ba_check_l(ba, 6, 7 * BSIZE, 100);
202 ba_check_none(ba, 7);
203
204 ba_free(ba, BSIZE, 100);
205 ba_free(ba, 5 * BSIZE, 100);
206 ba_check_l(ba, 0, 0, 100);
207 ba_check_l(ba, 1, 2 * BSIZE, BSIZE + 100);
208 ba_check_l(ba, 2, 4 * BSIZE, 100);
209 ba_check_l(ba, 3, 6 * BSIZE, 100);
210 ba_check_l(ba, 4, 7 * BSIZE, 100);
211 ba_check_none(ba, 5);
212
213 // This alloc will allocate the first block after the reserve space in the
214 // case of first fit.
215 uint64_t b3;
216 ba_alloc(ba, 100, &b3);
217 invariant(b3 == BSIZE); // First fit.
218 // if (b3==5*BSIZE) then it is next fit.
219
220 // Now 5*BSIZE is free
221 uint64_t b5;
222 ba_alloc(ba, 100, &b5);
223 invariant(b5 == 5 * BSIZE);
224 ba_check_l(ba, 0, 0, 100);
225 ba_check_l(ba, 1, BSIZE, 100);
226 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
227 ba_check_l(ba, 3, 4 * BSIZE, 100);
228 ba_check_l(ba, 4, 5 * BSIZE, 100);
229 ba_check_l(ba, 5, 6 * BSIZE, 100);
230 ba_check_l(ba, 6, 7 * BSIZE, 100);
231 ba_check_none(ba, 7);
232
233 // Now all blocks are busy
234 uint64_t b6, b7, b8;
235 ba_alloc(ba, 100, &b6);
236 ba_alloc(ba, 100, &b7);
237 ba_alloc(ba, 100, &b8);
238 invariant(b6 == 8 * BSIZE);
239 invariant(b7 == 9 * BSIZE);
240 invariant(b8 == 10 * BSIZE);
241 ba_check_l(ba, 0, 0, 100);
242 ba_check_l(ba, 1, BSIZE, 100);
243 ba_check_l(ba, 2, 2 * BSIZE, BSIZE + 100);
244 ba_check_l(ba, 3, 4 * BSIZE, 100);
245 ba_check_l(ba, 4, 5 * BSIZE, 100);
246 ba_check_l(ba, 5, 6 * BSIZE, 100);
247 ba_check_l(ba, 6, 7 * BSIZE, 100);
248 ba_check_l(ba, 7, 8 * BSIZE, 100);
249 ba_check_l(ba, 8, 9 * BSIZE, 100);
250 ba_check_l(ba, 9, 10 * BSIZE, 100);
251 ba_check_none(ba, 10);
252
253 ba_free(ba, 9 * BSIZE, 100);
254 ba_free(ba, 7 * BSIZE, 100);
255 uint64_t b9;
256 ba_alloc(ba, 100, &b9);
257 invariant(b9 == 7 * BSIZE);
258
259 ba_free(ba, 5 * BSIZE, 100);
260 ba_free(ba, 2 * BSIZE, BSIZE + 100);
261 uint64_t b10, b11;
262 ba_alloc(ba, 100, &b10);
263 invariant(b10 == 2 * BSIZE);
264 ba_alloc(ba, 100, &b11);
265 invariant(b11 == 3 * BSIZE);
266 ba_alloc(ba, 100, &b11);
267 invariant(b11 == 5 * BSIZE);
268
269 ba->Destroy();
270 }
271
test_main(int argc,const char * argv[])272 int test_main(int argc __attribute__((__unused__)),
273 const char *argv[] __attribute__((__unused__))) {
274 test_ba0();
275 test_ba1(0);
276 test_ba1(10);
277 test_ba1(20);
278 test_ba2();
279 return 0;
280 }
281