linux-kernel - Re: [RFC PATCH 00/10] x86: undwarf unwinder

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: Windows password security audit tool. GUI, reports in PDF.

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

Date:   Tue, 6 Jun 2017 23:14:24 +0900
From:   Sergey Senozhatsky <sergey.senozhatsky.work@...il.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Josh Poimboeuf <jpoimboe@...hat.com>,
        Ingo Molnar <mingo@...nel.org>, x86@...nel.org,
        linux-kernel@...r.kernel.org, live-patching@...r.kernel.org,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Andy Lutomirski <luto@...nel.org>, Jiri Slaby <jslaby@...e.cz>,
        "H. Peter Anvin" <hpa@...or.com>,
        Sergey Senozhatsky <sergey.senozhatsky@...il.com>
Subject: Re: [RFC PATCH 00/10] x86: undwarf unwinder

On (06/01/17 15:25), Peter Zijlstra wrote:
[..]
> On Thu, Jun 01, 2017 at 07:47:05AM -0500, Josh Poimboeuf wrote:
> 
> > > It doesn't appear to be possible to get anywhere near a frame-pointer
> > > unwinder due to having to do this log(n) lookup for every single
> > > frame.
> > 
> > Hm, is there something faster, yet not substantially bigger?  Hash?
> > Trie?
> 
> Not sure how to make a Hash work with nearest neighbour searches. And a
> trie will only give you a constant speedup over the binary search but
> not an improvement in complexity IIRC.

by the way, as far as I know, there is *a bit* faster bsearch(). basically
there is a way to calculate pivot (middle element) using less instructions.

something like below, perhaps... may be can give some extra performance.
(not really tested. but I believe this is close to what gcc does in
libstdc++).


======

./scripts/bloat-o-meter lib/bsearch.o.old lib/bsearch.o.new
add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-24 (-24)
function                                     old     new   delta
bsearch                                      122      98     -24

---
 lib/bsearch.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index e33c179089db..18b445b010c3 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -33,19 +33,21 @@
 void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	      int (*cmp)(const void *key, const void *elt))
 {
-	size_t start = 0, end = num;
+	const char *pivot;
 	int result;
 
-	while (start < end) {
-		size_t mid = start + (end - start) / 2;
+	while (num > 0) {
+		pivot = base + (num >> 1) * size;
+		result = cmp(key, pivot);
 
-		result = cmp(key, base + mid * size);
-		if (result < 0)
-			end = mid;
-		else if (result > 0)
-			start = mid + 1;
-		else
-			return (void *)base + mid * size;
+		if (result == 0)
+			return (void *)pivot;
+
+		if (result > 0) {
+			base = pivot + size;
+			num--;
+		}
+		num >>= 1;
 	}
 
 	return NULL;
-- 
2.13.1