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