2 * Copyright (c) 2000-2001,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
20 #include "xfs_types.h"
23 #include "xfs_trans.h"
26 #include "xfs_mount.h"
27 #include "xfs_bmap_btree.h"
28 #include "xfs_alloc_btree.h"
29 #include "xfs_ialloc_btree.h"
30 #include "xfs_dinode.h"
31 #include "xfs_inode.h"
32 #include "xfs_btree.h"
33 #include "xfs_ialloc.h"
34 #include "xfs_alloc.h"
35 #include "xfs_error.h"
36 #include "xfs_trace.h"
40 xfs_inobt_get_minrecs(
41 struct xfs_btree_cur
*cur
,
44 return cur
->bc_mp
->m_inobt_mnr
[level
!= 0];
47 STATIC
struct xfs_btree_cur
*
49 struct xfs_btree_cur
*cur
)
51 return xfs_inobt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
52 cur
->bc_private
.a
.agbp
, cur
->bc_private
.a
.agno
);
57 struct xfs_btree_cur
*cur
,
58 union xfs_btree_ptr
*nptr
,
59 int inc
) /* level change */
61 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
62 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
64 agi
->agi_root
= nptr
->s
;
65 be32_add_cpu(&agi
->agi_level
, inc
);
66 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
, XFS_AGI_ROOT
| XFS_AGI_LEVEL
);
70 xfs_inobt_alloc_block(
71 struct xfs_btree_cur
*cur
,
72 union xfs_btree_ptr
*start
,
73 union xfs_btree_ptr
*new,
77 xfs_alloc_arg_t args
; /* block allocation args */
78 int error
; /* error return value */
79 xfs_agblock_t sbno
= be32_to_cpu(start
->s
);
81 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ENTRY
);
83 memset(&args
, 0, sizeof(args
));
86 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.a
.agno
, sbno
);
90 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
92 error
= xfs_alloc_vextent(&args
);
94 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ERROR
);
97 if (args
.fsbno
== NULLFSBLOCK
) {
98 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
102 ASSERT(args
.len
== 1);
103 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
105 new->s
= cpu_to_be32(XFS_FSB_TO_AGBNO(args
.mp
, args
.fsbno
));
111 xfs_inobt_free_block(
112 struct xfs_btree_cur
*cur
,
118 fsbno
= XFS_DADDR_TO_FSB(cur
->bc_mp
, XFS_BUF_ADDR(bp
));
119 error
= xfs_free_extent(cur
->bc_tp
, fsbno
, 1);
123 xfs_trans_binval(cur
->bc_tp
, bp
);
128 xfs_inobt_get_maxrecs(
129 struct xfs_btree_cur
*cur
,
132 return cur
->bc_mp
->m_inobt_mxr
[level
!= 0];
136 xfs_inobt_init_key_from_rec(
137 union xfs_btree_key
*key
,
138 union xfs_btree_rec
*rec
)
140 key
->inobt
.ir_startino
= rec
->inobt
.ir_startino
;
144 xfs_inobt_init_rec_from_key(
145 union xfs_btree_key
*key
,
146 union xfs_btree_rec
*rec
)
148 rec
->inobt
.ir_startino
= key
->inobt
.ir_startino
;
152 xfs_inobt_init_rec_from_cur(
153 struct xfs_btree_cur
*cur
,
154 union xfs_btree_rec
*rec
)
156 rec
->inobt
.ir_startino
= cpu_to_be32(cur
->bc_rec
.i
.ir_startino
);
157 rec
->inobt
.ir_freecount
= cpu_to_be32(cur
->bc_rec
.i
.ir_freecount
);
158 rec
->inobt
.ir_free
= cpu_to_be64(cur
->bc_rec
.i
.ir_free
);
162 * initial value of ptr for lookup
165 xfs_inobt_init_ptr_from_cur(
166 struct xfs_btree_cur
*cur
,
167 union xfs_btree_ptr
*ptr
)
169 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
171 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
173 ptr
->s
= agi
->agi_root
;
178 struct xfs_btree_cur
*cur
,
179 union xfs_btree_key
*key
)
181 return (__int64_t
)be32_to_cpu(key
->inobt
.ir_startino
) -
182 cur
->bc_rec
.i
.ir_startino
;
189 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
190 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
192 int sblock_ok
; /* block passes checks */
194 /* magic number and level verification */
195 level
= be16_to_cpu(block
->bb_level
);
196 sblock_ok
= block
->bb_magic
== cpu_to_be32(XFS_IBT_MAGIC
) &&
197 level
< mp
->m_in_maxlevels
;
199 /* numrecs verification */
200 sblock_ok
= sblock_ok
&&
201 be16_to_cpu(block
->bb_numrecs
) <= mp
->m_inobt_mxr
[level
!= 0];
203 /* sibling pointer verification */
204 sblock_ok
= sblock_ok
&&
205 (block
->bb_u
.s
.bb_leftsib
== cpu_to_be32(NULLAGBLOCK
) ||
206 be32_to_cpu(block
->bb_u
.s
.bb_leftsib
) < mp
->m_sb
.sb_agblocks
) &&
207 block
->bb_u
.s
.bb_leftsib
&&
208 (block
->bb_u
.s
.bb_rightsib
== cpu_to_be32(NULLAGBLOCK
) ||
209 be32_to_cpu(block
->bb_u
.s
.bb_rightsib
) < mp
->m_sb
.sb_agblocks
) &&
210 block
->bb_u
.s
.bb_rightsib
;
213 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
214 XFS_CORRUPTION_ERROR(__func__
, XFS_ERRLEVEL_LOW
, mp
, block
);
215 xfs_buf_ioerror(bp
, EFSCORRUPTED
);
220 xfs_inobt_read_verify(
223 xfs_inobt_verify(bp
);
227 xfs_inobt_write_verify(
230 xfs_inobt_verify(bp
);
233 const struct xfs_buf_ops xfs_inobt_buf_ops
= {
234 .verify_read
= xfs_inobt_read_verify
,
235 .verify_write
= xfs_inobt_write_verify
,
240 xfs_inobt_keys_inorder(
241 struct xfs_btree_cur
*cur
,
242 union xfs_btree_key
*k1
,
243 union xfs_btree_key
*k2
)
245 return be32_to_cpu(k1
->inobt
.ir_startino
) <
246 be32_to_cpu(k2
->inobt
.ir_startino
);
250 xfs_inobt_recs_inorder(
251 struct xfs_btree_cur
*cur
,
252 union xfs_btree_rec
*r1
,
253 union xfs_btree_rec
*r2
)
255 return be32_to_cpu(r1
->inobt
.ir_startino
) + XFS_INODES_PER_CHUNK
<=
256 be32_to_cpu(r2
->inobt
.ir_startino
);
260 static const struct xfs_btree_ops xfs_inobt_ops
= {
261 .rec_len
= sizeof(xfs_inobt_rec_t
),
262 .key_len
= sizeof(xfs_inobt_key_t
),
264 .dup_cursor
= xfs_inobt_dup_cursor
,
265 .set_root
= xfs_inobt_set_root
,
266 .alloc_block
= xfs_inobt_alloc_block
,
267 .free_block
= xfs_inobt_free_block
,
268 .get_minrecs
= xfs_inobt_get_minrecs
,
269 .get_maxrecs
= xfs_inobt_get_maxrecs
,
270 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
271 .init_rec_from_key
= xfs_inobt_init_rec_from_key
,
272 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
273 .init_ptr_from_cur
= xfs_inobt_init_ptr_from_cur
,
274 .key_diff
= xfs_inobt_key_diff
,
275 .buf_ops
= &xfs_inobt_buf_ops
,
277 .keys_inorder
= xfs_inobt_keys_inorder
,
278 .recs_inorder
= xfs_inobt_recs_inorder
,
283 * Allocate a new inode btree cursor.
285 struct xfs_btree_cur
* /* new inode btree cursor */
286 xfs_inobt_init_cursor(
287 struct xfs_mount
*mp
, /* file system mount point */
288 struct xfs_trans
*tp
, /* transaction pointer */
289 struct xfs_buf
*agbp
, /* buffer for agi structure */
290 xfs_agnumber_t agno
) /* allocation group number */
292 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
293 struct xfs_btree_cur
*cur
;
295 cur
= kmem_zone_zalloc(xfs_btree_cur_zone
, KM_SLEEP
);
299 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_level
);
300 cur
->bc_btnum
= XFS_BTNUM_INO
;
301 cur
->bc_blocklog
= mp
->m_sb
.sb_blocklog
;
303 cur
->bc_ops
= &xfs_inobt_ops
;
305 cur
->bc_private
.a
.agbp
= agbp
;
306 cur
->bc_private
.a
.agno
= agno
;
312 * Calculate number of records in an inobt btree block.
316 struct xfs_mount
*mp
,
320 blocklen
-= XFS_INOBT_BLOCK_LEN(mp
);
323 return blocklen
/ sizeof(xfs_inobt_rec_t
);
324 return blocklen
/ (sizeof(xfs_inobt_key_t
) + sizeof(xfs_inobt_ptr_t
));