fs/xfs/xfs_alloc_btree.h

   1 /*
   2  * Copyright (c) 2000 Silicon Graphics, Inc.  All Rights Reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of version 2 of the GNU General Public License as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it would be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11  *
  12  * Further, this software is distributed without any warranty that it is
  13  * free of the rightful claim of any third person regarding infringement
  14  * or the like.  Any license provided herein, whether implied or
  15  * otherwise, applies only to this software file.  Patent licenses, if
  16  * any, provided herein do not apply to combinations of this program with
  17  * other software, or any other product whatsoever.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write the Free Software Foundation, Inc., 59
  21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22  *
  23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24  * Mountain View, CA  94043, or:
  25  *
  26  * http://www.sgi.com
  27  *
  28  * For further information regarding this notice, see:
  29  *
  30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31  */
  32 #ifndef __XFS_ALLOC_BTREE_H__
  33 #define __XFS_ALLOC_BTREE_H__
  34
  35 /*
  36  * Freespace on-disk structures
  37  */
  38
  39 struct xfs_buf;
  40 struct xfs_btree_cur;
  41 struct xfs_btree_sblock;
  42 struct xfs_mount;
  43
  44 /*
  45  * There are two on-disk btrees, one sorted by blockno and one sorted
  46  * by blockcount and blockno.  All blocks look the same to make the code
  47  * simpler; if we have time later, we'll make the optimizations.
  48  */
  49 #define XFS_ABTB_MAGIC  0x41425442      /* 'ABTB' for bno tree */
  50 #define XFS_ABTC_MAGIC  0x41425443      /* 'ABTC' for cnt tree */
  51
  52 /*
  53  * Data record/key structure
  54  */
  55 typedef struct xfs_alloc_rec
  56 {
  57         xfs_agblock_t   ar_startblock;  /* starting block number */
  58         xfs_extlen_t    ar_blockcount;  /* count of free blocks */
  59 } xfs_alloc_rec_t, xfs_alloc_key_t;
  60
  61 typedef xfs_agblock_t xfs_alloc_ptr_t;  /* btree pointer type */
  62                                         /* btree block header type */
  63 typedef struct xfs_btree_sblock xfs_alloc_block_t;
  64
  65 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_BUF_TO_ALLOC_BLOCK)
  66 xfs_alloc_block_t *xfs_buf_to_alloc_block(struct xfs_buf *bp);
  67 #define XFS_BUF_TO_ALLOC_BLOCK(bp)      xfs_buf_to_alloc_block(bp)
  68 #else
  69 #define XFS_BUF_TO_ALLOC_BLOCK(bp) ((xfs_alloc_block_t *)(XFS_BUF_PTR(bp)))
  70 #endif
  71
  72 /*
  73  * Real block structures have a size equal to the disk block size.
  74  */
  75
  76 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_BLOCK_SIZE)
  77 int xfs_alloc_block_size(int lev, struct xfs_btree_cur *cur);
  78 #define XFS_ALLOC_BLOCK_SIZE(lev,cur)   xfs_alloc_block_size(lev,cur)
  79 #else
  80 #define XFS_ALLOC_BLOCK_SIZE(lev,cur)   (1 << (cur)->bc_blocklog)
  81 #endif
  82
  83 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_BLOCK_MAXRECS)
  84 int xfs_alloc_block_maxrecs(int lev, struct xfs_btree_cur *cur);
  85 #define XFS_ALLOC_BLOCK_MAXRECS(lev,cur)        xfs_alloc_block_maxrecs(lev,cur)
  86 #else
  87 #define XFS_ALLOC_BLOCK_MAXRECS(lev,cur)        \
  88         ((cur)->bc_mp->m_alloc_mxr[lev != 0])
  89 #endif
  90 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_BLOCK_MINRECS)
  91 int xfs_alloc_block_minrecs(int lev, struct xfs_btree_cur *cur);
  92 #define XFS_ALLOC_BLOCK_MINRECS(lev,cur)        xfs_alloc_block_minrecs(lev,cur)
  93 #else
  94 #define XFS_ALLOC_BLOCK_MINRECS(lev,cur)        \
  95         ((cur)->bc_mp->m_alloc_mnr[lev != 0])
  96 #endif
  97
  98 /*
  99  * Minimum and maximum blocksize and sectorsize.
 100  * The blocksize upper limit is pretty much arbitrary.
 101  * The sectorsize upper limit is due to sizeof(sb_sectsize).
 102  */
 103 #define XFS_MIN_BLOCKSIZE_LOG   9       /* i.e. 512 bytes */
 104 #define XFS_MAX_BLOCKSIZE_LOG   16      /* i.e. 65536 bytes */
 105 #define XFS_MIN_BLOCKSIZE       (1 << XFS_MIN_BLOCKSIZE_LOG)
 106 #define XFS_MAX_BLOCKSIZE       (1 << XFS_MAX_BLOCKSIZE_LOG)
 107 #define XFS_MIN_SECTORSIZE_LOG  9       /* i.e. 512 bytes */
 108 #define XFS_MAX_SECTORSIZE_LOG  15      /* i.e. 32768 bytes */
 109 #define XFS_MIN_SECTORSIZE      (1 << XFS_MIN_SECTORSIZE_LOG)
 110 #define XFS_MAX_SECTORSIZE      (1 << XFS_MAX_SECTORSIZE_LOG)
 111
 112 /*
 113  * Block numbers in the AG:
 114  * SB is sector 0, AGF is sector 1, AGI is sector 2, AGFL is sector 3.
 115  */
 116 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_BNO_BLOCK)
 117 xfs_agblock_t xfs_bno_block(struct xfs_mount *mp);
 118 #define XFS_BNO_BLOCK(mp)       xfs_bno_block(mp)
 119 #else
 120 #define XFS_BNO_BLOCK(mp)       ((xfs_agblock_t)(XFS_AGFL_BLOCK(mp) + 1))
 121 #endif
 122 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_CNT_BLOCK)
 123 xfs_agblock_t xfs_cnt_block(struct xfs_mount *mp);
 124 #define XFS_CNT_BLOCK(mp)       xfs_cnt_block(mp)
 125 #else
 126 #define XFS_CNT_BLOCK(mp)       ((xfs_agblock_t)(XFS_BNO_BLOCK(mp) + 1))
 127 #endif
 128
 129 /*
 130  * Record, key, and pointer address macros for btree blocks.
 131  */
 132 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_REC_ADDR)
 133 xfs_alloc_rec_t *xfs_alloc_rec_addr(xfs_alloc_block_t *bb, int i,
 134                                     struct xfs_btree_cur *cur);
 135 #define XFS_ALLOC_REC_ADDR(bb,i,cur)    xfs_alloc_rec_addr(bb,i,cur)
 136 #else
 137 #define XFS_ALLOC_REC_ADDR(bb,i,cur)    \
 138         XFS_BTREE_REC_ADDR(XFS_ALLOC_BLOCK_SIZE(0,cur), xfs_alloc, bb, i, \
 139                 XFS_ALLOC_BLOCK_MAXRECS(0, cur))
 140 #endif
 141
 142 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_KEY_ADDR)
 143 xfs_alloc_key_t *xfs_alloc_key_addr(xfs_alloc_block_t *bb, int i,
 144                                     struct xfs_btree_cur *cur);
 145 #define XFS_ALLOC_KEY_ADDR(bb,i,cur)    xfs_alloc_key_addr(bb,i,cur)
 146 #else
 147 #define XFS_ALLOC_KEY_ADDR(bb,i,cur)    \
 148         XFS_BTREE_KEY_ADDR(XFS_ALLOC_BLOCK_SIZE(1,cur), xfs_alloc, bb, i, \
 149                 XFS_ALLOC_BLOCK_MAXRECS(1, cur))
 150 #endif
 151
 152 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ALLOC_PTR_ADDR)
 153 xfs_alloc_ptr_t *xfs_alloc_ptr_addr(xfs_alloc_block_t *bb, int i,
 154                                     struct xfs_btree_cur *cur);
 155 #define XFS_ALLOC_PTR_ADDR(bb,i,cur)    xfs_alloc_ptr_addr(bb,i,cur)
 156 #else
 157 #define XFS_ALLOC_PTR_ADDR(bb,i,cur)    \
 158         XFS_BTREE_PTR_ADDR(XFS_ALLOC_BLOCK_SIZE(1,cur), xfs_alloc, bb, i, \
 159                 XFS_ALLOC_BLOCK_MAXRECS(1, cur))
 160 #endif
 161
 162 /*
 163  * Prototypes for externally visible routines.
 164  */
 165
 166 /*
 167  * Decrement cursor by one record at the level.
 168  * For nonzero levels the leaf-ward information is untouched.
 169  */
 170 int                                     /* error */
 171 xfs_alloc_decrement(
 172         struct xfs_btree_cur    *cur,   /* btree cursor */
 173         int                     level,  /* level in btree, 0 is leaf */
 174         int                     *stat); /* success/failure */
 175
 176 /*
 177  * Delete the record pointed to by cur.
 178  * The cursor refers to the place where the record was (could be inserted)
 179  * when the operation returns.
 180  */
 181 int                                     /* error */
 182 xfs_alloc_delete(
 183         struct xfs_btree_cur    *cur,   /* btree cursor */
 184         int                     *stat); /* success/failure */
 185
 186 /*
 187  * Get the data from the pointed-to record.
 188  */
 189 int                                     /* error */
 190 xfs_alloc_get_rec(
 191         struct xfs_btree_cur    *cur,   /* btree cursor */
 192         xfs_agblock_t           *bno,   /* output: starting block of extent */
 193         xfs_extlen_t            *len,   /* output: length of extent */
 194         int                     *stat); /* output: success/failure */
 195
 196 /*
 197  * Increment cursor by one record at the level.
 198  * For nonzero levels the leaf-ward information is untouched.
 199  */
 200 int                                     /* error */
 201 xfs_alloc_increment(
 202         struct xfs_btree_cur    *cur,   /* btree cursor */
 203         int                     level,  /* level in btree, 0 is leaf */
 204         int                     *stat); /* success/failure */
 205
 206 /*
 207  * Insert the current record at the point referenced by cur.
 208  * The cursor may be inconsistent on return if splits have been done.
 209  */
 210 int                                     /* error */
 211 xfs_alloc_insert(
 212         struct xfs_btree_cur    *cur,   /* btree cursor */
 213         int                     *stat); /* success/failure */
 214
 215 /*
 216  * Lookup the record equal to [bno, len] in the btree given by cur.
 217  */
 218 int                                     /* error */
 219 xfs_alloc_lookup_eq(
 220         struct xfs_btree_cur    *cur,   /* btree cursor */
 221         xfs_agblock_t           bno,    /* starting block of extent */
 222         xfs_extlen_t            len,    /* length of extent */
 223         int                     *stat); /* success/failure */
 224
 225 /*
 226  * Lookup the first record greater than or equal to [bno, len]
 227  * in the btree given by cur.
 228  */
 229 int                                     /* error */
 230 xfs_alloc_lookup_ge(
 231         struct xfs_btree_cur    *cur,   /* btree cursor */
 232         xfs_agblock_t           bno,    /* starting block of extent */
 233         xfs_extlen_t            len,    /* length of extent */
 234         int                     *stat); /* success/failure */
 235
 236 /*
 237  * Lookup the first record less than or equal to [bno, len]
 238  * in the btree given by cur.
 239  */
 240 int                                     /* error */
 241 xfs_alloc_lookup_le(
 242         struct xfs_btree_cur    *cur,   /* btree cursor */
 243         xfs_agblock_t           bno,    /* starting block of extent */
 244         xfs_extlen_t            len,    /* length of extent */
 245         int                     *stat); /* success/failure */
 246
 247 /*
 248  * Update the record referred to by cur, to the value given by [bno, len].
 249  * This either works (return 0) or gets an EFSCORRUPTED error.
 250  */
 251 int                                     /* error */
 252 xfs_alloc_update(
 253         struct xfs_btree_cur    *cur,   /* btree cursor */
 254         xfs_agblock_t           bno,    /* starting block of extent */
 255         xfs_extlen_t            len);   /* length of extent */
 256
 257 #endif  /* __XFS_ALLOC_BTREE_H__ */