libgfs2: Improve rgblocks2bitblocks()

----- Original Message -----

| This patch reworks the rgblocks2bitblocks function which was
| inefficient, difficult to read and generally unwieldy.
|
| As this is core code from the days of yore and fsck.gfs2 depends on
| it,
| I made sure to test the new function extensively, comparing its
| outputs
| with the original function over a large range of values for rgblocks
| (up
| to 195312500) and valid block sizes between 512 and 4096.
|
| All call points have been updated and, as a nice side effect, the run
| time of the function is greatly reduced.
|
| Signed-off-by: Andrew Price<[email protected]>
| +	while (blks_rgrp + blks_meta * bitblocks<  ((rgblocks - bitblocks)

Hi,

The patch looks good. There's only thing I'd do differently:
I know the implied arithmetic operator order is correct, but I still prefer to see parens around statements like the above just for clarity. e.g.

(quoted diff) +1 -0

+	while (blks_rgrp + (blks_meta * bitblocks)<  ((rgblocks - bitblocks)

I guess that's more of a style thing.

This patch reworks the rgblocks2bitblocks function which was inefficient, difficult to read and generally unwieldy.

As this is core code from the days of yore and fsck.gfs2 depends on it, I made sure to test the new function extensively, comparing its outputs with the original function over a large range of values for rgblocks (up to 195312500) and valid block sizes between 512 and 4096.

All call points have been updated and, as a nice side effect, the run time of the function is greatly reduced.

Signed-off-by Andrew Price <[email protected]>

---
 gfs2/fsck/rgrepair.c       |   14 +++--------
 gfs2/libgfs2/fs_geometry.c |   54 +++++++++++++++++--------------------------
 gfs2/libgfs2/libgfs2.h     |    4 +-
 3 files changed, 27 insertions(+), 45 deletions(-)

gfs2/fsck/rgrepair.c +4 -10

index 6394546..1ffa2c0 100644
@@ -507,12 +507,9 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, int *num_rgs,
 		calc_rgd->ri.ri_data0 = calc_rgd->ri.ri_addr +
 			calc_rgd->ri.ri_length;
 		if (prev_rgd) {
-			uint32_t rgblocks, bitblocks;
+			uint32_t rgblocks;
 
-			rgblocks = block_bump;
-			rgblocks2bitblocks(sdp->bsize, &rgblocks, &bitblocks);
-
-			prev_rgd->ri.ri_length = bitblocks;
+			prev_rgd->ri.ri_length = rgblocks2bitblocks(sdp->bsize, block_bump, &rgblocks);
 			prev_rgd->ri.ri_data = rgblocks;
 			prev_rgd->ri.ri_data0 = prev_rgd->ri.ri_addr +
 				prev_rgd->ri.ri_length;

@@ -566,12 +563,9 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, int *num_rgs,
 	/* allocation information for the very last RG.                      */
 	/* ----------------------------------------------------------------- */
 	if (prev_rgd && !prev_rgd->ri.ri_data) {
-		uint32_t rgblocks, bitblocks;
-
-		rgblocks = block_bump;
-		rgblocks2bitblocks(sdp->bsize, &rgblocks, &bitblocks);
+		uint32_t rgblocks;
 
-		prev_rgd->ri.ri_length = bitblocks;
+		prev_rgd->ri.ri_length = rgblocks2bitblocks(sdp->bsize, block_bump, &rgblocks);
 		prev_rgd->ri.ri_data0 = prev_rgd->ri.ri_addr +
 			prev_rgd->ri.ri_length;
 		prev_rgd->ri.ri_data = rgblocks;

gfs2/libgfs2/fs_geometry.c +21 -33

index 130331a..891858e 100644
@@ -34,11 +34,10 @@ uint64_t how_many_rgrps(struct gfs2_sbd *sdp, struct device *dev, int rgsize_spe
 		nrgrp = DIV_RU(dev->length, (sdp->rgsize << 20) / sdp->bsize);
 
 		/* check to see if the rg length overflows max # bitblks */
-		rgblocksn = dev->length / nrgrp;
-		rgblocks2bitblocks(sdp->bsize, &rgblocksn, &bitblocksn);
+		bitblocksn = rgblocks2bitblocks(sdp->bsize, dev->length / nrgrp, &rgblocksn);
 		/* calculate size of the first rgrp */
-		rgblocks1 = dev->length - (nrgrp - 1) * (dev->length / nrgrp);
-		rgblocks2bitblocks(sdp->bsize, &rgblocks1, &bitblocks1);
+		bitblocks1 = rgblocks2bitblocks(sdp->bsize, dev->length - (nrgrp - 1) * (dev->length / nrgrp),
+		                                &rgblocks1);
 		if (bitblocks1 > 2149 || bitblocksn > 2149) {
 			bitmap_overflow = 1;
 			if (sdp->rgsize <= GFS2_DEFAULT_RGSIZE) {

@@ -158,39 +157,29 @@ void compute_rgrp_layout(struct gfs2_sbd *sdp, struct osi_root *rgtree,
 }
 
 /**
- * rgblocks2bitblocks -
- * @bsize:
- * @rgblocks:
- * @bitblocks:
- *
- * Given a number of blocks in a RG, figure out the number of blocks
- * needed for bitmaps.
- *
+ * Given a number of blocks in a resource group, return the number of blocks
+ * needed for bitmaps. Also calculate the adjusted number of free data blocks
+ * in the resource group and store it in *ri_data.
  */
-
-void rgblocks2bitblocks(unsigned int bsize, uint32_t *rgblocks, uint32_t *bitblocks)
+uint32_t rgblocks2bitblocks(const unsigned int bsize, const uint32_t rgblocks, uint32_t *ri_data)
 {
-	unsigned int bitbytes_provided, last = 0;
-	unsigned int bitbytes_needed;
+	uint32_t mappable = 0;
+	uint32_t bitblocks = 0;
+	/* Number of blocks mappable by bitmap blocks with these header types */
+	const uint32_t blks_rgrp = GFS2_NBBY * (bsize - sizeof(struct gfs2_rgrp));
+	const uint32_t blks_meta = GFS2_NBBY * (bsize - sizeof(struct gfs2_meta_header));
 
-	*bitblocks = 1;
-	bitbytes_provided = bsize - sizeof(struct gfs2_rgrp);
+	while (blks_rgrp + blks_meta * bitblocks < ((rgblocks - bitblocks) & ~(uint32_t)3))
+		bitblocks++;
 
-	for (;;) {
-	        bitbytes_needed = (*rgblocks - *bitblocks) / GFS2_NBBY;
+	if (bitblocks > 0)
+		mappable = blks_rgrp + blks_meta * (bitblocks - 1);
 
-		if (bitbytes_provided >= bitbytes_needed) {
-			if (last >= bitbytes_needed)
-				(*bitblocks)--;
-			break;
-		}
-
-		last = bitbytes_provided;
-		(*bitblocks)++;
-		bitbytes_provided += bsize - sizeof(struct gfs2_meta_header);
-	}
+	*ri_data = (rgblocks - (bitblocks + 1)) & ~(uint32_t)3;
+	if (mappable < *ri_data)
+		bitblocks++;
 
-	*rgblocks = bitbytes_needed * GFS2_NBBY;
+	return bitblocks;
 }
 
 /**

@@ -220,8 +209,7 @@ void build_rgrps(struct gfs2_sbd *sdp, int do_write)
 		rl = (struct rgrp_tree *)n;
 		ri = &rl->ri;
 
-		rgblocks = rl->length;
-		rgblocks2bitblocks(sdp->bsize, &rgblocks, &bitblocks);
+		bitblocks = rgblocks2bitblocks(sdp->bsize, rl->length, &rgblocks);
 
 		ri->ri_addr = rl->start;
 		ri->ri_length = bitblocks;

gfs2/libgfs2/libgfs2.h +2 -2

index 77dfc29..95fd2b4 100644
@@ -338,8 +338,8 @@ extern int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
 extern int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state);
 
 /* fs_geometry.c */
-extern void rgblocks2bitblocks(unsigned int bsize, uint32_t *rgblocks,
-			       uint32_t *bitblocks);
+extern uint32_t rgblocks2bitblocks(const unsigned int bsize, const uint32_t rgblocks,
+                                    uint32_t *ri_data) __attribute__((nonnull(3)));
 extern uint64_t how_many_rgrps(struct gfs2_sbd *sdp, struct device *dev,
 			       int rgsize_specified);
 extern void compute_rgrp_layout(struct gfs2_sbd *sdp, struct osi_root *rgtree,