linux-ext4 - [PATCH 2/3] libext2fs: further optimize rb_test

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri,  5 Oct 2012 22:04:11 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	Ext4 Developers List <linux-ext4@...r.kernel.org>
Cc:	Theodore Ts'o <tytso@....edu>
Subject: [PATCH 2/3] libext2fs: further optimize rb_test_bit

Profiling shows that rb_test_bit() is now calling ext2fs_rb_next() a
lot, and this function is now the hot spot when running e2freefrag.
If we cache the results of ext2fs_rb_next(), we can eliminate those
extra calls, which further speeds up both e2freefrag and e2fsck by
reducing the amount of CPU time spent in userspace.

Signed-off-by: "Theodore Ts'o" <tytso@....edu>
---
 lib/ext2fs/blkmap64_rb.c | 23 +++++++++++++++++++----
 1 file changed, 19 insertions(+), 4 deletions(-)

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 900c0d3..40d982f 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -40,6 +40,7 @@ struct ext2fs_rb_private {
 	struct rb_root root;
 	struct bmap_rb_extent *wcursor;
 	struct bmap_rb_extent *rcursor;
+	struct bmap_rb_extent *rcursor_next;
 #ifdef BMAP_STATS_OPS
 	__u64 mark_hit;
 	__u64 test_hit;
@@ -152,6 +153,8 @@ static void rb_free_extent(struct ext2fs_rb_private *bp,
 		bp->wcursor = NULL;
 	if (bp->rcursor == ext)
 		bp->rcursor = NULL;
+	if (bp->rcursor_next == ext)
+		bp->rcursor_next = NULL;
 	ext2fs_free_mem(&ext);
 }
 
@@ -166,6 +169,7 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
 
 	bp->root = RB_ROOT;
 	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 	bp->wcursor = NULL;
 
 #ifdef BMAP_STATS_OPS
@@ -306,7 +310,7 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
 inline static int
 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 {
-	struct bmap_rb_extent *rcursor, *next_ext;
+	struct bmap_rb_extent *rcursor, *next_ext = NULL;
 	struct rb_node *parent = NULL, *next;
 	struct rb_node **n = &bp->root.rb_node;
 	struct bmap_rb_extent *ext;
@@ -322,9 +326,15 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 		return 1;
 	}
 
-	next = ext2fs_rb_next(&rcursor->node);
-	if (next) {
-		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
+	next_ext = bp->rcursor_next;
+	if (!next_ext) {
+		next = ext2fs_rb_next(&rcursor->node);
+		if (next)
+			next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent,
+						   node);
+		bp->rcursor_next = next_ext;
+	}
+	if (next_ext) {
 		if ((bit >= rcursor->start + rcursor->count) &&
 		    (bit < next_ext->start)) {
 #ifdef BMAP_STATS_OPS
@@ -333,6 +343,8 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 			return 0;
 		}
 	}
+	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 
 	rcursor = bp->wcursor;
 	if (!rcursor)
@@ -352,6 +364,7 @@ search_tree:
 			n = &(*n)->rb_right;
 		else {
 			bp->rcursor = ext;
+			bp->rcursor_next = 0;
 			return 1;
 		}
 	}
@@ -368,6 +381,7 @@ static int rb_insert_extent(__u64 start, __u64 count,
 	struct bmap_rb_extent *ext;
 	int retval = 0;
 
+	bp->rcursor_next = NULL;
 	ext = bp->wcursor;
 	if (ext) {
 		if (start >= ext->start &&
@@ -738,6 +752,7 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
 
 	rb_free_tree(&bp->root);
 	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 	bp->wcursor = NULL;
 }
 
-- 
1.7.12.rc0.22.gcdd159b

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html