From 209875400d1f11d4d3f37032d3d35ebb4559ef4b Mon Sep 17 00:00:00 2001 From: Christoph Hellwig Date: Wed, 2 Sep 2009 17:55:44 +0000 Subject: [PATCH] repair: optimize duplicate extent tracking Switch the duplicate extent tracking from an avl tree to our new btree implementation. Modify search_dup_extent to find overlapping extents with differening start blocks instead of having the caller walk every possible start block. Signed-off-by: Barry Naujok Signed-off-by: Christoph Hellwig Reviewed-by: Alex Elder Signed-off-by: Alex Elder --- repair/dinode.c | 20 +++--- repair/incore.h | 22 ++---- repair/incore_ext.c | 165 +++++++++++++++----------------------------- repair/scan.c | 5 +- 4 files changed, 71 insertions(+), 141 deletions(-) diff --git a/repair/dinode.c b/repair/dinode.c index 980d3c378..bf04c6ee5 100644 --- a/repair/dinode.c +++ b/repair/dinode.c @@ -735,18 +735,14 @@ process_bmbt_reclist_int( * checking each entry without setting the * block bitmap */ - for (b = irec.br_startblock; - agbno < ebno; - b++, agbno++) { - if (search_dup_extent(mp, agno, agbno)) { - do_warn(_("%s fork in ino %llu claims " - "dup extent, off - %llu, " - "start - %llu, cnt %llu\n"), - forkname, ino, irec.br_startoff, - irec.br_startblock, - irec.br_blockcount); - goto done; - } + if (search_dup_extent(agno, agbno, ebno)) { + do_warn(_("%s fork in ino %llu claims " + "dup extent, off - %llu, " + "start - %llu, cnt %llu\n"), + forkname, ino, irec.br_startoff, + irec.br_startblock, + irec.br_blockcount); + goto done; } *tot += irec.br_blockcount; continue; diff --git a/repair/incore.h b/repair/incore.h index 60c6d11d7..99853fb0b 100644 --- a/repair/incore.h +++ b/repair/incore.h @@ -20,6 +20,8 @@ #define XFS_REPAIR_INCORE_H #include "avl.h" + + /* * contains definition information. implementation (code) * is spread out in separate files. @@ -168,23 +170,11 @@ get_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, /* * duplicate extent tree functions */ -void add_dup_extent(xfs_agnumber_t agno, - xfs_agblock_t startblock, - xfs_extlen_t blockcount); - -extern avltree_desc_t **extent_tree_ptrs; -/* ARGSUSED */ -static inline int -search_dup_extent(xfs_mount_t *mp, xfs_agnumber_t agno, xfs_agblock_t agbno) -{ - ASSERT(agno < glob_agcount); - - if (avl_findrange(extent_tree_ptrs[agno], agbno) != NULL) - return(1); - - return(0); -} +int add_dup_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, + xfs_extlen_t blockcount); +int search_dup_extent(xfs_agnumber_t agno, + xfs_agblock_t start_agbno, xfs_agblock_t end_agbno); void add_rt_dup_extent(xfs_drtbno_t startblock, xfs_extlen_t blockcount); diff --git a/repair/incore_ext.c b/repair/incore_ext.c index d0b8cdc4b..a362e5a6a 100644 --- a/repair/incore_ext.c +++ b/repair/incore_ext.c @@ -18,6 +18,7 @@ #include #include "avl.h" +#include "btree.h" #include "globals.h" #include "incore.h" #include "agheader.h" @@ -72,8 +73,8 @@ static rt_ext_flist_t rt_ext_flist; static avl64tree_desc_t *rt_ext_tree_ptr; /* dup extent tree for rt */ -avltree_desc_t **extent_tree_ptrs; /* array of extent tree ptrs */ - /* one per ag for dups */ +static struct btree_root **dup_extent_trees; /* per ag dup extent trees */ + static avltree_desc_t **extent_bno_ptrs; /* * array of extent tree ptrs * one per ag for free extents @@ -99,6 +100,48 @@ static pthread_mutex_t ext_flist_lock; static pthread_mutex_t rt_ext_tree_lock; static pthread_mutex_t rt_ext_flist_lock; +/* + * duplicate extent tree functions + */ + +void +release_dup_extent_tree( + xfs_agnumber_t agno) +{ + btree_clear(dup_extent_trees[agno]); +} + +int +add_dup_extent( + xfs_agnumber_t agno, + xfs_agblock_t startblock, + xfs_extlen_t blockcount) +{ +#ifdef XR_DUP_TRACE + fprintf(stderr, "Adding dup extent - %d/%d %d\n", agno, startblock, + blockcount); +#endif + return btree_insert(dup_extent_trees[agno], startblock, + (void *)(uintptr_t)(startblock + blockcount)); +} + +int +search_dup_extent( + xfs_agnumber_t agno, + xfs_agblock_t start_agbno, + xfs_agblock_t end_agbno) +{ + unsigned long bno; + + if (!btree_find(dup_extent_trees[agno], start_agbno, &bno)) + return 0; /* this really shouldn't happen */ + if (bno < end_agbno) + return 1; + return (uintptr_t)btree_peek_prev(dup_extent_trees[agno], NULL) > + start_agbno; +} + + /* * extent tree stuff is avl trees of duplicate extents, * sorted in order by block number. there is one tree per ag. @@ -210,14 +253,6 @@ release_extent_tree(avltree_desc_t *tree) /* * top-level (visible) routines */ -void -release_dup_extent_tree(xfs_agnumber_t agno) -{ - release_extent_tree(extent_tree_ptrs[agno]); - - return; -} - void release_agbno_extent_tree(xfs_agnumber_t agno) { @@ -522,93 +557,6 @@ get_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, return(ext); } -/* - * the next 2 routines manage the trees of duplicate extents -- 1 tree - * per AG - */ -void -add_dup_extent(xfs_agnumber_t agno, xfs_agblock_t startblock, - xfs_extlen_t blockcount) -{ - extent_tree_node_t *first, *last, *ext, *next_ext; - xfs_agblock_t new_startblock; - xfs_extlen_t new_blockcount; - - ASSERT(agno < glob_agcount); - -#ifdef XR_DUP_TRACE - fprintf(stderr, "Adding dup extent - %d/%d %d\n", agno, startblock, blockcount); -#endif - avl_findranges(extent_tree_ptrs[agno], startblock - 1, - startblock + blockcount + 1, - (avlnode_t **) &first, (avlnode_t **) &last); - /* - * find adjacent and overlapping extent blocks - */ - if (first == NULL && last == NULL) { - /* nothing, just make and insert new extent */ - - ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_MULT); - - if (avl_insert(extent_tree_ptrs[agno], - (avlnode_t *) ext) == NULL) { - do_error(_("duplicate extent range\n")); - } - - return; - } - - ASSERT(first != NULL && last != NULL); - - /* - * find the new composite range, delete old extent nodes - * as we go - */ - new_startblock = startblock; - new_blockcount = blockcount; - - for (ext = first; - ext != (extent_tree_node_t *) last->avl_node.avl_nextino; - ext = next_ext) { - /* - * preserve the next inorder node - */ - next_ext = (extent_tree_node_t *) ext->avl_node.avl_nextino; - /* - * just bail if the new extent is contained within an old one - */ - if (ext->ex_startblock <= startblock && - ext->ex_blockcount >= blockcount) - return; - /* - * now check for overlaps and adjacent extents - */ - if (ext->ex_startblock + ext->ex_blockcount >= startblock - || ext->ex_startblock <= startblock + blockcount) { - - if (ext->ex_startblock < new_startblock) - new_startblock = ext->ex_startblock; - - if (ext->ex_startblock + ext->ex_blockcount > - new_startblock + new_blockcount) - new_blockcount = ext->ex_startblock + - ext->ex_blockcount - - new_startblock; - - avl_delete(extent_tree_ptrs[agno], (avlnode_t *) ext); - continue; - } - } - - ext = mk_extent_tree_nodes(new_startblock, new_blockcount, XR_E_MULT); - - if (avl_insert(extent_tree_ptrs[agno], (avlnode_t *) ext) == NULL) { - do_error(_("duplicate extent range\n")); - } - - return; -} - static __psunsigned_t avl_ext_start(avlnode_t *node) { @@ -904,10 +852,9 @@ incore_ext_init(xfs_mount_t *mp) pthread_mutex_init(&rt_ext_tree_lock, NULL); pthread_mutex_init(&rt_ext_flist_lock, NULL); - if ((extent_tree_ptrs = malloc(agcount * - sizeof(avltree_desc_t *))) == NULL) - do_error( - _("couldn't malloc dup extent tree descriptor table\n")); + dup_extent_trees = calloc(agcount, sizeof(struct btree_root *)); + if (!dup_extent_trees) + do_error(_("couldn't malloc dup extent tree descriptor table\n")); if ((extent_bno_ptrs = malloc(agcount * sizeof(avltree_desc_t *))) == NULL) @@ -920,10 +867,6 @@ incore_ext_init(xfs_mount_t *mp) _("couldn't malloc free by-bcnt extent tree descriptor table\n")); for (i = 0; i < agcount; i++) { - if ((extent_tree_ptrs[i] = - malloc(sizeof(avltree_desc_t))) == NULL) - do_error( - _("couldn't malloc dup extent tree descriptor\n")); if ((extent_bno_ptrs[i] = malloc(sizeof(avltree_desc_t))) == NULL) do_error( @@ -935,7 +878,7 @@ incore_ext_init(xfs_mount_t *mp) } for (i = 0; i < agcount; i++) { - avl_init_tree(extent_tree_ptrs[i], &avl_extent_tree_ops); + btree_init(&dup_extent_trees[i]); avl_init_tree(extent_bno_ptrs[i], &avl_extent_tree_ops); avl_init_tree(extent_bcnt_ptrs[i], &avl_extent_bcnt_tree_ops); } @@ -964,18 +907,18 @@ incore_ext_teardown(xfs_mount_t *mp) free(cur); for (i = 0; i < mp->m_sb.sb_agcount; i++) { - free(extent_tree_ptrs[i]); + btree_destroy(dup_extent_trees[i]); free(extent_bno_ptrs[i]); free(extent_bcnt_ptrs[i]); } + free(dup_extent_trees); free(extent_bcnt_ptrs); free(extent_bno_ptrs); - free(extent_tree_ptrs); - extent_bcnt_ptrs = extent_bno_ptrs = extent_tree_ptrs = NULL; - - return; + dup_extent_trees = NULL; + extent_bcnt_ptrs = NULL; + extent_bno_ptrs = NULL; } int diff --git a/repair/scan.c b/repair/scan.c index f8b67762e..158fb4363 100644 --- a/repair/scan.c +++ b/repair/scan.c @@ -286,8 +286,9 @@ _("bad back (left) sibling pointer (saw %llu should be NULL (0))\n" * filesystem */ if (type != XR_INO_RTDATA || whichfork != XFS_DATA_FORK) { - if (search_dup_extent(mp, XFS_FSB_TO_AGNO(mp, bno), - XFS_FSB_TO_AGBNO(mp, bno))) + if (search_dup_extent(XFS_FSB_TO_AGNO(mp, bno), + XFS_FSB_TO_AGBNO(mp, bno), + XFS_FSB_TO_AGBNO(mp, bno) + 1)) return(1); } else { if (search_rt_dup_extent(mp, bno)) -- 2.39.5