1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Copyright (c) 2022-2024 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_format.h" 10 #include "xfs_trans_resv.h" 11 #include "xfs_mount.h" 12 #include "xfs_defer.h" 13 #include "xfs_btree.h" 14 #include "xfs_buf_mem.h" 15 #include "xfs_btree_mem.h" 16 #include "xfs_error.h" 17 #include "scrub/rcbag_btree.h" 18 #include "scrub/trace.h" 19 20 static struct kmem_cache *rcbagbt_cur_cache; 21 22 STATIC void 23 rcbagbt_init_key_from_rec( 24 union xfs_btree_key *key, 25 const union xfs_btree_rec *rec) 26 { 27 struct rcbag_key *bag_key = (struct rcbag_key *)key; 28 const struct rcbag_rec *bag_rec = (const struct rcbag_rec *)rec; 29 30 BUILD_BUG_ON(sizeof(struct rcbag_key) > sizeof(union xfs_btree_key)); 31 BUILD_BUG_ON(sizeof(struct rcbag_rec) > sizeof(union xfs_btree_rec)); 32 33 bag_key->rbg_startblock = bag_rec->rbg_startblock; 34 bag_key->rbg_blockcount = bag_rec->rbg_blockcount; 35 } 36 37 STATIC void 38 rcbagbt_init_rec_from_cur( 39 struct xfs_btree_cur *cur, 40 union xfs_btree_rec *rec) 41 { 42 struct rcbag_rec *bag_rec = (struct rcbag_rec *)rec; 43 struct rcbag_rec *bag_irec = (struct rcbag_rec *)&cur->bc_rec; 44 45 bag_rec->rbg_startblock = bag_irec->rbg_startblock; 46 bag_rec->rbg_blockcount = bag_irec->rbg_blockcount; 47 bag_rec->rbg_refcount = bag_irec->rbg_refcount; 48 } 49 50 STATIC int64_t 51 rcbagbt_key_diff( 52 struct xfs_btree_cur *cur, 53 const union xfs_btree_key *key) 54 { 55 struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; 56 const struct rcbag_key *kp = (const struct rcbag_key *)key; 57 58 if (kp->rbg_startblock > rec->rbg_startblock) 59 return 1; 60 if (kp->rbg_startblock < rec->rbg_startblock) 61 return -1; 62 63 if (kp->rbg_blockcount > rec->rbg_blockcount) 64 return 1; 65 if (kp->rbg_blockcount < rec->rbg_blockcount) 66 return -1; 67 68 return 0; 69 } 70 71 STATIC int64_t 72 rcbagbt_diff_two_keys( 73 struct xfs_btree_cur *cur, 74 const union xfs_btree_key *k1, 75 const union xfs_btree_key *k2, 76 const union xfs_btree_key *mask) 77 { 78 const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; 79 const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; 80 81 ASSERT(mask == NULL); 82 83 if (kp1->rbg_startblock > kp2->rbg_startblock) 84 return 1; 85 if (kp1->rbg_startblock < kp2->rbg_startblock) 86 return -1; 87 88 if (kp1->rbg_blockcount > kp2->rbg_blockcount) 89 return 1; 90 if (kp1->rbg_blockcount < kp2->rbg_blockcount) 91 return -1; 92 93 return 0; 94 } 95 96 STATIC int 97 rcbagbt_keys_inorder( 98 struct xfs_btree_cur *cur, 99 const union xfs_btree_key *k1, 100 const union xfs_btree_key *k2) 101 { 102 const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; 103 const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; 104 105 if (kp1->rbg_startblock > kp2->rbg_startblock) 106 return 0; 107 if (kp1->rbg_startblock < kp2->rbg_startblock) 108 return 1; 109 110 if (kp1->rbg_blockcount > kp2->rbg_blockcount) 111 return 0; 112 if (kp1->rbg_blockcount < kp2->rbg_blockcount) 113 return 1; 114 115 return 0; 116 } 117 118 STATIC int 119 rcbagbt_recs_inorder( 120 struct xfs_btree_cur *cur, 121 const union xfs_btree_rec *r1, 122 const union xfs_btree_rec *r2) 123 { 124 const struct rcbag_rec *rp1 = (const struct rcbag_rec *)r1; 125 const struct rcbag_rec *rp2 = (const struct rcbag_rec *)r2; 126 127 if (rp1->rbg_startblock > rp2->rbg_startblock) 128 return 0; 129 if (rp1->rbg_startblock < rp2->rbg_startblock) 130 return 1; 131 132 if (rp1->rbg_blockcount > rp2->rbg_blockcount) 133 return 0; 134 if (rp1->rbg_blockcount < rp2->rbg_blockcount) 135 return 1; 136 137 return 0; 138 } 139 140 static xfs_failaddr_t 141 rcbagbt_verify( 142 struct xfs_buf *bp) 143 { 144 struct xfs_mount *mp = bp->b_mount; 145 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 146 xfs_failaddr_t fa; 147 unsigned int level; 148 unsigned int maxrecs; 149 150 if (!xfs_verify_magic(bp, block->bb_magic)) 151 return __this_address; 152 153 fa = xfs_btree_fsblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN); 154 if (fa) 155 return fa; 156 157 level = be16_to_cpu(block->bb_level); 158 if (level >= rcbagbt_maxlevels_possible()) 159 return __this_address; 160 161 maxrecs = rcbagbt_maxrecs(mp, XFBNO_BLOCKSIZE, level == 0); 162 return xfs_btree_memblock_verify(bp, maxrecs); 163 } 164 165 static void 166 rcbagbt_rw_verify( 167 struct xfs_buf *bp) 168 { 169 xfs_failaddr_t fa = rcbagbt_verify(bp); 170 171 if (fa) 172 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 173 } 174 175 /* skip crc checks on in-memory btrees to save time */ 176 static const struct xfs_buf_ops rcbagbt_mem_buf_ops = { 177 .name = "rcbagbt_mem", 178 .magic = { 0, cpu_to_be32(RCBAG_MAGIC) }, 179 .verify_read = rcbagbt_rw_verify, 180 .verify_write = rcbagbt_rw_verify, 181 .verify_struct = rcbagbt_verify, 182 }; 183 184 static const struct xfs_btree_ops rcbagbt_mem_ops = { 185 .name = "rcbag", 186 .type = XFS_BTREE_TYPE_MEM, 187 188 .rec_len = sizeof(struct rcbag_rec), 189 .key_len = sizeof(struct rcbag_key), 190 .ptr_len = XFS_BTREE_LONG_PTR_LEN, 191 192 .lru_refs = 1, 193 .statoff = XFS_STATS_CALC_INDEX(xs_rcbag_2), 194 195 .dup_cursor = xfbtree_dup_cursor, 196 .set_root = xfbtree_set_root, 197 .alloc_block = xfbtree_alloc_block, 198 .free_block = xfbtree_free_block, 199 .get_minrecs = xfbtree_get_minrecs, 200 .get_maxrecs = xfbtree_get_maxrecs, 201 .init_key_from_rec = rcbagbt_init_key_from_rec, 202 .init_rec_from_cur = rcbagbt_init_rec_from_cur, 203 .init_ptr_from_cur = xfbtree_init_ptr_from_cur, 204 .key_diff = rcbagbt_key_diff, 205 .buf_ops = &rcbagbt_mem_buf_ops, 206 .diff_two_keys = rcbagbt_diff_two_keys, 207 .keys_inorder = rcbagbt_keys_inorder, 208 .recs_inorder = rcbagbt_recs_inorder, 209 }; 210 211 /* Create a cursor for an in-memory btree. */ 212 struct xfs_btree_cur * 213 rcbagbt_mem_cursor( 214 struct xfs_mount *mp, 215 struct xfs_trans *tp, 216 struct xfbtree *xfbtree) 217 { 218 struct xfs_btree_cur *cur; 219 220 cur = xfs_btree_alloc_cursor(mp, tp, &rcbagbt_mem_ops, 221 rcbagbt_maxlevels_possible(), rcbagbt_cur_cache); 222 223 cur->bc_mem.xfbtree = xfbtree; 224 cur->bc_nlevels = xfbtree->nlevels; 225 return cur; 226 } 227 228 /* Create an in-memory refcount bag btree. */ 229 int 230 rcbagbt_mem_init( 231 struct xfs_mount *mp, 232 struct xfbtree *xfbt, 233 struct xfs_buftarg *btp) 234 { 235 xfbt->owner = 0; 236 return xfbtree_init(mp, xfbt, btp, &rcbagbt_mem_ops); 237 } 238 239 /* Calculate number of records in a refcount bag btree block. */ 240 static inline unsigned int 241 rcbagbt_block_maxrecs( 242 unsigned int blocklen, 243 bool leaf) 244 { 245 if (leaf) 246 return blocklen / sizeof(struct rcbag_rec); 247 return blocklen / 248 (sizeof(struct rcbag_key) + sizeof(rcbag_ptr_t)); 249 } 250 251 /* 252 * Calculate number of records in an refcount bag btree block. 253 */ 254 unsigned int 255 rcbagbt_maxrecs( 256 struct xfs_mount *mp, 257 unsigned int blocklen, 258 bool leaf) 259 { 260 blocklen -= RCBAG_BLOCK_LEN; 261 return rcbagbt_block_maxrecs(blocklen, leaf); 262 } 263 264 /* Compute the max possible height for refcount bag btrees. */ 265 unsigned int 266 rcbagbt_maxlevels_possible(void) 267 { 268 unsigned int minrecs[2]; 269 unsigned int blocklen; 270 271 blocklen = XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN; 272 273 minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; 274 minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; 275 276 return xfs_btree_space_to_height(minrecs, ULLONG_MAX); 277 } 278 279 /* Calculate the refcount bag btree size for some records. */ 280 unsigned long long 281 rcbagbt_calc_size( 282 unsigned long long nr_records) 283 { 284 unsigned int minrecs[2]; 285 unsigned int blocklen; 286 287 blocklen = XFBNO_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN; 288 289 minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; 290 minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; 291 292 return xfs_btree_calc_size(minrecs, nr_records); 293 } 294 295 int __init 296 rcbagbt_init_cur_cache(void) 297 { 298 rcbagbt_cur_cache = kmem_cache_create("xfs_rcbagbt_cur", 299 xfs_btree_cur_sizeof(rcbagbt_maxlevels_possible()), 300 0, 0, NULL); 301 302 if (!rcbagbt_cur_cache) 303 return -ENOMEM; 304 return 0; 305 } 306 307 void 308 rcbagbt_destroy_cur_cache(void) 309 { 310 kmem_cache_destroy(rcbagbt_cur_cache); 311 rcbagbt_cur_cache = NULL; 312 } 313 314 /* Look up the refcount bag record corresponding to this reverse mapping. */ 315 int 316 rcbagbt_lookup_eq( 317 struct xfs_btree_cur *cur, 318 const struct xfs_rmap_irec *rmap, 319 int *success) 320 { 321 struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; 322 323 rec->rbg_startblock = rmap->rm_startblock; 324 rec->rbg_blockcount = rmap->rm_blockcount; 325 326 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, success); 327 } 328 329 /* Get the data from the pointed-to record. */ 330 int 331 rcbagbt_get_rec( 332 struct xfs_btree_cur *cur, 333 struct rcbag_rec *rec, 334 int *has) 335 { 336 union xfs_btree_rec *btrec; 337 int error; 338 339 error = xfs_btree_get_rec(cur, &btrec, has); 340 if (error || !(*has)) 341 return error; 342 343 memcpy(rec, btrec, sizeof(struct rcbag_rec)); 344 return 0; 345 } 346 347 /* Update the record referred to by cur to the value given. */ 348 int 349 rcbagbt_update( 350 struct xfs_btree_cur *cur, 351 const struct rcbag_rec *rec) 352 { 353 union xfs_btree_rec btrec; 354 355 memcpy(&btrec, rec, sizeof(struct rcbag_rec)); 356 return xfs_btree_update(cur, &btrec); 357 } 358 359 /* Update the record referred to by cur to the value given. */ 360 int 361 rcbagbt_insert( 362 struct xfs_btree_cur *cur, 363 const struct rcbag_rec *rec, 364 int *success) 365 { 366 struct rcbag_rec *btrec = (struct rcbag_rec *)&cur->bc_rec; 367 368 memcpy(btrec, rec, sizeof(struct rcbag_rec)); 369 return xfs_btree_insert(cur, success); 370 } 371