[PATCH] softmac: fix Makefiles
[linux-2.6] / fs / xfs / xfs_btree.h
1 /*
2  * Copyright (c) 2000-2001,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_BTREE_H__
19 #define __XFS_BTREE_H__
20
21 struct xfs_buf;
22 struct xfs_bmap_free;
23 struct xfs_inode;
24 struct xfs_mount;
25 struct xfs_trans;
26
27 /*
28  * This nonsense is to make -wlint happy.
29  */
30 #define XFS_LOOKUP_EQ   ((xfs_lookup_t)XFS_LOOKUP_EQi)
31 #define XFS_LOOKUP_LE   ((xfs_lookup_t)XFS_LOOKUP_LEi)
32 #define XFS_LOOKUP_GE   ((xfs_lookup_t)XFS_LOOKUP_GEi)
33
34 #define XFS_BTNUM_BNO   ((xfs_btnum_t)XFS_BTNUM_BNOi)
35 #define XFS_BTNUM_CNT   ((xfs_btnum_t)XFS_BTNUM_CNTi)
36 #define XFS_BTNUM_BMAP  ((xfs_btnum_t)XFS_BTNUM_BMAPi)
37 #define XFS_BTNUM_INO   ((xfs_btnum_t)XFS_BTNUM_INOi)
38
39 /*
40  * Short form header: space allocation btrees.
41  */
42 typedef struct xfs_btree_sblock {
43         __be32          bb_magic;       /* magic number for block type */
44         __be16          bb_level;       /* 0 is a leaf */
45         __be16          bb_numrecs;     /* current # of data records */
46         __be32          bb_leftsib;     /* left sibling block or NULLAGBLOCK */
47         __be32          bb_rightsib;    /* right sibling block or NULLAGBLOCK */
48 } xfs_btree_sblock_t;
49
50 /*
51  * Long form header: bmap btrees.
52  */
53 typedef struct xfs_btree_lblock {
54         __be32          bb_magic;       /* magic number for block type */
55         __be16          bb_level;       /* 0 is a leaf */
56         __be16          bb_numrecs;     /* current # of data records */
57         __be64          bb_leftsib;     /* left sibling block or NULLDFSBNO */
58         __be64          bb_rightsib;    /* right sibling block or NULLDFSBNO */
59 } xfs_btree_lblock_t;
60
61 /*
62  * Combined header and structure, used by common code.
63  */
64 typedef struct xfs_btree_hdr
65 {
66         __be32          bb_magic;       /* magic number for block type */
67         __be16          bb_level;       /* 0 is a leaf */
68         __be16          bb_numrecs;     /* current # of data records */
69 } xfs_btree_hdr_t;
70
71 typedef struct xfs_btree_block {
72         xfs_btree_hdr_t bb_h;           /* header */
73         union {
74                 struct {
75                         __be32          bb_leftsib;
76                         __be32          bb_rightsib;
77                 } s;                    /* short form pointers */
78                 struct  {
79                         __be64          bb_leftsib;
80                         __be64          bb_rightsib;
81                 } l;                    /* long form pointers */
82         } bb_u;                         /* rest */
83 } xfs_btree_block_t;
84
85 /*
86  * For logging record fields.
87  */
88 #define XFS_BB_MAGIC            0x01
89 #define XFS_BB_LEVEL            0x02
90 #define XFS_BB_NUMRECS          0x04
91 #define XFS_BB_LEFTSIB          0x08
92 #define XFS_BB_RIGHTSIB         0x10
93 #define XFS_BB_NUM_BITS         5
94 #define XFS_BB_ALL_BITS         ((1 << XFS_BB_NUM_BITS) - 1)
95
96 /*
97  * Boolean to select which form of xfs_btree_block_t.bb_u to use.
98  */
99 #define XFS_BTREE_LONG_PTRS(btnum)      ((btnum) == XFS_BTNUM_BMAP)
100
101 /*
102  * Magic numbers for btree blocks.
103  */
104 extern const __uint32_t xfs_magics[];
105
106 /*
107  * Maximum and minimum records in a btree block.
108  * Given block size, type prefix, and leaf flag (0 or 1).
109  * The divisor below is equivalent to lf ? (e1) : (e2) but that produces
110  * compiler warnings.
111  */
112 #define XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf)       \
113         ((int)(((bsz) - (uint)sizeof(t ## _block_t)) / \
114          (((lf) * (uint)sizeof(t ## _rec_t)) + \
115           ((1 - (lf)) * \
116            ((uint)sizeof(t ## _key_t) + (uint)sizeof(t ## _ptr_t))))))
117 #define XFS_BTREE_BLOCK_MINRECS(bsz,t,lf)       \
118         (XFS_BTREE_BLOCK_MAXRECS(bsz,t,lf) / 2)
119
120 /*
121  * Record, key, and pointer address calculation macros.
122  * Given block size, type prefix, block pointer, and index of requested entry
123  * (first entry numbered 1).
124  */
125 #define XFS_BTREE_REC_ADDR(bsz,t,bb,i,mxr)      \
126         ((t ## _rec_t *)((char *)(bb) + sizeof(t ## _block_t) + \
127          ((i) - 1) * sizeof(t ## _rec_t)))
128 #define XFS_BTREE_KEY_ADDR(bsz,t,bb,i,mxr)      \
129         ((t ## _key_t *)((char *)(bb) + sizeof(t ## _block_t) + \
130          ((i) - 1) * sizeof(t ## _key_t)))
131 #define XFS_BTREE_PTR_ADDR(bsz,t,bb,i,mxr)      \
132         ((t ## _ptr_t *)((char *)(bb) + sizeof(t ## _block_t) + \
133          (mxr) * sizeof(t ## _key_t) + ((i) - 1) * sizeof(t ## _ptr_t)))
134
135 #define XFS_BTREE_MAXLEVELS     8       /* max of all btrees */
136
137 /*
138  * Btree cursor structure.
139  * This collects all information needed by the btree code in one place.
140  */
141 typedef struct xfs_btree_cur
142 {
143         struct xfs_trans        *bc_tp; /* transaction we're in, if any */
144         struct xfs_mount        *bc_mp; /* file system mount struct */
145         union {
146                 xfs_alloc_rec_incore_t  a;
147                 xfs_bmbt_irec_t         b;
148                 xfs_inobt_rec_t         i;
149         }               bc_rec;         /* current insert/search record value */
150         struct xfs_buf  *bc_bufs[XFS_BTREE_MAXLEVELS];  /* buf ptr per level */
151         int             bc_ptrs[XFS_BTREE_MAXLEVELS];   /* key/record # */
152         __uint8_t       bc_ra[XFS_BTREE_MAXLEVELS];     /* readahead bits */
153 #define XFS_BTCUR_LEFTRA        1       /* left sibling has been read-ahead */
154 #define XFS_BTCUR_RIGHTRA       2       /* right sibling has been read-ahead */
155         __uint8_t       bc_nlevels;     /* number of levels in the tree */
156         __uint8_t       bc_blocklog;    /* log2(blocksize) of btree blocks */
157         xfs_btnum_t     bc_btnum;       /* identifies which btree type */
158         union {
159                 struct {                        /* needed for BNO, CNT */
160                         struct xfs_buf  *agbp;  /* agf buffer pointer */
161                         xfs_agnumber_t  agno;   /* ag number */
162                 } a;
163                 struct {                        /* needed for BMAP */
164                         struct xfs_inode *ip;   /* pointer to our inode */
165                         struct xfs_bmap_free *flist;    /* list to free after */
166                         xfs_fsblock_t   firstblock;     /* 1st blk allocated */
167                         int             allocated;      /* count of alloced */
168                         short           forksize;       /* fork's inode space */
169                         char            whichfork;      /* data or attr fork */
170                         char            flags;          /* flags */
171 #define XFS_BTCUR_BPRV_WASDEL   1                       /* was delayed */
172                 } b;
173                 struct {                        /* needed for INO */
174                         struct xfs_buf  *agbp;  /* agi buffer pointer */
175                         xfs_agnumber_t  agno;   /* ag number */
176                 } i;
177         }               bc_private;     /* per-btree type data */
178 } xfs_btree_cur_t;
179
180 #define XFS_BTREE_NOERROR       0
181 #define XFS_BTREE_ERROR         1
182
183 /*
184  * Convert from buffer to btree block header.
185  */
186 #define XFS_BUF_TO_BLOCK(bp)    ((xfs_btree_block_t *)XFS_BUF_PTR(bp))
187 #define XFS_BUF_TO_LBLOCK(bp)   ((xfs_btree_lblock_t *)XFS_BUF_PTR(bp))
188 #define XFS_BUF_TO_SBLOCK(bp)   ((xfs_btree_sblock_t *)XFS_BUF_PTR(bp))
189
190
191 #ifdef __KERNEL__
192
193 #ifdef DEBUG
194 /*
195  * Debug routine: check that block header is ok.
196  */
197 void
198 xfs_btree_check_block(
199         xfs_btree_cur_t         *cur,   /* btree cursor */
200         xfs_btree_block_t       *block, /* generic btree block pointer */
201         int                     level,  /* level of the btree block */
202         struct xfs_buf          *bp);   /* buffer containing block, if any */
203
204 /*
205  * Debug routine: check that keys are in the right order.
206  */
207 void
208 xfs_btree_check_key(
209         xfs_btnum_t             btnum,  /* btree identifier */
210         void                    *ak1,   /* pointer to left (lower) key */
211         void                    *ak2);  /* pointer to right (higher) key */
212
213 /*
214  * Debug routine: check that records are in the right order.
215  */
216 void
217 xfs_btree_check_rec(
218         xfs_btnum_t             btnum,  /* btree identifier */
219         void                    *ar1,   /* pointer to left (lower) record */
220         void                    *ar2);  /* pointer to right (higher) record */
221 #else
222 #define xfs_btree_check_block(a,b,c,d)
223 #define xfs_btree_check_key(a,b,c)
224 #define xfs_btree_check_rec(a,b,c)
225 #endif  /* DEBUG */
226
227 /*
228  * Checking routine: check that long form block header is ok.
229  */
230 int                                     /* error (0 or EFSCORRUPTED) */
231 xfs_btree_check_lblock(
232         xfs_btree_cur_t         *cur,   /* btree cursor */
233         xfs_btree_lblock_t      *block, /* btree long form block pointer */
234         int                     level,  /* level of the btree block */
235         struct xfs_buf          *bp);   /* buffer containing block, if any */
236
237 /*
238  * Checking routine: check that (long) pointer is ok.
239  */
240 int                                     /* error (0 or EFSCORRUPTED) */
241 xfs_btree_check_lptr(
242         xfs_btree_cur_t         *cur,   /* btree cursor */
243         xfs_dfsbno_t            ptr,    /* btree block disk address */
244         int                     level); /* btree block level */
245
246 /*
247  * Checking routine: check that short form block header is ok.
248  */
249 int                                     /* error (0 or EFSCORRUPTED) */
250 xfs_btree_check_sblock(
251         xfs_btree_cur_t         *cur,   /* btree cursor */
252         xfs_btree_sblock_t      *block, /* btree short form block pointer */
253         int                     level,  /* level of the btree block */
254         struct xfs_buf          *bp);   /* buffer containing block */
255
256 /*
257  * Checking routine: check that (short) pointer is ok.
258  */
259 int                                     /* error (0 or EFSCORRUPTED) */
260 xfs_btree_check_sptr(
261         xfs_btree_cur_t         *cur,   /* btree cursor */
262         xfs_agblock_t           ptr,    /* btree block disk address */
263         int                     level); /* btree block level */
264
265 /*
266  * Delete the btree cursor.
267  */
268 void
269 xfs_btree_del_cursor(
270         xfs_btree_cur_t         *cur,   /* btree cursor */
271         int                     error); /* del because of error */
272
273 /*
274  * Duplicate the btree cursor.
275  * Allocate a new one, copy the record, re-get the buffers.
276  */
277 int                                     /* error */
278 xfs_btree_dup_cursor(
279         xfs_btree_cur_t         *cur,   /* input cursor */
280         xfs_btree_cur_t         **ncur);/* output cursor */
281
282 /*
283  * Change the cursor to point to the first record in the current block
284  * at the given level.  Other levels are unaffected.
285  */
286 int                                     /* success=1, failure=0 */
287 xfs_btree_firstrec(
288         xfs_btree_cur_t         *cur,   /* btree cursor */
289         int                     level); /* level to change */
290
291 /*
292  * Get a buffer for the block, return it with no data read.
293  * Long-form addressing.
294  */
295 struct xfs_buf *                                /* buffer for fsbno */
296 xfs_btree_get_bufl(
297         struct xfs_mount        *mp,    /* file system mount point */
298         struct xfs_trans        *tp,    /* transaction pointer */
299         xfs_fsblock_t           fsbno,  /* file system block number */
300         uint                    lock);  /* lock flags for get_buf */
301
302 /*
303  * Get a buffer for the block, return it with no data read.
304  * Short-form addressing.
305  */
306 struct xfs_buf *                                /* buffer for agno/agbno */
307 xfs_btree_get_bufs(
308         struct xfs_mount        *mp,    /* file system mount point */
309         struct xfs_trans        *tp,    /* transaction pointer */
310         xfs_agnumber_t          agno,   /* allocation group number */
311         xfs_agblock_t           agbno,  /* allocation group block number */
312         uint                    lock);  /* lock flags for get_buf */
313
314 /*
315  * Allocate a new btree cursor.
316  * The cursor is either for allocation (A) or bmap (B).
317  */
318 xfs_btree_cur_t *                       /* new btree cursor */
319 xfs_btree_init_cursor(
320         struct xfs_mount        *mp,    /* file system mount point */
321         struct xfs_trans        *tp,    /* transaction pointer */
322         struct xfs_buf          *agbp,  /* (A only) buffer for agf structure */
323         xfs_agnumber_t          agno,   /* (A only) allocation group number */
324         xfs_btnum_t             btnum,  /* btree identifier */
325         struct xfs_inode        *ip,    /* (B only) inode owning the btree */
326         int                     whichfork); /* (B only) data/attr fork */
327
328 /*
329  * Check for the cursor referring to the last block at the given level.
330  */
331 int                                     /* 1=is last block, 0=not last block */
332 xfs_btree_islastblock(
333         xfs_btree_cur_t         *cur,   /* btree cursor */
334         int                     level); /* level to check */
335
336 /*
337  * Change the cursor to point to the last record in the current block
338  * at the given level.  Other levels are unaffected.
339  */
340 int                                     /* success=1, failure=0 */
341 xfs_btree_lastrec(
342         xfs_btree_cur_t         *cur,   /* btree cursor */
343         int                     level); /* level to change */
344
345 /*
346  * Compute first and last byte offsets for the fields given.
347  * Interprets the offsets table, which contains struct field offsets.
348  */
349 void
350 xfs_btree_offsets(
351         __int64_t               fields, /* bitmask of fields */
352         const short             *offsets,/* table of field offsets */
353         int                     nbits,  /* number of bits to inspect */
354         int                     *first, /* output: first byte offset */
355         int                     *last); /* output: last byte offset */
356
357 /*
358  * Get a buffer for the block, return it read in.
359  * Long-form addressing.
360  */
361 int                                     /* error */
362 xfs_btree_read_bufl(
363         struct xfs_mount        *mp,    /* file system mount point */
364         struct xfs_trans        *tp,    /* transaction pointer */
365         xfs_fsblock_t           fsbno,  /* file system block number */
366         uint                    lock,   /* lock flags for read_buf */
367         struct xfs_buf          **bpp,  /* buffer for fsbno */
368         int                     refval);/* ref count value for buffer */
369
370 /*
371  * Get a buffer for the block, return it read in.
372  * Short-form addressing.
373  */
374 int                                     /* error */
375 xfs_btree_read_bufs(
376         struct xfs_mount        *mp,    /* file system mount point */
377         struct xfs_trans        *tp,    /* transaction pointer */
378         xfs_agnumber_t          agno,   /* allocation group number */
379         xfs_agblock_t           agbno,  /* allocation group block number */
380         uint                    lock,   /* lock flags for read_buf */
381         struct xfs_buf          **bpp,  /* buffer for agno/agbno */
382         int                     refval);/* ref count value for buffer */
383
384 /*
385  * Read-ahead the block, don't wait for it, don't return a buffer.
386  * Long-form addressing.
387  */
388 void                                    /* error */
389 xfs_btree_reada_bufl(
390         struct xfs_mount        *mp,    /* file system mount point */
391         xfs_fsblock_t           fsbno,  /* file system block number */
392         xfs_extlen_t            count); /* count of filesystem blocks */
393
394 /*
395  * Read-ahead the block, don't wait for it, don't return a buffer.
396  * Short-form addressing.
397  */
398 void                                    /* error */
399 xfs_btree_reada_bufs(
400         struct xfs_mount        *mp,    /* file system mount point */
401         xfs_agnumber_t          agno,   /* allocation group number */
402         xfs_agblock_t           agbno,  /* allocation group block number */
403         xfs_extlen_t            count); /* count of filesystem blocks */
404
405 /*
406  * Read-ahead btree blocks, at the given level.
407  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
408  */
409 int                                     /* readahead block count */
410 xfs_btree_readahead_core(
411         xfs_btree_cur_t         *cur,   /* btree cursor */
412         int                     lev,    /* level in btree */
413         int                     lr);    /* left/right bits */
414
415 static inline int                       /* readahead block count */
416 xfs_btree_readahead(
417         xfs_btree_cur_t         *cur,   /* btree cursor */
418         int                     lev,    /* level in btree */
419         int                     lr)     /* left/right bits */
420 {
421         if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
422                 return 0;
423
424         return xfs_btree_readahead_core(cur, lev, lr);
425 }
426
427
428 /*
429  * Set the buffer for level "lev" in the cursor to bp, releasing
430  * any previous buffer.
431  */
432 void
433 xfs_btree_setbuf(
434         xfs_btree_cur_t         *cur,   /* btree cursor */
435         int                     lev,    /* level in btree */
436         struct xfs_buf          *bp);   /* new buffer to set */
437
438 #endif  /* __KERNEL__ */
439
440
441 /*
442  * Min and max functions for extlen, agblock, fileoff, and filblks types.
443  */
444 #define XFS_EXTLEN_MIN(a,b)     \
445         ((xfs_extlen_t)(a) < (xfs_extlen_t)(b) ? \
446                 (xfs_extlen_t)(a) : (xfs_extlen_t)(b))
447 #define XFS_EXTLEN_MAX(a,b)     \
448         ((xfs_extlen_t)(a) > (xfs_extlen_t)(b) ? \
449                 (xfs_extlen_t)(a) : (xfs_extlen_t)(b))
450 #define XFS_AGBLOCK_MIN(a,b)    \
451         ((xfs_agblock_t)(a) < (xfs_agblock_t)(b) ? \
452                 (xfs_agblock_t)(a) : (xfs_agblock_t)(b))
453 #define XFS_AGBLOCK_MAX(a,b)    \
454         ((xfs_agblock_t)(a) > (xfs_agblock_t)(b) ? \
455                 (xfs_agblock_t)(a) : (xfs_agblock_t)(b))
456 #define XFS_FILEOFF_MIN(a,b)    \
457         ((xfs_fileoff_t)(a) < (xfs_fileoff_t)(b) ? \
458                 (xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
459 #define XFS_FILEOFF_MAX(a,b)    \
460         ((xfs_fileoff_t)(a) > (xfs_fileoff_t)(b) ? \
461                 (xfs_fileoff_t)(a) : (xfs_fileoff_t)(b))
462 #define XFS_FILBLKS_MIN(a,b)    \
463         ((xfs_filblks_t)(a) < (xfs_filblks_t)(b) ? \
464                 (xfs_filblks_t)(a) : (xfs_filblks_t)(b))
465 #define XFS_FILBLKS_MAX(a,b)    \
466         ((xfs_filblks_t)(a) > (xfs_filblks_t)(b) ? \
467                 (xfs_filblks_t)(a) : (xfs_filblks_t)(b))
468
469 #define XFS_FSB_SANITY_CHECK(mp,fsb)    \
470         (XFS_FSB_TO_AGNO(mp, fsb) < mp->m_sb.sb_agcount && \
471                 XFS_FSB_TO_AGBNO(mp, fsb) < mp->m_sb.sb_agblocks)
472
473 #endif  /* __XFS_BTREE_H__ */