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