netdev - [PATCH 4/5] perf: net_dropmonitor: Use bisection in symbol lookup

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]

Message-ID: <1369097142.3469.135.camel@deadeye.wl.decadent.org.uk>
Date:	Tue, 21 May 2013 01:45:42 +0100
From:	Ben Hutchings <ben@...adent.org.uk>
To:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Paul Mackerras <paulus@...ba.org>,
	Ingo Molnar <mingo@...hat.com>
Cc:	Neil Horman <nhorman@...driver.com>, netdev@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: [PATCH 4/5] perf: net_dropmonitor: Use bisection in symbol lookup

Signed-off-by: Ben Hutchings <ben@...adent.org.uk>
---
 tools/perf/scripts/python/net_dropmonitor.py |   22 ++++++++++++++++++----
 1 file changed, 18 insertions(+), 4 deletions(-)

diff --git a/tools/perf/scripts/python/net_dropmonitor.py b/tools/perf/scripts/python/net_dropmonitor.py
index 6acdc82e..32fcee0 100755
--- a/tools/perf/scripts/python/net_dropmonitor.py
+++ b/tools/perf/scripts/python/net_dropmonitor.py
@@ -40,10 +40,24 @@ def get_kallsyms_table():
 
 def get_sym(sloc):
 	loc = int(sloc)
-	for symloc, name in kallsyms[::-1]:
-		if loc >= symloc:
-			return (name, loc - symloc)
-	return (None, 0)
+
+	# Invariant: kallsyms[i][0] <= loc for all 0 <= i <= start
+	#            kallsyms[i][0] > loc for all end <= i < len(kallsyms)
+	start, end = -1, len(kallsyms)
+	while end != start + 1:
+		pivot = (start + end) // 2
+		if loc < kallsyms[pivot][0]:
+			end = pivot
+		else:
+			start = pivot
+
+	# Now (start == -1 or kallsyms[start][0] <= loc)
+	# and (start == len(kallsyms) - 1 or loc < kallsyms[start + 1][0])
+	if start >= 0:
+		symloc, name = kallsyms[start]
+		return (name, loc - symloc)
+	else:
+		return (None, 0)
 
 def print_drop_table():
 	print "%25s %25s %25s" % ("LOCATION", "OFFSET", "COUNT")



Download attachment "signature.asc" of type "application/pgp-signature" (829 bytes)