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