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
25 #include "err_protos.h"
33 * we maintain the current slice (path from root to leaf)
34 * of the btree incore. when we need a new block, we ask
35 * the block allocator for the address of a block on that
36 * level, map the block in, and set up the appropriate
37 * pointers (child, silbing, etc.) and keys that should
38 * point to the new block.
40 typedef struct bt_stat_level
{
42 * set in setup_cursor routine and maintained in the tree-building
45 xfs_buf_t
*buf_p
; /* 2 buffer pointers to ... */
46 xfs_buf_t
*prev_buf_p
;
47 xfs_agblock_t agbno
; /* current block being filled */
48 xfs_agblock_t prev_agbno
; /* previous block */
50 * set in calculate/init cursor routines for each btree level
52 int num_recs_tot
; /* # tree recs in level */
53 int num_blocks
; /* # tree blocks in level */
54 int num_recs_pb
; /* num_recs_tot / num_blocks */
55 int modulo
; /* num_recs_tot % num_blocks */
58 typedef struct bt_status
{
59 int init
; /* cursor set up once? */
60 int num_levels
; /* # of levels in btree */
61 xfs_extlen_t num_tot_blocks
; /* # blocks alloc'ed for tree */
62 xfs_extlen_t num_free_blocks
;/* # blocks currently unused */
64 xfs_agblock_t root
; /* root block */
66 * list of blocks to be used to set up this tree
67 * and pointer to the first unused block on the list
69 xfs_agblock_t
*btree_blocks
; /* block list */
70 xfs_agblock_t
*free_btree_blocks
; /* first unused block */
72 * per-level status info
74 bt_stat_level_t level
[XFS_BTREE_MAXLEVELS
];
77 static __uint64_t
*sb_icount_ag
; /* allocated inodes per ag */
78 static __uint64_t
*sb_ifree_ag
; /* free inodes per ag */
79 static __uint64_t
*sb_fdblocks_ag
; /* free data blocks per ag */
82 mk_incore_fstree(xfs_mount_t
*mp
, xfs_agnumber_t agno
)
86 xfs_agblock_t extent_start
;
87 xfs_extlen_t extent_len
;
91 #ifdef XR_BLD_FREE_TRACE
93 int state
= XR_E_BAD_STATE
;
97 * scan the bitmap for the ag looking for continuous
98 * extents of free blocks. At this point, we know
99 * that blocks in the bitmap are either set to an
100 * "in use" state or set to unknown (0) since the
101 * bmaps were zero'ed in phase 4 and only blocks
102 * being used by inodes, inode bmaps, ag headers,
103 * and the files themselves were put into the bitmap.
106 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
108 extent_start
= extent_len
= 0;
110 num_extents
= free_blocks
= 0;
112 if (agno
< mp
->m_sb
.sb_agcount
- 1)
113 ag_end
= mp
->m_sb
.sb_agblocks
;
115 ag_end
= mp
->m_sb
.sb_dblocks
-
116 mp
->m_sb
.sb_agblocks
* (mp
->m_sb
.sb_agcount
- 1);
119 * ok, now find the number of extents, keep track of the
122 for (agbno
= 0; agbno
< ag_end
; agbno
++) {
125 state
= get_agbno_state(mp
, agno
, agbno
);
126 if (state
!= old_state
) {
127 fprintf(stderr
, "agbno %u - new state is %d\n",
131 /* Process in chunks of 16 (XR_BB_UNIT/XR_BB) */
132 if ((in_extent
== 0) && ((agbno
& XR_BB_MASK
) == 0)) {
133 /* testing >= XR_E_INUSE */
134 switch (ba_bmap
[agno
][agbno
>>XR_BB
]) {
136 case XR_E_INUSE_FS_LL
:
139 agbno
+= (XR_BB_UNIT
/XR_BB
) - 1;
144 if (get_agbno_state(mp
, agno
, agbno
) < XR_E_INUSE
) {
146 if (in_extent
== 0) {
148 * found the start of a free extent
152 extent_start
= agbno
;
160 * free extent ends here, add extent to the
161 * 2 incore extent (avl-to-be-B+) trees
164 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
165 fprintf(stderr
, "adding extent %u [%u %u]\n",
166 agno
, extent_start
, extent_len
);
168 add_bno_extent(agno
, extent_start
, extent_len
);
169 add_bcnt_extent(agno
, extent_start
, extent_len
);
175 * free extent ends here
178 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
179 fprintf(stderr
, "adding extent %u [%u %u]\n",
180 agno
, extent_start
, extent_len
);
182 add_bno_extent(agno
, extent_start
, extent_len
);
183 add_bcnt_extent(agno
, extent_start
, extent_len
);
191 get_next_blockaddr(xfs_agnumber_t agno
, int level
, bt_status_t
*curs
)
193 ASSERT(curs
->free_btree_blocks
< curs
->btree_blocks
+
194 curs
->num_tot_blocks
);
195 ASSERT(curs
->num_free_blocks
> 0);
197 curs
->num_free_blocks
--;
198 return(*curs
->free_btree_blocks
++);
202 * set up the dynamically allocated block allocation data in the btree
203 * cursor that depends on the info in the static portion of the cursor.
204 * allocates space from the incore bno/bcnt extent trees and sets up
205 * the first path up the left side of the tree. Also sets up the
206 * cursor pointer to the btree root. called by init_freespace_cursor()
207 * and init_ino_cursor()
211 setup_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*curs
)
215 xfs_extlen_t big_extent_len
;
216 xfs_agblock_t big_extent_start
;
217 extent_tree_node_t
*ext_ptr
;
218 extent_tree_node_t
*bno_ext_ptr
;
219 xfs_extlen_t blocks_allocated
;
220 xfs_agblock_t
*agb_ptr
;
223 * get the number of blocks we need to allocate, then
224 * set up block number array, set the free block pointer
225 * to the first block in the array, and null the array
227 big_extent_len
= curs
->num_tot_blocks
;
228 blocks_allocated
= 0;
230 ASSERT(big_extent_len
> 0);
232 if ((curs
->btree_blocks
= malloc(sizeof(xfs_agblock_t
*)
233 * big_extent_len
)) == NULL
)
234 do_error(_("could not set up btree block array\n"));
236 agb_ptr
= curs
->free_btree_blocks
= curs
->btree_blocks
;
238 for (j
= 0; j
< curs
->num_free_blocks
; j
++, agb_ptr
++)
239 *agb_ptr
= NULLAGBLOCK
;
242 * grab the smallest extent and use it up, then get the
243 * next smallest. This mimics the init_*_cursor code.
245 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
246 do_error(_("error - not enough free space in filesystem\n"));
248 agb_ptr
= curs
->btree_blocks
;
249 j
= curs
->level
[0].num_blocks
;
252 * set up the free block array
254 while (blocks_allocated
< big_extent_len
) {
256 * use up the extent we've got
258 for (u
= 0; u
< ext_ptr
->ex_blockcount
&&
259 blocks_allocated
< big_extent_len
; u
++) {
260 ASSERT(agb_ptr
< curs
->btree_blocks
261 + curs
->num_tot_blocks
);
262 *agb_ptr
++ = ext_ptr
->ex_startblock
+ u
;
267 * if we only used part of this last extent, then we
268 * need only to reset the extent in the extent
269 * trees and we're done
271 if (u
< ext_ptr
->ex_blockcount
) {
272 big_extent_start
= ext_ptr
->ex_startblock
+ u
;
273 big_extent_len
= ext_ptr
->ex_blockcount
- u
;
275 ASSERT(big_extent_len
> 0);
277 bno_ext_ptr
= find_bno_extent(agno
,
278 ext_ptr
->ex_startblock
);
279 ASSERT(bno_ext_ptr
!= NULL
);
280 get_bno_extent(agno
, bno_ext_ptr
);
281 release_extent_tree_node(bno_ext_ptr
);
283 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
284 ext_ptr
->ex_blockcount
);
285 release_extent_tree_node(ext_ptr
);
286 #ifdef XR_BLD_FREE_TRACE
287 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
288 agno
, ext_ptr
->ex_startblock
,
289 ext_ptr
->ex_blockcount
);
290 fprintf(stderr
, "blocks_allocated = %d\n",
294 add_bno_extent(agno
, big_extent_start
, big_extent_len
);
295 add_bcnt_extent(agno
, big_extent_start
, big_extent_len
);
300 * delete the used-up extent from both extent trees and
301 * find next biggest extent
303 #ifdef XR_BLD_FREE_TRACE
304 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
305 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
307 bno_ext_ptr
= find_bno_extent(agno
, ext_ptr
->ex_startblock
);
308 ASSERT(bno_ext_ptr
!= NULL
);
309 get_bno_extent(agno
, bno_ext_ptr
);
310 release_extent_tree_node(bno_ext_ptr
);
312 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
313 ext_ptr
->ex_blockcount
);
314 ASSERT(ext_ptr
!= NULL
);
315 release_extent_tree_node(ext_ptr
);
317 ext_ptr
= findfirst_bcnt_extent(agno
);
319 #ifdef XR_BLD_FREE_TRACE
320 fprintf(stderr
, "blocks_allocated = %d\n",
326 write_cursor(bt_status_t
*curs
)
330 for (i
= 0; i
< curs
->num_levels
; i
++) {
331 #if defined(XR_BLD_FREE_TRACE) || defined(XR_BLD_INO_TRACE)
332 fprintf(stderr
, "writing bt block %u\n", curs
->level
[i
].agbno
);
334 if (curs
->level
[i
].prev_buf_p
!= NULL
) {
335 ASSERT(curs
->level
[i
].prev_agbno
!= NULLAGBLOCK
);
336 #if defined(XR_BLD_FREE_TRACE) || defined(XR_BLD_INO_TRACE)
337 fprintf(stderr
, "writing bt prev block %u\n",
338 curs
->level
[i
].prev_agbno
);
340 libxfs_writebuf(curs
->level
[i
].prev_buf_p
, 0);
342 libxfs_writebuf(curs
->level
[i
].buf_p
, 0);
347 finish_cursor(bt_status_t
*curs
)
349 ASSERT(curs
->num_free_blocks
== 0);
350 free(curs
->btree_blocks
);
354 * XXX(hch): any reason we don't just look at mp->m_alloc_mxr?
356 #define XR_ALLOC_BLOCK_MAXRECS(mp, level) \
357 xfs_allocbt_maxrecs((mp), (mp)->m_sb.sb_blocksize, \
361 * this calculates a freespace cursor for an ag.
362 * btree_curs is an in/out. returns the number of
363 * blocks that will show up in the AGFL.
367 calculate_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
368 xfs_agblock_t
*extents
, bt_status_t
*btree_curs
)
370 xfs_extlen_t blocks_needed
; /* a running count */
371 xfs_extlen_t blocks_allocated_pt
; /* per tree */
372 xfs_extlen_t blocks_allocated_total
; /* for both trees */
373 xfs_agblock_t num_extents
;
377 bt_stat_level_t
*lptr
;
378 bt_stat_level_t
*p_lptr
;
379 extent_tree_node_t
*ext_ptr
;
381 #ifdef XR_BLD_FREE_TRACE
383 int state
= XR_E_BAD_STATE
;
385 #ifdef XR_BLD_FREE_TRACE
387 "in init_freespace_cursor, agno = %d\n", agno
);
390 num_extents
= *extents
;
393 ASSERT(num_extents
!= 0);
395 lptr
= &btree_curs
->level
[0];
396 btree_curs
->init
= 1;
399 * figure out how much space we need for the leaf level
400 * of the tree and set up the cursor for the leaf level
401 * (note that the same code is duplicated further down)
403 lptr
->num_blocks
= howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
404 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
405 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
406 lptr
->num_recs_tot
= num_extents
;
410 * if we need more levels, set them up. # of records
411 * per level is the # of blocks in the level below it
413 if (lptr
->num_blocks
> 1) {
414 for (; btree_curs
->level
[level
- 1].num_blocks
> 1
415 && level
< XFS_BTREE_MAXLEVELS
;
417 lptr
= &btree_curs
->level
[level
];
418 p_lptr
= &btree_curs
->level
[level
- 1];
419 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
420 XR_ALLOC_BLOCK_MAXRECS(mp
, level
));
421 lptr
->modulo
= p_lptr
->num_blocks
423 lptr
->num_recs_pb
= p_lptr
->num_blocks
425 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
429 ASSERT(lptr
->num_blocks
== 1);
430 btree_curs
->num_levels
= level
;
433 * ok, now we have a hypothetical cursor that
434 * will work for both the bno and bcnt trees.
435 * now figure out if using up blocks to set up the
436 * trees will perturb the shape of the freespace tree.
437 * if so, we've over-allocated. the freespace trees
438 * as they will be *after* accounting for the free space
439 * we've used up will need fewer blocks to to represent
440 * than we've allocated. We can use the AGFL to hold
441 * XFS_AGFL_SIZE (sector/xfs_agfl_t) blocks but that's it.
442 * Thus we limit things to XFS_AGFL_SIZE/2 for each of the 2 btrees.
443 * if the number of extra blocks is more than that,
444 * we'll have to be called again.
446 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
447 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
451 * record the # of blocks we've allocated
453 blocks_allocated_pt
= blocks_needed
;
455 blocks_allocated_total
= blocks_needed
;
458 * figure out how many free extents will be used up by
459 * our space allocation
461 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
462 do_error(_("can't rebuild fs trees -- not enough free space "
463 "on ag %u\n"), agno
);
466 while (ext_ptr
!= NULL
&& blocks_needed
> 0) {
467 if (ext_ptr
->ex_blockcount
<= blocks_needed
) {
468 blocks_needed
-= ext_ptr
->ex_blockcount
;
474 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
476 #ifdef XR_BLD_FREE_TRACE
477 if (ext_ptr
!= NULL
) {
478 fprintf(stderr
, "got next extent [%u %u]\n",
479 ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
481 fprintf(stderr
, "out of extents\n");
485 if (blocks_needed
> 0)
486 do_error(_("ag %u - not enough free space to build freespace "
489 ASSERT(num_extents
>= extents_used
);
491 num_extents
-= extents_used
;
494 * see if the number of leaf blocks will change as a result
495 * of the number of extents changing
497 if (howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0))
498 != btree_curs
->level
[0].num_blocks
) {
500 * yes -- recalculate the cursor. If the number of
501 * excess (overallocated) blocks is < XFS_AGFL_SIZE/2, we're ok.
502 * we can put those into the AGFL. we don't try
503 * and get things to converge exactly (reach a
504 * state with zero excess blocks) because there
505 * exist pathological cases which will never
506 * converge. first, check for the zero-case.
508 if (num_extents
== 0) {
510 * ok, we've used up all the free blocks
511 * trying to lay out the leaf level. go
512 * to a one block (empty) btree and put the
513 * already allocated blocks into the AGFL
515 if (btree_curs
->level
[0].num_blocks
!= 1) {
517 * we really needed more blocks because
518 * the old tree had more than one level.
521 do_warn(_("not enough free blocks left to "
522 "describe all free blocks in AG "
525 #ifdef XR_BLD_FREE_TRACE
527 "ag %u -- no free extents, alloc'ed %d\n",
528 agno
, blocks_allocated_pt
);
530 lptr
->num_blocks
= 1;
532 lptr
->num_recs_pb
= 0;
533 lptr
->num_recs_tot
= 0;
535 btree_curs
->num_levels
= 1;
538 * don't reset the allocation stats, assume
539 * they're all extra blocks
540 * don't forget to return the total block count
541 * not the per-tree block count. these are the
542 * extras that will go into the AGFL. subtract
543 * two for the root blocks.
545 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
546 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
550 return(blocks_allocated_total
- 2);
553 lptr
= &btree_curs
->level
[0];
554 lptr
->num_blocks
= howmany(num_extents
,
555 XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
556 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
557 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
558 lptr
->num_recs_tot
= num_extents
;
562 * if we need more levels, set them up
564 if (lptr
->num_blocks
> 1) {
565 for (level
= 1; btree_curs
->level
[level
-1].num_blocks
566 > 1 && level
< XFS_BTREE_MAXLEVELS
;
568 lptr
= &btree_curs
->level
[level
];
569 p_lptr
= &btree_curs
->level
[level
-1];
570 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
571 XR_ALLOC_BLOCK_MAXRECS(mp
,
573 lptr
->modulo
= p_lptr
->num_blocks
575 lptr
->num_recs_pb
= p_lptr
->num_blocks
577 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
580 ASSERT(lptr
->num_blocks
== 1);
581 btree_curs
->num_levels
= level
;
584 * now figure out the number of excess blocks
586 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
587 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
591 ASSERT(blocks_allocated_total
>= blocks_needed
);
592 extra_blocks
= blocks_allocated_total
- blocks_needed
;
594 if (extents_used
> 0) {
596 * reset the leaf level geometry to account
597 * for consumed extents. we can leave the
598 * rest of the cursor alone since the number
599 * of leaf blocks hasn't changed.
601 lptr
= &btree_curs
->level
[0];
603 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
604 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
605 lptr
->num_recs_tot
= num_extents
;
611 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
612 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
614 *extents
= num_extents
;
616 return(extra_blocks
);
620 prop_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
621 bt_status_t
*btree_curs
, xfs_agblock_t startblock
,
622 xfs_extlen_t blockcount
, int level
, __uint32_t magic
)
624 struct xfs_btree_block
*bt_hdr
;
625 xfs_alloc_key_t
*bt_key
;
626 xfs_alloc_ptr_t
*bt_ptr
;
628 bt_stat_level_t
*lptr
;
632 if (level
>= btree_curs
->num_levels
)
635 lptr
= &btree_curs
->level
[level
];
636 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
638 if (be16_to_cpu(bt_hdr
->bb_numrecs
) == 0) {
640 * only happens once when initializing the
641 * left-hand side of the tree.
643 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
644 blockcount
, level
, magic
);
647 if (be16_to_cpu(bt_hdr
->bb_numrecs
) ==
648 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
650 * write out current prev block, grab us a new block,
651 * and set the rightsib pointer of current block
653 #ifdef XR_BLD_FREE_TRACE
654 fprintf(stderr
, " %d ", lptr
->prev_agbno
);
656 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
657 ASSERT(lptr
->prev_buf_p
!= NULL
);
658 libxfs_writebuf(lptr
->prev_buf_p
, 0);
660 lptr
->prev_agbno
= lptr
->agbno
;;
661 lptr
->prev_buf_p
= lptr
->buf_p
;
662 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
664 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(agbno
);
666 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
667 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
668 XFS_FSB_TO_BB(mp
, 1));
675 * initialize block header
677 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
678 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
680 bt_hdr
->bb_magic
= cpu_to_be32(magic
);
681 bt_hdr
->bb_level
= cpu_to_be16(level
);
682 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
683 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
684 bt_hdr
->bb_numrecs
= 0;
687 * propagate extent record for first extent in new block up
689 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
690 blockcount
, level
, magic
);
693 * add extent info to current block
695 be16_add_cpu(&bt_hdr
->bb_numrecs
, 1);
697 bt_key
= XFS_ALLOC_KEY_ADDR(mp
, bt_hdr
,
698 be16_to_cpu(bt_hdr
->bb_numrecs
));
699 bt_ptr
= XFS_ALLOC_PTR_ADDR(mp
, bt_hdr
,
700 be16_to_cpu(bt_hdr
->bb_numrecs
),
703 bt_key
->ar_startblock
= cpu_to_be32(startblock
);
704 bt_key
->ar_blockcount
= cpu_to_be32(blockcount
);
705 *bt_ptr
= cpu_to_be32(btree_curs
->level
[level
-1].agbno
);
709 * rebuilds a freespace tree given a cursor and magic number of type
710 * of tree to build (bno or bcnt). returns the number of free blocks
711 * represented by the tree.
714 build_freespace_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
715 bt_status_t
*btree_curs
, __uint32_t magic
)
719 struct xfs_btree_block
*bt_hdr
;
720 xfs_alloc_rec_t
*bt_rec
;
723 extent_tree_node_t
*ext_ptr
;
724 bt_stat_level_t
*lptr
;
725 xfs_extlen_t freeblks
;
727 #ifdef XR_BLD_FREE_TRACE
728 fprintf(stderr
, "in build_freespace_tree, agno = %d\n", agno
);
730 level
= btree_curs
->num_levels
;
736 * initialize the first block on each btree level
738 for (i
= 0; i
< level
; i
++) {
739 lptr
= &btree_curs
->level
[i
];
741 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
742 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
743 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
744 XFS_FSB_TO_BB(mp
, 1));
746 if (i
== btree_curs
->num_levels
- 1)
747 btree_curs
->root
= agbno
;
750 lptr
->prev_agbno
= NULLAGBLOCK
;
751 lptr
->prev_buf_p
= NULL
;
753 * initialize block header
755 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
756 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
758 bt_hdr
->bb_magic
= cpu_to_be32(magic
);
759 bt_hdr
->bb_level
= cpu_to_be16(i
);
760 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
761 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
762 bt_hdr
->bb_numrecs
= 0;
765 * run along leaf, setting up records. as we have to switch
766 * blocks, call the prop_freespace_cursor routine to set up the new
767 * pointers for the parent. that can recurse up to the root
768 * if required. set the sibling pointers for leaf level here.
770 if (magic
== XFS_ABTB_MAGIC
)
771 ext_ptr
= findfirst_bno_extent(agno
);
773 ext_ptr
= findfirst_bcnt_extent(agno
);
775 #ifdef XR_BLD_FREE_TRACE
776 fprintf(stderr
, "bft, agno = %d, start = %u, count = %u\n",
777 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
780 lptr
= &btree_curs
->level
[0];
782 for (i
= 0; i
< btree_curs
->level
[0].num_blocks
; i
++) {
784 * block initialization, lay in block header
786 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
787 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
789 bt_hdr
->bb_magic
= cpu_to_be32(magic
);
790 bt_hdr
->bb_level
= 0;
791 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
792 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
793 bt_hdr
->bb_numrecs
= cpu_to_be16(lptr
->num_recs_pb
+
795 #ifdef XR_BLD_FREE_TRACE
796 fprintf(stderr
, "bft, bb_numrecs = %d\n",
797 be16_to_cpu(bt_hdr
->bb_numrecs
));
800 if (lptr
->modulo
> 0)
804 * initialize values in the path up to the root if
805 * this is a multi-level btree
807 if (btree_curs
->num_levels
> 1)
808 prop_freespace_cursor(mp
, agno
, btree_curs
,
809 ext_ptr
->ex_startblock
,
810 ext_ptr
->ex_blockcount
,
813 bt_rec
= (xfs_alloc_rec_t
*)
814 ((char *)bt_hdr
+ XFS_ALLOC_BLOCK_LEN(mp
));
815 for (j
= 0; j
< be16_to_cpu(bt_hdr
->bb_numrecs
); j
++) {
816 ASSERT(ext_ptr
!= NULL
);
817 bt_rec
[j
].ar_startblock
= cpu_to_be32(
818 ext_ptr
->ex_startblock
);
819 bt_rec
[j
].ar_blockcount
= cpu_to_be32(
820 ext_ptr
->ex_blockcount
);
821 freeblks
+= ext_ptr
->ex_blockcount
;
822 if (magic
== XFS_ABTB_MAGIC
)
823 ext_ptr
= findnext_bno_extent(ext_ptr
);
825 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
827 #ifdef XR_BLD_FREE_TRACE
829 fprintf(stderr
, "null extent pointer, j = %d\n",
833 "bft, agno = %d, start = %u, count = %u\n",
834 agno
, ext_ptr
->ex_startblock
,
835 ext_ptr
->ex_blockcount
);
840 if (ext_ptr
!= NULL
) {
842 * get next leaf level block
844 if (lptr
->prev_buf_p
!= NULL
) {
845 #ifdef XR_BLD_FREE_TRACE
846 fprintf(stderr
, " writing fst agbno %u\n",
849 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
850 libxfs_writebuf(lptr
->prev_buf_p
, 0);
852 lptr
->prev_buf_p
= lptr
->buf_p
;
853 lptr
->prev_agbno
= lptr
->agbno
;
854 lptr
->agbno
= get_next_blockaddr(agno
, 0, btree_curs
);
855 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(lptr
->agbno
);
857 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
858 XFS_AGB_TO_DADDR(mp
, agno
, lptr
->agbno
),
859 XFS_FSB_TO_BB(mp
, 1));
867 * XXX(hch): any reason we don't just look at mp->m_inobt_mxr?
869 #define XR_INOBT_BLOCK_MAXRECS(mp, level) \
870 xfs_inobt_maxrecs((mp), (mp)->m_sb.sb_blocksize, \
874 * we don't have to worry here about how chewing up free extents
875 * may perturb things because inode tree building happens before
876 * freespace tree building.
879 init_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
880 __uint64_t
*num_inos
, __uint64_t
*num_free_inos
)
884 ino_tree_node_t
*ino_rec
;
887 bt_stat_level_t
*lptr
;
888 bt_stat_level_t
*p_lptr
;
889 xfs_extlen_t blocks_allocated
;
892 *num_inos
= *num_free_inos
= 0;
895 lptr
= &btree_curs
->level
[0];
896 btree_curs
->init
= 1;
898 if ((ino_rec
= findfirst_inode_rec(agno
)) == NULL
) {
900 * easy corner-case -- no inode records
902 lptr
->num_blocks
= 1;
904 lptr
->num_recs_pb
= 0;
905 lptr
->num_recs_tot
= 0;
907 btree_curs
->num_levels
= 1;
908 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
= 1;
910 setup_cursor(mp
, agno
, btree_curs
);
916 * build up statistics
918 for (num_recs
= 0; ino_rec
!= NULL
; ino_rec
= next_ino_rec(ino_rec
)) {
919 ninos
+= XFS_INODES_PER_CHUNK
;
921 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
922 ASSERT(is_inode_confirmed(ino_rec
, i
));
923 if (is_inode_free(ino_rec
, i
))
928 blocks_allocated
= lptr
->num_blocks
= howmany(num_recs
,
929 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
931 lptr
->modulo
= num_recs
% lptr
->num_blocks
;
932 lptr
->num_recs_pb
= num_recs
/ lptr
->num_blocks
;
933 lptr
->num_recs_tot
= num_recs
;
936 if (lptr
->num_blocks
> 1) {
937 for (; btree_curs
->level
[level
-1].num_blocks
> 1
938 && level
< XFS_BTREE_MAXLEVELS
;
940 lptr
= &btree_curs
->level
[level
];
941 p_lptr
= &btree_curs
->level
[level
- 1];
942 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
943 XR_INOBT_BLOCK_MAXRECS(mp
, level
));
944 lptr
->modulo
= p_lptr
->num_blocks
% lptr
->num_blocks
;
945 lptr
->num_recs_pb
= p_lptr
->num_blocks
947 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
949 blocks_allocated
+= lptr
->num_blocks
;
952 ASSERT(lptr
->num_blocks
== 1);
953 btree_curs
->num_levels
= level
;
955 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
958 setup_cursor(mp
, agno
, btree_curs
);
961 *num_free_inos
= nfinos
;
967 prop_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
968 xfs_agino_t startino
, int level
)
970 struct xfs_btree_block
*bt_hdr
;
971 xfs_inobt_key_t
*bt_key
;
972 xfs_inobt_ptr_t
*bt_ptr
;
974 bt_stat_level_t
*lptr
;
978 if (level
>= btree_curs
->num_levels
)
981 lptr
= &btree_curs
->level
[level
];
982 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
984 if (be16_to_cpu(bt_hdr
->bb_numrecs
) == 0) {
986 * this only happens once to initialize the
987 * first path up the left side of the tree
988 * where the agbno's are already set up
990 prop_ino_cursor(mp
, agno
, btree_curs
, startino
, level
);
993 if (be16_to_cpu(bt_hdr
->bb_numrecs
) ==
994 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
996 * write out current prev block, grab us a new block,
997 * and set the rightsib pointer of current block
999 #ifdef XR_BLD_INO_TRACE
1000 fprintf(stderr
, " ino prop agbno %d ", lptr
->prev_agbno
);
1002 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
1003 ASSERT(lptr
->prev_buf_p
!= NULL
);
1004 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1006 lptr
->prev_agbno
= lptr
->agbno
;;
1007 lptr
->prev_buf_p
= lptr
->buf_p
;
1008 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
1010 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(agbno
);
1012 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1013 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1014 XFS_FSB_TO_BB(mp
, 1));
1015 lptr
->agbno
= agbno
;
1021 * initialize block header
1023 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1024 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1026 bt_hdr
->bb_magic
= cpu_to_be32(XFS_IBT_MAGIC
);
1027 bt_hdr
->bb_level
= cpu_to_be16(level
);
1028 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
1029 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1030 bt_hdr
->bb_numrecs
= 0;
1032 * propagate extent record for first extent in new block up
1034 prop_ino_cursor(mp
, agno
, btree_curs
, startino
, level
);
1037 * add inode info to current block
1039 be16_add_cpu(&bt_hdr
->bb_numrecs
, 1);
1041 bt_key
= XFS_INOBT_KEY_ADDR(mp
, bt_hdr
,
1042 be16_to_cpu(bt_hdr
->bb_numrecs
));
1043 bt_ptr
= XFS_INOBT_PTR_ADDR(mp
, bt_hdr
,
1044 be16_to_cpu(bt_hdr
->bb_numrecs
),
1045 mp
->m_inobt_mxr
[1]);
1047 bt_key
->ir_startino
= cpu_to_be32(startino
);
1048 *bt_ptr
= cpu_to_be32(btree_curs
->level
[level
-1].agbno
);
1052 build_agi(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1053 bt_status_t
*btree_curs
, xfs_agino_t first_agino
,
1054 xfs_agino_t count
, xfs_agino_t freecount
)
1060 agi_buf
= libxfs_getbuf(mp
->m_dev
,
1061 XFS_AG_DADDR(mp
, agno
, XFS_AGI_DADDR(mp
)),
1062 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1063 agi
= XFS_BUF_TO_AGI(agi_buf
);
1064 memset(agi
, 0, mp
->m_sb
.sb_sectsize
);
1066 agi
->agi_magicnum
= cpu_to_be32(XFS_AGI_MAGIC
);
1067 agi
->agi_versionnum
= cpu_to_be32(XFS_AGI_VERSION
);
1068 agi
->agi_seqno
= cpu_to_be32(agno
);
1069 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1070 agi
->agi_length
= cpu_to_be32(mp
->m_sb
.sb_agblocks
);
1072 agi
->agi_length
= cpu_to_be32(mp
->m_sb
.sb_dblocks
-
1073 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1074 agi
->agi_count
= cpu_to_be32(count
);
1075 agi
->agi_root
= cpu_to_be32(btree_curs
->root
);
1076 agi
->agi_level
= cpu_to_be32(btree_curs
->num_levels
);
1077 agi
->agi_freecount
= cpu_to_be32(freecount
);
1078 agi
->agi_newino
= cpu_to_be32(first_agino
);
1079 agi
->agi_dirino
= cpu_to_be32(NULLAGINO
);
1081 for (i
= 0; i
< XFS_AGI_UNLINKED_BUCKETS
; i
++)
1082 agi
->agi_unlinked
[i
] = cpu_to_be32(NULLAGINO
);
1084 libxfs_writebuf(agi_buf
, 0);
1088 * rebuilds an inode tree given a cursor. We're lazy here and call
1089 * the routine that builds the agi
1092 build_ino_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1093 bt_status_t
*btree_curs
)
1097 xfs_agblock_t agbno
;
1098 xfs_agino_t first_agino
;
1099 struct xfs_btree_block
*bt_hdr
;
1100 xfs_inobt_rec_t
*bt_rec
;
1101 ino_tree_node_t
*ino_rec
;
1102 bt_stat_level_t
*lptr
;
1103 xfs_agino_t count
= 0;
1104 xfs_agino_t freecount
= 0;
1107 int level
= btree_curs
->num_levels
;
1109 for (i
= 0; i
< level
; i
++) {
1110 lptr
= &btree_curs
->level
[i
];
1112 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
1113 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1114 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1115 XFS_FSB_TO_BB(mp
, 1));
1117 if (i
== btree_curs
->num_levels
- 1)
1118 btree_curs
->root
= agbno
;
1120 lptr
->agbno
= agbno
;
1121 lptr
->prev_agbno
= NULLAGBLOCK
;
1122 lptr
->prev_buf_p
= NULL
;
1124 * initialize block header
1126 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1127 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1129 bt_hdr
->bb_magic
= cpu_to_be32(XFS_IBT_MAGIC
);
1130 bt_hdr
->bb_level
= cpu_to_be16(i
);
1131 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(NULLAGBLOCK
);
1132 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1133 bt_hdr
->bb_numrecs
= 0;
1136 * run along leaf, setting up records. as we have to switch
1137 * blocks, call the prop_ino_cursor routine to set up the new
1138 * pointers for the parent. that can recurse up to the root
1139 * if required. set the sibling pointers for leaf level here.
1141 ino_rec
= findfirst_inode_rec(agno
);
1143 if (ino_rec
!= NULL
)
1144 first_agino
= ino_rec
->ino_startnum
;
1146 first_agino
= NULLAGINO
;
1148 lptr
= &btree_curs
->level
[0];
1150 for (i
= 0; i
< lptr
->num_blocks
; i
++) {
1152 * block initialization, lay in block header
1154 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1155 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1157 bt_hdr
->bb_magic
= cpu_to_be32(XFS_IBT_MAGIC
);
1158 bt_hdr
->bb_level
= 0;
1159 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
1160 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(NULLAGBLOCK
);
1161 bt_hdr
->bb_numrecs
= cpu_to_be16(lptr
->num_recs_pb
+
1162 (lptr
->modulo
> 0));
1164 if (lptr
->modulo
> 0)
1167 if (lptr
->num_recs_pb
> 0)
1168 prop_ino_cursor(mp
, agno
, btree_curs
,
1169 ino_rec
->ino_startnum
, 0);
1171 bt_rec
= (xfs_inobt_rec_t
*)
1172 ((char *)bt_hdr
+ XFS_INOBT_BLOCK_LEN(mp
));
1173 for (j
= 0; j
< be16_to_cpu(bt_hdr
->bb_numrecs
); j
++) {
1174 ASSERT(ino_rec
!= NULL
);
1175 bt_rec
[j
].ir_startino
=
1176 cpu_to_be32(ino_rec
->ino_startnum
);
1177 bt_rec
[j
].ir_free
= cpu_to_be64(ino_rec
->ir_free
);
1180 for (k
= 0; k
< sizeof(xfs_inofree_t
)*NBBY
; k
++) {
1181 ASSERT(is_inode_confirmed(ino_rec
, k
));
1182 inocnt
+= is_inode_free(ino_rec
, k
);
1185 bt_rec
[j
].ir_freecount
= cpu_to_be32(inocnt
);
1186 freecount
+= inocnt
;
1187 count
+= XFS_INODES_PER_CHUNK
;
1188 ino_rec
= next_ino_rec(ino_rec
);
1191 if (ino_rec
!= NULL
) {
1193 * get next leaf level block
1195 if (lptr
->prev_buf_p
!= NULL
) {
1196 #ifdef XR_BLD_INO_TRACE
1197 fprintf(stderr
, "writing inobt agbno %u\n",
1200 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
1201 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1203 lptr
->prev_buf_p
= lptr
->buf_p
;
1204 lptr
->prev_agbno
= lptr
->agbno
;
1205 lptr
->agbno
= get_next_blockaddr(agno
, 0, btree_curs
);
1206 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(lptr
->agbno
);
1208 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1209 XFS_AGB_TO_DADDR(mp
, agno
, lptr
->agbno
),
1210 XFS_FSB_TO_BB(mp
, 1));
1214 build_agi(mp
, agno
, btree_curs
, first_agino
, count
, freecount
);
1218 * build both the agf and the agfl for an agno given both
1222 build_agf_agfl(xfs_mount_t
*mp
,
1223 xfs_agnumber_t agno
,
1224 bt_status_t
*bno_bt
,
1225 bt_status_t
*bcnt_bt
,
1226 xfs_extlen_t freeblks
, /* # free blocks in tree */
1227 int lostblocks
) /* # blocks that will be lost */
1229 extent_tree_node_t
*ext_ptr
;
1230 xfs_buf_t
*agf_buf
, *agfl_buf
;
1236 agf_buf
= libxfs_getbuf(mp
->m_dev
,
1237 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
1238 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1239 agf
= XFS_BUF_TO_AGF(agf_buf
);
1240 memset(agf
, 0, mp
->m_sb
.sb_sectsize
);
1242 #ifdef XR_BLD_FREE_TRACE
1243 fprintf(stderr
, "agf = 0x%x, agf_buf->b_un.b_addr = 0x%x\n",
1244 (__psint_t
) agf
, (__psint_t
) agf_buf
->b_un
.b_addr
);
1248 * set up fixed part of agf
1250 agf
->agf_magicnum
= cpu_to_be32(XFS_AGF_MAGIC
);
1251 agf
->agf_versionnum
= cpu_to_be32(XFS_AGF_VERSION
);
1252 agf
->agf_seqno
= cpu_to_be32(agno
);
1254 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1255 agf
->agf_length
= cpu_to_be32(mp
->m_sb
.sb_agblocks
);
1257 agf
->agf_length
= cpu_to_be32(mp
->m_sb
.sb_dblocks
-
1258 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1260 agf
->agf_roots
[XFS_BTNUM_BNO
] = cpu_to_be32(bno_bt
->root
);
1261 agf
->agf_levels
[XFS_BTNUM_BNO
] = cpu_to_be32(bno_bt
->num_levels
);
1262 agf
->agf_roots
[XFS_BTNUM_CNT
] = cpu_to_be32(bcnt_bt
->root
);
1263 agf
->agf_levels
[XFS_BTNUM_CNT
] = cpu_to_be32(bcnt_bt
->num_levels
);
1264 agf
->agf_freeblks
= cpu_to_be32(freeblks
);
1267 * Count and record the number of btree blocks consumed if required.
1269 if (xfs_sb_version_haslazysbcount(&mp
->m_sb
)) {
1271 * Don't count the root blocks as they are already
1274 agf
->agf_btreeblks
= cpu_to_be32(
1275 (bno_bt
->num_tot_blocks
- bno_bt
->num_free_blocks
) +
1276 (bcnt_bt
->num_tot_blocks
- bcnt_bt
->num_free_blocks
) -
1278 #ifdef XR_BLD_FREE_TRACE
1279 fprintf(stderr
, "agf->agf_btreeblks = %u\n",
1280 be32_to_cpu(agf
->agf_btreeblks
));
1284 #ifdef XR_BLD_FREE_TRACE
1285 fprintf(stderr
, "bno root = %u, bcnt root = %u, indices = %u %u\n",
1286 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_BNO
]),
1287 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_CNT
]),
1293 * do we have left-over blocks in the btree cursors that should
1294 * be used to fill the AGFL?
1296 if (bno_bt
->num_free_blocks
> 0 || bcnt_bt
->num_free_blocks
> 0) {
1298 * yes - grab the AGFL buffer
1300 agfl_buf
= libxfs_getbuf(mp
->m_dev
,
1301 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
1302 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1303 agfl
= XFS_BUF_TO_AGFL(agfl_buf
);
1304 memset(agfl
, 0, mp
->m_sb
.sb_sectsize
);
1306 * ok, now grab as many blocks as we can
1309 while (bno_bt
->num_free_blocks
> 0 && i
< XFS_AGFL_SIZE(mp
)) {
1310 agfl
->agfl_bno
[i
] = cpu_to_be32(
1311 get_next_blockaddr(agno
, 0, bno_bt
));
1315 while (bcnt_bt
->num_free_blocks
> 0 && i
< XFS_AGFL_SIZE(mp
)) {
1316 agfl
->agfl_bno
[i
] = cpu_to_be32(
1317 get_next_blockaddr(agno
, 0, bcnt_bt
));
1321 * now throw the rest of the blocks away and complain
1323 while (bno_bt
->num_free_blocks
> 0) {
1324 (void) get_next_blockaddr(agno
, 0, bno_bt
);
1327 while (bcnt_bt
->num_free_blocks
> 0) {
1328 (void) get_next_blockaddr(agno
, 0, bcnt_bt
);
1333 if (j
== lostblocks
)
1334 do_warn(_("lost %d blocks in ag %u\n"),
1337 do_warn(_("thought we were going to lose %d "
1338 "blocks in ag %u, actually lost "
1340 lostblocks
, j
, agno
);
1343 agf
->agf_flfirst
= 0;
1344 agf
->agf_fllast
= cpu_to_be32(i
- 1);
1345 agf
->agf_flcount
= cpu_to_be32(i
);
1347 #ifdef XR_BLD_FREE_TRACE
1348 fprintf(stderr
, "writing agfl for ag %u\n", agno
);
1351 libxfs_writebuf(agfl_buf
, 0);
1353 agf
->agf_flfirst
= 0;
1354 agf
->agf_fllast
= cpu_to_be32(XFS_AGFL_SIZE(mp
) - 1);
1355 agf
->agf_flcount
= 0;
1358 ext_ptr
= findbiggest_bcnt_extent(agno
);
1359 agf
->agf_longest
= cpu_to_be32((ext_ptr
!= NULL
) ?
1360 ext_ptr
->ex_blockcount
: 0);
1362 ASSERT(be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_BNOi
]) !=
1363 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_CNTi
]));
1365 libxfs_writebuf(agf_buf
, 0);
1367 #ifdef XR_BLD_FREE_TRACE
1368 fprintf(stderr
, "wrote agf for ag %u, error = %d\n", agno
, error
);
1373 * update the superblock counters, sync the sb version numbers and
1374 * feature bits to the filesystem, and sync up the on-disk superblock
1375 * to match the incore superblock.
1378 sync_sb(xfs_mount_t
*mp
)
1382 bp
= libxfs_getsb(mp
, 0);
1384 do_error(_("couldn't get superblock\n"));
1386 mp
->m_sb
.sb_icount
= sb_icount
;
1387 mp
->m_sb
.sb_ifree
= sb_ifree
;
1388 mp
->m_sb
.sb_fdblocks
= sb_fdblocks
;
1389 mp
->m_sb
.sb_frextents
= sb_frextents
;
1391 update_sb_version(mp
);
1393 libxfs_sb_to_disk(XFS_BUF_TO_SBP(bp
), &mp
->m_sb
, XFS_SB_ALL_BITS
);
1394 libxfs_writebuf(bp
, 0);
1398 * make sure the root and realtime inodes show up allocated
1399 * even if they've been freed. they get reinitialized in phase6.
1402 keep_fsinos(xfs_mount_t
*mp
)
1404 ino_tree_node_t
*irec
;
1407 irec
= find_inode_rec(XFS_INO_TO_AGNO(mp
, mp
->m_sb
.sb_rootino
),
1408 XFS_INO_TO_AGINO(mp
, mp
->m_sb
.sb_rootino
));
1410 for (i
= 0; i
< 3; i
++)
1411 set_inode_used(irec
, i
);
1417 xfs_agnumber_t agno
)
1419 __uint64_t num_inos
;
1420 __uint64_t num_free_inos
;
1421 bt_status_t bno_btree_curs
;
1422 bt_status_t bcnt_btree_curs
;
1423 bt_status_t ino_btree_curs
;
1424 int extra_blocks
= 0;
1425 uint num_freeblocks
;
1426 xfs_extlen_t freeblks1
;
1428 xfs_extlen_t freeblks2
;
1430 xfs_agblock_t num_extents
;
1431 extern int count_bno_extents(xfs_agnumber_t
);
1432 extern int count_bno_extents_blocks(xfs_agnumber_t
, uint
*);
1433 #ifdef XR_BLD_FREE_TRACE
1434 extern int count_bcnt_extents(xfs_agnumber_t
);
1438 do_log(_(" - agno = %d\n"), agno
);
1442 * build up incore bno and bcnt extent btrees
1444 num_extents
= mk_incore_fstree(mp
, agno
);
1446 #ifdef XR_BLD_FREE_TRACE
1447 fprintf(stderr
, "# of bno extents is %d\n",
1448 count_bno_extents(agno
));
1451 if (num_extents
== 0) {
1453 * XXX - what we probably should do here is pick an
1454 * inode for a regular file in the allocation group
1455 * that has space allocated and shoot it by traversing
1456 * the bmap list and putting all its extents on the
1457 * incore freespace trees, clearing the inode,
1458 * and clearing the in-use bit in the incore inode
1459 * tree. Then try mk_incore_fstree() again.
1461 do_error(_("unable to rebuild AG %u. "
1462 "Not enough free space in on-disk AG.\n"),
1467 * done with the AG bitmap, toss it...
1469 teardown_ag_bmap(mp
, agno
);
1472 * ok, now set up the btree cursors for the
1473 * on-disk btrees (includs pre-allocating all
1474 * required blocks for the trees themselves)
1476 init_ino_cursor(mp
, agno
, &ino_btree_curs
,
1477 &num_inos
, &num_free_inos
);
1479 sb_icount_ag
[agno
] += num_inos
;
1480 sb_ifree_ag
[agno
] += num_free_inos
;
1482 num_extents
= count_bno_extents_blocks(agno
, &num_freeblocks
);
1484 * lose two blocks per AG -- the space tree roots
1485 * are counted as allocated since the space trees
1488 sb_fdblocks_ag
[agno
] += num_freeblocks
- 2;
1490 if (num_extents
== 0) {
1492 * XXX - what we probably should do here is pick an
1493 * inode for a regular file in the allocation group
1494 * that has space allocated and shoot it by traversing
1495 * the bmap list and putting all its extents on the
1496 * incore freespace trees, clearing the inode,
1497 * and clearing the in-use bit in the incore inode
1498 * tree. Then try mk_incore_fstree() again.
1501 _("unable to rebuild AG %u. No free space.\n"), agno
);
1504 #ifdef XR_BLD_FREE_TRACE
1505 fprintf(stderr
, "# of bno extents is %d\n", num_extents
);
1509 * track blocks that we might really lose
1511 extra_blocks
= calculate_freespace_cursor(mp
, agno
,
1512 &num_extents
, &bno_btree_curs
);
1515 * freespace btrees live in the "free space" but
1516 * the filesystem treats AGFL blocks as allocated
1517 * since they aren't described by the freespace trees
1521 * see if we can fit all the extra blocks into the AGFL
1523 extra_blocks
= (extra_blocks
- XFS_AGFL_SIZE(mp
) > 0)
1524 ? extra_blocks
- XFS_AGFL_SIZE(mp
)
1527 if (extra_blocks
> 0) {
1528 do_warn(_("lost %d blocks in agno %d, sorry.\n"),
1529 extra_blocks
, agno
);
1530 sb_fdblocks_ag
[agno
] -= extra_blocks
;
1533 bcnt_btree_curs
= bno_btree_curs
;
1535 setup_cursor(mp
, agno
, &bno_btree_curs
);
1536 setup_cursor(mp
, agno
, &bcnt_btree_curs
);
1538 #ifdef XR_BLD_FREE_TRACE
1539 fprintf(stderr
, "# of bno extents is %d\n",
1540 count_bno_extents(agno
));
1541 fprintf(stderr
, "# of bcnt extents is %d\n",
1542 count_bcnt_extents(agno
));
1546 * now rebuild the freespace trees
1548 freeblks1
= build_freespace_tree(mp
, agno
,
1549 &bno_btree_curs
, XFS_ABTB_MAGIC
);
1550 #ifdef XR_BLD_FREE_TRACE
1551 fprintf(stderr
, "# of free blocks == %d\n", freeblks1
);
1553 write_cursor(&bno_btree_curs
);
1556 freeblks2
= build_freespace_tree(mp
, agno
,
1557 &bcnt_btree_curs
, XFS_ABTC_MAGIC
);
1559 (void) build_freespace_tree(mp
, agno
,
1560 &bcnt_btree_curs
, XFS_ABTC_MAGIC
);
1562 write_cursor(&bcnt_btree_curs
);
1564 ASSERT(freeblks1
== freeblks2
);
1567 * set up agf and agfl
1569 build_agf_agfl(mp
, agno
, &bno_btree_curs
,
1570 &bcnt_btree_curs
, freeblks1
, extra_blocks
);
1572 * build inode allocation tree. this also build the agi
1574 build_ino_tree(mp
, agno
, &ino_btree_curs
);
1575 write_cursor(&ino_btree_curs
);
1579 finish_cursor(&bno_btree_curs
);
1580 finish_cursor(&ino_btree_curs
);
1581 finish_cursor(&bcnt_btree_curs
);
1583 * release the incore per-AG bno/bcnt trees so
1584 * the extent nodes can be recycled
1586 release_agbno_extent_tree(agno
);
1587 release_agbcnt_extent_tree(agno
);
1589 PROG_RPT_INC(prog_rpt_done
[agno
], 1);
1593 phase5(xfs_mount_t
*mp
)
1595 xfs_agnumber_t agno
;
1597 do_log(_("Phase 5 - rebuild AG headers and trees...\n"));
1598 set_progress_msg(PROG_FMT_REBUILD_AG
, (__uint64_t
)glob_agcount
);
1600 #ifdef XR_BLD_FREE_TRACE
1601 fprintf(stderr
, "inobt level 1, maxrec = %d, minrec = %d\n",
1602 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0),
1603 xfs_inobt_maxrecs(mp
->m_sb
.sb_blocksize
, 0) / 2
1605 fprintf(stderr
, "inobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1606 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1),
1607 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1) / 2);
1608 fprintf(stderr
, "xr inobt level 0 (leaf), maxrec = %d\n",
1609 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
1610 fprintf(stderr
, "xr inobt level 1 (int), maxrec = %d\n",
1611 XR_INOBT_BLOCK_MAXRECS(mp
, 1));
1612 fprintf(stderr
, "bnobt level 1, maxrec = %d, minrec = %d\n",
1613 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0),
1614 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0) / 2);
1615 fprintf(stderr
, "bnobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1616 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 1),
1617 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 1) / 2);
1620 * make sure the root and realtime inodes show up allocated
1624 /* allocate per ag counters */
1625 sb_icount_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1626 if (sb_icount_ag
== NULL
)
1627 do_error(_("cannot alloc sb_icount_ag buffers\n"));
1629 sb_ifree_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1630 if (sb_ifree_ag
== NULL
)
1631 do_error(_("cannot alloc sb_ifree_ag buffers\n"));
1633 sb_fdblocks_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1634 if (sb_fdblocks_ag
== NULL
)
1635 do_error(_("cannot alloc sb_fdblocks_ag buffers\n"));
1637 for (agno
= 0; agno
< mp
->m_sb
.sb_agcount
; agno
++)
1638 phase5_func(mp
, agno
);
1642 /* aggregate per ag counters */
1643 for (agno
= 0; agno
< mp
->m_sb
.sb_agcount
; agno
++) {
1644 sb_icount
+= sb_icount_ag
[agno
];
1645 sb_ifree
+= sb_ifree_ag
[agno
];
1646 sb_fdblocks
+= sb_fdblocks_ag
[agno
];
1650 free(sb_fdblocks_ag
);
1652 if (mp
->m_sb
.sb_rblocks
) {
1654 _(" - generate realtime summary info and bitmap...\n"));
1656 generate_rtinfo(mp
, btmcompute
, sumcompute
);
1657 teardown_rt_bmap(mp
);
1660 do_log(_(" - reset superblock...\n"));
1663 * sync superblock counter and set version bits correctly