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 | /* | |
28 | * This test just does basic sanity checking, making sure we can add an exten | |
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 | * | |
399 | * This stealing approach is benefical, since we always prefer to allocate from | |
400 | * extent entries, both for clustered and non-clustered allocation requests. | |
401 | */ | |
402 | static int | |
403 | test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache) | |
404 | { | |
405 | int ret; | |
406 | u64 offset; | |
407 | u64 max_extent_size; | |
20e5506b | 408 | const struct btrfs_free_space_op test_free_space_ops = { |
28f0779a DS |
409 | .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds, |
410 | .use_bitmap = test_use_bitmap, | |
411 | }; | |
20e5506b | 412 | const struct btrfs_free_space_op *orig_free_space_ops; |
20005523 FM |
413 | |
414 | test_msg("Running space stealing from bitmap to extent\n"); | |
415 | ||
416 | /* | |
417 | * For this test, we want to ensure we end up with an extent entry | |
418 | * immediately adjacent to a bitmap entry, where the bitmap starts | |
419 | * at an offset where the extent entry ends. We keep adding and | |
420 | * removing free space to reach into this state, but to get there | |
421 | * we need to reach a point where marking new free space doesn't | |
422 | * result in adding new extent entries or merging the new space | |
423 | * with existing extent entries - the space ends up being marked | |
424 | * in an existing bitmap that covers the new free space range. | |
425 | * | |
426 | * To get there, we need to reach the threshold defined set at | |
427 | * cache->free_space_ctl->extents_thresh, which currently is | |
428 | * 256 extents on a x86_64 system at least, and a few other | |
429 | * conditions (check free_space_cache.c). Instead of making the | |
430 | * test much longer and complicated, use a "use_bitmap" operation | |
431 | * that forces use of bitmaps as soon as we have at least 1 | |
432 | * extent entry. | |
433 | */ | |
28f0779a DS |
434 | orig_free_space_ops = cache->free_space_ctl->op; |
435 | cache->free_space_ctl->op = &test_free_space_ops; | |
20005523 FM |
436 | |
437 | /* | |
438 | * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[ | |
439 | */ | |
ee22184b | 440 | ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0); |
20005523 FM |
441 | if (ret) { |
442 | test_msg("Couldn't add extent entry %d\n", ret); | |
443 | return ret; | |
444 | } | |
445 | ||
446 | /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */ | |
ee22184b BL |
447 | ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K, |
448 | SZ_128M - SZ_512K, 1); | |
20005523 FM |
449 | if (ret) { |
450 | test_msg("Couldn't add bitmap entry %d\n", ret); | |
451 | return ret; | |
452 | } | |
453 | ||
454 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
455 | if (ret) | |
456 | return ret; | |
457 | ||
458 | /* | |
459 | * Now make only the first 256Kb of the bitmap marked as free, so that | |
460 | * we end up with only the following ranges marked as free space: | |
461 | * | |
462 | * [128Mb - 256Kb, 128Mb - 128Kb[ | |
463 | * [128Mb + 512Kb, 128Mb + 768Kb[ | |
464 | */ | |
465 | ret = btrfs_remove_free_space(cache, | |
ee22184b BL |
466 | SZ_128M + 768 * SZ_1K, |
467 | SZ_128M - 768 * SZ_1K); | |
20005523 FM |
468 | if (ret) { |
469 | test_msg("Failed to free part of bitmap space %d\n", ret); | |
470 | return ret; | |
471 | } | |
472 | ||
473 | /* Confirm that only those 2 ranges are marked as free. */ | |
ee22184b | 474 | if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) { |
20005523 FM |
475 | test_msg("Free space range missing\n"); |
476 | return -ENOENT; | |
477 | } | |
ee22184b | 478 | if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) { |
20005523 FM |
479 | test_msg("Free space range missing\n"); |
480 | return -ENOENT; | |
481 | } | |
482 | ||
483 | /* | |
484 | * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked | |
485 | * as free anymore. | |
486 | */ | |
ee22184b BL |
487 | if (test_check_exists(cache, SZ_128M + 768 * SZ_1K, |
488 | SZ_128M - 768 * SZ_1K)) { | |
20005523 FM |
489 | test_msg("Bitmap region not removed from space cache\n"); |
490 | return -EINVAL; | |
491 | } | |
492 | ||
493 | /* | |
494 | * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is | |
495 | * covered by the bitmap, isn't marked as free. | |
496 | */ | |
ee22184b | 497 | if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) { |
20005523 FM |
498 | test_msg("Invalid bitmap region marked as free\n"); |
499 | return -EINVAL; | |
500 | } | |
501 | ||
502 | /* | |
503 | * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered | |
504 | * by the bitmap too, isn't marked as free either. | |
505 | */ | |
ee22184b | 506 | if (test_check_exists(cache, SZ_128M, SZ_256K)) { |
20005523 FM |
507 | test_msg("Invalid bitmap region marked as free\n"); |
508 | return -EINVAL; | |
509 | } | |
510 | ||
511 | /* | |
512 | * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But, | |
513 | * lets make sure the free space cache marks it as free in the bitmap, | |
514 | * and doesn't insert a new extent entry to represent this region. | |
515 | */ | |
ee22184b | 516 | ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K); |
20005523 FM |
517 | if (ret) { |
518 | test_msg("Error adding free space: %d\n", ret); | |
519 | return ret; | |
520 | } | |
521 | /* Confirm the region is marked as free. */ | |
ee22184b | 522 | if (!test_check_exists(cache, SZ_128M, SZ_512K)) { |
20005523 FM |
523 | test_msg("Bitmap region not marked as free\n"); |
524 | return -ENOENT; | |
525 | } | |
526 | ||
527 | /* | |
528 | * Confirm that no new extent entries or bitmap entries were added to | |
529 | * the cache after adding that free space region. | |
530 | */ | |
531 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
532 | if (ret) | |
533 | return ret; | |
534 | ||
535 | /* | |
536 | * Now lets add a small free space region to the right of the previous | |
537 | * one, which is not contiguous with it and is part of the bitmap too. | |
538 | * The goal is to test that the bitmap entry space stealing doesn't | |
539 | * steal this space region. | |
540 | */ | |
ee22184b | 541 | ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, 4096); |
20005523 FM |
542 | if (ret) { |
543 | test_msg("Error adding free space: %d\n", ret); | |
544 | return ret; | |
545 | } | |
546 | ||
547 | /* | |
548 | * Confirm that no new extent entries or bitmap entries were added to | |
549 | * the cache after adding that free space region. | |
550 | */ | |
551 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
552 | if (ret) | |
553 | return ret; | |
554 | ||
555 | /* | |
556 | * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will | |
557 | * expand the range covered by the existing extent entry that represents | |
558 | * the free space [128Mb - 256Kb, 128Mb - 128Kb[. | |
559 | */ | |
ee22184b | 560 | ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K); |
20005523 FM |
561 | if (ret) { |
562 | test_msg("Error adding free space: %d\n", ret); | |
563 | return ret; | |
564 | } | |
565 | /* Confirm the region is marked as free. */ | |
ee22184b | 566 | if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) { |
20005523 FM |
567 | test_msg("Extent region not marked as free\n"); |
568 | return -ENOENT; | |
569 | } | |
570 | ||
571 | /* | |
572 | * Confirm that our extent entry didn't stole all free space from the | |
573 | * bitmap, because of the small 4Kb free space region. | |
574 | */ | |
575 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
576 | if (ret) | |
577 | return ret; | |
578 | ||
579 | /* | |
580 | * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free | |
581 | * space. Without stealing bitmap free space into extent entry space, | |
582 | * we would have all this free space represented by 2 entries in the | |
583 | * cache: | |
584 | * | |
585 | * extent entry covering range: [128Mb - 256Kb, 128Mb[ | |
586 | * bitmap entry covering range: [128Mb, 128Mb + 768Kb[ | |
587 | * | |
588 | * Attempting to allocate the whole free space (1Mb) would fail, because | |
589 | * we can't allocate from multiple entries. | |
590 | * With the bitmap free space stealing, we get a single extent entry | |
591 | * that represents the 1Mb free space, and therefore we're able to | |
592 | * allocate the whole free space at once. | |
593 | */ | |
ee22184b | 594 | if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) { |
20005523 FM |
595 | test_msg("Expected region not marked as free\n"); |
596 | return -ENOENT; | |
597 | } | |
598 | ||
ee22184b | 599 | if (cache->free_space_ctl->free_space != (SZ_1M + 4096)) { |
20005523 FM |
600 | test_msg("Cache free space is not 1Mb + 4Kb\n"); |
601 | return -EINVAL; | |
602 | } | |
603 | ||
604 | offset = btrfs_find_space_for_alloc(cache, | |
ee22184b | 605 | 0, SZ_1M, 0, |
20005523 | 606 | &max_extent_size); |
ee22184b | 607 | if (offset != (SZ_128M - SZ_256K)) { |
20005523 FM |
608 | test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", |
609 | offset); | |
610 | return -EINVAL; | |
611 | } | |
612 | ||
613 | /* All that remains is a 4Kb free space region in a bitmap. Confirm. */ | |
614 | ret = check_num_extents_and_bitmaps(cache, 1, 1); | |
615 | if (ret) | |
616 | return ret; | |
617 | ||
618 | if (cache->free_space_ctl->free_space != 4096) { | |
619 | test_msg("Cache free space is not 4Kb\n"); | |
620 | return -EINVAL; | |
621 | } | |
622 | ||
623 | offset = btrfs_find_space_for_alloc(cache, | |
624 | 0, 4096, 0, | |
625 | &max_extent_size); | |
ee22184b | 626 | if (offset != (SZ_128M + SZ_16M)) { |
20005523 FM |
627 | test_msg("Failed to allocate 4Kb from space cache, returned offset is: %llu\n", |
628 | offset); | |
629 | return -EINVAL; | |
630 | } | |
631 | ||
632 | ret = check_cache_empty(cache); | |
633 | if (ret) | |
634 | return ret; | |
635 | ||
636 | __btrfs_remove_free_space_cache(cache->free_space_ctl); | |
637 | ||
638 | /* | |
639 | * Now test a similar scenario, but where our extent entry is located | |
640 | * to the right of the bitmap entry, so that we can check that stealing | |
641 | * space from a bitmap to the front of an extent entry works. | |
642 | */ | |
643 | ||
644 | /* | |
645 | * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[ | |
646 | */ | |
ee22184b | 647 | ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0); |
20005523 FM |
648 | if (ret) { |
649 | test_msg("Couldn't add extent entry %d\n", ret); | |
650 | return ret; | |
651 | } | |
652 | ||
653 | /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */ | |
ee22184b | 654 | ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1); |
20005523 FM |
655 | if (ret) { |
656 | test_msg("Couldn't add bitmap entry %d\n", ret); | |
657 | return ret; | |
658 | } | |
659 | ||
660 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
661 | if (ret) | |
662 | return ret; | |
663 | ||
664 | /* | |
665 | * Now make only the last 256Kb of the bitmap marked as free, so that | |
666 | * we end up with only the following ranges marked as free space: | |
667 | * | |
668 | * [128Mb + 128b, 128Mb + 256Kb[ | |
669 | * [128Mb - 768Kb, 128Mb - 512Kb[ | |
670 | */ | |
ee22184b | 671 | ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K); |
20005523 FM |
672 | if (ret) { |
673 | test_msg("Failed to free part of bitmap space %d\n", ret); | |
674 | return ret; | |
675 | } | |
676 | ||
677 | /* Confirm that only those 2 ranges are marked as free. */ | |
ee22184b | 678 | if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) { |
20005523 FM |
679 | test_msg("Free space range missing\n"); |
680 | return -ENOENT; | |
681 | } | |
ee22184b | 682 | if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) { |
20005523 FM |
683 | test_msg("Free space range missing\n"); |
684 | return -ENOENT; | |
685 | } | |
686 | ||
687 | /* | |
688 | * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked | |
689 | * as free anymore. | |
690 | */ | |
ee22184b | 691 | if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) { |
20005523 FM |
692 | test_msg("Bitmap region not removed from space cache\n"); |
693 | return -EINVAL; | |
694 | } | |
695 | ||
696 | /* | |
697 | * Confirm that the region [128Mb - 512Kb, 128Mb[, which is | |
698 | * covered by the bitmap, isn't marked as free. | |
699 | */ | |
ee22184b | 700 | if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { |
20005523 FM |
701 | test_msg("Invalid bitmap region marked as free\n"); |
702 | return -EINVAL; | |
703 | } | |
704 | ||
705 | /* | |
706 | * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But, | |
707 | * lets make sure the free space cache marks it as free in the bitmap, | |
708 | * and doesn't insert a new extent entry to represent this region. | |
709 | */ | |
ee22184b | 710 | ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K); |
20005523 FM |
711 | if (ret) { |
712 | test_msg("Error adding free space: %d\n", ret); | |
713 | return ret; | |
714 | } | |
715 | /* Confirm the region is marked as free. */ | |
ee22184b | 716 | if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { |
20005523 FM |
717 | test_msg("Bitmap region not marked as free\n"); |
718 | return -ENOENT; | |
719 | } | |
720 | ||
721 | /* | |
722 | * Confirm that no new extent entries or bitmap entries were added to | |
723 | * the cache after adding that free space region. | |
724 | */ | |
725 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
726 | if (ret) | |
727 | return ret; | |
728 | ||
729 | /* | |
730 | * Now lets add a small free space region to the left of the previous | |
731 | * one, which is not contiguous with it and is part of the bitmap too. | |
732 | * The goal is to test that the bitmap entry space stealing doesn't | |
733 | * steal this space region. | |
734 | */ | |
ee22184b | 735 | ret = btrfs_add_free_space(cache, SZ_32M, 8192); |
20005523 FM |
736 | if (ret) { |
737 | test_msg("Error adding free space: %d\n", ret); | |
738 | return ret; | |
739 | } | |
740 | ||
741 | /* | |
742 | * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will | |
743 | * expand the range covered by the existing extent entry that represents | |
744 | * the free space [128Mb + 128Kb, 128Mb + 256Kb[. | |
745 | */ | |
ee22184b | 746 | ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K); |
20005523 FM |
747 | if (ret) { |
748 | test_msg("Error adding free space: %d\n", ret); | |
749 | return ret; | |
750 | } | |
751 | /* Confirm the region is marked as free. */ | |
ee22184b | 752 | if (!test_check_exists(cache, SZ_128M, SZ_128K)) { |
20005523 FM |
753 | test_msg("Extent region not marked as free\n"); |
754 | return -ENOENT; | |
755 | } | |
756 | ||
757 | /* | |
758 | * Confirm that our extent entry didn't stole all free space from the | |
759 | * bitmap, because of the small 8Kb free space region. | |
760 | */ | |
761 | ret = check_num_extents_and_bitmaps(cache, 2, 1); | |
762 | if (ret) | |
763 | return ret; | |
764 | ||
765 | /* | |
766 | * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free | |
767 | * space. Without stealing bitmap free space into extent entry space, | |
768 | * we would have all this free space represented by 2 entries in the | |
769 | * cache: | |
770 | * | |
771 | * extent entry covering range: [128Mb, 128Mb + 256Kb[ | |
772 | * bitmap entry covering range: [128Mb - 768Kb, 128Mb[ | |
773 | * | |
774 | * Attempting to allocate the whole free space (1Mb) would fail, because | |
775 | * we can't allocate from multiple entries. | |
776 | * With the bitmap free space stealing, we get a single extent entry | |
777 | * that represents the 1Mb free space, and therefore we're able to | |
778 | * allocate the whole free space at once. | |
779 | */ | |
ee22184b | 780 | if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) { |
20005523 FM |
781 | test_msg("Expected region not marked as free\n"); |
782 | return -ENOENT; | |
783 | } | |
784 | ||
ee22184b | 785 | if (cache->free_space_ctl->free_space != (SZ_1M + 8192)) { |
20005523 FM |
786 | test_msg("Cache free space is not 1Mb + 8Kb\n"); |
787 | return -EINVAL; | |
788 | } | |
789 | ||
ee22184b | 790 | offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0, |
20005523 | 791 | &max_extent_size); |
ee22184b | 792 | if (offset != (SZ_128M - 768 * SZ_1K)) { |
20005523 FM |
793 | test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", |
794 | offset); | |
795 | return -EINVAL; | |
796 | } | |
797 | ||
798 | /* All that remains is a 8Kb free space region in a bitmap. Confirm. */ | |
799 | ret = check_num_extents_and_bitmaps(cache, 1, 1); | |
800 | if (ret) | |
801 | return ret; | |
802 | ||
803 | if (cache->free_space_ctl->free_space != 8192) { | |
804 | test_msg("Cache free space is not 8Kb\n"); | |
805 | return -EINVAL; | |
806 | } | |
807 | ||
808 | offset = btrfs_find_space_for_alloc(cache, | |
809 | 0, 8192, 0, | |
810 | &max_extent_size); | |
ee22184b | 811 | if (offset != SZ_32M) { |
20005523 FM |
812 | test_msg("Failed to allocate 8Kb from space cache, returned offset is: %llu\n", |
813 | offset); | |
814 | return -EINVAL; | |
815 | } | |
816 | ||
817 | ret = check_cache_empty(cache); | |
818 | if (ret) | |
819 | return ret; | |
820 | ||
28f0779a | 821 | cache->free_space_ctl->op = orig_free_space_ops; |
20005523 FM |
822 | __btrfs_remove_free_space_cache(cache->free_space_ctl); |
823 | ||
824 | return 0; | |
825 | } | |
826 | ||
dc11dd5d JB |
827 | int btrfs_test_free_space_cache(void) |
828 | { | |
829 | struct btrfs_block_group_cache *cache; | |
d0bd4560 JB |
830 | struct btrfs_root *root = NULL; |
831 | int ret = -ENOMEM; | |
dc11dd5d JB |
832 | |
833 | test_msg("Running btrfs free space cache tests\n"); | |
834 | ||
7c55ee0c | 835 | cache = btrfs_alloc_dummy_block_group(1024 * 1024 * 1024); |
dc11dd5d JB |
836 | if (!cache) { |
837 | test_msg("Couldn't run the tests\n"); | |
838 | return 0; | |
839 | } | |
840 | ||
d0bd4560 | 841 | root = btrfs_alloc_dummy_root(); |
89b6c8d1 DC |
842 | if (IS_ERR(root)) { |
843 | ret = PTR_ERR(root); | |
d0bd4560 | 844 | goto out; |
89b6c8d1 | 845 | } |
d0bd4560 JB |
846 | |
847 | root->fs_info = btrfs_alloc_dummy_fs_info(); | |
848 | if (!root->fs_info) | |
849 | goto out; | |
850 | ||
851 | root->fs_info->extent_root = root; | |
852 | cache->fs_info = root->fs_info; | |
853 | ||
dc11dd5d JB |
854 | ret = test_extents(cache); |
855 | if (ret) | |
856 | goto out; | |
857 | ret = test_bitmaps(cache); | |
858 | if (ret) | |
859 | goto out; | |
860 | ret = test_bitmaps_and_extents(cache); | |
861 | if (ret) | |
862 | goto out; | |
20005523 FM |
863 | |
864 | ret = test_steal_space_from_bitmap_to_extent(cache); | |
dc11dd5d | 865 | out: |
7c55ee0c | 866 | btrfs_free_dummy_block_group(cache); |
d0bd4560 | 867 | btrfs_free_dummy_root(root); |
dc11dd5d JB |
868 | test_msg("Free space cache tests finished\n"); |
869 | return ret; | |
870 | } |