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