[linux-2.6-block.git] / fs / xfs / scrub / bitmap.c

// SPDX-License-Identifier: GPL-2.0+
/*
 * Copyright (C) 2018 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.h"
#include "xfs_btree.h"
#include "scrub/xfs_scrub.h"
#include "scrub/scrub.h"
#include "scrub/common.h"
#include "scrub/trace.h"
#include "scrub/repair.h"
#include "scrub/bitmap.h"

/*
 * Set a range of this bitmap.  Caller must ensure the range is not set.
 *
 * This is the logical equivalent of bitmap |= mask(start, len).
 */
int
xfs_bitmap_set(
	struct xfs_bitmap	*bitmap,
	uint64_t		start,
	uint64_t		len)
{
	struct xfs_bitmap_range	*bmr;

	bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL);
	if (!bmr)
		return -ENOMEM;

	INIT_LIST_HEAD(&bmr->list);
	bmr->start = start;
	bmr->len = len;
	list_add_tail(&bmr->list, &bitmap->list);

	return 0;
}

/* Free everything related to this bitmap. */
void
xfs_bitmap_destroy(
	struct xfs_bitmap	*bitmap)
{
	struct xfs_bitmap_range	*bmr;
	struct xfs_bitmap_range	*n;

	for_each_xfs_bitmap_extent(bmr, n, bitmap) {
		list_del(&bmr->list);
		kmem_free(bmr);
	}
}

/* Set up a per-AG block bitmap. */
void
xfs_bitmap_init(
	struct xfs_bitmap	*bitmap)
{
	INIT_LIST_HEAD(&bitmap->list);
}

/* Compare two btree extents. */
static int
xfs_bitmap_range_cmp(
	void			*priv,
	struct list_head	*a,
	struct list_head	*b)
{
	struct xfs_bitmap_range	*ap;
	struct xfs_bitmap_range	*bp;

	ap = container_of(a, struct xfs_bitmap_range, list);
	bp = container_of(b, struct xfs_bitmap_range, list);

	if (ap->start > bp->start)
		return 1;
	if (ap->start < bp->start)
		return -1;
	return 0;
}

/*
 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
 *
 * The intent is that callers will iterate the rmapbt for all of its records
 * for a given owner to generate @bitmap; and iterate all the blocks of the
 * metadata structures that are not being rebuilt and have the same rmapbt
 * owner to generate @sub.  This routine subtracts all the extents
 * mentioned in sub from all the extents linked in @bitmap, which leaves
 * @bitmap as the list of blocks that are not accounted for, which we assume
 * are the dead blocks of the old metadata structure.  The blocks mentioned in
 * @bitmap can be reaped.
 *
 * This is the logical equivalent of bitmap &= ~sub.
 */
#define LEFT_ALIGNED	(1 << 0)
#define RIGHT_ALIGNED	(1 << 1)
int
xfs_bitmap_disunion(
	struct xfs_bitmap	*bitmap,
	struct xfs_bitmap	*sub)
{
	struct list_head	*lp;
	struct xfs_bitmap_range	*br;
	struct xfs_bitmap_range	*new_br;
	struct xfs_bitmap_range	*sub_br;
	uint64_t		sub_start;
	uint64_t		sub_len;
	int			state;
	int			error = 0;

	if (list_empty(&bitmap->list) || list_empty(&sub->list))
		return 0;
	ASSERT(!list_empty(&sub->list));

	list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);
	list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);

	/*
	 * Now that we've sorted both lists, we iterate bitmap once, rolling
	 * forward through sub and/or bitmap as necessary until we find an
	 * overlap or reach the end of either list.  We do not reset lp to the
	 * head of bitmap nor do we reset sub_br to the head of sub.  The
	 * list traversal is similar to merge sort, but we're deleting
	 * instead.  In this manner we avoid O(n^2) operations.
	 */
	sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
			list);
	lp = bitmap->list.next;
	while (lp != &bitmap->list) {
		br = list_entry(lp, struct xfs_bitmap_range, list);

		/*
		 * Advance sub_br and/or br until we find a pair that
		 * intersect or we run out of extents.
		 */
		while (sub_br->start + sub_br->len <= br->start) {
			if (list_is_last(&sub_br->list, &sub->list))
				goto out;
			sub_br = list_next_entry(sub_br, list);
		}
		if (sub_br->start >= br->start + br->len) {
			lp = lp->next;
			continue;
		}

		/* trim sub_br to fit the extent we have */
		sub_start = sub_br->start;
		sub_len = sub_br->len;
		if (sub_br->start < br->start) {
			sub_len -= br->start - sub_br->start;
			sub_start = br->start;
		}
		if (sub_len > br->len)
			sub_len = br->len;

		state = 0;
		if (sub_start == br->start)
			state |= LEFT_ALIGNED;
		if (sub_start + sub_len == br->start + br->len)
			state |= RIGHT_ALIGNED;
		switch (state) {
		case LEFT_ALIGNED:
			/* Coincides with only the left. */
			br->start += sub_len;
			br->len -= sub_len;
			break;
		case RIGHT_ALIGNED:
			/* Coincides with only the right. */
			br->len -= sub_len;
			lp = lp->next;
			break;
		case LEFT_ALIGNED | RIGHT_ALIGNED:
			/* Total overlap, just delete ex. */
			lp = lp->next;
			list_del(&br->list);
			kmem_free(br);
			break;
		case 0:
			/*
			 * Deleting from the middle: add the new right extent
			 * and then shrink the left extent.
			 */
			new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
					KM_MAYFAIL);
			if (!new_br) {
				error = -ENOMEM;
				goto out;
			}
			INIT_LIST_HEAD(&new_br->list);
			new_br->start = sub_start + sub_len;
			new_br->len = br->start + br->len - new_br->start;
			list_add(&new_br->list, &br->list);
			br->len = sub_start - br->start;
			lp = lp->next;
			break;
		default:
			ASSERT(0);
			break;
		}
	}

out:
	return error;
}
#undef LEFT_ALIGNED
#undef RIGHT_ALIGNED

/*
 * Record all btree blocks seen while iterating all records of a btree.
 *
 * We know that the btree query_all function starts at the left edge and walks
 * towards the right edge of the tree.  Therefore, we know that we can walk up
 * the btree cursor towards the root; if the pointer for a given level points
 * to the first record/key in that block, we haven't seen this block before;
 * and therefore we need to remember that we saw this block in the btree.
 *
 * So if our btree is:
 *
 *    4
 *  / | \
 * 1  2  3
 *
 * Pretend for this example that each leaf block has 100 btree records.  For
 * the first btree record, we'll observe that bc_ptrs[0] == 1, so we record
 * that we saw block 1.  Then we observe that bc_ptrs[1] == 1, so we record
 * block 4.  The list is [1, 4].
 *
 * For the second btree record, we see that bc_ptrs[0] == 2, so we exit the
 * loop.  The list remains [1, 4].
 *
 * For the 101st btree record, we've moved onto leaf block 2.  Now
 * bc_ptrs[0] == 1 again, so we record that we saw block 2.  We see that
 * bc_ptrs[1] == 2, so we exit the loop.  The list is now [1, 4, 2].
 *
 * For the 102nd record, bc_ptrs[0] == 2, so we continue.
 *
 * For the 201st record, we've moved on to leaf block 3.  bc_ptrs[0] == 1, so
 * we add 3 to the list.  Now it is [1, 4, 2, 3].
 *
 * For the 300th record we just exit, with the list being [1, 4, 2, 3].
 */

/*
 * Record all the buffers pointed to by the btree cursor.  Callers already
 * engaged in a btree walk should call this function to capture the list of
 * blocks going from the leaf towards the root.
 */
int
xfs_bitmap_set_btcur_path(
	struct xfs_bitmap	*bitmap,
	struct xfs_btree_cur	*cur)
{
	struct xfs_buf		*bp;
	xfs_fsblock_t		fsb;
	int			i;
	int			error;

	for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
		xfs_btree_get_block(cur, i, &bp);
		if (!bp)
			continue;
		fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
		error = xfs_bitmap_set(bitmap, fsb, 1);
		if (error)
			return error;
	}

	return 0;
}

/* Collect a btree's block in the bitmap. */
STATIC int
xfs_bitmap_collect_btblock(
	struct xfs_btree_cur	*cur,
	int			level,
	void			*priv)
{
	struct xfs_bitmap	*bitmap = priv;
	struct xfs_buf		*bp;
	xfs_fsblock_t		fsbno;

	xfs_btree_get_block(cur, level, &bp);
	if (!bp)
		return 0;

	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
	return xfs_bitmap_set(bitmap, fsbno, 1);
}

/* Walk the btree and mark the bitmap wherever a btree block is found. */
int
xfs_bitmap_set_btblocks(
	struct xfs_bitmap	*bitmap,
	struct xfs_btree_cur	*cur)
{
	return xfs_btree_visit_blocks(cur, xfs_bitmap_collect_btblock, bitmap);
}
Commit	Line	Data
bc270b53 DW	1	// SPDX-License-Identifier: GPL-2.0+
	2	/*
	3	* Copyright (C) 2018 Oracle. All Rights Reserved.
	4	* Author: Darrick J. Wong <darrick.wong@oracle.com>
	5	*/
	6	#include "xfs.h"
	7	#include "xfs_fs.h"
	8	#include "xfs_shared.h"
	9	#include "xfs_format.h"
	10	#include "xfs_trans_resv.h"
	11	#include "xfs_mount.h"
0e93d3f4	12	#include "xfs_btree.h"
bc270b53 DW	13	#include "scrub/xfs_scrub.h"
	14	#include "scrub/scrub.h"
	15	#include "scrub/common.h"
	16	#include "scrub/trace.h"
	17	#include "scrub/repair.h"
	18	#include "scrub/bitmap.h"
	19
86d969b4 DW	20	/*
	21	* Set a range of this bitmap. Caller must ensure the range is not set.
	22	*
	23	* This is the logical equivalent of bitmap \|= mask(start, len).
	24	*/
bc270b53	25	int
86d969b4 DW	26	xfs_bitmap_set(
	27	struct xfs_bitmap *bitmap,
	28	uint64_t start,
	29	uint64_t len)
bc270b53	30	{
86d969b4	31	struct xfs_bitmap_range *bmr;
bc270b53	32
86d969b4 DW	33	bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL);
86d969b4 DW	34	if (!bmr)
bc270b53 DW	35	return -ENOMEM;
bc270b53 DW	36
86d969b4 DW	37	INIT_LIST_HEAD(&bmr->list);
	38	bmr->start = start;
	39	bmr->len = len;
	40	list_add_tail(&bmr->list, &bitmap->list);
bc270b53 DW	41
	42	return 0;
	43	}
	44
86d969b4	45	/* Free everything related to this bitmap. */
bc270b53	46	void
86d969b4 DW	47	xfs_bitmap_destroy(
86d969b4 DW	48	struct xfs_bitmap *bitmap)
bc270b53	49	{
86d969b4 DW	50	struct xfs_bitmap_range *bmr;
86d969b4 DW	51	struct xfs_bitmap_range *n;
bc270b53	52
86d969b4 DW	53	for_each_xfs_bitmap_extent(bmr, n, bitmap) {
	54	list_del(&bmr->list);
	55	kmem_free(bmr);
bc270b53 DW	56	}
	57	}
	58
86d969b4 DW	59	/* Set up a per-AG block bitmap. */
	60	void
	61	xfs_bitmap_init(
	62	struct xfs_bitmap *bitmap)
	63	{
	64	INIT_LIST_HEAD(&bitmap->list);
	65	}
	66
bc270b53 DW	67	/* Compare two btree extents. */
bc270b53 DW	68	static int
86d969b4	69	xfs_bitmap_range_cmp(
bc270b53 DW	70	void *priv,
	71	struct list_head *a,
	72	struct list_head *b)
	73	{
86d969b4 DW	74	struct xfs_bitmap_range *ap;
86d969b4 DW	75	struct xfs_bitmap_range *bp;
bc270b53	76
86d969b4 DW	77	ap = container_of(a, struct xfs_bitmap_range, list);
86d969b4 DW	78	bp = container_of(b, struct xfs_bitmap_range, list);
bc270b53	79
86d969b4	80	if (ap->start > bp->start)
bc270b53	81	return 1;
86d969b4	82	if (ap->start < bp->start)
bc270b53 DW	83	return -1;
	84	return 0;
	85	}
	86
	87	/*
86d969b4	88	* Remove all the blocks mentioned in @sub from the extents in @bitmap.
bc270b53 DW	89	*
bc270b53 DW	90	* The intent is that callers will iterate the rmapbt for all of its records
86d969b4	91	* for a given owner to generate @bitmap; and iterate all the blocks of the
bc270b53	92	* metadata structures that are not being rebuilt and have the same rmapbt
86d969b4 DW	93	* owner to generate @sub. This routine subtracts all the extents
	94	* mentioned in sub from all the extents linked in @bitmap, which leaves
	95	* @bitmap as the list of blocks that are not accounted for, which we assume
bc270b53	96	* are the dead blocks of the old metadata structure. The blocks mentioned in
86d969b4 DW	97	* @bitmap can be reaped.
	98	*
	99	* This is the logical equivalent of bitmap &= ~sub.
bc270b53 DW	100	*/
	101	#define LEFT_ALIGNED (1 << 0)
	102	#define RIGHT_ALIGNED (1 << 1)
	103	int
86d969b4 DW	104	xfs_bitmap_disunion(
	105	struct xfs_bitmap *bitmap,
	106	struct xfs_bitmap *sub)
bc270b53 DW	107	{
bc270b53 DW	108	struct list_head *lp;
86d969b4 DW	109	struct xfs_bitmap_range *br;
	110	struct xfs_bitmap_range *new_br;
	111	struct xfs_bitmap_range *sub_br;
	112	uint64_t sub_start;
	113	uint64_t sub_len;
bc270b53 DW	114	int state;
	115	int error = 0;
	116
86d969b4	117	if (list_empty(&bitmap->list) \|\| list_empty(&sub->list))
bc270b53	118	return 0;
86d969b4	119	ASSERT(!list_empty(&sub->list));
bc270b53	120
86d969b4 DW	121	list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);
86d969b4 DW	122	list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);
bc270b53 DW	123
bc270b53 DW	124	/*
86d969b4 DW	125	* Now that we've sorted both lists, we iterate bitmap once, rolling
86d969b4 DW	126	* forward through sub and/or bitmap as necessary until we find an
bc270b53	127	* overlap or reach the end of either list. We do not reset lp to the
86d969b4	128	* head of bitmap nor do we reset sub_br to the head of sub. The
bc270b53 DW	129	* list traversal is similar to merge sort, but we're deleting
	130	* instead. In this manner we avoid O(n^2) operations.
	131	*/
86d969b4	132	sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
bc270b53	133	list);
86d969b4 DW	134	lp = bitmap->list.next;
	135	while (lp != &bitmap->list) {
	136	br = list_entry(lp, struct xfs_bitmap_range, list);
bc270b53 DW	137
bc270b53 DW	138	/*
86d969b4	139	* Advance sub_br and/or br until we find a pair that
bc270b53 DW	140	* intersect or we run out of extents.
bc270b53 DW	141	*/
86d969b4 DW	142	while (sub_br->start + sub_br->len <= br->start) {
86d969b4 DW	143	if (list_is_last(&sub_br->list, &sub->list))
bc270b53	144	goto out;
86d969b4	145	sub_br = list_next_entry(sub_br, list);
bc270b53	146	}
86d969b4	147	if (sub_br->start >= br->start + br->len) {
bc270b53 DW	148	lp = lp->next;
	149	continue;
	150	}
	151
86d969b4 DW	152	/* trim sub_br to fit the extent we have */
	153	sub_start = sub_br->start;
	154	sub_len = sub_br->len;
	155	if (sub_br->start < br->start) {
	156	sub_len -= br->start - sub_br->start;
	157	sub_start = br->start;
bc270b53	158	}
86d969b4 DW	159	if (sub_len > br->len)
86d969b4 DW	160	sub_len = br->len;
bc270b53 DW	161
bc270b53 DW	162	state = 0;
86d969b4	163	if (sub_start == br->start)
bc270b53	164	state \|= LEFT_ALIGNED;
86d969b4	165	if (sub_start + sub_len == br->start + br->len)
bc270b53 DW	166	state \|= RIGHT_ALIGNED;
	167	switch (state) {
	168	case LEFT_ALIGNED:
	169	/* Coincides with only the left. */
86d969b4 DW	170	br->start += sub_len;
86d969b4 DW	171	br->len -= sub_len;
bc270b53 DW	172	break;
	173	case RIGHT_ALIGNED:
	174	/* Coincides with only the right. */
86d969b4	175	br->len -= sub_len;
bc270b53 DW	176	lp = lp->next;
	177	break;
	178	case LEFT_ALIGNED \| RIGHT_ALIGNED:
	179	/* Total overlap, just delete ex. */
	180	lp = lp->next;
86d969b4 DW	181	list_del(&br->list);
86d969b4 DW	182	kmem_free(br);
bc270b53 DW	183	break;
	184	case 0:
	185	/*
	186	* Deleting from the middle: add the new right extent
	187	* and then shrink the left extent.
	188	*/
86d969b4	189	new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
bc270b53	190	KM_MAYFAIL);
86d969b4	191	if (!new_br) {
bc270b53 DW	192	error = -ENOMEM;
	193	goto out;
	194	}
86d969b4 DW	195	INIT_LIST_HEAD(&new_br->list);
	196	new_br->start = sub_start + sub_len;
	197	new_br->len = br->start + br->len - new_br->start;
	198	list_add(&new_br->list, &br->list);
	199	br->len = sub_start - br->start;
bc270b53 DW	200	lp = lp->next;
	201	break;
	202	default:
	203	ASSERT(0);
	204	break;
	205	}
	206	}
	207
	208	out:
	209	return error;
	210	}
	211	#undef LEFT_ALIGNED
	212	#undef RIGHT_ALIGNED
0e93d3f4 DW	213
	214	/*
	215	* Record all btree blocks seen while iterating all records of a btree.
	216	*
	217	* We know that the btree query_all function starts at the left edge and walks
	218	* towards the right edge of the tree. Therefore, we know that we can walk up
	219	* the btree cursor towards the root; if the pointer for a given level points
	220	* to the first record/key in that block, we haven't seen this block before;
	221	* and therefore we need to remember that we saw this block in the btree.
	222	*
	223	* So if our btree is:
	224	*
	225	* 4
	226	* / \| \
	227	* 1 2 3
	228	*
	229	* Pretend for this example that each leaf block has 100 btree records. For
	230	* the first btree record, we'll observe that bc_ptrs[0] == 1, so we record
	231	* that we saw block 1. Then we observe that bc_ptrs[1] == 1, so we record
	232	* block 4. The list is [1, 4].
	233	*
	234	* For the second btree record, we see that bc_ptrs[0] == 2, so we exit the
	235	* loop. The list remains [1, 4].
	236	*
	237	* For the 101st btree record, we've moved onto leaf block 2. Now
	238	* bc_ptrs[0] == 1 again, so we record that we saw block 2. We see that
	239	* bc_ptrs[1] == 2, so we exit the loop. The list is now [1, 4, 2].
	240	*
	241	* For the 102nd record, bc_ptrs[0] == 2, so we continue.
	242	*
	243	* For the 201st record, we've moved on to leaf block 3. bc_ptrs[0] == 1, so
	244	* we add 3 to the list. Now it is [1, 4, 2, 3].
	245	*
	246	* For the 300th record we just exit, with the list being [1, 4, 2, 3].
	247	*/
	248
	249	/*
	250	* Record all the buffers pointed to by the btree cursor. Callers already
	251	* engaged in a btree walk should call this function to capture the list of
	252	* blocks going from the leaf towards the root.
	253	*/
	254	int
	255	xfs_bitmap_set_btcur_path(
	256	struct xfs_bitmap *bitmap,
	257	struct xfs_btree_cur *cur)
	258	{
	259	struct xfs_buf *bp;
	260	xfs_fsblock_t fsb;
	261	int i;
	262	int error;
	263
	264	for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
	265	xfs_btree_get_block(cur, i, &bp);
	266	if (!bp)
	267	continue;
	268	fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
	269	error = xfs_bitmap_set(bitmap, fsb, 1);
	270	if (error)
	271	return error;
	272	}
	273
	274	return 0;
	275	}
	276
277	/* Collect a btree's block in the bitmap. */
278	STATIC int
279	xfs_bitmap_collect_btblock(
280	struct xfs_btree_cur *cur,
281	int level,
282	void *priv)
283	{
284	struct xfs_bitmap *bitmap = priv;
285	struct xfs_buf *bp;
286	xfs_fsblock_t fsbno;
287
288	xfs_btree_get_block(cur, level, &bp);
289	if (!bp)
290	return 0;
291
292	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
293	return xfs_bitmap_set(bitmap, fsbno, 1);
294	}
295
296	/* Walk the btree and mark the bitmap wherever a btree block is found. */
297	int
298	xfs_bitmap_set_btblocks(
299	struct xfs_bitmap *bitmap,
300	struct xfs_btree_cur *cur)
301	{
302	return xfs_btree_visit_blocks(cur, xfs_bitmap_collect_btblock, bitmap);
303	}