2 * Copyright (c) 2000-2001 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
39 #include "err_protos.h"
45 * we maintain the current slice (path from root to leaf)
46 * of the btree incore. when we need a new block, we ask
47 * the block allocator for the address of a block on that
48 * level, map the block in, and set up the appropriate
49 * pointers (child, silbing, etc.) and keys that should
50 * point to the new block.
52 typedef struct bt_stat_level
{
54 * set in setup_cursor routine and maintained in the tree-building
57 xfs_buf_t
*buf_p
; /* 2 buffer pointers to ... */
58 xfs_buf_t
*prev_buf_p
;
59 xfs_agblock_t agbno
; /* current block being filled */
60 xfs_agblock_t prev_agbno
; /* previous block */
62 * set in calculate/init cursor routines for each btree level
64 int num_recs_tot
; /* # tree recs in level */
65 int num_blocks
; /* # tree blocks in level */
66 int num_recs_pb
; /* num_recs_tot / num_blocks */
67 int modulo
; /* num_recs_tot % num_blocks */
70 typedef struct bt_status
{
71 int init
; /* cursor set up once? */
72 int num_levels
; /* # of levels in btree */
73 xfs_extlen_t num_tot_blocks
; /* # blocks alloc'ed for tree */
74 xfs_extlen_t num_free_blocks
;/* # blocks currently unused */
76 xfs_agblock_t root
; /* root block */
78 * list of blocks to be used to set up this tree
79 * and pointer to the first unused block on the list
81 xfs_agblock_t
*btree_blocks
; /* block list */
82 xfs_agblock_t
*free_btree_blocks
; /* first unused block */
84 * per-level status info
86 bt_stat_level_t level
[XFS_BTREE_MAXLEVELS
];
91 mk_incore_fstree(xfs_mount_t
*mp
, xfs_agnumber_t agno
)
95 xfs_agblock_t extent_start
;
96 xfs_extlen_t extent_len
;
100 #ifdef XR_BLD_FREE_TRACE
102 int state
= XR_E_BAD_STATE
;
106 * scan the bitmap for the ag looking for continuous
107 * extents of free blocks. At this point, we know
108 * that blocks in the bitmap are either set to an
109 * "in use" state or set to unknown (0) since the
110 * bmaps were bzero'ed in phase 4 and only blocks
111 * being used by inodes, inode bmaps, ag headers,
112 * and the files themselves were put into the bitmap.
115 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
117 extent_start
= extent_len
= 0;
119 num_extents
= free_blocks
= 0;
121 if (agno
< mp
->m_sb
.sb_agcount
- 1)
122 ag_end
= mp
->m_sb
.sb_agblocks
;
124 ag_end
= mp
->m_sb
.sb_dblocks
-
125 mp
->m_sb
.sb_agblocks
* (mp
->m_sb
.sb_agcount
- 1);
128 * ok, now find the number of extents, keep track of the
131 for (agbno
= 0; agbno
< ag_end
; agbno
++) {
134 state
= get_agbno_state(mp
, agno
, agbno
);
135 if (state
!= old_state
) {
136 fprintf(stderr
, "agbno %u - new state is %d\n",
140 if (get_agbno_state(mp
, agno
, agbno
) < XR_E_INUSE
) {
142 if (in_extent
== 0) {
144 * found the start of a free extent
148 extent_start
= agbno
;
156 * free extent ends here, add extent to the
157 * 2 incore extent (avl-to-be-B+) trees
160 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
161 fprintf(stderr
, "adding extent %u [%u %u]\n",
162 agno
, extent_start
, extent_len
);
164 add_bno_extent(agno
, extent_start
, extent_len
);
165 add_bcnt_extent(agno
, extent_start
, extent_len
);
171 * free extent ends here
174 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
175 fprintf(stderr
, "adding extent %u [%u %u]\n",
176 agno
, extent_start
, extent_len
);
178 add_bno_extent(agno
, extent_start
, extent_len
);
179 add_bcnt_extent(agno
, extent_start
, extent_len
);
187 get_next_blockaddr(xfs_agnumber_t agno
, int level
, bt_status_t
*curs
)
189 ASSERT(curs
->free_btree_blocks
< curs
->btree_blocks
+
190 curs
->num_tot_blocks
);
191 ASSERT(curs
->num_free_blocks
> 0);
193 curs
->num_free_blocks
--;
194 return(*curs
->free_btree_blocks
++);
198 * set up the dynamically allocated block allocation data in the btree
199 * cursor that depends on the info in the static portion of the cursor.
200 * allocates space from the incore bno/bcnt extent trees and sets up
201 * the first path up the left side of the tree. Also sets up the
202 * cursor pointer to the btree root. called by init_freespace_cursor()
203 * and init_ino_cursor()
207 setup_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*curs
)
211 xfs_extlen_t big_extent_len
;
212 xfs_agblock_t big_extent_start
;
213 extent_tree_node_t
*ext_ptr
;
214 extent_tree_node_t
*bno_ext_ptr
;
215 xfs_extlen_t blocks_allocated
;
216 xfs_agblock_t
*agb_ptr
;
219 * get the number of blocks we need to allocate, then
220 * set up block number array, set the free block pointer
221 * to the first block in the array, and null the array
223 big_extent_len
= curs
->num_tot_blocks
;
224 blocks_allocated
= 0;
226 ASSERT(big_extent_len
> 0);
228 if ((curs
->btree_blocks
= malloc(sizeof(xfs_agblock_t
*)
229 * big_extent_len
)) == NULL
)
230 do_error(_("could not set up btree block array\n"));
232 agb_ptr
= curs
->free_btree_blocks
= curs
->btree_blocks
;
234 for (j
= 0; j
< curs
->num_free_blocks
; j
++, agb_ptr
++)
235 *agb_ptr
= NULLAGBLOCK
;
238 * grab the smallest extent and use it up, then get the
239 * next smallest. This mimics the init_*_cursor code.
241 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
242 do_error(_("error - not enough free space in filesystem\n"));
244 agb_ptr
= curs
->btree_blocks
;
245 j
= curs
->level
[0].num_blocks
;
248 * set up the free block array
250 while (blocks_allocated
< big_extent_len
) {
252 * use up the extent we've got
254 for (u
= 0; u
< ext_ptr
->ex_blockcount
&&
255 blocks_allocated
< big_extent_len
; u
++) {
256 ASSERT(agb_ptr
< curs
->btree_blocks
257 + curs
->num_tot_blocks
);
258 *agb_ptr
++ = ext_ptr
->ex_startblock
+ u
;
263 * if we only used part of this last extent, then we
264 * need only to reset the extent in the extent
265 * trees and we're done
267 if (u
< ext_ptr
->ex_blockcount
) {
268 big_extent_start
= ext_ptr
->ex_startblock
+ u
;
269 big_extent_len
= ext_ptr
->ex_blockcount
- u
;
271 ASSERT(big_extent_len
> 0);
273 bno_ext_ptr
= find_bno_extent(agno
,
274 ext_ptr
->ex_startblock
);
275 ASSERT(bno_ext_ptr
!= NULL
);
276 get_bno_extent(agno
, bno_ext_ptr
);
277 release_extent_tree_node(bno_ext_ptr
);
279 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
280 ext_ptr
->ex_blockcount
);
281 release_extent_tree_node(ext_ptr
);
282 #ifdef XR_BLD_FREE_TRACE
283 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
284 agno
, ext_ptr
->ex_startblock
,
285 ext_ptr
->ex_blockcount
);
286 fprintf(stderr
, "blocks_allocated = %d\n",
290 add_bno_extent(agno
, big_extent_start
, big_extent_len
);
291 add_bcnt_extent(agno
, big_extent_start
, big_extent_len
);
296 * delete the used-up extent from both extent trees and
297 * find next biggest extent
299 #ifdef XR_BLD_FREE_TRACE
300 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
301 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
303 bno_ext_ptr
= find_bno_extent(agno
, ext_ptr
->ex_startblock
);
304 ASSERT(bno_ext_ptr
!= NULL
);
305 get_bno_extent(agno
, bno_ext_ptr
);
306 release_extent_tree_node(bno_ext_ptr
);
308 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
309 ext_ptr
->ex_blockcount
);
310 ASSERT(ext_ptr
!= NULL
);
311 release_extent_tree_node(ext_ptr
);
313 ext_ptr
= findfirst_bcnt_extent(agno
);
315 #ifdef XR_BLD_FREE_TRACE
316 fprintf(stderr
, "blocks_allocated = %d\n",
322 write_cursor(bt_status_t
*curs
)
326 for (i
= 0; i
< curs
->num_levels
; i
++) {
327 #if defined(XR_BLD_FREE_TRACE) || defined(XR_BLD_INO_TRACE)
328 fprintf(stderr
, "writing bt block %u\n", curs
->level
[i
].agbno
);
330 if (curs
->level
[i
].prev_buf_p
!= NULL
) {
331 ASSERT(curs
->level
[i
].prev_agbno
!= NULLAGBLOCK
);
332 libxfs_writebuf(curs
->level
[i
].prev_buf_p
, 0);
334 libxfs_writebuf(curs
->level
[i
].buf_p
, 0);
339 finish_cursor(bt_status_t
*curs
)
341 ASSERT(curs
->num_free_blocks
== 0);
342 free(curs
->btree_blocks
);
346 * no-cursor versions of the XFS equivalents. The address calculators
347 * should be used only for interior btree nodes.
348 * these are adapted from xfs_alloc_btree.h and xfs_tree.h
350 #define XR_ALLOC_KEY_ADDR(mp, bp, i) \
351 (xfs_alloc_key_t *) ((char *) (bp) + sizeof(xfs_alloc_block_t) \
352 + ((i)-1) * sizeof(xfs_alloc_key_t))
354 #define XR_ALLOC_PTR_ADDR(mp, bp, i) \
355 (xfs_alloc_ptr_t *) ((char *) (bp) + sizeof(xfs_alloc_block_t) \
356 + (mp)->m_alloc_mxr[1] * sizeof(xfs_alloc_key_t) \
357 + ((i)-1) * sizeof(xfs_alloc_ptr_t))
359 #define XR_ALLOC_BLOCK_MAXRECS(mp, level) \
360 XFS_BTREE_BLOCK_MAXRECS((mp)->m_sb.sb_blocksize, \
361 xfs_alloc, (level) == 0)
364 * this calculates a freespace cursor for an ag.
365 * btree_curs is an in/out. returns the number of
366 * blocks that will show up in the AGFL.
370 calculate_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
371 xfs_agblock_t
*extents
, bt_status_t
*btree_curs
)
373 xfs_extlen_t blocks_needed
; /* a running count */
374 xfs_extlen_t blocks_allocated_pt
; /* per tree */
375 xfs_extlen_t blocks_allocated_total
; /* for both trees */
376 xfs_agblock_t num_extents
;
380 bt_stat_level_t
*lptr
;
381 bt_stat_level_t
*p_lptr
;
382 extent_tree_node_t
*ext_ptr
;
384 #ifdef XR_BLD_FREE_TRACE
386 int state
= XR_E_BAD_STATE
;
388 #ifdef XR_BLD_FREE_TRACE
390 "in init_freespace_cursor, agno = %d\n", agno
);
393 num_extents
= *extents
;
396 ASSERT(num_extents
!= 0);
398 lptr
= &btree_curs
->level
[0];
399 btree_curs
->init
= 1;
402 * figure out how much space we need for the leaf level
403 * of the tree and set up the cursor for the leaf level
404 * (note that the same code is duplicated further down)
406 lptr
->num_blocks
= howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
407 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
408 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
409 lptr
->num_recs_tot
= num_extents
;
413 * if we need more levels, set them up. # of records
414 * per level is the # of blocks in the level below it
416 if (lptr
->num_blocks
> 1) {
417 for (; btree_curs
->level
[level
- 1].num_blocks
> 1
418 && level
< XFS_BTREE_MAXLEVELS
;
420 lptr
= &btree_curs
->level
[level
];
421 p_lptr
= &btree_curs
->level
[level
- 1];
422 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
423 XR_ALLOC_BLOCK_MAXRECS(mp
, level
));
424 lptr
->modulo
= p_lptr
->num_blocks
426 lptr
->num_recs_pb
= p_lptr
->num_blocks
428 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
432 ASSERT(lptr
->num_blocks
== 1);
433 btree_curs
->num_levels
= level
;
436 * ok, now we have a hypothetical cursor that
437 * will work for both the bno and bcnt trees.
438 * now figure out if using up blocks to set up the
439 * trees will perturb the shape of the freespace tree.
440 * if so, we've over-allocated. the freespace trees
441 * as they will be *after* accounting for the free space
442 * we've used up will need fewer blocks to to represent
443 * than we've allocated. We can use the AGFL to hold
444 * XFS_AGFL_SIZE (sector/xfs_agfl_t) blocks but that's it.
445 * Thus we limit things to XFS_AGFL_SIZE/2 for each of the 2 btrees.
446 * if the number of extra blocks is more than that,
447 * we'll have to be called again.
449 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
450 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
454 * record the # of blocks we've allocated
456 blocks_allocated_pt
= blocks_needed
;
458 blocks_allocated_total
= blocks_needed
;
461 * figure out how many free extents will be used up by
462 * our space allocation
464 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
465 do_error(_("can't rebuild fs trees -- not enough free space "
466 "on ag %u\n"), agno
);
469 while (ext_ptr
!= NULL
&& blocks_needed
> 0) {
470 if (ext_ptr
->ex_blockcount
<= blocks_needed
) {
471 blocks_needed
-= ext_ptr
->ex_blockcount
;
477 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
479 #ifdef XR_BLD_FREE_TRACE
480 if (ext_ptr
!= NULL
) {
481 fprintf(stderr
, "got next extent [%u %u]\n",
482 ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
484 fprintf(stderr
, "out of extents\n");
488 if (blocks_needed
> 0)
489 do_error(_("ag %u - not enough free space to build freespace "
492 ASSERT(num_extents
>= extents_used
);
494 num_extents
-= extents_used
;
497 * see if the number of leaf blocks will change as a result
498 * of the number of extents changing
500 if (howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0))
501 != btree_curs
->level
[0].num_blocks
) {
503 * yes -- recalculate the cursor. If the number of
504 * excess (overallocated) blocks is < XFS_AGFL_SIZE/2, we're ok.
505 * we can put those into the AGFL. we don't try
506 * and get things to converge exactly (reach a
507 * state with zero excess blocks) because there
508 * exist pathological cases which will never
509 * converge. first, check for the zero-case.
511 if (num_extents
== 0) {
513 * ok, we've used up all the free blocks
514 * trying to lay out the leaf level. go
515 * to a one block (empty) btree and put the
516 * already allocated blocks into the AGFL
518 if (btree_curs
->level
[0].num_blocks
!= 1) {
520 * we really needed more blocks because
521 * the old tree had more than one level.
524 do_warn(_("not enough free blocks left to "
525 "describe all free blocks in AG "
528 #ifdef XR_BLD_FREE_TRACE
530 "ag %u -- no free extents, alloc'ed %d\n",
531 agno
, blocks_allocated_pt
);
533 lptr
->num_blocks
= 1;
535 lptr
->num_recs_pb
= 0;
536 lptr
->num_recs_tot
= 0;
538 btree_curs
->num_levels
= 1;
541 * don't reset the allocation stats, assume
542 * they're all extra blocks
543 * don't forget to return the total block count
544 * not the per-tree block count. these are the
545 * extras that will go into the AGFL. subtract
546 * two for the root blocks.
548 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
549 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
553 return(blocks_allocated_total
- 2);
556 lptr
= &btree_curs
->level
[0];
557 lptr
->num_blocks
= howmany(num_extents
,
558 XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
559 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
560 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
561 lptr
->num_recs_tot
= num_extents
;
565 * if we need more levels, set them up
567 if (lptr
->num_blocks
> 1) {
568 for (level
= 1; btree_curs
->level
[level
-1].num_blocks
569 > 1 && level
< XFS_BTREE_MAXLEVELS
;
571 lptr
= &btree_curs
->level
[level
];
572 p_lptr
= &btree_curs
->level
[level
-1];
573 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
574 XR_ALLOC_BLOCK_MAXRECS(mp
,
576 lptr
->modulo
= p_lptr
->num_blocks
578 lptr
->num_recs_pb
= p_lptr
->num_blocks
580 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
583 ASSERT(lptr
->num_blocks
== 1);
584 btree_curs
->num_levels
= level
;
587 * now figure out the number of excess blocks
589 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
590 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
594 ASSERT(blocks_allocated_total
>= blocks_needed
);
595 extra_blocks
= blocks_allocated_total
- blocks_needed
;
597 if (extents_used
> 0) {
599 * reset the leaf level geometry to account
600 * for consumed extents. we can leave the
601 * rest of the cursor alone since the number
602 * of leaf blocks hasn't changed.
604 lptr
= &btree_curs
->level
[0];
606 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
607 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
608 lptr
->num_recs_tot
= num_extents
;
614 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
615 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
617 *extents
= num_extents
;
619 return(extra_blocks
);
623 prop_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
624 bt_status_t
*btree_curs
, xfs_agblock_t startblock
,
625 xfs_extlen_t blockcount
, int level
, __uint32_t magic
)
627 xfs_alloc_block_t
*bt_hdr
;
628 xfs_alloc_key_t
*bt_key
;
629 xfs_alloc_ptr_t
*bt_ptr
;
631 bt_stat_level_t
*lptr
;
635 if (level
>= btree_curs
->num_levels
)
638 lptr
= &btree_curs
->level
[level
];
639 bt_hdr
= XFS_BUF_TO_ALLOC_BLOCK(lptr
->buf_p
);
641 if (INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
) == 0) {
643 * only happens once when initializing the
644 * left-hand side of the tree.
646 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
647 blockcount
, level
, magic
);
650 if (INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
) ==
651 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
653 * write out current prev block, grab us a new block,
654 * and set the rightsib pointer of current block
656 #ifdef XR_BLD_FREE_TRACE
657 fprintf(stderr
, " %d ", lptr
->prev_agbno
);
659 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
660 ASSERT(lptr
->prev_buf_p
!= NULL
);
661 libxfs_writebuf(lptr
->prev_buf_p
, 0);
663 lptr
->prev_agbno
= lptr
->agbno
;;
664 lptr
->prev_buf_p
= lptr
->buf_p
;
665 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
667 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, agbno
);
669 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
670 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
671 XFS_FSB_TO_BB(mp
, 1));
678 * initialize block header
680 bt_hdr
= XFS_BUF_TO_ALLOC_BLOCK(lptr
->buf_p
);
681 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
683 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, magic
);
684 INT_SET(bt_hdr
->bb_level
, ARCH_CONVERT
, level
);
685 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
, lptr
->prev_agbno
);
686 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
687 INT_ZERO(bt_hdr
->bb_numrecs
, ARCH_CONVERT
);
690 * propagate extent record for first extent in new block up
692 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
693 blockcount
, level
, magic
);
696 * add extent info to current block
698 INT_MOD(bt_hdr
->bb_numrecs
, ARCH_CONVERT
, +1);
700 bt_key
= XR_ALLOC_KEY_ADDR(mp
, bt_hdr
,
701 INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
));
702 bt_ptr
= XR_ALLOC_PTR_ADDR(mp
, bt_hdr
,
703 INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
));
705 INT_SET(bt_key
->ar_startblock
, ARCH_CONVERT
, startblock
);
706 INT_SET(bt_key
->ar_blockcount
, ARCH_CONVERT
, blockcount
);
707 INT_SET(*bt_ptr
, ARCH_CONVERT
, btree_curs
->level
[level
-1].agbno
);
711 * rebuilds a freespace tree given a cursor and magic number of type
712 * of tree to build (bno or bcnt). returns the number of free blocks
713 * represented by the tree.
716 build_freespace_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
717 bt_status_t
*btree_curs
, __uint32_t magic
)
721 xfs_alloc_block_t
*bt_hdr
;
722 xfs_alloc_rec_t
*bt_rec
;
725 extent_tree_node_t
*ext_ptr
;
726 bt_stat_level_t
*lptr
;
727 xfs_extlen_t freeblks
;
729 #ifdef XR_BLD_FREE_TRACE
730 fprintf(stderr
, "in build_freespace_tree, agno = %d\n", agno
);
732 level
= btree_curs
->num_levels
;
738 * initialize the first block on each btree level
740 for (i
= 0; i
< level
; i
++) {
741 lptr
= &btree_curs
->level
[i
];
743 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
744 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
745 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
746 XFS_FSB_TO_BB(mp
, 1));
748 if (i
== btree_curs
->num_levels
- 1)
749 btree_curs
->root
= agbno
;
752 lptr
->prev_agbno
= NULLAGBLOCK
;
753 lptr
->prev_buf_p
= NULL
;
755 * initialize block header
757 bt_hdr
= XFS_BUF_TO_ALLOC_BLOCK(lptr
->buf_p
);
758 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
760 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, magic
);
761 INT_SET(bt_hdr
->bb_level
, ARCH_CONVERT
, i
);
762 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
,
763 bt_hdr
->bb_rightsib
= NULLAGBLOCK
);
764 INT_ZERO(bt_hdr
->bb_numrecs
, ARCH_CONVERT
);
767 * run along leaf, setting up records. as we have to switch
768 * blocks, call the prop_freespace_cursor routine to set up the new
769 * pointers for the parent. that can recurse up to the root
770 * if required. set the sibling pointers for leaf level here.
772 if (magic
== XFS_ABTB_MAGIC
)
773 ext_ptr
= findfirst_bno_extent(agno
);
775 ext_ptr
= findfirst_bcnt_extent(agno
);
777 #ifdef XR_BLD_FREE_TRACE
778 fprintf(stderr
, "bft, agno = %d, start = %u, count = %u\n",
779 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
782 lptr
= &btree_curs
->level
[0];
784 for (i
= 0; i
< btree_curs
->level
[0].num_blocks
; i
++) {
786 * block initialization, lay in block header
788 bt_hdr
= XFS_BUF_TO_ALLOC_BLOCK(lptr
->buf_p
);
789 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
791 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, magic
);
792 INT_ZERO(bt_hdr
->bb_level
, ARCH_CONVERT
);
793 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
, lptr
->prev_agbno
);
794 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
795 INT_SET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
,
796 lptr
->num_recs_pb
+ (lptr
->modulo
> 0));
797 #ifdef XR_BLD_FREE_TRACE
798 fprintf(stderr
, "bft, bb_numrecs = %d\n",
799 INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
));
802 if (lptr
->modulo
> 0)
806 * initialize values in the path up to the root if
807 * this is a multi-level btree
809 if (btree_curs
->num_levels
> 1)
810 prop_freespace_cursor(mp
, agno
, btree_curs
,
811 ext_ptr
->ex_startblock
,
812 ext_ptr
->ex_blockcount
,
815 bt_rec
= (xfs_alloc_rec_t
*) ((char *) bt_hdr
+
816 sizeof(xfs_alloc_block_t
));
817 for (j
= 0; j
< INT_GET(bt_hdr
->bb_numrecs
,ARCH_CONVERT
); j
++) {
818 ASSERT(ext_ptr
!= NULL
);
819 INT_SET(bt_rec
[j
].ar_startblock
, ARCH_CONVERT
,
820 ext_ptr
->ex_startblock
);
821 INT_SET(bt_rec
[j
].ar_blockcount
, ARCH_CONVERT
,
822 ext_ptr
->ex_blockcount
);
823 freeblks
+= ext_ptr
->ex_blockcount
;
824 if (magic
== XFS_ABTB_MAGIC
)
825 ext_ptr
= findnext_bno_extent(ext_ptr
);
827 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
829 #ifdef XR_BLD_FREE_TRACE
831 fprintf(stderr
, "null extent pointer, j = %d\n",
835 "bft, agno = %d, start = %u, count = %u\n",
836 agno
, ext_ptr
->ex_startblock
,
837 ext_ptr
->ex_blockcount
);
842 if (ext_ptr
!= NULL
) {
844 * get next leaf level block
846 if (lptr
->prev_buf_p
!= NULL
) {
847 #ifdef XR_BLD_FREE_TRACE
848 fprintf(stderr
, " writing fst agbno %u\n",
851 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
852 libxfs_writebuf(lptr
->prev_buf_p
, 0);
854 lptr
->prev_buf_p
= lptr
->buf_p
;
855 lptr
->prev_agbno
= lptr
->agbno
;
857 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, lptr
->agbno
=
858 get_next_blockaddr(agno
, 0, btree_curs
));
860 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
861 XFS_AGB_TO_DADDR(mp
, agno
, lptr
->agbno
),
862 XFS_FSB_TO_BB(mp
, 1));
870 * no-cursor versions of the XFS equivalents. The address calculators
871 * should be used only for interior btree nodes.
872 * these are adapted from xfs_ialloc_btree.h and xfs_tree.h
874 #define XR_INOBT_KEY_ADDR(mp, bp, i) \
875 (xfs_inobt_key_t *) ((char *) (bp) + sizeof(xfs_inobt_block_t) \
876 + ((i)-1) * sizeof(xfs_inobt_key_t))
878 #define XR_INOBT_PTR_ADDR(mp, bp, i) \
879 (xfs_inobt_ptr_t *) ((char *) (bp) + sizeof(xfs_inobt_block_t) \
880 + (mp)->m_inobt_mxr[1] * sizeof(xfs_inobt_key_t) \
881 + ((i)-1) * sizeof(xfs_inobt_ptr_t))
883 #define XR_INOBT_BLOCK_MAXRECS(mp, level) \
884 XFS_BTREE_BLOCK_MAXRECS((mp)->m_sb.sb_blocksize, \
885 xfs_inobt, (level) == 0)
888 * we don't have to worry here about how chewing up free extents
889 * may perturb things because inode tree building happens before
890 * freespace tree building.
893 init_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
894 __uint64_t
*num_inos
, __uint64_t
*num_free_inos
)
898 ino_tree_node_t
*ino_rec
;
901 bt_stat_level_t
*lptr
;
902 bt_stat_level_t
*p_lptr
;
903 xfs_extlen_t blocks_allocated
;
906 *num_inos
= *num_free_inos
= 0;
909 lptr
= &btree_curs
->level
[0];
910 btree_curs
->init
= 1;
912 if ((ino_rec
= findfirst_inode_rec(agno
)) == NULL
) {
914 * easy corner-case -- no inode records
916 lptr
->num_blocks
= 1;
918 lptr
->num_recs_pb
= 0;
919 lptr
->num_recs_tot
= 0;
921 btree_curs
->num_levels
= 1;
922 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
= 1;
924 setup_cursor(mp
, agno
, btree_curs
);
930 * build up statistics
932 for (num_recs
= 0; ino_rec
!= NULL
; ino_rec
= next_ino_rec(ino_rec
)) {
933 ninos
+= XFS_INODES_PER_CHUNK
;
935 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
936 ASSERT(is_inode_confirmed(ino_rec
, i
));
937 if (is_inode_free(ino_rec
, i
))
942 blocks_allocated
= lptr
->num_blocks
= howmany(num_recs
,
943 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
945 lptr
->modulo
= num_recs
% lptr
->num_blocks
;
946 lptr
->num_recs_pb
= num_recs
/ lptr
->num_blocks
;
947 lptr
->num_recs_tot
= num_recs
;
950 if (lptr
->num_blocks
> 1) {
951 for (; btree_curs
->level
[level
-1].num_blocks
> 1
952 && level
< XFS_BTREE_MAXLEVELS
;
954 lptr
= &btree_curs
->level
[level
];
955 p_lptr
= &btree_curs
->level
[level
- 1];
956 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
957 XR_INOBT_BLOCK_MAXRECS(mp
, level
));
958 lptr
->modulo
= p_lptr
->num_blocks
% lptr
->num_blocks
;
959 lptr
->num_recs_pb
= p_lptr
->num_blocks
961 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
963 blocks_allocated
+= lptr
->num_blocks
;
966 ASSERT(lptr
->num_blocks
== 1);
967 btree_curs
->num_levels
= level
;
969 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
972 setup_cursor(mp
, agno
, btree_curs
);
975 *num_free_inos
= nfinos
;
981 prop_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
982 xfs_agino_t startino
, int level
)
984 xfs_inobt_block_t
*bt_hdr
;
985 xfs_inobt_key_t
*bt_key
;
986 xfs_inobt_ptr_t
*bt_ptr
;
988 bt_stat_level_t
*lptr
;
992 if (level
>= btree_curs
->num_levels
)
995 lptr
= &btree_curs
->level
[level
];
996 bt_hdr
= XFS_BUF_TO_INOBT_BLOCK(lptr
->buf_p
);
998 if (INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
) == 0) {
1000 * this only happens once to initialize the
1001 * first path up the left side of the tree
1002 * where the agbno's are already set up
1004 prop_ino_cursor(mp
, agno
, btree_curs
, startino
, level
);
1007 if (INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
) ==
1008 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
1010 * write out current prev block, grab us a new block,
1011 * and set the rightsib pointer of current block
1013 #ifdef XR_BLD_INO_TRACE
1014 fprintf(stderr
, " ino prop agbno %d ", lptr
->prev_agbno
);
1016 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
1017 ASSERT(lptr
->prev_buf_p
!= NULL
);
1018 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1020 lptr
->prev_agbno
= lptr
->agbno
;;
1021 lptr
->prev_buf_p
= lptr
->buf_p
;
1022 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
1024 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, agbno
);
1026 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1027 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1028 XFS_FSB_TO_BB(mp
, 1));
1029 lptr
->agbno
= agbno
;
1035 * initialize block header
1037 bt_hdr
= XFS_BUF_TO_INOBT_BLOCK(lptr
->buf_p
);
1038 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
1040 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, XFS_IBT_MAGIC
);
1041 INT_SET(bt_hdr
->bb_level
, ARCH_CONVERT
, level
);
1042 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
, lptr
->prev_agbno
);
1043 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1044 INT_ZERO(bt_hdr
->bb_numrecs
, ARCH_CONVERT
);
1046 * propagate extent record for first extent in new block up
1048 prop_ino_cursor(mp
, agno
, btree_curs
, startino
, level
);
1051 * add inode info to current block
1053 INT_MOD(bt_hdr
->bb_numrecs
, ARCH_CONVERT
, +1);
1055 bt_key
= XR_INOBT_KEY_ADDR(mp
, bt_hdr
,
1056 INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
));
1057 bt_ptr
= XR_INOBT_PTR_ADDR(mp
, bt_hdr
,
1058 INT_GET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
));
1060 INT_SET(bt_key
->ir_startino
, ARCH_CONVERT
, startino
);
1061 INT_SET(*bt_ptr
, ARCH_CONVERT
, btree_curs
->level
[level
-1].agbno
);
1065 build_agi(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1066 bt_status_t
*btree_curs
, xfs_agino_t first_agino
,
1067 xfs_agino_t count
, xfs_agino_t freecount
)
1073 agi_buf
= libxfs_getbuf(mp
->m_dev
,
1074 XFS_AG_DADDR(mp
, agno
, XFS_AGI_DADDR(mp
)),
1075 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1076 agi
= XFS_BUF_TO_AGI(agi_buf
);
1077 bzero(agi
, mp
->m_sb
.sb_sectsize
);
1079 INT_SET(agi
->agi_magicnum
, ARCH_CONVERT
, XFS_AGI_MAGIC
);
1080 INT_SET(agi
->agi_versionnum
, ARCH_CONVERT
, XFS_AGI_VERSION
);
1081 INT_SET(agi
->agi_seqno
, ARCH_CONVERT
, agno
);
1082 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1083 INT_SET(agi
->agi_length
, ARCH_CONVERT
, mp
->m_sb
.sb_agblocks
);
1085 INT_SET(agi
->agi_length
, ARCH_CONVERT
, mp
->m_sb
.sb_dblocks
-
1086 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1087 INT_SET(agi
->agi_count
, ARCH_CONVERT
, count
);
1088 INT_SET(agi
->agi_root
, ARCH_CONVERT
, btree_curs
->root
);
1089 INT_SET(agi
->agi_level
, ARCH_CONVERT
, btree_curs
->num_levels
);
1090 INT_SET(agi
->agi_freecount
, ARCH_CONVERT
, freecount
);
1091 INT_SET(agi
->agi_newino
, ARCH_CONVERT
, first_agino
);
1092 INT_SET(agi
->agi_dirino
, ARCH_CONVERT
, NULLAGINO
);
1094 for (i
= 0; i
< XFS_AGI_UNLINKED_BUCKETS
; i
++) {
1095 INT_SET(agi
->agi_unlinked
[i
], ARCH_CONVERT
, NULLAGINO
);
1098 libxfs_writebuf(agi_buf
, 0);
1102 * rebuilds an inode tree given a cursor. We're lazy here and call
1103 * the routine that builds the agi
1106 build_ino_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1107 bt_status_t
*btree_curs
)
1111 xfs_agblock_t agbno
;
1112 xfs_agino_t first_agino
;
1113 xfs_inobt_block_t
*bt_hdr
;
1114 xfs_inobt_rec_t
*bt_rec
;
1115 ino_tree_node_t
*ino_rec
;
1116 bt_stat_level_t
*lptr
;
1117 xfs_agino_t count
= 0;
1118 xfs_agino_t freecount
= 0;
1121 int level
= btree_curs
->num_levels
;
1123 for (i
= 0; i
< level
; i
++) {
1124 lptr
= &btree_curs
->level
[i
];
1126 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
1127 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1128 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1129 XFS_FSB_TO_BB(mp
, 1));
1131 if (i
== btree_curs
->num_levels
- 1)
1132 btree_curs
->root
= agbno
;
1134 lptr
->agbno
= agbno
;
1135 lptr
->prev_agbno
= NULLAGBLOCK
;
1136 lptr
->prev_buf_p
= NULL
;
1138 * initialize block header
1140 bt_hdr
= XFS_BUF_TO_INOBT_BLOCK(lptr
->buf_p
);
1141 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
1143 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, XFS_IBT_MAGIC
);
1144 INT_SET(bt_hdr
->bb_level
, ARCH_CONVERT
, i
);
1145 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
,
1146 bt_hdr
->bb_rightsib
= NULLAGBLOCK
);
1147 INT_ZERO(bt_hdr
->bb_numrecs
, ARCH_CONVERT
);
1150 * run along leaf, setting up records. as we have to switch
1151 * blocks, call the prop_ino_cursor routine to set up the new
1152 * pointers for the parent. that can recurse up to the root
1153 * if required. set the sibling pointers for leaf level here.
1155 ino_rec
= findfirst_inode_rec(agno
);
1157 if (ino_rec
!= NULL
)
1158 first_agino
= ino_rec
->ino_startnum
;
1160 first_agino
= NULLAGINO
;
1162 lptr
= &btree_curs
->level
[0];
1164 for (i
= 0; i
< lptr
->num_blocks
; i
++) {
1166 * block initialization, lay in block header
1168 bt_hdr
= XFS_BUF_TO_INOBT_BLOCK(lptr
->buf_p
);
1169 bzero(bt_hdr
, mp
->m_sb
.sb_blocksize
);
1171 INT_SET(bt_hdr
->bb_magic
, ARCH_CONVERT
, XFS_IBT_MAGIC
);
1172 INT_ZERO(bt_hdr
->bb_level
, ARCH_CONVERT
);
1173 INT_SET(bt_hdr
->bb_leftsib
, ARCH_CONVERT
, lptr
->prev_agbno
);
1174 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, NULLAGBLOCK
);
1175 INT_SET(bt_hdr
->bb_numrecs
, ARCH_CONVERT
,
1176 lptr
->num_recs_pb
+ (lptr
->modulo
> 0));
1178 if (lptr
->modulo
> 0)
1181 if (lptr
->num_recs_pb
> 0)
1182 prop_ino_cursor(mp
, agno
, btree_curs
,
1183 ino_rec
->ino_startnum
, 0);
1185 bt_rec
= (xfs_inobt_rec_t
*) ((char *) bt_hdr
+
1186 sizeof(xfs_inobt_block_t
));
1187 for (j
= 0; j
< INT_GET(bt_hdr
->bb_numrecs
,ARCH_CONVERT
); j
++) {
1188 ASSERT(ino_rec
!= NULL
);
1189 INT_SET(bt_rec
[j
].ir_startino
, ARCH_CONVERT
,
1190 ino_rec
->ino_startnum
);
1191 INT_SET(bt_rec
[j
].ir_free
, ARCH_CONVERT
,
1195 for (k
= 0; k
< sizeof(xfs_inofree_t
)*NBBY
; k
++) {
1196 ASSERT(is_inode_confirmed(ino_rec
, k
));
1197 inocnt
+= is_inode_free(ino_rec
, k
);
1200 INT_SET(bt_rec
[j
].ir_freecount
, ARCH_CONVERT
, inocnt
);
1201 freecount
+= inocnt
;
1202 count
+= XFS_INODES_PER_CHUNK
;
1203 ino_rec
= next_ino_rec(ino_rec
);
1206 if (ino_rec
!= NULL
) {
1208 * get next leaf level block
1210 if (lptr
->prev_buf_p
!= NULL
) {
1211 #ifdef XR_BLD_INO_TRACE
1212 fprintf(stderr
, "writing inobt agbno %u\n",
1215 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
1216 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1218 lptr
->prev_buf_p
= lptr
->buf_p
;
1219 lptr
->prev_agbno
= lptr
->agbno
;
1221 INT_SET(bt_hdr
->bb_rightsib
, ARCH_CONVERT
, lptr
->agbno
=
1222 get_next_blockaddr(agno
, 0, btree_curs
));
1224 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1225 XFS_AGB_TO_DADDR(mp
, agno
, lptr
->agbno
),
1226 XFS_FSB_TO_BB(mp
, 1));
1230 build_agi(mp
, agno
, btree_curs
, first_agino
, count
, freecount
);
1234 * build both the agf and the agfl for an agno given both
1238 build_agf_agfl(xfs_mount_t
*mp
,
1239 xfs_agnumber_t agno
,
1240 bt_status_t
*bno_bt
,
1241 bt_status_t
*bcnt_bt
,
1242 xfs_extlen_t freeblks
, /* # free blocks in tree */
1243 int lostblocks
) /* # blocks that will be lost */
1245 extent_tree_node_t
*ext_ptr
;
1246 xfs_buf_t
*agf_buf
, *agfl_buf
;
1252 agf_buf
= libxfs_getbuf(mp
->m_dev
,
1253 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
1254 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1255 agf
= XFS_BUF_TO_AGF(agf_buf
);
1256 bzero(agf
, mp
->m_sb
.sb_sectsize
);
1258 #ifdef XR_BLD_FREE_TRACE
1259 fprintf(stderr
, "agf = 0x%x, agf_buf->b_un.b_addr = 0x%x\n",
1260 (__psint_t
) agf
, (__psint_t
) agf_buf
->b_un
.b_addr
);
1264 * set up fixed part of agf
1266 INT_SET(agf
->agf_magicnum
, ARCH_CONVERT
, XFS_AGF_MAGIC
);
1267 INT_SET(agf
->agf_versionnum
, ARCH_CONVERT
, XFS_AGF_VERSION
);
1268 INT_SET(agf
->agf_seqno
, ARCH_CONVERT
, agno
);
1270 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1271 INT_SET(agf
->agf_length
, ARCH_CONVERT
, mp
->m_sb
.sb_agblocks
);
1273 INT_SET(agf
->agf_length
, ARCH_CONVERT
, mp
->m_sb
.sb_dblocks
-
1274 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1276 INT_SET(agf
->agf_roots
[XFS_BTNUM_BNO
], ARCH_CONVERT
, bno_bt
->root
);
1277 INT_SET(agf
->agf_levels
[XFS_BTNUM_BNO
], ARCH_CONVERT
,
1278 bno_bt
->num_levels
);
1279 INT_SET(agf
->agf_roots
[XFS_BTNUM_CNT
], ARCH_CONVERT
, bcnt_bt
->root
);
1280 INT_SET(agf
->agf_levels
[XFS_BTNUM_CNT
], ARCH_CONVERT
,
1281 bcnt_bt
->num_levels
);
1282 INT_SET(agf
->agf_freeblks
, ARCH_CONVERT
, freeblks
);
1284 #ifdef XR_BLD_FREE_TRACE
1285 fprintf(stderr
, "bno root = %u, bcnt root = %u, indices = %u %u\n",
1286 INT_GET(agf
->agf_roots
[XFS_BTNUM_BNO
], ARCH_CONVERT
),
1287 INT_GET(agf
->agf_roots
[XFS_BTNUM_CNT
], ARCH_CONVERT
),
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 bzero(agfl
, 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 INT_SET(agfl
->agfl_bno
[i
], ARCH_CONVERT
,
1311 get_next_blockaddr(agno
, 0, bno_bt
));
1315 while (bcnt_bt
->num_free_blocks
> 0 && i
< XFS_AGFL_SIZE(mp
)) {
1316 INT_SET(agfl
->agfl_bno
[i
], ARCH_CONVERT
,
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 INT_ZERO(agf
->agf_flfirst
, ARCH_CONVERT
);
1344 INT_SET(agf
->agf_fllast
, ARCH_CONVERT
, i
- 1);
1345 INT_SET(agf
->agf_flcount
, ARCH_CONVERT
, i
);
1347 #ifdef XR_BLD_FREE_TRACE
1348 fprintf(stderr
, "writing agfl for ag %u\n", agno
);
1351 libxfs_writebuf(agfl_buf
, 0);
1353 INT_ZERO(agf
->agf_flfirst
, ARCH_CONVERT
);
1354 INT_SET(agf
->agf_fllast
, ARCH_CONVERT
, XFS_AGFL_SIZE(mp
) - 1);
1355 INT_ZERO(agf
->agf_flcount
, ARCH_CONVERT
);
1358 ext_ptr
= findbiggest_bcnt_extent(agno
);
1359 INT_SET(agf
->agf_longest
, ARCH_CONVERT
,
1360 (ext_ptr
!= NULL
) ? ext_ptr
->ex_blockcount
: 0);
1362 ASSERT(INT_GET(agf
->agf_roots
[XFS_BTNUM_BNOi
], ARCH_CONVERT
) !=
1363 INT_GET(agf
->agf_roots
[XFS_BTNUM_CNTi
], ARCH_CONVERT
));
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
)
1383 bp
= libxfs_getsb(mp
, 0);
1385 do_error(_("couldn't get superblock\n"));
1387 sbp
= XFS_BUF_TO_SBP(bp
);
1389 mp
->m_sb
.sb_icount
= sb_icount
;
1390 mp
->m_sb
.sb_ifree
= sb_ifree
;
1391 mp
->m_sb
.sb_fdblocks
= sb_fdblocks
;
1392 mp
->m_sb
.sb_frextents
= sb_frextents
;
1394 update_sb_version(mp
);
1397 libxfs_xlate_sb(XFS_BUF_PTR(bp
), sbp
, -1, ARCH_CONVERT
,
1399 libxfs_writebuf(bp
, 0);
1403 * make sure the root and realtime inodes show up allocated
1404 * even if they've been freed. they get reinitialized in phase6.
1407 keep_fsinos(xfs_mount_t
*mp
)
1409 ino_tree_node_t
*irec
;
1412 irec
= find_inode_rec(XFS_INO_TO_AGNO(mp
, mp
->m_sb
.sb_rootino
),
1413 XFS_INO_TO_AGINO(mp
, mp
->m_sb
.sb_rootino
));
1415 for (i
= 0; i
< 3; i
++)
1416 set_inode_used(irec
, i
);
1420 phase5(xfs_mount_t
*mp
)
1422 __uint64_t num_inos
;
1423 __uint64_t num_free_inos
;
1424 bt_status_t bno_btree_curs
;
1425 bt_status_t bcnt_btree_curs
;
1426 bt_status_t ino_btree_curs
;
1427 xfs_agnumber_t agno
;
1428 int extra_blocks
= 0;
1429 uint num_freeblocks
;
1430 xfs_extlen_t freeblks1
;
1431 xfs_extlen_t freeblks2
;
1432 xfs_agblock_t num_extents
;
1433 extern int count_bno_extents(xfs_agnumber_t
);
1434 extern int count_bno_extents_blocks(xfs_agnumber_t
, uint
*);
1435 #ifdef XR_BLD_FREE_TRACE
1436 extern int count_bcnt_extents(xfs_agnumber_t
);
1439 do_log(_("Phase 5 - rebuild AG headers and trees...\n"));
1441 #ifdef XR_BLD_FREE_TRACE
1442 fprintf(stderr
, "inobt level 1, maxrec = %d, minrec = %d\n",
1443 XFS_BTREE_BLOCK_MAXRECS(mp
->m_sb
.sb_blocksize
, xfs_inobt
, 0),
1444 XFS_BTREE_BLOCK_MINRECS(mp
->m_sb
.sb_blocksize
, xfs_inobt
, 0)
1446 fprintf(stderr
, "inobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1447 XFS_BTREE_BLOCK_MAXRECS(mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1),
1448 XFS_BTREE_BLOCK_MINRECS(mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1)
1450 fprintf(stderr
, "xr inobt level 0 (leaf), maxrec = %d\n",
1451 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
1452 fprintf(stderr
, "xr inobt level 1 (int), maxrec = %d\n",
1453 XR_INOBT_BLOCK_MAXRECS(mp
, 1));
1454 fprintf(stderr
, "bnobt level 1, maxrec = %d, minrec = %d\n",
1455 XFS_BTREE_BLOCK_MAXRECS(mp
->m_sb
.sb_blocksize
, xfs_alloc
, 0),
1456 XFS_BTREE_BLOCK_MINRECS(mp
->m_sb
.sb_blocksize
, xfs_alloc
, 0));
1457 fprintf(stderr
, "bnobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1458 XFS_BTREE_BLOCK_MAXRECS(mp
->m_sb
.sb_blocksize
, xfs_alloc
, 1),
1459 XFS_BTREE_BLOCK_MINRECS(mp
->m_sb
.sb_blocksize
, xfs_alloc
, 1));
1463 * make sure the root and realtime inodes show up allocated
1467 for (agno
= 0; agno
< mp
->m_sb
.sb_agcount
; agno
++) {
1469 * build up incore bno and bcnt extent btrees
1471 num_extents
= mk_incore_fstree(mp
, agno
);
1473 #ifdef XR_BLD_FREE_TRACE
1474 fprintf(stderr
, "# of bno extents is %d\n",
1475 count_bno_extents(agno
));
1478 if (num_extents
== 0) {
1480 * XXX - what we probably should do here is pick an
1481 * inode for a regular file in the allocation group
1482 * that has space allocated and shoot it by traversing
1483 * the bmap list and putting all its extents on the
1484 * incore freespace trees, clearing the inode,
1485 * and clearing the in-use bit in the incore inode
1486 * tree. Then try mk_incore_fstree() again.
1488 do_error(_("unable to rebuild AG %u. "
1489 "Not enough free space in on-disk AG.\n"),
1494 * done with the AG bitmap, toss it...
1496 teardown_ag_bmap(mp
, agno
);
1499 * ok, now set up the btree cursors for the
1500 * on-disk btrees (includs pre-allocating all
1501 * required blocks for the trees themselves)
1503 init_ino_cursor(mp
, agno
, &ino_btree_curs
,
1504 &num_inos
, &num_free_inos
);
1506 sb_icount
+= num_inos
;
1507 sb_ifree
+= num_free_inos
;
1509 num_extents
= count_bno_extents_blocks(agno
, &num_freeblocks
);
1511 * lose two blocks per AG -- the space tree roots
1512 * are counted as allocated since the space trees
1515 sb_fdblocks
+= num_freeblocks
- 2;
1517 if (num_extents
== 0) {
1519 * XXX - what we probably should do here is pick an
1520 * inode for a regular file in the allocation group
1521 * that has space allocated and shoot it by traversing
1522 * the bmap list and putting all its extents on the
1523 * incore freespace trees, clearing the inode,
1524 * and clearing the in-use bit in the incore inode
1525 * tree. Then try mk_incore_fstree() again.
1528 _("unable to rebuild AG %u. No free space.\n"), agno
);
1531 #ifdef XR_BLD_FREE_TRACE
1532 fprintf(stderr
, "# of bno extents is %d\n", num_extents
);
1536 * track blocks that we might really lose
1538 extra_blocks
= calculate_freespace_cursor(mp
, agno
,
1539 &num_extents
, &bno_btree_curs
);
1542 * freespace btrees live in the "free space" but
1543 * the filesystem treats AGFL blocks as allocated
1544 * since they aren't described by the freespace trees
1548 * see if we can fit all the extra blocks into the AGFL
1550 extra_blocks
= (extra_blocks
- XFS_AGFL_SIZE(mp
) > 0)
1551 ? extra_blocks
- XFS_AGFL_SIZE(mp
)
1554 if (extra_blocks
> 0) {
1555 do_warn(_("lost %d blocks in agno %d, sorry.\n"),
1556 extra_blocks
, agno
);
1557 sb_fdblocks
-= extra_blocks
;
1560 bcnt_btree_curs
= bno_btree_curs
;
1562 setup_cursor(mp
, agno
, &bno_btree_curs
);
1563 setup_cursor(mp
, agno
, &bcnt_btree_curs
);
1565 #ifdef XR_BLD_FREE_TRACE
1566 fprintf(stderr
, "# of bno extents is %d\n",
1567 count_bno_extents(agno
));
1568 fprintf(stderr
, "# of bcnt extents is %d\n",
1569 count_bcnt_extents(agno
));
1572 * now rebuild the freespace trees
1574 freeblks1
= build_freespace_tree(mp
, agno
, &bno_btree_curs
,
1576 #ifdef XR_BLD_FREE_TRACE
1577 fprintf(stderr
, "# of free blocks == %d\n", freeblks1
);
1579 write_cursor(&bno_btree_curs
);
1581 freeblks2
= build_freespace_tree(mp
, agno
, &bcnt_btree_curs
,
1583 write_cursor(&bcnt_btree_curs
);
1585 ASSERT(freeblks1
== freeblks2
);
1588 * set up agf and agfl
1590 build_agf_agfl(mp
, agno
, &bno_btree_curs
,
1591 &bcnt_btree_curs
, freeblks1
, extra_blocks
);
1593 * build inode allocation tree. this also build the agi
1595 build_ino_tree(mp
, agno
, &ino_btree_curs
);
1596 write_cursor(&ino_btree_curs
);
1600 finish_cursor(&bno_btree_curs
);
1601 finish_cursor(&ino_btree_curs
);
1602 finish_cursor(&bcnt_btree_curs
);
1604 * release the incore per-AG bno/bcnt trees so
1605 * the extent nodes can be recycled
1607 release_agbno_extent_tree(agno
);
1608 release_agbcnt_extent_tree(agno
);
1611 if (mp
->m_sb
.sb_rblocks
) {
1613 _(" - generate realtime summary info and bitmap...\n"));
1615 generate_rtinfo(mp
, btmcompute
, sumcompute
);
1616 teardown_rt_bmap(mp
);
1619 do_log(_(" - reset superblock...\n"));
1622 * sync superblock counter and set version bits correctly