xfs/libxfs/xfs_btree_staging.c

27  * initializing new btree blocks and filling them with records or key/ptr
183  * height of and the number of blocks needed to construct the btree.  See the
187  * In step four, the caller must allocate xfs_btree_bload.nr_blocks blocks and
189  * blocks to be allocated beforehand to avoid ENOSPC failures midway through a
196  * is responsible for cleaning up the previous btree blocks, if any.
204  * is the number of blocks in the next lower level of the tree.  For each
209  * The number of blocks for the level is defined to be:
211  * blocks = floor(nr_items / desired)
217  * npb =  nr_items / blocks
219  * Some of the leftmost blocks in the level will contain one extra record as
221  * would exceed maxrecs for that level, blocks is incremented and npb is
224  * In other words, we compute the number of blocks needed to satisfy a given
227  * The height and number of fs blocks required to create the btree are computed
233  * The btree blocks will be written to disk when bulk loading is finished.
319 	/* Claim one of the caller's preallocated blocks. */
466 	/* Root blocks are not subject to minrecs rules. */
475  * the number of blocks for this level.  For leaf levels, we must populate an
486 	uint64_t		*blocks,
504 	 * Compute the number of blocks we need to fill each block with the
511 	*blocks = div64_u64_rem(nr_this_level, desired_npb, &dontcare);
512 	*blocks = max(1ULL, *blocks);
517 	 * the blocks.  Take care that the effective # of items per block (npb)
518 	 * won't exceed maxrecs even for the blocks that get an extra record,
522 	npb = div64_u64_rem(nr_this_level, *blocks, blocks_with_extra);
524 		(*blocks)++;
525 		npb = div64_u64_rem(nr_this_level, *blocks, blocks_with_extra);
531 			*avg_per_block, desired_npb, *blocks,
583 	 * node blocks.  Inode-rooted btrees will return different minrecs and
617 			 * level in traditional btree blocks and therefore need
618 			 * another level of btree to point to those blocks.
681 	uint64_t			blocks;
698 			&avg_per_block, &blocks, &blocks_with_extra);
701 	for (i = 0; i < blocks; i++) {
705 		 * Due to rounding, btree blocks will not be evenly populated
706 		 * in most cases.  blocks_with_extra tells us how many blocks
718 		trace_xfs_btree_bload_block(cur, level, i, blocks, &ptr,
733 	total_blocks += blocks;
743 		nr_this_level = blocks;
748 				&avg_per_block, &blocks, &blocks_with_extra);
751 		for (i = 0; i < blocks; i++) {
763 			trace_xfs_btree_bload_block(cur, level, i, blocks,
778 		total_blocks += blocks;
799 	 * Write the new blocks to disk.  If the ordered list isn't empty after