Commit | Line | Data |
---|---|---|
dc11dd5d JB |
1 | /* |
2 | * Copyright (C) 2013 Fusion IO. All rights reserved. | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or | |
5 | * modify it under the terms of the GNU General Public | |
6 | * License v2 as published by the Free Software Foundation. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
11 | * General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU General Public | |
14 | * License along with this program; if not, write to the | |
15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
16 | * Boston, MA 021110-1307, USA. | |
17 | */ | |
18 | ||
19 | #include <linux/slab.h> | |
20 | #include "btrfs-tests.h" | |
21 | #include "../ctree.h" | |
d0bd4560 | 22 | #include "../disk-io.h" |
dc11dd5d JB |
23 | #include "../free-space-cache.h" |
24 | ||
0ef6447a | 25 | #define BITS_PER_BITMAP (PAGE_SIZE * 8UL) |
dc11dd5d JB |
26 | |
27 | /* | |
01327610 | 28 | * This test just does basic sanity checking, making sure we can add an extent |
dc11dd5d JB |
29 | * entry and remove space from either end and the middle, and make sure we can |
30 | * remove space that covers adjacent extent entries. | |
31 | */ | |
32 | static int test_extents(struct btrfs_block_group_cache *cache) | |
33 | { | |
34 | int ret = 0; | |
35 | ||
36 | test_msg("Running extent only tests\n"); | |
37 | ||
38 | /* First just make sure we can remove an entire entry */ | |
ee22184b | 39 | ret = btrfs_add_free_space(cache, 0, SZ_4M); |
dc11dd5d JB |
40 | if (ret) { |
41 | test_msg("Error adding initial extents %d\n", ret); | |
42 | return ret; | |
43 | } | |
44 | ||
ee22184b | 45 | ret = btrfs_remove_free_space(cache, 0, SZ_4M); |
dc11dd5d JB |
46 | if (ret) { |
47 | test_msg("Error removing extent %d\n", ret); | |
48 | return ret; | |
49 | } | |
50 | ||
ee22184b | 51 | if (test_check_exists(cache, 0, SZ_4M)) { |
dc11dd5d JB |
52 | test_msg("Full remove left some lingering space\n"); |
53 | return -1; | |
54 | } | |
55 | ||
56 | /* Ok edge and middle cases now */ | |
ee22184b | 57 | ret = btrfs_add_free_space(cache, 0, SZ_4M); |
dc11dd5d JB |
58 | if (ret) { |
59 | test_msg("Error adding half extent %d\n", ret); | |
60 | return ret; | |
61 | } | |
62 | ||
ee22184b | 63 | ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M); |
dc11dd5d JB |
64 | if (ret) { |
65 | test_msg("Error removing tail end %d\n", ret); | |
66 | return ret; | |
67 | } | |
68 | ||
ee22184b | 69 | ret = btrfs_remove_free_space(cache, 0, SZ_1M); |
dc11dd5d JB |
70 | if (ret) { |
71 | test_msg("Error removing front end %d\n", ret); | |
72 | return ret; | |
73 | } | |
74 | ||
ee22184b | 75 | ret = btrfs_remove_free_space(cache, SZ_2M, 4096); |
dc11dd5d | 76 | if (ret) { |
77d84ff8 | 77 | test_msg("Error removing middle piece %d\n", ret); |
dc11dd5d JB |
78 | return ret; |
79 | } | |
80 | ||
ee22184b | 81 | if (test_check_exists(cache, 0, SZ_1M)) { |
dc11dd5d JB |
82 | test_msg("Still have space at the front\n"); |
83 | return -1; | |
84 | } | |
85 | ||
ee22184b | 86 | if (test_check_exists(cache, SZ_2M, 4096)) { |
dc11dd5d JB |
87 | test_msg("Still have space in the middle\n"); |
88 | return -1; | |
89 | } | |
90 | ||
ee22184b | 91 | if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) { |
dc11dd5d JB |
92 | test_msg("Still have space at the end\n"); |
93 | return -1; | |
94 | } | |
95 | ||
96 | /* Cleanup */ | |
97 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
98 | ||
99 | return 0; | |
100 | } | |
101 | ||
b9ef22de FX |
102 | static int test_bitmaps(struct btrfs_block_group_cache *cache, |
103 | u32 sectorsize) | |
dc11dd5d JB |
104 | { |
105 | u64 next_bitmap_offset; | |
106 | int ret; | |
107 | ||
108 | test_msg("Running bitmap only tests\n"); | |
109 | ||
ee22184b | 110 | ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); |
dc11dd5d JB |
111 | if (ret) { |
112 | test_msg("Couldn't create a bitmap entry %d\n", ret); | |
113 | return ret; | |
114 | } | |
115 | ||
ee22184b | 116 | ret = btrfs_remove_free_space(cache, 0, SZ_4M); |
dc11dd5d JB |
117 | if (ret) { |
118 | test_msg("Error removing bitmap full range %d\n", ret); | |
119 | return ret; | |
120 | } | |
121 | ||
ee22184b | 122 | if (test_check_exists(cache, 0, SZ_4M)) { |
dc11dd5d JB |
123 | test_msg("Left some space in bitmap\n"); |
124 | return -1; | |
125 | } | |
126 | ||
ee22184b | 127 | ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); |
dc11dd5d JB |
128 | if (ret) { |
129 | test_msg("Couldn't add to our bitmap entry %d\n", ret); | |
130 | return ret; | |
131 | } | |
132 | ||
ee22184b | 133 | ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M); |
dc11dd5d JB |
134 | if (ret) { |
135 | test_msg("Couldn't remove middle chunk %d\n", ret); | |
136 | return ret; | |
137 | } | |
138 | ||
139 | /* | |
140 | * The first bitmap we have starts at offset 0 so the next one is just | |
141 | * at the end of the first bitmap. | |
142 | */ | |
b9ef22de | 143 | next_bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize); |
dc11dd5d JB |
144 | |
145 | /* Test a bit straddling two bitmaps */ | |
ee22184b BL |
146 | ret = test_add_free_space_entry(cache, next_bitmap_offset - SZ_2M, |
147 | SZ_4M, 1); | |
dc11dd5d JB |
148 | if (ret) { |
149 | test_msg("Couldn't add space that straddles two bitmaps %d\n", | |
150 | ret); | |
151 | return ret; | |
152 | } | |
153 | ||
ee22184b | 154 | ret = btrfs_remove_free_space(cache, next_bitmap_offset - SZ_1M, SZ_2M); |
dc11dd5d JB |
155 | if (ret) { |
156 | test_msg("Couldn't remove overlapping space %d\n", ret); | |
157 | return ret; | |
158 | } | |
159 | ||
ee22184b | 160 | if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) { |
dc11dd5d JB |
161 | test_msg("Left some space when removing overlapping\n"); |
162 | return -1; | |
163 | } | |
164 | ||
165 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
166 | ||
167 | return 0; | |
168 | } | |
169 | ||
170 | /* This is the high grade jackassery */ | |
b9ef22de FX |
171 | static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache, |
172 | u32 sectorsize) | |
dc11dd5d | 173 | { |
b9ef22de | 174 | u64 bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize); |
dc11dd5d JB |
175 | int ret; |
176 | ||
177 | test_msg("Running bitmap and extent tests\n"); | |
178 | ||
179 | /* | |
180 | * First let's do something simple, an extent at the same offset as the | |
181 | * bitmap, but the free space completely in the extent and then | |
182 | * completely in the bitmap. | |
183 | */ | |
ee22184b | 184 | ret = test_add_free_space_entry(cache, SZ_4M, SZ_1M, 1); |
dc11dd5d JB |
185 | if (ret) { |
186 | test_msg("Couldn't create bitmap entry %d\n", ret); | |
187 | return ret; | |
188 | } | |
189 | ||
ee22184b | 190 | ret = test_add_free_space_entry(cache, 0, SZ_1M, 0); |
dc11dd5d JB |
191 | if (ret) { |
192 | test_msg("Couldn't add extent entry %d\n", ret); | |
193 | return ret; | |
194 | } | |
195 | ||
ee22184b | 196 | ret = btrfs_remove_free_space(cache, 0, SZ_1M); |
dc11dd5d JB |
197 | if (ret) { |
198 | test_msg("Couldn't remove extent entry %d\n", ret); | |
199 | return ret; | |
200 | } | |
201 | ||
ee22184b | 202 | if (test_check_exists(cache, 0, SZ_1M)) { |
dc11dd5d JB |
203 | test_msg("Left remnants after our remove\n"); |
204 | return -1; | |
205 | } | |
206 | ||
207 | /* Now to add back the extent entry and remove from the bitmap */ | |
ee22184b | 208 | ret = test_add_free_space_entry(cache, 0, SZ_1M, 0); |
dc11dd5d JB |
209 | if (ret) { |
210 | test_msg("Couldn't re-add extent entry %d\n", ret); | |
211 | return ret; | |
212 | } | |
213 | ||
ee22184b | 214 | ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M); |
dc11dd5d JB |
215 | if (ret) { |
216 | test_msg("Couldn't remove from bitmap %d\n", ret); | |
217 | return ret; | |
218 | } | |
219 | ||
ee22184b | 220 | if (test_check_exists(cache, SZ_4M, SZ_1M)) { |
dc11dd5d JB |
221 | test_msg("Left remnants in the bitmap\n"); |
222 | return -1; | |
223 | } | |
224 | ||
225 | /* | |
226 | * Ok so a little more evil, extent entry and bitmap at the same offset, | |
227 | * removing an overlapping chunk. | |
228 | */ | |
ee22184b | 229 | ret = test_add_free_space_entry(cache, SZ_1M, SZ_4M, 1); |
dc11dd5d JB |
230 | if (ret) { |
231 | test_msg("Couldn't add to a bitmap %d\n", ret); | |
232 | return ret; | |
233 | } | |
234 | ||
ee22184b | 235 | ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M); |
dc11dd5d JB |
236 | if (ret) { |
237 | test_msg("Couldn't remove overlapping space %d\n", ret); | |
238 | return ret; | |
239 | } | |
240 | ||
ee22184b | 241 | if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) { |
8faaaead | 242 | test_msg("Left over pieces after removing overlapping\n"); |
dc11dd5d JB |
243 | return -1; |
244 | } | |
245 | ||
246 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
247 | ||
248 | /* Now with the extent entry offset into the bitmap */ | |
ee22184b | 249 | ret = test_add_free_space_entry(cache, SZ_4M, SZ_4M, 1); |
dc11dd5d JB |
250 | if (ret) { |
251 | test_msg("Couldn't add space to the bitmap %d\n", ret); | |
252 | return ret; | |
253 | } | |
254 | ||
ee22184b | 255 | ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0); |
dc11dd5d JB |
256 | if (ret) { |
257 | test_msg("Couldn't add extent to the cache %d\n", ret); | |
258 | return ret; | |
259 | } | |
260 | ||
ee22184b | 261 | ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M); |
dc11dd5d JB |
262 | if (ret) { |
263 | test_msg("Problem removing overlapping space %d\n", ret); | |
264 | return ret; | |
265 | } | |
266 | ||
ee22184b | 267 | if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) { |
dc11dd5d JB |
268 | test_msg("Left something behind when removing space"); |
269 | return -1; | |
270 | } | |
271 | ||
272 | /* | |
273 | * This has blown up in the past, the extent entry starts before the | |
274 | * bitmap entry, but we're trying to remove an offset that falls | |
275 | * completely within the bitmap range and is in both the extent entry | |
276 | * and the bitmap entry, looks like this | |
277 | * | |
278 | * [ extent ] | |
279 | * [ bitmap ] | |
280 | * [ del ] | |
281 | */ | |
282 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
ee22184b | 283 | ret = test_add_free_space_entry(cache, bitmap_offset + SZ_4M, SZ_4M, 1); |
dc11dd5d JB |
284 | if (ret) { |
285 | test_msg("Couldn't add bitmap %d\n", ret); | |
286 | return ret; | |
287 | } | |
288 | ||
ee22184b BL |
289 | ret = test_add_free_space_entry(cache, bitmap_offset - SZ_1M, |
290 | 5 * SZ_1M, 0); | |
dc11dd5d JB |
291 | if (ret) { |
292 | test_msg("Couldn't add extent entry %d\n", ret); | |
293 | return ret; | |
294 | } | |
295 | ||
ee22184b | 296 | ret = btrfs_remove_free_space(cache, bitmap_offset + SZ_1M, 5 * SZ_1M); |
dc11dd5d JB |
297 | if (ret) { |
298 | test_msg("Failed to free our space %d\n", ret); | |
299 | return ret; | |
300 | } | |
301 | ||
ee22184b | 302 | if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) { |
dc11dd5d JB |
303 | test_msg("Left stuff over\n"); |
304 | return -1; | |
305 | } | |
306 | ||
307 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
308 | ||
309 | /* | |
310 | * This blew up before, we have part of the free space in a bitmap and | |
311 | * then the entirety of the rest of the space in an extent. This used | |
312 | * to return -EAGAIN back from btrfs_remove_extent, make sure this | |
313 | * doesn't happen. | |
314 | */ | |
ee22184b | 315 | ret = test_add_free_space_entry(cache, SZ_1M, SZ_2M, 1); |
dc11dd5d JB |
316 | if (ret) { |
317 | test_msg("Couldn't add bitmap entry %d\n", ret); | |
318 | return ret; | |
319 | } | |
320 | ||
ee22184b | 321 | ret = test_add_free_space_entry(cache, 3 * SZ_1M, SZ_1M, 0); |
dc11dd5d JB |
322 | if (ret) { |
323 | test_msg("Couldn't add extent entry %d\n", ret); | |
324 | return ret; | |
325 | } | |
326 | ||
ee22184b | 327 | ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M); |
dc11dd5d JB |
328 | if (ret) { |
329 | test_msg("Error removing bitmap and extent overlapping %d\n", ret); | |
330 | return ret; | |
331 | } | |
332 | ||
333 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
334 | return 0; | |
335 | } | |
336 | ||
20005523 FM |
337 | /* Used by test_steal_space_from_bitmap_to_extent(). */ |
338 | static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl, | |
339 | struct btrfs_free_space *info) | |
340 | { | |
341 | return ctl->free_extents > 0; | |
342 | } | |
343 | ||
344 | /* Used by test_steal_space_from_bitmap_to_extent(). */ | |
345 | static int | |
346 | check_num_extents_and_bitmaps(const struct btrfs_block_group_cache *cache, | |
347 | const int num_extents, | |
348 | const int num_bitmaps) | |
349 | { | |
350 | if (cache->free_space_ctl->free_extents != num_extents) { | |
351 | test_msg("Incorrect # of extent entries in the cache: %d, expected %d\n", | |
352 | cache->free_space_ctl->free_extents, num_extents); | |
353 | return -EINVAL; | |
354 | } | |
355 | if (cache->free_space_ctl->total_bitmaps != num_bitmaps) { | |
356 | test_msg("Incorrect # of extent entries in the cache: %d, expected %d\n", | |
357 | cache->free_space_ctl->total_bitmaps, num_bitmaps); | |
358 | return -EINVAL; | |
359 | } | |
360 | return 0; | |
361 | } | |
362 | ||
363 | /* Used by test_steal_space_from_bitmap_to_extent(). */ | |
364 | static int check_cache_empty(struct btrfs_block_group_cache *cache) | |
365 | { | |
366 | u64 offset; | |
367 | u64 max_extent_size; | |
368 | ||
369 | /* | |
370 | * Now lets confirm that there's absolutely no free space left to | |
371 | * allocate. | |
372 | */ | |
373 | if (cache->free_space_ctl->free_space != 0) { | |
374 | test_msg("Cache free space is not 0\n"); | |
375 | return -EINVAL; | |
376 | } | |
377 | ||
378 | /* And any allocation request, no matter how small, should fail now. */ | |
379 | offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0, | |
380 | &max_extent_size); | |
381 | if (offset != 0) { | |
382 | test_msg("Space allocation did not fail, returned offset: %llu", | |
383 | offset); | |
384 | return -EINVAL; | |
385 | } | |
386 | ||
387 | /* And no extent nor bitmap entries in the cache anymore. */ | |
388 | return check_num_extents_and_bitmaps(cache, 0, 0); | |
389 | } | |
390 | ||
391 | /* | |
392 | * Before we were able to steal free space from a bitmap entry to an extent | |
393 | * entry, we could end up with 2 entries representing a contiguous free space. | |
394 | * One would be an extent entry and the other a bitmap entry. Since in order | |
395 | * to allocate space to a caller we use only 1 entry, we couldn't return that | |
396 | * whole range to the caller if it was requested. This forced the caller to | |
397 | * either assume ENOSPC or perform several smaller space allocations, which | |
398 | * wasn't optimal as they could be spread all over the block group while under | |
399 | * concurrency (extra overhead and fragmentation). | |
400 | * | |
01327610 NS |
401 | * This stealing approach is beneficial, since we always prefer to allocate |
402 | * from extent entries, both for clustered and non-clustered allocation | |
403 | * requests. | |
20005523 FM |
404 | */ |
405 | static int | |
b9ef22de FX |
406 | test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache, |
407 | u32 sectorsize) | |
20005523 FM |
408 | { |
409 | int ret; | |
410 | u64 offset; | |
411 | u64 max_extent_size; | |
20e5506b | 412 | const struct btrfs_free_space_op test_free_space_ops = { |
28f0779a DS |
413 | .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds, |
414 | .use_bitmap = test_use_bitmap, | |
415 | }; | |
20e5506b | 416 | const struct btrfs_free_space_op *orig_free_space_ops; |
20005523 FM |
417 | |
418 | test_msg("Running space stealing from bitmap to extent\n"); | |
419 | ||
420 | /* | |
421 | * For this test, we want to ensure we end up with an extent entry | |
422 | * immediately adjacent to a bitmap entry, where the bitmap starts | |
423 | * at an offset where the extent entry ends. We keep adding and | |
424 | * removing free space to reach into this state, but to get there | |
425 | * we need to reach a point where marking new free space doesn't | |
426 | * result in adding new extent entries or merging the new space | |
427 | * with existing extent entries - the space ends up being marked | |
428 | * in an existing bitmap that covers the new free space range. | |
429 | * | |
430 | * To get there, we need to reach the threshold defined set at | |
431 | * cache->free_space_ctl->extents_thresh, which currently is | |
432 | * 256 extents on a x86_64 system at least, and a few other | |
433 | * conditions (check free_space_cache.c). Instead of making the | |
434 | * test much longer and complicated, use a "use_bitmap" operation | |
435 | * that forces use of bitmaps as soon as we have at least 1 | |
436 | * extent entry. | |
437 | */ | |
28f0779a DS |
438 | orig_free_space_ops = cache->free_space_ctl->op; |
439 | cache->free_space_ctl->op = &test_free_space_ops; | |
20005523 FM |
440 | |
441 | /* | |
442 | * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[ | |
443 | */ | |
ee22184b | 444 | ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0); |
20005523 FM |
445 | if (ret) { |
446 | test_msg("Couldn't add extent entry %d\n", ret); | |
447 | return ret; | |
448 | } | |
449 | ||
450 | /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */ | |
ee22184b BL |
451 | ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K, |
452 | SZ_128M - SZ_512K, 1); | |
20005523 FM |
453 | if (ret) { |
454 | test_msg("Couldn't add bitmap entry %d\n", ret); | |
455 | return ret; | |
456 | } | |
457 | ||
458 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
459 | if (ret) | |
460 | return ret; | |
461 | ||
462 | /* | |
463 | * Now make only the first 256Kb of the bitmap marked as free, so that | |
464 | * we end up with only the following ranges marked as free space: | |
465 | * | |
466 | * [128Mb - 256Kb, 128Mb - 128Kb[ | |
467 | * [128Mb + 512Kb, 128Mb + 768Kb[ | |
468 | */ | |
469 | ret = btrfs_remove_free_space(cache, | |
ee22184b BL |
470 | SZ_128M + 768 * SZ_1K, |
471 | SZ_128M - 768 * SZ_1K); | |
20005523 FM |
472 | if (ret) { |
473 | test_msg("Failed to free part of bitmap space %d\n", ret); | |
474 | return ret; | |
475 | } | |
476 | ||
477 | /* Confirm that only those 2 ranges are marked as free. */ | |
ee22184b | 478 | if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) { |
20005523 FM |
479 | test_msg("Free space range missing\n"); |
480 | return -ENOENT; | |
481 | } | |
ee22184b | 482 | if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) { |
20005523 FM |
483 | test_msg("Free space range missing\n"); |
484 | return -ENOENT; | |
485 | } | |
486 | ||
487 | /* | |
488 | * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked | |
489 | * as free anymore. | |
490 | */ | |
ee22184b BL |
491 | if (test_check_exists(cache, SZ_128M + 768 * SZ_1K, |
492 | SZ_128M - 768 * SZ_1K)) { | |
20005523 FM |
493 | test_msg("Bitmap region not removed from space cache\n"); |
494 | return -EINVAL; | |
495 | } | |
496 | ||
497 | /* | |
498 | * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is | |
499 | * covered by the bitmap, isn't marked as free. | |
500 | */ | |
ee22184b | 501 | if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) { |
20005523 FM |
502 | test_msg("Invalid bitmap region marked as free\n"); |
503 | return -EINVAL; | |
504 | } | |
505 | ||
506 | /* | |
507 | * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered | |
508 | * by the bitmap too, isn't marked as free either. | |
509 | */ | |
ee22184b | 510 | if (test_check_exists(cache, SZ_128M, SZ_256K)) { |
20005523 FM |
511 | test_msg("Invalid bitmap region marked as free\n"); |
512 | return -EINVAL; | |
513 | } | |
514 | ||
515 | /* | |
516 | * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But, | |
517 | * lets make sure the free space cache marks it as free in the bitmap, | |
518 | * and doesn't insert a new extent entry to represent this region. | |
519 | */ | |
ee22184b | 520 | ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K); |
20005523 FM |
521 | if (ret) { |
522 | test_msg("Error adding free space: %d\n", ret); | |
523 | return ret; | |
524 | } | |
525 | /* Confirm the region is marked as free. */ | |
ee22184b | 526 | if (!test_check_exists(cache, SZ_128M, SZ_512K)) { |
20005523 FM |
527 | test_msg("Bitmap region not marked as free\n"); |
528 | return -ENOENT; | |
529 | } | |
530 | ||
531 | /* | |
532 | * Confirm that no new extent entries or bitmap entries were added to | |
533 | * the cache after adding that free space region. | |
534 | */ | |
535 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
536 | if (ret) | |
537 | return ret; | |
538 | ||
539 | /* | |
540 | * Now lets add a small free space region to the right of the previous | |
541 | * one, which is not contiguous with it and is part of the bitmap too. | |
542 | * The goal is to test that the bitmap entry space stealing doesn't | |
543 | * steal this space region. | |
544 | */ | |
b9ef22de | 545 | ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize); |
20005523 FM |
546 | if (ret) { |
547 | test_msg("Error adding free space: %d\n", ret); | |
548 | return ret; | |
549 | } | |
550 | ||
551 | /* | |
552 | * Confirm that no new extent entries or bitmap entries were added to | |
553 | * the cache after adding that free space region. | |
554 | */ | |
555 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
556 | if (ret) | |
557 | return ret; | |
558 | ||
559 | /* | |
560 | * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will | |
561 | * expand the range covered by the existing extent entry that represents | |
562 | * the free space [128Mb - 256Kb, 128Mb - 128Kb[. | |
563 | */ | |
ee22184b | 564 | ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K); |
20005523 FM |
565 | if (ret) { |
566 | test_msg("Error adding free space: %d\n", ret); | |
567 | return ret; | |
568 | } | |
569 | /* Confirm the region is marked as free. */ | |
ee22184b | 570 | if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) { |
20005523 FM |
571 | test_msg("Extent region not marked as free\n"); |
572 | return -ENOENT; | |
573 | } | |
574 | ||
575 | /* | |
576 | * Confirm that our extent entry didn't stole all free space from the | |
577 | * bitmap, because of the small 4Kb free space region. | |
578 | */ | |
579 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
580 | if (ret) | |
581 | return ret; | |
582 | ||
583 | /* | |
584 | * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free | |
585 | * space. Without stealing bitmap free space into extent entry space, | |
586 | * we would have all this free space represented by 2 entries in the | |
587 | * cache: | |
588 | * | |
589 | * extent entry covering range: [128Mb - 256Kb, 128Mb[ | |
590 | * bitmap entry covering range: [128Mb, 128Mb + 768Kb[ | |
591 | * | |
592 | * Attempting to allocate the whole free space (1Mb) would fail, because | |
593 | * we can't allocate from multiple entries. | |
594 | * With the bitmap free space stealing, we get a single extent entry | |
595 | * that represents the 1Mb free space, and therefore we're able to | |
596 | * allocate the whole free space at once. | |
597 | */ | |
ee22184b | 598 | if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) { |
20005523 FM |
599 | test_msg("Expected region not marked as free\n"); |
600 | return -ENOENT; | |
601 | } | |
602 | ||
b9ef22de FX |
603 | if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) { |
604 | test_msg("Cache free space is not 1Mb + %u\n", sectorsize); | |
20005523 FM |
605 | return -EINVAL; |
606 | } | |
607 | ||
608 | offset = btrfs_find_space_for_alloc(cache, | |
ee22184b | 609 | 0, SZ_1M, 0, |
20005523 | 610 | &max_extent_size); |
ee22184b | 611 | if (offset != (SZ_128M - SZ_256K)) { |
20005523 FM |
612 | test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", |
613 | offset); | |
614 | return -EINVAL; | |
615 | } | |
616 | ||
b9ef22de FX |
617 | /* |
618 | * All that remains is a sectorsize free space region in a bitmap. | |
619 | * Confirm. | |
620 | */ | |
20005523 FM |
621 | ret = check_num_extents_and_bitmaps(cache, 1, 1); |
622 | if (ret) | |
623 | return ret; | |
624 | ||
b9ef22de FX |
625 | if (cache->free_space_ctl->free_space != sectorsize) { |
626 | test_msg("Cache free space is not %u\n", sectorsize); | |
20005523 FM |
627 | return -EINVAL; |
628 | } | |
629 | ||
630 | offset = btrfs_find_space_for_alloc(cache, | |
b9ef22de | 631 | 0, sectorsize, 0, |
20005523 | 632 | &max_extent_size); |
ee22184b | 633 | if (offset != (SZ_128M + SZ_16M)) { |
b9ef22de FX |
634 | test_msg("Failed to allocate %u, returned offset : %llu\n", |
635 | sectorsize, offset); | |
20005523 FM |
636 | return -EINVAL; |
637 | } | |
638 | ||
639 | ret = check_cache_empty(cache); | |
640 | if (ret) | |
641 | return ret; | |
642 | ||
643 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
644 | ||
645 | /* | |
646 | * Now test a similar scenario, but where our extent entry is located | |
647 | * to the right of the bitmap entry, so that we can check that stealing | |
648 | * space from a bitmap to the front of an extent entry works. | |
649 | */ | |
650 | ||
651 | /* | |
652 | * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[ | |
653 | */ | |
ee22184b | 654 | ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0); |
20005523 FM |
655 | if (ret) { |
656 | test_msg("Couldn't add extent entry %d\n", ret); | |
657 | return ret; | |
658 | } | |
659 | ||
660 | /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */ | |
ee22184b | 661 | ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1); |
20005523 FM |
662 | if (ret) { |
663 | test_msg("Couldn't add bitmap entry %d\n", ret); | |
664 | return ret; | |
665 | } | |
666 | ||
667 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
668 | if (ret) | |
669 | return ret; | |
670 | ||
671 | /* | |
672 | * Now make only the last 256Kb of the bitmap marked as free, so that | |
673 | * we end up with only the following ranges marked as free space: | |
674 | * | |
675 | * [128Mb + 128b, 128Mb + 256Kb[ | |
676 | * [128Mb - 768Kb, 128Mb - 512Kb[ | |
677 | */ | |
ee22184b | 678 | ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K); |
20005523 FM |
679 | if (ret) { |
680 | test_msg("Failed to free part of bitmap space %d\n", ret); | |
681 | return ret; | |
682 | } | |
683 | ||
684 | /* Confirm that only those 2 ranges are marked as free. */ | |
ee22184b | 685 | if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) { |
20005523 FM |
686 | test_msg("Free space range missing\n"); |
687 | return -ENOENT; | |
688 | } | |
ee22184b | 689 | if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) { |
20005523 FM |
690 | test_msg("Free space range missing\n"); |
691 | return -ENOENT; | |
692 | } | |
693 | ||
694 | /* | |
695 | * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked | |
696 | * as free anymore. | |
697 | */ | |
ee22184b | 698 | if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) { |
20005523 FM |
699 | test_msg("Bitmap region not removed from space cache\n"); |
700 | return -EINVAL; | |
701 | } | |
702 | ||
703 | /* | |
704 | * Confirm that the region [128Mb - 512Kb, 128Mb[, which is | |
705 | * covered by the bitmap, isn't marked as free. | |
706 | */ | |
ee22184b | 707 | if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { |
20005523 FM |
708 | test_msg("Invalid bitmap region marked as free\n"); |
709 | return -EINVAL; | |
710 | } | |
711 | ||
712 | /* | |
713 | * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But, | |
714 | * lets make sure the free space cache marks it as free in the bitmap, | |
715 | * and doesn't insert a new extent entry to represent this region. | |
716 | */ | |
ee22184b | 717 | ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K); |
20005523 FM |
718 | if (ret) { |
719 | test_msg("Error adding free space: %d\n", ret); | |
720 | return ret; | |
721 | } | |
722 | /* Confirm the region is marked as free. */ | |
ee22184b | 723 | if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { |
20005523 FM |
724 | test_msg("Bitmap region not marked as free\n"); |
725 | return -ENOENT; | |
726 | } | |
727 | ||
728 | /* | |
729 | * Confirm that no new extent entries or bitmap entries were added to | |
730 | * the cache after adding that free space region. | |
731 | */ | |
732 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
733 | if (ret) | |
734 | return ret; | |
735 | ||
736 | /* | |
737 | * Now lets add a small free space region to the left of the previous | |
738 | * one, which is not contiguous with it and is part of the bitmap too. | |
739 | * The goal is to test that the bitmap entry space stealing doesn't | |
740 | * steal this space region. | |
741 | */ | |
b9ef22de | 742 | ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize); |
20005523 FM |
743 | if (ret) { |
744 | test_msg("Error adding free space: %d\n", ret); | |
745 | return ret; | |
746 | } | |
747 | ||
748 | /* | |
749 | * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will | |
750 | * expand the range covered by the existing extent entry that represents | |
751 | * the free space [128Mb + 128Kb, 128Mb + 256Kb[. | |
752 | */ | |
ee22184b | 753 | ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K); |
20005523 FM |
754 | if (ret) { |
755 | test_msg("Error adding free space: %d\n", ret); | |
756 | return ret; | |
757 | } | |
758 | /* Confirm the region is marked as free. */ | |
ee22184b | 759 | if (!test_check_exists(cache, SZ_128M, SZ_128K)) { |
20005523 FM |
760 | test_msg("Extent region not marked as free\n"); |
761 | return -ENOENT; | |
762 | } | |
763 | ||
764 | /* | |
765 | * Confirm that our extent entry didn't stole all free space from the | |
b9ef22de | 766 | * bitmap, because of the small 2 * sectorsize free space region. |
20005523 FM |
767 | */ |
768 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
769 | if (ret) | |
770 | return ret; | |
771 | ||
772 | /* | |
773 | * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free | |
774 | * space. Without stealing bitmap free space into extent entry space, | |
775 | * we would have all this free space represented by 2 entries in the | |
776 | * cache: | |
777 | * | |
778 | * extent entry covering range: [128Mb, 128Mb + 256Kb[ | |
779 | * bitmap entry covering range: [128Mb - 768Kb, 128Mb[ | |
780 | * | |
781 | * Attempting to allocate the whole free space (1Mb) would fail, because | |
782 | * we can't allocate from multiple entries. | |
783 | * With the bitmap free space stealing, we get a single extent entry | |
784 | * that represents the 1Mb free space, and therefore we're able to | |
785 | * allocate the whole free space at once. | |
786 | */ | |
ee22184b | 787 | if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) { |
20005523 FM |
788 | test_msg("Expected region not marked as free\n"); |
789 | return -ENOENT; | |
790 | } | |
791 | ||
b9ef22de FX |
792 | if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) { |
793 | test_msg("Cache free space is not 1Mb + %u\n", 2 * sectorsize); | |
20005523 FM |
794 | return -EINVAL; |
795 | } | |
796 | ||
ee22184b | 797 | offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0, |
20005523 | 798 | &max_extent_size); |
ee22184b | 799 | if (offset != (SZ_128M - 768 * SZ_1K)) { |
20005523 FM |
800 | test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", |
801 | offset); | |
802 | return -EINVAL; | |
803 | } | |
804 | ||
b9ef22de FX |
805 | /* |
806 | * All that remains is 2 * sectorsize free space region | |
807 | * in a bitmap. Confirm. | |
808 | */ | |
20005523 FM |
809 | ret = check_num_extents_and_bitmaps(cache, 1, 1); |
810 | if (ret) | |
811 | return ret; | |
812 | ||
b9ef22de FX |
813 | if (cache->free_space_ctl->free_space != 2 * sectorsize) { |
814 | test_msg("Cache free space is not %u\n", 2 * sectorsize); | |
20005523 FM |
815 | return -EINVAL; |
816 | } | |
817 | ||
818 | offset = btrfs_find_space_for_alloc(cache, | |
b9ef22de | 819 | 0, 2 * sectorsize, 0, |
20005523 | 820 | &max_extent_size); |
ee22184b | 821 | if (offset != SZ_32M) { |
b9ef22de FX |
822 | test_msg("Failed to allocate %u, offset: %llu\n", |
823 | 2 * sectorsize, | |
20005523 FM |
824 | offset); |
825 | return -EINVAL; | |
826 | } | |
827 | ||
828 | ret = check_cache_empty(cache); | |
829 | if (ret) | |
830 | return ret; | |
831 | ||
28f0779a | 832 | cache->free_space_ctl->op = orig_free_space_ops; |
20005523 FM |
833 | __btrfs_remove_free_space_cache(cache->free_space_ctl); |
834 | ||
835 | return 0; | |
836 | } | |
837 | ||
b9ef22de | 838 | int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize) |
dc11dd5d JB |
839 | { |
840 | struct btrfs_block_group_cache *cache; | |
d0bd4560 JB |
841 | struct btrfs_root *root = NULL; |
842 | int ret = -ENOMEM; | |
dc11dd5d JB |
843 | |
844 | test_msg("Running btrfs free space cache tests\n"); | |
845 | ||
b9ef22de | 846 | cache = btrfs_alloc_dummy_block_group(1024 * 1024 * 1024, sectorsize); |
dc11dd5d JB |
847 | if (!cache) { |
848 | test_msg("Couldn't run the tests\n"); | |
849 | return 0; | |
850 | } | |
851 | ||
b9ef22de | 852 | root = btrfs_alloc_dummy_root(sectorsize, nodesize); |
89b6c8d1 DC |
853 | if (IS_ERR(root)) { |
854 | ret = PTR_ERR(root); | |
d0bd4560 | 855 | goto out; |
89b6c8d1 | 856 | } |
d0bd4560 JB |
857 | |
858 | root->fs_info = btrfs_alloc_dummy_fs_info(); | |
859 | if (!root->fs_info) | |
860 | goto out; | |
861 | ||
862 | root->fs_info->extent_root = root; | |
863 | cache->fs_info = root->fs_info; | |
864 | ||
dc11dd5d JB |
865 | ret = test_extents(cache); |
866 | if (ret) | |
867 | goto out; | |
b9ef22de | 868 | ret = test_bitmaps(cache, sectorsize); |
dc11dd5d JB |
869 | if (ret) |
870 | goto out; | |
b9ef22de | 871 | ret = test_bitmaps_and_extents(cache, sectorsize); |
dc11dd5d JB |
872 | if (ret) |
873 | goto out; | |
20005523 | 874 | |
b9ef22de | 875 | ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize); |
dc11dd5d | 876 | out: |
7c55ee0c | 877 | btrfs_free_dummy_block_group(cache); |
d0bd4560 | 878 | btrfs_free_dummy_root(root); |
dc11dd5d JB |
879 | test_msg("Free space cache tests finished\n"); |
880 | return ret; | |
881 | } |