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"
38 xfs_inobt_get_minrecs(
39 struct xfs_btree_cur
*cur
,
42 return cur
->bc_mp
->m_inobt_mnr
[level
!= 0];
45 STATIC
struct xfs_btree_cur
*
47 struct xfs_btree_cur
*cur
)
49 return xfs_inobt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
50 cur
->bc_private
.a
.agbp
, cur
->bc_private
.a
.agno
,
56 struct xfs_btree_cur
*cur
,
57 union xfs_btree_ptr
*nptr
,
58 int inc
) /* level change */
60 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
61 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
63 agi
->agi_root
= nptr
->s
;
64 be32_add_cpu(&agi
->agi_level
, inc
);
65 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
, XFS_AGI_ROOT
| XFS_AGI_LEVEL
);
70 struct xfs_btree_cur
*cur
,
71 union xfs_btree_ptr
*nptr
,
72 int inc
) /* level change */
74 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
75 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
77 agi
->agi_free_root
= nptr
->s
;
78 be32_add_cpu(&agi
->agi_free_level
, inc
);
79 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
,
80 XFS_AGI_FREE_ROOT
| XFS_AGI_FREE_LEVEL
);
84 __xfs_inobt_alloc_block(
85 struct xfs_btree_cur
*cur
,
86 union xfs_btree_ptr
*start
,
87 union xfs_btree_ptr
*new,
89 enum xfs_ag_resv_type resv
)
91 xfs_alloc_arg_t args
; /* block allocation args */
92 int error
; /* error return value */
93 xfs_agblock_t sbno
= be32_to_cpu(start
->s
);
95 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ENTRY
);
97 memset(&args
, 0, sizeof(args
));
100 xfs_rmap_ag_owner(&args
.oinfo
, XFS_RMAP_OWN_INOBT
);
101 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.a
.agno
, sbno
);
105 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
108 error
= xfs_alloc_vextent(&args
);
110 XFS_BTREE_TRACE_CURSOR(cur
, XBT_ERROR
);
113 if (args
.fsbno
== NULLFSBLOCK
) {
114 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
118 ASSERT(args
.len
== 1);
119 XFS_BTREE_TRACE_CURSOR(cur
, XBT_EXIT
);
121 new->s
= cpu_to_be32(XFS_FSB_TO_AGBNO(args
.mp
, args
.fsbno
));
127 xfs_inobt_alloc_block(
128 struct xfs_btree_cur
*cur
,
129 union xfs_btree_ptr
*start
,
130 union xfs_btree_ptr
*new,
133 return __xfs_inobt_alloc_block(cur
, start
, new, stat
, XFS_AG_RESV_NONE
);
137 xfs_finobt_alloc_block(
138 struct xfs_btree_cur
*cur
,
139 union xfs_btree_ptr
*start
,
140 union xfs_btree_ptr
*new,
143 return __xfs_inobt_alloc_block(cur
, start
, new, stat
,
144 XFS_AG_RESV_METADATA
);
148 xfs_inobt_free_block(
149 struct xfs_btree_cur
*cur
,
152 struct xfs_owner_info oinfo
;
154 xfs_rmap_ag_owner(&oinfo
, XFS_RMAP_OWN_INOBT
);
155 return xfs_free_extent(cur
->bc_tp
,
156 XFS_DADDR_TO_FSB(cur
->bc_mp
, XFS_BUF_ADDR(bp
)), 1,
157 &oinfo
, XFS_AG_RESV_NONE
);
161 xfs_inobt_get_maxrecs(
162 struct xfs_btree_cur
*cur
,
165 return cur
->bc_mp
->m_inobt_mxr
[level
!= 0];
169 xfs_inobt_init_key_from_rec(
170 union xfs_btree_key
*key
,
171 union xfs_btree_rec
*rec
)
173 key
->inobt
.ir_startino
= rec
->inobt
.ir_startino
;
177 xfs_inobt_init_rec_from_cur(
178 struct xfs_btree_cur
*cur
,
179 union xfs_btree_rec
*rec
)
181 rec
->inobt
.ir_startino
= cpu_to_be32(cur
->bc_rec
.i
.ir_startino
);
182 if (xfs_sb_version_hassparseinodes(&cur
->bc_mp
->m_sb
)) {
183 rec
->inobt
.ir_u
.sp
.ir_holemask
=
184 cpu_to_be16(cur
->bc_rec
.i
.ir_holemask
);
185 rec
->inobt
.ir_u
.sp
.ir_count
= cur
->bc_rec
.i
.ir_count
;
186 rec
->inobt
.ir_u
.sp
.ir_freecount
= cur
->bc_rec
.i
.ir_freecount
;
188 /* ir_holemask/ir_count not supported on-disk */
189 rec
->inobt
.ir_u
.f
.ir_freecount
=
190 cpu_to_be32(cur
->bc_rec
.i
.ir_freecount
);
192 rec
->inobt
.ir_free
= cpu_to_be64(cur
->bc_rec
.i
.ir_free
);
196 * initial value of ptr for lookup
199 xfs_inobt_init_ptr_from_cur(
200 struct xfs_btree_cur
*cur
,
201 union xfs_btree_ptr
*ptr
)
203 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
205 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
207 ptr
->s
= agi
->agi_root
;
211 xfs_finobt_init_ptr_from_cur(
212 struct xfs_btree_cur
*cur
,
213 union xfs_btree_ptr
*ptr
)
215 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
217 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
218 ptr
->s
= agi
->agi_free_root
;
223 struct xfs_btree_cur
*cur
,
224 union xfs_btree_key
*key
)
226 return (int64_t)be32_to_cpu(key
->inobt
.ir_startino
) -
227 cur
->bc_rec
.i
.ir_startino
;
234 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
235 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
239 * During growfs operations, we can't verify the exact owner as the
240 * perag is not fully initialised and hence not attached to the buffer.
242 * Similarly, during log recovery we will have a perag structure
243 * attached, but the agi information will not yet have been initialised
244 * from the on disk AGI. We don't currently use any of this information,
245 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
248 switch (block
->bb_magic
) {
249 case cpu_to_be32(XFS_IBT_CRC_MAGIC
):
250 case cpu_to_be32(XFS_FIBT_CRC_MAGIC
):
251 if (!xfs_btree_sblock_v5hdr_verify(bp
))
254 case cpu_to_be32(XFS_IBT_MAGIC
):
255 case cpu_to_be32(XFS_FIBT_MAGIC
):
261 /* level verification */
262 level
= be16_to_cpu(block
->bb_level
);
263 if (level
>= mp
->m_in_maxlevels
)
266 return xfs_btree_sblock_verify(bp
, mp
->m_inobt_mxr
[level
!= 0]);
270 xfs_inobt_read_verify(
273 if (!xfs_btree_sblock_verify_crc(bp
))
274 xfs_buf_ioerror(bp
, -EFSBADCRC
);
275 else if (!xfs_inobt_verify(bp
))
276 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
279 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
280 xfs_verifier_error(bp
);
285 xfs_inobt_write_verify(
288 if (!xfs_inobt_verify(bp
)) {
289 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
290 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
291 xfs_verifier_error(bp
);
294 xfs_btree_sblock_calc_crc(bp
);
298 const struct xfs_buf_ops xfs_inobt_buf_ops
= {
300 .verify_read
= xfs_inobt_read_verify
,
301 .verify_write
= xfs_inobt_write_verify
,
304 #if defined(DEBUG) || defined(XFS_WARN)
306 xfs_inobt_keys_inorder(
307 struct xfs_btree_cur
*cur
,
308 union xfs_btree_key
*k1
,
309 union xfs_btree_key
*k2
)
311 return be32_to_cpu(k1
->inobt
.ir_startino
) <
312 be32_to_cpu(k2
->inobt
.ir_startino
);
316 xfs_inobt_recs_inorder(
317 struct xfs_btree_cur
*cur
,
318 union xfs_btree_rec
*r1
,
319 union xfs_btree_rec
*r2
)
321 return be32_to_cpu(r1
->inobt
.ir_startino
) + XFS_INODES_PER_CHUNK
<=
322 be32_to_cpu(r2
->inobt
.ir_startino
);
326 static const struct xfs_btree_ops xfs_inobt_ops
= {
327 .rec_len
= sizeof(xfs_inobt_rec_t
),
328 .key_len
= sizeof(xfs_inobt_key_t
),
330 .dup_cursor
= xfs_inobt_dup_cursor
,
331 .set_root
= xfs_inobt_set_root
,
332 .alloc_block
= xfs_inobt_alloc_block
,
333 .free_block
= xfs_inobt_free_block
,
334 .get_minrecs
= xfs_inobt_get_minrecs
,
335 .get_maxrecs
= xfs_inobt_get_maxrecs
,
336 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
337 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
338 .init_ptr_from_cur
= xfs_inobt_init_ptr_from_cur
,
339 .key_diff
= xfs_inobt_key_diff
,
340 .buf_ops
= &xfs_inobt_buf_ops
,
341 #if defined(DEBUG) || defined(XFS_WARN)
342 .keys_inorder
= xfs_inobt_keys_inorder
,
343 .recs_inorder
= xfs_inobt_recs_inorder
,
347 static const struct xfs_btree_ops xfs_finobt_ops
= {
348 .rec_len
= sizeof(xfs_inobt_rec_t
),
349 .key_len
= sizeof(xfs_inobt_key_t
),
351 .dup_cursor
= xfs_inobt_dup_cursor
,
352 .set_root
= xfs_finobt_set_root
,
353 .alloc_block
= xfs_finobt_alloc_block
,
354 .free_block
= xfs_inobt_free_block
,
355 .get_minrecs
= xfs_inobt_get_minrecs
,
356 .get_maxrecs
= xfs_inobt_get_maxrecs
,
357 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
358 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
359 .init_ptr_from_cur
= xfs_finobt_init_ptr_from_cur
,
360 .key_diff
= xfs_inobt_key_diff
,
361 .buf_ops
= &xfs_inobt_buf_ops
,
362 #if defined(DEBUG) || defined(XFS_WARN)
363 .keys_inorder
= xfs_inobt_keys_inorder
,
364 .recs_inorder
= xfs_inobt_recs_inorder
,
369 * Allocate a new inode btree cursor.
371 struct xfs_btree_cur
* /* new inode btree cursor */
372 xfs_inobt_init_cursor(
373 struct xfs_mount
*mp
, /* file system mount point */
374 struct xfs_trans
*tp
, /* transaction pointer */
375 struct xfs_buf
*agbp
, /* buffer for agi structure */
376 xfs_agnumber_t agno
, /* allocation group number */
377 xfs_btnum_t btnum
) /* ialloc or free ino btree */
379 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
380 struct xfs_btree_cur
*cur
;
382 cur
= kmem_zone_zalloc(xfs_btree_cur_zone
, KM_NOFS
);
386 cur
->bc_btnum
= btnum
;
387 if (btnum
== XFS_BTNUM_INO
) {
388 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_level
);
389 cur
->bc_ops
= &xfs_inobt_ops
;
390 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_ibt_2
);
392 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_free_level
);
393 cur
->bc_ops
= &xfs_finobt_ops
;
394 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_fibt_2
);
397 cur
->bc_blocklog
= mp
->m_sb
.sb_blocklog
;
399 if (xfs_sb_version_hascrc(&mp
->m_sb
))
400 cur
->bc_flags
|= XFS_BTREE_CRC_BLOCKS
;
402 cur
->bc_private
.a
.agbp
= agbp
;
403 cur
->bc_private
.a
.agno
= agno
;
409 * Calculate number of records in an inobt btree block.
413 struct xfs_mount
*mp
,
417 blocklen
-= XFS_INOBT_BLOCK_LEN(mp
);
420 return blocklen
/ sizeof(xfs_inobt_rec_t
);
421 return blocklen
/ (sizeof(xfs_inobt_key_t
) + sizeof(xfs_inobt_ptr_t
));
425 * Convert the inode record holemask to an inode allocation bitmap. The inode
426 * allocation bitmap is inode granularity and specifies whether an inode is
427 * physically allocated on disk (not whether the inode is considered allocated
428 * or free by the fs).
430 * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
433 xfs_inobt_irec_to_allocmask(
434 struct xfs_inobt_rec_incore
*rec
)
442 * The holemask has 16-bits for a 64 inode record. Therefore each
443 * holemask bit represents multiple inodes. Create a mask of bits to set
444 * in the allocmask for each holemask bit.
446 inodespbit
= (1 << XFS_INODES_PER_HOLEMASK_BIT
) - 1;
449 * Allocated inodes are represented by 0 bits in holemask. Invert the 0
450 * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
451 * anything beyond the 16 holemask bits since this casts to a larger
454 allocbitmap
= ~rec
->ir_holemask
& ((1 << XFS_INOBT_HOLEMASK_BITS
) - 1);
457 * allocbitmap is the inverted holemask so every set bit represents
458 * allocated inodes. To expand from 16-bit holemask granularity to
459 * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
460 * bitmap for every holemask bit.
462 nextbit
= xfs_next_bit(&allocbitmap
, 1, 0);
463 while (nextbit
!= -1) {
464 ASSERT(nextbit
< (sizeof(rec
->ir_holemask
) * NBBY
));
466 bitmap
|= (inodespbit
<<
467 (nextbit
* XFS_INODES_PER_HOLEMASK_BIT
));
469 nextbit
= xfs_next_bit(&allocbitmap
, 1, nextbit
+ 1);
475 #if defined(DEBUG) || defined(XFS_WARN)
477 * Verify that an in-core inode record has a valid inode count.
480 xfs_inobt_rec_check_count(
481 struct xfs_mount
*mp
,
482 struct xfs_inobt_rec_incore
*rec
)
489 wordsz
= sizeof(allocbmap
) / sizeof(unsigned int);
490 allocbmap
= xfs_inobt_irec_to_allocmask(rec
);
492 nextbit
= xfs_next_bit((uint
*) &allocbmap
, wordsz
, nextbit
);
493 while (nextbit
!= -1) {
495 nextbit
= xfs_next_bit((uint
*) &allocbmap
, wordsz
,
499 if (inocount
!= rec
->ir_count
)
500 return -EFSCORRUPTED
;
508 struct xfs_mount
*mp
)
510 /* Bail out if we're uninitialized, which can happen in mkfs. */
511 if (mp
->m_inobt_mxr
[0] == 0)
514 return xfs_btree_calc_size(mp
, mp
->m_inobt_mnr
,
515 (uint64_t)mp
->m_sb
.sb_agblocks
* mp
->m_sb
.sb_inopblock
/
516 XFS_INODES_PER_CHUNK
);
520 xfs_inobt_count_blocks(
521 struct xfs_mount
*mp
,
524 xfs_extlen_t
*tree_blocks
)
526 struct xfs_buf
*agbp
;
527 struct xfs_btree_cur
*cur
;
530 error
= xfs_ialloc_read_agi(mp
, NULL
, agno
, &agbp
);
534 cur
= xfs_inobt_init_cursor(mp
, NULL
, agbp
, agno
, btnum
);
535 error
= xfs_btree_count_blocks(cur
, tree_blocks
);
536 xfs_btree_del_cursor(cur
, error
? XFS_BTREE_ERROR
: XFS_BTREE_NOERROR
);
543 * Figure out how many blocks to reserve and how many are used by this btree.
546 xfs_finobt_calc_reserves(
547 struct xfs_mount
*mp
,
552 xfs_extlen_t tree_len
= 0;
555 if (!xfs_sb_version_hasfinobt(&mp
->m_sb
))
558 error
= xfs_inobt_count_blocks(mp
, agno
, XFS_BTNUM_FINO
, &tree_len
);
562 *ask
+= xfs_inobt_max_size(mp
);