~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/tests/free-space-tree-tests.c

Version: ~ [ linux-5.5-rc6 ] ~ [ linux-5.4.11 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.95 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.164 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.209 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.209 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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_err("could not find free space info");
 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_err("extent count is wrong");
 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_err("free space tree is invalid");
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_err("could not find free space info");
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_err("could not convert to extents");
137                         return ret;
138                 }
139         } else {
140                 ret = convert_free_space_to_bitmaps(trans, cache, path);
141                 if (ret) {
142                         test_err("could not convert to bitmaps");
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, cache, path,
174                                             cache->key.objectid,
175                                             cache->key.offset);
176         if (ret) {
177                 test_err("could not remove free space");
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, cache, path,
198                                             cache->key.objectid, alignment);
199         if (ret) {
200                 test_err("could not remove free space");
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, cache, path,
221                                             cache->key.objectid +
222                                             cache->key.offset - alignment,
223                                             alignment);
224         if (ret) {
225                 test_err("could not remove free space");
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, cache, path,
247                                             cache->key.objectid + alignment,
248                                             alignment);
249         if (ret) {
250                 test_err("could not remove free space");
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, cache, path,
270                                             cache->key.objectid,
271                                             cache->key.offset);
272         if (ret) {
273                 test_err("could not remove free space");
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_err("could not add free space");
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_err("could not add free space");
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, cache, path,
308                                             cache->key.objectid,
309                                             cache->key.offset);
310         if (ret) {
311                 test_err("could not remove free space");
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_err("could not add free space");
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_err("could not add free space");
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, cache, path,
347                                             cache->key.objectid,
348                                             cache->key.offset);
349         if (ret) {
350                 test_err("could not remove free space");
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_err("could not add free space");
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_err("could not add free space");
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_err("could not add free space");
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, cache, path,
395                                             cache->key.objectid,
396                                             cache->key.offset);
397         if (ret) {
398                 test_err("could not remove free space");
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_err("could not add free space");
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_err("could not add free space");
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_err("could not add free space");
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_err("couldn't allocate dummy fs info");
448                 ret = -ENOMEM;
449                 goto out;
450         }
451 
452         root = btrfs_alloc_dummy_root(fs_info);
453         if (IS_ERR(root)) {
454                 test_err("couldn't allocate dummy root");
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_err("couldn't allocate dummy buffer");
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_err("couldn't allocate dummy block group cache");
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_err("couldn't allocate path");
490                 ret = -ENOMEM;
491                 goto out;
492         }
493 
494         ret = add_block_group_free_space(&trans, cache);
495         if (ret) {
496                 test_err("could not add block group free space");
497                 goto out;
498         }
499 
500         if (bitmaps) {
501                 ret = convert_free_space_to_bitmaps(&trans, cache, path);
502                 if (ret) {
503                         test_err("could not convert block group to bitmaps");
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_err("could not remove block group free space");
515                 goto out;
516         }
517 
518         if (btrfs_header_nritems(root->node) != 0) {
519                 test_err("free space tree has leftover items");
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_err(
542         "%pf failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
543                          test_func, sectorsize, nodesize, alignment);
544                 test_ret = ret;
545         }
546 
547         ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
548         if (ret) {
549                 test_err(
550         "%pf failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
551                          test_func, sectorsize, nodesize, alignment);
552                 test_ret = ret;
553         }
554 
555         return test_ret;
556 }
557 
558 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
559 {
560         test_func_t tests[] = {
561                 test_empty_block_group,
562                 test_remove_all,
563                 test_remove_beginning,
564                 test_remove_end,
565                 test_remove_middle,
566                 test_merge_left,
567                 test_merge_right,
568                 test_merge_both,
569                 test_merge_none,
570         };
571         u32 bitmap_alignment;
572         int test_ret = 0;
573         int i;
574 
575         /*
576          * Align some operations to a page to flush out bugs in the extent
577          * buffer bitmap handling of highmem.
578          */
579         bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
580 
581         test_msg("running free space tree tests");
582         for (i = 0; i < ARRAY_SIZE(tests); i++) {
583                 int ret;
584 
585                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
586                                             sectorsize);
587                 if (ret)
588                         test_ret = ret;
589 
590                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
591                                             bitmap_alignment);
592                 if (ret)
593                         test_ret = ret;
594         }
595 
596         return test_ret;
597 }
598 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp