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__ */ 258