fs/xfs/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_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_mount.h"
  28 #include "xfs_bmap_btree.h"
  29 #include "xfs_alloc_btree.h"
  30 #include "xfs_ialloc_btree.h"
  31 #include "xfs_dinode.h"
  32 #include "xfs_inode.h"
  33 #include "xfs_btree.h"
  34 #include "xfs_btree_trace.h"
  35 #include "xfs_alloc.h"
  36 #include "xfs_error.h"
  37 #include "xfs_trace.h"
  38
  39
  40 STATIC struct xfs_btree_cur *
  41 xfs_allocbt_dup_cursor(
  42         struct xfs_btree_cur    *cur)
  43 {
  44         return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
  45                         cur->bc_private.a.agbp, cur->bc_private.a.agno,
  46                         cur->bc_btnum);
  47 }
  48
  49 STATIC void
  50 xfs_allocbt_set_root(
  51         struct xfs_btree_cur    *cur,
  52         union xfs_btree_ptr     *ptr,
  53         int                     inc)
  54 {
  55         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
  56         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
  57         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
  58         int                     btnum = cur->bc_btnum;
  59         struct xfs_perag        *pag = xfs_perag_get(cur->bc_mp, seqno);
  60
  61         ASSERT(ptr->s != 0);
  62
  63         agf->agf_roots[btnum] = ptr->s;
  64         be32_add_cpu(&agf->agf_levels[btnum], inc);
  65         pag->pagf_levels[btnum] += inc;
  66         xfs_perag_put(pag);
  67
  68         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  69 }
  70
  71 STATIC int
  72 xfs_allocbt_alloc_block(
  73         struct xfs_btree_cur    *cur,
  74         union xfs_btree_ptr     *start,
  75         union xfs_btree_ptr     *new,
  76         int                     length,
  77         int                     *stat)
  78 {
  79         int                     error;
  80         xfs_agblock_t           bno;
  81
  82         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
  83
  84         /* Allocate the new block from the freelist. If we can't, give up.  */
  85         error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
  86                                        &bno, 1);
  87         if (error) {
  88                 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
  89                 return error;
  90         }
  91
  92         if (bno == NULLAGBLOCK) {
  93                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
  94                 *stat = 0;
  95                 return 0;
  96         }
  97
  98         xfs_trans_agbtree_delta(cur->bc_tp, 1);
  99         new->s = cpu_to_be32(bno);
 100
 101         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 102         *stat = 1;
 103         return 0;
 104 }
 105
 106 STATIC int
 107 xfs_allocbt_free_block(
 108         struct xfs_btree_cur    *cur,
 109         struct xfs_buf          *bp)
 110 {
 111         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 112         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 113         xfs_agblock_t           bno;
 114         int                     error;
 115
 116         bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp));
 117         error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
 118         if (error)
 119                 return error;
 120
 121         /*
 122          * Since blocks move to the free list without the coordination used in
 123          * xfs_bmap_finish, we can't allow block to be available for
 124          * reallocation and non-transaction writing (user data) until we know
 125          * that the transaction that moved it to the free list is permanently
 126          * on disk. We track the blocks by declaring these blocks as "busy";
 127          * the busy list is maintained on a per-ag basis and each transaction
 128          * records which entries should be removed when the iclog commits to
 129          * disk. If a busy block is allocated, the iclog is pushed up to the
 130          * LSN that freed the block.
 131          */
 132         xfs_alloc_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
 133         xfs_trans_agbtree_delta(cur->bc_tp, -1);
 134         return 0;
 135 }
 136
 137 /*
 138  * Update the longest extent in the AGF
 139  */
 140 STATIC void
 141 xfs_allocbt_update_lastrec(
 142         struct xfs_btree_cur    *cur,
 143         struct xfs_btree_block  *block,
 144         union xfs_btree_rec     *rec,
 145         int                     ptr,
 146         int                     reason)
 147 {
 148         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 149         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
 150         struct xfs_perag        *pag;
 151         __be32                  len;
 152         int                     numrecs;
 153
 154         ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
 155
 156         switch (reason) {
 157         case LASTREC_UPDATE:
 158                 /*
 159                  * If this is the last leaf block and it's the last record,
 160                  * then update the size of the longest extent in the AG.
 161                  */
 162                 if (ptr != xfs_btree_get_numrecs(block))
 163                         return;
 164                 len = rec->alloc.ar_blockcount;
 165                 break;
 166         case LASTREC_INSREC:
 167                 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
 168                     be32_to_cpu(agf->agf_longest))
 169                         return;
 170                 len = rec->alloc.ar_blockcount;
 171                 break;
 172         case LASTREC_DELREC:
 173                 numrecs = xfs_btree_get_numrecs(block);
 174                 if (ptr <= numrecs)
 175                         return;
 176                 ASSERT(ptr == numrecs + 1);
 177
 178                 if (numrecs) {
 179                         xfs_alloc_rec_t *rrp;
 180
 181                         rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs);
 182                         len = rrp->ar_blockcount;
 183                 } else {
 184                         len = 0;
 185                 }
 186
 187                 break;
 188         default:
 189                 ASSERT(0);
 190                 return;
 191         }
 192
 193         agf->agf_longest = len;
 194         pag = xfs_perag_get(cur->bc_mp, seqno);
 195         pag->pagf_longest = be32_to_cpu(len);
 196         xfs_perag_put(pag);
 197         xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST);
 198 }
 199
 200 STATIC int
 201 xfs_allocbt_get_minrecs(
 202         struct xfs_btree_cur    *cur,
 203         int                     level)
 204 {
 205         return cur->bc_mp->m_alloc_mnr[level != 0];
 206 }
 207
 208 STATIC int
 209 xfs_allocbt_get_maxrecs(
 210         struct xfs_btree_cur    *cur,
 211         int                     level)
 212 {
 213         return cur->bc_mp->m_alloc_mxr[level != 0];
 214 }
 215
 216 STATIC void
 217 xfs_allocbt_init_key_from_rec(
 218         union xfs_btree_key     *key,
 219         union xfs_btree_rec     *rec)
 220 {
 221         ASSERT(rec->alloc.ar_startblock != 0);
 222
 223         key->alloc.ar_startblock = rec->alloc.ar_startblock;
 224         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
 225 }
 226
 227 STATIC void
 228 xfs_allocbt_init_rec_from_key(
 229         union xfs_btree_key     *key,
 230         union xfs_btree_rec     *rec)
 231 {
 232         ASSERT(key->alloc.ar_startblock != 0);
 233
 234         rec->alloc.ar_startblock = key->alloc.ar_startblock;
 235         rec->alloc.ar_blockcount = key->alloc.ar_blockcount;
 236 }
 237
 238 STATIC void
 239 xfs_allocbt_init_rec_from_cur(
 240         struct xfs_btree_cur    *cur,
 241         union xfs_btree_rec     *rec)
 242 {
 243         ASSERT(cur->bc_rec.a.ar_startblock != 0);
 244
 245         rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
 246         rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
 247 }
 248
 249 STATIC void
 250 xfs_allocbt_init_ptr_from_cur(
 251         struct xfs_btree_cur    *cur,
 252         union xfs_btree_ptr     *ptr)
 253 {
 254         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 255
 256         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
 257         ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
 258
 259         ptr->s = agf->agf_roots[cur->bc_btnum];
 260 }
 261
 262 STATIC __int64_t
 263 xfs_allocbt_key_diff(
 264         struct xfs_btree_cur    *cur,
 265         union xfs_btree_key     *key)
 266 {
 267         xfs_alloc_rec_incore_t  *rec = &cur->bc_rec.a;
 268         xfs_alloc_key_t         *kp = &key->alloc;
 269         __int64_t               diff;
 270
 271         if (cur->bc_btnum == XFS_BTNUM_BNO) {
 272                 return (__int64_t)be32_to_cpu(kp->ar_startblock) -
 273                                 rec->ar_startblock;
 274         }
 275
 276         diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
 277         if (diff)
 278                 return diff;
 279
 280         return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
 281 }
 282
 283 #ifdef DEBUG
 284 STATIC int
 285 xfs_allocbt_keys_inorder(
 286         struct xfs_btree_cur    *cur,
 287         union xfs_btree_key     *k1,
 288         union xfs_btree_key     *k2)
 289 {
 290         if (cur->bc_btnum == XFS_BTNUM_BNO) {
 291                 return be32_to_cpu(k1->alloc.ar_startblock) <
 292                        be32_to_cpu(k2->alloc.ar_startblock);
 293         } else {
 294                 return be32_to_cpu(k1->alloc.ar_blockcount) <
 295                         be32_to_cpu(k2->alloc.ar_blockcount) ||
 296                         (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount &&
 297                          be32_to_cpu(k1->alloc.ar_startblock) <
 298                          be32_to_cpu(k2->alloc.ar_startblock));
 299         }
 300 }
 301
 302 STATIC int
 303 xfs_allocbt_recs_inorder(
 304         struct xfs_btree_cur    *cur,
 305         union xfs_btree_rec     *r1,
 306         union xfs_btree_rec     *r2)
 307 {
 308         if (cur->bc_btnum == XFS_BTNUM_BNO) {
 309                 return be32_to_cpu(r1->alloc.ar_startblock) +
 310                         be32_to_cpu(r1->alloc.ar_blockcount) <=
 311                         be32_to_cpu(r2->alloc.ar_startblock);
 312         } else {
 313                 return be32_to_cpu(r1->alloc.ar_blockcount) <
 314                         be32_to_cpu(r2->alloc.ar_blockcount) ||
 315                         (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount &&
 316                          be32_to_cpu(r1->alloc.ar_startblock) <
 317                          be32_to_cpu(r2->alloc.ar_startblock));
 318         }
 319 }
 320 #endif  /* DEBUG */
 321
 322 #ifdef XFS_BTREE_TRACE
 323 ktrace_t        *xfs_allocbt_trace_buf;
 324
 325 STATIC void
 326 xfs_allocbt_trace_enter(
 327         struct xfs_btree_cur    *cur,
 328         const char              *func,
 329         char                    *s,
 330         int                     type,
 331         int                     line,
 332         __psunsigned_t          a0,
 333         __psunsigned_t          a1,
 334         __psunsigned_t          a2,
 335         __psunsigned_t          a3,
 336         __psunsigned_t          a4,
 337         __psunsigned_t          a5,
 338         __psunsigned_t          a6,
 339         __psunsigned_t          a7,
 340         __psunsigned_t          a8,
 341         __psunsigned_t          a9,
 342         __psunsigned_t          a10)
 343 {
 344         ktrace_enter(xfs_allocbt_trace_buf, (void *)(__psint_t)type,
 345                 (void *)func, (void *)s, NULL, (void *)cur,
 346                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 347                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 348                 (void *)a8, (void *)a9, (void *)a10);
 349 }
 350
 351 STATIC void
 352 xfs_allocbt_trace_cursor(
 353         struct xfs_btree_cur    *cur,
 354         __uint32_t              *s0,
 355         __uint64_t              *l0,
 356         __uint64_t              *l1)
 357 {
 358         *s0 = cur->bc_private.a.agno;
 359         *l0 = cur->bc_rec.a.ar_startblock;
 360         *l1 = cur->bc_rec.a.ar_blockcount;
 361 }
 362
 363 STATIC void
 364 xfs_allocbt_trace_key(
 365         struct xfs_btree_cur    *cur,
 366         union xfs_btree_key     *key,
 367         __uint64_t              *l0,
 368         __uint64_t              *l1)
 369 {
 370         *l0 = be32_to_cpu(key->alloc.ar_startblock);
 371         *l1 = be32_to_cpu(key->alloc.ar_blockcount);
 372 }
 373
 374 STATIC void
 375 xfs_allocbt_trace_record(
 376         struct xfs_btree_cur    *cur,
 377         union xfs_btree_rec     *rec,
 378         __uint64_t              *l0,
 379         __uint64_t              *l1,
 380         __uint64_t              *l2)
 381 {
 382         *l0 = be32_to_cpu(rec->alloc.ar_startblock);
 383         *l1 = be32_to_cpu(rec->alloc.ar_blockcount);
 384         *l2 = 0;
 385 }
 386 #endif /* XFS_BTREE_TRACE */
 387
 388 static const struct xfs_btree_ops xfs_allocbt_ops = {
 389         .rec_len                = sizeof(xfs_alloc_rec_t),
 390         .key_len                = sizeof(xfs_alloc_key_t),
 391
 392         .dup_cursor             = xfs_allocbt_dup_cursor,
 393         .set_root               = xfs_allocbt_set_root,
 394         .alloc_block            = xfs_allocbt_alloc_block,
 395         .free_block             = xfs_allocbt_free_block,
 396         .update_lastrec         = xfs_allocbt_update_lastrec,
 397         .get_minrecs            = xfs_allocbt_get_minrecs,
 398         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 399         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 400         .init_rec_from_key      = xfs_allocbt_init_rec_from_key,
 401         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 402         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 403         .key_diff               = xfs_allocbt_key_diff,
 404
 405 #ifdef DEBUG
 406         .keys_inorder           = xfs_allocbt_keys_inorder,
 407         .recs_inorder           = xfs_allocbt_recs_inorder,
 408 #endif
 409
 410 #ifdef XFS_BTREE_TRACE
 411         .trace_enter            = xfs_allocbt_trace_enter,
 412         .trace_cursor           = xfs_allocbt_trace_cursor,
 413         .trace_key              = xfs_allocbt_trace_key,
 414         .trace_record           = xfs_allocbt_trace_record,
 415 #endif
 416 };
 417
 418 /*
 419  * Allocate a new allocation btree cursor.
 420  */
 421 struct xfs_btree_cur *                  /* new alloc btree cursor */
 422 xfs_allocbt_init_cursor(
 423         struct xfs_mount        *mp,            /* file system mount point */
 424         struct xfs_trans        *tp,            /* transaction pointer */
 425         struct xfs_buf          *agbp,          /* buffer for agf structure */
 426         xfs_agnumber_t          agno,           /* allocation group number */
 427         xfs_btnum_t             btnum)          /* btree identifier */
 428 {
 429         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 430         struct xfs_btree_cur    *cur;
 431
 432         ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
 433
 434         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 435
 436         cur->bc_tp = tp;
 437         cur->bc_mp = mp;
 438         cur->bc_nlevels = be32_to_cpu(agf->agf_levels[btnum]);
 439         cur->bc_btnum = btnum;
 440         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 441
 442         cur->bc_ops = &xfs_allocbt_ops;
 443         if (btnum == XFS_BTNUM_CNT)
 444                 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
 445
 446         cur->bc_private.a.agbp = agbp;
 447         cur->bc_private.a.agno = agno;
 448
 449         return cur;
 450 }
 451
 452 /*
 453  * Calculate number of records in an alloc btree block.
 454  */
 455 int
 456 xfs_allocbt_maxrecs(
 457         struct xfs_mount        *mp,
 458         int                     blocklen,
 459         int                     leaf)
 460 {
 461         blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
 462
 463         if (leaf)
 464                 return blocklen / sizeof(xfs_alloc_rec_t);
 465         return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
 466 }