[Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2

[Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2

[Andrew Price]

valid_block() is only used by fsck.gfs2 as none of the other utils
require the same level of paranoia so we can move it into fsck.h and
make it static inline.

In my (small) tests the speedup effect is barely noticeable but it
should make a difference for larger file systems, particularly those
with very large directories.

Also fsck/fs_bits.h is no longer used so this patch removes it.

Signed-off-by: Andrew Price <anprice@redhat.com>
---
 gfs2/fsck/Makefile.am  |  2 +-
 gfs2/fsck/fs_bits.h    | 17 -----------------
 gfs2/fsck/fsck.h       |  6 ++++++
 gfs2/fsck/util.c       |  1 -
 gfs2/libgfs2/fs_bits.c | 17 -----------------
 gfs2/libgfs2/libgfs2.h |  1 -
 6 files changed, 7 insertions(+), 37 deletions(-)
 delete mode 100644 gfs2/fsck/fs_bits.h

diff --git a/gfs2/fsck/Makefile.am b/gfs2/fsck/Makefile.am
index 261f6b1..b92c745 100644
--- a/gfs2/fsck/Makefile.am
+++ b/gfs2/fsck/Makefile.am
@@ -10,7 +10,7 @@ sbindir := $(shell rpl=0; test '$(exec_prefix):$(sbindir)' = /usr:/usr/sbin \
 
 sbin_PROGRAMS		= fsck.gfs2
 
-noinst_HEADERS		= eattr.h fs_bits.h fsck.h fs_recovery.h \
+noinst_HEADERS		= eattr.h fsck.h fs_recovery.h \
 			  inode_hash.h link.h lost_n_found.h metawalk.h util.h
 
 fsck_gfs2_SOURCES	= eattr.c fs_recovery.c initialize.c \
diff --git a/gfs2/fsck/fs_bits.h b/gfs2/fsck/fs_bits.h
deleted file mode 100644
index d4f262e..0000000
--- a/gfs2/fsck/fs_bits.h
+++ /dev/null
@@ -1,17 +0,0 @@
-#ifndef __FS_BITS_H__
-#define __FS_BITS_H__
-
-#include "libgfs2.h"
-#include "fsck.h"
-
-#define BFITNOENT (0xFFFFFFFF)
-
-struct fs_bitmap
-{
-	uint32_t   bi_offset;	/* The offset in the buffer of the first byte */
-	uint32_t   bi_start;    /* The position of the first byte in this block */
-	uint32_t   bi_len;      /* The number of bytes in this block */
-};
-typedef struct fs_bitmap fs_bitmap_t;
-
-#endif /* __FS_BITS_H__ */
diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index 70fc3d7..dd49280 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -148,4 +148,10 @@ extern int dups_found_first; /* How many duplicates have we found the original
 				reference for? */
 extern struct gfs_sb *sbd1;
 
+static inline int valid_block(struct gfs2_sbd *sdp, uint64_t blkno)
+{
+	return !((blkno > sdp->fssize) || (blkno <= sdp->sb_addr) ||
+	         (gfs2_get_bitmap(sdp, blkno, NULL) < 0));
+}
+
 #endif /* _FSCK_H */
diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c
index 6c80ae8..eff7382 100644
--- a/gfs2/fsck/util.c
+++ b/gfs2/fsck/util.c
@@ -13,7 +13,6 @@
 #define _(String) gettext(String)
 
 #include "libgfs2.h"
-#include "fs_bits.h"
 #include "metawalk.h"
 #include "util.h"
 
diff --git a/gfs2/libgfs2/fs_bits.c b/gfs2/libgfs2/fs_bits.c
index 5eeb920..fdc3bb3 100644
--- a/gfs2/libgfs2/fs_bits.c
+++ b/gfs2/libgfs2/fs_bits.c
@@ -113,23 +113,6 @@ int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno)
 }
 
 /*
- * valid_block - check if blkno is valid and not part of our rgrps or bitmaps
- * @sdp: super block
- * @blkno: block number
- *
- * Returns: 1 if ok, 0 if out of bounds
- */
-int valid_block(struct gfs2_sbd *sdp, uint64_t blkno)
-{
-	if((blkno > sdp->fssize) || (blkno <= sdp->sb_addr))
-		return 0;
-	/* Check if the block is one of our rgrp or bitmap blocks */
-	if (gfs2_get_bitmap(sdp, blkno, NULL) < 0)
-		return 0;
-	return 1;
-}
-
-/*
  * gfs2_set_bitmap
  * @sdp: super block
  * @blkno: block number relative to file system
diff --git a/gfs2/libgfs2/libgfs2.h b/gfs2/libgfs2/libgfs2.h
index 3045337..bf65922 100644
--- a/gfs2/libgfs2/libgfs2.h
+++ b/gfs2/libgfs2/libgfs2.h
@@ -408,7 +408,6 @@ extern uint32_t gfs2_blkalloc_internal(struct rgrp_tree *rgd, uint32_t goal,
 extern int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno);
 
 /* functions with blk #'s that are file system relative */
-extern int valid_block(struct gfs2_sbd *sdp, uint64_t blkno);
 extern int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
 			   struct rgrp_tree *rgd);
 extern int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state);
-- 
1.7.11.7

[Cluster-devel] [PATCH 2/2] libgfs2: gfs2_get_bitmap performance enhancements

[Andrew Price]

This patch takes the bit lookup strategy from the kernel code (an
amalgamation of gfs2_rbm_from_block and gfs2_testbit) to speed up
gfs2_get_bitmap, which is renamed lgfs2_get_bitmap.

Timings obtained running fsck.gfs2 on a 5% full, 10G local fs with 512
byte blocks (to maximize the number of leaf blocks) and many large
directories:

   HEAD~2      HEAD
   -------    -------
   2:15.70    2:10.03
   2:14.32    2:09.89
   2:14.32    2:09.83
   2:14.66    2:09.84
   2:14.30    2:09.89
   2:14.62    2:10.23
   2:14.58    2:09.64
   2:14.50    2:09.68
   2:14.99    2:09.49
   2:14.79    2:09.97

For sanity the output of the new lgfs2_get_bitmap was checked against
the output of the old gfs2_get_bitmap over 1 million block state
lookups.

Signed-off-by: Andrew Price <anprice@redhat.com>
---
 gfs2/edit/hexedit.c    |  8 ++++----
 gfs2/fsck/fsck.h       |  2 +-
 gfs2/fsck/metawalk.c   |  2 +-
 gfs2/libgfs2/fs_bits.c | 44 ++++++++++++++++++++++++--------------------
 gfs2/libgfs2/lang.c    |  2 +-
 gfs2/libgfs2/libgfs2.h |  4 ++--
 gfs2/libgfs2/rgrp.c    | 17 ++++++-----------
 gfs2/libgfs2/super.c   |  2 ++
 8 files changed, 41 insertions(+), 40 deletions(-)

diff --git a/gfs2/edit/hexedit.c b/gfs2/edit/hexedit.c
index ff0dca9..6f5f5af 100644
--- a/gfs2/edit/hexedit.c
+++ b/gfs2/edit/hexedit.c
@@ -698,7 +698,7 @@ int display_block_type(int from_restore)
 			    (be32_to_cpu(mh->mh_type) == GFS2_METATYPE_RB))
 				type = 4;
 			else {
-				type = gfs2_get_bitmap(&sbd, block, rgd);
+				type = lgfs2_get_bitmap(&sbd, block, rgd);
 			}
 		} else
 			type = 4;
@@ -726,7 +726,7 @@ int display_block_type(int from_restore)
 
 				print_gfs2(" blk ");
 				for (b = blknum; b < blknum + 4; b++) {
-					btype = gfs2_get_bitmap(&sbd, b, rgd);
+					btype = lgfs2_get_bitmap(&sbd, b, rgd);
 					if (btype >= 0) {
 						print_gfs2("0x%x-%s  ", b,
 							   allocdesc[sbd.gfs1][btype]);
@@ -760,7 +760,7 @@ int display_block_type(int from_restore)
 				blknum += rgd->ri.ri_data0;
 				print_gfs2(" blk ");
 				for (b = blknum; b < blknum + 4; b++) {
-					btype = gfs2_get_bitmap(&sbd, b, rgd);
+					btype = lgfs2_get_bitmap(&sbd, b, rgd);
 					if (btype >= 0) {
 						print_gfs2("0x%x-%s  ", b,
 							   allocdesc[sbd.gfs1][btype]);
@@ -2053,7 +2053,7 @@ static void find_change_block_alloc(int *newval)
 				else
 					printf("%d\n", *newval);
 			} else {
-				type = gfs2_get_bitmap(&sbd, ablock, rgd);
+				type = lgfs2_get_bitmap(&sbd, ablock, rgd);
 				if (type < 0) {
 					printf("-1 (block invalid or part of "
 					       "an rgrp).\n");
diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index dd49280..ecd37ad 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -151,7 +151,7 @@ extern struct gfs_sb *sbd1;
 static inline int valid_block(struct gfs2_sbd *sdp, uint64_t blkno)
 {
 	return !((blkno > sdp->fssize) || (blkno <= sdp->sb_addr) ||
-	         (gfs2_get_bitmap(sdp, blkno, NULL) < 0));
+	         (lgfs2_get_bitmap(sdp, blkno, NULL) < 0));
 }
 
 #endif /* _FSCK_H */
diff --git a/gfs2/fsck/metawalk.c b/gfs2/fsck/metawalk.c
index 24de901..f19c0f7 100644
--- a/gfs2/fsck/metawalk.c
+++ b/gfs2/fsck/metawalk.c
@@ -34,7 +34,7 @@ int check_n_fix_bitmap(struct gfs2_sbd *sdp, uint64_t blk,
 
 	rgd = gfs2_blk2rgrpd(sdp, blk);
 
-	old_bitmap_state = gfs2_get_bitmap(sdp, blk, rgd);
+	old_bitmap_state = lgfs2_get_bitmap(sdp, blk, rgd);
 	if (old_bitmap_state < 0) {
 		log_err( _("Block %llu (0x%llx) is not represented in the "
 			   "system bitmap; part of an rgrp or superblock.\n"),
diff --git a/gfs2/libgfs2/fs_bits.c b/gfs2/libgfs2/fs_bits.c
index fdc3bb3..94a612b 100644
--- a/gfs2/libgfs2/fs_bits.c
+++ b/gfs2/libgfs2/fs_bits.c
@@ -4,6 +4,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <limits.h>
 
 #include "libgfs2.h"
 
@@ -175,14 +176,12 @@ int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state)
  *
  * Returns: state on success, -1 on error
  */
-int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
-		    struct rgrp_tree *rgd)
+int lgfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, struct rgrp_tree *rgd)
 {
-	int           i, val;
-	uint32_t        rgrp_block;
-	struct gfs2_bitmap	*bits = NULL;
-	unsigned int  bit;
-	unsigned char *byte;
+	uint64_t offset;
+	uint32_t i = 0;
+	char *byte;
+	unsigned int bit;
 
 	if (rgd == NULL) {
 		rgd = gfs2_blk2rgrpd(sdp, blkno);
@@ -190,23 +189,28 @@ int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
 			return -1;
 	}
 
-	rgrp_block = (uint32_t)(blkno - rgd->ri.ri_data0);
+	offset = blkno - rgd->ri.ri_data0;
+	if (offset > UINT_MAX) {
+		errno = EINVAL;
+		return -1;
+	}
+	if (offset >= rgd->ri.ri_data0 + rgd->ri.ri_data) {
+		errno = E2BIG;
+		return -1;
+	}
 
-	for (i = 0; i < rgd->ri.ri_length; i++) {
-		bits = &(rgd->bits[i]);
-		if(rgrp_block < ((bits->bi_start + bits->bi_len)*GFS2_NBBY))
-			break;
+	if (offset >= (rgd->bits->bi_start + rgd->bits->bi_len) * GFS2_NBBY) {
+		offset += (sizeof(struct gfs2_rgrp) - sizeof(struct gfs2_meta_header))
+		          * GFS2_NBBY;
+		i = offset / sdp->sd_blocks_per_bitmap;
+		offset -= i * sdp->sd_blocks_per_bitmap;
 	}
 
-	if (i >= rgd->ri.ri_length)
-		return -1;
 	if (!rgd->bh || !rgd->bh[i])
-		return 0;
-	byte = (unsigned char *)(rgd->bh[i]->b_data + bits->bi_offset) +
-		(rgrp_block/GFS2_NBBY - bits->bi_start);
-	bit = (rgrp_block % GFS2_NBBY) * GFS2_BIT_SIZE;
+		return GFS2_BLKST_FREE;
 
-	val = ((*byte >> bit) & GFS2_BIT_MASK);
+	byte = (rgd->bh[i]->b_data + rgd->bits[i].bi_offset) + (offset/GFS2_NBBY);
+	bit = (offset % GFS2_NBBY) * GFS2_BIT_SIZE;
 
-	return val;
+	return (*byte >> bit) & GFS2_BIT_MASK;
 }
diff --git a/gfs2/libgfs2/lang.c b/gfs2/libgfs2/lang.c
index 12ca7bd..ad9382f 100644
--- a/gfs2/libgfs2/lang.c
+++ b/gfs2/libgfs2/lang.c
@@ -329,7 +329,7 @@ static int ast_get_bitstate(uint64_t bn, struct gfs2_sbd *sbd)
 		return -1;
 	}
 
-	state = gfs2_get_bitmap(sbd, bn, rgd);
+	state = lgfs2_get_bitmap(sbd, bn, rgd);
 	if (state == -1) {
 		fprintf(stderr, "Failed to acquire bitmap state for block %"PRIu64"\n", bn);
 		return -1;
diff --git a/gfs2/libgfs2/libgfs2.h b/gfs2/libgfs2/libgfs2.h
index bf65922..2b109fb 100644
--- a/gfs2/libgfs2/libgfs2.h
+++ b/gfs2/libgfs2/libgfs2.h
@@ -276,6 +276,7 @@ struct gfs2_sbd {
 	uint32_t sd_hash_bsize;
 	uint32_t sd_hash_bsize_shift;
 	uint32_t sd_hash_ptrs;
+	uint32_t sd_blocks_per_bitmap;
 	uint32_t sd_max_dirres;
 	uint32_t sd_max_height;
 	uint64_t sd_heightsize[GFS2_MAX_META_HEIGHT];
@@ -408,8 +409,7 @@ extern uint32_t gfs2_blkalloc_internal(struct rgrp_tree *rgd, uint32_t goal,
 extern int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno);
 
 /* functions with blk #'s that are file system relative */
-extern int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
-			   struct rgrp_tree *rgd);
+extern int lgfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, struct rgrp_tree *rgd);
 extern int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state);
 
 /* fs_geometry.c */
diff --git a/gfs2/libgfs2/rgrp.c b/gfs2/libgfs2/rgrp.c
index c0f72fd..cbab2a3 100644
--- a/gfs2/libgfs2/rgrp.c
+++ b/gfs2/libgfs2/rgrp.c
@@ -98,17 +98,12 @@ int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_tree *rgd)
  */
 struct rgrp_tree *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk)
 {
-	struct osi_node *node = sdp->rgtree.osi_node;
-	struct gfs2_rindex *ri;
-
-	while (node) {
-		struct rgrp_tree *rgd = (struct rgrp_tree *)node;
-		ri = &rgd->ri;
-
-		if (blk < ri->ri_addr)
-			node = node->osi_left;
-		else if (blk >= ri->ri_data0 + ri->ri_data)
-			node = node->osi_right;
+	struct rgrp_tree *rgd = (struct rgrp_tree *)sdp->rgtree.osi_node;
+	while (rgd) {
+		if (blk < rgd->ri.ri_addr)
+			rgd = (struct rgrp_tree *)rgd->node.osi_left;
+		else if (blk >= rgd->ri.ri_data0 + rgd->ri.ri_data)
+			rgd = (struct rgrp_tree *)rgd->node.osi_right;
 		else
 			return rgd;
 	}
diff --git a/gfs2/libgfs2/super.c b/gfs2/libgfs2/super.c
index fdf0e60..8317862 100644
--- a/gfs2/libgfs2/super.c
+++ b/gfs2/libgfs2/super.c
@@ -116,6 +116,8 @@ int read_sb(struct gfs2_sbd *sdp)
 	}
 	sdp->fssize = lseek(sdp->device_fd, 0, SEEK_END) / sdp->sd_sb.sb_bsize;
 	sdp->sb_addr = GFS2_SB_ADDR * GFS2_BASIC_BLOCK / sdp->bsize;
+	sdp->sd_blocks_per_bitmap = (sdp->sd_sb.sb_bsize - sizeof(struct gfs2_meta_header))
+	                             * GFS2_NBBY;
 
 	return 0;
 }
-- 
1.7.11.7

[Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2

[Steven Whitehouse]

Hi,

Both of these patches look good to me,

Steve.

On Thu, 2012-10-25 at 22:38 +0100, Andrew Price wrote:
> valid_block() is only used by fsck.gfs2 as none of the other utils
> require the same level of paranoia so we can move it into fsck.h and
> make it static inline.
> 
> In my (small) tests the speedup effect is barely noticeable but it
> should make a difference for larger file systems, particularly those
> with very large directories.
> 
> Also fsck/fs_bits.h is no longer used so this patch removes it.
> 
> Signed-off-by: Andrew Price <anprice@redhat.com>
> ---
>  gfs2/fsck/Makefile.am  |  2 +-
>  gfs2/fsck/fs_bits.h    | 17 -----------------
>  gfs2/fsck/fsck.h       |  6 ++++++
>  gfs2/fsck/util.c       |  1 -
>  gfs2/libgfs2/fs_bits.c | 17 -----------------
>  gfs2/libgfs2/libgfs2.h |  1 -
>  6 files changed, 7 insertions(+), 37 deletions(-)
>  delete mode 100644 gfs2/fsck/fs_bits.h
> 
> diff --git a/gfs2/fsck/Makefile.am b/gfs2/fsck/Makefile.am
> index 261f6b1..b92c745 100644
> --- a/gfs2/fsck/Makefile.am
> +++ b/gfs2/fsck/Makefile.am
> @@ -10,7 +10,7 @@ sbindir := $(shell rpl=0; test '$(exec_prefix):$(sbindir)' = /usr:/usr/sbin \
>  
>  sbin_PROGRAMS		= fsck.gfs2
>  
> -noinst_HEADERS		= eattr.h fs_bits.h fsck.h fs_recovery.h \
> +noinst_HEADERS		= eattr.h fsck.h fs_recovery.h \
>  			  inode_hash.h link.h lost_n_found.h metawalk.h util.h
>  
>  fsck_gfs2_SOURCES	= eattr.c fs_recovery.c initialize.c \
> diff --git a/gfs2/fsck/fs_bits.h b/gfs2/fsck/fs_bits.h
> deleted file mode 100644
> index d4f262e..0000000
> --- a/gfs2/fsck/fs_bits.h
> +++ /dev/null
> @@ -1,17 +0,0 @@
> -#ifndef __FS_BITS_H__
> -#define __FS_BITS_H__
> -
> -#include "libgfs2.h"
> -#include "fsck.h"
> -
> -#define BFITNOENT (0xFFFFFFFF)
> -
> -struct fs_bitmap
> -{
> -	uint32_t   bi_offset;	/* The offset in the buffer of the first byte */
> -	uint32_t   bi_start;    /* The position of the first byte in this block */
> -	uint32_t   bi_len;      /* The number of bytes in this block */
> -};
> -typedef struct fs_bitmap fs_bitmap_t;
> -
> -#endif /* __FS_BITS_H__ */
> diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
> index 70fc3d7..dd49280 100644
> --- a/gfs2/fsck/fsck.h
> +++ b/gfs2/fsck/fsck.h
> @@ -148,4 +148,10 @@ extern int dups_found_first; /* How many duplicates have we found the original
>  				reference for? */
>  extern struct gfs_sb *sbd1;
>  
> +static inline int valid_block(struct gfs2_sbd *sdp, uint64_t blkno)
> +{
> +	return !((blkno > sdp->fssize) || (blkno <= sdp->sb_addr) ||
> +	         (gfs2_get_bitmap(sdp, blkno, NULL) < 0));
> +}
> +
>  #endif /* _FSCK_H */
> diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c
> index 6c80ae8..eff7382 100644
> --- a/gfs2/fsck/util.c
> +++ b/gfs2/fsck/util.c
> @@ -13,7 +13,6 @@
>  #define _(String) gettext(String)
>  
>  #include "libgfs2.h"
> -#include "fs_bits.h"
>  #include "metawalk.h"
>  #include "util.h"
>  
> diff --git a/gfs2/libgfs2/fs_bits.c b/gfs2/libgfs2/fs_bits.c
> index 5eeb920..fdc3bb3 100644
> --- a/gfs2/libgfs2/fs_bits.c
> +++ b/gfs2/libgfs2/fs_bits.c
> @@ -113,23 +113,6 @@ int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno)
>  }
>  
>  /*
> - * valid_block - check if blkno is valid and not part of our rgrps or bitmaps
> - * @sdp: super block
> - * @blkno: block number
> - *
> - * Returns: 1 if ok, 0 if out of bounds
> - */
> -int valid_block(struct gfs2_sbd *sdp, uint64_t blkno)
> -{
> -	if((blkno > sdp->fssize) || (blkno <= sdp->sb_addr))
> -		return 0;
> -	/* Check if the block is one of our rgrp or bitmap blocks */
> -	if (gfs2_get_bitmap(sdp, blkno, NULL) < 0)
> -		return 0;
> -	return 1;
> -}
> -
> -/*
>   * gfs2_set_bitmap
>   * @sdp: super block
>   * @blkno: block number relative to file system
> diff --git a/gfs2/libgfs2/libgfs2.h b/gfs2/libgfs2/libgfs2.h
> index 3045337..bf65922 100644
> --- a/gfs2/libgfs2/libgfs2.h
> +++ b/gfs2/libgfs2/libgfs2.h
> @@ -408,7 +408,6 @@ extern uint32_t gfs2_blkalloc_internal(struct rgrp_tree *rgd, uint32_t goal,
>  extern int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno);
>  
>  /* functions with blk #'s that are file system relative */
> -extern int valid_block(struct gfs2_sbd *sdp, uint64_t blkno);
>  extern int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno,
>  			   struct rgrp_tree *rgd);
>  extern int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state);