1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
6 #include "libxfs_priv.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_inode.h"
15 #include "xfs_btree.h"
16 #include "xfs_ialloc.h"
17 #include "xfs_ialloc_btree.h"
18 #include "xfs_alloc.h"
19 #include "xfs_trace.h"
20 #include "xfs_cksum.h"
21 #include "xfs_trans.h"
26 xfs_inobt_get_minrecs(
27 struct xfs_btree_cur
*cur
,
30 return cur
->bc_mp
->m_inobt_mnr
[level
!= 0];
33 STATIC
struct xfs_btree_cur
*
35 struct xfs_btree_cur
*cur
)
37 return xfs_inobt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
38 cur
->bc_private
.a
.agbp
, cur
->bc_private
.a
.agno
,
44 struct xfs_btree_cur
*cur
,
45 union xfs_btree_ptr
*nptr
,
46 int inc
) /* level change */
48 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
49 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
51 agi
->agi_root
= nptr
->s
;
52 be32_add_cpu(&agi
->agi_level
, inc
);
53 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
, XFS_AGI_ROOT
| XFS_AGI_LEVEL
);
58 struct xfs_btree_cur
*cur
,
59 union xfs_btree_ptr
*nptr
,
60 int inc
) /* level change */
62 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
63 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
65 agi
->agi_free_root
= nptr
->s
;
66 be32_add_cpu(&agi
->agi_free_level
, inc
);
67 xfs_ialloc_log_agi(cur
->bc_tp
, agbp
,
68 XFS_AGI_FREE_ROOT
| XFS_AGI_FREE_LEVEL
);
72 __xfs_inobt_alloc_block(
73 struct xfs_btree_cur
*cur
,
74 union xfs_btree_ptr
*start
,
75 union xfs_btree_ptr
*new,
77 enum xfs_ag_resv_type resv
)
79 xfs_alloc_arg_t args
; /* block allocation args */
80 int error
; /* error return value */
81 xfs_agblock_t sbno
= be32_to_cpu(start
->s
);
83 memset(&args
, 0, sizeof(args
));
86 args
.oinfo
= XFS_RMAP_OINFO_INOBT
;
87 args
.fsbno
= XFS_AGB_TO_FSB(args
.mp
, cur
->bc_private
.a
.agno
, sbno
);
91 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
94 error
= xfs_alloc_vextent(&args
);
98 if (args
.fsbno
== NULLFSBLOCK
) {
102 ASSERT(args
.len
== 1);
104 new->s
= cpu_to_be32(XFS_FSB_TO_AGBNO(args
.mp
, args
.fsbno
));
110 xfs_inobt_alloc_block(
111 struct xfs_btree_cur
*cur
,
112 union xfs_btree_ptr
*start
,
113 union xfs_btree_ptr
*new,
116 return __xfs_inobt_alloc_block(cur
, start
, new, stat
, XFS_AG_RESV_NONE
);
120 xfs_finobt_alloc_block(
121 struct xfs_btree_cur
*cur
,
122 union xfs_btree_ptr
*start
,
123 union xfs_btree_ptr
*new,
126 if (cur
->bc_mp
->m_finobt_nores
)
127 return xfs_inobt_alloc_block(cur
, start
, new, stat
);
128 return __xfs_inobt_alloc_block(cur
, start
, new, stat
,
129 XFS_AG_RESV_METADATA
);
133 __xfs_inobt_free_block(
134 struct xfs_btree_cur
*cur
,
136 enum xfs_ag_resv_type resv
)
138 return xfs_free_extent(cur
->bc_tp
,
139 XFS_DADDR_TO_FSB(cur
->bc_mp
, XFS_BUF_ADDR(bp
)), 1,
140 &XFS_RMAP_OINFO_INOBT
, resv
);
144 xfs_inobt_free_block(
145 struct xfs_btree_cur
*cur
,
148 return __xfs_inobt_free_block(cur
, bp
, XFS_AG_RESV_NONE
);
152 xfs_finobt_free_block(
153 struct xfs_btree_cur
*cur
,
156 if (cur
->bc_mp
->m_finobt_nores
)
157 return xfs_inobt_free_block(cur
, bp
);
158 return __xfs_inobt_free_block(cur
, bp
, XFS_AG_RESV_METADATA
);
162 xfs_inobt_get_maxrecs(
163 struct xfs_btree_cur
*cur
,
166 return cur
->bc_mp
->m_inobt_mxr
[level
!= 0];
170 xfs_inobt_init_key_from_rec(
171 union xfs_btree_key
*key
,
172 union xfs_btree_rec
*rec
)
174 key
->inobt
.ir_startino
= rec
->inobt
.ir_startino
;
178 xfs_inobt_init_high_key_from_rec(
179 union xfs_btree_key
*key
,
180 union xfs_btree_rec
*rec
)
184 x
= be32_to_cpu(rec
->inobt
.ir_startino
);
185 x
+= XFS_INODES_PER_CHUNK
- 1;
186 key
->inobt
.ir_startino
= cpu_to_be32(x
);
190 xfs_inobt_init_rec_from_cur(
191 struct xfs_btree_cur
*cur
,
192 union xfs_btree_rec
*rec
)
194 rec
->inobt
.ir_startino
= cpu_to_be32(cur
->bc_rec
.i
.ir_startino
);
195 if (xfs_sb_version_hassparseinodes(&cur
->bc_mp
->m_sb
)) {
196 rec
->inobt
.ir_u
.sp
.ir_holemask
=
197 cpu_to_be16(cur
->bc_rec
.i
.ir_holemask
);
198 rec
->inobt
.ir_u
.sp
.ir_count
= cur
->bc_rec
.i
.ir_count
;
199 rec
->inobt
.ir_u
.sp
.ir_freecount
= cur
->bc_rec
.i
.ir_freecount
;
201 /* ir_holemask/ir_count not supported on-disk */
202 rec
->inobt
.ir_u
.f
.ir_freecount
=
203 cpu_to_be32(cur
->bc_rec
.i
.ir_freecount
);
205 rec
->inobt
.ir_free
= cpu_to_be64(cur
->bc_rec
.i
.ir_free
);
209 * initial value of ptr for lookup
212 xfs_inobt_init_ptr_from_cur(
213 struct xfs_btree_cur
*cur
,
214 union xfs_btree_ptr
*ptr
)
216 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
218 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
220 ptr
->s
= agi
->agi_root
;
224 xfs_finobt_init_ptr_from_cur(
225 struct xfs_btree_cur
*cur
,
226 union xfs_btree_ptr
*ptr
)
228 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(cur
->bc_private
.a
.agbp
);
230 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agi
->agi_seqno
));
231 ptr
->s
= agi
->agi_free_root
;
236 struct xfs_btree_cur
*cur
,
237 union xfs_btree_key
*key
)
239 return (int64_t)be32_to_cpu(key
->inobt
.ir_startino
) -
240 cur
->bc_rec
.i
.ir_startino
;
244 xfs_inobt_diff_two_keys(
245 struct xfs_btree_cur
*cur
,
246 union xfs_btree_key
*k1
,
247 union xfs_btree_key
*k2
)
249 return (int64_t)be32_to_cpu(k1
->inobt
.ir_startino
) -
250 be32_to_cpu(k2
->inobt
.ir_startino
);
253 static xfs_failaddr_t
257 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
258 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
262 if (!xfs_verify_magic(bp
, block
->bb_magic
))
263 return __this_address
;
266 * During growfs operations, we can't verify the exact owner as the
267 * perag is not fully initialised and hence not attached to the buffer.
269 * Similarly, during log recovery we will have a perag structure
270 * attached, but the agi information will not yet have been initialised
271 * from the on disk AGI. We don't currently use any of this information,
272 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
275 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
276 fa
= xfs_btree_sblock_v5hdr_verify(bp
);
281 /* level verification */
282 level
= be16_to_cpu(block
->bb_level
);
283 if (level
>= mp
->m_in_maxlevels
)
284 return __this_address
;
286 return xfs_btree_sblock_verify(bp
, mp
->m_inobt_mxr
[level
!= 0]);
290 xfs_inobt_read_verify(
295 if (!xfs_btree_sblock_verify_crc(bp
))
296 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
298 fa
= xfs_inobt_verify(bp
);
300 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
304 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
308 xfs_inobt_write_verify(
313 fa
= xfs_inobt_verify(bp
);
315 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
316 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
319 xfs_btree_sblock_calc_crc(bp
);
323 const struct xfs_buf_ops xfs_inobt_buf_ops
= {
325 .magic
= { cpu_to_be32(XFS_IBT_MAGIC
), cpu_to_be32(XFS_IBT_CRC_MAGIC
) },
326 .verify_read
= xfs_inobt_read_verify
,
327 .verify_write
= xfs_inobt_write_verify
,
328 .verify_struct
= xfs_inobt_verify
,
331 const struct xfs_buf_ops xfs_finobt_buf_ops
= {
332 .name
= "xfs_finobt",
333 .magic
= { cpu_to_be32(XFS_FIBT_MAGIC
),
334 cpu_to_be32(XFS_FIBT_CRC_MAGIC
) },
335 .verify_read
= xfs_inobt_read_verify
,
336 .verify_write
= xfs_inobt_write_verify
,
337 .verify_struct
= xfs_inobt_verify
,
341 xfs_inobt_keys_inorder(
342 struct xfs_btree_cur
*cur
,
343 union xfs_btree_key
*k1
,
344 union xfs_btree_key
*k2
)
346 return be32_to_cpu(k1
->inobt
.ir_startino
) <
347 be32_to_cpu(k2
->inobt
.ir_startino
);
351 xfs_inobt_recs_inorder(
352 struct xfs_btree_cur
*cur
,
353 union xfs_btree_rec
*r1
,
354 union xfs_btree_rec
*r2
)
356 return be32_to_cpu(r1
->inobt
.ir_startino
) + XFS_INODES_PER_CHUNK
<=
357 be32_to_cpu(r2
->inobt
.ir_startino
);
360 static const struct xfs_btree_ops xfs_inobt_ops
= {
361 .rec_len
= sizeof(xfs_inobt_rec_t
),
362 .key_len
= sizeof(xfs_inobt_key_t
),
364 .dup_cursor
= xfs_inobt_dup_cursor
,
365 .set_root
= xfs_inobt_set_root
,
366 .alloc_block
= xfs_inobt_alloc_block
,
367 .free_block
= xfs_inobt_free_block
,
368 .get_minrecs
= xfs_inobt_get_minrecs
,
369 .get_maxrecs
= xfs_inobt_get_maxrecs
,
370 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
371 .init_high_key_from_rec
= xfs_inobt_init_high_key_from_rec
,
372 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
373 .init_ptr_from_cur
= xfs_inobt_init_ptr_from_cur
,
374 .key_diff
= xfs_inobt_key_diff
,
375 .buf_ops
= &xfs_inobt_buf_ops
,
376 .diff_two_keys
= xfs_inobt_diff_two_keys
,
377 .keys_inorder
= xfs_inobt_keys_inorder
,
378 .recs_inorder
= xfs_inobt_recs_inorder
,
381 static const struct xfs_btree_ops xfs_finobt_ops
= {
382 .rec_len
= sizeof(xfs_inobt_rec_t
),
383 .key_len
= sizeof(xfs_inobt_key_t
),
385 .dup_cursor
= xfs_inobt_dup_cursor
,
386 .set_root
= xfs_finobt_set_root
,
387 .alloc_block
= xfs_finobt_alloc_block
,
388 .free_block
= xfs_finobt_free_block
,
389 .get_minrecs
= xfs_inobt_get_minrecs
,
390 .get_maxrecs
= xfs_inobt_get_maxrecs
,
391 .init_key_from_rec
= xfs_inobt_init_key_from_rec
,
392 .init_high_key_from_rec
= xfs_inobt_init_high_key_from_rec
,
393 .init_rec_from_cur
= xfs_inobt_init_rec_from_cur
,
394 .init_ptr_from_cur
= xfs_finobt_init_ptr_from_cur
,
395 .key_diff
= xfs_inobt_key_diff
,
396 .buf_ops
= &xfs_finobt_buf_ops
,
397 .diff_two_keys
= xfs_inobt_diff_two_keys
,
398 .keys_inorder
= xfs_inobt_keys_inorder
,
399 .recs_inorder
= xfs_inobt_recs_inorder
,
403 * Allocate a new inode btree cursor.
405 struct xfs_btree_cur
* /* new inode btree cursor */
406 xfs_inobt_init_cursor(
407 struct xfs_mount
*mp
, /* file system mount point */
408 struct xfs_trans
*tp
, /* transaction pointer */
409 struct xfs_buf
*agbp
, /* buffer for agi structure */
410 xfs_agnumber_t agno
, /* allocation group number */
411 xfs_btnum_t btnum
) /* ialloc or free ino btree */
413 struct xfs_agi
*agi
= XFS_BUF_TO_AGI(agbp
);
414 struct xfs_btree_cur
*cur
;
416 cur
= kmem_zone_zalloc(xfs_btree_cur_zone
, KM_NOFS
);
420 cur
->bc_btnum
= btnum
;
421 if (btnum
== XFS_BTNUM_INO
) {
422 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_level
);
423 cur
->bc_ops
= &xfs_inobt_ops
;
424 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_ibt_2
);
426 cur
->bc_nlevels
= be32_to_cpu(agi
->agi_free_level
);
427 cur
->bc_ops
= &xfs_finobt_ops
;
428 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_fibt_2
);
431 cur
->bc_blocklog
= mp
->m_sb
.sb_blocklog
;
433 if (xfs_sb_version_hascrc(&mp
->m_sb
))
434 cur
->bc_flags
|= XFS_BTREE_CRC_BLOCKS
;
436 cur
->bc_private
.a
.agbp
= agbp
;
437 cur
->bc_private
.a
.agno
= agno
;
443 * Calculate number of records in an inobt btree block.
447 struct xfs_mount
*mp
,
451 blocklen
-= XFS_INOBT_BLOCK_LEN(mp
);
454 return blocklen
/ sizeof(xfs_inobt_rec_t
);
455 return blocklen
/ (sizeof(xfs_inobt_key_t
) + sizeof(xfs_inobt_ptr_t
));
459 * Convert the inode record holemask to an inode allocation bitmap. The inode
460 * allocation bitmap is inode granularity and specifies whether an inode is
461 * physically allocated on disk (not whether the inode is considered allocated
462 * or free by the fs).
464 * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
467 xfs_inobt_irec_to_allocmask(
468 struct xfs_inobt_rec_incore
*rec
)
476 * The holemask has 16-bits for a 64 inode record. Therefore each
477 * holemask bit represents multiple inodes. Create a mask of bits to set
478 * in the allocmask for each holemask bit.
480 inodespbit
= (1 << XFS_INODES_PER_HOLEMASK_BIT
) - 1;
483 * Allocated inodes are represented by 0 bits in holemask. Invert the 0
484 * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
485 * anything beyond the 16 holemask bits since this casts to a larger
488 allocbitmap
= ~rec
->ir_holemask
& ((1 << XFS_INOBT_HOLEMASK_BITS
) - 1);
491 * allocbitmap is the inverted holemask so every set bit represents
492 * allocated inodes. To expand from 16-bit holemask granularity to
493 * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
494 * bitmap for every holemask bit.
496 nextbit
= xfs_next_bit(&allocbitmap
, 1, 0);
497 while (nextbit
!= -1) {
498 ASSERT(nextbit
< (sizeof(rec
->ir_holemask
) * NBBY
));
500 bitmap
|= (inodespbit
<<
501 (nextbit
* XFS_INODES_PER_HOLEMASK_BIT
));
503 nextbit
= xfs_next_bit(&allocbitmap
, 1, nextbit
+ 1);
509 #if defined(DEBUG) || defined(XFS_WARN)
511 * Verify that an in-core inode record has a valid inode count.
514 xfs_inobt_rec_check_count(
515 struct xfs_mount
*mp
,
516 struct xfs_inobt_rec_incore
*rec
)
523 wordsz
= sizeof(allocbmap
) / sizeof(unsigned int);
524 allocbmap
= xfs_inobt_irec_to_allocmask(rec
);
526 nextbit
= xfs_next_bit((uint
*) &allocbmap
, wordsz
, nextbit
);
527 while (nextbit
!= -1) {
529 nextbit
= xfs_next_bit((uint
*) &allocbmap
, wordsz
,
533 if (inocount
!= rec
->ir_count
)
534 return -EFSCORRUPTED
;
542 struct xfs_mount
*mp
,
545 xfs_agblock_t agblocks
= xfs_ag_block_count(mp
, agno
);
547 /* Bail out if we're uninitialized, which can happen in mkfs. */
548 if (mp
->m_inobt_mxr
[0] == 0)
552 * The log is permanently allocated, so the space it occupies will
553 * never be available for the kinds of things that would require btree
554 * expansion. We therefore can pretend the space isn't there.
556 if (mp
->m_sb
.sb_logstart
&&
557 XFS_FSB_TO_AGNO(mp
, mp
->m_sb
.sb_logstart
) == agno
)
558 agblocks
-= mp
->m_sb
.sb_logblocks
;
560 return xfs_btree_calc_size(mp
->m_inobt_mnr
,
561 (uint64_t)agblocks
* mp
->m_sb
.sb_inopblock
/
562 XFS_INODES_PER_CHUNK
);
566 xfs_inobt_count_blocks(
567 struct xfs_mount
*mp
,
568 struct xfs_trans
*tp
,
571 xfs_extlen_t
*tree_blocks
)
573 struct xfs_buf
*agbp
;
574 struct xfs_btree_cur
*cur
;
577 error
= xfs_ialloc_read_agi(mp
, tp
, agno
, &agbp
);
581 cur
= xfs_inobt_init_cursor(mp
, tp
, agbp
, agno
, btnum
);
582 error
= xfs_btree_count_blocks(cur
, tree_blocks
);
583 xfs_btree_del_cursor(cur
, error
);
584 xfs_trans_brelse(tp
, agbp
);
590 * Figure out how many blocks to reserve and how many are used by this btree.
593 xfs_finobt_calc_reserves(
594 struct xfs_mount
*mp
,
595 struct xfs_trans
*tp
,
600 xfs_extlen_t tree_len
= 0;
603 if (!xfs_sb_version_hasfinobt(&mp
->m_sb
))
606 error
= xfs_inobt_count_blocks(mp
, tp
, agno
, XFS_BTNUM_FINO
, &tree_len
);
610 *ask
+= xfs_inobt_max_size(mp
, agno
);
615 /* Calculate the inobt btree size for some records. */
617 xfs_iallocbt_calc_size(
618 struct xfs_mount
*mp
,
619 unsigned long long len
)
621 return xfs_btree_calc_size(mp
->m_inobt_mnr
, len
);