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