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" 12 #include "scrub/xfs_scrub.h" 13 #include "scrub/scrub.h" 14 #include "scrub/common.h" 15 #include "scrub/trace.h" 16 #include "scrub/repair.h" 17 #include "scrub/bitmap.h" 18 19 /* 20 * Set a range of this bitmap. Caller must ensure the range is not set. 21 * 22 * This is the logical equivalent of bitmap |= mask(start, len). 23 */ 24 int 25 xfs_bitmap_set( 26 struct xfs_bitmap *bitmap, 27 uint64_t start, 28 uint64_t len) 29 { 30 struct xfs_bitmap_range *bmr; 31 32 bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL); 33 if (!bmr) 34 return -ENOMEM; 35 36 INIT_LIST_HEAD(&bmr->list); 37 bmr->start = start; 38 bmr->len = len; 39 list_add_tail(&bmr->list, &bitmap->list); 40 41 return 0; 42 } 43 44 /* Free everything related to this bitmap. */ 45 void 46 xfs_bitmap_destroy( 47 struct xfs_bitmap *bitmap) 48 { 49 struct xfs_bitmap_range *bmr; 50 struct xfs_bitmap_range *n; 51 52 for_each_xfs_bitmap_extent(bmr, n, bitmap) { 53 list_del(&bmr->list); 54 kmem_free(bmr); 55 } 56 } 57 58 /* Set up a per-AG block bitmap. */ 59 void 60 xfs_bitmap_init( 61 struct xfs_bitmap *bitmap) 62 { 63 INIT_LIST_HEAD(&bitmap->list); 64 } 65 66 /* Compare two btree extents. */ 67 static int 68 xfs_bitmap_range_cmp( 69 void *priv, 70 struct list_head *a, 71 struct list_head *b) 72 { 73 struct xfs_bitmap_range *ap; 74 struct xfs_bitmap_range *bp; 75 76 ap = container_of(a, struct xfs_bitmap_range, list); 77 bp = container_of(b, struct xfs_bitmap_range, list); 78 79 if (ap->start > bp->start) 80 return 1; 81 if (ap->start < bp->start) 82 return -1; 83 return 0; 84 } 85 86 /* 87 * Remove all the blocks mentioned in @sub from the extents in @bitmap. 88 * 89 * The intent is that callers will iterate the rmapbt for all of its records 90 * for a given owner to generate @bitmap; and iterate all the blocks of the 91 * metadata structures that are not being rebuilt and have the same rmapbt 92 * owner to generate @sub. This routine subtracts all the extents 93 * mentioned in sub from all the extents linked in @bitmap, which leaves 94 * @bitmap as the list of blocks that are not accounted for, which we assume 95 * are the dead blocks of the old metadata structure. The blocks mentioned in 96 * @bitmap can be reaped. 97 * 98 * This is the logical equivalent of bitmap &= ~sub. 99 */ 100 #define LEFT_ALIGNED (1 << 0) 101 #define RIGHT_ALIGNED (1 << 1) 102 int 103 xfs_bitmap_disunion( 104 struct xfs_bitmap *bitmap, 105 struct xfs_bitmap *sub) 106 { 107 struct list_head *lp; 108 struct xfs_bitmap_range *br; 109 struct xfs_bitmap_range *new_br; 110 struct xfs_bitmap_range *sub_br; 111 uint64_t sub_start; 112 uint64_t sub_len; 113 int state; 114 int error = 0; 115 116 if (list_empty(&bitmap->list) || list_empty(&sub->list)) 117 return 0; 118 ASSERT(!list_empty(&sub->list)); 119 120 list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp); 121 list_sort(NULL, &sub->list, xfs_bitmap_range_cmp); 122 123 /* 124 * Now that we've sorted both lists, we iterate bitmap once, rolling 125 * forward through sub and/or bitmap as necessary until we find an 126 * overlap or reach the end of either list. We do not reset lp to the 127 * head of bitmap nor do we reset sub_br to the head of sub. The 128 * list traversal is similar to merge sort, but we're deleting 129 * instead. In this manner we avoid O(n^2) operations. 130 */ 131 sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range, 132 list); 133 lp = bitmap->list.next; 134 while (lp != &bitmap->list) { 135 br = list_entry(lp, struct xfs_bitmap_range, list); 136 137 /* 138 * Advance sub_br and/or br until we find a pair that 139 * intersect or we run out of extents. 140 */ 141 while (sub_br->start + sub_br->len <= br->start) { 142 if (list_is_last(&sub_br->list, &sub->list)) 143 goto out; 144 sub_br = list_next_entry(sub_br, list); 145 } 146 if (sub_br->start >= br->start + br->len) { 147 lp = lp->next; 148 continue; 149 } 150 151 /* trim sub_br to fit the extent we have */ 152 sub_start = sub_br->start; 153 sub_len = sub_br->len; 154 if (sub_br->start < br->start) { 155 sub_len -= br->start - sub_br->start; 156 sub_start = br->start; 157 } 158 if (sub_len > br->len) 159 sub_len = br->len; 160 161 state = 0; 162 if (sub_start == br->start) 163 state |= LEFT_ALIGNED; 164 if (sub_start + sub_len == br->start + br->len) 165 state |= RIGHT_ALIGNED; 166 switch (state) { 167 case LEFT_ALIGNED: 168 /* Coincides with only the left. */ 169 br->start += sub_len; 170 br->len -= sub_len; 171 break; 172 case RIGHT_ALIGNED: 173 /* Coincides with only the right. */ 174 br->len -= sub_len; 175 lp = lp->next; 176 break; 177 case LEFT_ALIGNED | RIGHT_ALIGNED: 178 /* Total overlap, just delete ex. */ 179 lp = lp->next; 180 list_del(&br->list); 181 kmem_free(br); 182 break; 183 case 0: 184 /* 185 * Deleting from the middle: add the new right extent 186 * and then shrink the left extent. 187 */ 188 new_br = kmem_alloc(sizeof(struct xfs_bitmap_range), 189 KM_MAYFAIL); 190 if (!new_br) { 191 error = -ENOMEM; 192 goto out; 193 } 194 INIT_LIST_HEAD(&new_br->list); 195 new_br->start = sub_start + sub_len; 196 new_br->len = br->start + br->len - new_br->start; 197 list_add(&new_br->list, &br->list); 198 br->len = sub_start - br->start; 199 lp = lp->next; 200 break; 201 default: 202 ASSERT(0); 203 break; 204 } 205 } 206 207 out: 208 return error; 209 } 210 #undef LEFT_ALIGNED 211 #undef RIGHT_ALIGNED 212