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))