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
;
95 * scan the bitmap for the ag looking for continuous
96 * extents of free blocks. At this point, we know
97 * that blocks in the bitmap are either set to an
98 * "in use" state or set to unknown (0) since the
99 * bmaps were zero'ed in phase 4 and only blocks
100 * being used by inodes, inode bmaps, ag headers,
101 * and the files themselves were put into the bitmap.
104 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
106 extent_start
= extent_len
= 0;
108 num_extents
= free_blocks
= 0;
110 if (agno
< mp
->m_sb
.sb_agcount
- 1)
111 ag_end
= mp
->m_sb
.sb_agblocks
;
113 ag_end
= mp
->m_sb
.sb_dblocks
-
114 (xfs_drfsbno_t
)mp
->m_sb
.sb_agblocks
*
115 (mp
->m_sb
.sb_agcount
- 1);
118 * ok, now find the number of extents, keep track of the
121 for (agbno
= 0; agbno
< ag_end
; agbno
+= blen
) {
122 bstate
= get_bmap_ext(agno
, agbno
, ag_end
, &blen
);
123 if (bstate
< XR_E_INUSE
) {
125 if (in_extent
== 0) {
127 * found the start of a free extent
131 extent_start
= agbno
;
139 * free extent ends here, add extent to the
140 * 2 incore extent (avl-to-be-B+) trees
143 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
144 fprintf(stderr
, "adding extent %u [%u %u]\n",
145 agno
, extent_start
, extent_len
);
147 add_bno_extent(agno
, extent_start
, extent_len
);
148 add_bcnt_extent(agno
, extent_start
, extent_len
);
154 * free extent ends here
157 #if defined(XR_BLD_FREE_TRACE) && defined(XR_BLD_ADD_EXTENT)
158 fprintf(stderr
, "adding extent %u [%u %u]\n",
159 agno
, extent_start
, extent_len
);
161 add_bno_extent(agno
, extent_start
, extent_len
);
162 add_bcnt_extent(agno
, extent_start
, extent_len
);
169 get_next_blockaddr(xfs_agnumber_t agno
, int level
, bt_status_t
*curs
)
171 ASSERT(curs
->free_btree_blocks
< curs
->btree_blocks
+
172 curs
->num_tot_blocks
);
173 ASSERT(curs
->num_free_blocks
> 0);
175 curs
->num_free_blocks
--;
176 return(*curs
->free_btree_blocks
++);
180 * set up the dynamically allocated block allocation data in the btree
181 * cursor that depends on the info in the static portion of the cursor.
182 * allocates space from the incore bno/bcnt extent trees and sets up
183 * the first path up the left side of the tree. Also sets up the
184 * cursor pointer to the btree root. called by init_freespace_cursor()
185 * and init_ino_cursor()
188 setup_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*curs
)
192 xfs_extlen_t big_extent_len
;
193 xfs_agblock_t big_extent_start
;
194 extent_tree_node_t
*ext_ptr
;
195 extent_tree_node_t
*bno_ext_ptr
;
196 xfs_extlen_t blocks_allocated
;
197 xfs_agblock_t
*agb_ptr
;
200 * get the number of blocks we need to allocate, then
201 * set up block number array, set the free block pointer
202 * to the first block in the array, and null the array
204 big_extent_len
= curs
->num_tot_blocks
;
205 blocks_allocated
= 0;
207 ASSERT(big_extent_len
> 0);
209 if ((curs
->btree_blocks
= malloc(sizeof(xfs_agblock_t
)
210 * big_extent_len
)) == NULL
)
211 do_error(_("could not set up btree block array\n"));
213 agb_ptr
= curs
->free_btree_blocks
= curs
->btree_blocks
;
215 for (j
= 0; j
< curs
->num_free_blocks
; j
++, agb_ptr
++)
216 *agb_ptr
= NULLAGBLOCK
;
219 * grab the smallest extent and use it up, then get the
220 * next smallest. This mimics the init_*_cursor code.
222 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
223 do_error(_("error - not enough free space in filesystem\n"));
225 agb_ptr
= curs
->btree_blocks
;
226 j
= curs
->level
[0].num_blocks
;
229 * set up the free block array
231 while (blocks_allocated
< big_extent_len
) {
233 * use up the extent we've got
235 for (u
= 0; u
< ext_ptr
->ex_blockcount
&&
236 blocks_allocated
< big_extent_len
; u
++) {
237 ASSERT(agb_ptr
< curs
->btree_blocks
238 + curs
->num_tot_blocks
);
239 *agb_ptr
++ = ext_ptr
->ex_startblock
+ u
;
244 * if we only used part of this last extent, then we
245 * need only to reset the extent in the extent
246 * trees and we're done
248 if (u
< ext_ptr
->ex_blockcount
) {
249 big_extent_start
= ext_ptr
->ex_startblock
+ u
;
250 big_extent_len
= ext_ptr
->ex_blockcount
- u
;
252 ASSERT(big_extent_len
> 0);
254 bno_ext_ptr
= find_bno_extent(agno
,
255 ext_ptr
->ex_startblock
);
256 ASSERT(bno_ext_ptr
!= NULL
);
257 get_bno_extent(agno
, bno_ext_ptr
);
258 release_extent_tree_node(bno_ext_ptr
);
260 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
261 ext_ptr
->ex_blockcount
);
262 release_extent_tree_node(ext_ptr
);
263 #ifdef XR_BLD_FREE_TRACE
264 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
265 agno
, ext_ptr
->ex_startblock
,
266 ext_ptr
->ex_blockcount
);
267 fprintf(stderr
, "blocks_allocated = %d\n",
271 add_bno_extent(agno
, big_extent_start
, big_extent_len
);
272 add_bcnt_extent(agno
, big_extent_start
, big_extent_len
);
277 * delete the used-up extent from both extent trees and
278 * find next biggest extent
280 #ifdef XR_BLD_FREE_TRACE
281 fprintf(stderr
, "releasing extent: %u [%u %u]\n",
282 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
284 bno_ext_ptr
= find_bno_extent(agno
, ext_ptr
->ex_startblock
);
285 ASSERT(bno_ext_ptr
!= NULL
);
286 get_bno_extent(agno
, bno_ext_ptr
);
287 release_extent_tree_node(bno_ext_ptr
);
289 ext_ptr
= get_bcnt_extent(agno
, ext_ptr
->ex_startblock
,
290 ext_ptr
->ex_blockcount
);
291 ASSERT(ext_ptr
!= NULL
);
292 release_extent_tree_node(ext_ptr
);
294 ext_ptr
= findfirst_bcnt_extent(agno
);
296 #ifdef XR_BLD_FREE_TRACE
297 fprintf(stderr
, "blocks_allocated = %d\n",
303 write_cursor(bt_status_t
*curs
)
307 for (i
= 0; i
< curs
->num_levels
; i
++) {
308 #if defined(XR_BLD_FREE_TRACE) || defined(XR_BLD_INO_TRACE)
309 fprintf(stderr
, "writing bt block %u\n", curs
->level
[i
].agbno
);
311 if (curs
->level
[i
].prev_buf_p
!= NULL
) {
312 ASSERT(curs
->level
[i
].prev_agbno
!= NULLAGBLOCK
);
313 #if defined(XR_BLD_FREE_TRACE) || defined(XR_BLD_INO_TRACE)
314 fprintf(stderr
, "writing bt prev block %u\n",
315 curs
->level
[i
].prev_agbno
);
317 libxfs_writebuf(curs
->level
[i
].prev_buf_p
, 0);
319 libxfs_writebuf(curs
->level
[i
].buf_p
, 0);
324 finish_cursor(bt_status_t
*curs
)
326 ASSERT(curs
->num_free_blocks
== 0);
327 free(curs
->btree_blocks
);
331 * XXX(hch): any reason we don't just look at mp->m_alloc_mxr?
333 #define XR_ALLOC_BLOCK_MAXRECS(mp, level) \
334 xfs_allocbt_maxrecs((mp), (mp)->m_sb.sb_blocksize, \
338 * this calculates a freespace cursor for an ag.
339 * btree_curs is an in/out. returns the number of
340 * blocks that will show up in the AGFL.
343 calculate_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
344 xfs_agblock_t
*extents
, bt_status_t
*btree_curs
)
346 xfs_extlen_t blocks_needed
; /* a running count */
347 xfs_extlen_t blocks_allocated_pt
; /* per tree */
348 xfs_extlen_t blocks_allocated_total
; /* for both trees */
349 xfs_agblock_t num_extents
;
353 bt_stat_level_t
*lptr
;
354 bt_stat_level_t
*p_lptr
;
355 extent_tree_node_t
*ext_ptr
;
357 #ifdef XR_BLD_FREE_TRACE
359 int state
= XR_E_BAD_STATE
;
361 #ifdef XR_BLD_FREE_TRACE
363 "in init_freespace_cursor, agno = %d\n", agno
);
366 num_extents
= *extents
;
369 ASSERT(num_extents
!= 0);
371 lptr
= &btree_curs
->level
[0];
372 btree_curs
->init
= 1;
375 * figure out how much space we need for the leaf level
376 * of the tree and set up the cursor for the leaf level
377 * (note that the same code is duplicated further down)
379 lptr
->num_blocks
= howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
380 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
381 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
382 lptr
->num_recs_tot
= num_extents
;
386 * if we need more levels, set them up. # of records
387 * per level is the # of blocks in the level below it
389 if (lptr
->num_blocks
> 1) {
390 for (; btree_curs
->level
[level
- 1].num_blocks
> 1
391 && level
< XFS_BTREE_MAXLEVELS
;
393 lptr
= &btree_curs
->level
[level
];
394 p_lptr
= &btree_curs
->level
[level
- 1];
395 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
396 XR_ALLOC_BLOCK_MAXRECS(mp
, level
));
397 lptr
->modulo
= p_lptr
->num_blocks
399 lptr
->num_recs_pb
= p_lptr
->num_blocks
401 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
405 ASSERT(lptr
->num_blocks
== 1);
406 btree_curs
->num_levels
= level
;
409 * ok, now we have a hypothetical cursor that
410 * will work for both the bno and bcnt trees.
411 * now figure out if using up blocks to set up the
412 * trees will perturb the shape of the freespace tree.
413 * if so, we've over-allocated. the freespace trees
414 * as they will be *after* accounting for the free space
415 * we've used up will need fewer blocks to to represent
416 * than we've allocated. We can use the AGFL to hold
417 * XFS_AGFL_SIZE (sector/xfs_agfl_t) blocks but that's it.
418 * Thus we limit things to XFS_AGFL_SIZE/2 for each of the 2 btrees.
419 * if the number of extra blocks is more than that,
420 * we'll have to be called again.
422 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
423 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
427 * record the # of blocks we've allocated
429 blocks_allocated_pt
= blocks_needed
;
431 blocks_allocated_total
= blocks_needed
;
434 * figure out how many free extents will be used up by
435 * our space allocation
437 if ((ext_ptr
= findfirst_bcnt_extent(agno
)) == NULL
)
438 do_error(_("can't rebuild fs trees -- not enough free space "
439 "on ag %u\n"), agno
);
442 while (ext_ptr
!= NULL
&& blocks_needed
> 0) {
443 if (ext_ptr
->ex_blockcount
<= blocks_needed
) {
444 blocks_needed
-= ext_ptr
->ex_blockcount
;
450 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
452 #ifdef XR_BLD_FREE_TRACE
453 if (ext_ptr
!= NULL
) {
454 fprintf(stderr
, "got next extent [%u %u]\n",
455 ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
457 fprintf(stderr
, "out of extents\n");
461 if (blocks_needed
> 0)
462 do_error(_("ag %u - not enough free space to build freespace "
465 ASSERT(num_extents
>= extents_used
);
467 num_extents
-= extents_used
;
470 * see if the number of leaf blocks will change as a result
471 * of the number of extents changing
473 if (howmany(num_extents
, XR_ALLOC_BLOCK_MAXRECS(mp
, 0))
474 != btree_curs
->level
[0].num_blocks
) {
476 * yes -- recalculate the cursor. If the number of
477 * excess (overallocated) blocks is < XFS_AGFL_SIZE/2, we're ok.
478 * we can put those into the AGFL. we don't try
479 * and get things to converge exactly (reach a
480 * state with zero excess blocks) because there
481 * exist pathological cases which will never
482 * converge. first, check for the zero-case.
484 if (num_extents
== 0) {
486 * ok, we've used up all the free blocks
487 * trying to lay out the leaf level. go
488 * to a one block (empty) btree and put the
489 * already allocated blocks into the AGFL
491 if (btree_curs
->level
[0].num_blocks
!= 1) {
493 * we really needed more blocks because
494 * the old tree had more than one level.
497 do_warn(_("not enough free blocks left to "
498 "describe all free blocks in AG "
501 #ifdef XR_BLD_FREE_TRACE
503 "ag %u -- no free extents, alloc'ed %d\n",
504 agno
, blocks_allocated_pt
);
506 lptr
->num_blocks
= 1;
508 lptr
->num_recs_pb
= 0;
509 lptr
->num_recs_tot
= 0;
511 btree_curs
->num_levels
= 1;
514 * don't reset the allocation stats, assume
515 * they're all extra blocks
516 * don't forget to return the total block count
517 * not the per-tree block count. these are the
518 * extras that will go into the AGFL. subtract
519 * two for the root blocks.
521 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
522 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
526 return(blocks_allocated_total
- 2);
529 lptr
= &btree_curs
->level
[0];
530 lptr
->num_blocks
= howmany(num_extents
,
531 XR_ALLOC_BLOCK_MAXRECS(mp
, 0));
532 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
533 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
534 lptr
->num_recs_tot
= num_extents
;
538 * if we need more levels, set them up
540 if (lptr
->num_blocks
> 1) {
541 for (level
= 1; btree_curs
->level
[level
-1].num_blocks
542 > 1 && level
< XFS_BTREE_MAXLEVELS
;
544 lptr
= &btree_curs
->level
[level
];
545 p_lptr
= &btree_curs
->level
[level
-1];
546 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
547 XR_ALLOC_BLOCK_MAXRECS(mp
,
549 lptr
->modulo
= p_lptr
->num_blocks
551 lptr
->num_recs_pb
= p_lptr
->num_blocks
553 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
556 ASSERT(lptr
->num_blocks
== 1);
557 btree_curs
->num_levels
= level
;
560 * now figure out the number of excess blocks
562 for (blocks_needed
= 0, i
= 0; i
< level
; i
++) {
563 blocks_needed
+= btree_curs
->level
[i
].num_blocks
;
567 ASSERT(blocks_allocated_total
>= blocks_needed
);
568 extra_blocks
= blocks_allocated_total
- blocks_needed
;
570 if (extents_used
> 0) {
572 * reset the leaf level geometry to account
573 * for consumed extents. we can leave the
574 * rest of the cursor alone since the number
575 * of leaf blocks hasn't changed.
577 lptr
= &btree_curs
->level
[0];
579 lptr
->num_recs_pb
= num_extents
/ lptr
->num_blocks
;
580 lptr
->modulo
= num_extents
% lptr
->num_blocks
;
581 lptr
->num_recs_tot
= num_extents
;
587 btree_curs
->num_tot_blocks
= blocks_allocated_pt
;
588 btree_curs
->num_free_blocks
= blocks_allocated_pt
;
590 *extents
= num_extents
;
592 return(extra_blocks
);
596 prop_freespace_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
597 bt_status_t
*btree_curs
, xfs_agblock_t startblock
,
598 xfs_extlen_t blockcount
, int level
, __uint32_t magic
)
600 struct xfs_btree_block
*bt_hdr
;
601 xfs_alloc_key_t
*bt_key
;
602 xfs_alloc_ptr_t
*bt_ptr
;
604 bt_stat_level_t
*lptr
;
605 __uint32_t crc_magic
;
607 if (magic
== XFS_ABTB_MAGIC
)
608 crc_magic
= XFS_ABTB_CRC_MAGIC
;
610 crc_magic
= XFS_ABTC_CRC_MAGIC
;
614 if (level
>= btree_curs
->num_levels
)
617 lptr
= &btree_curs
->level
[level
];
618 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
620 if (be16_to_cpu(bt_hdr
->bb_numrecs
) == 0) {
622 * only happens once when initializing the
623 * left-hand side of the tree.
625 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
626 blockcount
, level
, magic
);
629 if (be16_to_cpu(bt_hdr
->bb_numrecs
) ==
630 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
632 * write out current prev block, grab us a new block,
633 * and set the rightsib pointer of current block
635 #ifdef XR_BLD_FREE_TRACE
636 fprintf(stderr
, " %d ", lptr
->prev_agbno
);
638 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
639 ASSERT(lptr
->prev_buf_p
!= NULL
);
640 libxfs_writebuf(lptr
->prev_buf_p
, 0);
642 lptr
->prev_agbno
= lptr
->agbno
;;
643 lptr
->prev_buf_p
= lptr
->buf_p
;
644 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
646 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(agbno
);
648 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
649 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
650 XFS_FSB_TO_BB(mp
, 1));
657 * initialize block header
659 lptr
->buf_p
->b_ops
= &xfs_allocbt_buf_ops
;
660 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
661 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
662 if (xfs_sb_version_hascrc(&mp
->m_sb
))
663 xfs_btree_init_block(mp
, lptr
->buf_p
, crc_magic
, level
,
664 0, agno
, XFS_BTREE_CRC_BLOCKS
);
666 xfs_btree_init_block(mp
, lptr
->buf_p
, magic
, level
,
669 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
672 * propagate extent record for first extent in new block up
674 prop_freespace_cursor(mp
, agno
, btree_curs
, startblock
,
675 blockcount
, level
, magic
);
678 * add extent info to current block
680 be16_add_cpu(&bt_hdr
->bb_numrecs
, 1);
682 bt_key
= XFS_ALLOC_KEY_ADDR(mp
, bt_hdr
,
683 be16_to_cpu(bt_hdr
->bb_numrecs
));
684 bt_ptr
= XFS_ALLOC_PTR_ADDR(mp
, bt_hdr
,
685 be16_to_cpu(bt_hdr
->bb_numrecs
),
688 bt_key
->ar_startblock
= cpu_to_be32(startblock
);
689 bt_key
->ar_blockcount
= cpu_to_be32(blockcount
);
690 *bt_ptr
= cpu_to_be32(btree_curs
->level
[level
-1].agbno
);
694 * rebuilds a freespace tree given a cursor and magic number of type
695 * of tree to build (bno or bcnt). returns the number of free blocks
696 * represented by the tree.
699 build_freespace_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
700 bt_status_t
*btree_curs
, __uint32_t magic
)
704 struct xfs_btree_block
*bt_hdr
;
705 xfs_alloc_rec_t
*bt_rec
;
708 extent_tree_node_t
*ext_ptr
;
709 bt_stat_level_t
*lptr
;
710 xfs_extlen_t freeblks
;
711 __uint32_t crc_magic
;
713 #ifdef XR_BLD_FREE_TRACE
714 fprintf(stderr
, "in build_freespace_tree, agno = %d\n", agno
);
716 level
= btree_curs
->num_levels
;
720 if (magic
== XFS_ABTB_MAGIC
)
721 crc_magic
= XFS_ABTB_CRC_MAGIC
;
723 crc_magic
= XFS_ABTC_CRC_MAGIC
;
726 * initialize the first block on each btree level
728 for (i
= 0; i
< level
; i
++) {
729 lptr
= &btree_curs
->level
[i
];
731 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
732 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
733 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
734 XFS_FSB_TO_BB(mp
, 1));
736 if (i
== btree_curs
->num_levels
- 1)
737 btree_curs
->root
= agbno
;
740 lptr
->prev_agbno
= NULLAGBLOCK
;
741 lptr
->prev_buf_p
= NULL
;
743 * initialize block header
745 lptr
->buf_p
->b_ops
= &xfs_allocbt_buf_ops
;
746 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
747 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
748 if (xfs_sb_version_hascrc(&mp
->m_sb
))
749 xfs_btree_init_block(mp
, lptr
->buf_p
, crc_magic
, i
,
750 0, agno
, XFS_BTREE_CRC_BLOCKS
);
752 xfs_btree_init_block(mp
, lptr
->buf_p
, magic
, i
,
756 * run along leaf, setting up records. as we have to switch
757 * blocks, call the prop_freespace_cursor routine to set up the new
758 * pointers for the parent. that can recurse up to the root
759 * if required. set the sibling pointers for leaf level here.
761 if (magic
== XFS_ABTB_MAGIC
)
762 ext_ptr
= findfirst_bno_extent(agno
);
764 ext_ptr
= findfirst_bcnt_extent(agno
);
766 #ifdef XR_BLD_FREE_TRACE
767 fprintf(stderr
, "bft, agno = %d, start = %u, count = %u\n",
768 agno
, ext_ptr
->ex_startblock
, ext_ptr
->ex_blockcount
);
771 lptr
= &btree_curs
->level
[0];
773 for (i
= 0; i
< btree_curs
->level
[0].num_blocks
; i
++) {
775 * block initialization, lay in block header
777 lptr
->buf_p
->b_ops
= &xfs_allocbt_buf_ops
;
778 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
779 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
780 if (xfs_sb_version_hascrc(&mp
->m_sb
))
781 xfs_btree_init_block(mp
, lptr
->buf_p
, crc_magic
, 0,
782 0, agno
, XFS_BTREE_CRC_BLOCKS
);
784 xfs_btree_init_block(mp
, lptr
->buf_p
, magic
, 0,
787 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
788 bt_hdr
->bb_numrecs
= cpu_to_be16(lptr
->num_recs_pb
+
790 #ifdef XR_BLD_FREE_TRACE
791 fprintf(stderr
, "bft, bb_numrecs = %d\n",
792 be16_to_cpu(bt_hdr
->bb_numrecs
));
795 if (lptr
->modulo
> 0)
799 * initialize values in the path up to the root if
800 * this is a multi-level btree
802 if (btree_curs
->num_levels
> 1)
803 prop_freespace_cursor(mp
, agno
, btree_curs
,
804 ext_ptr
->ex_startblock
,
805 ext_ptr
->ex_blockcount
,
808 bt_rec
= (xfs_alloc_rec_t
*)
809 ((char *)bt_hdr
+ XFS_ALLOC_BLOCK_LEN(mp
));
810 for (j
= 0; j
< be16_to_cpu(bt_hdr
->bb_numrecs
); j
++) {
811 ASSERT(ext_ptr
!= NULL
);
812 bt_rec
[j
].ar_startblock
= cpu_to_be32(
813 ext_ptr
->ex_startblock
);
814 bt_rec
[j
].ar_blockcount
= cpu_to_be32(
815 ext_ptr
->ex_blockcount
);
816 freeblks
+= ext_ptr
->ex_blockcount
;
817 if (magic
== XFS_ABTB_MAGIC
)
818 ext_ptr
= findnext_bno_extent(ext_ptr
);
820 ext_ptr
= findnext_bcnt_extent(agno
, ext_ptr
);
822 #ifdef XR_BLD_FREE_TRACE
824 fprintf(stderr
, "null extent pointer, j = %d\n",
828 "bft, agno = %d, start = %u, count = %u\n",
829 agno
, ext_ptr
->ex_startblock
,
830 ext_ptr
->ex_blockcount
);
835 if (ext_ptr
!= NULL
) {
837 * get next leaf level block
839 if (lptr
->prev_buf_p
!= NULL
) {
840 #ifdef XR_BLD_FREE_TRACE
841 fprintf(stderr
, " writing fst agbno %u\n",
844 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
845 libxfs_writebuf(lptr
->prev_buf_p
, 0);
847 lptr
->prev_buf_p
= lptr
->buf_p
;
848 lptr
->prev_agbno
= lptr
->agbno
;
849 lptr
->agbno
= get_next_blockaddr(agno
, 0, btree_curs
);
850 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(lptr
->agbno
);
852 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
853 XFS_AGB_TO_DADDR(mp
, agno
, lptr
->agbno
),
854 XFS_FSB_TO_BB(mp
, 1));
862 * XXX(hch): any reason we don't just look at mp->m_inobt_mxr?
864 #define XR_INOBT_BLOCK_MAXRECS(mp, level) \
865 xfs_inobt_maxrecs((mp), (mp)->m_sb.sb_blocksize, \
869 * we don't have to worry here about how chewing up free extents
870 * may perturb things because inode tree building happens before
871 * freespace tree building.
874 init_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
875 __uint64_t
*num_inos
, __uint64_t
*num_free_inos
)
879 ino_tree_node_t
*ino_rec
;
882 bt_stat_level_t
*lptr
;
883 bt_stat_level_t
*p_lptr
;
884 xfs_extlen_t blocks_allocated
;
887 *num_inos
= *num_free_inos
= 0;
890 lptr
= &btree_curs
->level
[0];
891 btree_curs
->init
= 1;
893 if ((ino_rec
= findfirst_inode_rec(agno
)) == NULL
) {
895 * easy corner-case -- no inode records
897 lptr
->num_blocks
= 1;
899 lptr
->num_recs_pb
= 0;
900 lptr
->num_recs_tot
= 0;
902 btree_curs
->num_levels
= 1;
903 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
= 1;
905 setup_cursor(mp
, agno
, btree_curs
);
911 * build up statistics
913 for (num_recs
= 0; ino_rec
!= NULL
; ino_rec
= next_ino_rec(ino_rec
)) {
914 ninos
+= XFS_INODES_PER_CHUNK
;
916 for (i
= 0; i
< XFS_INODES_PER_CHUNK
; i
++) {
917 ASSERT(is_inode_confirmed(ino_rec
, i
));
918 if (is_inode_free(ino_rec
, i
))
923 blocks_allocated
= lptr
->num_blocks
= howmany(num_recs
,
924 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
926 lptr
->modulo
= num_recs
% lptr
->num_blocks
;
927 lptr
->num_recs_pb
= num_recs
/ lptr
->num_blocks
;
928 lptr
->num_recs_tot
= num_recs
;
931 if (lptr
->num_blocks
> 1) {
932 for (; btree_curs
->level
[level
-1].num_blocks
> 1
933 && level
< XFS_BTREE_MAXLEVELS
;
935 lptr
= &btree_curs
->level
[level
];
936 p_lptr
= &btree_curs
->level
[level
- 1];
937 lptr
->num_blocks
= howmany(p_lptr
->num_blocks
,
938 XR_INOBT_BLOCK_MAXRECS(mp
, level
));
939 lptr
->modulo
= p_lptr
->num_blocks
% lptr
->num_blocks
;
940 lptr
->num_recs_pb
= p_lptr
->num_blocks
942 lptr
->num_recs_tot
= p_lptr
->num_blocks
;
944 blocks_allocated
+= lptr
->num_blocks
;
947 ASSERT(lptr
->num_blocks
== 1);
948 btree_curs
->num_levels
= level
;
950 btree_curs
->num_tot_blocks
= btree_curs
->num_free_blocks
953 setup_cursor(mp
, agno
, btree_curs
);
956 *num_free_inos
= nfinos
;
962 prop_ino_cursor(xfs_mount_t
*mp
, xfs_agnumber_t agno
, bt_status_t
*btree_curs
,
963 xfs_agino_t startino
, int level
)
965 struct xfs_btree_block
*bt_hdr
;
966 xfs_inobt_key_t
*bt_key
;
967 xfs_inobt_ptr_t
*bt_ptr
;
969 bt_stat_level_t
*lptr
;
973 if (level
>= btree_curs
->num_levels
)
976 lptr
= &btree_curs
->level
[level
];
977 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
979 if (be16_to_cpu(bt_hdr
->bb_numrecs
) == 0) {
981 * this only happens once to initialize the
982 * first path up the left side of the tree
983 * where the agbno's are already set up
985 prop_ino_cursor(mp
, agno
, btree_curs
, startino
, level
);
988 if (be16_to_cpu(bt_hdr
->bb_numrecs
) ==
989 lptr
->num_recs_pb
+ (lptr
->modulo
> 0)) {
991 * write out current prev block, grab us a new block,
992 * and set the rightsib pointer of current block
994 #ifdef XR_BLD_INO_TRACE
995 fprintf(stderr
, " ino prop agbno %d ", lptr
->prev_agbno
);
997 if (lptr
->prev_agbno
!= NULLAGBLOCK
) {
998 ASSERT(lptr
->prev_buf_p
!= NULL
);
999 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1001 lptr
->prev_agbno
= lptr
->agbno
;;
1002 lptr
->prev_buf_p
= lptr
->buf_p
;
1003 agbno
= get_next_blockaddr(agno
, level
, btree_curs
);
1005 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(agbno
);
1007 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1008 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1009 XFS_FSB_TO_BB(mp
, 1));
1010 lptr
->agbno
= agbno
;
1016 * initialize block header
1018 lptr
->buf_p
->b_ops
= &xfs_inobt_buf_ops
;
1019 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1020 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1021 if (xfs_sb_version_hascrc(&mp
->m_sb
))
1022 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_CRC_MAGIC
,
1024 XFS_BTREE_CRC_BLOCKS
);
1026 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_MAGIC
,
1029 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
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 * XXX: yet more code that can be shared with mkfs, growfs.
1055 build_agi(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1056 bt_status_t
*btree_curs
, xfs_agino_t first_agino
,
1057 xfs_agino_t count
, xfs_agino_t freecount
)
1063 agi_buf
= libxfs_getbuf(mp
->m_dev
,
1064 XFS_AG_DADDR(mp
, agno
, XFS_AGI_DADDR(mp
)),
1065 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1066 agi_buf
->b_ops
= &xfs_agi_buf_ops
;
1067 agi
= XFS_BUF_TO_AGI(agi_buf
);
1068 memset(agi
, 0, mp
->m_sb
.sb_sectsize
);
1070 agi
->agi_magicnum
= cpu_to_be32(XFS_AGI_MAGIC
);
1071 agi
->agi_versionnum
= cpu_to_be32(XFS_AGI_VERSION
);
1072 agi
->agi_seqno
= cpu_to_be32(agno
);
1073 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1074 agi
->agi_length
= cpu_to_be32(mp
->m_sb
.sb_agblocks
);
1076 agi
->agi_length
= cpu_to_be32(mp
->m_sb
.sb_dblocks
-
1077 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1078 agi
->agi_count
= cpu_to_be32(count
);
1079 agi
->agi_root
= cpu_to_be32(btree_curs
->root
);
1080 agi
->agi_level
= cpu_to_be32(btree_curs
->num_levels
);
1081 agi
->agi_freecount
= cpu_to_be32(freecount
);
1082 agi
->agi_newino
= cpu_to_be32(first_agino
);
1083 agi
->agi_dirino
= cpu_to_be32(NULLAGINO
);
1085 for (i
= 0; i
< XFS_AGI_UNLINKED_BUCKETS
; i
++)
1086 agi
->agi_unlinked
[i
] = cpu_to_be32(NULLAGINO
);
1088 if (xfs_sb_version_hascrc(&mp
->m_sb
))
1089 platform_uuid_copy(&agi
->agi_uuid
, &mp
->m_sb
.sb_uuid
);
1091 libxfs_writebuf(agi_buf
, 0);
1095 * rebuilds an inode tree given a cursor. We're lazy here and call
1096 * the routine that builds the agi
1099 build_ino_tree(xfs_mount_t
*mp
, xfs_agnumber_t agno
,
1100 bt_status_t
*btree_curs
)
1104 xfs_agblock_t agbno
;
1105 xfs_agino_t first_agino
;
1106 struct xfs_btree_block
*bt_hdr
;
1107 xfs_inobt_rec_t
*bt_rec
;
1108 ino_tree_node_t
*ino_rec
;
1109 bt_stat_level_t
*lptr
;
1110 xfs_agino_t count
= 0;
1111 xfs_agino_t freecount
= 0;
1114 int level
= btree_curs
->num_levels
;
1116 for (i
= 0; i
< level
; i
++) {
1117 lptr
= &btree_curs
->level
[i
];
1119 agbno
= get_next_blockaddr(agno
, i
, btree_curs
);
1120 lptr
->buf_p
= libxfs_getbuf(mp
->m_dev
,
1121 XFS_AGB_TO_DADDR(mp
, agno
, agbno
),
1122 XFS_FSB_TO_BB(mp
, 1));
1124 if (i
== btree_curs
->num_levels
- 1)
1125 btree_curs
->root
= agbno
;
1127 lptr
->agbno
= agbno
;
1128 lptr
->prev_agbno
= NULLAGBLOCK
;
1129 lptr
->prev_buf_p
= NULL
;
1131 * initialize block header
1134 lptr
->buf_p
->b_ops
= &xfs_inobt_buf_ops
;
1135 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1136 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1137 if (xfs_sb_version_hascrc(&mp
->m_sb
))
1138 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_CRC_MAGIC
,
1140 XFS_BTREE_CRC_BLOCKS
);
1142 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_MAGIC
,
1147 * run along leaf, setting up records. as we have to switch
1148 * blocks, call the prop_ino_cursor routine to set up the new
1149 * pointers for the parent. that can recurse up to the root
1150 * if required. set the sibling pointers for leaf level here.
1152 ino_rec
= findfirst_inode_rec(agno
);
1154 if (ino_rec
!= NULL
)
1155 first_agino
= ino_rec
->ino_startnum
;
1157 first_agino
= NULLAGINO
;
1159 lptr
= &btree_curs
->level
[0];
1161 for (i
= 0; i
< lptr
->num_blocks
; i
++) {
1163 * block initialization, lay in block header
1165 lptr
->buf_p
->b_ops
= &xfs_inobt_buf_ops
;
1166 bt_hdr
= XFS_BUF_TO_BLOCK(lptr
->buf_p
);
1167 memset(bt_hdr
, 0, mp
->m_sb
.sb_blocksize
);
1168 if (xfs_sb_version_hascrc(&mp
->m_sb
))
1169 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_CRC_MAGIC
,
1171 XFS_BTREE_CRC_BLOCKS
);
1173 xfs_btree_init_block(mp
, lptr
->buf_p
, XFS_IBT_MAGIC
,
1176 bt_hdr
->bb_u
.s
.bb_leftsib
= cpu_to_be32(lptr
->prev_agbno
);
1177 bt_hdr
->bb_numrecs
= cpu_to_be16(lptr
->num_recs_pb
+
1178 (lptr
->modulo
> 0));
1180 if (lptr
->modulo
> 0)
1183 if (lptr
->num_recs_pb
> 0)
1184 prop_ino_cursor(mp
, agno
, btree_curs
,
1185 ino_rec
->ino_startnum
, 0);
1187 bt_rec
= (xfs_inobt_rec_t
*)
1188 ((char *)bt_hdr
+ XFS_INOBT_BLOCK_LEN(mp
));
1189 for (j
= 0; j
< be16_to_cpu(bt_hdr
->bb_numrecs
); j
++) {
1190 ASSERT(ino_rec
!= NULL
);
1191 bt_rec
[j
].ir_startino
=
1192 cpu_to_be32(ino_rec
->ino_startnum
);
1193 bt_rec
[j
].ir_free
= cpu_to_be64(ino_rec
->ir_free
);
1196 for (k
= 0; k
< sizeof(xfs_inofree_t
)*NBBY
; k
++) {
1197 ASSERT(is_inode_confirmed(ino_rec
, k
));
1198 inocnt
+= is_inode_free(ino_rec
, k
);
1201 bt_rec
[j
].ir_freecount
= cpu_to_be32(inocnt
);
1202 freecount
+= inocnt
;
1203 count
+= XFS_INODES_PER_CHUNK
;
1204 ino_rec
= next_ino_rec(ino_rec
);
1207 if (ino_rec
!= NULL
) {
1209 * get next leaf level block
1211 if (lptr
->prev_buf_p
!= NULL
) {
1212 #ifdef XR_BLD_INO_TRACE
1213 fprintf(stderr
, "writing inobt agbno %u\n",
1216 ASSERT(lptr
->prev_agbno
!= NULLAGBLOCK
);
1217 libxfs_writebuf(lptr
->prev_buf_p
, 0);
1219 lptr
->prev_buf_p
= lptr
->buf_p
;
1220 lptr
->prev_agbno
= lptr
->agbno
;
1221 lptr
->agbno
= get_next_blockaddr(agno
, 0, btree_curs
);
1222 bt_hdr
->bb_u
.s
.bb_rightsib
= cpu_to_be32(lptr
->agbno
);
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
1237 * XXX: yet more common code that can be shared with mkfs/growfs.
1240 build_agf_agfl(xfs_mount_t
*mp
,
1241 xfs_agnumber_t agno
,
1242 bt_status_t
*bno_bt
,
1243 bt_status_t
*bcnt_bt
,
1244 xfs_extlen_t freeblks
, /* # free blocks in tree */
1245 int lostblocks
) /* # blocks that will be lost */
1247 extent_tree_node_t
*ext_ptr
;
1248 xfs_buf_t
*agf_buf
, *agfl_buf
;
1255 agf_buf
= libxfs_getbuf(mp
->m_dev
,
1256 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
1257 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1258 agf_buf
->b_ops
= &xfs_agf_buf_ops
;
1259 agf
= XFS_BUF_TO_AGF(agf_buf
);
1260 memset(agf
, 0, mp
->m_sb
.sb_sectsize
);
1262 #ifdef XR_BLD_FREE_TRACE
1263 fprintf(stderr
, "agf = 0x%x, agf_buf->b_un.b_addr = 0x%x\n",
1264 (__psint_t
) agf
, (__psint_t
) agf_buf
->b_un
.b_addr
);
1268 * set up fixed part of agf
1270 agf
->agf_magicnum
= cpu_to_be32(XFS_AGF_MAGIC
);
1271 agf
->agf_versionnum
= cpu_to_be32(XFS_AGF_VERSION
);
1272 agf
->agf_seqno
= cpu_to_be32(agno
);
1274 if (agno
< mp
->m_sb
.sb_agcount
- 1)
1275 agf
->agf_length
= cpu_to_be32(mp
->m_sb
.sb_agblocks
);
1277 agf
->agf_length
= cpu_to_be32(mp
->m_sb
.sb_dblocks
-
1278 (xfs_drfsbno_t
) mp
->m_sb
.sb_agblocks
* agno
);
1280 agf
->agf_roots
[XFS_BTNUM_BNO
] = cpu_to_be32(bno_bt
->root
);
1281 agf
->agf_levels
[XFS_BTNUM_BNO
] = cpu_to_be32(bno_bt
->num_levels
);
1282 agf
->agf_roots
[XFS_BTNUM_CNT
] = cpu_to_be32(bcnt_bt
->root
);
1283 agf
->agf_levels
[XFS_BTNUM_CNT
] = cpu_to_be32(bcnt_bt
->num_levels
);
1284 agf
->agf_freeblks
= cpu_to_be32(freeblks
);
1287 * Count and record the number of btree blocks consumed if required.
1289 if (xfs_sb_version_haslazysbcount(&mp
->m_sb
)) {
1291 * Don't count the root blocks as they are already
1294 agf
->agf_btreeblks
= cpu_to_be32(
1295 (bno_bt
->num_tot_blocks
- bno_bt
->num_free_blocks
) +
1296 (bcnt_bt
->num_tot_blocks
- bcnt_bt
->num_free_blocks
) -
1298 #ifdef XR_BLD_FREE_TRACE
1299 fprintf(stderr
, "agf->agf_btreeblks = %u\n",
1300 be32_to_cpu(agf
->agf_btreeblks
));
1304 #ifdef XR_BLD_FREE_TRACE
1305 fprintf(stderr
, "bno root = %u, bcnt root = %u, indices = %u %u\n",
1306 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_BNO
]),
1307 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_CNT
]),
1312 if (xfs_sb_version_hascrc(&mp
->m_sb
))
1313 platform_uuid_copy(&agf
->agf_uuid
, &mp
->m_sb
.sb_uuid
);
1315 /* initialise the AGFL, then fill it if there are blocks left over. */
1316 agfl_buf
= libxfs_getbuf(mp
->m_dev
,
1317 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
1318 mp
->m_sb
.sb_sectsize
/BBSIZE
);
1319 agfl_buf
->b_ops
= &xfs_agfl_buf_ops
;
1320 agfl
= XFS_BUF_TO_AGFL(agfl_buf
);
1322 /* setting to 0xff results in initialisation to NULLAGBLOCK */
1323 memset(agfl
, 0xff, mp
->m_sb
.sb_sectsize
);
1324 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
1325 agfl
->agfl_magicnum
= cpu_to_be32(XFS_AGFL_MAGIC
);
1326 agfl
->agfl_seqno
= cpu_to_be32(agno
);
1327 platform_uuid_copy(&agfl
->agfl_uuid
, &mp
->m_sb
.sb_uuid
);
1328 for (i
= 0; i
< XFS_AGFL_SIZE(mp
); i
++)
1329 agfl
->agfl_bno
[i
] = cpu_to_be32(NULLAGBLOCK
);
1331 freelist
= XFS_BUF_TO_AGFL_BNO(mp
, agfl_buf
);
1334 * do we have left-over blocks in the btree cursors that should
1335 * be used to fill the AGFL?
1337 if (bno_bt
->num_free_blocks
> 0 || bcnt_bt
->num_free_blocks
> 0) {
1339 * yes, now grab as many blocks as we can
1342 while (bno_bt
->num_free_blocks
> 0 && i
< XFS_AGFL_SIZE(mp
)) {
1343 freelist
[i
] = cpu_to_be32(
1344 get_next_blockaddr(agno
, 0, bno_bt
));
1348 while (bcnt_bt
->num_free_blocks
> 0 && i
< XFS_AGFL_SIZE(mp
)) {
1349 freelist
[i
] = cpu_to_be32(
1350 get_next_blockaddr(agno
, 0, bcnt_bt
));
1354 * now throw the rest of the blocks away and complain
1356 while (bno_bt
->num_free_blocks
> 0) {
1357 (void) get_next_blockaddr(agno
, 0, bno_bt
);
1360 while (bcnt_bt
->num_free_blocks
> 0) {
1361 (void) get_next_blockaddr(agno
, 0, bcnt_bt
);
1366 if (j
== lostblocks
)
1367 do_warn(_("lost %d blocks in ag %u\n"),
1370 do_warn(_("thought we were going to lose %d "
1371 "blocks in ag %u, actually lost "
1373 lostblocks
, j
, agno
);
1376 agf
->agf_flfirst
= 0;
1377 agf
->agf_fllast
= cpu_to_be32(i
- 1);
1378 agf
->agf_flcount
= cpu_to_be32(i
);
1380 #ifdef XR_BLD_FREE_TRACE
1381 fprintf(stderr
, "writing agfl for ag %u\n", agno
);
1385 agf
->agf_flfirst
= 0;
1386 agf
->agf_fllast
= cpu_to_be32(XFS_AGFL_SIZE(mp
) - 1);
1387 agf
->agf_flcount
= 0;
1390 libxfs_writebuf(agfl_buf
, 0);
1392 ext_ptr
= findbiggest_bcnt_extent(agno
);
1393 agf
->agf_longest
= cpu_to_be32((ext_ptr
!= NULL
) ?
1394 ext_ptr
->ex_blockcount
: 0);
1396 ASSERT(be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_BNOi
]) !=
1397 be32_to_cpu(agf
->agf_roots
[XFS_BTNUM_CNTi
]));
1399 libxfs_writebuf(agf_buf
, 0);
1402 * now fix up the free list appropriately
1403 * XXX: code lifted from mkfs, should be shared.
1406 xfs_alloc_arg_t args
;
1408 struct xfs_trans_res tres
= {0};
1410 memset(&args
, 0, sizeof(args
));
1411 args
.tp
= tp
= libxfs_trans_alloc(mp
, 0);
1415 args
.pag
= xfs_perag_get(mp
,agno
);
1416 libxfs_trans_reserve(tp
, &tres
, XFS_MIN_FREELIST(agf
, mp
), 0);
1417 libxfs_alloc_fix_freelist(&args
, 0);
1418 xfs_perag_put(args
.pag
);
1419 libxfs_trans_commit(tp
, 0);
1422 #ifdef XR_BLD_FREE_TRACE
1423 fprintf(stderr
, "wrote agf for ag %u, error = %d\n", agno
, error
);
1428 * update the superblock counters, sync the sb version numbers and
1429 * feature bits to the filesystem, and sync up the on-disk superblock
1430 * to match the incore superblock.
1433 sync_sb(xfs_mount_t
*mp
)
1437 bp
= libxfs_getsb(mp
, 0);
1439 do_error(_("couldn't get superblock\n"));
1441 mp
->m_sb
.sb_icount
= sb_icount
;
1442 mp
->m_sb
.sb_ifree
= sb_ifree
;
1443 mp
->m_sb
.sb_fdblocks
= sb_fdblocks
;
1444 mp
->m_sb
.sb_frextents
= sb_frextents
;
1446 update_sb_version(mp
);
1448 libxfs_sb_to_disk(XFS_BUF_TO_SBP(bp
), &mp
->m_sb
, XFS_SB_ALL_BITS
);
1449 libxfs_writebuf(bp
, 0);
1453 * make sure the root and realtime inodes show up allocated
1454 * even if they've been freed. they get reinitialized in phase6.
1457 keep_fsinos(xfs_mount_t
*mp
)
1459 ino_tree_node_t
*irec
;
1462 irec
= find_inode_rec(mp
, XFS_INO_TO_AGNO(mp
, mp
->m_sb
.sb_rootino
),
1463 XFS_INO_TO_AGINO(mp
, mp
->m_sb
.sb_rootino
));
1465 for (i
= 0; i
< 3; i
++)
1466 set_inode_used(irec
, i
);
1472 xfs_agnumber_t agno
)
1474 __uint64_t num_inos
;
1475 __uint64_t num_free_inos
;
1476 bt_status_t bno_btree_curs
;
1477 bt_status_t bcnt_btree_curs
;
1478 bt_status_t ino_btree_curs
;
1479 int extra_blocks
= 0;
1480 uint num_freeblocks
;
1481 xfs_extlen_t freeblks1
;
1483 xfs_extlen_t freeblks2
;
1485 xfs_agblock_t num_extents
;
1488 do_log(_(" - agno = %d\n"), agno
);
1492 * build up incore bno and bcnt extent btrees
1494 num_extents
= mk_incore_fstree(mp
, agno
);
1496 #ifdef XR_BLD_FREE_TRACE
1497 fprintf(stderr
, "# of bno extents is %d\n",
1498 count_bno_extents(agno
));
1501 if (num_extents
== 0) {
1503 * XXX - what we probably should do here is pick an
1504 * inode for a regular file in the allocation group
1505 * that has space allocated and shoot it by traversing
1506 * the bmap list and putting all its extents on the
1507 * incore freespace trees, clearing the inode,
1508 * and clearing the in-use bit in the incore inode
1509 * tree. Then try mk_incore_fstree() again.
1511 do_error(_("unable to rebuild AG %u. "
1512 "Not enough free space in on-disk AG.\n"),
1517 * ok, now set up the btree cursors for the
1518 * on-disk btrees (includs pre-allocating all
1519 * required blocks for the trees themselves)
1521 init_ino_cursor(mp
, agno
, &ino_btree_curs
,
1522 &num_inos
, &num_free_inos
);
1524 sb_icount_ag
[agno
] += num_inos
;
1525 sb_ifree_ag
[agno
] += num_free_inos
;
1527 num_extents
= count_bno_extents_blocks(agno
, &num_freeblocks
);
1529 * lose two blocks per AG -- the space tree roots
1530 * are counted as allocated since the space trees
1533 sb_fdblocks_ag
[agno
] += num_freeblocks
- 2;
1535 if (num_extents
== 0) {
1537 * XXX - what we probably should do here is pick an
1538 * inode for a regular file in the allocation group
1539 * that has space allocated and shoot it by traversing
1540 * the bmap list and putting all its extents on the
1541 * incore freespace trees, clearing the inode,
1542 * and clearing the in-use bit in the incore inode
1543 * tree. Then try mk_incore_fstree() again.
1546 _("unable to rebuild AG %u. No free space.\n"), agno
);
1549 #ifdef XR_BLD_FREE_TRACE
1550 fprintf(stderr
, "# of bno extents is %d\n", num_extents
);
1554 * track blocks that we might really lose
1556 extra_blocks
= calculate_freespace_cursor(mp
, agno
,
1557 &num_extents
, &bno_btree_curs
);
1560 * freespace btrees live in the "free space" but
1561 * the filesystem treats AGFL blocks as allocated
1562 * since they aren't described by the freespace trees
1566 * see if we can fit all the extra blocks into the AGFL
1568 extra_blocks
= (extra_blocks
- XFS_AGFL_SIZE(mp
) > 0)
1569 ? extra_blocks
- XFS_AGFL_SIZE(mp
)
1572 if (extra_blocks
> 0) {
1573 do_warn(_("lost %d blocks in agno %d, sorry.\n"),
1574 extra_blocks
, agno
);
1575 sb_fdblocks_ag
[agno
] -= extra_blocks
;
1578 bcnt_btree_curs
= bno_btree_curs
;
1580 setup_cursor(mp
, agno
, &bno_btree_curs
);
1581 setup_cursor(mp
, agno
, &bcnt_btree_curs
);
1583 #ifdef XR_BLD_FREE_TRACE
1584 fprintf(stderr
, "# of bno extents is %d\n",
1585 count_bno_extents(agno
));
1586 fprintf(stderr
, "# of bcnt extents is %d\n",
1587 count_bcnt_extents(agno
));
1591 * now rebuild the freespace trees
1593 freeblks1
= build_freespace_tree(mp
, agno
,
1594 &bno_btree_curs
, XFS_ABTB_MAGIC
);
1595 #ifdef XR_BLD_FREE_TRACE
1596 fprintf(stderr
, "# of free blocks == %d\n", freeblks1
);
1598 write_cursor(&bno_btree_curs
);
1601 freeblks2
= build_freespace_tree(mp
, agno
,
1602 &bcnt_btree_curs
, XFS_ABTC_MAGIC
);
1604 (void) build_freespace_tree(mp
, agno
,
1605 &bcnt_btree_curs
, XFS_ABTC_MAGIC
);
1607 write_cursor(&bcnt_btree_curs
);
1609 ASSERT(freeblks1
== freeblks2
);
1612 * set up agf and agfl
1614 build_agf_agfl(mp
, agno
, &bno_btree_curs
,
1615 &bcnt_btree_curs
, freeblks1
, extra_blocks
);
1617 * build inode allocation tree. this also build the agi
1619 build_ino_tree(mp
, agno
, &ino_btree_curs
);
1620 write_cursor(&ino_btree_curs
);
1624 finish_cursor(&bno_btree_curs
);
1625 finish_cursor(&ino_btree_curs
);
1626 finish_cursor(&bcnt_btree_curs
);
1628 * release the incore per-AG bno/bcnt trees so
1629 * the extent nodes can be recycled
1631 release_agbno_extent_tree(agno
);
1632 release_agbcnt_extent_tree(agno
);
1634 PROG_RPT_INC(prog_rpt_done
[agno
], 1);
1638 phase5(xfs_mount_t
*mp
)
1640 xfs_agnumber_t agno
;
1642 do_log(_("Phase 5 - rebuild AG headers and trees...\n"));
1643 set_progress_msg(PROG_FMT_REBUILD_AG
, (__uint64_t
)glob_agcount
);
1645 #ifdef XR_BLD_FREE_TRACE
1646 fprintf(stderr
, "inobt level 1, maxrec = %d, minrec = %d\n",
1647 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0),
1648 xfs_inobt_maxrecs(mp
->m_sb
.sb_blocksize
, 0) / 2
1650 fprintf(stderr
, "inobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1651 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1),
1652 xfs_inobt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, xfs_inobt
, 1) / 2);
1653 fprintf(stderr
, "xr inobt level 0 (leaf), maxrec = %d\n",
1654 XR_INOBT_BLOCK_MAXRECS(mp
, 0));
1655 fprintf(stderr
, "xr inobt level 1 (int), maxrec = %d\n",
1656 XR_INOBT_BLOCK_MAXRECS(mp
, 1));
1657 fprintf(stderr
, "bnobt level 1, maxrec = %d, minrec = %d\n",
1658 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0),
1659 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 0) / 2);
1660 fprintf(stderr
, "bnobt level 0 (leaf), maxrec = %d, minrec = %d\n",
1661 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 1),
1662 xfs_allocbt_maxrecs(mp
, mp
->m_sb
.sb_blocksize
, 1) / 2);
1665 * make sure the root and realtime inodes show up allocated
1669 /* allocate per ag counters */
1670 sb_icount_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1671 if (sb_icount_ag
== NULL
)
1672 do_error(_("cannot alloc sb_icount_ag buffers\n"));
1674 sb_ifree_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1675 if (sb_ifree_ag
== NULL
)
1676 do_error(_("cannot alloc sb_ifree_ag buffers\n"));
1678 sb_fdblocks_ag
= calloc(mp
->m_sb
.sb_agcount
, sizeof(__uint64_t
));
1679 if (sb_fdblocks_ag
== NULL
)
1680 do_error(_("cannot alloc sb_fdblocks_ag buffers\n"));
1682 for (agno
= 0; agno
< mp
->m_sb
.sb_agcount
; agno
++)
1683 phase5_func(mp
, agno
);
1687 /* aggregate per ag counters */
1688 for (agno
= 0; agno
< mp
->m_sb
.sb_agcount
; agno
++) {
1689 sb_icount
+= sb_icount_ag
[agno
];
1690 sb_ifree
+= sb_ifree_ag
[agno
];
1691 sb_fdblocks
+= sb_fdblocks_ag
[agno
];
1695 free(sb_fdblocks_ag
);
1697 if (mp
->m_sb
.sb_rblocks
) {
1699 _(" - generate realtime summary info and bitmap...\n"));
1701 generate_rtinfo(mp
, btmcompute
, sumcompute
);
1704 do_log(_(" - reset superblock...\n"));
1707 * sync superblock counter and set version bits correctly