1/* 2 * Copyright (c) 2000,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#ifndef __XFS_IALLOC_BTREE_H__ 19#define __XFS_IALLOC_BTREE_H__ 20 21/* 22 * Inode map on-disk structures 23 */ 24 25struct xfs_buf; 26struct xfs_btree_cur; 27struct xfs_btree_sblock; 28struct xfs_mount; 29 30/* 31 * There is a btree for the inode map per allocation group. 32 */ 33#define XFS_IBT_MAGIC 0x49414254 /* 'IABT' */ 34 35typedef __uint64_t xfs_inofree_t; 36#define XFS_INODES_PER_CHUNK (NBBY * sizeof(xfs_inofree_t)) 37#define XFS_INODES_PER_CHUNK_LOG (XFS_NBBYLOG + 3) 38#define XFS_INOBT_ALL_FREE ((xfs_inofree_t)-1) 39 40#define XFS_INOBT_MASKN(i,n) xfs_inobt_maskn(i,n) 41static inline xfs_inofree_t xfs_inobt_maskn(int i, int n) 42{ 43 return (((n) >= XFS_INODES_PER_CHUNK ? \ 44 (xfs_inofree_t)0 : ((xfs_inofree_t)1 << (n))) - 1) << (i); 45} 46 47/* 48 * Data record structure 49 */ 50typedef struct xfs_inobt_rec { 51 __be32 ir_startino; /* starting inode number */ 52 __be32 ir_freecount; /* count of free inodes (set bits) */ 53 __be64 ir_free; /* free inode mask */ 54} xfs_inobt_rec_t; 55 56typedef struct xfs_inobt_rec_incore { 57 xfs_agino_t ir_startino; /* starting inode number */ 58 __int32_t ir_freecount; /* count of free inodes (set bits) */ 59 xfs_inofree_t ir_free; /* free inode mask */ 60} xfs_inobt_rec_incore_t; 61 62 63/* 64 * Key structure 65 */ 66typedef struct xfs_inobt_key { 67 __be32 ir_startino; /* starting inode number */ 68} xfs_inobt_key_t; 69 70/* btree pointer type */ 71typedef __be32 xfs_inobt_ptr_t; 72 73/* btree block header type */ 74typedef struct xfs_btree_sblock xfs_inobt_block_t; 75 76#define XFS_BUF_TO_INOBT_BLOCK(bp) ((xfs_inobt_block_t *)XFS_BUF_PTR(bp)) 77 78/* 79 * Bit manipulations for ir_free. 80 */ 81#define XFS_INOBT_MASK(i) ((xfs_inofree_t)1 << (i)) 82#define XFS_INOBT_IS_FREE(rp,i) \ 83 (((rp)->ir_free & XFS_INOBT_MASK(i)) != 0) 84#define XFS_INOBT_IS_FREE_DISK(rp,i) \ 85 ((be64_to_cpu((rp)->ir_free) & XFS_INOBT_MASK(i)) != 0) 86#define XFS_INOBT_SET_FREE(rp,i) ((rp)->ir_free |= XFS_INOBT_MASK(i)) 87#define XFS_INOBT_CLR_FREE(rp,i) ((rp)->ir_free &= ~XFS_INOBT_MASK(i)) 88 89/* 90 * Real block structures have a size equal to the disk block size. 91 */ 92#define XFS_INOBT_BLOCK_MAXRECS(lev,cur) ((cur)->bc_mp->m_inobt_mxr[lev != 0]) 93#define XFS_INOBT_BLOCK_MINRECS(lev,cur) ((cur)->bc_mp->m_inobt_mnr[lev != 0]) 94#define XFS_INOBT_IS_LAST_REC(cur) \ 95 ((cur)->bc_ptrs[0] == be16_to_cpu(XFS_BUF_TO_INOBT_BLOCK((cur)->bc_bufs[0])->bb_numrecs)) 96 97/* 98 * Maximum number of inode btree levels. 99 */ 100#define XFS_IN_MAXLEVELS(mp) ((mp)->m_in_maxlevels) 101 102/* 103 * block numbers in the AG. 104 */ 105#define XFS_IBT_BLOCK(mp) ((xfs_agblock_t)(XFS_CNT_BLOCK(mp) + 1)) 106#define XFS_PREALLOC_BLOCKS(mp) ((xfs_agblock_t)(XFS_IBT_BLOCK(mp) + 1)) 107 108/* 109 * Record, key, and pointer address macros for btree blocks. 110 */ 111#define XFS_INOBT_REC_ADDR(bb,i,cur) \ 112 (XFS_BTREE_REC_ADDR(xfs_inobt, bb, i)) 113 114#define XFS_INOBT_KEY_ADDR(bb,i,cur) \ 115 (XFS_BTREE_KEY_ADDR(xfs_inobt, bb, i)) 116 117#define XFS_INOBT_PTR_ADDR(bb,i,cur) \ 118 (XFS_BTREE_PTR_ADDR(xfs_inobt, bb, \ 119 i, XFS_INOBT_BLOCK_MAXRECS(1, cur))) 120 121/* 122 * Decrement cursor by one record at the level. 123 * For nonzero levels the leaf-ward information is untouched. 124 */ 125extern int xfs_inobt_decrement(struct xfs_btree_cur *cur, int level, int *stat); 126 127/* 128 * Delete the record pointed to by cur. 129 * The cursor refers to the place where the record was (could be inserted) 130 * when the operation returns. 131 */ 132extern int xfs_inobt_delete(struct xfs_btree_cur *cur, int *stat); 133 134/* 135 * Get the data from the pointed-to record. 136 */ 137extern int xfs_inobt_get_rec(struct xfs_btree_cur *cur, xfs_agino_t *ino, 138 __int32_t *fcnt, xfs_inofree_t *free, int *stat); 139 140/* 141 * Increment cursor by one record at the level. 142 * For nonzero levels the leaf-ward information is untouched. 143 */ 144extern int xfs_inobt_increment(struct xfs_btree_cur *cur, int level, int *stat); 145 146/* 147 * Insert the current record at the point referenced by cur. 148 * The cursor may be inconsistent on return if splits have been done. 149 */ 150extern int xfs_inobt_insert(struct xfs_btree_cur *cur, int *stat); 151 152/* 153 * Lookup the record equal to ino in the btree given by cur. 154 */ 155extern int xfs_inobt_lookup_eq(struct xfs_btree_cur *cur, xfs_agino_t ino, 156 __int32_t fcnt, xfs_inofree_t free, int *stat); 157 158/* 159 * Lookup the first record greater than or equal to ino 160 * in the btree given by cur. 161 */ 162extern int xfs_inobt_lookup_ge(struct xfs_btree_cur *cur, xfs_agino_t ino, 163 __int32_t fcnt, xfs_inofree_t free, int *stat); 164 165/* 166 * Lookup the first record less than or equal to ino 167 * in the btree given by cur. 168 */ 169extern int xfs_inobt_lookup_le(struct xfs_btree_cur *cur, xfs_agino_t ino, 170 __int32_t fcnt, xfs_inofree_t free, int *stat); 171 172/* 173 * Update the record referred to by cur, to the value given 174 * by [ino, fcnt, free]. 175 * This either works (return 0) or gets an EFSCORRUPTED error. 176 */ 177extern int xfs_inobt_update(struct xfs_btree_cur *cur, xfs_agino_t ino, 178 __int32_t fcnt, xfs_inofree_t free); 179 180#endif /* __XFS_IALLOC_BTREE_H__ */ 181