1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2017 Oracle.  All rights reserved.
4  */
5 
6 #include <linux/types.h>
7 #include "btrfs-tests.h"
8 #include "../ctree.h"
9 #include "../volumes.h"
10 #include "../disk-io.h"
11 #include "../block-group.h"
12 
13 static void free_extent_map_tree(struct extent_map_tree *em_tree)
14 {
15 	struct extent_map *em;
16 	struct rb_node *node;
17 
18 	write_lock(&em_tree->lock);
19 	while (!RB_EMPTY_ROOT(&em_tree->map.rb_root)) {
20 		node = rb_first_cached(&em_tree->map);
21 		em = rb_entry(node, struct extent_map, rb_node);
22 		remove_extent_mapping(em_tree, em);
23 
24 #ifdef CONFIG_BTRFS_DEBUG
25 		if (refcount_read(&em->refs) != 1) {
26 			test_err(
27 "em leak: em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx) refs %d",
28 				 em->start, em->len, em->block_start,
29 				 em->block_len, refcount_read(&em->refs));
30 
31 			refcount_set(&em->refs, 1);
32 		}
33 #endif
34 		free_extent_map(em);
35 	}
36 	write_unlock(&em_tree->lock);
37 }
38 
39 /*
40  * Test scenario:
41  *
42  * Suppose that no extent map has been loaded into memory yet, there is a file
43  * extent [0, 16K), followed by another file extent [16K, 20K), two dio reads
44  * are entering btrfs_get_extent() concurrently, t1 is reading [8K, 16K), t2 is
45  * reading [0, 8K)
46  *
47  *     t1                            t2
48  *  btrfs_get_extent()              btrfs_get_extent()
49  *    -> lookup_extent_mapping()      ->lookup_extent_mapping()
50  *    -> add_extent_mapping(0, 16K)
51  *    -> return em
52  *                                    ->add_extent_mapping(0, 16K)
53  *                                    -> #handle -EEXIST
54  */
55 static int test_case_1(struct btrfs_fs_info *fs_info,
56 		struct extent_map_tree *em_tree)
57 {
58 	struct extent_map *em;
59 	u64 start = 0;
60 	u64 len = SZ_8K;
61 	int ret;
62 
63 	em = alloc_extent_map();
64 	if (!em) {
65 		test_std_err(TEST_ALLOC_EXTENT_MAP);
66 		return -ENOMEM;
67 	}
68 
69 	/* Add [0, 16K) */
70 	em->start = 0;
71 	em->len = SZ_16K;
72 	em->block_start = 0;
73 	em->block_len = SZ_16K;
74 	write_lock(&em_tree->lock);
75 	ret = add_extent_mapping(em_tree, em, 0);
76 	write_unlock(&em_tree->lock);
77 	if (ret < 0) {
78 		test_err("cannot add extent range [0, 16K)");
79 		goto out;
80 	}
81 	free_extent_map(em);
82 
83 	/* Add [16K, 20K) following [0, 16K)  */
84 	em = alloc_extent_map();
85 	if (!em) {
86 		test_std_err(TEST_ALLOC_EXTENT_MAP);
87 		ret = -ENOMEM;
88 		goto out;
89 	}
90 
91 	em->start = SZ_16K;
92 	em->len = SZ_4K;
93 	em->block_start = SZ_32K; /* avoid merging */
94 	em->block_len = SZ_4K;
95 	write_lock(&em_tree->lock);
96 	ret = add_extent_mapping(em_tree, em, 0);
97 	write_unlock(&em_tree->lock);
98 	if (ret < 0) {
99 		test_err("cannot add extent range [16K, 20K)");
100 		goto out;
101 	}
102 	free_extent_map(em);
103 
104 	em = alloc_extent_map();
105 	if (!em) {
106 		test_std_err(TEST_ALLOC_EXTENT_MAP);
107 		ret = -ENOMEM;
108 		goto out;
109 	}
110 
111 	/* Add [0, 8K), should return [0, 16K) instead. */
112 	em->start = start;
113 	em->len = len;
114 	em->block_start = start;
115 	em->block_len = len;
116 	write_lock(&em_tree->lock);
117 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
118 	write_unlock(&em_tree->lock);
119 	if (ret) {
120 		test_err("case1 [%llu %llu]: ret %d", start, start + len, ret);
121 		goto out;
122 	}
123 	if (em &&
124 	    (em->start != 0 || extent_map_end(em) != SZ_16K ||
125 	     em->block_start != 0 || em->block_len != SZ_16K)) {
126 		test_err(
127 "case1 [%llu %llu]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
128 			 start, start + len, ret, em->start, em->len,
129 			 em->block_start, em->block_len);
130 		ret = -EINVAL;
131 	}
132 	free_extent_map(em);
133 out:
134 	free_extent_map_tree(em_tree);
135 
136 	return ret;
137 }
138 
139 /*
140  * Test scenario:
141  *
142  * Reading the inline ending up with EEXIST, ie. read an inline
143  * extent and discard page cache and read it again.
144  */
145 static int test_case_2(struct btrfs_fs_info *fs_info,
146 		struct extent_map_tree *em_tree)
147 {
148 	struct extent_map *em;
149 	int ret;
150 
151 	em = alloc_extent_map();
152 	if (!em) {
153 		test_std_err(TEST_ALLOC_EXTENT_MAP);
154 		return -ENOMEM;
155 	}
156 
157 	/* Add [0, 1K) */
158 	em->start = 0;
159 	em->len = SZ_1K;
160 	em->block_start = EXTENT_MAP_INLINE;
161 	em->block_len = (u64)-1;
162 	write_lock(&em_tree->lock);
163 	ret = add_extent_mapping(em_tree, em, 0);
164 	write_unlock(&em_tree->lock);
165 	if (ret < 0) {
166 		test_err("cannot add extent range [0, 1K)");
167 		goto out;
168 	}
169 	free_extent_map(em);
170 
171 	/* Add [4K, 8K) following [0, 1K)  */
172 	em = alloc_extent_map();
173 	if (!em) {
174 		test_std_err(TEST_ALLOC_EXTENT_MAP);
175 		ret = -ENOMEM;
176 		goto out;
177 	}
178 
179 	em->start = SZ_4K;
180 	em->len = SZ_4K;
181 	em->block_start = SZ_4K;
182 	em->block_len = SZ_4K;
183 	write_lock(&em_tree->lock);
184 	ret = add_extent_mapping(em_tree, em, 0);
185 	write_unlock(&em_tree->lock);
186 	if (ret < 0) {
187 		test_err("cannot add extent range [4K, 8K)");
188 		goto out;
189 	}
190 	free_extent_map(em);
191 
192 	em = alloc_extent_map();
193 	if (!em) {
194 		test_std_err(TEST_ALLOC_EXTENT_MAP);
195 		ret = -ENOMEM;
196 		goto out;
197 	}
198 
199 	/* Add [0, 1K) */
200 	em->start = 0;
201 	em->len = SZ_1K;
202 	em->block_start = EXTENT_MAP_INLINE;
203 	em->block_len = (u64)-1;
204 	write_lock(&em_tree->lock);
205 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
206 	write_unlock(&em_tree->lock);
207 	if (ret) {
208 		test_err("case2 [0 1K]: ret %d", ret);
209 		goto out;
210 	}
211 	if (em &&
212 	    (em->start != 0 || extent_map_end(em) != SZ_1K ||
213 	     em->block_start != EXTENT_MAP_INLINE || em->block_len != (u64)-1)) {
214 		test_err(
215 "case2 [0 1K]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
216 			 ret, em->start, em->len, em->block_start,
217 			 em->block_len);
218 		ret = -EINVAL;
219 	}
220 	free_extent_map(em);
221 out:
222 	free_extent_map_tree(em_tree);
223 
224 	return ret;
225 }
226 
227 static int __test_case_3(struct btrfs_fs_info *fs_info,
228 		struct extent_map_tree *em_tree, u64 start)
229 {
230 	struct extent_map *em;
231 	u64 len = SZ_4K;
232 	int ret;
233 
234 	em = alloc_extent_map();
235 	if (!em) {
236 		test_std_err(TEST_ALLOC_EXTENT_MAP);
237 		return -ENOMEM;
238 	}
239 
240 	/* Add [4K, 8K) */
241 	em->start = SZ_4K;
242 	em->len = SZ_4K;
243 	em->block_start = SZ_4K;
244 	em->block_len = SZ_4K;
245 	write_lock(&em_tree->lock);
246 	ret = add_extent_mapping(em_tree, em, 0);
247 	write_unlock(&em_tree->lock);
248 	if (ret < 0) {
249 		test_err("cannot add extent range [4K, 8K)");
250 		goto out;
251 	}
252 	free_extent_map(em);
253 
254 	em = alloc_extent_map();
255 	if (!em) {
256 		test_std_err(TEST_ALLOC_EXTENT_MAP);
257 		ret = -ENOMEM;
258 		goto out;
259 	}
260 
261 	/* Add [0, 16K) */
262 	em->start = 0;
263 	em->len = SZ_16K;
264 	em->block_start = 0;
265 	em->block_len = SZ_16K;
266 	write_lock(&em_tree->lock);
267 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
268 	write_unlock(&em_tree->lock);
269 	if (ret) {
270 		test_err("case3 [0x%llx 0x%llx): ret %d",
271 			 start, start + len, ret);
272 		goto out;
273 	}
274 	/*
275 	 * Since bytes within em are contiguous, em->block_start is identical to
276 	 * em->start.
277 	 */
278 	if (em &&
279 	    (start < em->start || start + len > extent_map_end(em) ||
280 	     em->start != em->block_start || em->len != em->block_len)) {
281 		test_err(
282 "case3 [0x%llx 0x%llx): ret %d em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
283 			 start, start + len, ret, em->start, em->len,
284 			 em->block_start, em->block_len);
285 		ret = -EINVAL;
286 	}
287 	free_extent_map(em);
288 out:
289 	free_extent_map_tree(em_tree);
290 
291 	return ret;
292 }
293 
294 /*
295  * Test scenario:
296  *
297  * Suppose that no extent map has been loaded into memory yet.
298  * There is a file extent [0, 16K), two jobs are running concurrently
299  * against it, t1 is buffered writing to [4K, 8K) and t2 is doing dio
300  * read from [0, 4K) or [8K, 12K) or [12K, 16K).
301  *
302  * t1 goes ahead of t2 and adds em [4K, 8K) into tree.
303  *
304  *         t1                       t2
305  *  cow_file_range()	     btrfs_get_extent()
306  *                            -> lookup_extent_mapping()
307  *   -> add_extent_mapping()
308  *                            -> add_extent_mapping()
309  */
310 static int test_case_3(struct btrfs_fs_info *fs_info,
311 		struct extent_map_tree *em_tree)
312 {
313 	int ret;
314 
315 	ret = __test_case_3(fs_info, em_tree, 0);
316 	if (ret)
317 		return ret;
318 	ret = __test_case_3(fs_info, em_tree, SZ_8K);
319 	if (ret)
320 		return ret;
321 	ret = __test_case_3(fs_info, em_tree, (12 * SZ_1K));
322 
323 	return ret;
324 }
325 
326 static int __test_case_4(struct btrfs_fs_info *fs_info,
327 		struct extent_map_tree *em_tree, u64 start)
328 {
329 	struct extent_map *em;
330 	u64 len = SZ_4K;
331 	int ret;
332 
333 	em = alloc_extent_map();
334 	if (!em) {
335 		test_std_err(TEST_ALLOC_EXTENT_MAP);
336 		return -ENOMEM;
337 	}
338 
339 	/* Add [0K, 8K) */
340 	em->start = 0;
341 	em->len = SZ_8K;
342 	em->block_start = 0;
343 	em->block_len = SZ_8K;
344 	write_lock(&em_tree->lock);
345 	ret = add_extent_mapping(em_tree, em, 0);
346 	write_unlock(&em_tree->lock);
347 	if (ret < 0) {
348 		test_err("cannot add extent range [0, 8K)");
349 		goto out;
350 	}
351 	free_extent_map(em);
352 
353 	em = alloc_extent_map();
354 	if (!em) {
355 		test_std_err(TEST_ALLOC_EXTENT_MAP);
356 		ret = -ENOMEM;
357 		goto out;
358 	}
359 
360 	/* Add [8K, 32K) */
361 	em->start = SZ_8K;
362 	em->len = 24 * SZ_1K;
363 	em->block_start = SZ_16K; /* avoid merging */
364 	em->block_len = 24 * SZ_1K;
365 	write_lock(&em_tree->lock);
366 	ret = add_extent_mapping(em_tree, em, 0);
367 	write_unlock(&em_tree->lock);
368 	if (ret < 0) {
369 		test_err("cannot add extent range [8K, 32K)");
370 		goto out;
371 	}
372 	free_extent_map(em);
373 
374 	em = alloc_extent_map();
375 	if (!em) {
376 		test_std_err(TEST_ALLOC_EXTENT_MAP);
377 		ret = -ENOMEM;
378 		goto out;
379 	}
380 	/* Add [0K, 32K) */
381 	em->start = 0;
382 	em->len = SZ_32K;
383 	em->block_start = 0;
384 	em->block_len = SZ_32K;
385 	write_lock(&em_tree->lock);
386 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
387 	write_unlock(&em_tree->lock);
388 	if (ret) {
389 		test_err("case4 [0x%llx 0x%llx): ret %d",
390 			 start, len, ret);
391 		goto out;
392 	}
393 	if (em && (start < em->start || start + len > extent_map_end(em))) {
394 		test_err(
395 "case4 [0x%llx 0x%llx): ret %d, added wrong em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
396 			 start, len, ret, em->start, em->len, em->block_start,
397 			 em->block_len);
398 		ret = -EINVAL;
399 	}
400 	free_extent_map(em);
401 out:
402 	free_extent_map_tree(em_tree);
403 
404 	return ret;
405 }
406 
407 /*
408  * Test scenario:
409  *
410  * Suppose that no extent map has been loaded into memory yet.
411  * There is a file extent [0, 32K), two jobs are running concurrently
412  * against it, t1 is doing dio write to [8K, 32K) and t2 is doing dio
413  * read from [0, 4K) or [4K, 8K).
414  *
415  * t1 goes ahead of t2 and splits em [0, 32K) to em [0K, 8K) and [8K 32K).
416  *
417  *         t1                                t2
418  *  btrfs_get_blocks_direct()	       btrfs_get_blocks_direct()
419  *   -> btrfs_get_extent()              -> btrfs_get_extent()
420  *       -> lookup_extent_mapping()
421  *       -> add_extent_mapping()            -> lookup_extent_mapping()
422  *          # load [0, 32K)
423  *   -> btrfs_new_extent_direct()
424  *       -> btrfs_drop_extent_cache()
425  *          # split [0, 32K)
426  *       -> add_extent_mapping()
427  *          # add [8K, 32K)
428  *                                          -> add_extent_mapping()
429  *                                             # handle -EEXIST when adding
430  *                                             # [0, 32K)
431  */
432 static int test_case_4(struct btrfs_fs_info *fs_info,
433 		struct extent_map_tree *em_tree)
434 {
435 	int ret;
436 
437 	ret = __test_case_4(fs_info, em_tree, 0);
438 	if (ret)
439 		return ret;
440 	ret = __test_case_4(fs_info, em_tree, SZ_4K);
441 
442 	return ret;
443 }
444 
445 struct rmap_test_vector {
446 	u64 raid_type;
447 	u64 physical_start;
448 	u64 data_stripe_size;
449 	u64 num_data_stripes;
450 	u64 num_stripes;
451 	/* Assume we won't have more than 5 physical stripes */
452 	u64 data_stripe_phys_start[5];
453 	bool expected_mapped_addr;
454 	/* Physical to logical addresses */
455 	u64 mapped_logical[5];
456 };
457 
458 static int test_rmap_block(struct btrfs_fs_info *fs_info,
459 			   struct rmap_test_vector *test)
460 {
461 	struct extent_map *em;
462 	struct map_lookup *map = NULL;
463 	u64 *logical = NULL;
464 	int i, out_ndaddrs, out_stripe_len;
465 	int ret;
466 
467 	em = alloc_extent_map();
468 	if (!em) {
469 		test_std_err(TEST_ALLOC_EXTENT_MAP);
470 		return -ENOMEM;
471 	}
472 
473 	map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
474 	if (!map) {
475 		kfree(em);
476 		test_std_err(TEST_ALLOC_EXTENT_MAP);
477 		return -ENOMEM;
478 	}
479 
480 	set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
481 	/* Start at 4GiB logical address */
482 	em->start = SZ_4G;
483 	em->len = test->data_stripe_size * test->num_data_stripes;
484 	em->block_len = em->len;
485 	em->orig_block_len = test->data_stripe_size;
486 	em->map_lookup = map;
487 
488 	map->num_stripes = test->num_stripes;
489 	map->type = test->raid_type;
490 
491 	for (i = 0; i < map->num_stripes; i++) {
492 		struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
493 
494 		if (IS_ERR(dev)) {
495 			test_err("cannot allocate device");
496 			ret = PTR_ERR(dev);
497 			goto out;
498 		}
499 		map->stripes[i].dev = dev;
500 		map->stripes[i].physical = test->data_stripe_phys_start[i];
501 	}
502 
503 	write_lock(&fs_info->mapping_tree.lock);
504 	ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
505 	write_unlock(&fs_info->mapping_tree.lock);
506 	if (ret) {
507 		test_err("error adding block group mapping to mapping tree");
508 		goto out_free;
509 	}
510 
511 	ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1),
512 			       &logical, &out_ndaddrs, &out_stripe_len);
513 	if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
514 		test_err("didn't rmap anything but expected %d",
515 			 test->expected_mapped_addr);
516 		goto out;
517 	}
518 
519 	if (out_stripe_len != BTRFS_STRIPE_LEN) {
520 		test_err("calculated stripe length doesn't match");
521 		goto out;
522 	}
523 
524 	if (out_ndaddrs != test->expected_mapped_addr) {
525 		for (i = 0; i < out_ndaddrs; i++)
526 			test_msg("mapped %llu", logical[i]);
527 		test_err("unexpected number of mapped addresses: %d", out_ndaddrs);
528 		goto out;
529 	}
530 
531 	for (i = 0; i < out_ndaddrs; i++) {
532 		if (logical[i] != test->mapped_logical[i]) {
533 			test_err("unexpected logical address mapped");
534 			goto out;
535 		}
536 	}
537 
538 	ret = 0;
539 out:
540 	write_lock(&fs_info->mapping_tree.lock);
541 	remove_extent_mapping(&fs_info->mapping_tree, em);
542 	write_unlock(&fs_info->mapping_tree.lock);
543 	/* For us */
544 	free_extent_map(em);
545 out_free:
546 	/* For the tree */
547 	free_extent_map(em);
548 	kfree(logical);
549 	return ret;
550 }
551 
552 int btrfs_test_extent_map(void)
553 {
554 	struct btrfs_fs_info *fs_info = NULL;
555 	struct extent_map_tree *em_tree;
556 	int ret = 0, i;
557 	struct rmap_test_vector rmap_tests[] = {
558 		{
559 			/*
560 			 * Test a chunk with 2 data stripes one of which
561 			 * intersects the physical address of the super block
562 			 * is correctly recognised.
563 			 */
564 			.raid_type = BTRFS_BLOCK_GROUP_RAID1,
565 			.physical_start = SZ_64M - SZ_4M,
566 			.data_stripe_size = SZ_256M,
567 			.num_data_stripes = 2,
568 			.num_stripes = 2,
569 			.data_stripe_phys_start =
570 				{SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},
571 			.expected_mapped_addr = true,
572 			.mapped_logical= {SZ_4G + SZ_4M}
573 		},
574 		{
575 			/*
576 			 * Test that out-of-range physical addresses are
577 			 * ignored
578 			 */
579 
580 			 /* SINGLE chunk type */
581 			.raid_type = 0,
582 			.physical_start = SZ_4G,
583 			.data_stripe_size = SZ_256M,
584 			.num_data_stripes = 1,
585 			.num_stripes = 1,
586 			.data_stripe_phys_start = {SZ_256M},
587 			.expected_mapped_addr = false,
588 			.mapped_logical = {0}
589 		}
590 	};
591 
592 	test_msg("running extent_map tests");
593 
594 	/*
595 	 * Note: the fs_info is not set up completely, we only need
596 	 * fs_info::fsid for the tracepoint.
597 	 */
598 	fs_info = btrfs_alloc_dummy_fs_info(PAGE_SIZE, PAGE_SIZE);
599 	if (!fs_info) {
600 		test_std_err(TEST_ALLOC_FS_INFO);
601 		return -ENOMEM;
602 	}
603 
604 	em_tree = kzalloc(sizeof(*em_tree), GFP_KERNEL);
605 	if (!em_tree) {
606 		ret = -ENOMEM;
607 		goto out;
608 	}
609 
610 	extent_map_tree_init(em_tree);
611 
612 	ret = test_case_1(fs_info, em_tree);
613 	if (ret)
614 		goto out;
615 	ret = test_case_2(fs_info, em_tree);
616 	if (ret)
617 		goto out;
618 	ret = test_case_3(fs_info, em_tree);
619 	if (ret)
620 		goto out;
621 	ret = test_case_4(fs_info, em_tree);
622 
623 	test_msg("running rmap tests");
624 	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
625 		ret = test_rmap_block(fs_info, &rmap_tests[i]);
626 		if (ret)
627 			goto out;
628 	}
629 
630 out:
631 	kfree(em_tree);
632 	btrfs_free_dummy_fs_info(fs_info);
633 
634 	return ret;
635 }
636