xfs: clean up xfs_btree_{calc_size,compute_maxlevels}

Source kernel commit: 1b236ad7ba800bc3e9994881a8a453eb8bf5ca0f

During review of the next patch, Dave remarked that he found these two
btree geometry calculation functions lacking in documentation and that
they performed more work than was really necessary.

These functions take the same parameters and have nearly the same logic;
the only real difference is in the return values.  Reword the function
comment to make it clearer what each function does, and move them to be
adjacent to reinforce their relation.

Clean up both of them to stop opencoding the howmany functions, stop
using the uint typedefs, and make them both support computations for
more than 2^32 leaf records, since we're going to need all of the above
for files with large data forks and large rmap btrees.

Signed-off-by: Darrick J. Wong <djwong@kernel.org>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
Signed-off-by: Eric Sandeen <sandeen@sandeen.net>

diff --git a/libxfs/xfs_btree.c b/libxfs/xfs_btree.c
index 6a049c641eb3bf94cd12f346b3dea9d5b2db3666..5ada6cc4d380330569453025a4f7795d4ba51ead 100644 (file)
--- a/libxfs/xfs_btree.c
+++ b/libxfs/xfs_btree.c
@@ -4515,21 +4515,43 @@ xfs_btree_sblock_verify(
 }
 
 /*
- * Calculate the number of btree levels needed to store a given number of
- * records in a short-format btree.
+ * For the given limits on leaf and keyptr records per block, calculate the
+ * height of the tree needed to index the number of leaf records.
  */
-uint
+unsigned int
 xfs_btree_compute_maxlevels(
-       uint                    *limits,
-       unsigned long           len)
+       const unsigned int      *limits,
+       unsigned long long      records)
 {
-       uint                    level;
-       unsigned long           maxblocks;
+       unsigned long long      level_blocks = howmany_64(records, limits[0]);
+       unsigned int            height = 1;
 
-       maxblocks = (len + limits[0] - 1) / limits[0];
-       for (level = 1; maxblocks > 1; level++)
-               maxblocks = (maxblocks + limits[1] - 1) / limits[1];
-       return level;
+       while (level_blocks > 1) {
+               level_blocks = howmany_64(level_blocks, limits[1]);
+               height++;
+       }
+
+       return height;
+}
+
+/*
+ * For the given limits on leaf and keyptr records per block, calculate the
+ * number of blocks needed to index the given number of leaf records.
+ */
+unsigned long long
+xfs_btree_calc_size(
+       const unsigned int      *limits,
+       unsigned long long      records)
+{
+       unsigned long long      level_blocks = howmany_64(records, limits[0]);
+       unsigned long long      blocks = level_blocks;
+
+       while (level_blocks > 1) {
+               level_blocks = howmany_64(level_blocks, limits[1]);
+               blocks += level_blocks;
+       }
+
+       return blocks;
 }
 
 /*
@@ -4823,29 +4845,6 @@ xfs_btree_query_all(
        return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv);
 }
 
-/*
- * Calculate the number of blocks needed to store a given number of records
- * in a short-format (per-AG metadata) btree.
- */
-unsigned long long
-xfs_btree_calc_size(
-       uint                    *limits,
-       unsigned long long      len)
-{
-       int                     level;
-       int                     maxrecs;
-       unsigned long long      rval;
-
-       maxrecs = limits[0];
-       for (level = 0, rval = 0; len > 1; level++) {
-               len += maxrecs - 1;
-               do_div(len, maxrecs);
-               maxrecs = limits[1];
-               rval += len;
-       }
-       return rval;
-}
-
 static int
 xfs_btree_count_blocks_helper(
        struct xfs_btree_cur    *cur,

diff --git a/libxfs/xfs_btree.h b/libxfs/xfs_btree.h
index b46cd98309fa2aaa0be8f936ee2ae96a0fedc4e6..3bd69fe425a7291bb85b0752839521691f74f587 100644 (file)
--- a/libxfs/xfs_btree.h
+++ b/libxfs/xfs_btree.h
@@ -487,8 +487,10 @@ xfs_failaddr_t xfs_btree_lblock_v5hdr_verify(struct xfs_buf *bp,
 xfs_failaddr_t xfs_btree_lblock_verify(struct xfs_buf *bp,
                unsigned int max_recs);
 
-uint xfs_btree_compute_maxlevels(uint *limits, unsigned long len);
-unsigned long long xfs_btree_calc_size(uint *limits, unsigned long long len);
+unsigned int xfs_btree_compute_maxlevels(const unsigned int *limits,
+               unsigned long long records);
+unsigned long long xfs_btree_calc_size(const unsigned int *limits,
+               unsigned long long records);
 
 /*
  * Return codes for the query range iterator function are 0 to continue