* [Cluster-devel] [PATCH 2/2] libgfs2: gfs2_get_bitmap performance enhancements
2012-10-25 21:38 [Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2 Andrew Price
@ 2012-10-25 21:38 ` Andrew Price
2012-10-29 9:08 ` [Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2 Steven Whitehouse
1 sibling, 0 replies; 3+ messages in thread
From: Andrew Price @ 2012-10-25 21:38 UTC (permalink / raw)
To: cluster-devel.redhat.com
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
^ permalink raw reply related [flat|nested] 3+ messages in thread* [Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2
2012-10-25 21:38 [Cluster-devel] [PATCH 1/2] libgfs2: Move valid_block into fsck.gfs2 Andrew Price
2012-10-25 21:38 ` [Cluster-devel] [PATCH 2/2] libgfs2: gfs2_get_bitmap performance enhancements Andrew Price
@ 2012-10-29 9:08 ` Steven Whitehouse
1 sibling, 0 replies; 3+ messages in thread
From: Steven Whitehouse @ 2012-10-29 9:08 UTC (permalink / raw)
To: cluster-devel.redhat.com
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);
^ permalink raw reply [flat|nested] 3+ messages in thread