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 <bnaujok@sgi.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
diff --git a/repair/dinode.c b/repair/dinode.c
index 980d3c3..bf04c6e 100644
--- a/repair/dinode.c
+++ b/repair/dinode.c
@@ -735,18 +735,14 @@
* 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 503d920..7f4f60c 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.
@@ -179,23 +181,11 @@
/*
* 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 a2acbf4..dad9995 100644
--- a/repair/incore_ext.c
+++ b/repair/incore_ext.c
@@ -18,6 +18,7 @@
#include <libxfs.h>
#include "avl.h"
+#include "btree.h"
#include "globals.h"
#include "incore.h"
#include "agheader.h"
@@ -72,8 +73,8 @@
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
@@ -100,6 +101,48 @@
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.
*/
@@ -211,14 +254,6 @@
* 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)
{
release_extent_tree(extent_bno_ptrs[agno]);
@@ -522,93 +557,6 @@
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)
{
@@ -901,10 +849,9 @@
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)
@@ -917,10 +864,6 @@
_("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(
@@ -932,7 +875,7 @@
}
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);
}
@@ -959,18 +902,18 @@
free_allocations(ba_list);
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 21fba74..8255b0b 100644
--- a/repair/scan.c
+++ b/repair/scan.c
@@ -286,8 +286,9 @@
* 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))
