blob: 813b5f21911387e32045ba65daadafd9a51e1389 [file] [log] [blame]
// 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/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
xbitmap_set(
struct xbitmap *bitmap,
uint64_t start,
uint64_t len)
{
struct xbitmap_range *bmr;
bmr = kmem_alloc(sizeof(struct xbitmap_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
xbitmap_destroy(
struct xbitmap *bitmap)
{
struct xbitmap_range *bmr;
struct xbitmap_range *n;
for_each_xbitmap_extent(bmr, n, bitmap) {
list_del(&bmr->list);
kmem_free(bmr);
}
}
/* Set up a per-AG block bitmap. */
void
xbitmap_init(
struct xbitmap *bitmap)
{
INIT_LIST_HEAD(&bitmap->list);
}
/* Compare two btree extents. */
static int
xbitmap_range_cmp(
void *priv,
const struct list_head *a,
const struct list_head *b)
{
struct xbitmap_range *ap;
struct xbitmap_range *bp;
ap = container_of(a, struct xbitmap_range, list);
bp = container_of(b, struct xbitmap_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
xbitmap_disunion(
struct xbitmap *bitmap,
struct xbitmap *sub)
{
struct list_head *lp;
struct xbitmap_range *br;
struct xbitmap_range *new_br;
struct xbitmap_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, xbitmap_range_cmp);
list_sort(NULL, &sub->list, xbitmap_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 xbitmap_range,
list);
lp = bitmap->list.next;
while (lp != &bitmap->list) {
br = list_entry(lp, struct xbitmap_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 xbitmap_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
xbitmap_set_btcur_path(
struct xbitmap *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 = xbitmap_set(bitmap, fsb, 1);
if (error)
return error;
}
return 0;
}
/* Collect a btree's block in the bitmap. */
STATIC int
xbitmap_collect_btblock(
struct xfs_btree_cur *cur,
int level,
void *priv)
{
struct xbitmap *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 xbitmap_set(bitmap, fsbno, 1);
}
/* Walk the btree and mark the bitmap wherever a btree block is found. */
int
xbitmap_set_btblocks(
struct xbitmap *bitmap,
struct xfs_btree_cur *cur)
{
return xfs_btree_visit_blocks(cur, xbitmap_collect_btblock,
XFS_BTREE_VISIT_ALL, bitmap);
}
/* How many bits are set in this bitmap? */
uint64_t
xbitmap_hweight(
struct xbitmap *bitmap)
{
struct xbitmap_range *bmr;
struct xbitmap_range *n;
uint64_t ret = 0;
for_each_xbitmap_extent(bmr, n, bitmap)
ret += bmr->len;
return ret;
}