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 
10 static void free_extent_map_tree(struct extent_map_tree *em_tree)
11 {
12 	struct extent_map *em;
13 	struct rb_node *node;
14 
15 	while (!RB_EMPTY_ROOT(&em_tree->map.rb_root)) {
16 		node = rb_first_cached(&em_tree->map);
17 		em = rb_entry(node, struct extent_map, rb_node);
18 		remove_extent_mapping(em_tree, em);
19 
20 #ifdef CONFIG_BTRFS_DEBUG
21 		if (refcount_read(&em->refs) != 1) {
22 			test_err(
23 "em leak: em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx) refs %d",
24 				 em->start, em->len, em->block_start,
25 				 em->block_len, refcount_read(&em->refs));
26 
27 			refcount_set(&em->refs, 1);
28 		}
29 #endif
30 		free_extent_map(em);
31 	}
32 }
33 
34 /*
35  * Test scenario:
36  *
37  * Suppose that no extent map has been loaded into memory yet, there is a file
38  * extent [0, 16K), followed by another file extent [16K, 20K), two dio reads
39  * are entering btrfs_get_extent() concurrently, t1 is reading [8K, 16K), t2 is
40  * reading [0, 8K)
41  *
42  *     t1                            t2
43  *  btrfs_get_extent()              btrfs_get_extent()
44  *    -> lookup_extent_mapping()      ->lookup_extent_mapping()
45  *    -> add_extent_mapping(0, 16K)
46  *    -> return em
47  *                                    ->add_extent_mapping(0, 16K)
48  *                                    -> #handle -EEXIST
49  */
50 static int test_case_1(struct btrfs_fs_info *fs_info,
51 		struct extent_map_tree *em_tree)
52 {
53 	struct extent_map *em;
54 	u64 start = 0;
55 	u64 len = SZ_8K;
56 	int ret;
57 
58 	em = alloc_extent_map();
59 	if (!em) {
60 		test_std_err(TEST_ALLOC_EXTENT_MAP);
61 		return -ENOMEM;
62 	}
63 
64 	/* Add [0, 16K) */
65 	em->start = 0;
66 	em->len = SZ_16K;
67 	em->block_start = 0;
68 	em->block_len = SZ_16K;
69 	ret = add_extent_mapping(em_tree, em, 0);
70 	if (ret < 0) {
71 		test_err("cannot add extent range [0, 16K)");
72 		goto out;
73 	}
74 	free_extent_map(em);
75 
76 	/* Add [16K, 20K) following [0, 16K)  */
77 	em = alloc_extent_map();
78 	if (!em) {
79 		test_std_err(TEST_ALLOC_EXTENT_MAP);
80 		ret = -ENOMEM;
81 		goto out;
82 	}
83 
84 	em->start = SZ_16K;
85 	em->len = SZ_4K;
86 	em->block_start = SZ_32K; /* avoid merging */
87 	em->block_len = SZ_4K;
88 	ret = add_extent_mapping(em_tree, em, 0);
89 	if (ret < 0) {
90 		test_err("cannot add extent range [16K, 20K)");
91 		goto out;
92 	}
93 	free_extent_map(em);
94 
95 	em = alloc_extent_map();
96 	if (!em) {
97 		test_std_err(TEST_ALLOC_EXTENT_MAP);
98 		ret = -ENOMEM;
99 		goto out;
100 	}
101 
102 	/* Add [0, 8K), should return [0, 16K) instead. */
103 	em->start = start;
104 	em->len = len;
105 	em->block_start = start;
106 	em->block_len = len;
107 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
108 	if (ret) {
109 		test_err("case1 [%llu %llu]: ret %d", start, start + len, ret);
110 		goto out;
111 	}
112 	if (em &&
113 	    (em->start != 0 || extent_map_end(em) != SZ_16K ||
114 	     em->block_start != 0 || em->block_len != SZ_16K)) {
115 		test_err(
116 "case1 [%llu %llu]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
117 			 start, start + len, ret, em->start, em->len,
118 			 em->block_start, em->block_len);
119 		ret = -EINVAL;
120 	}
121 	free_extent_map(em);
122 out:
123 	free_extent_map_tree(em_tree);
124 
125 	return ret;
126 }
127 
128 /*
129  * Test scenario:
130  *
131  * Reading the inline ending up with EEXIST, ie. read an inline
132  * extent and discard page cache and read it again.
133  */
134 static int test_case_2(struct btrfs_fs_info *fs_info,
135 		struct extent_map_tree *em_tree)
136 {
137 	struct extent_map *em;
138 	int ret;
139 
140 	em = alloc_extent_map();
141 	if (!em) {
142 		test_std_err(TEST_ALLOC_EXTENT_MAP);
143 		return -ENOMEM;
144 	}
145 
146 	/* Add [0, 1K) */
147 	em->start = 0;
148 	em->len = SZ_1K;
149 	em->block_start = EXTENT_MAP_INLINE;
150 	em->block_len = (u64)-1;
151 	ret = add_extent_mapping(em_tree, em, 0);
152 	if (ret < 0) {
153 		test_err("cannot add extent range [0, 1K)");
154 		goto out;
155 	}
156 	free_extent_map(em);
157 
158 	/* Add [4K, 8K) following [0, 1K)  */
159 	em = alloc_extent_map();
160 	if (!em) {
161 		test_std_err(TEST_ALLOC_EXTENT_MAP);
162 		ret = -ENOMEM;
163 		goto out;
164 	}
165 
166 	em->start = SZ_4K;
167 	em->len = SZ_4K;
168 	em->block_start = SZ_4K;
169 	em->block_len = SZ_4K;
170 	ret = add_extent_mapping(em_tree, em, 0);
171 	if (ret < 0) {
172 		test_err("cannot add extent range [4K, 8K)");
173 		goto out;
174 	}
175 	free_extent_map(em);
176 
177 	em = alloc_extent_map();
178 	if (!em) {
179 		test_std_err(TEST_ALLOC_EXTENT_MAP);
180 		ret = -ENOMEM;
181 		goto out;
182 	}
183 
184 	/* Add [0, 1K) */
185 	em->start = 0;
186 	em->len = SZ_1K;
187 	em->block_start = EXTENT_MAP_INLINE;
188 	em->block_len = (u64)-1;
189 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
190 	if (ret) {
191 		test_err("case2 [0 1K]: ret %d", ret);
192 		goto out;
193 	}
194 	if (em &&
195 	    (em->start != 0 || extent_map_end(em) != SZ_1K ||
196 	     em->block_start != EXTENT_MAP_INLINE || em->block_len != (u64)-1)) {
197 		test_err(
198 "case2 [0 1K]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
199 			 ret, em->start, em->len, em->block_start,
200 			 em->block_len);
201 		ret = -EINVAL;
202 	}
203 	free_extent_map(em);
204 out:
205 	free_extent_map_tree(em_tree);
206 
207 	return ret;
208 }
209 
210 static int __test_case_3(struct btrfs_fs_info *fs_info,
211 		struct extent_map_tree *em_tree, u64 start)
212 {
213 	struct extent_map *em;
214 	u64 len = SZ_4K;
215 	int ret;
216 
217 	em = alloc_extent_map();
218 	if (!em) {
219 		test_std_err(TEST_ALLOC_EXTENT_MAP);
220 		return -ENOMEM;
221 	}
222 
223 	/* Add [4K, 8K) */
224 	em->start = SZ_4K;
225 	em->len = SZ_4K;
226 	em->block_start = SZ_4K;
227 	em->block_len = SZ_4K;
228 	ret = add_extent_mapping(em_tree, em, 0);
229 	if (ret < 0) {
230 		test_err("cannot add extent range [4K, 8K)");
231 		goto out;
232 	}
233 	free_extent_map(em);
234 
235 	em = alloc_extent_map();
236 	if (!em) {
237 		test_std_err(TEST_ALLOC_EXTENT_MAP);
238 		ret = -ENOMEM;
239 		goto out;
240 	}
241 
242 	/* Add [0, 16K) */
243 	em->start = 0;
244 	em->len = SZ_16K;
245 	em->block_start = 0;
246 	em->block_len = SZ_16K;
247 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
248 	if (ret) {
249 		test_err("case3 [0x%llx 0x%llx): ret %d",
250 			 start, start + len, ret);
251 		goto out;
252 	}
253 	/*
254 	 * Since bytes within em are contiguous, em->block_start is identical to
255 	 * em->start.
256 	 */
257 	if (em &&
258 	    (start < em->start || start + len > extent_map_end(em) ||
259 	     em->start != em->block_start || em->len != em->block_len)) {
260 		test_err(
261 "case3 [0x%llx 0x%llx): ret %d em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
262 			 start, start + len, ret, em->start, em->len,
263 			 em->block_start, em->block_len);
264 		ret = -EINVAL;
265 	}
266 	free_extent_map(em);
267 out:
268 	free_extent_map_tree(em_tree);
269 
270 	return ret;
271 }
272 
273 /*
274  * Test scenario:
275  *
276  * Suppose that no extent map has been loaded into memory yet.
277  * There is a file extent [0, 16K), two jobs are running concurrently
278  * against it, t1 is buffered writing to [4K, 8K) and t2 is doing dio
279  * read from [0, 4K) or [8K, 12K) or [12K, 16K).
280  *
281  * t1 goes ahead of t2 and adds em [4K, 8K) into tree.
282  *
283  *         t1                       t2
284  *  cow_file_range()	     btrfs_get_extent()
285  *                            -> lookup_extent_mapping()
286  *   -> add_extent_mapping()
287  *                            -> add_extent_mapping()
288  */
289 static int test_case_3(struct btrfs_fs_info *fs_info,
290 		struct extent_map_tree *em_tree)
291 {
292 	int ret;
293 
294 	ret = __test_case_3(fs_info, em_tree, 0);
295 	if (ret)
296 		return ret;
297 	ret = __test_case_3(fs_info, em_tree, SZ_8K);
298 	if (ret)
299 		return ret;
300 	ret = __test_case_3(fs_info, em_tree, (12 * SZ_1K));
301 
302 	return ret;
303 }
304 
305 static int __test_case_4(struct btrfs_fs_info *fs_info,
306 		struct extent_map_tree *em_tree, u64 start)
307 {
308 	struct extent_map *em;
309 	u64 len = SZ_4K;
310 	int ret;
311 
312 	em = alloc_extent_map();
313 	if (!em) {
314 		test_std_err(TEST_ALLOC_EXTENT_MAP);
315 		return -ENOMEM;
316 	}
317 
318 	/* Add [0K, 8K) */
319 	em->start = 0;
320 	em->len = SZ_8K;
321 	em->block_start = 0;
322 	em->block_len = SZ_8K;
323 	ret = add_extent_mapping(em_tree, em, 0);
324 	if (ret < 0) {
325 		test_err("cannot add extent range [0, 8K)");
326 		goto out;
327 	}
328 	free_extent_map(em);
329 
330 	em = alloc_extent_map();
331 	if (!em) {
332 		test_std_err(TEST_ALLOC_EXTENT_MAP);
333 		ret = -ENOMEM;
334 		goto out;
335 	}
336 
337 	/* Add [8K, 32K) */
338 	em->start = SZ_8K;
339 	em->len = 24 * SZ_1K;
340 	em->block_start = SZ_16K; /* avoid merging */
341 	em->block_len = 24 * SZ_1K;
342 	ret = add_extent_mapping(em_tree, em, 0);
343 	if (ret < 0) {
344 		test_err("cannot add extent range [8K, 32K)");
345 		goto out;
346 	}
347 	free_extent_map(em);
348 
349 	em = alloc_extent_map();
350 	if (!em) {
351 		test_std_err(TEST_ALLOC_EXTENT_MAP);
352 		ret = -ENOMEM;
353 		goto out;
354 	}
355 	/* Add [0K, 32K) */
356 	em->start = 0;
357 	em->len = SZ_32K;
358 	em->block_start = 0;
359 	em->block_len = SZ_32K;
360 	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
361 	if (ret) {
362 		test_err("case4 [0x%llx 0x%llx): ret %d",
363 			 start, len, ret);
364 		goto out;
365 	}
366 	if (em && (start < em->start || start + len > extent_map_end(em))) {
367 		test_err(
368 "case4 [0x%llx 0x%llx): ret %d, added wrong em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
369 			 start, len, ret, em->start, em->len, em->block_start,
370 			 em->block_len);
371 		ret = -EINVAL;
372 	}
373 	free_extent_map(em);
374 out:
375 	free_extent_map_tree(em_tree);
376 
377 	return ret;
378 }
379 
380 /*
381  * Test scenario:
382  *
383  * Suppose that no extent map has been loaded into memory yet.
384  * There is a file extent [0, 32K), two jobs are running concurrently
385  * against it, t1 is doing dio write to [8K, 32K) and t2 is doing dio
386  * read from [0, 4K) or [4K, 8K).
387  *
388  * t1 goes ahead of t2 and splits em [0, 32K) to em [0K, 8K) and [8K 32K).
389  *
390  *         t1                                t2
391  *  btrfs_get_blocks_direct()	       btrfs_get_blocks_direct()
392  *   -> btrfs_get_extent()              -> btrfs_get_extent()
393  *       -> lookup_extent_mapping()
394  *       -> add_extent_mapping()            -> lookup_extent_mapping()
395  *          # load [0, 32K)
396  *   -> btrfs_new_extent_direct()
397  *       -> btrfs_drop_extent_cache()
398  *          # split [0, 32K)
399  *       -> add_extent_mapping()
400  *          # add [8K, 32K)
401  *                                          -> add_extent_mapping()
402  *                                             # handle -EEXIST when adding
403  *                                             # [0, 32K)
404  */
405 static int test_case_4(struct btrfs_fs_info *fs_info,
406 		struct extent_map_tree *em_tree)
407 {
408 	int ret;
409 
410 	ret = __test_case_4(fs_info, em_tree, 0);
411 	if (ret)
412 		return ret;
413 	ret = __test_case_4(fs_info, em_tree, SZ_4K);
414 
415 	return ret;
416 }
417 
418 int btrfs_test_extent_map(void)
419 {
420 	struct btrfs_fs_info *fs_info = NULL;
421 	struct extent_map_tree *em_tree;
422 	int ret = 0;
423 
424 	test_msg("running extent_map tests");
425 
426 	/*
427 	 * Note: the fs_info is not set up completely, we only need
428 	 * fs_info::fsid for the tracepoint.
429 	 */
430 	fs_info = btrfs_alloc_dummy_fs_info(PAGE_SIZE, PAGE_SIZE);
431 	if (!fs_info) {
432 		test_std_err(TEST_ALLOC_FS_INFO);
433 		return -ENOMEM;
434 	}
435 
436 	em_tree = kzalloc(sizeof(*em_tree), GFP_KERNEL);
437 	if (!em_tree) {
438 		ret = -ENOMEM;
439 		goto out;
440 	}
441 
442 	extent_map_tree_init(em_tree);
443 
444 	ret = test_case_1(fs_info, em_tree);
445 	if (ret)
446 		goto out;
447 	ret = test_case_2(fs_info, em_tree);
448 	if (ret)
449 		goto out;
450 	ret = test_case_3(fs_info, em_tree);
451 	if (ret)
452 		goto out;
453 	ret = test_case_4(fs_info, em_tree);
454 
455 out:
456 	kfree(em_tree);
457 	btrfs_free_dummy_fs_info(fs_info);
458 
459 	return ret;
460 }
461