From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758617Ab3EUApt (ORCPT ); Mon, 20 May 2013 20:45:49 -0400 Received: from shadbolt.e.decadent.org.uk ([88.96.1.126]:34602 "EHLO shadbolt.e.decadent.org.uk" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755993Ab3EUApr (ORCPT ); Mon, 20 May 2013 20:45:47 -0400 Message-ID: <1369097142.3469.135.camel@deadeye.wl.decadent.org.uk> Subject: [PATCH 4/5] perf: net_dropmonitor: Use bisection in symbol lookup From: Ben Hutchings To: Peter Zijlstra , Paul Mackerras , Ingo Molnar Cc: Neil Horman , netdev@vger.kernel.org, linux-kernel@vger.kernel.org Date: Tue, 21 May 2013 01:45:42 +0100 In-Reply-To: <1369096976.3469.131.camel@deadeye.wl.decadent.org.uk> References: <1369096976.3469.131.camel@deadeye.wl.decadent.org.uk> Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-tRevJHoDC/9C2G3h77db" X-Mailer: Evolution 3.4.4-2 Mime-Version: 1.0 X-SA-Exim-Connect-IP: 192.168.4.101 X-SA-Exim-Mail-From: ben@decadent.org.uk X-SA-Exim-Scanned: No (on shadbolt.decadent.org.uk); SAEximRunCond expanded to false Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org --=-tRevJHoDC/9C2G3h77db Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Signed-off-by: Ben Hutchings --- 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/scri= pts/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(): =20 def get_sym(sloc): loc =3D int(sloc) - for symloc, name in kallsyms[::-1]: - if loc >=3D symloc: - return (name, loc - symloc) - return (None, 0) + + # Invariant: kallsyms[i][0] <=3D loc for all 0 <=3D i <=3D start + # kallsyms[i][0] > loc for all end <=3D i < len(kallsyms) + start, end =3D -1, len(kallsyms) + while end !=3D start + 1: + pivot =3D (start + end) // 2 + if loc < kallsyms[pivot][0]: + end =3D pivot + else: + start =3D pivot + + # Now (start =3D=3D -1 or kallsyms[start][0] <=3D loc) + # and (start =3D=3D len(kallsyms) - 1 or loc < kallsyms[start + 1][0]) + if start >=3D 0: + symloc, name =3D kallsyms[start] + return (name, loc - symloc) + else: + return (None, 0) =20 def print_drop_table(): print "%25s %25s %25s" % ("LOCATION", "OFFSET", "COUNT") --=-tRevJHoDC/9C2G3h77db Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQIVAwUAUZrDtue/yOyVhhEJAQo5Pg/7BB10z6arw8/D4E00yEqX8i6ctFnFr8ZJ le4efiyGRgFRAHfiYELLXbZPBUn77SumPWeO4Xj5YskARxDUSpJMYN7JStVUx+j6 zS/80usc7TvXbG0SWSHFp/e6fsrgNDtn5HnNWAxo1YugbhMqPZyPE9QhhoQgneFR rA1MncNMNKfA+EW/BfWKKjoIAR3yOLtbBuSFacr2c161IkNZ1RAgWpYmpQnTFhk8 eBlgB+MMbFrW3gOKKT1RcFXe86dhbltdAgA1L3ELA5qJn04M/EHmDsqnZ/njpNkw DEmzIFWtr1m52epGZGxfce1VKuDq2Y2jxdozBbafRkKSMTJvihDVx7RKO1RnDknf ODa170kpJJtmrX6c7XrGGhuN5Rj2QL3i6swDt0EF093c+qINRYcD9S7DAxg8eL9A Y2bgy+l6pqr3WPhQNVIJ/GfAa7T+gfmkr8jmqG8ucBosSTBoRNiQ99emQNGGaUdr NGJgrcMmojIKAM+KVBU/ooT31u0amRxvjEaohR5a4Us22ldWdL9ifH92IDRz/w/n jIf0So2lhYBNTnOoNGS6pAlH+iYPf/9Uvir9BZaAqy/Td68n4+Ih5IfUgxkJfbwd j6v79U3vCfdrB2PGmtbRCV2eevgAqyVYNy06Ad0xyFh8ealTXt6aOZ35Afuf3jzW +qdeCnqGBaE= =k9t0 -----END PGP SIGNATURE----- --=-tRevJHoDC/9C2G3h77db--