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 20static struct kmem_cache *rcbagbt_cur_cache; 21 22STATIC void 23rcbagbt_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 37STATIC void 38rcbagbt_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 50STATIC int64_t 51rcbagbt_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 71STATIC int64_t 72rcbagbt_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 96STATIC int 97rcbagbt_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 118STATIC int 119rcbagbt_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 140static xfs_failaddr_t 141rcbagbt_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 165static void 166rcbagbt_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 */ 176static 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 184static 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. */ 212struct xfs_btree_cur * 213rcbagbt_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. */ 229int 230rcbagbt_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. */ 240static inline unsigned int 241rcbagbt_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 */ 254unsigned int 255rcbagbt_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. */ 265unsigned int 266rcbagbt_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. */ 280unsigned long long 281rcbagbt_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 295int __init 296rcbagbt_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 307void 308rcbagbt_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. */ 315int 316rcbagbt_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. */ 330int 331rcbagbt_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. */ 348int 349rcbagbt_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. */ 360int 361rcbagbt_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