fs/xfs/xfs_ialloc_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_dir2.h"
  28 #include "xfs_dmapi.h"
  29 #include "xfs_mount.h"
  30 #include "xfs_bmap_btree.h"
  31 #include "xfs_alloc_btree.h"
  32 #include "xfs_ialloc_btree.h"
  33 #include "xfs_dir2_sf.h"
  34 #include "xfs_attr_sf.h"
  35 #include "xfs_dinode.h"
  36 #include "xfs_inode.h"
  37 #include "xfs_btree.h"
  38 #include "xfs_btree_trace.h"
  39 #include "xfs_ialloc.h"
  40 #include "xfs_alloc.h"
  41 #include "xfs_error.h"
  42
  43
  44 /*
  45  * Get the data from the pointed-to record.
  46  */
  47 int                                     /* error */
  48 xfs_inobt_get_rec(
  49         xfs_btree_cur_t         *cur,   /* btree cursor */
  50         xfs_agino_t             *ino,   /* output: starting inode of chunk */
  51         __int32_t               *fcnt,  /* output: number of free inodes */
  52         xfs_inofree_t           *free,  /* output: free inode mask */
  53         int                     *stat)  /* output: success/failure */
  54 {
  55         xfs_inobt_block_t       *block; /* btree block */
  56         xfs_buf_t               *bp;    /* buffer containing btree block */
  57 #ifdef DEBUG
  58         int                     error;  /* error return value */
  59 #endif
  60         int                     ptr;    /* record number */
  61         xfs_inobt_rec_t         *rec;   /* record data */
  62
  63         bp = cur->bc_bufs[0];
  64         ptr = cur->bc_ptrs[0];
  65         block = XFS_BUF_TO_INOBT_BLOCK(bp);
  66 #ifdef DEBUG
  67         if ((error = xfs_btree_check_sblock(cur, block, 0, bp)))
  68                 return error;
  69 #endif
  70         /*
  71          * Off the right end or left end, return failure.
  72          */
  73         if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
  74                 *stat = 0;
  75                 return 0;
  76         }
  77         /*
  78          * Point to the record and extract its data.
  79          */
  80         rec = XFS_INOBT_REC_ADDR(block, ptr, cur);
  81         *ino = be32_to_cpu(rec->ir_startino);
  82         *fcnt = be32_to_cpu(rec->ir_freecount);
  83         *free = be64_to_cpu(rec->ir_free);
  84         *stat = 1;
  85         return 0;
  86 }
  87
  88 STATIC int
  89 xfs_inobt_get_minrecs(
  90         struct xfs_btree_cur    *cur,
  91         int                     level)
  92 {
  93         return cur->bc_mp->m_inobt_mnr[level != 0];
  94 }
  95
  96 STATIC struct xfs_btree_cur *
  97 xfs_inobt_dup_cursor(
  98         struct xfs_btree_cur    *cur)
  99 {
 100         return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
 101                         cur->bc_private.a.agbp, cur->bc_private.a.agno);
 102 }
 103
 104 STATIC void
 105 xfs_inobt_set_root(
 106         struct xfs_btree_cur    *cur,
 107         union xfs_btree_ptr     *nptr,
 108         int                     inc)    /* level change */
 109 {
 110         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 111         struct xfs_agi          *agi = XFS_BUF_TO_AGI(agbp);
 112
 113         agi->agi_root = nptr->s;
 114         be32_add_cpu(&agi->agi_level, inc);
 115         xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
 116 }
 117
 118 STATIC int
 119 xfs_inobt_alloc_block(
 120         struct xfs_btree_cur    *cur,
 121         union xfs_btree_ptr     *start,
 122         union xfs_btree_ptr     *new,
 123         int                     length,
 124         int                     *stat)
 125 {
 126         xfs_alloc_arg_t         args;           /* block allocation args */
 127         int                     error;          /* error return value */
 128         xfs_agblock_t           sbno = be32_to_cpu(start->s);
 129
 130         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
 131
 132         memset(&args, 0, sizeof(args));
 133         args.tp = cur->bc_tp;
 134         args.mp = cur->bc_mp;
 135         args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
 136         args.minlen = 1;
 137         args.maxlen = 1;
 138         args.prod = 1;
 139         args.type = XFS_ALLOCTYPE_NEAR_BNO;
 140
 141         error = xfs_alloc_vextent(&args);
 142         if (error) {
 143                 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 144                 return error;
 145         }
 146         if (args.fsbno == NULLFSBLOCK) {
 147                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 148                 *stat = 0;
 149                 return 0;
 150         }
 151         ASSERT(args.len == 1);
 152         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 153
 154         new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
 155         *stat = 1;
 156         return 0;
 157 }
 158
 159 STATIC int
 160 xfs_inobt_free_block(
 161         struct xfs_btree_cur    *cur,
 162         struct xfs_buf          *bp)
 163 {
 164         xfs_fsblock_t           fsbno;
 165         int                     error;
 166
 167         fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp));
 168         error = xfs_free_extent(cur->bc_tp, fsbno, 1);
 169         if (error)
 170                 return error;
 171
 172         xfs_trans_binval(cur->bc_tp, bp);
 173         return error;
 174 }
 175
 176 STATIC int
 177 xfs_inobt_get_maxrecs(
 178         struct xfs_btree_cur    *cur,
 179         int                     level)
 180 {
 181         return cur->bc_mp->m_inobt_mxr[level != 0];
 182 }
 183
 184 STATIC void
 185 xfs_inobt_init_key_from_rec(
 186         union xfs_btree_key     *key,
 187         union xfs_btree_rec     *rec)
 188 {
 189         key->inobt.ir_startino = rec->inobt.ir_startino;
 190 }
 191
 192 STATIC void
 193 xfs_inobt_init_rec_from_key(
 194         union xfs_btree_key     *key,
 195         union xfs_btree_rec     *rec)
 196 {
 197         rec->inobt.ir_startino = key->inobt.ir_startino;
 198 }
 199
 200 STATIC void
 201 xfs_inobt_init_rec_from_cur(
 202         struct xfs_btree_cur    *cur,
 203         union xfs_btree_rec     *rec)
 204 {
 205         rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
 206         rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
 207         rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
 208 }
 209
 210 /*
 211  * intial value of ptr for lookup
 212  */
 213 STATIC void
 214 xfs_inobt_init_ptr_from_cur(
 215         struct xfs_btree_cur    *cur,
 216         union xfs_btree_ptr     *ptr)
 217 {
 218         struct xfs_agi          *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
 219
 220         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
 221
 222         ptr->s = agi->agi_root;
 223 }
 224
 225 STATIC __int64_t
 226 xfs_inobt_key_diff(
 227         struct xfs_btree_cur    *cur,
 228         union xfs_btree_key     *key)
 229 {
 230         return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
 231                           cur->bc_rec.i.ir_startino;
 232 }
 233
 234 STATIC int
 235 xfs_inobt_kill_root(
 236         struct xfs_btree_cur    *cur,
 237         struct xfs_buf          *bp,
 238         int                     level,
 239         union xfs_btree_ptr     *newroot)
 240 {
 241         int                     error;
 242
 243         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
 244         XFS_BTREE_STATS_INC(cur, killroot);
 245
 246         /*
 247          * Update the root pointer, decreasing the level by 1 and then
 248          * free the old root.
 249          */
 250         xfs_inobt_set_root(cur, newroot, -1);
 251         error = xfs_inobt_free_block(cur, bp);
 252         if (error) {
 253                 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 254                 return error;
 255         }
 256
 257         XFS_BTREE_STATS_INC(cur, free);
 258
 259         cur->bc_bufs[level] = NULL;
 260         cur->bc_nlevels--;
 261
 262         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 263         return 0;
 264 }
 265
 266 #ifdef XFS_BTREE_TRACE
 267 ktrace_t        *xfs_inobt_trace_buf;
 268
 269 STATIC void
 270 xfs_inobt_trace_enter(
 271         struct xfs_btree_cur    *cur,
 272         const char              *func,
 273         char                    *s,
 274         int                     type,
 275         int                     line,
 276         __psunsigned_t          a0,
 277         __psunsigned_t          a1,
 278         __psunsigned_t          a2,
 279         __psunsigned_t          a3,
 280         __psunsigned_t          a4,
 281         __psunsigned_t          a5,
 282         __psunsigned_t          a6,
 283         __psunsigned_t          a7,
 284         __psunsigned_t          a8,
 285         __psunsigned_t          a9,
 286         __psunsigned_t          a10)
 287 {
 288         ktrace_enter(xfs_inobt_trace_buf, (void *)(__psint_t)type,
 289                 (void *)func, (void *)s, NULL, (void *)cur,
 290                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 291                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 292                 (void *)a8, (void *)a9, (void *)a10);
 293 }
 294
 295 STATIC void
 296 xfs_inobt_trace_cursor(
 297         struct xfs_btree_cur    *cur,
 298         __uint32_t              *s0,
 299         __uint64_t              *l0,
 300         __uint64_t              *l1)
 301 {
 302         *s0 = cur->bc_private.a.agno;
 303         *l0 = cur->bc_rec.i.ir_startino;
 304         *l1 = cur->bc_rec.i.ir_free;
 305 }
 306
 307 STATIC void
 308 xfs_inobt_trace_key(
 309         struct xfs_btree_cur    *cur,
 310         union xfs_btree_key     *key,
 311         __uint64_t              *l0,
 312         __uint64_t              *l1)
 313 {
 314         *l0 = be32_to_cpu(key->inobt.ir_startino);
 315         *l1 = 0;
 316 }
 317
 318 STATIC void
 319 xfs_inobt_trace_record(
 320         struct xfs_btree_cur    *cur,
 321         union xfs_btree_rec     *rec,
 322         __uint64_t              *l0,
 323         __uint64_t              *l1,
 324         __uint64_t              *l2)
 325 {
 326         *l0 = be32_to_cpu(rec->inobt.ir_startino);
 327         *l1 = be32_to_cpu(rec->inobt.ir_freecount);
 328         *l2 = be64_to_cpu(rec->inobt.ir_free);
 329 }
 330 #endif /* XFS_BTREE_TRACE */
 331
 332 static const struct xfs_btree_ops xfs_inobt_ops = {
 333         .rec_len                = sizeof(xfs_inobt_rec_t),
 334         .key_len                = sizeof(xfs_inobt_key_t),
 335
 336         .dup_cursor             = xfs_inobt_dup_cursor,
 337         .set_root               = xfs_inobt_set_root,
 338         .kill_root              = xfs_inobt_kill_root,
 339         .alloc_block            = xfs_inobt_alloc_block,
 340         .free_block             = xfs_inobt_free_block,
 341         .get_minrecs            = xfs_inobt_get_minrecs,
 342         .get_maxrecs            = xfs_inobt_get_maxrecs,
 343         .init_key_from_rec      = xfs_inobt_init_key_from_rec,
 344         .init_rec_from_key      = xfs_inobt_init_rec_from_key,
 345         .init_rec_from_cur      = xfs_inobt_init_rec_from_cur,
 346         .init_ptr_from_cur      = xfs_inobt_init_ptr_from_cur,
 347         .key_diff               = xfs_inobt_key_diff,
 348
 349 #ifdef XFS_BTREE_TRACE
 350         .trace_enter            = xfs_inobt_trace_enter,
 351         .trace_cursor           = xfs_inobt_trace_cursor,
 352         .trace_key              = xfs_inobt_trace_key,
 353         .trace_record           = xfs_inobt_trace_record,
 354 #endif
 355 };
 356
 357 /*
 358  * Allocate a new inode btree cursor.
 359  */
 360 struct xfs_btree_cur *                          /* new inode btree cursor */
 361 xfs_inobt_init_cursor(
 362         struct xfs_mount        *mp,            /* file system mount point */
 363         struct xfs_trans        *tp,            /* transaction pointer */
 364         struct xfs_buf          *agbp,          /* buffer for agi structure */
 365         xfs_agnumber_t          agno)           /* allocation group number */
 366 {
 367         struct xfs_agi          *agi = XFS_BUF_TO_AGI(agbp);
 368         struct xfs_btree_cur    *cur;
 369
 370         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 371
 372         cur->bc_tp = tp;
 373         cur->bc_mp = mp;
 374         cur->bc_nlevels = be32_to_cpu(agi->agi_level);
 375         cur->bc_btnum = XFS_BTNUM_INO;
 376         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 377
 378         cur->bc_ops = &xfs_inobt_ops;
 379
 380         cur->bc_private.a.agbp = agbp;
 381         cur->bc_private.a.agno = agno;
 382
 383         return cur;
 384 }