2 * Copyright (c) 2000-2001 Silicon Graphics, Inc. All Rights Reserved.
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.
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.
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.
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.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
32 #ifndef __XFS_BTREE_H__
33 #define __XFS_BTREE_H__
42 * This nonsense is to make -wlint happy.
44 #define XFS_LOOKUP_EQ ((xfs_lookup_t)XFS_LOOKUP_EQi)
45 #define XFS_LOOKUP_LE ((xfs_lookup_t)XFS_LOOKUP_LEi)
46 #define XFS_LOOKUP_GE ((xfs_lookup_t)XFS_LOOKUP_GEi)
48 #define XFS_BTNUM_BNO ((xfs_btnum_t)XFS_BTNUM_BNOi)
49 #define XFS_BTNUM_CNT ((xfs_btnum_t)XFS_BTNUM_CNTi)
50 #define XFS_BTNUM_BMAP ((xfs_btnum_t)XFS_BTNUM_BMAPi)
51 #define XFS_BTNUM_INO ((xfs_btnum_t)XFS_BTNUM_INOi)
54 * Short form header: space allocation btrees.
56 typedef struct xfs_btree_sblock
58 __uint32_t bb_magic
; /* magic number for block type */
59 __uint16_t bb_level
; /* 0 is a leaf */
60 __uint16_t bb_numrecs
; /* current # of data records */
61 xfs_agblock_t bb_leftsib
; /* left sibling block or NULLAGBLOCK */
62 xfs_agblock_t bb_rightsib
; /* right sibling block or NULLAGBLOCK */
66 * Long form header: bmap btrees.
68 typedef struct xfs_btree_lblock
70 __uint32_t bb_magic
; /* magic number for block type */
71 __uint16_t bb_level
; /* 0 is a leaf */
72 __uint16_t bb_numrecs
; /* current # of data records */
73 xfs_dfsbno_t bb_leftsib
; /* left sibling block or NULLDFSBNO */
74 xfs_dfsbno_t bb_rightsib
; /* right sibling block or NULLDFSBNO */
78 * Combined header and structure, used by common code.
80 typedef struct xfs_btree_hdr
82 __uint32_t bb_magic
; /* magic number for block type */
83 __uint16_t bb_level
; /* 0 is a leaf */
84 __uint16_t bb_numrecs
; /* current # of data records */
87 typedef struct xfs_btree_block
89 xfs_btree_hdr_t bb_h
; /* header */
92 xfs_agblock_t bb_leftsib
;
93 xfs_agblock_t bb_rightsib
;
94 } s
; /* short form pointers */
96 xfs_dfsbno_t bb_leftsib
;
97 xfs_dfsbno_t bb_rightsib
;
98 } l
; /* long form pointers */
103 * For logging record fields.
105 #define XFS_BB_MAGIC 0x01
106 #define XFS_BB_LEVEL 0x02
107 #define XFS_BB_NUMRECS 0x04
108 #define XFS_BB_LEFTSIB 0x08
109 #define XFS_BB_RIGHTSIB 0x10
110 #define XFS_BB_NUM_BITS 5
111 #define XFS_BB_ALL_BITS ((1 << XFS_BB_NUM_BITS) - 1)
114 * Boolean to select which form of xfs_btree_block_t.bb_u to use.
116 #define XFS_BTREE_LONG_PTRS(btnum) ((btnum) == XFS_BTNUM_BMAP)
119 * Magic numbers for btree blocks.
121 extern const __uint32_t xfs_magics
[];
124 * Maximum and minimum records in a btree block.
125 * Given block size, type prefix, and leaf flag (0 or 1).
126 * The divisor below is equivalent to lf ? (e1) : (e2) but that produces
129 #define XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf) \
130 ((int)(((bsz) - (uint)sizeof(t ## _block_t)) / \
131 (((lf) * (uint)sizeof(t ## _rec_t)) + \
133 ((uint)sizeof(t ## _key_t) + (uint)sizeof(t ## _ptr_t))))))
134 #define XFS_BTREE_BLOCK_MINRECS(bsz,t,lf) \
135 (XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf) / 2)
138 * Record, key, and pointer address calculation macros.
139 * Given block size, type prefix, block pointer, and index of requested entry
140 * (first entry numbered 1).
142 #define XFS_BTREE_REC_ADDR(bsz,t,bb,i,mxr) \
143 ((t ## _rec_t *)((char *)(bb) + sizeof(t ## _block_t) + \
144 ((i) - 1) * sizeof(t ## _rec_t)))
145 #define XFS_BTREE_KEY_ADDR(bsz,t,bb,i,mxr) \
146 ((t ## _key_t *)((char *)(bb) + sizeof(t ## _block_t) + \
147 ((i) - 1) * sizeof(t ## _key_t)))
148 #define XFS_BTREE_PTR_ADDR(bsz,t,bb,i,mxr) \
149 ((t ## _ptr_t *)((char *)(bb) + sizeof(t ## _block_t) + \
150 (mxr) * sizeof(t ## _key_t) + ((i) - 1) * sizeof(t ## _ptr_t)))
152 #define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */
155 * Btree cursor structure.
156 * This collects all information needed by the btree code in one place.
158 typedef struct xfs_btree_cur
160 struct xfs_trans
*bc_tp
; /* transaction we're in, if any */
161 struct xfs_mount
*bc_mp
; /* file system mount struct */
166 } bc_rec
; /* current insert/search record value */
167 struct xfs_buf
*bc_bufs
[XFS_BTREE_MAXLEVELS
]; /* buf ptr per level */
168 int bc_ptrs
[XFS_BTREE_MAXLEVELS
]; /* key/record # */
169 __uint8_t bc_ra
[XFS_BTREE_MAXLEVELS
]; /* readahead bits */
170 #define XFS_BTCUR_LEFTRA 1 /* left sibling has been read-ahead */
171 #define XFS_BTCUR_RIGHTRA 2 /* right sibling has been read-ahead */
172 __uint8_t bc_nlevels
; /* number of levels in the tree */
173 __uint8_t bc_blocklog
; /* log2(blocksize) of btree blocks */
174 xfs_btnum_t bc_btnum
; /* identifies which btree type */
176 struct { /* needed for BNO, CNT */
177 struct xfs_buf
*agbp
; /* agf buffer pointer */
178 xfs_agnumber_t agno
; /* ag number */
180 struct { /* needed for BMAP */
181 struct xfs_inode
*ip
; /* pointer to our inode */
182 struct xfs_bmap_free
*flist
; /* list to free after */
183 xfs_fsblock_t firstblock
; /* 1st blk allocated */
184 int allocated
; /* count of alloced */
185 short forksize
; /* fork's inode space */
186 char whichfork
; /* data or attr fork */
187 char flags
; /* flags */
188 #define XFS_BTCUR_BPRV_WASDEL 1 /* was delayed */
190 struct { /* needed for INO */
191 struct xfs_buf
*agbp
; /* agi buffer pointer */
192 xfs_agnumber_t agno
; /* ag number */
194 } bc_private
; /* per-btree type data */
197 #define XFS_BTREE_NOERROR 0
198 #define XFS_BTREE_ERROR 1
201 * Convert from buffer to btree block header.
203 #define XFS_BUF_TO_BLOCK(bp) ((xfs_btree_block_t *)XFS_BUF_PTR(bp))
204 #define XFS_BUF_TO_LBLOCK(bp) ((xfs_btree_lblock_t *)XFS_BUF_PTR(bp))
205 #define XFS_BUF_TO_SBLOCK(bp) ((xfs_btree_sblock_t *)XFS_BUF_PTR(bp))
212 * Debug routine: check that block header is ok.
215 xfs_btree_check_block(
216 xfs_btree_cur_t
*cur
, /* btree cursor */
217 xfs_btree_block_t
*block
, /* generic btree block pointer */
218 int level
, /* level of the btree block */
219 struct xfs_buf
*bp
); /* buffer containing block, if any */
222 * Debug routine: check that keys are in the right order.
226 xfs_btnum_t btnum
, /* btree identifier */
227 void *ak1
, /* pointer to left (lower) key */
228 void *ak2
); /* pointer to right (higher) key */
231 * Debug routine: check that records are in the right order.
235 xfs_btnum_t btnum
, /* btree identifier */
236 void *ar1
, /* pointer to left (lower) record */
237 void *ar2
); /* pointer to right (higher) record */
239 #define xfs_btree_check_block(a,b,c,d)
240 #define xfs_btree_check_key(a,b,c)
241 #define xfs_btree_check_rec(a,b,c)
245 * Checking routine: check that long form block header is ok.
247 int /* error (0 or EFSCORRUPTED) */
248 xfs_btree_check_lblock(
249 xfs_btree_cur_t
*cur
, /* btree cursor */
250 xfs_btree_lblock_t
*block
, /* btree long form block pointer */
251 int level
, /* level of the btree block */
252 struct xfs_buf
*bp
); /* buffer containing block, if any */
255 * Checking routine: check that (long) pointer is ok.
257 int /* error (0 or EFSCORRUPTED) */
258 xfs_btree_check_lptr(
259 xfs_btree_cur_t
*cur
, /* btree cursor */
260 xfs_dfsbno_t ptr
, /* btree block disk address */
261 int level
); /* btree block level */
264 * Checking routine: check that short form block header is ok.
266 int /* error (0 or EFSCORRUPTED) */
267 xfs_btree_check_sblock(
268 xfs_btree_cur_t
*cur
, /* btree cursor */
269 xfs_btree_sblock_t
*block
, /* btree short form block pointer */
270 int level
, /* level of the btree block */
271 struct xfs_buf
*bp
); /* buffer containing block */
274 * Checking routine: check that (short) pointer is ok.
276 int /* error (0 or EFSCORRUPTED) */
277 xfs_btree_check_sptr(
278 xfs_btree_cur_t
*cur
, /* btree cursor */
279 xfs_agblock_t ptr
, /* btree block disk address */
280 int level
); /* btree block level */
283 * Delete the btree cursor.
286 xfs_btree_del_cursor(
287 xfs_btree_cur_t
*cur
, /* btree cursor */
288 int error
); /* del because of error */
291 * Duplicate the btree cursor.
292 * Allocate a new one, copy the record, re-get the buffers.
295 xfs_btree_dup_cursor(
296 xfs_btree_cur_t
*cur
, /* input cursor */
297 xfs_btree_cur_t
**ncur
);/* output cursor */
300 * Change the cursor to point to the first record in the current block
301 * at the given level. Other levels are unaffected.
303 int /* success=1, failure=0 */
305 xfs_btree_cur_t
*cur
, /* btree cursor */
306 int level
); /* level to change */
309 * Get a buffer for the block, return it with no data read.
310 * Long-form addressing.
312 struct xfs_buf
* /* buffer for fsbno */
314 struct xfs_mount
*mp
, /* file system mount point */
315 struct xfs_trans
*tp
, /* transaction pointer */
316 xfs_fsblock_t fsbno
, /* file system block number */
317 uint lock
); /* lock flags for get_buf */
320 * Get a buffer for the block, return it with no data read.
321 * Short-form addressing.
323 struct xfs_buf
* /* buffer for agno/agbno */
325 struct xfs_mount
*mp
, /* file system mount point */
326 struct xfs_trans
*tp
, /* transaction pointer */
327 xfs_agnumber_t agno
, /* allocation group number */
328 xfs_agblock_t agbno
, /* allocation group block number */
329 uint lock
); /* lock flags for get_buf */
332 * Allocate a new btree cursor.
333 * The cursor is either for allocation (A) or bmap (B).
335 xfs_btree_cur_t
* /* new btree cursor */
336 xfs_btree_init_cursor(
337 struct xfs_mount
*mp
, /* file system mount point */
338 struct xfs_trans
*tp
, /* transaction pointer */
339 struct xfs_buf
*agbp
, /* (A only) buffer for agf structure */
340 xfs_agnumber_t agno
, /* (A only) allocation group number */
341 xfs_btnum_t btnum
, /* btree identifier */
342 struct xfs_inode
*ip
, /* (B only) inode owning the btree */
343 int whichfork
); /* (B only) data/attr fork */
346 * Check for the cursor referring to the last block at the given level.
348 int /* 1=is last block, 0=not last block */
349 xfs_btree_islastblock(
350 xfs_btree_cur_t
*cur
, /* btree cursor */
351 int level
); /* level to check */
354 * Change the cursor to point to the last record in the current block
355 * at the given level. Other levels are unaffected.
357 int /* success=1, failure=0 */
359 xfs_btree_cur_t
*cur
, /* btree cursor */
360 int level
); /* level to change */
363 * Compute first and last byte offsets for the fields given.
364 * Interprets the offsets table, which contains struct field offsets.
368 __int64_t fields
, /* bitmask of fields */
369 const short *offsets
,/* table of field offsets */
370 int nbits
, /* number of bits to inspect */
371 int *first
, /* output: first byte offset */
372 int *last
); /* output: last byte offset */
375 * Get a buffer for the block, return it read in.
376 * Long-form addressing.
380 struct xfs_mount
*mp
, /* file system mount point */
381 struct xfs_trans
*tp
, /* transaction pointer */
382 xfs_fsblock_t fsbno
, /* file system block number */
383 uint lock
, /* lock flags for read_buf */
384 struct xfs_buf
**bpp
, /* buffer for fsbno */
385 int refval
);/* ref count value for buffer */
388 * Get a buffer for the block, return it read in.
389 * Short-form addressing.
393 struct xfs_mount
*mp
, /* file system mount point */
394 struct xfs_trans
*tp
, /* transaction pointer */
395 xfs_agnumber_t agno
, /* allocation group number */
396 xfs_agblock_t agbno
, /* allocation group block number */
397 uint lock
, /* lock flags for read_buf */
398 struct xfs_buf
**bpp
, /* buffer for agno/agbno */
399 int refval
);/* ref count value for buffer */
402 * Read-ahead the block, don't wait for it, don't return a buffer.
403 * Long-form addressing.
406 xfs_btree_reada_bufl(
407 struct xfs_mount
*mp
, /* file system mount point */
408 xfs_fsblock_t fsbno
, /* file system block number */
409 xfs_extlen_t count
); /* count of filesystem blocks */
412 * Read-ahead the block, don't wait for it, don't return a buffer.
413 * Short-form addressing.
416 xfs_btree_reada_bufs(
417 struct xfs_mount
*mp
, /* file system mount point */
418 xfs_agnumber_t agno
, /* allocation group number */
419 xfs_agblock_t agbno
, /* allocation group block number */
420 xfs_extlen_t count
); /* count of filesystem blocks */
423 * Read-ahead btree blocks, at the given level.
424 * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
426 int /* readahead block count */
427 xfs_btree_readahead_core(
428 xfs_btree_cur_t
*cur
, /* btree cursor */
429 int lev
, /* level in btree */
430 int lr
); /* left/right bits */
432 static inline int /* readahead block count */
434 xfs_btree_cur_t
*cur
, /* btree cursor */
435 int lev
, /* level in btree */
436 int lr
) /* left/right bits */
438 if ((cur
->bc_ra
[lev
] | lr
) == cur
->bc_ra
[lev
])
441 return xfs_btree_readahead_core(cur
, lev
, lr
);
446 * Set the buffer for level "lev" in the cursor to bp, releasing
447 * any previous buffer.
451 xfs_btree_cur_t
*cur
, /* btree cursor */
452 int lev
, /* level in btree */
453 struct xfs_buf
*bp
); /* new buffer to set */
455 #endif /* __KERNEL__ */
459 * Min and max functions for extlen, agblock, fileoff, and filblks types.
461 #define XFS_EXTLEN_MIN(a,b) \
462 ((xfs_extlen_t)(a) < (xfs_extlen_t)(b) ? \
463 (xfs_extlen_t)(a) : (xfs_extlen_t)(b))
464 #define XFS_EXTLEN_MAX(a,b) \
465 ((xfs_extlen_t)(a) > (xfs_extlen_t)(b) ? \
466 (xfs_extlen_t)(a) : (xfs_extlen_t)(b))
467 #define XFS_AGBLOCK_MIN(a,b) \
468 ((xfs_agblock_t)(a) < (xfs_agblock_t)(b) ? \
469 (xfs_agblock_t)(a) : (xfs_agblock_t)(b))
470 #define XFS_AGBLOCK_MAX(a,b) \
471 ((xfs_agblock_t)(a) > (xfs_agblock_t)(b) ? \
472 (xfs_agblock_t)(a) : (xfs_agblock_t)(b))
473 #define XFS_FILEOFF_MIN(a,b) \
474 ((xfs_fileoff_t)(a) < (xfs_fileoff_t)(b) ? \
475 (xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
476 #define XFS_FILEOFF_MAX(a,b) \
477 ((xfs_fileoff_t)(a) > (xfs_fileoff_t)(b) ? \
478 (xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
479 #define XFS_FILBLKS_MIN(a,b) \
480 ((xfs_filblks_t)(a) < (xfs_filblks_t)(b) ? \
481 (xfs_filblks_t)(a) : (xfs_filblks_t)(b))
482 #define XFS_FILBLKS_MAX(a,b) \
483 ((xfs_filblks_t)(a) > (xfs_filblks_t)(b) ? \
484 (xfs_filblks_t)(a) : (xfs_filblks_t)(b))
486 #define XFS_FSB_SANITY_CHECK(mp,fsb) \
487 (XFS_FSB_TO_AGNO(mp, fsb) < mp->m_sb.sb_agcount && \
488 XFS_FSB_TO_AGBNO(mp, fsb) < mp->m_sb.sb_agblocks)
490 #endif /* __XFS_BTREE_H__ */