1 // SPDX-License-Identifier: GPL-2.0+
3 * Copyright (C) 2016 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
8 #include "err_protos.h"
15 #include "libfrog/bitmap.h"
20 # define dbg_printf(f, a...) do {printf(f, ## a); fflush(stdout); } while (0)
22 # define dbg_printf(f, a...)
25 /* per-AG rmap object anchor */
27 struct xfs_slab
*ar_rmaps
; /* rmap observations, p4 */
28 struct xfs_slab
*ar_raw_rmaps
; /* unmerged rmaps */
29 int ar_flcount
; /* agfl entries from leftover */
30 /* agbt allocations */
31 struct xfs_rmap_irec ar_last_rmap
; /* last rmap seen */
32 struct xfs_slab
*ar_refcount_items
; /* refcount items, p4-5 */
35 static struct xfs_ag_rmap
*ag_rmaps
;
36 static bool rmapbt_suspect
;
37 static bool refcbt_suspect
;
39 static inline int rmap_compare(const void *a
, const void *b
)
41 return libxfs_rmap_compare(a
, b
);
45 * Returns true if we must reconstruct either the reference count or reverse
52 return xfs_sb_version_hasreflink(&mp
->m_sb
) ||
53 xfs_sb_version_hasrmapbt(&mp
->m_sb
);
57 * Initialize per-AG reverse map data.
66 if (!rmap_needs_work(mp
))
69 ag_rmaps
= calloc(mp
->m_sb
.sb_agcount
, sizeof(struct xfs_ag_rmap
));
71 do_error(_("couldn't allocate per-AG reverse map roots\n"));
73 for (i
= 0; i
< mp
->m_sb
.sb_agcount
; i
++) {
74 error
= init_slab(&ag_rmaps
[i
].ar_rmaps
,
75 sizeof(struct xfs_rmap_irec
));
78 _("Insufficient memory while allocating reverse mapping slabs."));
79 error
= init_slab(&ag_rmaps
[i
].ar_raw_rmaps
,
80 sizeof(struct xfs_rmap_irec
));
83 _("Insufficient memory while allocating raw metadata reverse mapping slabs."));
84 ag_rmaps
[i
].ar_last_rmap
.rm_owner
= XFS_RMAP_OWN_UNKNOWN
;
85 error
= init_slab(&ag_rmaps
[i
].ar_refcount_items
,
86 sizeof(struct xfs_refcount_irec
));
89 _("Insufficient memory while allocating refcount item slabs."));
94 * Free the per-AG reverse-mapping data.
102 if (!rmap_needs_work(mp
))
105 for (i
= 0; i
< mp
->m_sb
.sb_agcount
; i
++) {
106 free_slab(&ag_rmaps
[i
].ar_rmaps
);
107 free_slab(&ag_rmaps
[i
].ar_raw_rmaps
);
108 free_slab(&ag_rmaps
[i
].ar_refcount_items
);
115 * Decide if two reverse-mapping records can be merged.
119 struct xfs_rmap_irec
*r1
,
120 struct xfs_rmap_irec
*r2
)
122 if (r1
->rm_owner
!= r2
->rm_owner
)
124 if (r1
->rm_startblock
+ r1
->rm_blockcount
!= r2
->rm_startblock
)
126 if ((unsigned long long)r1
->rm_blockcount
+ r2
->rm_blockcount
>
129 if (XFS_RMAP_NON_INODE_OWNER(r2
->rm_owner
))
131 /* must be an inode owner below here */
132 if (r1
->rm_flags
!= r2
->rm_flags
)
134 if (r1
->rm_flags
& XFS_RMAP_BMBT_BLOCK
)
136 return r1
->rm_offset
+ r1
->rm_blockcount
== r2
->rm_offset
;
140 * Add an observation about a block mapping in an inode's data or attribute
141 * fork for later btree reconstruction.
145 struct xfs_mount
*mp
,
148 struct xfs_bmbt_irec
*irec
)
150 struct xfs_rmap_irec rmap
;
153 struct xfs_rmap_irec
*last_rmap
;
156 if (!rmap_needs_work(mp
))
159 agno
= XFS_FSB_TO_AGNO(mp
, irec
->br_startblock
);
160 agbno
= XFS_FSB_TO_AGBNO(mp
, irec
->br_startblock
);
161 ASSERT(agno
!= NULLAGNUMBER
);
162 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
163 ASSERT(agbno
+ irec
->br_blockcount
<= mp
->m_sb
.sb_agblocks
);
164 ASSERT(ino
!= NULLFSINO
);
165 ASSERT(whichfork
== XFS_DATA_FORK
|| whichfork
== XFS_ATTR_FORK
);
168 rmap
.rm_offset
= irec
->br_startoff
;
170 if (whichfork
== XFS_ATTR_FORK
)
171 rmap
.rm_flags
|= XFS_RMAP_ATTR_FORK
;
172 rmap
.rm_startblock
= agbno
;
173 rmap
.rm_blockcount
= irec
->br_blockcount
;
174 if (irec
->br_state
== XFS_EXT_UNWRITTEN
)
175 rmap
.rm_flags
|= XFS_RMAP_UNWRITTEN
;
176 last_rmap
= &ag_rmaps
[agno
].ar_last_rmap
;
177 if (last_rmap
->rm_owner
== XFS_RMAP_OWN_UNKNOWN
)
179 else if (rmaps_are_mergeable(last_rmap
, &rmap
))
180 last_rmap
->rm_blockcount
+= rmap
.rm_blockcount
;
182 error
= slab_add(ag_rmaps
[agno
].ar_rmaps
, last_rmap
);
191 /* Finish collecting inode data/attr fork rmaps. */
193 rmap_finish_collecting_fork_recs(
194 struct xfs_mount
*mp
,
197 if (!rmap_needs_work(mp
) ||
198 ag_rmaps
[agno
].ar_last_rmap
.rm_owner
== XFS_RMAP_OWN_UNKNOWN
)
200 return slab_add(ag_rmaps
[agno
].ar_rmaps
, &ag_rmaps
[agno
].ar_last_rmap
);
203 /* add a raw rmap; these will be merged later */
206 struct xfs_mount
*mp
,
214 struct xfs_rmap_irec rmap
;
217 rmap
.rm_owner
= owner
;
221 rmap
.rm_flags
|= XFS_RMAP_ATTR_FORK
;
223 rmap
.rm_flags
|= XFS_RMAP_BMBT_BLOCK
;
224 rmap
.rm_startblock
= agbno
;
225 rmap
.rm_blockcount
= len
;
226 return slab_add(ag_rmaps
[agno
].ar_raw_rmaps
, &rmap
);
230 * Add a reverse mapping for an inode fork's block mapping btree block.
234 struct xfs_mount
*mp
,
242 if (!rmap_needs_work(mp
))
245 agno
= XFS_FSB_TO_AGNO(mp
, fsbno
);
246 agbno
= XFS_FSB_TO_AGBNO(mp
, fsbno
);
247 ASSERT(agno
!= NULLAGNUMBER
);
248 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
249 ASSERT(agbno
+ 1 <= mp
->m_sb
.sb_agblocks
);
251 return __rmap_add_raw_rec(mp
, agno
, agbno
, 1, ino
,
252 whichfork
== XFS_ATTR_FORK
, true);
256 * Add a reverse mapping for a per-AG fixed metadata extent.
260 struct xfs_mount
*mp
,
266 if (!rmap_needs_work(mp
))
269 ASSERT(agno
!= NULLAGNUMBER
);
270 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
271 ASSERT(agbno
+ len
<= mp
->m_sb
.sb_agblocks
);
273 return __rmap_add_raw_rec(mp
, agno
, agbno
, len
, owner
, false, false);
277 * Merge adjacent raw rmaps and add them to the main rmap list.
281 struct xfs_mount
*mp
,
284 struct xfs_slab_cursor
*cur
= NULL
;
285 struct xfs_rmap_irec
*prev
, *rec
;
289 old_sz
= slab_count(ag_rmaps
[agno
].ar_rmaps
);
290 if (slab_count(ag_rmaps
[agno
].ar_raw_rmaps
) == 0)
292 qsort_slab(ag_rmaps
[agno
].ar_raw_rmaps
, rmap_compare
);
293 error
= init_slab_cursor(ag_rmaps
[agno
].ar_raw_rmaps
, rmap_compare
,
298 prev
= pop_slab_cursor(cur
);
299 rec
= pop_slab_cursor(cur
);
300 while (prev
&& rec
) {
301 if (rmaps_are_mergeable(prev
, rec
)) {
302 prev
->rm_blockcount
+= rec
->rm_blockcount
;
303 rec
= pop_slab_cursor(cur
);
306 error
= slab_add(ag_rmaps
[agno
].ar_rmaps
, prev
);
310 rec
= pop_slab_cursor(cur
);
313 error
= slab_add(ag_rmaps
[agno
].ar_rmaps
, prev
);
317 free_slab(&ag_rmaps
[agno
].ar_raw_rmaps
);
318 error
= init_slab(&ag_rmaps
[agno
].ar_raw_rmaps
,
319 sizeof(struct xfs_rmap_irec
));
322 _("Insufficient memory while allocating raw metadata reverse mapping slabs."));
325 qsort_slab(ag_rmaps
[agno
].ar_rmaps
, rmap_compare
);
327 free_slab_cursor(&cur
);
338 for (n
= 0; n
< sizeof(mask
) * NBBY
&& (mask
& 1); n
++, mask
>>= 1)
354 for (n
= 0; n
< sizeof(mask
) * NBBY
; n
++, mask
>>= 1)
362 * Add an allocation group's fixed metadata to the rmap list. This includes
363 * sb/agi/agf/agfl headers, inode chunks, and the log.
366 rmap_add_fixed_ag_rec(
367 struct xfs_mount
*mp
,
372 ino_tree_node_t
*ino_rec
;
378 if (!rmap_needs_work(mp
))
381 /* sb/agi/agf/agfl headers */
382 error
= rmap_add_ag_rec(mp
, agno
, 0, XFS_BNO_BLOCK(mp
),
388 ino_rec
= findfirst_inode_rec(agno
);
389 for (; ino_rec
!= NULL
; ino_rec
= next_ino_rec(ino_rec
)) {
390 if (xfs_sb_version_hassparseinodes(&mp
->m_sb
)) {
391 startidx
= find_first_zero_bit(ino_rec
->ir_sparse
);
392 nr
= XFS_INODES_PER_CHUNK
- popcnt(ino_rec
->ir_sparse
);
395 nr
= XFS_INODES_PER_CHUNK
;
397 nr
/= mp
->m_sb
.sb_inopblock
;
400 agino
= ino_rec
->ino_startnum
+ startidx
;
401 agbno
= XFS_AGINO_TO_AGBNO(mp
, agino
);
402 if (XFS_AGINO_TO_OFFSET(mp
, agino
) == 0) {
403 error
= rmap_add_ag_rec(mp
, agno
, agbno
, nr
,
404 XFS_RMAP_OWN_INODES
);
411 fsbno
= mp
->m_sb
.sb_logstart
;
412 if (fsbno
&& XFS_FSB_TO_AGNO(mp
, fsbno
) == agno
) {
413 agbno
= XFS_FSB_TO_AGBNO(mp
, mp
->m_sb
.sb_logstart
);
414 error
= rmap_add_ag_rec(mp
, agno
, agbno
, mp
->m_sb
.sb_logblocks
,
424 * Copy the per-AG btree reverse-mapping data into the rmapbt.
426 * At rmapbt reconstruction time, the rmapbt will be populated _only_ with
427 * rmaps for file extents, inode chunks, AG headers, and bmbt blocks. While
428 * building the AG btrees we can record all the blocks allocated for each
429 * btree, but we cannot resolve the conflict between the fact that one has to
430 * finish allocating the space for the rmapbt before building the bnobt and the
431 * fact that allocating blocks for the bnobt requires adding rmapbt entries.
432 * Therefore we record in-core the rmaps for each btree and here use the
433 * libxfs rmap functions to finish building the rmap btree.
435 * During AGF/AGFL reconstruction in phase 5, rmaps for the AG btrees are
436 * recorded in memory. The rmapbt has not been set up yet, so we need to be
437 * able to "expand" the AGFL without updating the rmapbt. After we've written
438 * out the new AGF header the new rmapbt is available, so this function reads
439 * each AGFL to generate rmap entries. These entries are merged with the AG
440 * btree rmap entries, and then we use libxfs' rmap functions to add them to
441 * the rmapbt, after which it is fully regenerated.
444 rmap_store_ag_btree_rec(
445 struct xfs_mount
*mp
,
448 struct xfs_slab_cursor
*rm_cur
;
449 struct xfs_rmap_irec
*rm_rec
= NULL
;
450 struct xfs_buf
*agbp
= NULL
;
451 struct xfs_buf
*agflbp
= NULL
;
452 struct xfs_trans
*tp
;
453 __be32
*agfl_bno
, *b
;
454 struct xfs_ag_rmap
*ag_rmap
= &ag_rmaps
[agno
];
455 struct bitmap
*own_ag_bitmap
= NULL
;
458 if (!xfs_sb_version_hasrmapbt(&mp
->m_sb
))
461 /* Release the ar_rmaps; they were put into the rmapbt during p5. */
462 free_slab(&ag_rmap
->ar_rmaps
);
463 error
= init_slab(&ag_rmap
->ar_rmaps
, sizeof(struct xfs_rmap_irec
));
467 /* Add the AGFL blocks to the rmap list */
468 error
= -libxfs_trans_read_buf(
469 mp
, NULL
, mp
->m_ddev_targp
,
470 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
471 XFS_FSS_TO_BB(mp
, 1), 0, &agflbp
, &xfs_agfl_buf_ops
);
476 * Sometimes, the blocks at the beginning of the AGFL are there
477 * because we overestimated how many blocks we needed to rebuild
478 * the freespace btrees. ar_flcount records the number of
479 * blocks in this situation. Since those blocks already have an
480 * rmap, we only need to add rmap records for AGFL blocks past
481 * that point in the AGFL because those blocks are a result of a
482 * no-rmap no-shrink freelist fixup that we did earlier.
484 * However, some blocks end up on the AGFL because the free space
485 * btrees shed blocks as a result of allocating space to fix the
486 * freelist. We already created in-core rmap records for the free
487 * space btree blocks, so we must be careful not to create those
488 * records again. Create a bitmap of already-recorded OWN_AG rmaps.
490 error
= init_slab_cursor(ag_rmap
->ar_raw_rmaps
, rmap_compare
, &rm_cur
);
493 error
= -bitmap_alloc(&own_ag_bitmap
);
496 while ((rm_rec
= pop_slab_cursor(rm_cur
)) != NULL
) {
497 if (rm_rec
->rm_owner
!= XFS_RMAP_OWN_AG
)
499 error
= -bitmap_set(own_ag_bitmap
, rm_rec
->rm_startblock
,
500 rm_rec
->rm_blockcount
);
503 * If this range is already set, then the incore rmap
504 * records for the AG free space btrees overlap and
505 * we're toast because that is not allowed.
508 error
= EFSCORRUPTED
;
512 free_slab_cursor(&rm_cur
);
514 /* Create rmaps for any AGFL blocks that aren't already rmapped. */
515 agfl_bno
= XFS_BUF_TO_AGFL_BNO(mp
, agflbp
);
516 b
= agfl_bno
+ ag_rmap
->ar_flcount
;
517 while (*b
!= cpu_to_be32(NULLAGBLOCK
) &&
518 b
- agfl_bno
< libxfs_agfl_size(mp
)) {
521 agbno
= be32_to_cpu(*b
);
522 if (!bitmap_test(own_ag_bitmap
, agbno
, 1)) {
523 error
= rmap_add_ag_rec(mp
, agno
, agbno
, 1,
530 libxfs_putbuf(agflbp
);
532 bitmap_free(&own_ag_bitmap
);
534 /* Merge all the raw rmaps into the main list */
535 error
= rmap_fold_raw_recs(mp
, agno
);
539 /* Create cursors to refcount structures */
540 error
= init_slab_cursor(ag_rmap
->ar_rmaps
, rmap_compare
, &rm_cur
);
544 /* Insert rmaps into the btree one at a time */
545 rm_rec
= pop_slab_cursor(rm_cur
);
547 struct xfs_owner_info oinfo
= {};
549 error
= -libxfs_trans_alloc_rollable(mp
, 16, &tp
);
553 error
= -libxfs_alloc_read_agf(mp
, tp
, agno
, 0, &agbp
);
557 ASSERT(XFS_RMAP_NON_INODE_OWNER(rm_rec
->rm_owner
));
558 oinfo
.oi_owner
= rm_rec
->rm_owner
;
559 error
= -libxfs_rmap_alloc(tp
, agbp
, agno
, rm_rec
->rm_startblock
,
560 rm_rec
->rm_blockcount
, &oinfo
);
564 error
= -libxfs_trans_commit(tp
);
568 fix_freelist(mp
, agno
, false);
570 rm_rec
= pop_slab_cursor(rm_cur
);
573 free_slab_cursor(&rm_cur
);
577 libxfs_trans_cancel(tp
);
579 free_slab_cursor(&rm_cur
);
582 libxfs_putbuf(agflbp
);
584 bitmap_free(&own_ag_bitmap
);
593 struct xfs_rmap_irec
*rmap
)
595 printf("%s: %p agno=%u pblk=%llu own=%lld lblk=%llu len=%u flags=0x%x\n",
598 (unsigned long long)rmap
->rm_startblock
,
599 (unsigned long long)rmap
->rm_owner
,
600 (unsigned long long)rmap
->rm_offset
,
601 (unsigned int)rmap
->rm_blockcount
,
602 (unsigned int)rmap
->rm_flags
);
605 # define rmap_dump(m, a, r)
609 * Rebuilding the Reference Count & Reverse Mapping Btrees
611 * The reference count (refcnt) and reverse mapping (rmap) btrees are
612 * rebuilt during phase 5, like all other AG btrees. Therefore, reverse
613 * mappings must be processed into reference counts at the end of phase
614 * 4, and the rmaps must be recorded during phase 4. There is a need to
615 * access the rmaps in physical block order, but no particular need for
616 * random access, so the slab.c code provides a big logical array
617 * (consisting of smaller slabs) and some inorder iterator functions.
619 * Once we've recorded all the reverse mappings, we're ready to
620 * translate the rmaps into refcount entries. Imagine the rmap entries
621 * as rectangles representing extents of physical blocks, and that the
622 * rectangles can be laid down to allow them to overlap each other; then
623 * we know that we must emit a refcnt btree entry wherever the amount of
624 * overlap changes, i.e. the emission stimulus is level-triggered:
627 * -- ----- ---- --- ------
628 * -- ---- ----------- ---- ---------
629 * -------------------------------- -----------
630 * ^ ^ ^^ ^^ ^ ^^ ^^^ ^^^^ ^ ^^ ^ ^ ^
631 * 2 1 23 21 3 43 234 2123 1 01 2 3 0
633 * For our purposes, a rmap is a tuple (startblock, len, fileoff, owner).
635 * Note that in the actual refcnt btree we don't store the refcount < 2
636 * cases because the bnobt tells us which blocks are free; single-use
637 * blocks aren't recorded in the bnobt or the refcntbt. If the rmapbt
638 * supports storing multiple entries covering a given block we could
639 * theoretically dispense with the refcntbt and simply count rmaps, but
640 * that's inefficient in the (hot) write path, so we'll take the cost of
641 * the extra tree to save time. Also there's no guarantee that rmap
644 * Given an array of rmaps sorted by physical block number, a starting
645 * physical block (sp), a bag to hold rmaps that cover sp, and the next
646 * physical block where the level changes (np), we can reconstruct the
647 * refcount btree as follows:
649 * While there are still unprocessed rmaps in the array,
650 * - Set sp to the physical block (pblk) of the next unprocessed rmap.
651 * - Add to the bag all rmaps in the array where startblock == sp.
652 * - Set np to the physical block where the bag size will change. This
653 * is the minimum of (the pblk of the next unprocessed rmap) and
654 * (startblock + len of each rmap in the bag).
655 * - Record the bag size as old_bag_size.
657 * - While the bag isn't empty,
658 * - Remove from the bag all rmaps where startblock + len == np.
659 * - Add to the bag all rmaps in the array where startblock == np.
660 * - If the bag size isn't old_bag_size, store the refcount entry
661 * (sp, np - sp, bag_size) in the refcnt btree.
662 * - If the bag is empty, break out of the inner loop.
663 * - Set old_bag_size to the bag size
665 * - Set np to the physical block where the bag size will change.
666 * This is the minimum of (the pblk of the next unprocessed rmap)
667 * and (startblock + len of each rmap in the bag).
669 * An implementation detail is that because this processing happens
670 * during phase 4, the refcount entries are stored in an array so that
671 * phase 5 can load them into the refcount btree. The rmaps can be
672 * loaded directly into the rmap btree during phase 5 as well.
676 * Mark all inodes in the reverse-mapping observation stack as requiring the
677 * reflink inode flag, if the stack depth is greater than 1.
681 struct xfs_mount
*mp
,
682 struct xfs_bag
*rmaps
)
684 xfs_agnumber_t iagno
;
685 struct xfs_rmap_irec
*rmap
;
686 struct ino_tree_node
*irec
;
691 if (bag_count(rmaps
) < 2)
694 /* Reflink flag accounting */
695 foreach_bag_ptr(rmaps
, idx
, rmap
) {
696 ASSERT(!XFS_RMAP_NON_INODE_OWNER(rmap
->rm_owner
));
697 iagno
= XFS_INO_TO_AGNO(mp
, rmap
->rm_owner
);
698 ino
= XFS_INO_TO_AGINO(mp
, rmap
->rm_owner
);
699 pthread_mutex_lock(&ag_locks
[iagno
].lock
);
700 irec
= find_inode_rec(mp
, iagno
, ino
);
701 off
= get_inode_offset(mp
, rmap
->rm_owner
, irec
);
702 /* lock here because we might go outside this ag */
703 set_inode_is_rl(irec
, off
);
704 pthread_mutex_unlock(&ag_locks
[iagno
].lock
);
709 * Emit a refcount object for refcntbt reconstruction during phase 5.
711 #define REFCOUNT_CLAMP(nr) ((nr) > MAXREFCOUNT ? MAXREFCOUNT : (nr))
714 struct xfs_mount
*mp
,
720 struct xfs_refcount_irec rlrec
;
722 struct xfs_slab
*rlslab
;
724 rlslab
= ag_rmaps
[agno
].ar_refcount_items
;
725 ASSERT(nr_rmaps
> 0);
727 dbg_printf("REFL: agno=%u pblk=%u, len=%u -> refcount=%zu\n",
728 agno
, agbno
, len
, nr_rmaps
);
729 rlrec
.rc_startblock
= agbno
;
730 rlrec
.rc_blockcount
= len
;
731 rlrec
.rc_refcount
= REFCOUNT_CLAMP(nr_rmaps
);
732 error
= slab_add(rlslab
, &rlrec
);
735 _("Insufficient memory while recreating refcount tree."));
737 #undef REFCOUNT_CLAMP
740 * Transform a pile of physical block mapping observations into refcount data
741 * for eventual rebuilding of the btrees.
743 #define RMAP_END(r) ((r)->rm_startblock + (r)->rm_blockcount)
746 struct xfs_mount
*mp
,
749 struct xfs_bag
*stack_top
= NULL
;
750 struct xfs_slab
*rmaps
;
751 struct xfs_slab_cursor
*rmaps_cur
;
752 struct xfs_rmap_irec
*array_cur
;
753 struct xfs_rmap_irec
*rmap
;
754 xfs_agblock_t sbno
; /* first bno of this rmap set */
755 xfs_agblock_t cbno
; /* first bno of this refcount set */
756 xfs_agblock_t nbno
; /* next bno where rmap set changes */
761 if (!xfs_sb_version_hasreflink(&mp
->m_sb
))
764 rmaps
= ag_rmaps
[agno
].ar_rmaps
;
766 error
= init_slab_cursor(rmaps
, rmap_compare
, &rmaps_cur
);
770 error
= init_bag(&stack_top
);
774 /* While there are rmaps to be processed... */
776 while (n
< slab_count(rmaps
)) {
777 array_cur
= peek_slab_cursor(rmaps_cur
);
778 sbno
= cbno
= array_cur
->rm_startblock
;
779 /* Push all rmaps with pblk == sbno onto the stack */
781 array_cur
&& array_cur
->rm_startblock
== sbno
;
782 array_cur
= peek_slab_cursor(rmaps_cur
)) {
783 advance_slab_cursor(rmaps_cur
); n
++;
784 rmap_dump("push0", agno
, array_cur
);
785 error
= bag_add(stack_top
, array_cur
);
789 mark_inode_rl(mp
, stack_top
);
791 /* Set nbno to the bno of the next refcount change */
792 if (n
< slab_count(rmaps
) && array_cur
)
793 nbno
= array_cur
->rm_startblock
;
796 foreach_bag_ptr(stack_top
, idx
, rmap
) {
797 nbno
= min(nbno
, RMAP_END(rmap
));
800 /* Emit reverse mappings, if needed */
802 old_stack_nr
= bag_count(stack_top
);
804 /* While stack isn't empty... */
805 while (bag_count(stack_top
)) {
806 /* Pop all rmaps that end at nbno */
807 foreach_bag_ptr_reverse(stack_top
, idx
, rmap
) {
808 if (RMAP_END(rmap
) != nbno
)
810 rmap_dump("pop", agno
, rmap
);
811 error
= bag_remove(stack_top
, idx
);
816 /* Push array items that start at nbno */
818 array_cur
&& array_cur
->rm_startblock
== nbno
;
819 array_cur
= peek_slab_cursor(rmaps_cur
)) {
820 advance_slab_cursor(rmaps_cur
); n
++;
821 rmap_dump("push1", agno
, array_cur
);
822 error
= bag_add(stack_top
, array_cur
);
826 mark_inode_rl(mp
, stack_top
);
828 /* Emit refcount if necessary */
830 if (bag_count(stack_top
) != old_stack_nr
) {
831 if (old_stack_nr
> 1) {
832 refcount_emit(mp
, agno
, cbno
,
839 /* Stack empty, go find the next rmap */
840 if (bag_count(stack_top
) == 0)
842 old_stack_nr
= bag_count(stack_top
);
845 /* Set nbno to the bno of the next refcount change */
846 if (n
< slab_count(rmaps
))
847 nbno
= array_cur
->rm_startblock
;
850 foreach_bag_ptr(stack_top
, idx
, rmap
) {
851 nbno
= min(nbno
, RMAP_END(rmap
));
854 /* Emit reverse mappings, if needed */
859 free_bag(&stack_top
);
860 free_slab_cursor(&rmaps_cur
);
867 * Return the number of rmap objects for an AG.
871 struct xfs_mount
*mp
,
874 return slab_count(ag_rmaps
[agno
].ar_rmaps
);
878 * Return a slab cursor that will return rmap objects in order.
883 struct xfs_slab_cursor
**cur
)
885 return init_slab_cursor(ag_rmaps
[agno
].ar_rmaps
, rmap_compare
, cur
);
889 * Disable the refcount btree check.
892 rmap_avoid_check(void)
894 rmapbt_suspect
= true;
897 /* Look for an rmap in the rmapbt that matches a given rmap. */
900 struct xfs_btree_cur
*bt_cur
,
901 struct xfs_rmap_irec
*rm_rec
,
902 struct xfs_rmap_irec
*tmp
,
907 /* Use the regular btree retrieval routine. */
908 error
= -libxfs_rmap_lookup_le(bt_cur
, rm_rec
->rm_startblock
,
909 rm_rec
->rm_blockcount
,
910 rm_rec
->rm_owner
, rm_rec
->rm_offset
,
911 rm_rec
->rm_flags
, have
);
916 return -libxfs_rmap_get_rec(bt_cur
, tmp
, have
);
919 /* Look for an rmap in the rmapbt that matches a given rmap. */
921 rmap_lookup_overlapped(
922 struct xfs_btree_cur
*bt_cur
,
923 struct xfs_rmap_irec
*rm_rec
,
924 struct xfs_rmap_irec
*tmp
,
927 /* Have to use our fancy version for overlapped */
928 return -libxfs_rmap_lookup_le_range(bt_cur
, rm_rec
->rm_startblock
,
929 rm_rec
->rm_owner
, rm_rec
->rm_offset
,
930 rm_rec
->rm_flags
, tmp
, have
);
933 /* Does the btree rmap cover the observed rmap? */
934 #define NEXTP(x) ((x)->rm_startblock + (x)->rm_blockcount)
935 #define NEXTL(x) ((x)->rm_offset + (x)->rm_blockcount)
938 struct xfs_rmap_irec
*observed
,
939 struct xfs_rmap_irec
*btree
)
941 /* Can't have mismatches in the flags or the owner. */
942 if (btree
->rm_flags
!= observed
->rm_flags
||
943 btree
->rm_owner
!= observed
->rm_owner
)
947 * Btree record can't physically start after the observed
948 * record, nor can it end before the observed record.
950 if (btree
->rm_startblock
> observed
->rm_startblock
||
951 NEXTP(btree
) < NEXTP(observed
))
954 /* If this is metadata or bmbt, we're done. */
955 if (XFS_RMAP_NON_INODE_OWNER(observed
->rm_owner
) ||
956 (observed
->rm_flags
& XFS_RMAP_BMBT_BLOCK
))
959 * Btree record can't logically start after the observed
960 * record, nor can it end before the observed record.
962 if (btree
->rm_offset
> observed
->rm_offset
||
963 NEXTL(btree
) < NEXTL(observed
))
972 * Compare the observed reverse mappings against what's in the ag btree.
976 struct xfs_mount
*mp
,
979 struct xfs_slab_cursor
*rm_cur
;
980 struct xfs_btree_cur
*bt_cur
= NULL
;
983 struct xfs_buf
*agbp
= NULL
;
984 struct xfs_rmap_irec
*rm_rec
;
985 struct xfs_rmap_irec tmp
;
986 struct xfs_perag
*pag
; /* per allocation group data */
988 if (!xfs_sb_version_hasrmapbt(&mp
->m_sb
))
990 if (rmapbt_suspect
) {
991 if (no_modify
&& agno
== 0)
992 do_warn(_("would rebuild corrupt rmap btrees.\n"));
996 /* Create cursors to refcount structures */
997 error
= rmap_init_cursor(agno
, &rm_cur
);
1001 error
= -libxfs_alloc_read_agf(mp
, NULL
, agno
, 0, &agbp
);
1005 /* Leave the per-ag data "uninitialized" since we rewrite it later */
1006 pag
= libxfs_perag_get(mp
, agno
);
1008 libxfs_perag_put(pag
);
1010 bt_cur
= libxfs_rmapbt_init_cursor(mp
, NULL
, agbp
, agno
);
1016 rm_rec
= pop_slab_cursor(rm_cur
);
1018 error
= rmap_lookup(bt_cur
, rm_rec
, &tmp
, &have
);
1022 * Using the range query is expensive, so only do it if
1023 * the regular lookup doesn't find anything or if it doesn't
1024 * match the observed rmap.
1026 if (xfs_sb_version_hasreflink(&bt_cur
->bc_mp
->m_sb
) &&
1027 (!have
|| !rmap_is_good(rm_rec
, &tmp
))) {
1028 error
= rmap_lookup_overlapped(bt_cur
, rm_rec
,
1035 _("Missing reverse-mapping record for (%u/%u) %slen %u owner %"PRId64
" \
1036 %s%soff %"PRIu64
"\n"),
1037 agno
, rm_rec
->rm_startblock
,
1038 (rm_rec
->rm_flags
& XFS_RMAP_UNWRITTEN
) ?
1039 _("unwritten ") : "",
1040 rm_rec
->rm_blockcount
,
1042 (rm_rec
->rm_flags
& XFS_RMAP_ATTR_FORK
) ?
1044 (rm_rec
->rm_flags
& XFS_RMAP_BMBT_BLOCK
) ?
1050 /* Compare each refcount observation against the btree's */
1051 if (!rmap_is_good(rm_rec
, &tmp
)) {
1053 _("Incorrect reverse-mapping: saw (%u/%u) %slen %u owner %"PRId64
" %s%soff \
1054 %"PRIu64
"; should be (%u/%u) %slen %u owner %"PRId64
" %s%soff %"PRIu64
"\n"),
1055 agno
, tmp
.rm_startblock
,
1056 (tmp
.rm_flags
& XFS_RMAP_UNWRITTEN
) ?
1057 _("unwritten ") : "",
1060 (tmp
.rm_flags
& XFS_RMAP_ATTR_FORK
) ?
1062 (tmp
.rm_flags
& XFS_RMAP_BMBT_BLOCK
) ?
1065 agno
, rm_rec
->rm_startblock
,
1066 (rm_rec
->rm_flags
& XFS_RMAP_UNWRITTEN
) ?
1067 _("unwritten ") : "",
1068 rm_rec
->rm_blockcount
,
1070 (rm_rec
->rm_flags
& XFS_RMAP_ATTR_FORK
) ?
1072 (rm_rec
->rm_flags
& XFS_RMAP_BMBT_BLOCK
) ?
1078 rm_rec
= pop_slab_cursor(rm_cur
);
1083 libxfs_btree_del_cursor(bt_cur
, XFS_BTREE_NOERROR
);
1085 libxfs_putbuf(agbp
);
1086 free_slab_cursor(&rm_cur
);
1091 * Compare the key fields of two rmap records -- positive if key1 > key2,
1092 * negative if key1 < key2, and zero if equal.
1096 struct xfs_rmap_irec
*kp1
,
1097 struct xfs_rmap_irec
*kp2
)
1102 struct xfs_rmap_irec tmp
;
1105 tmp
.rm_flags
&= ~XFS_RMAP_REC_FLAGS
;
1106 oa
= libxfs_rmap_irec_offset_pack(&tmp
);
1108 tmp
.rm_flags
&= ~XFS_RMAP_REC_FLAGS
;
1109 ob
= libxfs_rmap_irec_offset_pack(&tmp
);
1111 d
= (int64_t)kp1
->rm_startblock
- kp2
->rm_startblock
;
1115 if (kp1
->rm_owner
> kp2
->rm_owner
)
1117 else if (kp2
->rm_owner
> kp1
->rm_owner
)
1127 /* Compute the high key of an rmap record. */
1129 rmap_high_key_from_rec(
1130 struct xfs_rmap_irec
*rec
,
1131 struct xfs_rmap_irec
*key
)
1135 adj
= rec
->rm_blockcount
- 1;
1137 key
->rm_startblock
= rec
->rm_startblock
+ adj
;
1138 key
->rm_owner
= rec
->rm_owner
;
1139 key
->rm_offset
= rec
->rm_offset
;
1140 key
->rm_flags
= rec
->rm_flags
& XFS_RMAP_KEY_FLAGS
;
1141 if (XFS_RMAP_NON_INODE_OWNER(rec
->rm_owner
) ||
1142 (rec
->rm_flags
& XFS_RMAP_BMBT_BLOCK
))
1144 key
->rm_offset
+= adj
;
1148 * Record that an inode had the reflink flag set when repair started. The
1149 * inode reflink flag will be adjusted as necessary.
1152 record_inode_reflink_flag(
1153 struct xfs_mount
*mp
,
1154 struct xfs_dinode
*dino
,
1155 xfs_agnumber_t agno
,
1159 struct ino_tree_node
*irec
;
1162 ASSERT(XFS_AGINO_TO_INO(mp
, agno
, ino
) == be64_to_cpu(dino
->di_ino
));
1163 if (!(be64_to_cpu(dino
->di_flags2
) & XFS_DIFLAG2_REFLINK
))
1165 irec
= find_inode_rec(mp
, agno
, ino
);
1166 off
= get_inode_offset(mp
, lino
, irec
);
1167 ASSERT(!inode_was_rl(irec
, off
));
1168 set_inode_was_rl(irec
, off
);
1169 dbg_printf("set was_rl lino=%llu was=0x%llx\n",
1170 (unsigned long long)lino
, (unsigned long long)irec
->ino_was_rl
);
1174 * Inform the user that we're clearing the reflink flag on an inode that
1175 * doesn't actually share any blocks. This is an optimization (the kernel
1176 * skips refcount checks for non-reflink files) and not a corruption repair,
1177 * so we don't need to log every time we clear a flag unless verbose mode is
1181 warn_clearing_reflink(
1184 static bool warned
= false;
1185 static pthread_mutex_t lock
= PTHREAD_MUTEX_INITIALIZER
;
1188 do_warn(_("clearing reflink flag on inode %"PRIu64
"\n"), ino
);
1195 pthread_mutex_lock(&lock
);
1197 do_warn(_("clearing reflink flag on inodes when possible\n"));
1200 pthread_mutex_unlock(&lock
);
1204 * Fix an inode's reflink flag.
1207 fix_inode_reflink_flag(
1208 struct xfs_mount
*mp
,
1209 xfs_agnumber_t agno
,
1213 struct xfs_dinode
*dino
;
1214 struct xfs_buf
*buf
;
1218 _("setting reflink flag on inode %"PRIu64
"\n"),
1219 XFS_AGINO_TO_INO(mp
, agno
, agino
));
1220 else if (!no_modify
) /* && !set */
1221 warn_clearing_reflink(XFS_AGINO_TO_INO(mp
, agno
, agino
));
1225 buf
= get_agino_buf(mp
, agno
, agino
, &dino
);
1228 ASSERT(XFS_AGINO_TO_INO(mp
, agno
, agino
) == be64_to_cpu(dino
->di_ino
));
1230 dino
->di_flags2
|= cpu_to_be64(XFS_DIFLAG2_REFLINK
);
1232 dino
->di_flags2
&= cpu_to_be64(~XFS_DIFLAG2_REFLINK
);
1233 libxfs_dinode_calc_crc(mp
, dino
);
1234 libxfs_writebuf(buf
, 0);
1240 * Fix discrepancies between the state of the inode reflink flag and our
1241 * observations as to whether or not the inode really needs it.
1244 fix_inode_reflink_flags(
1245 struct xfs_mount
*mp
,
1246 xfs_agnumber_t agno
)
1248 struct ino_tree_node
*irec
;
1258 * Update the reflink flag for any inode where there's a discrepancy
1259 * between the inode flag and whether or not we found any reflinked
1262 for (irec
= findfirst_inode_rec(agno
);
1264 irec
= next_ino_rec(irec
)) {
1265 ASSERT((irec
->ino_was_rl
& irec
->ir_free
) == 0);
1266 ASSERT((irec
->ino_is_rl
& irec
->ir_free
) == 0);
1267 was
= irec
->ino_was_rl
;
1268 is
= irec
->ino_is_rl
;
1272 dbg_printf("mismatch ino=%llu was=0x%lx is=0x%lx dif=0x%lx\n",
1273 (unsigned long long)XFS_AGINO_TO_INO(mp
, agno
,
1274 irec
->ino_startnum
),
1277 for (bit
= 0, mask
= 1; bit
< 64; bit
++, mask
<<= 1) {
1278 agino
= bit
+ irec
->ino_startnum
;
1281 else if (was
& mask
)
1282 error
= fix_inode_reflink_flag(mp
, agno
, agino
,
1285 error
= fix_inode_reflink_flag(mp
, agno
, agino
,
1291 _("Unable to fix reflink flag on inode %"PRIu64
".\n"),
1292 XFS_AGINO_TO_INO(mp
, agno
, agino
));
1300 * Return the number of refcount objects for an AG.
1303 refcount_record_count(
1304 struct xfs_mount
*mp
,
1305 xfs_agnumber_t agno
)
1307 return slab_count(ag_rmaps
[agno
].ar_refcount_items
);
1311 * Return a slab cursor that will return refcount objects in order.
1314 init_refcount_cursor(
1315 xfs_agnumber_t agno
,
1316 struct xfs_slab_cursor
**cur
)
1318 return init_slab_cursor(ag_rmaps
[agno
].ar_refcount_items
, NULL
, cur
);
1322 * Disable the refcount btree check.
1325 refcount_avoid_check(void)
1327 refcbt_suspect
= true;
1331 * Compare the observed reference counts against what's in the ag btree.
1335 struct xfs_mount
*mp
,
1336 xfs_agnumber_t agno
)
1338 struct xfs_slab_cursor
*rl_cur
;
1339 struct xfs_btree_cur
*bt_cur
= NULL
;
1343 struct xfs_buf
*agbp
= NULL
;
1344 struct xfs_refcount_irec
*rl_rec
;
1345 struct xfs_refcount_irec tmp
;
1346 struct xfs_perag
*pag
; /* per allocation group data */
1348 if (!xfs_sb_version_hasreflink(&mp
->m_sb
))
1350 if (refcbt_suspect
) {
1351 if (no_modify
&& agno
== 0)
1352 do_warn(_("would rebuild corrupt refcount btrees.\n"));
1356 /* Create cursors to refcount structures */
1357 error
= init_refcount_cursor(agno
, &rl_cur
);
1361 error
= -libxfs_alloc_read_agf(mp
, NULL
, agno
, 0, &agbp
);
1365 /* Leave the per-ag data "uninitialized" since we rewrite it later */
1366 pag
= libxfs_perag_get(mp
, agno
);
1368 libxfs_perag_put(pag
);
1370 bt_cur
= libxfs_refcountbt_init_cursor(mp
, NULL
, agbp
, agno
);
1376 rl_rec
= pop_slab_cursor(rl_cur
);
1378 /* Look for a refcount record in the btree */
1379 error
= -libxfs_refcount_lookup_le(bt_cur
,
1380 rl_rec
->rc_startblock
, &have
);
1385 _("Missing reference count record for (%u/%u) len %u count %u\n"),
1386 agno
, rl_rec
->rc_startblock
,
1387 rl_rec
->rc_blockcount
, rl_rec
->rc_refcount
);
1391 error
= -libxfs_refcount_get_rec(bt_cur
, &tmp
, &i
);
1396 _("Missing reference count record for (%u/%u) len %u count %u\n"),
1397 agno
, rl_rec
->rc_startblock
,
1398 rl_rec
->rc_blockcount
, rl_rec
->rc_refcount
);
1402 /* Compare each refcount observation against the btree's */
1403 if (tmp
.rc_startblock
!= rl_rec
->rc_startblock
||
1404 tmp
.rc_blockcount
< rl_rec
->rc_blockcount
||
1405 tmp
.rc_refcount
< rl_rec
->rc_refcount
)
1407 _("Incorrect reference count: saw (%u/%u) len %u nlinks %u; should be (%u/%u) len %u nlinks %u\n"),
1408 agno
, tmp
.rc_startblock
, tmp
.rc_blockcount
,
1409 tmp
.rc_refcount
, agno
, rl_rec
->rc_startblock
,
1410 rl_rec
->rc_blockcount
, rl_rec
->rc_refcount
);
1412 rl_rec
= pop_slab_cursor(rl_cur
);
1417 libxfs_btree_del_cursor(bt_cur
, error
? XFS_BTREE_ERROR
:
1420 libxfs_putbuf(agbp
);
1421 free_slab_cursor(&rl_cur
);
1426 * Regenerate the AGFL so that we don't run out of it while rebuilding the
1427 * rmap btree. If skip_rmapbt is true, don't update the rmapbt (most probably
1428 * because we're updating the rmapbt).
1432 struct xfs_mount
*mp
,
1433 xfs_agnumber_t agno
,
1436 xfs_alloc_arg_t args
;
1441 memset(&args
, 0, sizeof(args
));
1445 args
.pag
= libxfs_perag_get(mp
, agno
);
1446 error
= -libxfs_trans_alloc_rollable(mp
, 0, &tp
);
1448 do_error(_("failed to fix AGFL on AG %d, error %d\n"),
1453 * Prior to rmapbt, all we had to do to fix the freelist is "expand"
1454 * the fresh AGFL header from empty to full. That hasn't changed. For
1455 * rmapbt, however, things change a bit.
1457 * When we're stuffing the rmapbt with the AG btree rmaps the tree can
1458 * expand, so we need to keep the AGFL well-stocked for the expansion.
1459 * However, this expansion can cause the bnobt/cntbt to shrink, which
1460 * can make the AGFL eligible for shrinking. Shrinking involves
1461 * freeing rmapbt entries, but since we haven't finished loading the
1462 * rmapbt with the btree rmaps it's possible for the remove operation
1463 * to fail. The AGFL block is large enough at this point to absorb any
1464 * blocks freed from the bnobt/cntbt, so we can disable shrinking.
1466 * During the initial AGFL regeneration during AGF generation in phase5
1467 * we must also disable rmapbt modifications because the AGF that
1468 * libxfs reads does not yet point to the new rmapbt. These initial
1469 * AGFL entries are added just prior to adding the AG btree block rmaps
1470 * to the rmapbt. It's ok to pass NOSHRINK here too, since the AGFL is
1471 * empty and cannot shrink.
1473 flags
= XFS_ALLOC_FLAG_NOSHRINK
;
1475 flags
|= XFS_ALLOC_FLAG_NORMAP
;
1476 error
= -libxfs_alloc_fix_freelist(&args
, flags
);
1477 libxfs_perag_put(args
.pag
);
1479 do_error(_("failed to fix AGFL on AG %d, error %d\n"),
1482 error
= -libxfs_trans_commit(tp
);
1484 do_error(_("%s: commit failed, error %d\n"), __func__
, error
);
1488 * Remember how many AGFL entries came from excess AG btree allocations and
1489 * therefore already have rmap entries.
1492 rmap_store_agflcount(
1493 struct xfs_mount
*mp
,
1494 xfs_agnumber_t agno
,
1497 if (!rmap_needs_work(mp
))
1500 ag_rmaps
[agno
].ar_flcount
= count
;