From da9398dd294193331f7e9c332e8e2a4106e67dc1 Mon Sep 17 00:00:00 2001 From: Christoph Hellwig Date: Wed, 2 Sep 2009 17:55:40 +0000 Subject: [PATCH] repair: track logical to physical block mapping more effeciently Currently we track the logical to physical block mapping by a structure which contains an array of physicial blocks. This is extremly efficient and is replaced with the normal starblock storage we use in the kernel and on disk in this patch. In addition also use thread-local storage for the block map, this is possible because repair only processes one inode at a given time per thread, and the block map does not have to outlive the processing of a single inode. The combination of those factors means we can use pthread thread-local storage to store the block map, and we can re-use the allocation over and over again. This should be ported over to xfs_db eventually, or even better we could try to share the code. [hch: added a small fix in blkmap_set_ext to not call memmove unless needed] Signed-off-by: Barry Naujok Signed-off-by: Christoph Hellwig Reviewed-by: Alex Elder Signed-off-by: Alex Elder --- repair/bmap.c | 389 +++++++++++++++--------------------------------- repair/bmap.h | 58 +++----- repair/dinode.c | 6 +- repair/init.c | 10 +- 4 files changed, 151 insertions(+), 312 deletions(-) diff --git a/repair/bmap.c b/repair/bmap.c index 05d5da89b..79b9f79f4 100644 --- a/repair/bmap.c +++ b/repair/bmap.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. + * Copyright (c) 2000-2001,2005,2008 Silicon Graphics, Inc. * All Rights Reserved. * * This program is free software; you can redistribute it and/or @@ -21,106 +21,46 @@ #include "bmap.h" /* - * Block mapping code taken from xfs_db. - */ - -/* - * Append an extent to the block entry. - */ -void -blkent_append( - blkent_t **entp, - xfs_dfsbno_t b, - xfs_dfilblks_t c) -{ - blkent_t *ent; - size_t size; - int i; - - ent = *entp; - size = BLKENT_SIZE(c + ent->nblks); - if ((*entp = ent = realloc(ent, size)) == NULL) { - do_warn(_("realloc failed in blkent_append (%u bytes)\n"), - size); - return; - } - for (i = 0; i < c; i++) - ent->blks[ent->nblks + i] = b + i; - ent->nblks += c; -} - -/* - * Make a new block entry. - */ -blkent_t * -blkent_new( - xfs_dfiloff_t o, - xfs_dfsbno_t b, - xfs_dfilblks_t c) -{ - blkent_t *ent; - int i; - - if ((ent = malloc(BLKENT_SIZE(c))) == NULL) { - do_warn(_("malloc failed in blkent_new (%u bytes)\n"), - BLKENT_SIZE(c)); - return ent; - } - ent->nblks = c; - ent->startoff = o; - for (i = 0; i < c; i++) - ent->blks[i] = b + i; - return ent; -} - -/* - * Prepend an extent to the block entry. + * Track the logical to physical block mapping for inodes. + * + * Repair only processes one inode at a given time per thread, and the + * block map does not have to outlive the processing of a single inode. + * + * The combination of those factors means we can use pthreads thread-local + * storage to store the block map, and we can re-use the allocation over + * and over again. */ -void -blkent_prepend( - blkent_t **entp, - xfs_dfsbno_t b, - xfs_dfilblks_t c) -{ - int i; - blkent_t *newent; - blkent_t *oldent; - oldent = *entp; - if ((newent = malloc(BLKENT_SIZE(oldent->nblks + c))) == NULL) { - do_warn(_("malloc failed in blkent_prepend (%u bytes)\n"), - BLKENT_SIZE(oldent->nblks + c)); - *entp = newent; - return; - } - newent->nblks = oldent->nblks + c; - newent->startoff = oldent->startoff - c; - for (i = 0; i < c; i++) - newent->blks[i] = b + c; - for (; i < oldent->nblks + c; i++) - newent->blks[i] = oldent->blks[i - c]; - free(oldent); - *entp = newent; -} +pthread_key_t dblkmap_key; +pthread_key_t ablkmap_key; -/* - * Allocate a block map. - */ blkmap_t * blkmap_alloc( - xfs_extnum_t nex) + xfs_extnum_t nex, + int whichfork) { + pthread_key_t key; blkmap_t *blkmap; + ASSERT(whichfork == XFS_DATA_FORK || whichfork == XFS_ATTR_FORK); + if (nex < 1) nex = 1; - if ((blkmap = malloc(BLKMAP_SIZE(nex))) == NULL) { - do_warn(_("malloc failed in blkmap_alloc (%u bytes)\n"), - BLKMAP_SIZE(nex)); - return blkmap; + + key = whichfork ? ablkmap_key : dblkmap_key; + blkmap = pthread_getspecific(key); + if (!blkmap || blkmap->naexts < nex) { + blkmap = realloc(blkmap, BLKMAP_SIZE(nex)); + if (!blkmap) { + do_warn(_("malloc failed in blkmap_alloc (%u bytes)\n"), + BLKMAP_SIZE(nex)); + return NULL; + } + pthread_setspecific(key, blkmap); + blkmap->naexts = nex; } - blkmap->naents = nex; - blkmap->nents = 0; + + blkmap->nexts = 0; return blkmap; } @@ -131,14 +71,7 @@ void blkmap_free( blkmap_t *blkmap) { - blkent_t **entp; - xfs_extnum_t i; - - if (blkmap == NULL) - return; - for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++) - free(*entp); - free(blkmap); + /* nothing to do! - keep the memory around for the next inode */ } /* @@ -149,20 +82,18 @@ blkmap_get( blkmap_t *blkmap, xfs_dfiloff_t o) { - blkent_t *ent; - blkent_t **entp; + bmap_ext_t *ext = blkmap->exts; int i; - for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++) { - ent = *entp; - if (o >= ent->startoff && o < ent->startoff + ent->nblks) - return ent->blks[o - ent->startoff]; + for (i = 0; i < blkmap->nexts; i++, ext++) { + if (o >= ext->startoff && o < ext->startoff + ext->blockcount) + return ext->startblock + (o - ext->startoff); } return NULLDFSBNO; } /* - * Get a chunk of entries from a block map. + * Get a chunk of entries from a block map - only used for reading dirv2 blocks */ int blkmap_getn( @@ -172,93 +103,62 @@ blkmap_getn( bmap_ext_t **bmpp, bmap_ext_t *bmpp_single) { - bmap_ext_t *bmp; - blkent_t *ent; - xfs_dfiloff_t ento; - blkent_t **entp; + bmap_ext_t *bmp = NULL; + bmap_ext_t *ext; int i; int nex; if (nb == 1) { - /* + /* * in the common case, when mp->m_dirblkfsbs == 1, * avoid additional malloc/free overhead */ bmpp_single->startblock = blkmap_get(blkmap, o); - bmpp_single->blockcount = 1; - bmpp_single->startoff = 0; - bmpp_single->flag = 0; - *bmpp = bmpp_single; - return (bmpp_single->startblock != NULLDFSBNO) ? 1 : 0; + goto single_ext; } - for (i = nex = 0, bmp = NULL, entp = blkmap->ents; - i < blkmap->nents; - i++, entp++) { - ent = *entp; - if (ent->startoff >= o + nb) + ext = blkmap->exts; + nex = 0; + for (i = 0; i < blkmap->nexts; i++, ext++) { + + if (ext->startoff >= o + nb) break; - if (ent->startoff + ent->nblks <= o) + if (ext->startoff + ext->blockcount <= o) continue; - for (ento = ent->startoff; - ento < ent->startoff + ent->nblks && ento < o + nb; - ento++) { - if (ento < o) - continue; - if (bmp && - bmp[nex - 1].startoff + bmp[nex - 1].blockcount == - ento && - bmp[nex - 1].startblock + bmp[nex - 1].blockcount == - ent->blks[ento - ent->startoff]) - bmp[nex - 1].blockcount++; - else { - bmp = realloc(bmp, ++nex * sizeof(*bmp)); - if (bmp == NULL) { - do_warn(_("blkmap_getn realloc failed" - " (%u bytes)\n"), - nex * sizeof(*bmp)); - continue; - } - bmp[nex - 1].startoff = ento; - bmp[nex - 1].startblock = - ent->blks[ento - ent->startoff]; - bmp[nex - 1].blockcount = 1; - bmp[nex - 1].flag = 0; - } + + /* + * if all the requested blocks are in one extent (also common), + * use the bmpp_single option as well + */ + if (!bmp && o >= ext->startoff && + o + nb <= ext->startoff + ext->blockcount) { + bmpp_single->startblock = + ext->startblock + (o - ext->startoff); + goto single_ext; } + + /* + * rare case - multiple extents for a single dir block + */ + bmp = malloc(nb * sizeof(bmap_ext_t)); + if (!bmp) + do_error(_("blkmap_getn malloc failed (%u bytes)\n"), + nb * sizeof(bmap_ext_t)); + + bmp[nex].startblock = ext->startblock + (o - ext->startoff); + bmp[nex].blockcount = MIN(nb, ext->blockcount - + (bmp[nex].startblock - ext->startblock)); + o += bmp[nex].blockcount; + nb -= bmp[nex].blockcount; + nex++; } *bmpp = bmp; return nex; -} - -/* - * Make a block map larger. - */ -void -blkmap_grow( - blkmap_t **blkmapp, - blkent_t **entp, - blkent_t *newent) -{ - blkmap_t *blkmap; - size_t size; - int i; - int idx; - blkmap = *blkmapp; - idx = (int)(entp - blkmap->ents); - if (blkmap->naents == blkmap->nents) { - size = BLKMAP_SIZE(blkmap->nents + 1); - if ((*blkmapp = blkmap = realloc(blkmap, size)) == NULL) { - do_warn(_("realloc failed in blkmap_grow (%u bytes)\n"), - size); - return; - } - blkmap->naents++; - } - for (i = blkmap->nents; i > idx; i--) - blkmap->ents[i] = blkmap->ents[i - 1]; - blkmap->ents[idx] = newent; - blkmap->nents++; +single_ext: + bmpp_single->blockcount = nb; + bmpp_single->startoff = 0; /* not even used by caller! */ + *bmpp = bmpp_single; + return (bmpp_single->startblock != NULLDFSBNO) ? 1 : 0; } /* @@ -268,12 +168,12 @@ xfs_dfiloff_t blkmap_last_off( blkmap_t *blkmap) { - blkent_t *ent; + bmap_ext_t *ext; - if (!blkmap->nents) + if (!blkmap->nexts) return NULLDFILOFF; - ent = blkmap->ents[blkmap->nents - 1]; - return ent->startoff + ent->nblks; + ext = blkmap->exts + blkmap->nexts - 1; + return ext->startoff + ext->blockcount; } /* @@ -285,73 +185,45 @@ blkmap_next_off( xfs_dfiloff_t o, int *t) { - blkent_t *ent; - blkent_t **entp; + bmap_ext_t *ext; - if (!blkmap->nents) + if (!blkmap->nexts) return NULLDFILOFF; if (o == NULLDFILOFF) { *t = 0; - ent = blkmap->ents[0]; - return ent->startoff; + return blkmap->exts[0].startoff; } - entp = &blkmap->ents[*t]; - ent = *entp; - if (o < ent->startoff + ent->nblks - 1) + ext = blkmap->exts + *t; + if (o < ext->startoff + ext->blockcount - 1) return o + 1; - entp++; - if (entp >= &blkmap->ents[blkmap->nents]) + if (*t >= blkmap->nexts - 1) return NULLDFILOFF; (*t)++; - ent = *entp; - return ent->startoff; + return ext[1].startoff; } /* - * Set a block value in a block map. + * Make a block map larger. */ -void -blkmap_set_blk( - blkmap_t **blkmapp, - xfs_dfiloff_t o, - xfs_dfsbno_t b) +static blkmap_t * +blkmap_grow( + blkmap_t **blkmapp) { - blkmap_t *blkmap; - blkent_t *ent; - blkent_t **entp; - blkent_t *nextent; + pthread_key_t key = dblkmap_key; + blkmap_t *blkmap = *blkmapp; - blkmap = *blkmapp; - for (entp = blkmap->ents; entp < &blkmap->ents[blkmap->nents]; entp++) { - ent = *entp; - if (o < ent->startoff - 1) { - ent = blkent_new(o, b, 1); - blkmap_grow(blkmapp, entp, ent); - return; - } - if (o == ent->startoff - 1) { - blkent_prepend(entp, b, 1); - return; - } - if (o >= ent->startoff && o < ent->startoff + ent->nblks) { - ent->blks[o - ent->startoff] = b; - return; - } - if (o > ent->startoff + ent->nblks) - continue; - blkent_append(entp, b, 1); - if (entp == &blkmap->ents[blkmap->nents - 1]) - return; - ent = *entp; - nextent = entp[1]; - if (ent->startoff + ent->nblks < nextent->startoff) - return; - blkent_append(entp, nextent->blks[0], nextent->nblks); - blkmap_shrink(blkmap, &entp[1]); - return; + if (pthread_getspecific(key) != blkmap) { + key = ablkmap_key; + ASSERT(pthread_getspecific(key) == blkmap); } - ent = blkent_new(o, b, 1); - blkmap_grow(blkmapp, entp, ent); + + blkmap->naexts += 4; + blkmap = realloc(blkmap, BLKMAP_SIZE(blkmap->naexts)); + if (blkmap == NULL) + do_error(_("realloc failed in blkmap_grow\n")); + *blkmapp = blkmap; + pthread_setspecific(key, blkmap); + return blkmap; } /* @@ -364,46 +236,23 @@ blkmap_set_ext( xfs_dfsbno_t b, xfs_dfilblks_t c) { - blkmap_t *blkmap; - blkent_t *ent; - blkent_t **entp; + blkmap_t *blkmap = *blkmapp; xfs_extnum_t i; - blkmap = *blkmapp; - if (!blkmap->nents) { - blkmap->ents[0] = blkent_new(o, b, c); - blkmap->nents = 1; - return; - } - entp = &blkmap->ents[blkmap->nents - 1]; - ent = *entp; - if (ent->startoff + ent->nblks == o) { - blkent_append(entp, b, c); - return; - } - if (ent->startoff + ent->nblks < o) { - ent = blkent_new(o, b, c); - blkmap_grow(blkmapp, &blkmap->ents[blkmap->nents], ent); - return; - } - for (i = 0; i < c; i++) - blkmap_set_blk(blkmapp, o + i, b + i); -} + if (blkmap->nexts == blkmap->naexts) + blkmap = blkmap_grow(blkmapp); -/* - * Make a block map smaller. - */ -void -blkmap_shrink( - blkmap_t *blkmap, - blkent_t **entp) -{ - int i; - int idx; + for (i = 0; i < blkmap->nexts; i++) { + if (blkmap->exts[i].startoff > o) { + memmove(blkmap->exts + i + 1, + blkmap->exts + i, + sizeof(bmap_ext_t) * (blkmap->nexts - i)); + break; + } + } - free(*entp); - idx = (int)(entp - blkmap->ents); - for (i = idx + 1; i < blkmap->nents; i++) - blkmap->ents[i] = blkmap->ents[i - 1]; - blkmap->nents--; + blkmap->exts[i].startoff = o; + blkmap->exts[i].startblock = b; + blkmap->exts[i].blockcount = c; + blkmap->nexts++; } diff --git a/repair/bmap.h b/repair/bmap.h index eba1799f5..58abf95fd 100644 --- a/repair/bmap.h +++ b/repair/bmap.h @@ -16,59 +16,41 @@ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ -/* - * Block mapping code taken from xfs_db. - */ +#ifndef _XFS_REPAIR_BMAP_H +#define _XFS_REPAIR_BMAP_H /* - * Block map entry. + * Extent descriptor. */ -typedef struct blkent { +typedef struct bmap_ext { xfs_dfiloff_t startoff; - xfs_dfilblks_t nblks; - xfs_dfsbno_t blks[1]; -} blkent_t; -#define BLKENT_SIZE(n) \ - (offsetof(blkent_t, blks) + (sizeof(xfs_dfsbno_t) * (n))) + xfs_dfsbno_t startblock; + xfs_dfilblks_t blockcount; +} bmap_ext_t; /* * Block map. */ typedef struct blkmap { - int naents; - int nents; - blkent_t *ents[1]; + int naexts; + int nexts; + bmap_ext_t exts[1]; } blkmap_t; -#define BLKMAP_SIZE(n) \ - (offsetof(blkmap_t, ents) + (sizeof(blkent_t *) * (n))) -/* - * Extent descriptor. - */ -typedef struct bmap_ext { - xfs_dfiloff_t startoff; - xfs_dfsbno_t startblock; - xfs_dfilblks_t blockcount; - int flag; -} bmap_ext_t; +#define BLKMAP_SIZE(n) \ + (offsetof(blkmap_t, exts) + (sizeof(bmap_ext_t) * (n))) -void blkent_append(blkent_t **entp, xfs_dfsbno_t b, - xfs_dfilblks_t c); -blkent_t *blkent_new(xfs_dfiloff_t o, xfs_dfsbno_t b, xfs_dfilblks_t c); -void blkent_prepend(blkent_t **entp, xfs_dfsbno_t b, - xfs_dfilblks_t c); -blkmap_t *blkmap_alloc(xfs_extnum_t); +blkmap_t *blkmap_alloc(xfs_extnum_t nex, int whichfork); void blkmap_free(blkmap_t *blkmap); + +void blkmap_set_ext(blkmap_t **blkmapp, xfs_dfiloff_t o, + xfs_dfsbno_t b, xfs_dfilblks_t c); + xfs_dfsbno_t blkmap_get(blkmap_t *blkmap, xfs_dfiloff_t o); int blkmap_getn(blkmap_t *blkmap, xfs_dfiloff_t o, - xfs_dfilblks_t nb, bmap_ext_t **bmpp, + xfs_dfilblks_t nb, bmap_ext_t **bmpp, bmap_ext_t *bmpp_single); -void blkmap_grow(blkmap_t **blkmapp, blkent_t **entp, - blkent_t *newent); xfs_dfiloff_t blkmap_last_off(blkmap_t *blkmap); xfs_dfiloff_t blkmap_next_off(blkmap_t *blkmap, xfs_dfiloff_t o, int *t); -void blkmap_set_blk(blkmap_t **blkmapp, xfs_dfiloff_t o, - xfs_dfsbno_t b); -void blkmap_set_ext(blkmap_t **blkmapp, xfs_dfiloff_t o, - xfs_dfsbno_t b, xfs_dfilblks_t c); -void blkmap_shrink(blkmap_t *blkmap, blkent_t **entp); + +#endif /* _XFS_REPAIR_BMAP_H */ diff --git a/repair/dinode.c b/repair/dinode.c index 9da721be4..df1dce9fe 100644 --- a/repair/dinode.c +++ b/repair/dinode.c @@ -2050,7 +2050,7 @@ process_inode_data_fork( *nextents = 1; if (dinoc->di_format != XFS_DINODE_FMT_LOCAL && type != XR_INO_RTDATA) - *dblkmap = blkmap_alloc(*nextents); + *dblkmap = blkmap_alloc(*nextents, XFS_DATA_FORK); *nextents = 0; switch (dinoc->di_format) { @@ -2172,14 +2172,14 @@ process_inode_attr_fork( err = process_lclinode(mp, agno, ino, dino, XFS_ATTR_FORK); break; case XFS_DINODE_FMT_EXTENTS: - ablkmap = blkmap_alloc(*anextents); + ablkmap = blkmap_alloc(*anextents, XFS_ATTR_FORK); *anextents = 0; err = process_exinode(mp, agno, ino, dino, type, dirty, atotblocks, anextents, &ablkmap, XFS_ATTR_FORK, check_dups); break; case XFS_DINODE_FMT_BTREE: - ablkmap = blkmap_alloc(*anextents); + ablkmap = blkmap_alloc(*anextents, XFS_ATTR_FORK); *anextents = 0; err = process_btinode(mp, agno, ino, dino, type, dirty, atotblocks, anextents, &ablkmap, diff --git a/repair/init.c b/repair/init.c index 1a1226f98..654c406f0 100644 --- a/repair/init.c +++ b/repair/init.c @@ -24,19 +24,24 @@ #include "pthread.h" #include "avl.h" #include "dir.h" +#include "bmap.h" #include "incore.h" #include "prefetch.h" #include +/* TODO: dirbuf/freemap key usage is completely b0rked - only used for dirv1 */ static pthread_key_t dirbuf_key; static pthread_key_t dir_freemap_key; static pthread_key_t attr_freemap_key; +extern pthread_key_t dblkmap_key; +extern pthread_key_t ablkmap_key; + static void ts_alloc(pthread_key_t key, unsigned n, size_t size) { void *voidp; - voidp = malloc((n)*(size)); + voidp = calloc(n, size); if (voidp == NULL) { do_error(_("ts_alloc: cannot allocate thread specific storage\n")); /* NO RETURN */ @@ -52,6 +57,9 @@ ts_create(void) pthread_key_create(&dirbuf_key, NULL); pthread_key_create(&dir_freemap_key, NULL); pthread_key_create(&attr_freemap_key, NULL); + + pthread_key_create(&dblkmap_key, NULL); + pthread_key_create(&ablkmap_key, NULL); } void -- 2.39.5