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