fs/xfs/scrub/rcbag_btree.c

   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 }