|
From: <sv...@va...> - 2005-05-02 09:43:48
|
Author: sewardj
Date: 2005-05-02 10:43:44 +0100 (Mon, 02 May 2005)
New Revision: 3589
Modified:
trunk/coregrind/vg_symtab2.c
Log:
Sort the CFI summary table and do lookups in it using binary search.
Modified: trunk/coregrind/vg_symtab2.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/coregrind/vg_symtab2.c 2005-05-02 00:36:27 UTC (rev 3588)
+++ trunk/coregrind/vg_symtab2.c 2005-05-02 09:43:44 UTC (rev 3589)
@@ -805,6 +805,26 @@
}
=20
=20
+/* Sort the call-frame-info table by starting address. Mash the table
+ around so as to establish the property that addresses are in order
+ and the ranges do not overlap. This facilitates using binary
+ search to map addresses to locations when we come to query the
+ table. =20
+
+ Also, set cfisi_minaddr and cfisi_maxaddr to be the min and max of
+ any of the address ranges contained in cfisi[0 .. cfisi_used-1], so
+ as to facilitate rapidly skipping this SegInfo when looking for an
+ address which falls outside that range.
+*/
+static Int compare_CfiSI(void *va, void *vb) {
+ CfiSI *a =3D (CfiSI*)va;
+ CfiSI *b =3D (CfiSI*)vb;
+
+ if (a->base < b->base) return -1;
+ if (a->base > b->base) return 1;
+ return 0;
+}
+
static
void canonicaliseCfiSI ( SegInfo* si )
{
@@ -826,6 +846,28 @@
}
VG_(printf)("%d entries, %p .. %p\n", si->cfisi_used,
si->cfisi_minaddr, si->cfisi_maxaddr);
+
+ /* Sort the cfisi array by base address. */
+ VG_(ssort)(si->cfisi, si->cfisi_used, sizeof(*si->cfisi), compare_Cfi=
SI);
+
+ /* Ensure relevant postconditions hold. */
+ for (i =3D 0; i < si->cfisi_used; i++) {
+ /* No zero-length ranges. */
+ vg_assert(si->cfisi[i].len > 0);
+ /* Makes sense w.r.t. summary address range */
+ vg_assert(si->cfisi[i].base >=3D si->cfisi_minaddr);
+ vg_assert(si->cfisi[i].base + si->cfisi[i].len - 1
+ <=3D si->cfisi_maxaddr);
+
+ if (i < si->cfisi_used - 1) {
+ /* In order. */
+ vg_assert(si->cfisi[i].base < si->cfisi[i+1].base);
+ /* No overlaps. */
+ vg_assert(si->cfisi[i].base + si->cfisi[i].len - 1
+ < si->cfisi[i+1].base);
+ }
+ }
+
}
=20
=20
@@ -2005,6 +2047,32 @@
VGP_POPCC(VgpSearchSyms);
}
=20
+
+/* Find a CFI-table index containing the specified pointer, or -1
+ if not found. Binary search. */
+
+static Int search_one_cfitab ( SegInfo* si, Addr ptr )
+{
+ Addr a_mid_lo, a_mid_hi;
+ Int mid, size,=20
+ lo =3D 0,=20
+ hi =3D si->cfisi_used-1;
+ while (True) {
+ /* current unsearched space is from lo to hi, inclusive. */
+ if (lo > hi) return -1; /* not found */
+ mid =3D (lo + hi) / 2;
+ a_mid_lo =3D si->cfisi[mid].base;
+ size =3D si->cfisi[mid].len;
+ a_mid_hi =3D a_mid_lo + size - 1;
+ vg_assert(a_mid_hi >=3D a_mid_lo);
+ if (ptr < a_mid_lo) { hi =3D mid-1; continue; }=20
+ if (ptr > a_mid_hi) { lo =3D mid+1; continue; }
+ vg_assert(ptr >=3D a_mid_lo && ptr <=3D a_mid_hi);
+ return mid;
+ }
+}
+
+
/* The whole point of this whole big deal: map a code address to a
plausible symbol name. Returns False if no idea; otherwise True.
Caller supplies buf and nbuf. If demangle is False, don't do
@@ -2367,22 +2435,14 @@
if (*ipP < si->cfisi_minaddr || *ipP > si->cfisi_maxaddr)
continue;
=20
- for (i =3D 0; i < si->cfisi_used; i++) {
-
- if (0) {static Int searches=3D0;
- searches++;
- if (searches % 10000000 =3D=3D 0) VG_(printf)("%d searches\n", search=
es);
- }
-
- if (si->cfisi[i].base <=3D *ipP
- && *ipP < si->cfisi[i].base+si->cfisi[i].len) {
- cfisi =3D &si->cfisi[i];
- goto postloop;
- }
+ i =3D search_one_cfitab( si, *ipP );
+ if (i !=3D -1) {
+ vg_assert(i >=3D 0 && i < si->cfisi_used);
+ cfisi =3D &si->cfisi[i];
+ break;
}
}
=20
- postloop:
if (cfisi =3D=3D NULL)
return False;
=20
|