1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2014 Red Hat, Inc. 4 * All Rights Reserved. 5 */ 6 #include "xfs.h" 7 #include "xfs_fs.h" 8 #include "xfs_shared.h" 9 #include "xfs_format.h" 10 #include "xfs_log_format.h" 11 #include "xfs_trans_resv.h" 12 #include "xfs_mount.h" 13 #include "xfs_trans.h" 14 #include "xfs_alloc.h" 15 #include "xfs_btree.h" 16 #include "xfs_btree_staging.h" 17 #include "xfs_rmap.h" 18 #include "xfs_rmap_btree.h" 19 #include "xfs_trace.h" 20 #include "xfs_error.h" 21 #include "xfs_extent_busy.h" 22 #include "xfs_ag.h" 23 #include "xfs_ag_resv.h" 24 25 static struct kmem_cache *xfs_rmapbt_cur_cache; 26 27 /* 28 * Reverse map btree. 29 * 30 * This is a per-ag tree used to track the owner(s) of a given extent. With 31 * reflink it is possible for there to be multiple owners, which is a departure 32 * from classic XFS. Owner records for data extents are inserted when the 33 * extent is mapped and removed when an extent is unmapped. Owner records for 34 * all other block types (i.e. metadata) are inserted when an extent is 35 * allocated and removed when an extent is freed. There can only be one owner 36 * of a metadata extent, usually an inode or some other metadata structure like 37 * an AG btree. 38 * 39 * The rmap btree is part of the free space management, so blocks for the tree 40 * are sourced from the agfl. Hence we need transaction reservation support for 41 * this tree so that the freelist is always large enough. This also impacts on 42 * the minimum space we need to leave free in the AG. 43 * 44 * The tree is ordered by [ag block, owner, offset]. This is a large key size, 45 * but it is the only way to enforce unique keys when a block can be owned by 46 * multiple files at any offset. There's no need to order/search by extent 47 * size for online updating/management of the tree. It is intended that most 48 * reverse lookups will be to find the owner(s) of a particular block, or to 49 * try to recover tree and file data from corrupt primary metadata. 50 */ 51 52 static struct xfs_btree_cur * 53 xfs_rmapbt_dup_cursor( 54 struct xfs_btree_cur *cur) 55 { 56 return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp, 57 cur->bc_ag.agbp, cur->bc_ag.pag); 58 } 59 60 STATIC void 61 xfs_rmapbt_set_root( 62 struct xfs_btree_cur *cur, 63 const union xfs_btree_ptr *ptr, 64 int inc) 65 { 66 struct xfs_buf *agbp = cur->bc_ag.agbp; 67 struct xfs_agf *agf = agbp->b_addr; 68 int btnum = cur->bc_btnum; 69 70 ASSERT(ptr->s != 0); 71 72 agf->agf_roots[btnum] = ptr->s; 73 be32_add_cpu(&agf->agf_levels[btnum], inc); 74 cur->bc_ag.pag->pagf_levels[btnum] += inc; 75 76 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 77 } 78 79 STATIC int 80 xfs_rmapbt_alloc_block( 81 struct xfs_btree_cur *cur, 82 const union xfs_btree_ptr *start, 83 union xfs_btree_ptr *new, 84 int *stat) 85 { 86 struct xfs_buf *agbp = cur->bc_ag.agbp; 87 struct xfs_agf *agf = agbp->b_addr; 88 struct xfs_perag *pag = cur->bc_ag.pag; 89 int error; 90 xfs_agblock_t bno; 91 92 /* Allocate the new block from the freelist. If we can't, give up. */ 93 error = xfs_alloc_get_freelist(pag, cur->bc_tp, cur->bc_ag.agbp, 94 &bno, 1); 95 if (error) 96 return error; 97 98 trace_xfs_rmapbt_alloc_block(cur->bc_mp, pag->pag_agno, bno, 1); 99 if (bno == NULLAGBLOCK) { 100 *stat = 0; 101 return 0; 102 } 103 104 xfs_extent_busy_reuse(cur->bc_mp, pag, bno, 1, false); 105 106 new->s = cpu_to_be32(bno); 107 be32_add_cpu(&agf->agf_rmap_blocks, 1); 108 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS); 109 110 xfs_ag_resv_rmapbt_alloc(cur->bc_mp, pag->pag_agno); 111 112 *stat = 1; 113 return 0; 114 } 115 116 STATIC int 117 xfs_rmapbt_free_block( 118 struct xfs_btree_cur *cur, 119 struct xfs_buf *bp) 120 { 121 struct xfs_buf *agbp = cur->bc_ag.agbp; 122 struct xfs_agf *agf = agbp->b_addr; 123 struct xfs_perag *pag = cur->bc_ag.pag; 124 xfs_agblock_t bno; 125 int error; 126 127 bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp)); 128 trace_xfs_rmapbt_free_block(cur->bc_mp, pag->pag_agno, 129 bno, 1); 130 be32_add_cpu(&agf->agf_rmap_blocks, -1); 131 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_RMAP_BLOCKS); 132 error = xfs_alloc_put_freelist(pag, cur->bc_tp, agbp, NULL, bno, 1); 133 if (error) 134 return error; 135 136 xfs_extent_busy_insert(cur->bc_tp, pag, bno, 1, 137 XFS_EXTENT_BUSY_SKIP_DISCARD); 138 139 xfs_ag_resv_free_extent(pag, XFS_AG_RESV_RMAPBT, NULL, 1); 140 return 0; 141 } 142 143 STATIC int 144 xfs_rmapbt_get_minrecs( 145 struct xfs_btree_cur *cur, 146 int level) 147 { 148 return cur->bc_mp->m_rmap_mnr[level != 0]; 149 } 150 151 STATIC int 152 xfs_rmapbt_get_maxrecs( 153 struct xfs_btree_cur *cur, 154 int level) 155 { 156 return cur->bc_mp->m_rmap_mxr[level != 0]; 157 } 158 159 /* 160 * Convert the ondisk record's offset field into the ondisk key's offset field. 161 * Fork and bmbt are significant parts of the rmap record key, but written 162 * status is merely a record attribute. 163 */ 164 static inline __be64 ondisk_rec_offset_to_key(const union xfs_btree_rec *rec) 165 { 166 return rec->rmap.rm_offset & ~cpu_to_be64(XFS_RMAP_OFF_UNWRITTEN); 167 } 168 169 STATIC void 170 xfs_rmapbt_init_key_from_rec( 171 union xfs_btree_key *key, 172 const union xfs_btree_rec *rec) 173 { 174 key->rmap.rm_startblock = rec->rmap.rm_startblock; 175 key->rmap.rm_owner = rec->rmap.rm_owner; 176 key->rmap.rm_offset = ondisk_rec_offset_to_key(rec); 177 } 178 179 /* 180 * The high key for a reverse mapping record can be computed by shifting 181 * the startblock and offset to the highest value that would still map 182 * to that record. In practice this means that we add blockcount-1 to 183 * the startblock for all records, and if the record is for a data/attr 184 * fork mapping, we add blockcount-1 to the offset too. 185 */ 186 STATIC void 187 xfs_rmapbt_init_high_key_from_rec( 188 union xfs_btree_key *key, 189 const union xfs_btree_rec *rec) 190 { 191 uint64_t off; 192 int adj; 193 194 adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1; 195 196 key->rmap.rm_startblock = rec->rmap.rm_startblock; 197 be32_add_cpu(&key->rmap.rm_startblock, adj); 198 key->rmap.rm_owner = rec->rmap.rm_owner; 199 key->rmap.rm_offset = ondisk_rec_offset_to_key(rec); 200 if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) || 201 XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset))) 202 return; 203 off = be64_to_cpu(key->rmap.rm_offset); 204 off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK); 205 key->rmap.rm_offset = cpu_to_be64(off); 206 } 207 208 STATIC void 209 xfs_rmapbt_init_rec_from_cur( 210 struct xfs_btree_cur *cur, 211 union xfs_btree_rec *rec) 212 { 213 rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock); 214 rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount); 215 rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner); 216 rec->rmap.rm_offset = cpu_to_be64( 217 xfs_rmap_irec_offset_pack(&cur->bc_rec.r)); 218 } 219 220 STATIC void 221 xfs_rmapbt_init_ptr_from_cur( 222 struct xfs_btree_cur *cur, 223 union xfs_btree_ptr *ptr) 224 { 225 struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 226 227 ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno)); 228 229 ptr->s = agf->agf_roots[cur->bc_btnum]; 230 } 231 232 /* 233 * Mask the appropriate parts of the ondisk key field for a key comparison. 234 * Fork and bmbt are significant parts of the rmap record key, but written 235 * status is merely a record attribute. 236 */ 237 static inline uint64_t offset_keymask(uint64_t offset) 238 { 239 return offset & ~XFS_RMAP_OFF_UNWRITTEN; 240 } 241 242 STATIC int64_t 243 xfs_rmapbt_key_diff( 244 struct xfs_btree_cur *cur, 245 const union xfs_btree_key *key) 246 { 247 struct xfs_rmap_irec *rec = &cur->bc_rec.r; 248 const struct xfs_rmap_key *kp = &key->rmap; 249 __u64 x, y; 250 int64_t d; 251 252 d = (int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock; 253 if (d) 254 return d; 255 256 x = be64_to_cpu(kp->rm_owner); 257 y = rec->rm_owner; 258 if (x > y) 259 return 1; 260 else if (y > x) 261 return -1; 262 263 x = offset_keymask(be64_to_cpu(kp->rm_offset)); 264 y = offset_keymask(xfs_rmap_irec_offset_pack(rec)); 265 if (x > y) 266 return 1; 267 else if (y > x) 268 return -1; 269 return 0; 270 } 271 272 STATIC int64_t 273 xfs_rmapbt_diff_two_keys( 274 struct xfs_btree_cur *cur, 275 const union xfs_btree_key *k1, 276 const union xfs_btree_key *k2) 277 { 278 const struct xfs_rmap_key *kp1 = &k1->rmap; 279 const struct xfs_rmap_key *kp2 = &k2->rmap; 280 int64_t d; 281 __u64 x, y; 282 283 d = (int64_t)be32_to_cpu(kp1->rm_startblock) - 284 be32_to_cpu(kp2->rm_startblock); 285 if (d) 286 return d; 287 288 x = be64_to_cpu(kp1->rm_owner); 289 y = be64_to_cpu(kp2->rm_owner); 290 if (x > y) 291 return 1; 292 else if (y > x) 293 return -1; 294 295 x = offset_keymask(be64_to_cpu(kp1->rm_offset)); 296 y = offset_keymask(be64_to_cpu(kp2->rm_offset)); 297 if (x > y) 298 return 1; 299 else if (y > x) 300 return -1; 301 return 0; 302 } 303 304 static xfs_failaddr_t 305 xfs_rmapbt_verify( 306 struct xfs_buf *bp) 307 { 308 struct xfs_mount *mp = bp->b_mount; 309 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 310 struct xfs_perag *pag = bp->b_pag; 311 xfs_failaddr_t fa; 312 unsigned int level; 313 314 /* 315 * magic number and level verification 316 * 317 * During growfs operations, we can't verify the exact level or owner as 318 * the perag is not fully initialised and hence not attached to the 319 * buffer. In this case, check against the maximum tree depth. 320 * 321 * Similarly, during log recovery we will have a perag structure 322 * attached, but the agf information will not yet have been initialised 323 * from the on disk AGF. Again, we can only check against maximum limits 324 * in this case. 325 */ 326 if (!xfs_verify_magic(bp, block->bb_magic)) 327 return __this_address; 328 329 if (!xfs_has_rmapbt(mp)) 330 return __this_address; 331 fa = xfs_btree_sblock_v5hdr_verify(bp); 332 if (fa) 333 return fa; 334 335 level = be16_to_cpu(block->bb_level); 336 if (pag && xfs_perag_initialised_agf(pag)) { 337 if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi]) 338 return __this_address; 339 } else if (level >= mp->m_rmap_maxlevels) 340 return __this_address; 341 342 return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]); 343 } 344 345 static void 346 xfs_rmapbt_read_verify( 347 struct xfs_buf *bp) 348 { 349 xfs_failaddr_t fa; 350 351 if (!xfs_btree_sblock_verify_crc(bp)) 352 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 353 else { 354 fa = xfs_rmapbt_verify(bp); 355 if (fa) 356 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 357 } 358 359 if (bp->b_error) 360 trace_xfs_btree_corrupt(bp, _RET_IP_); 361 } 362 363 static void 364 xfs_rmapbt_write_verify( 365 struct xfs_buf *bp) 366 { 367 xfs_failaddr_t fa; 368 369 fa = xfs_rmapbt_verify(bp); 370 if (fa) { 371 trace_xfs_btree_corrupt(bp, _RET_IP_); 372 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 373 return; 374 } 375 xfs_btree_sblock_calc_crc(bp); 376 377 } 378 379 const struct xfs_buf_ops xfs_rmapbt_buf_ops = { 380 .name = "xfs_rmapbt", 381 .magic = { 0, cpu_to_be32(XFS_RMAP_CRC_MAGIC) }, 382 .verify_read = xfs_rmapbt_read_verify, 383 .verify_write = xfs_rmapbt_write_verify, 384 .verify_struct = xfs_rmapbt_verify, 385 }; 386 387 STATIC int 388 xfs_rmapbt_keys_inorder( 389 struct xfs_btree_cur *cur, 390 const union xfs_btree_key *k1, 391 const union xfs_btree_key *k2) 392 { 393 uint32_t x; 394 uint32_t y; 395 uint64_t a; 396 uint64_t b; 397 398 x = be32_to_cpu(k1->rmap.rm_startblock); 399 y = be32_to_cpu(k2->rmap.rm_startblock); 400 if (x < y) 401 return 1; 402 else if (x > y) 403 return 0; 404 a = be64_to_cpu(k1->rmap.rm_owner); 405 b = be64_to_cpu(k2->rmap.rm_owner); 406 if (a < b) 407 return 1; 408 else if (a > b) 409 return 0; 410 a = offset_keymask(be64_to_cpu(k1->rmap.rm_offset)); 411 b = offset_keymask(be64_to_cpu(k2->rmap.rm_offset)); 412 if (a <= b) 413 return 1; 414 return 0; 415 } 416 417 STATIC int 418 xfs_rmapbt_recs_inorder( 419 struct xfs_btree_cur *cur, 420 const union xfs_btree_rec *r1, 421 const union xfs_btree_rec *r2) 422 { 423 uint32_t x; 424 uint32_t y; 425 uint64_t a; 426 uint64_t b; 427 428 x = be32_to_cpu(r1->rmap.rm_startblock); 429 y = be32_to_cpu(r2->rmap.rm_startblock); 430 if (x < y) 431 return 1; 432 else if (x > y) 433 return 0; 434 a = be64_to_cpu(r1->rmap.rm_owner); 435 b = be64_to_cpu(r2->rmap.rm_owner); 436 if (a < b) 437 return 1; 438 else if (a > b) 439 return 0; 440 a = offset_keymask(be64_to_cpu(r1->rmap.rm_offset)); 441 b = offset_keymask(be64_to_cpu(r2->rmap.rm_offset)); 442 if (a <= b) 443 return 1; 444 return 0; 445 } 446 447 STATIC enum xbtree_key_contig 448 xfs_rmapbt_keys_contiguous( 449 struct xfs_btree_cur *cur, 450 const union xfs_btree_key *key1, 451 const union xfs_btree_key *key2) 452 { 453 /* 454 * We only support checking contiguity of the physical space component. 455 * If any callers ever need more specificity than that, they'll have to 456 * implement it here. 457 */ 458 return xbtree_key_contig(be32_to_cpu(key1->rmap.rm_startblock), 459 be32_to_cpu(key2->rmap.rm_startblock)); 460 } 461 462 static const struct xfs_btree_ops xfs_rmapbt_ops = { 463 .rec_len = sizeof(struct xfs_rmap_rec), 464 .key_len = 2 * sizeof(struct xfs_rmap_key), 465 466 .dup_cursor = xfs_rmapbt_dup_cursor, 467 .set_root = xfs_rmapbt_set_root, 468 .alloc_block = xfs_rmapbt_alloc_block, 469 .free_block = xfs_rmapbt_free_block, 470 .get_minrecs = xfs_rmapbt_get_minrecs, 471 .get_maxrecs = xfs_rmapbt_get_maxrecs, 472 .init_key_from_rec = xfs_rmapbt_init_key_from_rec, 473 .init_high_key_from_rec = xfs_rmapbt_init_high_key_from_rec, 474 .init_rec_from_cur = xfs_rmapbt_init_rec_from_cur, 475 .init_ptr_from_cur = xfs_rmapbt_init_ptr_from_cur, 476 .key_diff = xfs_rmapbt_key_diff, 477 .buf_ops = &xfs_rmapbt_buf_ops, 478 .diff_two_keys = xfs_rmapbt_diff_two_keys, 479 .keys_inorder = xfs_rmapbt_keys_inorder, 480 .recs_inorder = xfs_rmapbt_recs_inorder, 481 .keys_contiguous = xfs_rmapbt_keys_contiguous, 482 }; 483 484 static struct xfs_btree_cur * 485 xfs_rmapbt_init_common( 486 struct xfs_mount *mp, 487 struct xfs_trans *tp, 488 struct xfs_perag *pag) 489 { 490 struct xfs_btree_cur *cur; 491 492 /* Overlapping btree; 2 keys per pointer. */ 493 cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RMAP, 494 mp->m_rmap_maxlevels, xfs_rmapbt_cur_cache); 495 cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING; 496 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_rmap_2); 497 cur->bc_ops = &xfs_rmapbt_ops; 498 499 cur->bc_ag.pag = xfs_perag_hold(pag); 500 return cur; 501 } 502 503 /* Create a new reverse mapping btree cursor. */ 504 struct xfs_btree_cur * 505 xfs_rmapbt_init_cursor( 506 struct xfs_mount *mp, 507 struct xfs_trans *tp, 508 struct xfs_buf *agbp, 509 struct xfs_perag *pag) 510 { 511 struct xfs_agf *agf = agbp->b_addr; 512 struct xfs_btree_cur *cur; 513 514 cur = xfs_rmapbt_init_common(mp, tp, pag); 515 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]); 516 cur->bc_ag.agbp = agbp; 517 return cur; 518 } 519 520 /* Create a new reverse mapping btree cursor with a fake root for staging. */ 521 struct xfs_btree_cur * 522 xfs_rmapbt_stage_cursor( 523 struct xfs_mount *mp, 524 struct xbtree_afakeroot *afake, 525 struct xfs_perag *pag) 526 { 527 struct xfs_btree_cur *cur; 528 529 cur = xfs_rmapbt_init_common(mp, NULL, pag); 530 xfs_btree_stage_afakeroot(cur, afake); 531 return cur; 532 } 533 534 /* 535 * Install a new reverse mapping btree root. Caller is responsible for 536 * invalidating and freeing the old btree blocks. 537 */ 538 void 539 xfs_rmapbt_commit_staged_btree( 540 struct xfs_btree_cur *cur, 541 struct xfs_trans *tp, 542 struct xfs_buf *agbp) 543 { 544 struct xfs_agf *agf = agbp->b_addr; 545 struct xbtree_afakeroot *afake = cur->bc_ag.afake; 546 547 ASSERT(cur->bc_flags & XFS_BTREE_STAGING); 548 549 agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root); 550 agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels); 551 agf->agf_rmap_blocks = cpu_to_be32(afake->af_blocks); 552 xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS | 553 XFS_AGF_RMAP_BLOCKS); 554 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_rmapbt_ops); 555 } 556 557 /* Calculate number of records in a reverse mapping btree block. */ 558 static inline unsigned int 559 xfs_rmapbt_block_maxrecs( 560 unsigned int blocklen, 561 bool leaf) 562 { 563 if (leaf) 564 return blocklen / sizeof(struct xfs_rmap_rec); 565 return blocklen / 566 (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); 567 } 568 569 /* 570 * Calculate number of records in an rmap btree block. 571 */ 572 int 573 xfs_rmapbt_maxrecs( 574 int blocklen, 575 int leaf) 576 { 577 blocklen -= XFS_RMAP_BLOCK_LEN; 578 return xfs_rmapbt_block_maxrecs(blocklen, leaf); 579 } 580 581 /* Compute the max possible height for reverse mapping btrees. */ 582 unsigned int 583 xfs_rmapbt_maxlevels_ondisk(void) 584 { 585 unsigned int minrecs[2]; 586 unsigned int blocklen; 587 588 blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; 589 590 minrecs[0] = xfs_rmapbt_block_maxrecs(blocklen, true) / 2; 591 minrecs[1] = xfs_rmapbt_block_maxrecs(blocklen, false) / 2; 592 593 /* 594 * Compute the asymptotic maxlevels for an rmapbt on any reflink fs. 595 * 596 * On a reflink filesystem, each AG block can have up to 2^32 (per the 597 * refcount record format) owners, which means that theoretically we 598 * could face up to 2^64 rmap records. However, we're likely to run 599 * out of blocks in the AG long before that happens, which means that 600 * we must compute the max height based on what the btree will look 601 * like if it consumes almost all the blocks in the AG due to maximal 602 * sharing factor. 603 */ 604 return xfs_btree_space_to_height(minrecs, XFS_MAX_CRC_AG_BLOCKS); 605 } 606 607 /* Compute the maximum height of an rmap btree. */ 608 void 609 xfs_rmapbt_compute_maxlevels( 610 struct xfs_mount *mp) 611 { 612 if (!xfs_has_rmapbt(mp)) { 613 mp->m_rmap_maxlevels = 0; 614 return; 615 } 616 617 if (xfs_has_reflink(mp)) { 618 /* 619 * Compute the asymptotic maxlevels for an rmap btree on a 620 * filesystem that supports reflink. 621 * 622 * On a reflink filesystem, each AG block can have up to 2^32 623 * (per the refcount record format) owners, which means that 624 * theoretically we could face up to 2^64 rmap records. 625 * However, we're likely to run out of blocks in the AG long 626 * before that happens, which means that we must compute the 627 * max height based on what the btree will look like if it 628 * consumes almost all the blocks in the AG due to maximal 629 * sharing factor. 630 */ 631 mp->m_rmap_maxlevels = xfs_btree_space_to_height(mp->m_rmap_mnr, 632 mp->m_sb.sb_agblocks); 633 } else { 634 /* 635 * If there's no block sharing, compute the maximum rmapbt 636 * height assuming one rmap record per AG block. 637 */ 638 mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels( 639 mp->m_rmap_mnr, mp->m_sb.sb_agblocks); 640 } 641 ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk()); 642 } 643 644 /* Calculate the refcount btree size for some records. */ 645 xfs_extlen_t 646 xfs_rmapbt_calc_size( 647 struct xfs_mount *mp, 648 unsigned long long len) 649 { 650 return xfs_btree_calc_size(mp->m_rmap_mnr, len); 651 } 652 653 /* 654 * Calculate the maximum refcount btree size. 655 */ 656 xfs_extlen_t 657 xfs_rmapbt_max_size( 658 struct xfs_mount *mp, 659 xfs_agblock_t agblocks) 660 { 661 /* Bail out if we're uninitialized, which can happen in mkfs. */ 662 if (mp->m_rmap_mxr[0] == 0) 663 return 0; 664 665 return xfs_rmapbt_calc_size(mp, agblocks); 666 } 667 668 /* 669 * Figure out how many blocks to reserve and how many are used by this btree. 670 */ 671 int 672 xfs_rmapbt_calc_reserves( 673 struct xfs_mount *mp, 674 struct xfs_trans *tp, 675 struct xfs_perag *pag, 676 xfs_extlen_t *ask, 677 xfs_extlen_t *used) 678 { 679 struct xfs_buf *agbp; 680 struct xfs_agf *agf; 681 xfs_agblock_t agblocks; 682 xfs_extlen_t tree_len; 683 int error; 684 685 if (!xfs_has_rmapbt(mp)) 686 return 0; 687 688 error = xfs_alloc_read_agf(pag, tp, 0, &agbp); 689 if (error) 690 return error; 691 692 agf = agbp->b_addr; 693 agblocks = be32_to_cpu(agf->agf_length); 694 tree_len = be32_to_cpu(agf->agf_rmap_blocks); 695 xfs_trans_brelse(tp, agbp); 696 697 /* 698 * The log is permanently allocated, so the space it occupies will 699 * never be available for the kinds of things that would require btree 700 * expansion. We therefore can pretend the space isn't there. 701 */ 702 if (xfs_ag_contains_log(mp, pag->pag_agno)) 703 agblocks -= mp->m_sb.sb_logblocks; 704 705 /* Reserve 1% of the AG or enough for 1 block per record. */ 706 *ask += max(agblocks / 100, xfs_rmapbt_max_size(mp, agblocks)); 707 *used += tree_len; 708 709 return error; 710 } 711 712 int __init 713 xfs_rmapbt_init_cur_cache(void) 714 { 715 xfs_rmapbt_cur_cache = kmem_cache_create("xfs_rmapbt_cur", 716 xfs_btree_cur_sizeof(xfs_rmapbt_maxlevels_ondisk()), 717 0, 0, NULL); 718 719 if (!xfs_rmapbt_cur_cache) 720 return -ENOMEM; 721 return 0; 722 } 723 724 void 725 xfs_rmapbt_destroy_cur_cache(void) 726 { 727 kmem_cache_destroy(xfs_rmapbt_cur_cache); 728 xfs_rmapbt_cur_cache = NULL; 729 } 730