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
18 #include "libxfs_priv.h"
20 #include "xfs_shared.h"
21 #include "xfs_format.h"
22 #include "xfs_log_format.h"
23 #include "xfs_trans_resv.h"
25 #include "xfs_mount.h"
26 #include "xfs_inode.h"
27 #include "xfs_btree.h"
28 #include "xfs_ialloc.h"
29 #include "xfs_ialloc_btree.h"
30 #include "xfs_alloc.h"
31 #include "xfs_trace.h"
32 #include "xfs_cksum.h"
33 #include "xfs_trans.h"
37 xfs_inobt_get_minrecs(
38 struct xfs_btree_cur
*cur
,
41 return cur
->bc_mp
->m_inobt_mnr
[level
!= 0];
44 STATIC
struct xfs_btree_cur
*
46 struct xfs_btree_cur
*cur
)
48 return xfs_inobt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
49 cur
->bc_private
.a
.agbp
, cur
->bc_private
.a
.agno
,
55 struct xfs_btree_cur
*cur
,
56 union xfs_btree_ptr
*nptr
,
57 int inc
) /* level change */
59 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
60 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
62 agi
->agi_root
= nptr
->s
;
63 be32_add_cpu(&agi
->agi_level
, inc
);
64 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
, XFS_AGI_ROOT
| XFS_AGI_LEVEL
);
69 struct xfs_btree_cur
*cur
,
70 union xfs_btree_ptr
*nptr
,
71 int inc
) /* level change */
73 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
74 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
76 agi
->agi_free_root
= nptr
->s
;
77 be32_add_cpu(&agi
->agi_free_level
, inc
);
78 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
,
79 XFS_AGI_FREE_ROOT
| XFS_AGI_FREE_LEVEL
);
83 xfs_inobt_alloc_block(
84 struct xfs_btree_cur
*cur
,
85 union xfs_btree_ptr
*start
,
86 union xfs_btree_ptr
*new,
89 xfs_alloc_arg_t args
; /* block allocation args */
90 int error
; /* error return value */
91 xfs_agblock_t sbno
= be32_to_cpu(start
->s
);
93 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ENTRY
);
95 memset(&args
, 0, sizeof(args
));
98 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.a
.agno
, sbno
);
102 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
104 error
= xfs_alloc_vextent(&args
);
106 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ERROR
);
109 if (args
.fsbno
== NULLFSBLOCK
) {
110 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
114 ASSERT(args
.len
== 1);
115 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
117 new->s
= cpu_to_be32(XFS_FSB_TO_AGBNO(args
.mp
, args
.fsbno
));
123 xfs_inobt_free_block(
124 struct xfs_btree_cur
*cur
,
130 fsbno
= XFS_DADDR_TO_FSB(cur
->bc_mp
, XFS_BUF_ADDR(bp
));
131 error
= xfs_free_extent(cur
->bc_tp
, fsbno
, 1);
135 xfs_trans_binval(cur
->bc_tp
, bp
);
140 xfs_inobt_get_maxrecs(
141 struct xfs_btree_cur
*cur
,
144 return cur
->bc_mp
->m_inobt_mxr
[level
!= 0];
148 xfs_inobt_init_key_from_rec(
149 union xfs_btree_key
*key
,
150 union xfs_btree_rec
*rec
)
152 key
->inobt
.ir_startino
= rec
->inobt
.ir_startino
;
156 xfs_inobt_init_rec_from_key(
157 union xfs_btree_key
*key
,
158 union xfs_btree_rec
*rec
)
160 rec
->inobt
.ir_startino
= key
->inobt
.ir_startino
;
164 xfs_inobt_init_rec_from_cur(
165 struct xfs_btree_cur
*cur
,
166 union xfs_btree_rec
*rec
)
168 rec
->inobt
.ir_startino
= cpu_to_be32(cur
->bc_rec
.i
.ir_startino
);
169 rec
->inobt
.ir_freecount
= cpu_to_be32(cur
->bc_rec
.i
.ir_freecount
);
170 rec
->inobt
.ir_free
= cpu_to_be64(cur
->bc_rec
.i
.ir_free
);
174 * initial value of ptr for lookup
177 xfs_inobt_init_ptr_from_cur(
178 struct xfs_btree_cur
*cur
,
179 union xfs_btree_ptr
*ptr
)
181 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
183 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
185 ptr
->s
= agi
->agi_root
;
189 xfs_finobt_init_ptr_from_cur(
190 struct xfs_btree_cur
*cur
,
191 union xfs_btree_ptr
*ptr
)
193 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
195 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
196 ptr
->s
= agi
->agi_free_root
;
201 struct xfs_btree_cur
*cur
,
202 union xfs_btree_key
*key
)
204 return (__int64_t
)be32_to_cpu(key
->inobt
.ir_startino
) -
205 cur
->bc_rec
.i
.ir_startino
;
212 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
213 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
214 struct xfs_perag
*pag
= bp
->b_pag
;
218 * During growfs operations, we can't verify the exact owner as the
219 * perag is not fully initialised and hence not attached to the buffer.
221 * Similarly, during log recovery we will have a perag structure
222 * attached, but the agi information will not yet have been initialised
223 * from the on disk AGI. We don't currently use any of this information,
224 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
227 switch (block
->bb_magic
) {
228 case cpu_to_be32(XFS_IBT_CRC_MAGIC
):
229 case cpu_to_be32(XFS_FIBT_CRC_MAGIC
):
230 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
232 if (!uuid_equal(&block
->bb_u
.s
.bb_uuid
, &mp
->m_sb
.sb_uuid
))
234 if (block
->bb_u
.s
.bb_blkno
!= cpu_to_be64(bp
->b_bn
))
237 be32_to_cpu(block
->bb_u
.s
.bb_owner
) != pag
->pag_agno
)
240 case cpu_to_be32(XFS_IBT_MAGIC
):
241 case cpu_to_be32(XFS_FIBT_MAGIC
):
247 /* numrecs and level verification */
248 level
= be16_to_cpu(block
->bb_level
);
249 if (level
>= mp
->m_in_maxlevels
)
251 if (be16_to_cpu(block
->bb_numrecs
) > mp
->m_inobt_mxr
[level
!= 0])
254 /* sibling pointer verification */
255 if (!block
->bb_u
.s
.bb_leftsib
||
256 (be32_to_cpu(block
->bb_u
.s
.bb_leftsib
) >= mp
->m_sb
.sb_agblocks
&&
257 block
->bb_u
.s
.bb_leftsib
!= cpu_to_be32(NULLAGBLOCK
)))
259 if (!block
->bb_u
.s
.bb_rightsib
||
260 (be32_to_cpu(block
->bb_u
.s
.bb_rightsib
) >= mp
->m_sb
.sb_agblocks
&&
261 block
->bb_u
.s
.bb_rightsib
!= cpu_to_be32(NULLAGBLOCK
)))
268 xfs_inobt_read_verify(
271 if (!xfs_btree_sblock_verify_crc(bp
))
272 xfs_buf_ioerror(bp
, -EFSBADCRC
);
273 else if (!xfs_inobt_verify(bp
))
274 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
277 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
278 xfs_verifier_error(bp
);
283 xfs_inobt_write_verify(
286 if (!xfs_inobt_verify(bp
)) {
287 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
288 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
289 xfs_verifier_error(bp
);
292 xfs_btree_sblock_calc_crc(bp
);
296 const struct xfs_buf_ops xfs_inobt_buf_ops
= {
297 .verify_read
= xfs_inobt_read_verify
,
298 .verify_write
= xfs_inobt_write_verify
,
301 #if defined(DEBUG) || defined(XFS_WARN)
303 xfs_inobt_keys_inorder(
304 struct xfs_btree_cur
*cur
,
305 union xfs_btree_key
*k1
,
306 union xfs_btree_key
*k2
)
308 return be32_to_cpu(k1
->inobt
.ir_startino
) <
309 be32_to_cpu(k2
->inobt
.ir_startino
);
313 xfs_inobt_recs_inorder(
314 struct xfs_btree_cur
*cur
,
315 union xfs_btree_rec
*r1
,
316 union xfs_btree_rec
*r2
)
318 return be32_to_cpu(r1
->inobt
.ir_startino
) + XFS_INODES_PER_CHUNK
<=
319 be32_to_cpu(r2
->inobt
.ir_startino
);
323 static const struct xfs_btree_ops xfs_inobt_ops
= {
324 .rec_len
= sizeof(xfs_inobt_rec_t
),
325 .key_len
= sizeof(xfs_inobt_key_t
),
327 .dup_cursor
= xfs_inobt_dup_cursor
,
328 .set_root
= xfs_inobt_set_root
,
329 .alloc_block
= xfs_inobt_alloc_block
,
330 .free_block
= xfs_inobt_free_block
,
331 .get_minrecs
= xfs_inobt_get_minrecs
,
332 .get_maxrecs
= xfs_inobt_get_maxrecs
,
333 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
334 .init_rec_from_key
= xfs_inobt_init_rec_from_key
,
335 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
336 .init_ptr_from_cur
= xfs_inobt_init_ptr_from_cur
,
337 .key_diff
= xfs_inobt_key_diff
,
338 .buf_ops
= &xfs_inobt_buf_ops
,
339 #if defined(DEBUG) || defined(XFS_WARN)
340 .keys_inorder
= xfs_inobt_keys_inorder
,
341 .recs_inorder
= xfs_inobt_recs_inorder
,
345 static const struct xfs_btree_ops xfs_finobt_ops
= {
346 .rec_len
= sizeof(xfs_inobt_rec_t
),
347 .key_len
= sizeof(xfs_inobt_key_t
),
349 .dup_cursor
= xfs_inobt_dup_cursor
,
350 .set_root
= xfs_finobt_set_root
,
351 .alloc_block
= xfs_inobt_alloc_block
,
352 .free_block
= xfs_inobt_free_block
,
353 .get_minrecs
= xfs_inobt_get_minrecs
,
354 .get_maxrecs
= xfs_inobt_get_maxrecs
,
355 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
356 .init_rec_from_key
= xfs_inobt_init_rec_from_key
,
357 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
358 .init_ptr_from_cur
= xfs_finobt_init_ptr_from_cur
,
359 .key_diff
= xfs_inobt_key_diff
,
360 .buf_ops
= &xfs_inobt_buf_ops
,
361 #if defined(DEBUG) || defined(XFS_WARN)
362 .keys_inorder
= xfs_inobt_keys_inorder
,
363 .recs_inorder
= xfs_inobt_recs_inorder
,
368 * Allocate a new inode btree cursor.
370 struct xfs_btree_cur
* /* new inode btree cursor */
371 xfs_inobt_init_cursor(
372 struct xfs_mount
*mp
, /* file system mount point */
373 struct xfs_trans
*tp
, /* transaction pointer */
374 struct xfs_buf
*agbp
, /* buffer for agi structure */
375 xfs_agnumber_t agno
, /* allocation group number */
376 xfs_btnum_t btnum
) /* ialloc or free ino btree */
378 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
379 struct xfs_btree_cur
*cur
;
381 cur
= kmem_zone_zalloc(xfs_btree_cur_zone
, KM_SLEEP
);
385 cur
->bc_btnum
= btnum
;
386 if (btnum
== XFS_BTNUM_INO
) {
387 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_level
);
388 cur
->bc_ops
= &xfs_inobt_ops
;
390 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_free_level
);
391 cur
->bc_ops
= &xfs_finobt_ops
;
394 cur
->bc_blocklog
= mp
->m_sb
.sb_blocklog
;
396 if (xfs_sb_version_hascrc(&mp
->m_sb
))
397 cur
->bc_flags
|= XFS_BTREE_CRC_BLOCKS
;
399 cur
->bc_private
.a
.agbp
= agbp
;
400 cur
->bc_private
.a
.agno
= agno
;
406 * Calculate number of records in an inobt btree block.
410 struct xfs_mount
*mp
,
414 blocklen
-= XFS_INOBT_BLOCK_LEN(mp
);
417 return blocklen
/ sizeof(xfs_inobt_rec_t
);
418 return blocklen
/ (sizeof(xfs_inobt_key_t
) + sizeof(xfs_inobt_ptr_t
));