1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2000-2001,2005 Silicon Graphics, 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_sb.h" 13 #include "xfs_mount.h" 14 #include "xfs_btree.h" 15 #include "xfs_btree_staging.h" 16 #include "xfs_alloc_btree.h" 17 #include "xfs_alloc.h" 18 #include "xfs_extent_busy.h" 19 #include "xfs_error.h" 20 #include "xfs_trace.h" 21 #include "xfs_trans.h" 22 23 24 STATIC struct xfs_btree_cur * 25 xfs_allocbt_dup_cursor( 26 struct xfs_btree_cur *cur) 27 { 28 return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, 29 cur->bc_ag.agbp, cur->bc_ag.agno, 30 cur->bc_btnum); 31 } 32 33 STATIC void 34 xfs_allocbt_set_root( 35 struct xfs_btree_cur *cur, 36 union xfs_btree_ptr *ptr, 37 int inc) 38 { 39 struct xfs_buf *agbp = cur->bc_ag.agbp; 40 struct xfs_agf *agf = agbp->b_addr; 41 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 42 int btnum = cur->bc_btnum; 43 struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); 44 45 ASSERT(ptr->s != 0); 46 47 agf->agf_roots[btnum] = ptr->s; 48 be32_add_cpu(&agf->agf_levels[btnum], inc); 49 pag->pagf_levels[btnum] += inc; 50 xfs_perag_put(pag); 51 52 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 53 } 54 55 STATIC int 56 xfs_allocbt_alloc_block( 57 struct xfs_btree_cur *cur, 58 union xfs_btree_ptr *start, 59 union xfs_btree_ptr *new, 60 int *stat) 61 { 62 int error; 63 xfs_agblock_t bno; 64 65 /* Allocate the new block from the freelist. If we can't, give up. */ 66 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_ag.agbp, 67 &bno, 1); 68 if (error) 69 return error; 70 71 if (bno == NULLAGBLOCK) { 72 *stat = 0; 73 return 0; 74 } 75 76 xfs_extent_busy_reuse(cur->bc_mp, cur->bc_ag.agno, bno, 1, false); 77 78 xfs_trans_agbtree_delta(cur->bc_tp, 1); 79 new->s = cpu_to_be32(bno); 80 81 *stat = 1; 82 return 0; 83 } 84 85 STATIC int 86 xfs_allocbt_free_block( 87 struct xfs_btree_cur *cur, 88 struct xfs_buf *bp) 89 { 90 struct xfs_buf *agbp = cur->bc_ag.agbp; 91 struct xfs_agf *agf = agbp->b_addr; 92 xfs_agblock_t bno; 93 int error; 94 95 bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); 96 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); 97 if (error) 98 return error; 99 100 xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, 101 XFS_EXTENT_BUSY_SKIP_DISCARD); 102 xfs_trans_agbtree_delta(cur->bc_tp, -1); 103 return 0; 104 } 105 106 /* 107 * Update the longest extent in the AGF 108 */ 109 STATIC void 110 xfs_allocbt_update_lastrec( 111 struct xfs_btree_cur *cur, 112 struct xfs_btree_block *block, 113 union xfs_btree_rec *rec, 114 int ptr, 115 int reason) 116 { 117 struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 118 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 119 struct xfs_perag *pag; 120 __be32 len; 121 int numrecs; 122 123 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); 124 125 switch (reason) { 126 case LASTREC_UPDATE: 127 /* 128 * If this is the last leaf block and it's the last record, 129 * then update the size of the longest extent in the AG. 130 */ 131 if (ptr != xfs_btree_get_numrecs(block)) 132 return; 133 len = rec->alloc.ar_blockcount; 134 break; 135 case LASTREC_INSREC: 136 if (be32_to_cpu(rec->alloc.ar_blockcount) <= 137 be32_to_cpu(agf->agf_longest)) 138 return; 139 len = rec->alloc.ar_blockcount; 140 break; 141 case LASTREC_DELREC: 142 numrecs = xfs_btree_get_numrecs(block); 143 if (ptr <= numrecs) 144 return; 145 ASSERT(ptr == numrecs + 1); 146 147 if (numrecs) { 148 xfs_alloc_rec_t *rrp; 149 150 rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); 151 len = rrp->ar_blockcount; 152 } else { 153 len = 0; 154 } 155 156 break; 157 default: 158 ASSERT(0); 159 return; 160 } 161 162 agf->agf_longest = len; 163 pag = xfs_perag_get(cur->bc_mp, seqno); 164 pag->pagf_longest = be32_to_cpu(len); 165 xfs_perag_put(pag); 166 xfs_alloc_log_agf(cur->bc_tp, cur->bc_ag.agbp, XFS_AGF_LONGEST); 167 } 168 169 STATIC int 170 xfs_allocbt_get_minrecs( 171 struct xfs_btree_cur *cur, 172 int level) 173 { 174 return cur->bc_mp->m_alloc_mnr[level != 0]; 175 } 176 177 STATIC int 178 xfs_allocbt_get_maxrecs( 179 struct xfs_btree_cur *cur, 180 int level) 181 { 182 return cur->bc_mp->m_alloc_mxr[level != 0]; 183 } 184 185 STATIC void 186 xfs_allocbt_init_key_from_rec( 187 union xfs_btree_key *key, 188 union xfs_btree_rec *rec) 189 { 190 key->alloc.ar_startblock = rec->alloc.ar_startblock; 191 key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 192 } 193 194 STATIC void 195 xfs_bnobt_init_high_key_from_rec( 196 union xfs_btree_key *key, 197 union xfs_btree_rec *rec) 198 { 199 __u32 x; 200 201 x = be32_to_cpu(rec->alloc.ar_startblock); 202 x += be32_to_cpu(rec->alloc.ar_blockcount) - 1; 203 key->alloc.ar_startblock = cpu_to_be32(x); 204 key->alloc.ar_blockcount = 0; 205 } 206 207 STATIC void 208 xfs_cntbt_init_high_key_from_rec( 209 union xfs_btree_key *key, 210 union xfs_btree_rec *rec) 211 { 212 key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 213 key->alloc.ar_startblock = 0; 214 } 215 216 STATIC void 217 xfs_allocbt_init_rec_from_cur( 218 struct xfs_btree_cur *cur, 219 union xfs_btree_rec *rec) 220 { 221 rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); 222 rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); 223 } 224 225 STATIC void 226 xfs_allocbt_init_ptr_from_cur( 227 struct xfs_btree_cur *cur, 228 union xfs_btree_ptr *ptr) 229 { 230 struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; 231 232 ASSERT(cur->bc_ag.agno == be32_to_cpu(agf->agf_seqno)); 233 234 ptr->s = agf->agf_roots[cur->bc_btnum]; 235 } 236 237 STATIC int64_t 238 xfs_bnobt_key_diff( 239 struct xfs_btree_cur *cur, 240 union xfs_btree_key *key) 241 { 242 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 243 xfs_alloc_key_t *kp = &key->alloc; 244 245 return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 246 } 247 248 STATIC int64_t 249 xfs_cntbt_key_diff( 250 struct xfs_btree_cur *cur, 251 union xfs_btree_key *key) 252 { 253 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 254 xfs_alloc_key_t *kp = &key->alloc; 255 int64_t diff; 256 257 diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; 258 if (diff) 259 return diff; 260 261 return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 262 } 263 264 STATIC int64_t 265 xfs_bnobt_diff_two_keys( 266 struct xfs_btree_cur *cur, 267 union xfs_btree_key *k1, 268 union xfs_btree_key *k2) 269 { 270 return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) - 271 be32_to_cpu(k2->alloc.ar_startblock); 272 } 273 274 STATIC int64_t 275 xfs_cntbt_diff_two_keys( 276 struct xfs_btree_cur *cur, 277 union xfs_btree_key *k1, 278 union xfs_btree_key *k2) 279 { 280 int64_t diff; 281 282 diff = be32_to_cpu(k1->alloc.ar_blockcount) - 283 be32_to_cpu(k2->alloc.ar_blockcount); 284 if (diff) 285 return diff; 286 287 return be32_to_cpu(k1->alloc.ar_startblock) - 288 be32_to_cpu(k2->alloc.ar_startblock); 289 } 290 291 static xfs_failaddr_t 292 xfs_allocbt_verify( 293 struct xfs_buf *bp) 294 { 295 struct xfs_mount *mp = bp->b_mount; 296 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 297 struct xfs_perag *pag = bp->b_pag; 298 xfs_failaddr_t fa; 299 unsigned int level; 300 xfs_btnum_t btnum = XFS_BTNUM_BNOi; 301 302 if (!xfs_verify_magic(bp, block->bb_magic)) 303 return __this_address; 304 305 if (xfs_sb_version_hascrc(&mp->m_sb)) { 306 fa = xfs_btree_sblock_v5hdr_verify(bp); 307 if (fa) 308 return fa; 309 } 310 311 /* 312 * The perag may not be attached during grow operations or fully 313 * initialized from the AGF during log recovery. Therefore we can only 314 * check against maximum tree depth from those contexts. 315 * 316 * Otherwise check against the per-tree limit. Peek at one of the 317 * verifier magic values to determine the type of tree we're verifying 318 * against. 319 */ 320 level = be16_to_cpu(block->bb_level); 321 if (bp->b_ops->magic[0] == cpu_to_be32(XFS_ABTC_MAGIC)) 322 btnum = XFS_BTNUM_CNTi; 323 if (pag && pag->pagf_init) { 324 if (level >= pag->pagf_levels[btnum]) 325 return __this_address; 326 } else if (level >= mp->m_ag_maxlevels) 327 return __this_address; 328 329 return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); 330 } 331 332 static void 333 xfs_allocbt_read_verify( 334 struct xfs_buf *bp) 335 { 336 xfs_failaddr_t fa; 337 338 if (!xfs_btree_sblock_verify_crc(bp)) 339 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 340 else { 341 fa = xfs_allocbt_verify(bp); 342 if (fa) 343 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 344 } 345 346 if (bp->b_error) 347 trace_xfs_btree_corrupt(bp, _RET_IP_); 348 } 349 350 static void 351 xfs_allocbt_write_verify( 352 struct xfs_buf *bp) 353 { 354 xfs_failaddr_t fa; 355 356 fa = xfs_allocbt_verify(bp); 357 if (fa) { 358 trace_xfs_btree_corrupt(bp, _RET_IP_); 359 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 360 return; 361 } 362 xfs_btree_sblock_calc_crc(bp); 363 364 } 365 366 const struct xfs_buf_ops xfs_bnobt_buf_ops = { 367 .name = "xfs_bnobt", 368 .magic = { cpu_to_be32(XFS_ABTB_MAGIC), 369 cpu_to_be32(XFS_ABTB_CRC_MAGIC) }, 370 .verify_read = xfs_allocbt_read_verify, 371 .verify_write = xfs_allocbt_write_verify, 372 .verify_struct = xfs_allocbt_verify, 373 }; 374 375 const struct xfs_buf_ops xfs_cntbt_buf_ops = { 376 .name = "xfs_cntbt", 377 .magic = { cpu_to_be32(XFS_ABTC_MAGIC), 378 cpu_to_be32(XFS_ABTC_CRC_MAGIC) }, 379 .verify_read = xfs_allocbt_read_verify, 380 .verify_write = xfs_allocbt_write_verify, 381 .verify_struct = xfs_allocbt_verify, 382 }; 383 384 STATIC int 385 xfs_bnobt_keys_inorder( 386 struct xfs_btree_cur *cur, 387 union xfs_btree_key *k1, 388 union xfs_btree_key *k2) 389 { 390 return be32_to_cpu(k1->alloc.ar_startblock) < 391 be32_to_cpu(k2->alloc.ar_startblock); 392 } 393 394 STATIC int 395 xfs_bnobt_recs_inorder( 396 struct xfs_btree_cur *cur, 397 union xfs_btree_rec *r1, 398 union xfs_btree_rec *r2) 399 { 400 return be32_to_cpu(r1->alloc.ar_startblock) + 401 be32_to_cpu(r1->alloc.ar_blockcount) <= 402 be32_to_cpu(r2->alloc.ar_startblock); 403 } 404 405 STATIC int 406 xfs_cntbt_keys_inorder( 407 struct xfs_btree_cur *cur, 408 union xfs_btree_key *k1, 409 union xfs_btree_key *k2) 410 { 411 return be32_to_cpu(k1->alloc.ar_blockcount) < 412 be32_to_cpu(k2->alloc.ar_blockcount) || 413 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && 414 be32_to_cpu(k1->alloc.ar_startblock) < 415 be32_to_cpu(k2->alloc.ar_startblock)); 416 } 417 418 STATIC int 419 xfs_cntbt_recs_inorder( 420 struct xfs_btree_cur *cur, 421 union xfs_btree_rec *r1, 422 union xfs_btree_rec *r2) 423 { 424 return be32_to_cpu(r1->alloc.ar_blockcount) < 425 be32_to_cpu(r2->alloc.ar_blockcount) || 426 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && 427 be32_to_cpu(r1->alloc.ar_startblock) < 428 be32_to_cpu(r2->alloc.ar_startblock)); 429 } 430 431 static const struct xfs_btree_ops xfs_bnobt_ops = { 432 .rec_len = sizeof(xfs_alloc_rec_t), 433 .key_len = sizeof(xfs_alloc_key_t), 434 435 .dup_cursor = xfs_allocbt_dup_cursor, 436 .set_root = xfs_allocbt_set_root, 437 .alloc_block = xfs_allocbt_alloc_block, 438 .free_block = xfs_allocbt_free_block, 439 .update_lastrec = xfs_allocbt_update_lastrec, 440 .get_minrecs = xfs_allocbt_get_minrecs, 441 .get_maxrecs = xfs_allocbt_get_maxrecs, 442 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 443 .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, 444 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 445 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 446 .key_diff = xfs_bnobt_key_diff, 447 .buf_ops = &xfs_bnobt_buf_ops, 448 .diff_two_keys = xfs_bnobt_diff_two_keys, 449 .keys_inorder = xfs_bnobt_keys_inorder, 450 .recs_inorder = xfs_bnobt_recs_inorder, 451 }; 452 453 static const struct xfs_btree_ops xfs_cntbt_ops = { 454 .rec_len = sizeof(xfs_alloc_rec_t), 455 .key_len = sizeof(xfs_alloc_key_t), 456 457 .dup_cursor = xfs_allocbt_dup_cursor, 458 .set_root = xfs_allocbt_set_root, 459 .alloc_block = xfs_allocbt_alloc_block, 460 .free_block = xfs_allocbt_free_block, 461 .update_lastrec = xfs_allocbt_update_lastrec, 462 .get_minrecs = xfs_allocbt_get_minrecs, 463 .get_maxrecs = xfs_allocbt_get_maxrecs, 464 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 465 .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, 466 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 467 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 468 .key_diff = xfs_cntbt_key_diff, 469 .buf_ops = &xfs_cntbt_buf_ops, 470 .diff_two_keys = xfs_cntbt_diff_two_keys, 471 .keys_inorder = xfs_cntbt_keys_inorder, 472 .recs_inorder = xfs_cntbt_recs_inorder, 473 }; 474 475 /* Allocate most of a new allocation btree cursor. */ 476 STATIC struct xfs_btree_cur * 477 xfs_allocbt_init_common( 478 struct xfs_mount *mp, 479 struct xfs_trans *tp, 480 xfs_agnumber_t agno, 481 xfs_btnum_t btnum) 482 { 483 struct xfs_btree_cur *cur; 484 485 ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); 486 487 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 488 489 cur->bc_tp = tp; 490 cur->bc_mp = mp; 491 cur->bc_btnum = btnum; 492 cur->bc_blocklog = mp->m_sb.sb_blocklog; 493 494 if (btnum == XFS_BTNUM_CNT) { 495 cur->bc_ops = &xfs_cntbt_ops; 496 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); 497 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; 498 } else { 499 cur->bc_ops = &xfs_bnobt_ops; 500 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); 501 } 502 503 cur->bc_ag.agno = agno; 504 cur->bc_ag.abt.active = false; 505 506 if (xfs_sb_version_hascrc(&mp->m_sb)) 507 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 508 509 return cur; 510 } 511 512 /* 513 * Allocate a new allocation btree cursor. 514 */ 515 struct xfs_btree_cur * /* new alloc btree cursor */ 516 xfs_allocbt_init_cursor( 517 struct xfs_mount *mp, /* file system mount point */ 518 struct xfs_trans *tp, /* transaction pointer */ 519 struct xfs_buf *agbp, /* buffer for agf structure */ 520 xfs_agnumber_t agno, /* allocation group number */ 521 xfs_btnum_t btnum) /* btree identifier */ 522 { 523 struct xfs_agf *agf = agbp->b_addr; 524 struct xfs_btree_cur *cur; 525 526 cur = xfs_allocbt_init_common(mp, tp, agno, btnum); 527 if (btnum == XFS_BTNUM_CNT) 528 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); 529 else 530 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); 531 532 cur->bc_ag.agbp = agbp; 533 534 return cur; 535 } 536 537 /* Create a free space btree cursor with a fake root for staging. */ 538 struct xfs_btree_cur * 539 xfs_allocbt_stage_cursor( 540 struct xfs_mount *mp, 541 struct xbtree_afakeroot *afake, 542 xfs_agnumber_t agno, 543 xfs_btnum_t btnum) 544 { 545 struct xfs_btree_cur *cur; 546 547 cur = xfs_allocbt_init_common(mp, NULL, agno, btnum); 548 xfs_btree_stage_afakeroot(cur, afake); 549 return cur; 550 } 551 552 /* 553 * Install a new free space btree root. Caller is responsible for invalidating 554 * and freeing the old btree blocks. 555 */ 556 void 557 xfs_allocbt_commit_staged_btree( 558 struct xfs_btree_cur *cur, 559 struct xfs_trans *tp, 560 struct xfs_buf *agbp) 561 { 562 struct xfs_agf *agf = agbp->b_addr; 563 struct xbtree_afakeroot *afake = cur->bc_ag.afake; 564 565 ASSERT(cur->bc_flags & XFS_BTREE_STAGING); 566 567 agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root); 568 agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels); 569 xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 570 571 if (cur->bc_btnum == XFS_BTNUM_BNO) { 572 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_bnobt_ops); 573 } else { 574 cur->bc_flags |= XFS_BTREE_LASTREC_UPDATE; 575 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_cntbt_ops); 576 } 577 } 578 579 /* 580 * Calculate number of records in an alloc btree block. 581 */ 582 int 583 xfs_allocbt_maxrecs( 584 struct xfs_mount *mp, 585 int blocklen, 586 int leaf) 587 { 588 blocklen -= XFS_ALLOC_BLOCK_LEN(mp); 589 590 if (leaf) 591 return blocklen / sizeof(xfs_alloc_rec_t); 592 return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); 593 } 594 595 /* Calculate the freespace btree size for some records. */ 596 xfs_extlen_t 597 xfs_allocbt_calc_size( 598 struct xfs_mount *mp, 599 unsigned long long len) 600 { 601 return xfs_btree_calc_size(mp->m_alloc_mnr, len); 602 } 603