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