2 * Copyright (c) 2000,2002-2005 Silicon Graphics, Inc.
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.
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.
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
18 #ifndef __XFS_BMAP_BTREE_H__
19 #define __XFS_BMAP_BTREE_H__
21 #define XFS_BMAP_MAGIC 0x424d4150 /* 'BMAP' */
24 struct xfs_btree_lblock
;
29 * Bmap root header, on-disk form only.
31 typedef struct xfs_bmdr_block
33 __uint16_t bb_level
; /* 0 is a leaf */
34 __uint16_t bb_numrecs
; /* current # of data records */
38 * Bmap btree record and extent descriptor.
40 * l0:31 is an extent flag (value 1 indicates non-normal).
41 * l0:0-30 and l1:9-31 are startoff.
42 * l1:0-8, l2:0-31, and l3:21-31 are startblock.
43 * l3:0-20 are blockcount.
45 * l0:63 is an extent flag (value 1 indicates non-normal).
46 * l0:9-62 are startoff.
47 * l0:0-8 and l1:21-63 are startblock.
48 * l1:0-20 are blockcount.
51 #ifndef XFS_NATIVE_HOST
53 #define BMBT_TOTAL_BITLEN 128 /* 128 bits, 16 bytes */
54 #define BMBT_EXNTFLAG_BITOFF 0
55 #define BMBT_EXNTFLAG_BITLEN 1
56 #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF + BMBT_EXNTFLAG_BITLEN)
57 #define BMBT_STARTOFF_BITLEN 54
58 #define BMBT_STARTBLOCK_BITOFF (BMBT_STARTOFF_BITOFF + BMBT_STARTOFF_BITLEN)
59 #define BMBT_STARTBLOCK_BITLEN 52
60 #define BMBT_BLOCKCOUNT_BITOFF \
61 (BMBT_STARTBLOCK_BITOFF + BMBT_STARTBLOCK_BITLEN)
62 #define BMBT_BLOCKCOUNT_BITLEN (BMBT_TOTAL_BITLEN - BMBT_BLOCKCOUNT_BITOFF)
66 #define BMBT_TOTAL_BITLEN 128 /* 128 bits, 16 bytes */
67 #define BMBT_EXNTFLAG_BITOFF 63
68 #define BMBT_EXNTFLAG_BITLEN 1
69 #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF - BMBT_STARTOFF_BITLEN)
70 #define BMBT_STARTOFF_BITLEN 54
71 #define BMBT_STARTBLOCK_BITOFF 85 /* 128 - 43 (other 9 is in first word) */
72 #define BMBT_STARTBLOCK_BITLEN 52
73 #define BMBT_BLOCKCOUNT_BITOFF 64 /* Start of second 64 bit container */
74 #define BMBT_BLOCKCOUNT_BITLEN 21
76 #endif /* XFS_NATIVE_HOST */
81 typedef struct xfs_bmbt_rec_32
83 __uint32_t l0
, l1
, l2
, l3
;
85 typedef struct xfs_bmbt_rec_64
90 typedef __uint64_t xfs_bmbt_rec_base_t
; /* use this for casts */
91 typedef xfs_bmbt_rec_64_t xfs_bmbt_rec_t
, xfs_bmdr_rec_t
;
94 * Values and macros for delayed-allocation startblock fields.
96 #define STARTBLOCKVALBITS 17
97 #define STARTBLOCKMASKBITS (15 + XFS_BIG_BLKNOS * 20)
98 #define DSTARTBLOCKMASKBITS (15 + 20)
99 #define STARTBLOCKMASK \
100 (((((xfs_fsblock_t)1) << STARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
101 #define DSTARTBLOCKMASK \
102 (((((xfs_dfsbno_t)1) << DSTARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
104 #define ISNULLSTARTBLOCK(x) isnullstartblock(x)
105 static inline int isnullstartblock(xfs_fsblock_t x
)
107 return ((x
) & STARTBLOCKMASK
) == STARTBLOCKMASK
;
110 #define ISNULLDSTARTBLOCK(x) isnulldstartblock(x)
111 static inline int isnulldstartblock(xfs_dfsbno_t x
)
113 return ((x
) & DSTARTBLOCKMASK
) == DSTARTBLOCKMASK
;
116 #define NULLSTARTBLOCK(k) nullstartblock(k)
117 static inline xfs_fsblock_t
nullstartblock(int k
)
119 ASSERT(k
< (1 << STARTBLOCKVALBITS
));
120 return STARTBLOCKMASK
| (k
);
123 #define STARTBLOCKVAL(x) startblockval(x)
124 static inline xfs_filblks_t
startblockval(xfs_fsblock_t x
)
126 return (xfs_filblks_t
)((x
) & ~STARTBLOCKMASK
);
130 * Possible extent formats.
133 XFS_EXTFMT_NOSTATE
= 0,
138 * Possible extent states.
141 XFS_EXT_NORM
, XFS_EXT_UNWRITTEN
,
142 XFS_EXT_DMAPI_OFFLINE
, XFS_EXT_INVALID
146 * Extent state and extent format macros.
148 #define XFS_EXTFMT_INODE(x) \
149 (XFS_SB_VERSION_HASEXTFLGBIT(&((x)->i_mount->m_sb)) ? \
150 XFS_EXTFMT_HASSTATE : XFS_EXTFMT_NOSTATE)
151 #define ISUNWRITTEN(x) ((x)->br_state == XFS_EXT_UNWRITTEN)
154 * Incore version of above.
156 typedef struct xfs_bmbt_irec
158 xfs_fileoff_t br_startoff
; /* starting file offset */
159 xfs_fsblock_t br_startblock
; /* starting block number */
160 xfs_filblks_t br_blockcount
; /* number of blocks */
161 xfs_exntst_t br_state
; /* extent state */
165 * Key structure for non-leaf levels of the tree.
167 typedef struct xfs_bmbt_key
169 xfs_dfiloff_t br_startoff
; /* starting file offset */
170 } xfs_bmbt_key_t
, xfs_bmdr_key_t
;
172 typedef xfs_dfsbno_t xfs_bmbt_ptr_t
, xfs_bmdr_ptr_t
; /* btree pointer type */
173 /* btree block header type */
174 typedef struct xfs_btree_lblock xfs_bmbt_block_t
;
176 #define XFS_BUF_TO_BMBT_BLOCK(bp) ((xfs_bmbt_block_t *)XFS_BUF_PTR(bp))
178 #define XFS_BMAP_IBLOCK_SIZE(lev,cur) (1 << (cur)->bc_blocklog)
179 #define XFS_BMAP_RBLOCK_DSIZE(lev,cur) ((cur)->bc_private.b.forksize)
180 #define XFS_BMAP_RBLOCK_ISIZE(lev,cur) \
181 ((int)XFS_IFORK_PTR((cur)->bc_private.b.ip, \
182 (cur)->bc_private.b.whichfork)->if_broot_bytes)
184 #define XFS_BMAP_BLOCK_DSIZE(lev,cur) \
185 (((lev) == (cur)->bc_nlevels - 1 ? \
186 XFS_BMAP_RBLOCK_DSIZE(lev,cur) : XFS_BMAP_IBLOCK_SIZE(lev,cur)))
187 #define XFS_BMAP_BLOCK_ISIZE(lev,cur) \
188 (((lev) == (cur)->bc_nlevels - 1 ? \
189 XFS_BMAP_RBLOCK_ISIZE(lev,cur) : XFS_BMAP_IBLOCK_SIZE(lev,cur)))
191 #define XFS_BMAP_BLOCK_DMAXRECS(lev,cur) \
192 (((lev) == (cur)->bc_nlevels - 1 ? \
193 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur), \
194 xfs_bmdr, (lev) == 0) : \
195 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
196 #define XFS_BMAP_BLOCK_IMAXRECS(lev,cur) \
197 (((lev) == (cur)->bc_nlevels - 1 ? \
198 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
199 xfs_bmbt, (lev) == 0) : \
200 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
202 #define XFS_BMAP_BLOCK_DMINRECS(lev,cur) \
203 (((lev) == (cur)->bc_nlevels - 1 ? \
204 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur),\
205 xfs_bmdr, (lev) == 0) : \
206 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
207 #define XFS_BMAP_BLOCK_IMINRECS(lev,cur) \
208 (((lev) == (cur)->bc_nlevels - 1 ? \
209 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
210 xfs_bmbt, (lev) == 0) : \
211 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
213 #define XFS_BMAP_REC_DADDR(bb,i,cur) \
214 (XFS_BTREE_REC_ADDR(XFS_BMAP_BLOCK_DSIZE( \
215 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
216 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \
217 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
218 #define XFS_BMAP_REC_IADDR(bb,i,cur) \
219 (XFS_BTREE_REC_ADDR(XFS_BMAP_BLOCK_ISIZE( \
220 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
221 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \
222 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
224 #define XFS_BMAP_KEY_DADDR(bb,i,cur) \
225 (XFS_BTREE_KEY_ADDR(XFS_BMAP_BLOCK_DSIZE( \
226 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
227 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \
228 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
229 #define XFS_BMAP_KEY_IADDR(bb,i,cur) \
230 (XFS_BTREE_KEY_ADDR(XFS_BMAP_BLOCK_ISIZE( \
231 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
232 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \
233 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
235 #define XFS_BMAP_PTR_DADDR(bb,i,cur) \
236 (XFS_BTREE_PTR_ADDR(XFS_BMAP_BLOCK_DSIZE( \
237 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
238 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \
239 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
240 #define XFS_BMAP_PTR_IADDR(bb,i,cur) \
241 (XFS_BTREE_PTR_ADDR(XFS_BMAP_BLOCK_ISIZE( \
242 INT_GET((bb)->bb_level, ARCH_CONVERT), cur), \
243 xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \
244 INT_GET((bb)->bb_level, ARCH_CONVERT), cur)))
247 * These are to be used when we know the size of the block and
248 * we don't have a cursor.
250 #define XFS_BMAP_BROOT_REC_ADDR(bb,i,sz) \
251 (XFS_BTREE_REC_ADDR(sz,xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz)))
252 #define XFS_BMAP_BROOT_KEY_ADDR(bb,i,sz) \
253 (XFS_BTREE_KEY_ADDR(sz,xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz)))
254 #define XFS_BMAP_BROOT_PTR_ADDR(bb,i,sz) \
255 (XFS_BTREE_PTR_ADDR(sz,xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz)))
257 #define XFS_BMAP_BROOT_NUMRECS(bb) INT_GET((bb)->bb_numrecs, ARCH_CONVERT)
258 #define XFS_BMAP_BROOT_MAXRECS(sz) XFS_BTREE_BLOCK_MAXRECS(sz,xfs_bmbt,0)
260 #define XFS_BMAP_BROOT_SPACE_CALC(nrecs) \
261 (int)(sizeof(xfs_bmbt_block_t) + \
262 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
264 #define XFS_BMAP_BROOT_SPACE(bb) \
265 (XFS_BMAP_BROOT_SPACE_CALC(INT_GET((bb)->bb_numrecs, ARCH_CONVERT)))
266 #define XFS_BMDR_SPACE_CALC(nrecs) \
267 (int)(sizeof(xfs_bmdr_block_t) + \
268 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
271 * Maximum number of bmap btree levels.
273 #define XFS_BM_MAXLEVELS(mp,w) ((mp)->m_bm_maxlevels[(w)])
275 #define XFS_BMAP_SANITY_CHECK(mp,bb,level) \
276 (INT_GET((bb)->bb_magic, ARCH_CONVERT) == XFS_BMAP_MAGIC && \
277 INT_GET((bb)->bb_level, ARCH_CONVERT) == level && \
278 INT_GET((bb)->bb_numrecs, ARCH_CONVERT) > 0 && \
279 INT_GET((bb)->bb_numrecs, ARCH_CONVERT) <= \
280 (mp)->m_bmap_dmxr[(level) != 0])
285 #if defined(XFS_BMBT_TRACE)
287 * Trace buffer entry types.
289 #define XFS_BMBT_KTRACE_ARGBI 1
290 #define XFS_BMBT_KTRACE_ARGBII 2
291 #define XFS_BMBT_KTRACE_ARGFFFI 3
292 #define XFS_BMBT_KTRACE_ARGI 4
293 #define XFS_BMBT_KTRACE_ARGIFK 5
294 #define XFS_BMBT_KTRACE_ARGIFR 6
295 #define XFS_BMBT_KTRACE_ARGIK 7
296 #define XFS_BMBT_KTRACE_CUR 8
298 #define XFS_BMBT_TRACE_SIZE 4096 /* size of global trace buffer */
299 #define XFS_BMBT_KTRACE_SIZE 32 /* size of per-inode trace buffer */
300 extern ktrace_t
*xfs_bmbt_trace_buf
;
304 * Prototypes for xfs_bmap.c to call.
306 extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t
*, int, xfs_bmbt_block_t
*, int);
307 extern int xfs_bmbt_decrement(struct xfs_btree_cur
*, int, int *);
308 extern int xfs_bmbt_delete(struct xfs_btree_cur
*, int *);
309 extern void xfs_bmbt_get_all(xfs_bmbt_rec_t
*r
, xfs_bmbt_irec_t
*s
);
310 extern xfs_bmbt_block_t
*xfs_bmbt_get_block(struct xfs_btree_cur
*cur
,
311 int, struct xfs_buf
**bpp
);
312 extern xfs_filblks_t
xfs_bmbt_get_blockcount(xfs_bmbt_rec_t
*r
);
313 extern xfs_fsblock_t
xfs_bmbt_get_startblock(xfs_bmbt_rec_t
*r
);
314 extern xfs_fileoff_t
xfs_bmbt_get_startoff(xfs_bmbt_rec_t
*r
);
315 extern xfs_exntst_t
xfs_bmbt_get_state(xfs_bmbt_rec_t
*r
);
317 #ifndef XFS_NATIVE_HOST
318 extern void xfs_bmbt_disk_get_all(xfs_bmbt_rec_t
*r
, xfs_bmbt_irec_t
*s
);
319 extern xfs_exntst_t
xfs_bmbt_disk_get_state(xfs_bmbt_rec_t
*r
);
320 extern xfs_filblks_t
xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t
*r
);
321 extern xfs_fsblock_t
xfs_bmbt_disk_get_startblock(xfs_bmbt_rec_t
*r
);
322 extern xfs_fileoff_t
xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t
*r
);
324 #define xfs_bmbt_disk_get_all(r, s) xfs_bmbt_get_all(r, s)
325 #define xfs_bmbt_disk_get_state(r) xfs_bmbt_get_state(r)
326 #define xfs_bmbt_disk_get_blockcount(r) xfs_bmbt_get_blockcount(r)
327 #define xfs_bmbt_disk_get_startblock(r) xfs_bmbt_get_blockcount(r)
328 #define xfs_bmbt_disk_get_startoff(r) xfs_bmbt_get_startoff(r)
329 #endif /* XFS_NATIVE_HOST */
331 extern int xfs_bmbt_increment(struct xfs_btree_cur
*, int, int *);
332 extern int xfs_bmbt_insert(struct xfs_btree_cur
*, int *);
333 extern void xfs_bmbt_log_block(struct xfs_btree_cur
*, struct xfs_buf
*, int);
334 extern void xfs_bmbt_log_recs(struct xfs_btree_cur
*, struct xfs_buf
*, int,
336 extern int xfs_bmbt_lookup_eq(struct xfs_btree_cur
*, xfs_fileoff_t
,
337 xfs_fsblock_t
, xfs_filblks_t
, int *);
338 extern int xfs_bmbt_lookup_ge(struct xfs_btree_cur
*, xfs_fileoff_t
,
339 xfs_fsblock_t
, xfs_filblks_t
, int *);
342 * Give the bmap btree a new root block. Copy the old broot contents
343 * down into a real block and make the broot point to it.
345 extern int xfs_bmbt_newroot(struct xfs_btree_cur
*cur
, int *lflags
, int *stat
);
347 extern void xfs_bmbt_set_all(xfs_bmbt_rec_t
*r
, xfs_bmbt_irec_t
*s
);
348 extern void xfs_bmbt_set_allf(xfs_bmbt_rec_t
*r
, xfs_fileoff_t o
,
349 xfs_fsblock_t b
, xfs_filblks_t c
, xfs_exntst_t v
);
350 extern void xfs_bmbt_set_blockcount(xfs_bmbt_rec_t
*r
, xfs_filblks_t v
);
351 extern void xfs_bmbt_set_startblock(xfs_bmbt_rec_t
*r
, xfs_fsblock_t v
);
352 extern void xfs_bmbt_set_startoff(xfs_bmbt_rec_t
*r
, xfs_fileoff_t v
);
353 extern void xfs_bmbt_set_state(xfs_bmbt_rec_t
*r
, xfs_exntst_t v
);
355 #ifndef XFS_NATIVE_HOST
356 extern void xfs_bmbt_disk_set_all(xfs_bmbt_rec_t
*r
, xfs_bmbt_irec_t
*s
);
357 extern void xfs_bmbt_disk_set_allf(xfs_bmbt_rec_t
*r
, xfs_fileoff_t o
,
358 xfs_fsblock_t b
, xfs_filblks_t c
, xfs_exntst_t v
);
360 #define xfs_bmbt_disk_set_all(r, s) xfs_bmbt_set_all(r, s)
361 #define xfs_bmbt_disk_set_allf(r, o, b, c, v) xfs_bmbt_set_allf(r, o, b, c, v)
362 #endif /* XFS_NATIVE_HOST */
364 extern void xfs_bmbt_to_bmdr(xfs_bmbt_block_t
*, int, xfs_bmdr_block_t
*, int);
365 extern int xfs_bmbt_update(struct xfs_btree_cur
*, xfs_fileoff_t
,
366 xfs_fsblock_t
, xfs_filblks_t
, xfs_exntst_t
);
370 * Get the data from the pointed-to record.
372 extern int xfs_bmbt_get_rec(struct xfs_btree_cur
*, xfs_fileoff_t
*,
373 xfs_fsblock_t
*, xfs_filblks_t
*,
374 xfs_exntst_t
*, int *);
378 * Search an extent list for the extent which includes block
381 xfs_bmbt_rec_t
*xfs_bmap_do_search_extents(xfs_bmbt_rec_t
*,
382 xfs_extnum_t
, xfs_extnum_t
, xfs_fileoff_t
, int *,
383 xfs_extnum_t
*, xfs_bmbt_irec_t
*, xfs_bmbt_irec_t
*);
385 #endif /* __KERNEL__ */
387 #endif /* __XFS_BMAP_BTREE_H__ */