linux-kernel - [PATCH 2/2] xfs: replace homemade binary search

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:   Sat, 19 Oct 2019 09:20:33 +0200
From:   Thomas Meyer <thomas@...3r.de>
To:     linux-kernel@...r.kernel.org, linux-xfs@...r.kernel.org
Cc:     Thomas Meyer <thomas@...3r.de>
Subject: [PATCH 2/2] xfs: replace homemade binary search

use newly introduced bsearch_idx instead.

Signed-off-by: Thomas Meyer <thomas@...3r.de>
---
 fs/xfs/libxfs/xfs_dir2_block.c | 30 ++++++++++++++++++------------
 1 file changed, 18 insertions(+), 12 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_dir2_block.c b/fs/xfs/libxfs/xfs_dir2_block.c
index 9595ced393dce..e484ec68944fb 100644
--- a/fs/xfs/libxfs/xfs_dir2_block.c
+++ b/fs/xfs/libxfs/xfs_dir2_block.c
@@ -20,6 +20,7 @@
 #include "xfs_error.h"
 #include "xfs_trace.h"
 #include "xfs_log.h"
+#include <linux/bsearch.h>
 
 /*
  * Local function prototypes.
@@ -314,6 +315,19 @@ xfs_dir2_block_compact(
 		xfs_dir2_data_freescan(args->dp, hdr, needlog);
 }
 
+static int cmp_hashval(const void *key, const void *elt)
+{
+	xfs_dahash_t _search_key = *(xfs_dahash_t *)key;
+	xfs_dahash_t _curren_key = be32_to_cpu((
+				(xfs_dir2_leaf_entry_t *) elt)->hashval);
+
+	if (_search_key == _curren_key)
+		return 0;
+	else if (_search_key < _curren_key)
+		return -1;
+	return 1;
+}
+
 /*
  * Add an entry to a block directory.
  */
@@ -331,19 +345,17 @@ xfs_dir2_block_addname(
 	xfs_dir2_data_unused_t	*dup;		/* block unused entry */
 	int			error;		/* error return value */
 	xfs_dir2_data_unused_t	*enddup=NULL;	/* unused at end of data */
-	xfs_dahash_t		hash;		/* hash value of found entry */
-	int			high;		/* high index for binary srch */
 	int			highstale;	/* high stale index */
 	int			lfloghigh=0;	/* last final leaf to log */
 	int			lfloglow=0;	/* first final leaf to log */
 	int			len;		/* length of the new entry */
-	int			low;		/* low index for binary srch */
 	int			lowstale;	/* low stale index */
 	int			mid=0;		/* midpoint for binary srch */
 	int			needlog;	/* need to log header */
 	int			needscan;	/* need to rescan freespace */
 	__be16			*tagp;		/* pointer to tag value */
 	xfs_trans_t		*tp;		/* transaction structure */
+	struct bsearch_result	idx;		/* bsearch result */
 
 	trace_xfs_dir2_block_addname(args);
 
@@ -420,15 +432,9 @@ xfs_dir2_block_addname(
 	/*
 	 * Find the slot that's first lower than our hash value, -1 if none.
 	 */
-	for (low = 0, high = be32_to_cpu(btp->count) - 1; low <= high; ) {
-		mid = (low + high) >> 1;
-		if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
-			break;
-		if (hash < args->hashval)
-			low = mid + 1;
-		else
-			high = mid - 1;
-	}
+	idx = bsearch_idx(&args->hashval, blp, be32_to_cpu(btp->count) - 1,
+			  sizeof(xfs_dir2_leaf_entry_t), cmp_hashval);
+	mid = idx.idx;
 	while (mid >= 0 && be32_to_cpu(blp[mid].hashval) >= args->hashval) {
 		mid--;
 	}
-- 
2.21.0