blob: 2d950e9759181f8bef3f499bfc8340555a60735a [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000,2002-2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * 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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * 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
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
18#ifndef __XFS_BMAP_BTREE_H__
19#define __XFS_BMAP_BTREE_H__
20
21#define XFS_BMAP_MAGIC 0x424d4150 /* 'BMAP' */
22
23struct xfs_btree_cur;
24struct xfs_btree_lblock;
25struct xfs_mount;
26struct xfs_inode;
27
28/*
29 * Bmap root header, on-disk form only.
30 */
Christoph Hellwig16259e72005-11-02 15:11:25 +110031typedef struct xfs_bmdr_block {
32 __be16 bb_level; /* 0 is a leaf */
33 __be16 bb_numrecs; /* current # of data records */
Linus Torvalds1da177e2005-04-16 15:20:36 -070034} xfs_bmdr_block_t;
35
36/*
37 * Bmap btree record and extent descriptor.
Linus Torvalds1da177e2005-04-16 15:20:36 -070038 * l0:63 is an extent flag (value 1 indicates non-normal).
39 * l0:9-62 are startoff.
40 * l0:0-8 and l1:21-63 are startblock.
41 * l1:0-20 are blockcount.
42 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070043#define BMBT_EXNTFLAG_BITLEN 1
Linus Torvalds1da177e2005-04-16 15:20:36 -070044#define BMBT_STARTOFF_BITLEN 54
Linus Torvalds1da177e2005-04-16 15:20:36 -070045#define BMBT_STARTBLOCK_BITLEN 52
Linus Torvalds1da177e2005-04-16 15:20:36 -070046#define BMBT_BLOCKCOUNT_BITLEN 21
47
Linus Torvalds1da177e2005-04-16 15:20:36 -070048
49#define BMBT_USE_64 1
50
51typedef struct xfs_bmbt_rec_32
52{
53 __uint32_t l0, l1, l2, l3;
54} xfs_bmbt_rec_32_t;
55typedef struct xfs_bmbt_rec_64
56{
Christoph Hellwigcd8b0a92007-08-16 16:24:15 +100057 __be64 l0, l1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070058} xfs_bmbt_rec_64_t;
59
60typedef __uint64_t xfs_bmbt_rec_base_t; /* use this for casts */
61typedef xfs_bmbt_rec_64_t xfs_bmbt_rec_t, xfs_bmdr_rec_t;
62
Christoph Hellwiga6f64d42007-08-16 16:23:40 +100063typedef struct xfs_bmbt_rec_host {
64 __uint64_t l0, l1;
65} xfs_bmbt_rec_host_t;
66
Linus Torvalds1da177e2005-04-16 15:20:36 -070067/*
68 * Values and macros for delayed-allocation startblock fields.
69 */
70#define STARTBLOCKVALBITS 17
71#define STARTBLOCKMASKBITS (15 + XFS_BIG_BLKNOS * 20)
72#define DSTARTBLOCKMASKBITS (15 + 20)
73#define STARTBLOCKMASK \
74 (((((xfs_fsblock_t)1) << STARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
75#define DSTARTBLOCKMASK \
76 (((((xfs_dfsbno_t)1) << DSTARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
Nathan Scotta844f452005-11-02 14:38:42 +110077
Linus Torvalds1da177e2005-04-16 15:20:36 -070078#define ISNULLSTARTBLOCK(x) isnullstartblock(x)
Nathan Scotta844f452005-11-02 14:38:42 +110079static inline int isnullstartblock(xfs_fsblock_t x)
80{
81 return ((x) & STARTBLOCKMASK) == STARTBLOCKMASK;
82}
83
Linus Torvalds1da177e2005-04-16 15:20:36 -070084#define ISNULLDSTARTBLOCK(x) isnulldstartblock(x)
Nathan Scotta844f452005-11-02 14:38:42 +110085static inline int isnulldstartblock(xfs_dfsbno_t x)
86{
87 return ((x) & DSTARTBLOCKMASK) == DSTARTBLOCKMASK;
88}
89
Linus Torvalds1da177e2005-04-16 15:20:36 -070090#define NULLSTARTBLOCK(k) nullstartblock(k)
Nathan Scotta844f452005-11-02 14:38:42 +110091static inline xfs_fsblock_t nullstartblock(int k)
92{
93 ASSERT(k < (1 << STARTBLOCKVALBITS));
94 return STARTBLOCKMASK | (k);
95}
96
Linus Torvalds1da177e2005-04-16 15:20:36 -070097#define STARTBLOCKVAL(x) startblockval(x)
Nathan Scotta844f452005-11-02 14:38:42 +110098static inline xfs_filblks_t startblockval(xfs_fsblock_t x)
99{
100 return (xfs_filblks_t)((x) & ~STARTBLOCKMASK);
101}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102
103/*
104 * Possible extent formats.
105 */
106typedef enum {
107 XFS_EXTFMT_NOSTATE = 0,
108 XFS_EXTFMT_HASSTATE
109} xfs_exntfmt_t;
110
111/*
112 * Possible extent states.
113 */
114typedef enum {
115 XFS_EXT_NORM, XFS_EXT_UNWRITTEN,
116 XFS_EXT_DMAPI_OFFLINE, XFS_EXT_INVALID
117} xfs_exntst_t;
118
119/*
120 * Extent state and extent format macros.
121 */
Nathan Scotta844f452005-11-02 14:38:42 +1100122#define XFS_EXTFMT_INODE(x) \
123 (XFS_SB_VERSION_HASEXTFLGBIT(&((x)->i_mount->m_sb)) ? \
124 XFS_EXTFMT_HASSTATE : XFS_EXTFMT_NOSTATE)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125#define ISUNWRITTEN(x) ((x)->br_state == XFS_EXT_UNWRITTEN)
126
127/*
128 * Incore version of above.
129 */
130typedef struct xfs_bmbt_irec
131{
132 xfs_fileoff_t br_startoff; /* starting file offset */
133 xfs_fsblock_t br_startblock; /* starting block number */
134 xfs_filblks_t br_blockcount; /* number of blocks */
135 xfs_exntst_t br_state; /* extent state */
136} xfs_bmbt_irec_t;
137
138/*
139 * Key structure for non-leaf levels of the tree.
140 */
Christoph Hellwig8801bb92006-09-28 10:58:17 +1000141typedef struct xfs_bmbt_key {
142 __be64 br_startoff; /* starting file offset */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143} xfs_bmbt_key_t, xfs_bmdr_key_t;
144
Christoph Hellwig397b5202006-09-28 10:57:52 +1000145/* btree pointer type */
146typedef __be64 xfs_bmbt_ptr_t, xfs_bmdr_ptr_t;
147
148/* btree block header type */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149typedef struct xfs_btree_lblock xfs_bmbt_block_t;
150
Nathan Scotta844f452005-11-02 14:38:42 +1100151#define XFS_BUF_TO_BMBT_BLOCK(bp) ((xfs_bmbt_block_t *)XFS_BUF_PTR(bp))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Nathan Scotta844f452005-11-02 14:38:42 +1100153#define XFS_BMAP_RBLOCK_DSIZE(lev,cur) ((cur)->bc_private.b.forksize)
154#define XFS_BMAP_RBLOCK_ISIZE(lev,cur) \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155 ((int)XFS_IFORK_PTR((cur)->bc_private.b.ip, \
Nathan Scotta844f452005-11-02 14:38:42 +1100156 (cur)->bc_private.b.whichfork)->if_broot_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157
Linus Torvalds1da177e2005-04-16 15:20:36 -0700158#define XFS_BMAP_BLOCK_DMAXRECS(lev,cur) \
Nathan Scotta844f452005-11-02 14:38:42 +1100159 (((lev) == (cur)->bc_nlevels - 1 ? \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur), \
161 xfs_bmdr, (lev) == 0) : \
Nathan Scotta844f452005-11-02 14:38:42 +1100162 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163#define XFS_BMAP_BLOCK_IMAXRECS(lev,cur) \
Nathan Scotta844f452005-11-02 14:38:42 +1100164 (((lev) == (cur)->bc_nlevels - 1 ? \
165 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
166 xfs_bmbt, (lev) == 0) : \
167 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169#define XFS_BMAP_BLOCK_DMINRECS(lev,cur) \
Nathan Scotta844f452005-11-02 14:38:42 +1100170 (((lev) == (cur)->bc_nlevels - 1 ? \
171 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur),\
172 xfs_bmdr, (lev) == 0) : \
173 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174#define XFS_BMAP_BLOCK_IMINRECS(lev,cur) \
Nathan Scotta844f452005-11-02 14:38:42 +1100175 (((lev) == (cur)->bc_nlevels - 1 ? \
176 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
177 xfs_bmbt, (lev) == 0) : \
178 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100180#define XFS_BMAP_REC_DADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i))
181
182#define XFS_BMAP_REC_IADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700183
Nathan Scotta844f452005-11-02 14:38:42 +1100184#define XFS_BMAP_KEY_DADDR(bb,i,cur) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100185 (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i))
186
Nathan Scotta844f452005-11-02 14:38:42 +1100187#define XFS_BMAP_KEY_IADDR(bb,i,cur) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100188 (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189
Nathan Scotta844f452005-11-02 14:38:42 +1100190#define XFS_BMAP_PTR_DADDR(bb,i,cur) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100191 (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \
Christoph Hellwig16259e72005-11-02 15:11:25 +1100192 be16_to_cpu((bb)->bb_level), cur)))
Nathan Scotta844f452005-11-02 14:38:42 +1100193#define XFS_BMAP_PTR_IADDR(bb,i,cur) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100194 (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \
Christoph Hellwig16259e72005-11-02 15:11:25 +1100195 be16_to_cpu((bb)->bb_level), cur)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196
197/*
198 * These are to be used when we know the size of the block and
199 * we don't have a cursor.
200 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201#define XFS_BMAP_BROOT_REC_ADDR(bb,i,sz) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100202 (XFS_BTREE_REC_ADDR(xfs_bmbt,bb,i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203#define XFS_BMAP_BROOT_KEY_ADDR(bb,i,sz) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100204 (XFS_BTREE_KEY_ADDR(xfs_bmbt,bb,i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205#define XFS_BMAP_BROOT_PTR_ADDR(bb,i,sz) \
Eric Sandeen2c36dde2007-02-10 18:37:33 +1100206 (XFS_BTREE_PTR_ADDR(xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207
Christoph Hellwig16259e72005-11-02 15:11:25 +1100208#define XFS_BMAP_BROOT_NUMRECS(bb) be16_to_cpu((bb)->bb_numrecs)
Nathan Scotta844f452005-11-02 14:38:42 +1100209#define XFS_BMAP_BROOT_MAXRECS(sz) XFS_BTREE_BLOCK_MAXRECS(sz,xfs_bmbt,0)
210
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211#define XFS_BMAP_BROOT_SPACE_CALC(nrecs) \
Nathan Scotta844f452005-11-02 14:38:42 +1100212 (int)(sizeof(xfs_bmbt_block_t) + \
213 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
214
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215#define XFS_BMAP_BROOT_SPACE(bb) \
Christoph Hellwig16259e72005-11-02 15:11:25 +1100216 (XFS_BMAP_BROOT_SPACE_CALC(be16_to_cpu((bb)->bb_numrecs)))
Nathan Scotta844f452005-11-02 14:38:42 +1100217#define XFS_BMDR_SPACE_CALC(nrecs) \
218 (int)(sizeof(xfs_bmdr_block_t) + \
219 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220
221/*
222 * Maximum number of bmap btree levels.
223 */
Nathan Scotta844f452005-11-02 14:38:42 +1100224#define XFS_BM_MAXLEVELS(mp,w) ((mp)->m_bm_maxlevels[(w)])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225
Nathan Scotta844f452005-11-02 14:38:42 +1100226#define XFS_BMAP_SANITY_CHECK(mp,bb,level) \
Christoph Hellwig16259e72005-11-02 15:11:25 +1100227 (be32_to_cpu((bb)->bb_magic) == XFS_BMAP_MAGIC && \
228 be16_to_cpu((bb)->bb_level) == level && \
229 be16_to_cpu((bb)->bb_numrecs) > 0 && \
230 be16_to_cpu((bb)->bb_numrecs) <= (mp)->m_bmap_dmxr[(level) != 0])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700231
232
233#ifdef __KERNEL__
234
235#if defined(XFS_BMBT_TRACE)
236/*
237 * Trace buffer entry types.
238 */
239#define XFS_BMBT_KTRACE_ARGBI 1
240#define XFS_BMBT_KTRACE_ARGBII 2
241#define XFS_BMBT_KTRACE_ARGFFFI 3
242#define XFS_BMBT_KTRACE_ARGI 4
243#define XFS_BMBT_KTRACE_ARGIFK 5
244#define XFS_BMBT_KTRACE_ARGIFR 6
245#define XFS_BMBT_KTRACE_ARGIK 7
246#define XFS_BMBT_KTRACE_CUR 8
247
248#define XFS_BMBT_TRACE_SIZE 4096 /* size of global trace buffer */
249#define XFS_BMBT_KTRACE_SIZE 32 /* size of per-inode trace buffer */
250extern ktrace_t *xfs_bmbt_trace_buf;
251#endif
252
253/*
254 * Prototypes for xfs_bmap.c to call.
255 */
Nathan Scotta844f452005-11-02 14:38:42 +1100256extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t *, int, xfs_bmbt_block_t *, int);
257extern int xfs_bmbt_decrement(struct xfs_btree_cur *, int, int *);
258extern int xfs_bmbt_delete(struct xfs_btree_cur *, int *);
Christoph Hellwiga6f64d42007-08-16 16:23:40 +1000259extern void xfs_bmbt_get_all(xfs_bmbt_rec_host_t *r, xfs_bmbt_irec_t *s);
Nathan Scotta844f452005-11-02 14:38:42 +1100260extern xfs_bmbt_block_t *xfs_bmbt_get_block(struct xfs_btree_cur *cur,
261 int, struct xfs_buf **bpp);
Christoph Hellwiga6f64d42007-08-16 16:23:40 +1000262extern xfs_filblks_t xfs_bmbt_get_blockcount(xfs_bmbt_rec_host_t *r);
263extern xfs_fsblock_t xfs_bmbt_get_startblock(xfs_bmbt_rec_host_t *r);
264extern xfs_fileoff_t xfs_bmbt_get_startoff(xfs_bmbt_rec_host_t *r);
265extern xfs_exntst_t xfs_bmbt_get_state(xfs_bmbt_rec_host_t *r);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266
Nathan Scotta844f452005-11-02 14:38:42 +1100267extern void xfs_bmbt_disk_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
Nathan Scotta844f452005-11-02 14:38:42 +1100268extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r);
Nathan Scotta844f452005-11-02 14:38:42 +1100269extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270
Nathan Scotta844f452005-11-02 14:38:42 +1100271extern int xfs_bmbt_increment(struct xfs_btree_cur *, int, int *);
272extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *);
273extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
274extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int,
275 int);
276extern int xfs_bmbt_lookup_eq(struct xfs_btree_cur *, xfs_fileoff_t,
277 xfs_fsblock_t, xfs_filblks_t, int *);
278extern int xfs_bmbt_lookup_ge(struct xfs_btree_cur *, xfs_fileoff_t,
279 xfs_fsblock_t, xfs_filblks_t, int *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281/*
282 * Give the bmap btree a new root block. Copy the old broot contents
283 * down into a real block and make the broot point to it.
284 */
Nathan Scotta844f452005-11-02 14:38:42 +1100285extern int xfs_bmbt_newroot(struct xfs_btree_cur *cur, int *lflags, int *stat);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286
Christoph Hellwiga6f64d42007-08-16 16:23:40 +1000287extern void xfs_bmbt_set_all(xfs_bmbt_rec_host_t *r, xfs_bmbt_irec_t *s);
288extern void xfs_bmbt_set_allf(xfs_bmbt_rec_host_t *r, xfs_fileoff_t o,
Nathan Scotta844f452005-11-02 14:38:42 +1100289 xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v);
Christoph Hellwiga6f64d42007-08-16 16:23:40 +1000290extern void xfs_bmbt_set_blockcount(xfs_bmbt_rec_host_t *r, xfs_filblks_t v);
291extern void xfs_bmbt_set_startblock(xfs_bmbt_rec_host_t *r, xfs_fsblock_t v);
292extern void xfs_bmbt_set_startoff(xfs_bmbt_rec_host_t *r, xfs_fileoff_t v);
293extern void xfs_bmbt_set_state(xfs_bmbt_rec_host_t *r, xfs_exntst_t v);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294
Nathan Scotta844f452005-11-02 14:38:42 +1100295extern void xfs_bmbt_disk_set_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
296extern void xfs_bmbt_disk_set_allf(xfs_bmbt_rec_t *r, xfs_fileoff_t o,
297 xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700298
Nathan Scotta844f452005-11-02 14:38:42 +1100299extern void xfs_bmbt_to_bmdr(xfs_bmbt_block_t *, int, xfs_bmdr_block_t *, int);
300extern int xfs_bmbt_update(struct xfs_btree_cur *, xfs_fileoff_t,
301 xfs_fsblock_t, xfs_filblks_t, xfs_exntst_t);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303#endif /* __KERNEL__ */
304
305#endif /* __XFS_BMAP_BTREE_H__ */