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_IALLOC_BTREE_H__ 33 #define __XFS_IALLOC_BTREE_H__ 34 35 /* 36 * Inode map 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 is a btree for the inode map per allocation group. 46 */ 47 #define XFS_IBT_MAGIC 0x49414254 /* 'IABT' */ 48 49 typedef __uint64_t xfs_inofree_t; 50 #define XFS_INODES_PER_CHUNK (NBBY * sizeof(xfs_inofree_t)) 51 #define XFS_INODES_PER_CHUNK_LOG (XFS_NBBYLOG + 3) 52 #define XFS_INOBT_ALL_FREE ((xfs_inofree_t)-1) 53 54 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_MASKN) 55 xfs_inofree_t xfs_inobt_maskn(int i, int n); 56 #define XFS_INOBT_MASKN(i,n) xfs_inobt_maskn(i,n) 57 #else 58 #define XFS_INOBT_MASKN(i,n) \ 59 ((((n) >= XFS_INODES_PER_CHUNK ? \ 60 (xfs_inofree_t)0 : ((xfs_inofree_t)1 << (n))) - 1) << (i)) 61 #endif 62 63 /* 64 * Data record structure 65 */ 66 typedef struct xfs_inobt_rec 67 { 68 xfs_agino_t ir_startino; /* starting inode number */ 69 __int32_t ir_freecount; /* count of free inodes (set bits) */ 70 xfs_inofree_t ir_free; /* free inode mask */ 71 } xfs_inobt_rec_t; 72 73 /* 74 * Key structure 75 */ 76 typedef struct xfs_inobt_key 77 { 78 xfs_agino_t ir_startino; /* starting inode number */ 79 } xfs_inobt_key_t; 80 81 typedef xfs_agblock_t xfs_inobt_ptr_t; /* btree pointer type */ 82 /* btree block header type */ 83 typedef struct xfs_btree_sblock xfs_inobt_block_t; 84 85 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_BUF_TO_INOBT_BLOCK) 86 xfs_inobt_block_t *xfs_buf_to_inobt_block(struct xfs_buf *bp); 87 #define XFS_BUF_TO_INOBT_BLOCK(bp) xfs_buf_to_inobt_block(bp) 88 #else 89 #define XFS_BUF_TO_INOBT_BLOCK(bp) ((xfs_inobt_block_t *)(XFS_BUF_PTR(bp))) 90 #endif 91 92 /* 93 * Bit manipulations for ir_free. 94 */ 95 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_MASK) 96 xfs_inofree_t xfs_inobt_mask(int i); 97 #define XFS_INOBT_MASK(i) xfs_inobt_mask(i) 98 #else 99 #define XFS_INOBT_MASK(i) ((xfs_inofree_t)1 << (i)) 100 #endif 101 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_IS_FREE) 102 int xfs_inobt_is_free(xfs_inobt_rec_t *rp, int i, xfs_arch_t arch); 103 #define XFS_INOBT_IS_FREE(rp,i,arch) xfs_inobt_is_free(rp,i,arch) 104 #else 105 #define XFS_INOBT_IS_FREE(rp,i,arch) ((INT_GET((rp)->ir_free, arch) \ 106 & XFS_INOBT_MASK(i)) != 0) 107 #endif 108 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_SET_FREE) 109 void xfs_inobt_set_free(xfs_inobt_rec_t *rp, int i, xfs_arch_t arch); 110 #define XFS_INOBT_SET_FREE(rp,i,arch) xfs_inobt_set_free(rp,i,arch) 111 #else 112 #define XFS_INOBT_SET_FREE(rp,i,arch) (INT_MOD_EXPR((rp)->ir_free, arch, |= XFS_INOBT_MASK(i))) 113 #endif 114 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_CLR_FREE) 115 void xfs_inobt_clr_free(xfs_inobt_rec_t *rp, int i, xfs_arch_t arch); 116 #define XFS_INOBT_CLR_FREE(rp,i,arch) xfs_inobt_clr_free(rp,i,arch) 117 #else 118 #define XFS_INOBT_CLR_FREE(rp,i,arch) (INT_MOD_EXPR((rp)->ir_free, arch, &= ~XFS_INOBT_MASK(i))) 119 #endif 120 121 /* 122 * Real block structures have a size equal to the disk block size. 123 */ 124 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_BLOCK_SIZE) 125 int xfs_inobt_block_size(int lev, struct xfs_btree_cur *cur); 126 #define XFS_INOBT_BLOCK_SIZE(lev,cur) xfs_inobt_block_size(lev,cur) 127 #else 128 #define XFS_INOBT_BLOCK_SIZE(lev,cur) (1 << (cur)->bc_blocklog) 129 #endif 130 131 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_BLOCK_MAXRECS) 132 int xfs_inobt_block_maxrecs(int lev, struct xfs_btree_cur *cur); 133 #define XFS_INOBT_BLOCK_MAXRECS(lev,cur) xfs_inobt_block_maxrecs(lev,cur) 134 #else 135 #define XFS_INOBT_BLOCK_MAXRECS(lev,cur) \ 136 ((cur)->bc_mp->m_inobt_mxr[lev != 0]) 137 #endif 138 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_BLOCK_MINRECS) 139 int xfs_inobt_block_minrecs(int lev, struct xfs_btree_cur *cur); 140 #define XFS_INOBT_BLOCK_MINRECS(lev,cur) xfs_inobt_block_minrecs(lev,cur) 141 #else 142 #define XFS_INOBT_BLOCK_MINRECS(lev,cur) \ 143 ((cur)->bc_mp->m_inobt_mnr[lev != 0]) 144 #endif 145 146 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_IS_LAST_REC) 147 int xfs_inobt_is_last_rec(struct xfs_btree_cur *cur); 148 #define XFS_INOBT_IS_LAST_REC(cur) xfs_inobt_is_last_rec(cur) 149 #else 150 #define XFS_INOBT_IS_LAST_REC(cur) \ 151 ((cur)->bc_ptrs[0] == \ 152 INT_GET(XFS_BUF_TO_INOBT_BLOCK((cur)->bc_bufs[0])->bb_numrecs, ARCH_CONVERT)) 153 #endif 154 155 /* 156 * Maximum number of inode btree levels. 157 */ 158 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_IN_MAXLEVELS) 159 int xfs_in_maxlevels(struct xfs_mount *mp); 160 #define XFS_IN_MAXLEVELS(mp) xfs_in_maxlevels(mp) 161 #else 162 #define XFS_IN_MAXLEVELS(mp) ((mp)->m_in_maxlevels) 163 #endif 164 165 /* 166 * block numbers in the AG. 167 */ 168 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_IBT_BLOCK) 169 xfs_agblock_t xfs_ibt_block(struct xfs_mount *mp); 170 #define XFS_IBT_BLOCK(mp) xfs_ibt_block(mp) 171 #else 172 #define XFS_IBT_BLOCK(mp) ((xfs_agblock_t)(XFS_CNT_BLOCK(mp) + 1)) 173 #endif 174 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_PREALLOC_BLOCKS) 175 xfs_agblock_t xfs_prealloc_blocks(struct xfs_mount *mp); 176 #define XFS_PREALLOC_BLOCKS(mp) xfs_prealloc_blocks(mp) 177 #else 178 #define XFS_PREALLOC_BLOCKS(mp) ((xfs_agblock_t)(XFS_IBT_BLOCK(mp) + 1)) 179 #endif 180 181 /* 182 * Record, key, and pointer address macros for btree blocks. 183 */ 184 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_REC_ADDR) 185 xfs_inobt_rec_t * 186 xfs_inobt_rec_addr(xfs_inobt_block_t *bb, int i, struct xfs_btree_cur *cur); 187 #define XFS_INOBT_REC_ADDR(bb,i,cur) xfs_inobt_rec_addr(bb,i,cur) 188 #else 189 #define XFS_INOBT_REC_ADDR(bb,i,cur) \ 190 XFS_BTREE_REC_ADDR(XFS_INOBT_BLOCK_SIZE(0,cur), xfs_inobt, bb, i, \ 191 XFS_INOBT_BLOCK_MAXRECS(0, cur)) 192 #endif 193 194 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_KEY_ADDR) 195 xfs_inobt_key_t * 196 xfs_inobt_key_addr(xfs_inobt_block_t *bb, int i, struct xfs_btree_cur *cur); 197 #define XFS_INOBT_KEY_ADDR(bb,i,cur) xfs_inobt_key_addr(bb,i,cur) 198 #else 199 #define XFS_INOBT_KEY_ADDR(bb,i,cur) \ 200 XFS_BTREE_KEY_ADDR(XFS_INOBT_BLOCK_SIZE(1,cur), xfs_inobt, bb, i, \ 201 XFS_INOBT_BLOCK_MAXRECS(1, cur)) 202 #endif 203 204 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_INOBT_PTR_ADDR) 205 xfs_inobt_ptr_t * 206 xfs_inobt_ptr_addr(xfs_inobt_block_t *bb, int i, struct xfs_btree_cur *cur); 207 #define XFS_INOBT_PTR_ADDR(bb,i,cur) xfs_inobt_ptr_addr(bb,i,cur) 208 #else 209 #define XFS_INOBT_PTR_ADDR(bb,i,cur) \ 210 XFS_BTREE_PTR_ADDR(XFS_INOBT_BLOCK_SIZE(1,cur), xfs_inobt, bb, i, \ 211 XFS_INOBT_BLOCK_MAXRECS(1, cur)) 212 #endif 213 214 /* 215 * Prototypes for externally visible routines. 216 */ 217 218 /* 219 * Decrement cursor by one record at the level. 220 * For nonzero levels the leaf-ward information is untouched. 221 */ 222 int /* error */ 223 xfs_inobt_decrement( 224 struct xfs_btree_cur *cur, /* btree cursor */ 225 int level, /* level in btree, 0 is leaf */ 226 int *stat); /* success/failure */ 227 228 /* 229 * Delete the record pointed to by cur. 230 * The cursor refers to the place where the record was (could be inserted) 231 * when the operation returns. 232 */ 233 int /* error */ 234 xfs_inobt_delete( 235 struct xfs_btree_cur *cur, /* btree cursor */ 236 int *stat); /* success/failure */ 237 238 /* 239 * Get the data from the pointed-to record. 240 */ 241 int /* error */ 242 xfs_inobt_get_rec( 243 struct xfs_btree_cur *cur, /* btree cursor */ 244 xfs_agino_t *ino, /* output: starting inode of chunk */ 245 __int32_t *fcnt, /* output: number of free inodes */ 246 xfs_inofree_t *free, /* output: free inode mask */ 247 int *stat, /* output: success/failure */ 248 xfs_arch_t arch); /* output: architecture */ 249 250 /* 251 * Increment cursor by one record at the level. 252 * For nonzero levels the leaf-ward information is untouched. 253 */ 254 int /* error */ 255 xfs_inobt_increment( 256 struct xfs_btree_cur *cur, /* btree cursor */ 257 int level, /* level in btree, 0 is leaf */ 258 int *stat); /* success/failure */ 259 260 /* 261 * Insert the current record at the point referenced by cur. 262 * The cursor may be inconsistent on return if splits have been done. 263 */ 264 int /* error */ 265 xfs_inobt_insert( 266 struct xfs_btree_cur *cur, /* btree cursor */ 267 int *stat); /* success/failure */ 268 269 /* 270 * Lookup the record equal to ino in the btree given by cur. 271 */ 272 int /* error */ 273 xfs_inobt_lookup_eq( 274 struct xfs_btree_cur *cur, /* btree cursor */ 275 xfs_agino_t ino, /* starting inode of chunk */ 276 __int32_t fcnt, /* free inode count */ 277 xfs_inofree_t free, /* free inode mask */ 278 int *stat); /* success/failure */ 279 280 /* 281 * Lookup the first record greater than or equal to ino 282 * in the btree given by cur. 283 */ 284 int /* error */ 285 xfs_inobt_lookup_ge( 286 struct xfs_btree_cur *cur, /* btree cursor */ 287 xfs_agino_t ino, /* starting inode of chunk */ 288 __int32_t fcnt, /* free inode count */ 289 xfs_inofree_t free, /* free inode mask */ 290 int *stat); /* success/failure */ 291 292 /* 293 * Lookup the first record less than or equal to ino 294 * in the btree given by cur. 295 */ 296 int /* error */ 297 xfs_inobt_lookup_le( 298 struct xfs_btree_cur *cur, /* btree cursor */ 299 xfs_agino_t ino, /* starting inode of chunk */ 300 __int32_t fcnt, /* free inode count */ 301 xfs_inofree_t free, /* free inode mask */ 302 int *stat); /* success/failure */ 303 304 /* 305 * Update the record referred to by cur, to the value given 306 * by [ino, fcnt, free]. 307 * This either works (return 0) or gets an EFSCORRUPTED error. 308 */ 309 int /* error */ 310 xfs_inobt_update( 311 struct xfs_btree_cur *cur, /* btree cursor */ 312 xfs_agino_t ino, /* starting inode of chunk */ 313 __int32_t fcnt, /* free inode count */ 314 xfs_inofree_t free); /* free inode mask */ 315 316 #endif /* __XFS_IALLOC_BTREE_H__ */ 317