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