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