fs/xfs/libxfs/xfs_alloc_btree.c

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