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_alloc_btree.h" 16 #include "xfs_alloc.h" 17 #include "xfs_extent_busy.h" 18 #include "xfs_error.h" 19 #include "xfs_trace.h" 20 #include "xfs_cksum.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_private.a.agbp, cur->bc_private.a.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_private.a.agbp; 40 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 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_private.a.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_private.a.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_private.a.agbp; 91 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 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 = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 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_private.a.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 = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 231 232 ASSERT(cur->bc_private.a.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_target->bt_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 301 /* 302 * magic number and level verification 303 * 304 * During growfs operations, we can't verify the exact level or owner as 305 * the perag is not fully initialised and hence not attached to the 306 * buffer. In this case, check against the maximum tree depth. 307 * 308 * Similarly, during log recovery we will have a perag structure 309 * attached, but the agf information will not yet have been initialised 310 * from the on disk AGF. Again, we can only check against maximum limits 311 * in this case. 312 */ 313 level = be16_to_cpu(block->bb_level); 314 switch (block->bb_magic) { 315 case cpu_to_be32(XFS_ABTB_CRC_MAGIC): 316 fa = xfs_btree_sblock_v5hdr_verify(bp); 317 if (fa) 318 return fa; 319 /* fall through */ 320 case cpu_to_be32(XFS_ABTB_MAGIC): 321 if (pag && pag->pagf_init) { 322 if (level >= pag->pagf_levels[XFS_BTNUM_BNOi]) 323 return __this_address; 324 } else if (level >= mp->m_ag_maxlevels) 325 return __this_address; 326 break; 327 case cpu_to_be32(XFS_ABTC_CRC_MAGIC): 328 fa = xfs_btree_sblock_v5hdr_verify(bp); 329 if (fa) 330 return fa; 331 /* fall through */ 332 case cpu_to_be32(XFS_ABTC_MAGIC): 333 if (pag && pag->pagf_init) { 334 if (level >= pag->pagf_levels[XFS_BTNUM_CNTi]) 335 return __this_address; 336 } else if (level >= mp->m_ag_maxlevels) 337 return __this_address; 338 break; 339 default: 340 return __this_address; 341 } 342 343 return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); 344 } 345 346 static void 347 xfs_allocbt_read_verify( 348 struct xfs_buf *bp) 349 { 350 xfs_failaddr_t fa; 351 352 if (!xfs_btree_sblock_verify_crc(bp)) 353 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 354 else { 355 fa = xfs_allocbt_verify(bp); 356 if (fa) 357 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 358 } 359 360 if (bp->b_error) 361 trace_xfs_btree_corrupt(bp, _RET_IP_); 362 } 363 364 static void 365 xfs_allocbt_write_verify( 366 struct xfs_buf *bp) 367 { 368 xfs_failaddr_t fa; 369 370 fa = xfs_allocbt_verify(bp); 371 if (fa) { 372 trace_xfs_btree_corrupt(bp, _RET_IP_); 373 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 374 return; 375 } 376 xfs_btree_sblock_calc_crc(bp); 377 378 } 379 380 const struct xfs_buf_ops xfs_allocbt_buf_ops = { 381 .name = "xfs_allocbt", 382 .verify_read = xfs_allocbt_read_verify, 383 .verify_write = xfs_allocbt_write_verify, 384 .verify_struct = xfs_allocbt_verify, 385 }; 386 387 388 STATIC int 389 xfs_bnobt_keys_inorder( 390 struct xfs_btree_cur *cur, 391 union xfs_btree_key *k1, 392 union xfs_btree_key *k2) 393 { 394 return be32_to_cpu(k1->alloc.ar_startblock) < 395 be32_to_cpu(k2->alloc.ar_startblock); 396 } 397 398 STATIC int 399 xfs_bnobt_recs_inorder( 400 struct xfs_btree_cur *cur, 401 union xfs_btree_rec *r1, 402 union xfs_btree_rec *r2) 403 { 404 return be32_to_cpu(r1->alloc.ar_startblock) + 405 be32_to_cpu(r1->alloc.ar_blockcount) <= 406 be32_to_cpu(r2->alloc.ar_startblock); 407 } 408 409 STATIC int 410 xfs_cntbt_keys_inorder( 411 struct xfs_btree_cur *cur, 412 union xfs_btree_key *k1, 413 union xfs_btree_key *k2) 414 { 415 return be32_to_cpu(k1->alloc.ar_blockcount) < 416 be32_to_cpu(k2->alloc.ar_blockcount) || 417 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && 418 be32_to_cpu(k1->alloc.ar_startblock) < 419 be32_to_cpu(k2->alloc.ar_startblock)); 420 } 421 422 STATIC int 423 xfs_cntbt_recs_inorder( 424 struct xfs_btree_cur *cur, 425 union xfs_btree_rec *r1, 426 union xfs_btree_rec *r2) 427 { 428 return be32_to_cpu(r1->alloc.ar_blockcount) < 429 be32_to_cpu(r2->alloc.ar_blockcount) || 430 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && 431 be32_to_cpu(r1->alloc.ar_startblock) < 432 be32_to_cpu(r2->alloc.ar_startblock)); 433 } 434 435 static const struct xfs_btree_ops xfs_bnobt_ops = { 436 .rec_len = sizeof(xfs_alloc_rec_t), 437 .key_len = sizeof(xfs_alloc_key_t), 438 439 .dup_cursor = xfs_allocbt_dup_cursor, 440 .set_root = xfs_allocbt_set_root, 441 .alloc_block = xfs_allocbt_alloc_block, 442 .free_block = xfs_allocbt_free_block, 443 .update_lastrec = xfs_allocbt_update_lastrec, 444 .get_minrecs = xfs_allocbt_get_minrecs, 445 .get_maxrecs = xfs_allocbt_get_maxrecs, 446 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 447 .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, 448 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 449 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 450 .key_diff = xfs_bnobt_key_diff, 451 .buf_ops = &xfs_allocbt_buf_ops, 452 .diff_two_keys = xfs_bnobt_diff_two_keys, 453 .keys_inorder = xfs_bnobt_keys_inorder, 454 .recs_inorder = xfs_bnobt_recs_inorder, 455 }; 456 457 static const struct xfs_btree_ops xfs_cntbt_ops = { 458 .rec_len = sizeof(xfs_alloc_rec_t), 459 .key_len = sizeof(xfs_alloc_key_t), 460 461 .dup_cursor = xfs_allocbt_dup_cursor, 462 .set_root = xfs_allocbt_set_root, 463 .alloc_block = xfs_allocbt_alloc_block, 464 .free_block = xfs_allocbt_free_block, 465 .update_lastrec = xfs_allocbt_update_lastrec, 466 .get_minrecs = xfs_allocbt_get_minrecs, 467 .get_maxrecs = xfs_allocbt_get_maxrecs, 468 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 469 .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, 470 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 471 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 472 .key_diff = xfs_cntbt_key_diff, 473 .buf_ops = &xfs_allocbt_buf_ops, 474 .diff_two_keys = xfs_cntbt_diff_two_keys, 475 .keys_inorder = xfs_cntbt_keys_inorder, 476 .recs_inorder = xfs_cntbt_recs_inorder, 477 }; 478 479 /* 480 * Allocate a new allocation btree cursor. 481 */ 482 struct xfs_btree_cur * /* new alloc btree cursor */ 483 xfs_allocbt_init_cursor( 484 struct xfs_mount *mp, /* file system mount point */ 485 struct xfs_trans *tp, /* transaction pointer */ 486 struct xfs_buf *agbp, /* buffer for agf structure */ 487 xfs_agnumber_t agno, /* allocation group number */ 488 xfs_btnum_t btnum) /* btree identifier */ 489 { 490 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 491 struct xfs_btree_cur *cur; 492 493 ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); 494 495 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 496 497 cur->bc_tp = tp; 498 cur->bc_mp = mp; 499 cur->bc_btnum = btnum; 500 cur->bc_blocklog = mp->m_sb.sb_blocklog; 501 502 if (btnum == XFS_BTNUM_CNT) { 503 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); 504 cur->bc_ops = &xfs_cntbt_ops; 505 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); 506 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; 507 } else { 508 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); 509 cur->bc_ops = &xfs_bnobt_ops; 510 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); 511 } 512 513 cur->bc_private.a.agbp = agbp; 514 cur->bc_private.a.agno = agno; 515 516 if (xfs_sb_version_hascrc(&mp->m_sb)) 517 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 518 519 return cur; 520 } 521 522 /* 523 * Calculate number of records in an alloc btree block. 524 */ 525 int 526 xfs_allocbt_maxrecs( 527 struct xfs_mount *mp, 528 int blocklen, 529 int leaf) 530 { 531 blocklen -= XFS_ALLOC_BLOCK_LEN(mp); 532 533 if (leaf) 534 return blocklen / sizeof(xfs_alloc_rec_t); 535 return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); 536 } 537 538 /* Calculate the freespace btree size for some records. */ 539 xfs_extlen_t 540 xfs_allocbt_calc_size( 541 struct xfs_mount *mp, 542 unsigned long long len) 543 { 544 return xfs_btree_calc_size(mp->m_alloc_mnr, len); 545 } 546