1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (c) 2014 Red Hat, Inc.
4  * All Rights Reserved.
5  */
6 #include "xfs.h"
7 #include "xfs_fs.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
12 #include "xfs_mount.h"
13 #include "xfs_trans.h"
14 #include "xfs_alloc.h"
15 #include "xfs_btree.h"
16 #include "xfs_btree_staging.h"
17 #include "xfs_rmap.h"
18 #include "xfs_rmap_btree.h"
19 #include "xfs_trace.h"
20 #include "xfs_error.h"
21 #include "xfs_extent_busy.h"
22 #include "xfs_ag.h"
23 #include "xfs_ag_resv.h"
24 
25 static struct kmem_cache	*xfs_rmapbt_cur_cache;
26 
27 /*
28  * Reverse map btree.
29  *
30  * This is a per-ag tree used to track the owner(s) of a given extent. With
31  * reflink it is possible for there to be multiple owners, which is a departure
32  * from classic XFS. Owner records for data extents are inserted when the
33  * extent is mapped and removed when an extent is unmapped.  Owner records for
34  * all other block types (i.e. metadata) are inserted when an extent is
35  * allocated and removed when an extent is freed. There can only be one owner
36  * of a metadata extent, usually an inode or some other metadata structure like
37  * an AG btree.
38  *
39  * The rmap btree is part of the free space management, so blocks for the tree
40  * are sourced from the agfl. Hence we need transaction reservation support for
41  * this tree so that the freelist is always large enough. This also impacts on
42  * the minimum space we need to leave free in the AG.
43  *
44  * The tree is ordered by [ag block, owner, offset]. This is a large key size,
45  * but it is the only way to enforce unique keys when a block can be owned by
46  * multiple files at any offset. There's no need to order/search by extent
47  * size for online updating/management of the tree. It is intended that most
48  * reverse lookups will be to find the owner(s) of a particular block, or to
49  * try to recover tree and file data from corrupt primary metadata.
50  */
51 
52 static struct xfs_btree_cur *
xfs_rmapbt_dup_cursor(struct xfs_btree_cur * cur)53 xfs_rmapbt_dup_cursor(
54 	struct xfs_btree_cur	*cur)
55 {
56 	return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp,
57 				cur->bc_ag.agbp, cur->bc_ag.pag);
58 }
59 
60 STATIC void
xfs_rmapbt_set_root(struct xfs_btree_cur * cur,const union xfs_btree_ptr * ptr,int inc)61 xfs_rmapbt_set_root(
62 	struct xfs_btree_cur		*cur,
63 	const union xfs_btree_ptr	*ptr,
64 	int				inc)
65 {
66 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
67 	struct xfs_agf		*agf = agbp->b_addr;
68 	int			btnum = cur->bc_btnum;
69 
70 	ASSERT(ptr->s != 0);
71 
72 	agf->agf_roots[btnum] = ptr->s;
73 	be32_add_cpu(&agf->agf_levels[btnum], inc);
74 	cur->bc_ag.pag->pagf_levels[btnum] += inc;
75 
76 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
77 }
78 
79 STATIC int
xfs_rmapbt_alloc_block(struct xfs_btree_cur * cur,const union xfs_btree_ptr * start,union xfs_btree_ptr * new,int * stat)80 xfs_rmapbt_alloc_block(
81 	struct xfs_btree_cur		*cur,
82 	const union xfs_btree_ptr	*start,
83 	union xfs_btree_ptr		*new,
84 	int				*stat)
85 {
86 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
87 	struct xfs_agf		*agf = agbp->b_addr;
88 	struct xfs_perag	*pag = cur->bc_ag.pag;
89 	int			error;
90 	xfs_agblock_t		bno;
91 
92 	/* Allocate the new block from the freelist. If we can't, give up.  */
93 	error = xfs_alloc_get_freelist(pag, cur->bc_tp, cur->bc_ag.agbp,
94 				       &bno, 1);
95 	if (error)
96 		return error;
97 
98 	trace_xfs_rmapbt_alloc_block(cur->bc_mp, pag->pag_agno, bno, 1);
99 	if (bno == NULLAGBLOCK) {
100 		*stat = 0;
101 		return 0;
102 	}
103 
104 	xfs_extent_busy_reuse(cur->bc_mp, pag, bno, 1, false);
105 
106 	new->s = cpu_to_be32(bno);
107 	be32_add_cpu(&agf->agf_rmap_blocks, 1);
108 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
109 
110 	xfs_ag_resv_rmapbt_alloc(cur->bc_mp, pag->pag_agno);
111 
112 	*stat = 1;
113 	return 0;
114 }
115 
116 STATIC int
xfs_rmapbt_free_block(struct xfs_btree_cur * cur,struct xfs_buf * bp)117 xfs_rmapbt_free_block(
118 	struct xfs_btree_cur	*cur,
119 	struct xfs_buf		*bp)
120 {
121 	struct xfs_buf		*agbp = cur->bc_ag.agbp;
122 	struct xfs_agf		*agf = agbp->b_addr;
123 	struct xfs_perag	*pag = cur->bc_ag.pag;
124 	xfs_agblock_t		bno;
125 	int			error;
126 
127 	bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp));
128 	trace_xfs_rmapbt_free_block(cur->bc_mp, pag->pag_agno,
129 			bno, 1);
130 	be32_add_cpu(&agf->agf_rmap_blocks, -1);
131 	xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS);
132 	error = xfs_alloc_put_freelist(pag, cur->bc_tp, agbp, NULL, bno, 1);
133 	if (error)
134 		return error;
135 
136 	xfs_extent_busy_insert(cur->bc_tp, pag, bno, 1,
137 			      XFS_EXTENT_BUSY_SKIP_DISCARD);
138 
139 	xfs_ag_resv_free_extent(pag, XFS_AG_RESV_RMAPBT, NULL, 1);
140 	return 0;
141 }
142 
143 STATIC int
xfs_rmapbt_get_minrecs(struct xfs_btree_cur * cur,int level)144 xfs_rmapbt_get_minrecs(
145 	struct xfs_btree_cur	*cur,
146 	int			level)
147 {
148 	return cur->bc_mp->m_rmap_mnr[level != 0];
149 }
150 
151 STATIC int
xfs_rmapbt_get_maxrecs(struct xfs_btree_cur * cur,int level)152 xfs_rmapbt_get_maxrecs(
153 	struct xfs_btree_cur	*cur,
154 	int			level)
155 {
156 	return cur->bc_mp->m_rmap_mxr[level != 0];
157 }
158 
159 /*
160  * Convert the ondisk record's offset field into the ondisk key's offset field.
161  * Fork and bmbt are significant parts of the rmap record key, but written
162  * status is merely a record attribute.
163  */
ondisk_rec_offset_to_key(const union xfs_btree_rec * rec)164 static inline __be64 ondisk_rec_offset_to_key(const union xfs_btree_rec *rec)
165 {
166 	return rec->rmap.rm_offset & ~cpu_to_be64(XFS_RMAP_OFF_UNWRITTEN);
167 }
168 
169 STATIC void
xfs_rmapbt_init_key_from_rec(union xfs_btree_key * key,const union xfs_btree_rec * rec)170 xfs_rmapbt_init_key_from_rec(
171 	union xfs_btree_key		*key,
172 	const union xfs_btree_rec	*rec)
173 {
174 	key->rmap.rm_startblock = rec->rmap.rm_startblock;
175 	key->rmap.rm_owner = rec->rmap.rm_owner;
176 	key->rmap.rm_offset = ondisk_rec_offset_to_key(rec);
177 }
178 
179 /*
180  * The high key for a reverse mapping record can be computed by shifting
181  * the startblock and offset to the highest value that would still map
182  * to that record.  In practice this means that we add blockcount-1 to
183  * the startblock for all records, and if the record is for a data/attr
184  * fork mapping, we add blockcount-1 to the offset too.
185  */
186 STATIC void
xfs_rmapbt_init_high_key_from_rec(union xfs_btree_key * key,const union xfs_btree_rec * rec)187 xfs_rmapbt_init_high_key_from_rec(
188 	union xfs_btree_key		*key,
189 	const union xfs_btree_rec	*rec)
190 {
191 	uint64_t			off;
192 	int				adj;
193 
194 	adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1;
195 
196 	key->rmap.rm_startblock = rec->rmap.rm_startblock;
197 	be32_add_cpu(&key->rmap.rm_startblock, adj);
198 	key->rmap.rm_owner = rec->rmap.rm_owner;
199 	key->rmap.rm_offset = ondisk_rec_offset_to_key(rec);
200 	if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) ||
201 	    XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset)))
202 		return;
203 	off = be64_to_cpu(key->rmap.rm_offset);
204 	off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK);
205 	key->rmap.rm_offset = cpu_to_be64(off);
206 }
207 
208 STATIC void
xfs_rmapbt_init_rec_from_cur(struct xfs_btree_cur * cur,union xfs_btree_rec * rec)209 xfs_rmapbt_init_rec_from_cur(
210 	struct xfs_btree_cur	*cur,
211 	union xfs_btree_rec	*rec)
212 {
213 	rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock);
214 	rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount);
215 	rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner);
216 	rec->rmap.rm_offset = cpu_to_be64(
217 			xfs_rmap_irec_offset_pack(&cur->bc_rec.r));
218 }
219 
220 STATIC void
xfs_rmapbt_init_ptr_from_cur(struct xfs_btree_cur * cur,union xfs_btree_ptr * ptr)221 xfs_rmapbt_init_ptr_from_cur(
222 	struct xfs_btree_cur	*cur,
223 	union xfs_btree_ptr	*ptr)
224 {
225 	struct xfs_agf		*agf = cur->bc_ag.agbp->b_addr;
226 
227 	ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));
228 
229 	ptr->s = agf->agf_roots[cur->bc_btnum];
230 }
231 
232 /*
233  * Mask the appropriate parts of the ondisk key field for a key comparison.
234  * Fork and bmbt are significant parts of the rmap record key, but written
235  * status is merely a record attribute.
236  */
offset_keymask(uint64_t offset)237 static inline uint64_t offset_keymask(uint64_t offset)
238 {
239 	return offset & ~XFS_RMAP_OFF_UNWRITTEN;
240 }
241 
242 STATIC int64_t
xfs_rmapbt_key_diff(struct xfs_btree_cur * cur,const union xfs_btree_key * key)243 xfs_rmapbt_key_diff(
244 	struct xfs_btree_cur		*cur,
245 	const union xfs_btree_key	*key)
246 {
247 	struct xfs_rmap_irec		*rec = &cur->bc_rec.r;
248 	const struct xfs_rmap_key	*kp = &key->rmap;
249 	__u64				x, y;
250 	int64_t				d;
251 
252 	d = (int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock;
253 	if (d)
254 		return d;
255 
256 	x = be64_to_cpu(kp->rm_owner);
257 	y = rec->rm_owner;
258 	if (x > y)
259 		return 1;
260 	else if (y > x)
261 		return -1;
262 
263 	x = offset_keymask(be64_to_cpu(kp->rm_offset));
264 	y = offset_keymask(xfs_rmap_irec_offset_pack(rec));
265 	if (x > y)
266 		return 1;
267 	else if (y > x)
268 		return -1;
269 	return 0;
270 }
271 
272 STATIC int64_t
xfs_rmapbt_diff_two_keys(struct xfs_btree_cur * cur,const union xfs_btree_key * k1,const union xfs_btree_key * k2,const union xfs_btree_key * mask)273 xfs_rmapbt_diff_two_keys(
274 	struct xfs_btree_cur		*cur,
275 	const union xfs_btree_key	*k1,
276 	const union xfs_btree_key	*k2,
277 	const union xfs_btree_key	*mask)
278 {
279 	const struct xfs_rmap_key	*kp1 = &k1->rmap;
280 	const struct xfs_rmap_key	*kp2 = &k2->rmap;
281 	int64_t				d;
282 	__u64				x, y;
283 
284 	/* Doesn't make sense to mask off the physical space part */
285 	ASSERT(!mask || mask->rmap.rm_startblock);
286 
287 	d = (int64_t)be32_to_cpu(kp1->rm_startblock) -
288 		     be32_to_cpu(kp2->rm_startblock);
289 	if (d)
290 		return d;
291 
292 	if (!mask || mask->rmap.rm_owner) {
293 		x = be64_to_cpu(kp1->rm_owner);
294 		y = be64_to_cpu(kp2->rm_owner);
295 		if (x > y)
296 			return 1;
297 		else if (y > x)
298 			return -1;
299 	}
300 
301 	if (!mask || mask->rmap.rm_offset) {
302 		/* Doesn't make sense to allow offset but not owner */
303 		ASSERT(!mask || mask->rmap.rm_owner);
304 
305 		x = offset_keymask(be64_to_cpu(kp1->rm_offset));
306 		y = offset_keymask(be64_to_cpu(kp2->rm_offset));
307 		if (x > y)
308 			return 1;
309 		else if (y > x)
310 			return -1;
311 	}
312 
313 	return 0;
314 }
315 
316 static xfs_failaddr_t
xfs_rmapbt_verify(struct xfs_buf * bp)317 xfs_rmapbt_verify(
318 	struct xfs_buf		*bp)
319 {
320 	struct xfs_mount	*mp = bp->b_mount;
321 	struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
322 	struct xfs_perag	*pag = bp->b_pag;
323 	xfs_failaddr_t		fa;
324 	unsigned int		level;
325 
326 	/*
327 	 * magic number and level verification
328 	 *
329 	 * During growfs operations, we can't verify the exact level or owner as
330 	 * the perag is not fully initialised and hence not attached to the
331 	 * buffer.  In this case, check against the maximum tree depth.
332 	 *
333 	 * Similarly, during log recovery we will have a perag structure
334 	 * attached, but the agf information will not yet have been initialised
335 	 * from the on disk AGF. Again, we can only check against maximum limits
336 	 * in this case.
337 	 */
338 	if (!xfs_verify_magic(bp, block->bb_magic))
339 		return __this_address;
340 
341 	if (!xfs_has_rmapbt(mp))
342 		return __this_address;
343 	fa = xfs_btree_sblock_v5hdr_verify(bp);
344 	if (fa)
345 		return fa;
346 
347 	level = be16_to_cpu(block->bb_level);
348 	if (pag && xfs_perag_initialised_agf(pag)) {
349 		if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi])
350 			return __this_address;
351 	} else if (level >= mp->m_rmap_maxlevels)
352 		return __this_address;
353 
354 	return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]);
355 }
356 
357 static void
xfs_rmapbt_read_verify(struct xfs_buf * bp)358 xfs_rmapbt_read_verify(
359 	struct xfs_buf	*bp)
360 {
361 	xfs_failaddr_t	fa;
362 
363 	if (!xfs_btree_sblock_verify_crc(bp))
364 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
365 	else {
366 		fa = xfs_rmapbt_verify(bp);
367 		if (fa)
368 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
369 	}
370 
371 	if (bp->b_error)
372 		trace_xfs_btree_corrupt(bp, _RET_IP_);
373 }
374 
375 static void
xfs_rmapbt_write_verify(struct xfs_buf * bp)376 xfs_rmapbt_write_verify(
377 	struct xfs_buf	*bp)
378 {
379 	xfs_failaddr_t	fa;
380 
381 	fa = xfs_rmapbt_verify(bp);
382 	if (fa) {
383 		trace_xfs_btree_corrupt(bp, _RET_IP_);
384 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
385 		return;
386 	}
387 	xfs_btree_sblock_calc_crc(bp);
388 
389 }
390 
391 const struct xfs_buf_ops xfs_rmapbt_buf_ops = {
392 	.name			= "xfs_rmapbt",
393 	.magic			= { 0, cpu_to_be32(XFS_RMAP_CRC_MAGIC) },
394 	.verify_read		= xfs_rmapbt_read_verify,
395 	.verify_write		= xfs_rmapbt_write_verify,
396 	.verify_struct		= xfs_rmapbt_verify,
397 };
398 
399 STATIC int
xfs_rmapbt_keys_inorder(struct xfs_btree_cur * cur,const union xfs_btree_key * k1,const union xfs_btree_key * k2)400 xfs_rmapbt_keys_inorder(
401 	struct xfs_btree_cur		*cur,
402 	const union xfs_btree_key	*k1,
403 	const union xfs_btree_key	*k2)
404 {
405 	uint32_t		x;
406 	uint32_t		y;
407 	uint64_t		a;
408 	uint64_t		b;
409 
410 	x = be32_to_cpu(k1->rmap.rm_startblock);
411 	y = be32_to_cpu(k2->rmap.rm_startblock);
412 	if (x < y)
413 		return 1;
414 	else if (x > y)
415 		return 0;
416 	a = be64_to_cpu(k1->rmap.rm_owner);
417 	b = be64_to_cpu(k2->rmap.rm_owner);
418 	if (a < b)
419 		return 1;
420 	else if (a > b)
421 		return 0;
422 	a = offset_keymask(be64_to_cpu(k1->rmap.rm_offset));
423 	b = offset_keymask(be64_to_cpu(k2->rmap.rm_offset));
424 	if (a <= b)
425 		return 1;
426 	return 0;
427 }
428 
429 STATIC int
xfs_rmapbt_recs_inorder(struct xfs_btree_cur * cur,const union xfs_btree_rec * r1,const union xfs_btree_rec * r2)430 xfs_rmapbt_recs_inorder(
431 	struct xfs_btree_cur		*cur,
432 	const union xfs_btree_rec	*r1,
433 	const union xfs_btree_rec	*r2)
434 {
435 	uint32_t		x;
436 	uint32_t		y;
437 	uint64_t		a;
438 	uint64_t		b;
439 
440 	x = be32_to_cpu(r1->rmap.rm_startblock);
441 	y = be32_to_cpu(r2->rmap.rm_startblock);
442 	if (x < y)
443 		return 1;
444 	else if (x > y)
445 		return 0;
446 	a = be64_to_cpu(r1->rmap.rm_owner);
447 	b = be64_to_cpu(r2->rmap.rm_owner);
448 	if (a < b)
449 		return 1;
450 	else if (a > b)
451 		return 0;
452 	a = offset_keymask(be64_to_cpu(r1->rmap.rm_offset));
453 	b = offset_keymask(be64_to_cpu(r2->rmap.rm_offset));
454 	if (a <= b)
455 		return 1;
456 	return 0;
457 }
458 
459 STATIC enum xbtree_key_contig
xfs_rmapbt_keys_contiguous(struct xfs_btree_cur * cur,const union xfs_btree_key * key1,const union xfs_btree_key * key2,const union xfs_btree_key * mask)460 xfs_rmapbt_keys_contiguous(
461 	struct xfs_btree_cur		*cur,
462 	const union xfs_btree_key	*key1,
463 	const union xfs_btree_key	*key2,
464 	const union xfs_btree_key	*mask)
465 {
466 	ASSERT(!mask || mask->rmap.rm_startblock);
467 
468 	/*
469 	 * We only support checking contiguity of the physical space component.
470 	 * If any callers ever need more specificity than that, they'll have to
471 	 * implement it here.
472 	 */
473 	ASSERT(!mask || (!mask->rmap.rm_owner && !mask->rmap.rm_offset));
474 
475 	return xbtree_key_contig(be32_to_cpu(key1->rmap.rm_startblock),
476 				 be32_to_cpu(key2->rmap.rm_startblock));
477 }
478 
479 static const struct xfs_btree_ops xfs_rmapbt_ops = {
480 	.rec_len		= sizeof(struct xfs_rmap_rec),
481 	.key_len		= 2 * sizeof(struct xfs_rmap_key),
482 
483 	.dup_cursor		= xfs_rmapbt_dup_cursor,
484 	.set_root		= xfs_rmapbt_set_root,
485 	.alloc_block		= xfs_rmapbt_alloc_block,
486 	.free_block		= xfs_rmapbt_free_block,
487 	.get_minrecs		= xfs_rmapbt_get_minrecs,
488 	.get_maxrecs		= xfs_rmapbt_get_maxrecs,
489 	.init_key_from_rec	= xfs_rmapbt_init_key_from_rec,
490 	.init_high_key_from_rec	= xfs_rmapbt_init_high_key_from_rec,
491 	.init_rec_from_cur	= xfs_rmapbt_init_rec_from_cur,
492 	.init_ptr_from_cur	= xfs_rmapbt_init_ptr_from_cur,
493 	.key_diff		= xfs_rmapbt_key_diff,
494 	.buf_ops		= &xfs_rmapbt_buf_ops,
495 	.diff_two_keys		= xfs_rmapbt_diff_two_keys,
496 	.keys_inorder		= xfs_rmapbt_keys_inorder,
497 	.recs_inorder		= xfs_rmapbt_recs_inorder,
498 	.keys_contiguous	= xfs_rmapbt_keys_contiguous,
499 };
500 
501 static struct xfs_btree_cur *
xfs_rmapbt_init_common(struct xfs_mount * mp,struct xfs_trans * tp,struct xfs_perag * pag)502 xfs_rmapbt_init_common(
503 	struct xfs_mount	*mp,
504 	struct xfs_trans	*tp,
505 	struct xfs_perag	*pag)
506 {
507 	struct xfs_btree_cur	*cur;
508 
509 	/* Overlapping btree; 2 keys per pointer. */
510 	cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RMAP,
511 			mp->m_rmap_maxlevels, xfs_rmapbt_cur_cache);
512 	cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING;
513 	cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_rmap_2);
514 	cur->bc_ops = &xfs_rmapbt_ops;
515 
516 	cur->bc_ag.pag = xfs_perag_hold(pag);
517 	return cur;
518 }
519 
520 /* Create a new reverse mapping btree cursor. */
521 struct xfs_btree_cur *
xfs_rmapbt_init_cursor(struct xfs_mount * mp,struct xfs_trans * tp,struct xfs_buf * agbp,struct xfs_perag * pag)522 xfs_rmapbt_init_cursor(
523 	struct xfs_mount	*mp,
524 	struct xfs_trans	*tp,
525 	struct xfs_buf		*agbp,
526 	struct xfs_perag	*pag)
527 {
528 	struct xfs_agf		*agf = agbp->b_addr;
529 	struct xfs_btree_cur	*cur;
530 
531 	cur = xfs_rmapbt_init_common(mp, tp, pag);
532 	cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]);
533 	cur->bc_ag.agbp = agbp;
534 	return cur;
535 }
536 
537 /* Create a new reverse mapping btree cursor with a fake root for staging. */
538 struct xfs_btree_cur *
xfs_rmapbt_stage_cursor(struct xfs_mount * mp,struct xbtree_afakeroot * afake,struct xfs_perag * pag)539 xfs_rmapbt_stage_cursor(
540 	struct xfs_mount	*mp,
541 	struct xbtree_afakeroot	*afake,
542 	struct xfs_perag	*pag)
543 {
544 	struct xfs_btree_cur	*cur;
545 
546 	cur = xfs_rmapbt_init_common(mp, NULL, pag);
547 	xfs_btree_stage_afakeroot(cur, afake);
548 	return cur;
549 }
550 
551 /*
552  * Install a new reverse mapping btree root.  Caller is responsible for
553  * invalidating and freeing the old btree blocks.
554  */
555 void
xfs_rmapbt_commit_staged_btree(struct xfs_btree_cur * cur,struct xfs_trans * tp,struct xfs_buf * agbp)556 xfs_rmapbt_commit_staged_btree(
557 	struct xfs_btree_cur	*cur,
558 	struct xfs_trans	*tp,
559 	struct xfs_buf		*agbp)
560 {
561 	struct xfs_agf		*agf = agbp->b_addr;
562 	struct xbtree_afakeroot	*afake = cur->bc_ag.afake;
563 
564 	ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
565 
566 	agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root);
567 	agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels);
568 	agf->agf_rmap_blocks = cpu_to_be32(afake->af_blocks);
569 	xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS |
570 				    XFS_AGF_RMAP_BLOCKS);
571 	xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_rmapbt_ops);
572 }
573 
574 /* Calculate number of records in a reverse mapping btree block. */
575 static inline unsigned int
xfs_rmapbt_block_maxrecs(unsigned int blocklen,bool leaf)576 xfs_rmapbt_block_maxrecs(
577 	unsigned int		blocklen,
578 	bool			leaf)
579 {
580 	if (leaf)
581 		return blocklen / sizeof(struct xfs_rmap_rec);
582 	return blocklen /
583 		(2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
584 }
585 
586 /*
587  * Calculate number of records in an rmap btree block.
588  */
589 int
xfs_rmapbt_maxrecs(int blocklen,int leaf)590 xfs_rmapbt_maxrecs(
591 	int			blocklen,
592 	int			leaf)
593 {
594 	blocklen -= XFS_RMAP_BLOCK_LEN;
595 	return xfs_rmapbt_block_maxrecs(blocklen, leaf);
596 }
597 
598 /* Compute the max possible height for reverse mapping btrees. */
599 unsigned int
xfs_rmapbt_maxlevels_ondisk(void)600 xfs_rmapbt_maxlevels_ondisk(void)
601 {
602 	unsigned int		minrecs[2];
603 	unsigned int		blocklen;
604 
605 	blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
606 
607 	minrecs[0] = xfs_rmapbt_block_maxrecs(blocklen, true) / 2;
608 	minrecs[1] = xfs_rmapbt_block_maxrecs(blocklen, false) / 2;
609 
610 	/*
611 	 * Compute the asymptotic maxlevels for an rmapbt on any reflink fs.
612 	 *
613 	 * On a reflink filesystem, each AG block can have up to 2^32 (per the
614 	 * refcount record format) owners, which means that theoretically we
615 	 * could face up to 2^64 rmap records.  However, we're likely to run
616 	 * out of blocks in the AG long before that happens, which means that
617 	 * we must compute the max height based on what the btree will look
618 	 * like if it consumes almost all the blocks in the AG due to maximal
619 	 * sharing factor.
620 	 */
621 	return xfs_btree_space_to_height(minrecs, XFS_MAX_CRC_AG_BLOCKS);
622 }
623 
624 /* Compute the maximum height of an rmap btree. */
625 void
xfs_rmapbt_compute_maxlevels(struct xfs_mount * mp)626 xfs_rmapbt_compute_maxlevels(
627 	struct xfs_mount		*mp)
628 {
629 	if (!xfs_has_rmapbt(mp)) {
630 		mp->m_rmap_maxlevels = 0;
631 		return;
632 	}
633 
634 	if (xfs_has_reflink(mp)) {
635 		/*
636 		 * Compute the asymptotic maxlevels for an rmap btree on a
637 		 * filesystem that supports reflink.
638 		 *
639 		 * On a reflink filesystem, each AG block can have up to 2^32
640 		 * (per the refcount record format) owners, which means that
641 		 * theoretically we could face up to 2^64 rmap records.
642 		 * However, we're likely to run out of blocks in the AG long
643 		 * before that happens, which means that we must compute the
644 		 * max height based on what the btree will look like if it
645 		 * consumes almost all the blocks in the AG due to maximal
646 		 * sharing factor.
647 		 */
648 		mp->m_rmap_maxlevels = xfs_btree_space_to_height(mp->m_rmap_mnr,
649 				mp->m_sb.sb_agblocks);
650 	} else {
651 		/*
652 		 * If there's no block sharing, compute the maximum rmapbt
653 		 * height assuming one rmap record per AG block.
654 		 */
655 		mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(
656 				mp->m_rmap_mnr, mp->m_sb.sb_agblocks);
657 	}
658 	ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk());
659 }
660 
661 /* Calculate the refcount btree size for some records. */
662 xfs_extlen_t
xfs_rmapbt_calc_size(struct xfs_mount * mp,unsigned long long len)663 xfs_rmapbt_calc_size(
664 	struct xfs_mount	*mp,
665 	unsigned long long	len)
666 {
667 	return xfs_btree_calc_size(mp->m_rmap_mnr, len);
668 }
669 
670 /*
671  * Calculate the maximum refcount btree size.
672  */
673 xfs_extlen_t
xfs_rmapbt_max_size(struct xfs_mount * mp,xfs_agblock_t agblocks)674 xfs_rmapbt_max_size(
675 	struct xfs_mount	*mp,
676 	xfs_agblock_t		agblocks)
677 {
678 	/* Bail out if we're uninitialized, which can happen in mkfs. */
679 	if (mp->m_rmap_mxr[0] == 0)
680 		return 0;
681 
682 	return xfs_rmapbt_calc_size(mp, agblocks);
683 }
684 
685 /*
686  * Figure out how many blocks to reserve and how many are used by this btree.
687  */
688 int
xfs_rmapbt_calc_reserves(struct xfs_mount * mp,struct xfs_trans * tp,struct xfs_perag * pag,xfs_extlen_t * ask,xfs_extlen_t * used)689 xfs_rmapbt_calc_reserves(
690 	struct xfs_mount	*mp,
691 	struct xfs_trans	*tp,
692 	struct xfs_perag	*pag,
693 	xfs_extlen_t		*ask,
694 	xfs_extlen_t		*used)
695 {
696 	struct xfs_buf		*agbp;
697 	struct xfs_agf		*agf;
698 	xfs_agblock_t		agblocks;
699 	xfs_extlen_t		tree_len;
700 	int			error;
701 
702 	if (!xfs_has_rmapbt(mp))
703 		return 0;
704 
705 	error = xfs_alloc_read_agf(pag, tp, 0, &agbp);
706 	if (error)
707 		return error;
708 
709 	agf = agbp->b_addr;
710 	agblocks = be32_to_cpu(agf->agf_length);
711 	tree_len = be32_to_cpu(agf->agf_rmap_blocks);
712 	xfs_trans_brelse(tp, agbp);
713 
714 	/*
715 	 * The log is permanently allocated, so the space it occupies will
716 	 * never be available for the kinds of things that would require btree
717 	 * expansion.  We therefore can pretend the space isn't there.
718 	 */
719 	if (xfs_ag_contains_log(mp, pag->pag_agno))
720 		agblocks -= mp->m_sb.sb_logblocks;
721 
722 	/* Reserve 1% of the AG or enough for 1 block per record. */
723 	*ask += max(agblocks / 100, xfs_rmapbt_max_size(mp, agblocks));
724 	*used += tree_len;
725 
726 	return error;
727 }
728 
729 int __init
xfs_rmapbt_init_cur_cache(void)730 xfs_rmapbt_init_cur_cache(void)
731 {
732 	xfs_rmapbt_cur_cache = kmem_cache_create("xfs_rmapbt_cur",
733 			xfs_btree_cur_sizeof(xfs_rmapbt_maxlevels_ondisk()),
734 			0, 0, NULL);
735 
736 	if (!xfs_rmapbt_cur_cache)
737 		return -ENOMEM;
738 	return 0;
739 }
740 
741 void
xfs_rmapbt_destroy_cur_cache(void)742 xfs_rmapbt_destroy_cur_cache(void)
743 {
744 	kmem_cache_destroy(xfs_rmapbt_cur_cache);
745 	xfs_rmapbt_cur_cache = NULL;
746 }
747