176ee997319c686638ed2c814749f90289cd9c91
[sfrench/cifs-2.6.git] / fs / btrfs / tests / free-space-tree-tests.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2015 Facebook.  All rights reserved.
4  */
5
6 #include <linux/types.h>
7 #include "btrfs-tests.h"
8 #include "../ctree.h"
9 #include "../disk-io.h"
10 #include "../free-space-tree.h"
11 #include "../transaction.h"
12
13 struct free_space_extent {
14         u64 start;
15         u64 length;
16 };
17
18 static int __check_free_space_extents(struct btrfs_trans_handle *trans,
19                                       struct btrfs_fs_info *fs_info,
20                                       struct btrfs_block_group_cache *cache,
21                                       struct btrfs_path *path,
22                                       const struct free_space_extent * const extents,
23                                       unsigned int num_extents)
24 {
25         struct btrfs_free_space_info *info;
26         struct btrfs_key key;
27         int prev_bit = 0, bit;
28         u64 extent_start = 0, offset, end;
29         u32 flags, extent_count;
30         unsigned int i;
31         int ret;
32
33         info = search_free_space_info(trans, fs_info, cache, path, 0);
34         if (IS_ERR(info)) {
35                 test_msg("Could not find free space info\n");
36                 ret = PTR_ERR(info);
37                 goto out;
38         }
39         flags = btrfs_free_space_flags(path->nodes[0], info);
40         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
41
42         if (extent_count != num_extents) {
43                 test_msg("Extent count is wrong\n");
44                 ret = -EINVAL;
45                 goto out;
46         }
47         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
48                 if (path->slots[0] != 0)
49                         goto invalid;
50                 end = cache->key.objectid + cache->key.offset;
51                 i = 0;
52                 while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
53                         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
54                         if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
55                                 goto invalid;
56                         offset = key.objectid;
57                         while (offset < key.objectid + key.offset) {
58                                 bit = free_space_test_bit(cache, path, offset);
59                                 if (prev_bit == 0 && bit == 1) {
60                                         extent_start = offset;
61                                 } else if (prev_bit == 1 && bit == 0) {
62                                         if (i >= num_extents)
63                                                 goto invalid;
64                                         if (i >= num_extents ||
65                                             extent_start != extents[i].start ||
66                                             offset - extent_start != extents[i].length)
67                                                 goto invalid;
68                                         i++;
69                                 }
70                                 prev_bit = bit;
71                                 offset += fs_info->sectorsize;
72                         }
73                 }
74                 if (prev_bit == 1) {
75                         if (i >= num_extents ||
76                             extent_start != extents[i].start ||
77                             end - extent_start != extents[i].length)
78                                 goto invalid;
79                         i++;
80                 }
81                 if (i != num_extents)
82                         goto invalid;
83         } else {
84                 if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
85                     path->slots[0] != 0)
86                         goto invalid;
87                 for (i = 0; i < num_extents; i++) {
88                         path->slots[0]++;
89                         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
90                         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
91                             key.objectid != extents[i].start ||
92                             key.offset != extents[i].length)
93                                 goto invalid;
94                 }
95         }
96
97         ret = 0;
98 out:
99         btrfs_release_path(path);
100         return ret;
101 invalid:
102         test_msg("Free space tree is invalid\n");
103         ret = -EINVAL;
104         goto out;
105 }
106
107 static int check_free_space_extents(struct btrfs_trans_handle *trans,
108                                     struct btrfs_fs_info *fs_info,
109                                     struct btrfs_block_group_cache *cache,
110                                     struct btrfs_path *path,
111                                     const struct free_space_extent * const extents,
112                                     unsigned int num_extents)
113 {
114         struct btrfs_free_space_info *info;
115         u32 flags;
116         int ret;
117
118         info = search_free_space_info(trans, fs_info, cache, path, 0);
119         if (IS_ERR(info)) {
120                 test_msg("Could not find free space info\n");
121                 btrfs_release_path(path);
122                 return PTR_ERR(info);
123         }
124         flags = btrfs_free_space_flags(path->nodes[0], info);
125         btrfs_release_path(path);
126
127         ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
128                                          num_extents);
129         if (ret)
130                 return ret;
131
132         /* Flip it to the other format and check that for good measure. */
133         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
134                 ret = convert_free_space_to_extents(trans, cache, path);
135                 if (ret) {
136                         test_msg("Could not convert to extents\n");
137                         return ret;
138                 }
139         } else {
140                 ret = convert_free_space_to_bitmaps(trans, cache, path);
141                 if (ret) {
142                         test_msg("Could not convert to bitmaps\n");
143                         return ret;
144                 }
145         }
146         return __check_free_space_extents(trans, fs_info, cache, path, extents,
147                                           num_extents);
148 }
149
150 static int test_empty_block_group(struct btrfs_trans_handle *trans,
151                                   struct btrfs_fs_info *fs_info,
152                                   struct btrfs_block_group_cache *cache,
153                                   struct btrfs_path *path,
154                                   u32 alignment)
155 {
156         const struct free_space_extent extents[] = {
157                 {cache->key.objectid, cache->key.offset},
158         };
159
160         return check_free_space_extents(trans, fs_info, cache, path,
161                                         extents, ARRAY_SIZE(extents));
162 }
163
164 static int test_remove_all(struct btrfs_trans_handle *trans,
165                            struct btrfs_fs_info *fs_info,
166                            struct btrfs_block_group_cache *cache,
167                            struct btrfs_path *path,
168                            u32 alignment)
169 {
170         const struct free_space_extent extents[] = {};
171         int ret;
172
173         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
174                                             cache->key.objectid,
175                                             cache->key.offset);
176         if (ret) {
177                 test_msg("Could not remove free space\n");
178                 return ret;
179         }
180
181         return check_free_space_extents(trans, fs_info, cache, path,
182                                         extents, ARRAY_SIZE(extents));
183 }
184
185 static int test_remove_beginning(struct btrfs_trans_handle *trans,
186                                  struct btrfs_fs_info *fs_info,
187                                  struct btrfs_block_group_cache *cache,
188                                  struct btrfs_path *path,
189                                  u32 alignment)
190 {
191         const struct free_space_extent extents[] = {
192                 {cache->key.objectid + alignment,
193                         cache->key.offset - alignment},
194         };
195         int ret;
196
197         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
198                                             cache->key.objectid, alignment);
199         if (ret) {
200                 test_msg("Could not remove free space\n");
201                 return ret;
202         }
203
204         return check_free_space_extents(trans, fs_info, cache, path,
205                                         extents, ARRAY_SIZE(extents));
206
207 }
208
209 static int test_remove_end(struct btrfs_trans_handle *trans,
210                            struct btrfs_fs_info *fs_info,
211                            struct btrfs_block_group_cache *cache,
212                            struct btrfs_path *path,
213                            u32 alignment)
214 {
215         const struct free_space_extent extents[] = {
216                 {cache->key.objectid, cache->key.offset - alignment},
217         };
218         int ret;
219
220         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
221                                             cache->key.objectid +
222                                             cache->key.offset - alignment,
223                                             alignment);
224         if (ret) {
225                 test_msg("Could not remove free space\n");
226                 return ret;
227         }
228
229         return check_free_space_extents(trans, fs_info, cache, path,
230                                         extents, ARRAY_SIZE(extents));
231 }
232
233 static int test_remove_middle(struct btrfs_trans_handle *trans,
234                               struct btrfs_fs_info *fs_info,
235                               struct btrfs_block_group_cache *cache,
236                               struct btrfs_path *path,
237                               u32 alignment)
238 {
239         const struct free_space_extent extents[] = {
240                 {cache->key.objectid, alignment},
241                 {cache->key.objectid + 2 * alignment,
242                         cache->key.offset - 2 * alignment},
243         };
244         int ret;
245
246         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
247                                             cache->key.objectid + alignment,
248                                             alignment);
249         if (ret) {
250                 test_msg("Could not remove free space\n");
251                 return ret;
252         }
253
254         return check_free_space_extents(trans, fs_info, cache, path,
255                                         extents, ARRAY_SIZE(extents));
256 }
257
258 static int test_merge_left(struct btrfs_trans_handle *trans,
259                            struct btrfs_fs_info *fs_info,
260                            struct btrfs_block_group_cache *cache,
261                            struct btrfs_path *path,
262                            u32 alignment)
263 {
264         const struct free_space_extent extents[] = {
265                 {cache->key.objectid, 2 * alignment},
266         };
267         int ret;
268
269         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
270                                             cache->key.objectid,
271                                             cache->key.offset);
272         if (ret) {
273                 test_msg("Could not remove free space\n");
274                 return ret;
275         }
276
277         ret = __add_to_free_space_tree(trans, cache, path, cache->key.objectid,
278                                        alignment);
279         if (ret) {
280                 test_msg("Could not add free space\n");
281                 return ret;
282         }
283
284         ret = __add_to_free_space_tree(trans, cache, path,
285                                        cache->key.objectid + alignment,
286                                        alignment);
287         if (ret) {
288                 test_msg("Could not add free space\n");
289                 return ret;
290         }
291
292         return check_free_space_extents(trans, fs_info, cache, path,
293                                         extents, ARRAY_SIZE(extents));
294 }
295
296 static int test_merge_right(struct btrfs_trans_handle *trans,
297                            struct btrfs_fs_info *fs_info,
298                            struct btrfs_block_group_cache *cache,
299                            struct btrfs_path *path,
300                            u32 alignment)
301 {
302         const struct free_space_extent extents[] = {
303                 {cache->key.objectid + alignment, 2 * alignment},
304         };
305         int ret;
306
307         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
308                                             cache->key.objectid,
309                                             cache->key.offset);
310         if (ret) {
311                 test_msg("Could not remove free space\n");
312                 return ret;
313         }
314
315         ret = __add_to_free_space_tree(trans, cache, path,
316                                        cache->key.objectid + 2 * alignment,
317                                        alignment);
318         if (ret) {
319                 test_msg("Could not add free space\n");
320                 return ret;
321         }
322
323         ret = __add_to_free_space_tree(trans, cache, path,
324                                        cache->key.objectid + alignment,
325                                        alignment);
326         if (ret) {
327                 test_msg("Could not add free space\n");
328                 return ret;
329         }
330
331         return check_free_space_extents(trans, fs_info, cache, path,
332                                         extents, ARRAY_SIZE(extents));
333 }
334
335 static int test_merge_both(struct btrfs_trans_handle *trans,
336                            struct btrfs_fs_info *fs_info,
337                            struct btrfs_block_group_cache *cache,
338                            struct btrfs_path *path,
339                            u32 alignment)
340 {
341         const struct free_space_extent extents[] = {
342                 {cache->key.objectid, 3 * alignment},
343         };
344         int ret;
345
346         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
347                                             cache->key.objectid,
348                                             cache->key.offset);
349         if (ret) {
350                 test_msg("Could not remove free space\n");
351                 return ret;
352         }
353
354         ret = __add_to_free_space_tree(trans, cache, path, cache->key.objectid,
355                                        alignment);
356         if (ret) {
357                 test_msg("Could not add free space\n");
358                 return ret;
359         }
360
361         ret = __add_to_free_space_tree(trans, cache, path,
362                                        cache->key.objectid + 2 * alignment,
363                                        alignment);
364         if (ret) {
365                 test_msg("Could not add free space\n");
366                 return ret;
367         }
368
369         ret = __add_to_free_space_tree(trans, cache, path,
370                                        cache->key.objectid + alignment,
371                                        alignment);
372         if (ret) {
373                 test_msg("Could not add free space\n");
374                 return ret;
375         }
376
377         return check_free_space_extents(trans, fs_info, cache, path,
378                                         extents, ARRAY_SIZE(extents));
379 }
380
381 static int test_merge_none(struct btrfs_trans_handle *trans,
382                            struct btrfs_fs_info *fs_info,
383                            struct btrfs_block_group_cache *cache,
384                            struct btrfs_path *path,
385                            u32 alignment)
386 {
387         const struct free_space_extent extents[] = {
388                 {cache->key.objectid, alignment},
389                 {cache->key.objectid + 2 * alignment, alignment},
390                 {cache->key.objectid + 4 * alignment, alignment},
391         };
392         int ret;
393
394         ret = __remove_from_free_space_tree(trans, fs_info, cache, path,
395                                             cache->key.objectid,
396                                             cache->key.offset);
397         if (ret) {
398                 test_msg("Could not remove free space\n");
399                 return ret;
400         }
401
402         ret = __add_to_free_space_tree(trans, cache, path, cache->key.objectid,
403                                        alignment);
404         if (ret) {
405                 test_msg("Could not add free space\n");
406                 return ret;
407         }
408
409         ret = __add_to_free_space_tree(trans, cache, path,
410                                        cache->key.objectid + 4 * alignment,
411                                        alignment);
412         if (ret) {
413                 test_msg("Could not add free space\n");
414                 return ret;
415         }
416
417         ret = __add_to_free_space_tree(trans, cache, path,
418                                        cache->key.objectid + 2 * alignment,
419                                        alignment);
420         if (ret) {
421                 test_msg("Could not add free space\n");
422                 return ret;
423         }
424
425         return check_free_space_extents(trans, fs_info, cache, path,
426                                         extents, ARRAY_SIZE(extents));
427 }
428
429 typedef int (*test_func_t)(struct btrfs_trans_handle *,
430                            struct btrfs_fs_info *,
431                            struct btrfs_block_group_cache *,
432                            struct btrfs_path *,
433                            u32 alignment);
434
435 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,
436                     u32 nodesize, u32 alignment)
437 {
438         struct btrfs_fs_info *fs_info;
439         struct btrfs_root *root = NULL;
440         struct btrfs_block_group_cache *cache = NULL;
441         struct btrfs_trans_handle trans;
442         struct btrfs_path *path = NULL;
443         int ret;
444
445         fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
446         if (!fs_info) {
447                 test_msg("Couldn't allocate dummy fs info\n");
448                 ret = -ENOMEM;
449                 goto out;
450         }
451
452         root = btrfs_alloc_dummy_root(fs_info);
453         if (IS_ERR(root)) {
454                 test_msg("Couldn't allocate dummy root\n");
455                 ret = PTR_ERR(root);
456                 goto out;
457         }
458
459         btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
460                                         BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
461         root->fs_info->free_space_root = root;
462         root->fs_info->tree_root = root;
463
464         root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
465         if (!root->node) {
466                 test_msg("Couldn't allocate dummy buffer\n");
467                 ret = -ENOMEM;
468                 goto out;
469         }
470         btrfs_set_header_level(root->node, 0);
471         btrfs_set_header_nritems(root->node, 0);
472         root->alloc_bytenr += 2 * nodesize;
473
474         cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
475         if (!cache) {
476                 test_msg("Couldn't allocate dummy block group cache\n");
477                 ret = -ENOMEM;
478                 goto out;
479         }
480         cache->bitmap_low_thresh = 0;
481         cache->bitmap_high_thresh = (u32)-1;
482         cache->needs_free_space = 1;
483         cache->fs_info = root->fs_info;
484
485         btrfs_init_dummy_trans(&trans, root->fs_info);
486
487         path = btrfs_alloc_path();
488         if (!path) {
489                 test_msg("Couldn't allocate path\n");
490                 ret = -ENOMEM;
491                 goto out;
492         }
493
494         ret = add_block_group_free_space(&trans, cache);
495         if (ret) {
496                 test_msg("Could not add block group free space\n");
497                 goto out;
498         }
499
500         if (bitmaps) {
501                 ret = convert_free_space_to_bitmaps(&trans, cache, path);
502                 if (ret) {
503                         test_msg("Could not convert block group to bitmaps\n");
504                         goto out;
505                 }
506         }
507
508         ret = test_func(&trans, root->fs_info, cache, path, alignment);
509         if (ret)
510                 goto out;
511
512         ret = remove_block_group_free_space(&trans, cache);
513         if (ret) {
514                 test_msg("Could not remove block group free space\n");
515                 goto out;
516         }
517
518         if (btrfs_header_nritems(root->node) != 0) {
519                 test_msg("Free space tree has leftover items\n");
520                 ret = -EINVAL;
521                 goto out;
522         }
523
524         ret = 0;
525 out:
526         btrfs_free_path(path);
527         btrfs_free_dummy_block_group(cache);
528         btrfs_free_dummy_root(root);
529         btrfs_free_dummy_fs_info(fs_info);
530         return ret;
531 }
532
533 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
534                                  u32 nodesize, u32 alignment)
535 {
536         int test_ret = 0;
537         int ret;
538
539         ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
540         if (ret) {
541                 test_msg("%pf failed with extents, sectorsize=%u, nodesize=%u, alignment=%u\n",
542                          test_func, sectorsize, nodesize, alignment);
543                 test_ret = ret;
544         }
545
546         ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
547         if (ret) {
548                 test_msg("%pf failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u\n",
549                          test_func, sectorsize, nodesize, alignment);
550                 test_ret = ret;
551         }
552
553         return test_ret;
554 }
555
556 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
557 {
558         test_func_t tests[] = {
559                 test_empty_block_group,
560                 test_remove_all,
561                 test_remove_beginning,
562                 test_remove_end,
563                 test_remove_middle,
564                 test_merge_left,
565                 test_merge_right,
566                 test_merge_both,
567                 test_merge_none,
568         };
569         u32 bitmap_alignment;
570         int test_ret = 0;
571         int i;
572
573         /*
574          * Align some operations to a page to flush out bugs in the extent
575          * buffer bitmap handling of highmem.
576          */
577         bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
578
579         test_msg("Running free space tree tests\n");
580         for (i = 0; i < ARRAY_SIZE(tests); i++) {
581                 int ret;
582
583                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
584                                             sectorsize);
585                 if (ret)
586                         test_ret = ret;
587
588                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
589                                             bitmap_alignment);
590                 if (ret)
591                         test_ret = ret;
592         }
593
594         return test_ret;
595 }