1 /* 2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include "xfs.h" 19 #include "xfs_fs.h" 20 #include "xfs_shared.h" 21 #include "xfs_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_sb.h" 25 #include "xfs_mount.h" 26 #include "xfs_btree.h" 27 #include "xfs_alloc_btree.h" 28 #include "xfs_alloc.h" 29 #include "xfs_extent_busy.h" 30 #include "xfs_error.h" 31 #include "xfs_trace.h" 32 #include "xfs_cksum.h" 33 #include "xfs_trans.h" 34 35 36 STATIC struct xfs_btree_cur * 37 xfs_allocbt_dup_cursor( 38 struct xfs_btree_cur *cur) 39 { 40 return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, 41 cur->bc_private.a.agbp, cur->bc_private.a.agno, 42 cur->bc_btnum); 43 } 44 45 STATIC void 46 xfs_allocbt_set_root( 47 struct xfs_btree_cur *cur, 48 union xfs_btree_ptr *ptr, 49 int inc) 50 { 51 struct xfs_buf *agbp = cur->bc_private.a.agbp; 52 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 53 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 54 int btnum = cur->bc_btnum; 55 struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); 56 57 ASSERT(ptr->s != 0); 58 59 agf->agf_roots[btnum] = ptr->s; 60 be32_add_cpu(&agf->agf_levels[btnum], inc); 61 pag->pagf_levels[btnum] += inc; 62 xfs_perag_put(pag); 63 64 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 65 } 66 67 STATIC int 68 xfs_allocbt_alloc_block( 69 struct xfs_btree_cur *cur, 70 union xfs_btree_ptr *start, 71 union xfs_btree_ptr *new, 72 int *stat) 73 { 74 int error; 75 xfs_agblock_t bno; 76 77 /* Allocate the new block from the freelist. If we can't, give up. */ 78 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp, 79 &bno, 1); 80 if (error) 81 return error; 82 83 if (bno == NULLAGBLOCK) { 84 *stat = 0; 85 return 0; 86 } 87 88 xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, false); 89 90 xfs_trans_agbtree_delta(cur->bc_tp, 1); 91 new->s = cpu_to_be32(bno); 92 93 *stat = 1; 94 return 0; 95 } 96 97 STATIC int 98 xfs_allocbt_free_block( 99 struct xfs_btree_cur *cur, 100 struct xfs_buf *bp) 101 { 102 struct xfs_buf *agbp = cur->bc_private.a.agbp; 103 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 104 xfs_agblock_t bno; 105 int error; 106 107 bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); 108 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); 109 if (error) 110 return error; 111 112 xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, 113 XFS_EXTENT_BUSY_SKIP_DISCARD); 114 xfs_trans_agbtree_delta(cur->bc_tp, -1); 115 return 0; 116 } 117 118 /* 119 * Update the longest extent in the AGF 120 */ 121 STATIC void 122 xfs_allocbt_update_lastrec( 123 struct xfs_btree_cur *cur, 124 struct xfs_btree_block *block, 125 union xfs_btree_rec *rec, 126 int ptr, 127 int reason) 128 { 129 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 130 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 131 struct xfs_perag *pag; 132 __be32 len; 133 int numrecs; 134 135 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); 136 137 switch (reason) { 138 case LASTREC_UPDATE: 139 /* 140 * If this is the last leaf block and it's the last record, 141 * then update the size of the longest extent in the AG. 142 */ 143 if (ptr != xfs_btree_get_numrecs(block)) 144 return; 145 len = rec->alloc.ar_blockcount; 146 break; 147 case LASTREC_INSREC: 148 if (be32_to_cpu(rec->alloc.ar_blockcount) <= 149 be32_to_cpu(agf->agf_longest)) 150 return; 151 len = rec->alloc.ar_blockcount; 152 break; 153 case LASTREC_DELREC: 154 numrecs = xfs_btree_get_numrecs(block); 155 if (ptr <= numrecs) 156 return; 157 ASSERT(ptr == numrecs + 1); 158 159 if (numrecs) { 160 xfs_alloc_rec_t *rrp; 161 162 rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); 163 len = rrp->ar_blockcount; 164 } else { 165 len = 0; 166 } 167 168 break; 169 default: 170 ASSERT(0); 171 return; 172 } 173 174 agf->agf_longest = len; 175 pag = xfs_perag_get(cur->bc_mp, seqno); 176 pag->pagf_longest = be32_to_cpu(len); 177 xfs_perag_put(pag); 178 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST); 179 } 180 181 STATIC int 182 xfs_allocbt_get_minrecs( 183 struct xfs_btree_cur *cur, 184 int level) 185 { 186 return cur->bc_mp->m_alloc_mnr[level != 0]; 187 } 188 189 STATIC int 190 xfs_allocbt_get_maxrecs( 191 struct xfs_btree_cur *cur, 192 int level) 193 { 194 return cur->bc_mp->m_alloc_mxr[level != 0]; 195 } 196 197 STATIC void 198 xfs_allocbt_init_key_from_rec( 199 union xfs_btree_key *key, 200 union xfs_btree_rec *rec) 201 { 202 key->alloc.ar_startblock = rec->alloc.ar_startblock; 203 key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 204 } 205 206 STATIC void 207 xfs_bnobt_init_high_key_from_rec( 208 union xfs_btree_key *key, 209 union xfs_btree_rec *rec) 210 { 211 __u32 x; 212 213 x = be32_to_cpu(rec->alloc.ar_startblock); 214 x += be32_to_cpu(rec->alloc.ar_blockcount) - 1; 215 key->alloc.ar_startblock = cpu_to_be32(x); 216 key->alloc.ar_blockcount = 0; 217 } 218 219 STATIC void 220 xfs_cntbt_init_high_key_from_rec( 221 union xfs_btree_key *key, 222 union xfs_btree_rec *rec) 223 { 224 key->alloc.ar_blockcount = rec->alloc.ar_blockcount; 225 key->alloc.ar_startblock = 0; 226 } 227 228 STATIC void 229 xfs_allocbt_init_rec_from_cur( 230 struct xfs_btree_cur *cur, 231 union xfs_btree_rec *rec) 232 { 233 rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); 234 rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); 235 } 236 237 STATIC void 238 xfs_allocbt_init_ptr_from_cur( 239 struct xfs_btree_cur *cur, 240 union xfs_btree_ptr *ptr) 241 { 242 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 243 244 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno)); 245 ASSERT(agf->agf_roots[cur->bc_btnum] != 0); 246 247 ptr->s = agf->agf_roots[cur->bc_btnum]; 248 } 249 250 STATIC int64_t 251 xfs_bnobt_key_diff( 252 struct xfs_btree_cur *cur, 253 union xfs_btree_key *key) 254 { 255 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 256 xfs_alloc_key_t *kp = &key->alloc; 257 258 return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 259 } 260 261 STATIC int64_t 262 xfs_cntbt_key_diff( 263 struct xfs_btree_cur *cur, 264 union xfs_btree_key *key) 265 { 266 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; 267 xfs_alloc_key_t *kp = &key->alloc; 268 int64_t diff; 269 270 diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; 271 if (diff) 272 return diff; 273 274 return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; 275 } 276 277 STATIC int64_t 278 xfs_bnobt_diff_two_keys( 279 struct xfs_btree_cur *cur, 280 union xfs_btree_key *k1, 281 union xfs_btree_key *k2) 282 { 283 return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) - 284 be32_to_cpu(k2->alloc.ar_startblock); 285 } 286 287 STATIC int64_t 288 xfs_cntbt_diff_two_keys( 289 struct xfs_btree_cur *cur, 290 union xfs_btree_key *k1, 291 union xfs_btree_key *k2) 292 { 293 int64_t diff; 294 295 diff = be32_to_cpu(k1->alloc.ar_blockcount) - 296 be32_to_cpu(k2->alloc.ar_blockcount); 297 if (diff) 298 return diff; 299 300 return be32_to_cpu(k1->alloc.ar_startblock) - 301 be32_to_cpu(k2->alloc.ar_startblock); 302 } 303 304 static xfs_failaddr_t 305 xfs_allocbt_verify( 306 struct xfs_buf *bp) 307 { 308 struct xfs_mount *mp = bp->b_target->bt_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 level = be16_to_cpu(block->bb_level); 327 switch (block->bb_magic) { 328 case cpu_to_be32(XFS_ABTB_CRC_MAGIC): 329 fa = xfs_btree_sblock_v5hdr_verify(bp); 330 if (fa) 331 return fa; 332 /* fall through */ 333 case cpu_to_be32(XFS_ABTB_MAGIC): 334 if (pag && pag->pagf_init) { 335 if (level >= pag->pagf_levels[XFS_BTNUM_BNOi]) 336 return __this_address; 337 } else if (level >= mp->m_ag_maxlevels) 338 return __this_address; 339 break; 340 case cpu_to_be32(XFS_ABTC_CRC_MAGIC): 341 fa = xfs_btree_sblock_v5hdr_verify(bp); 342 if (fa) 343 return fa; 344 /* fall through */ 345 case cpu_to_be32(XFS_ABTC_MAGIC): 346 if (pag && pag->pagf_init) { 347 if (level >= pag->pagf_levels[XFS_BTNUM_CNTi]) 348 return __this_address; 349 } else if (level >= mp->m_ag_maxlevels) 350 return __this_address; 351 break; 352 default: 353 return __this_address; 354 } 355 356 return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); 357 } 358 359 static void 360 xfs_allocbt_read_verify( 361 struct xfs_buf *bp) 362 { 363 xfs_failaddr_t fa; 364 365 if (!xfs_btree_sblock_verify_crc(bp)) 366 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 367 else { 368 fa = xfs_allocbt_verify(bp); 369 if (fa) 370 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 371 } 372 373 if (bp->b_error) 374 trace_xfs_btree_corrupt(bp, _RET_IP_); 375 } 376 377 static void 378 xfs_allocbt_write_verify( 379 struct xfs_buf *bp) 380 { 381 xfs_failaddr_t fa; 382 383 fa = xfs_allocbt_verify(bp); 384 if (fa) { 385 trace_xfs_btree_corrupt(bp, _RET_IP_); 386 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 387 return; 388 } 389 xfs_btree_sblock_calc_crc(bp); 390 391 } 392 393 const struct xfs_buf_ops xfs_allocbt_buf_ops = { 394 .name = "xfs_allocbt", 395 .verify_read = xfs_allocbt_read_verify, 396 .verify_write = xfs_allocbt_write_verify, 397 .verify_struct = xfs_allocbt_verify, 398 }; 399 400 401 STATIC int 402 xfs_bnobt_keys_inorder( 403 struct xfs_btree_cur *cur, 404 union xfs_btree_key *k1, 405 union xfs_btree_key *k2) 406 { 407 return be32_to_cpu(k1->alloc.ar_startblock) < 408 be32_to_cpu(k2->alloc.ar_startblock); 409 } 410 411 STATIC int 412 xfs_bnobt_recs_inorder( 413 struct xfs_btree_cur *cur, 414 union xfs_btree_rec *r1, 415 union xfs_btree_rec *r2) 416 { 417 return be32_to_cpu(r1->alloc.ar_startblock) + 418 be32_to_cpu(r1->alloc.ar_blockcount) <= 419 be32_to_cpu(r2->alloc.ar_startblock); 420 } 421 422 STATIC int 423 xfs_cntbt_keys_inorder( 424 struct xfs_btree_cur *cur, 425 union xfs_btree_key *k1, 426 union xfs_btree_key *k2) 427 { 428 return be32_to_cpu(k1->alloc.ar_blockcount) < 429 be32_to_cpu(k2->alloc.ar_blockcount) || 430 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && 431 be32_to_cpu(k1->alloc.ar_startblock) < 432 be32_to_cpu(k2->alloc.ar_startblock)); 433 } 434 435 STATIC int 436 xfs_cntbt_recs_inorder( 437 struct xfs_btree_cur *cur, 438 union xfs_btree_rec *r1, 439 union xfs_btree_rec *r2) 440 { 441 return be32_to_cpu(r1->alloc.ar_blockcount) < 442 be32_to_cpu(r2->alloc.ar_blockcount) || 443 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && 444 be32_to_cpu(r1->alloc.ar_startblock) < 445 be32_to_cpu(r2->alloc.ar_startblock)); 446 } 447 448 static const struct xfs_btree_ops xfs_bnobt_ops = { 449 .rec_len = sizeof(xfs_alloc_rec_t), 450 .key_len = sizeof(xfs_alloc_key_t), 451 452 .dup_cursor = xfs_allocbt_dup_cursor, 453 .set_root = xfs_allocbt_set_root, 454 .alloc_block = xfs_allocbt_alloc_block, 455 .free_block = xfs_allocbt_free_block, 456 .update_lastrec = xfs_allocbt_update_lastrec, 457 .get_minrecs = xfs_allocbt_get_minrecs, 458 .get_maxrecs = xfs_allocbt_get_maxrecs, 459 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 460 .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec, 461 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 462 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 463 .key_diff = xfs_bnobt_key_diff, 464 .buf_ops = &xfs_allocbt_buf_ops, 465 .diff_two_keys = xfs_bnobt_diff_two_keys, 466 .keys_inorder = xfs_bnobt_keys_inorder, 467 .recs_inorder = xfs_bnobt_recs_inorder, 468 }; 469 470 static const struct xfs_btree_ops xfs_cntbt_ops = { 471 .rec_len = sizeof(xfs_alloc_rec_t), 472 .key_len = sizeof(xfs_alloc_key_t), 473 474 .dup_cursor = xfs_allocbt_dup_cursor, 475 .set_root = xfs_allocbt_set_root, 476 .alloc_block = xfs_allocbt_alloc_block, 477 .free_block = xfs_allocbt_free_block, 478 .update_lastrec = xfs_allocbt_update_lastrec, 479 .get_minrecs = xfs_allocbt_get_minrecs, 480 .get_maxrecs = xfs_allocbt_get_maxrecs, 481 .init_key_from_rec = xfs_allocbt_init_key_from_rec, 482 .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec, 483 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, 484 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, 485 .key_diff = xfs_cntbt_key_diff, 486 .buf_ops = &xfs_allocbt_buf_ops, 487 .diff_two_keys = xfs_cntbt_diff_two_keys, 488 .keys_inorder = xfs_cntbt_keys_inorder, 489 .recs_inorder = xfs_cntbt_recs_inorder, 490 }; 491 492 /* 493 * Allocate a new allocation btree cursor. 494 */ 495 struct xfs_btree_cur * /* new alloc btree cursor */ 496 xfs_allocbt_init_cursor( 497 struct xfs_mount *mp, /* file system mount point */ 498 struct xfs_trans *tp, /* transaction pointer */ 499 struct xfs_buf *agbp, /* buffer for agf structure */ 500 xfs_agnumber_t agno, /* allocation group number */ 501 xfs_btnum_t btnum) /* btree identifier */ 502 { 503 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 504 struct xfs_btree_cur *cur; 505 506 ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); 507 508 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 509 510 cur->bc_tp = tp; 511 cur->bc_mp = mp; 512 cur->bc_btnum = btnum; 513 cur->bc_blocklog = mp->m_sb.sb_blocklog; 514 515 if (btnum == XFS_BTNUM_CNT) { 516 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2); 517 cur->bc_ops = &xfs_cntbt_ops; 518 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); 519 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; 520 } else { 521 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2); 522 cur->bc_ops = &xfs_bnobt_ops; 523 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); 524 } 525 526 cur->bc_private.a.agbp = agbp; 527 cur->bc_private.a.agno = agno; 528 529 if (xfs_sb_version_hascrc(&mp->m_sb)) 530 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 531 532 return cur; 533 } 534 535 /* 536 * Calculate number of records in an alloc btree block. 537 */ 538 int 539 xfs_allocbt_maxrecs( 540 struct xfs_mount *mp, 541 int blocklen, 542 int leaf) 543 { 544 blocklen -= XFS_ALLOC_BLOCK_LEN(mp); 545 546 if (leaf) 547 return blocklen / sizeof(xfs_alloc_rec_t); 548 return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); 549 } 550