summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBen Hutchings <ben@decadent.org.uk>2013-05-20 14:45:42 +0000
committerDavid S. Miller <davem@davemloft.net>2013-05-22 15:10:10 -0700
commit0ce58bae851dc3728af1c0b83905cd6b4565417a (patch)
tree3fd036c3c7219f200cd45d859ae97e4e7989cce1
parent326017c757e387007c6629797d7ae22fd33c1317 (diff)
perf: net_dropmonitor: Use bisection in symbol lookup
Signed-off-by: Ben Hutchings <ben@decadent.org.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
-rwxr-xr-xtools/perf/scripts/python/net_dropmonitor.py22
1 files changed, 18 insertions, 4 deletions
diff --git a/tools/perf/scripts/python/net_dropmonitor.py b/tools/perf/scripts/python/net_dropmonitor.py
index 6acdc82ef47f..32fcee05c0f6 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")