1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Copyright (C) 2018-2023 Oracle. All Rights Reserved. 4 * Author: Darrick J. Wong <djwong@kernel.org> 5 */ 6 #include "xfs.h" 7 #include "xfs_fs.h" 8 #include "xfs_shared.h" 9 #include "xfs_bit.h" 10 #include "xfs_format.h" 11 #include "xfs_trans_resv.h" 12 #include "xfs_mount.h" 13 #include "xfs_btree.h" 14 #include "scrub/scrub.h" 15 #include "scrub/bitmap.h" 16 17 #include <linux/interval_tree_generic.h> 18 19 struct xbitmap_node { 20 struct rb_node bn_rbnode; 21 22 /* First set bit of this interval and subtree. */ 23 uint64_t bn_start; 24 25 /* Last set bit of this interval. */ 26 uint64_t bn_last; 27 28 /* Last set bit of this subtree. Do not touch this. */ 29 uint64_t __bn_subtree_last; 30 }; 31 32 /* Define our own interval tree type with uint64_t parameters. */ 33 34 #define START(node) ((node)->bn_start) 35 #define LAST(node) ((node)->bn_last) 36 37 /* 38 * These functions are defined by the INTERVAL_TREE_DEFINE macro, but we'll 39 * forward-declare them anyway for clarity. 40 */ 41 static inline void 42 xbitmap_tree_insert(struct xbitmap_node *node, struct rb_root_cached *root); 43 44 static inline void 45 xbitmap_tree_remove(struct xbitmap_node *node, struct rb_root_cached *root); 46 47 static inline struct xbitmap_node * 48 xbitmap_tree_iter_first(struct rb_root_cached *root, uint64_t start, 49 uint64_t last); 50 51 static inline struct xbitmap_node * 52 xbitmap_tree_iter_next(struct xbitmap_node *node, uint64_t start, 53 uint64_t last); 54 55 INTERVAL_TREE_DEFINE(struct xbitmap_node, bn_rbnode, uint64_t, 56 __bn_subtree_last, START, LAST, static inline, xbitmap_tree) 57 58 /* Iterate each interval of a bitmap. Do not change the bitmap. */ 59 #define for_each_xbitmap_extent(bn, bitmap) \ 60 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ 61 struct xbitmap_node, bn_rbnode); \ 62 (bn) != NULL; \ 63 (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \ 64 struct xbitmap_node, bn_rbnode)) 65 66 /* Clear a range of this bitmap. */ 67 int 68 xbitmap_clear( 69 struct xbitmap *bitmap, 70 uint64_t start, 71 uint64_t len) 72 { 73 struct xbitmap_node *bn; 74 struct xbitmap_node *new_bn; 75 uint64_t last = start + len - 1; 76 77 while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last))) { 78 if (bn->bn_start < start && bn->bn_last > last) { 79 uint64_t old_last = bn->bn_last; 80 81 /* overlaps with the entire clearing range */ 82 xbitmap_tree_remove(bn, &bitmap->xb_root); 83 bn->bn_last = start - 1; 84 xbitmap_tree_insert(bn, &bitmap->xb_root); 85 86 /* add an extent */ 87 new_bn = kmalloc(sizeof(struct xbitmap_node), 88 XCHK_GFP_FLAGS); 89 if (!new_bn) 90 return -ENOMEM; 91 new_bn->bn_start = last + 1; 92 new_bn->bn_last = old_last; 93 xbitmap_tree_insert(new_bn, &bitmap->xb_root); 94 } else if (bn->bn_start < start) { 95 /* overlaps with the left side of the clearing range */ 96 xbitmap_tree_remove(bn, &bitmap->xb_root); 97 bn->bn_last = start - 1; 98 xbitmap_tree_insert(bn, &bitmap->xb_root); 99 } else if (bn->bn_last > last) { 100 /* overlaps with the right side of the clearing range */ 101 xbitmap_tree_remove(bn, &bitmap->xb_root); 102 bn->bn_start = last + 1; 103 xbitmap_tree_insert(bn, &bitmap->xb_root); 104 break; 105 } else { 106 /* in the middle of the clearing range */ 107 xbitmap_tree_remove(bn, &bitmap->xb_root); 108 kfree(bn); 109 } 110 } 111 112 return 0; 113 } 114 115 /* Set a range of this bitmap. */ 116 int 117 xbitmap_set( 118 struct xbitmap *bitmap, 119 uint64_t start, 120 uint64_t len) 121 { 122 struct xbitmap_node *left; 123 struct xbitmap_node *right; 124 uint64_t last = start + len - 1; 125 int error; 126 127 /* Is this whole range already set? */ 128 left = xbitmap_tree_iter_first(&bitmap->xb_root, start, last); 129 if (left && left->bn_start <= start && left->bn_last >= last) 130 return 0; 131 132 /* Clear out everything in the range we want to set. */ 133 error = xbitmap_clear(bitmap, start, len); 134 if (error) 135 return error; 136 137 /* Do we have a left-adjacent extent? */ 138 left = xbitmap_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); 139 ASSERT(!left || left->bn_last + 1 == start); 140 141 /* Do we have a right-adjacent extent? */ 142 right = xbitmap_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); 143 ASSERT(!right || right->bn_start == last + 1); 144 145 if (left && right) { 146 /* combine left and right adjacent extent */ 147 xbitmap_tree_remove(left, &bitmap->xb_root); 148 xbitmap_tree_remove(right, &bitmap->xb_root); 149 left->bn_last = right->bn_last; 150 xbitmap_tree_insert(left, &bitmap->xb_root); 151 kfree(right); 152 } else if (left) { 153 /* combine with left extent */ 154 xbitmap_tree_remove(left, &bitmap->xb_root); 155 left->bn_last = last; 156 xbitmap_tree_insert(left, &bitmap->xb_root); 157 } else if (right) { 158 /* combine with right extent */ 159 xbitmap_tree_remove(right, &bitmap->xb_root); 160 right->bn_start = start; 161 xbitmap_tree_insert(right, &bitmap->xb_root); 162 } else { 163 /* add an extent */ 164 left = kmalloc(sizeof(struct xbitmap_node), XCHK_GFP_FLAGS); 165 if (!left) 166 return -ENOMEM; 167 left->bn_start = start; 168 left->bn_last = last; 169 xbitmap_tree_insert(left, &bitmap->xb_root); 170 } 171 172 return 0; 173 } 174 175 /* Free everything related to this bitmap. */ 176 void 177 xbitmap_destroy( 178 struct xbitmap *bitmap) 179 { 180 struct xbitmap_node *bn; 181 182 while ((bn = xbitmap_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) { 183 xbitmap_tree_remove(bn, &bitmap->xb_root); 184 kfree(bn); 185 } 186 } 187 188 /* Set up a per-AG block bitmap. */ 189 void 190 xbitmap_init( 191 struct xbitmap *bitmap) 192 { 193 bitmap->xb_root = RB_ROOT_CACHED; 194 } 195 196 /* 197 * Remove all the blocks mentioned in @sub from the extents in @bitmap. 198 * 199 * The intent is that callers will iterate the rmapbt for all of its records 200 * for a given owner to generate @bitmap; and iterate all the blocks of the 201 * metadata structures that are not being rebuilt and have the same rmapbt 202 * owner to generate @sub. This routine subtracts all the extents 203 * mentioned in sub from all the extents linked in @bitmap, which leaves 204 * @bitmap as the list of blocks that are not accounted for, which we assume 205 * are the dead blocks of the old metadata structure. The blocks mentioned in 206 * @bitmap can be reaped. 207 * 208 * This is the logical equivalent of bitmap &= ~sub. 209 */ 210 int 211 xbitmap_disunion( 212 struct xbitmap *bitmap, 213 struct xbitmap *sub) 214 { 215 struct xbitmap_node *bn; 216 int error; 217 218 if (xbitmap_empty(bitmap) || xbitmap_empty(sub)) 219 return 0; 220 221 for_each_xbitmap_extent(bn, sub) { 222 error = xbitmap_clear(bitmap, bn->bn_start, 223 bn->bn_last - bn->bn_start + 1); 224 if (error) 225 return error; 226 } 227 228 return 0; 229 } 230 231 /* 232 * Record all btree blocks seen while iterating all records of a btree. 233 * 234 * We know that the btree query_all function starts at the left edge and walks 235 * towards the right edge of the tree. Therefore, we know that we can walk up 236 * the btree cursor towards the root; if the pointer for a given level points 237 * to the first record/key in that block, we haven't seen this block before; 238 * and therefore we need to remember that we saw this block in the btree. 239 * 240 * So if our btree is: 241 * 242 * 4 243 * / | \ 244 * 1 2 3 245 * 246 * Pretend for this example that each leaf block has 100 btree records. For 247 * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we 248 * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so 249 * we record block 4. The list is [1, 4]. 250 * 251 * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit 252 * the loop. The list remains [1, 4]. 253 * 254 * For the 101st btree record, we've moved onto leaf block 2. Now 255 * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that 256 * bc_levels[1].ptr == 2, so we exit the loop. The list is now [1, 4, 2]. 257 * 258 * For the 102nd record, bc_levels[0].ptr == 2, so we continue. 259 * 260 * For the 201st record, we've moved on to leaf block 3. 261 * bc_levels[0].ptr == 1, so we add 3 to the list. Now it is [1, 4, 2, 3]. 262 * 263 * For the 300th record we just exit, with the list being [1, 4, 2, 3]. 264 */ 265 266 /* Mark a btree block to the agblock bitmap. */ 267 STATIC int 268 xagb_bitmap_visit_btblock( 269 struct xfs_btree_cur *cur, 270 int level, 271 void *priv) 272 { 273 struct xagb_bitmap *bitmap = priv; 274 struct xfs_buf *bp; 275 xfs_fsblock_t fsbno; 276 xfs_agblock_t agbno; 277 278 xfs_btree_get_block(cur, level, &bp); 279 if (!bp) 280 return 0; 281 282 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp)); 283 agbno = XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno); 284 285 return xagb_bitmap_set(bitmap, agbno, 1); 286 } 287 288 /* Mark all (per-AG) btree blocks in the agblock bitmap. */ 289 int 290 xagb_bitmap_set_btblocks( 291 struct xagb_bitmap *bitmap, 292 struct xfs_btree_cur *cur) 293 { 294 return xfs_btree_visit_blocks(cur, xagb_bitmap_visit_btblock, 295 XFS_BTREE_VISIT_ALL, bitmap); 296 } 297 298 /* 299 * Record all the buffers pointed to by the btree cursor. Callers already 300 * engaged in a btree walk should call this function to capture the list of 301 * blocks going from the leaf towards the root. 302 */ 303 int 304 xbitmap_set_btcur_path( 305 struct xbitmap *bitmap, 306 struct xfs_btree_cur *cur) 307 { 308 struct xfs_buf *bp; 309 xfs_fsblock_t fsb; 310 int i; 311 int error; 312 313 for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) { 314 xfs_btree_get_block(cur, i, &bp); 315 if (!bp) 316 continue; 317 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp)); 318 error = xbitmap_set(bitmap, fsb, 1); 319 if (error) 320 return error; 321 } 322 323 return 0; 324 } 325 326 /* Collect a btree's block in the bitmap. */ 327 STATIC int 328 xbitmap_collect_btblock( 329 struct xfs_btree_cur *cur, 330 int level, 331 void *priv) 332 { 333 struct xbitmap *bitmap = priv; 334 struct xfs_buf *bp; 335 xfs_fsblock_t fsbno; 336 337 xfs_btree_get_block(cur, level, &bp); 338 if (!bp) 339 return 0; 340 341 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp)); 342 return xbitmap_set(bitmap, fsbno, 1); 343 } 344 345 /* Walk the btree and mark the bitmap wherever a btree block is found. */ 346 int 347 xbitmap_set_btblocks( 348 struct xbitmap *bitmap, 349 struct xfs_btree_cur *cur) 350 { 351 return xfs_btree_visit_blocks(cur, xbitmap_collect_btblock, 352 XFS_BTREE_VISIT_ALL, bitmap); 353 } 354 355 /* How many bits are set in this bitmap? */ 356 uint64_t 357 xbitmap_hweight( 358 struct xbitmap *bitmap) 359 { 360 struct xbitmap_node *bn; 361 uint64_t ret = 0; 362 363 for_each_xbitmap_extent(bn, bitmap) 364 ret += bn->bn_last - bn->bn_start + 1; 365 366 return ret; 367 } 368 369 /* Call a function for every run of set bits in this bitmap. */ 370 int 371 xbitmap_walk( 372 struct xbitmap *bitmap, 373 xbitmap_walk_fn fn, 374 void *priv) 375 { 376 struct xbitmap_node *bn; 377 int error = 0; 378 379 for_each_xbitmap_extent(bn, bitmap) { 380 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv); 381 if (error) 382 break; 383 } 384 385 return error; 386 } 387 388 struct xbitmap_walk_bits { 389 xbitmap_walk_bits_fn fn; 390 void *priv; 391 }; 392 393 /* Walk all the bits in a run. */ 394 static int 395 xbitmap_walk_bits_in_run( 396 uint64_t start, 397 uint64_t len, 398 void *priv) 399 { 400 struct xbitmap_walk_bits *wb = priv; 401 uint64_t i; 402 int error = 0; 403 404 for (i = start; i < start + len; i++) { 405 error = wb->fn(i, wb->priv); 406 if (error) 407 break; 408 } 409 410 return error; 411 } 412 413 /* Call a function for every set bit in this bitmap. */ 414 int 415 xbitmap_walk_bits( 416 struct xbitmap *bitmap, 417 xbitmap_walk_bits_fn fn, 418 void *priv) 419 { 420 struct xbitmap_walk_bits wb = {.fn = fn, .priv = priv}; 421 422 return xbitmap_walk(bitmap, xbitmap_walk_bits_in_run, &wb); 423 } 424 425 /* Does this bitmap have no bits set at all? */ 426 bool 427 xbitmap_empty( 428 struct xbitmap *bitmap) 429 { 430 return bitmap->xb_root.rb_root.rb_node == NULL; 431 } 432 433 /* Is the start of the range set or clear? And for how long? */ 434 bool 435 xbitmap_test( 436 struct xbitmap *bitmap, 437 uint64_t start, 438 uint64_t *len) 439 { 440 struct xbitmap_node *bn; 441 uint64_t last = start + *len - 1; 442 443 bn = xbitmap_tree_iter_first(&bitmap->xb_root, start, last); 444 if (!bn) 445 return false; 446 if (bn->bn_start <= start) { 447 if (bn->bn_last < last) 448 *len = bn->bn_last - start + 1; 449 return true; 450 } 451 *len = bn->bn_start - start; 452 return false; 453 } 454