|
From: <sv...@va...> - 2012-08-03 23:11:47
|
philippe 2012-08-04 00:11:39 +0100 (Sat, 04 Aug 2012)
New Revision: 12824
Log:
fix 284540 (optimise suppression matching)
Before this patch, matching an error stack trace with many suppression
patterns was implying to repeating the translation of the IPs of the
stack trace to the function name or object name for each suppr pattern.
This patch introduces a "lazy input completer" in the generic match
so that an IP is (in the worst case) translated once to its function
name and once to its object name.
It is a "lazy" completer in the sense that only the needed IP to fun or obj
name are done.
On a artificial test case, has given a factor 3 in performance.
On another big (real) application, gave a factor 2 to 3.
(there was less matching to do, but probably more debug info to search).
match-overrun.supp completed to have non matching suppr first to
better exercise the lazy completer.
Modified files:
trunk/NEWS
trunk/coregrind/m_errormgr.c
trunk/coregrind/m_seqmatch.c
trunk/include/pub_tool_seqmatch.h
trunk/memcheck/tests/match-overrun.supp
Modified: trunk/memcheck/tests/match-overrun.supp (+15 -0)
===================================================================
--- trunk/memcheck/tests/match-overrun.supp 2012-08-03 22:50:11 +01:00 (rev 12823)
+++ trunk/memcheck/tests/match-overrun.supp 2012-08-04 00:11:39 -23:00 (rev 12824)
@@ -1,4 +1,19 @@
{
+ nonmatching1
+ Memcheck:Addr4
+ fun:a123456789*
+ fun:nonmatching
+ fun:main
+}
+{
+ nonmatching2
+ Memcheck:Addr4
+ fun:a123456789*
+ fun:main
+ fun:nonmatching
+}
+
+{
test
Memcheck:Addr4
fun:a123456789*
Modified: trunk/coregrind/m_seqmatch.c (+9 -5)
===================================================================
--- trunk/coregrind/m_seqmatch.c 2012-08-03 22:50:11 +01:00 (rev 12823)
+++ trunk/coregrind/m_seqmatch.c 2012-08-04 00:11:39 -23:00 (rev 12824)
@@ -45,7 +45,8 @@
void* input, SizeT szbInput, UWord nInput, UWord ixInput,
Bool (*pIsStar)(void*),
Bool (*pIsQuery)(void*),
- Bool (*pattEQinp)(void*,void*)
+ Bool (*pattEQinp)(void*,void*,void*,UWord),
+ void* inputCompleter
)
{
/* This is the spec, written in my favourite formal specification
@@ -102,7 +103,8 @@
if (VG_(generic_match)( matchAll,
patt, szbPatt, nPatt, ixPatt+1,
input,szbInput,nInput, ixInput+0,
- pIsStar,pIsQuery,pattEQinp) ) {
+ pIsStar,pIsQuery,pattEQinp,
+ inputCompleter) ) {
return True;
}
// but we can tail-recurse for the second call
@@ -129,7 +131,7 @@
//
// ma (p:ps) (i:is) = p == i && ma ps is
if (havePatt && haveInput) {
- if (!pattEQinp(currPatt,currInput)) return False;
+ if (!pattEQinp(currPatt,currInput,inputCompleter,ixInput)) return False;
ixPatt++; ixInput++; goto tailcall;
}
@@ -163,7 +165,8 @@
*/
static Bool charIsStar ( void* pV ) { return *(Char*)pV == '*'; }
static Bool charIsQuery ( void* pV ) { return *(Char*)pV == '?'; }
-static Bool char_p_EQ_i ( void* pV, void* cV ) {
+static Bool char_p_EQ_i ( void* pV, void* cV,
+ void* null_completer, UWord ixcV ) {
Char p = *(Char*)pV;
Char c = *(Char*)cV;
vg_assert(p != '*' && p != '?');
@@ -175,7 +178,8 @@
True/* match-all */,
(void*)patt, sizeof(UChar), VG_(strlen)(patt), 0,
(void*)input, sizeof(UChar), VG_(strlen)(input), 0,
- charIsStar, charIsQuery, char_p_EQ_i
+ charIsStar, charIsQuery, char_p_EQ_i,
+ NULL
);
}
Modified: trunk/include/pub_tool_seqmatch.h (+8 -1)
===================================================================
--- trunk/include/pub_tool_seqmatch.h 2012-08-03 22:50:11 +01:00 (rev 12823)
+++ trunk/include/pub_tool_seqmatch.h 2012-08-04 00:11:39 -23:00 (rev 12824)
@@ -69,6 +69,12 @@
equal. Note that the pattern element is guaranteed to be neither
(conceptually) '*' nor '?', so it must be a literal (in the sense
that all the input sequence elements are literal).
+
+ input might be lazily constructed when pattEQinp is called.
+ For lazily constructing the input element, the two last arguments
+ of pattEQinp are the inputCompleter and the index of the input
+ element to complete.
+ inputCompleter can be NULL.
*/
Bool VG_(generic_match) (
Bool matchAll,
@@ -76,7 +82,8 @@
void* input, SizeT szbInput, UWord nInput, UWord ixInput,
Bool (*pIsStar)(void*),
Bool (*pIsQuery)(void*),
- Bool (*pattEQinp)(void*,void*)
+ Bool (*pattEQinp)(void*,void*,void*,UWord),
+ void* inputCompleter
);
/* Mini-regexp function. Searches for 'pat' in 'str'. Supports
Modified: trunk/NEWS (+1 -0)
===================================================================
--- trunk/NEWS 2012-08-03 22:50:11 +01:00 (rev 12823)
+++ trunk/NEWS 2012-08-04 00:11:39 -23:00 (rev 12824)
@@ -155,6 +155,7 @@
283671 Robustize alignment computation in LibVEX_Alloc
283961 Adding support for some HCI IOCTLs
284124 parse_type_DIE: confused by: DWARF 4
+284540 Optimise matching logic between an error and the suppressions
285219 Too-restrictive constraints for Thumb2 "SP plus/minus register"
286261 [patch] add wrapper for linux I2C_RDWR ioctl
286270 vgpreload is not friendly to 64->32 bit execs, gives ld.so warnings
Modified: trunk/coregrind/m_errormgr.c (+146 -28)
===================================================================
--- trunk/coregrind/m_errormgr.c 2012-08-03 22:50:11 +01:00 (rev 12823)
+++ trunk/coregrind/m_errormgr.c 2012-08-04 00:11:39 -23:00 (rev 12824)
@@ -1401,14 +1401,118 @@
return False; /* there's no '?' equivalent in the supp syntax */
}
-static Bool supp_pattEQinp ( void* supplocV, void* addrV )
+/* IPtoFunOrObjCompleter is a lazy completer of the IPs
+ needed to match an error with the suppression patterns.
+ The matching between an IP and a suppression pattern is done either
+ with the IP function name or with the IP object name.
+ First time the fun or obj name is needed for an IP member
+ of a stack trace, it will be computed and stored in names.
+ The IPtoFunOrObjCompleter type is designed to minimise the nr of
+ allocations and the nr of debuginfo search. */
+typedef
+ struct {
+ StackTrace ips; // stack trace we are lazily completing.
+ UWord n_ips; // nr of elements in ips.
+
+ Int* fun_offsets;
+ // fun_offsets[i] is the offset in names where the
+ // function name for ips[i] is located.
+ // An offset -1 means the function name is not yet completed.
+ Int* obj_offsets;
+ // Similarly, obj_offsets[i] gives the offset for the
+ // object name for ips[i] (-1 meaning object name not yet completed).
+
+ // All function names and object names will be concatenated
+ // in names. names is reallocated on demand.
+ Char *names;
+ Int names_szB; // size of names.
+ Int names_free; // offset first free Char in names.
+ }
+ IPtoFunOrObjCompleter;
+
+// free the memory in ip2fo.
+static void clearIPtoFunOrObjCompleter
+ (IPtoFunOrObjCompleter* ip2fo)
{
+ if (ip2fo->fun_offsets) VG_(free)(ip2fo->fun_offsets);
+ if (ip2fo->obj_offsets) VG_(free)(ip2fo->obj_offsets);
+ if (ip2fo->names) VG_(free)(ip2fo->names);
+}
+
+/* foComplete returns the function name or object name for IP.
+ If needFun, returns the function name for IP
+ else returns the object name for IP.
+ The function name or object name will be computed and added in
+ names if not yet done.
+ IP must be equal to focompl->ipc[ixIP]. */
+static Char* foComplete(IPtoFunOrObjCompleter* ip2fo,
+ Addr IP, Int ixIP, Bool needFun)
+{
+ vg_assert (ixIP < ip2fo->n_ips);
+ vg_assert (IP == ip2fo->ips[ixIP]);
+
+ // ptr to the offset array for function offsets (if needFun)
+ // or object offsets (if !needFun).
+ Int** offsets;
+ if (needFun)
+ offsets = &ip2fo->fun_offsets;
+ else
+ offsets = &ip2fo->obj_offsets;
+
+ // Allocate offsets if not yet done.
+ if (!*offsets) {
+ Int i;
+ *offsets =
+ VG_(malloc)("foComplete",
+ ip2fo->n_ips * sizeof(Int));
+ for (i = 0; i < ip2fo->n_ips; i++)
+ (*offsets)[i] = -1;
+ }
+
+ // Complete Fun name or Obj name for IP if not yet done.
+ if ((*offsets)[ixIP] == -1) {
+ /* Ensure we have ERRTXT_LEN characters available in names */
+ if (ip2fo->names_szB
+ < ip2fo->names_free + ERRTXT_LEN) {
+ ip2fo->names
+ = VG_(realloc)("foc_names",
+ ip2fo->names,
+ ip2fo->names_szB + ERRTXT_LEN);
+ ip2fo->names_szB += ERRTXT_LEN;
+ }
+ Char* caller_name = ip2fo->names + ip2fo->names_free;
+ (*offsets)[ixIP] = ip2fo->names_free;
+ if (needFun) {
+ /* Get the function name into 'caller_name', or "???"
+ if unknown. */
+ // Nb: C++-mangled names are used in suppressions. Do, though,
+ // Z-demangle them, since otherwise it's possible to wind
+ // up comparing "malloc" in the suppression against
+ // "_vgrZU_libcZdsoZa_malloc" in the backtrace, and the
+ // two of them need to be made to match.
+ if (!VG_(get_fnname_no_cxx_demangle)(IP, caller_name, ERRTXT_LEN))
+ VG_(strcpy)(caller_name, "???");
+ } else {
+ /* Get the object name into 'caller_name', or "???"
+ if unknown. */
+ if (!VG_(get_objname)(IP, caller_name, ERRTXT_LEN))
+ VG_(strcpy)(caller_name, "???");
+ }
+ ip2fo->names_free += VG_(strlen)(caller_name) + 1;
+ }
+
+ return ip2fo->names + (*offsets)[ixIP];
+}
+
+static Bool supp_pattEQinp ( void* supplocV, void* addrV,
+ void* inputCompleter, UWord ixAddrV )
+{
SuppLoc* supploc = (SuppLoc*)supplocV; /* PATTERN */
Addr ip = *(Addr*)addrV; /* INPUT */
+ IPtoFunOrObjCompleter* ip2fo
+ = (IPtoFunOrObjCompleter*)inputCompleter;
+ Char* funobj_name; // Fun or Obj name.
- Char caller_name[ERRTXT_LEN];
- caller_name[0] = 0;
-
/* So, does this IP address match this suppression-line? */
switch (supploc->ty) {
case DotDotDot:
@@ -1419,46 +1523,33 @@
this can't happen. */
vg_assert(0);
case ObjName:
- /* Get the object name into 'caller_name', or "???"
- if unknown. */
- if (!VG_(get_objname)(ip, caller_name, ERRTXT_LEN))
- VG_(strcpy)(caller_name, "???");
+ funobj_name = foComplete(ip2fo, ip, ixAddrV, False /*needFun*/);
break;
- case FunName:
- /* Get the function name into 'caller_name', or "???"
- if unknown. */
- // Nb: C++-mangled names are used in suppressions. Do, though,
- // Z-demangle them, since otherwise it's possible to wind
- // up comparing "malloc" in the suppression against
- // "_vgrZU_libcZdsoZa_malloc" in the backtrace, and the
- // two of them need to be made to match.
- if (!VG_(get_fnname_no_cxx_demangle)(ip, caller_name, ERRTXT_LEN))
- VG_(strcpy)(caller_name, "???");
+ case FunName:
+ funobj_name = foComplete(ip2fo, ip, ixAddrV, True /*needFun*/);
break;
default:
vg_assert(0);
}
- /* So now we have the function or object name in caller_name, and
+ /* So now we have the function or object name in funobj_name, and
the pattern (at the character level) to match against is in
supploc->name. Hence (and leading to a re-entrant call of
VG_(generic_match) if there is a wildcard character): */
if (supploc->name_is_simple_str)
- return VG_(strcmp) (supploc->name, caller_name) == 0;
+ return VG_(strcmp) (supploc->name, funobj_name) == 0;
else
- return VG_(string_match)(supploc->name, caller_name);
+ return VG_(string_match)(supploc->name, funobj_name);
}
/////////////////////////////////////////////////////
-static Bool supp_matches_callers(Error* err, Supp* su)
+static Bool supp_matches_callers(IPtoFunOrObjCompleter* ip2fo, Supp* su)
{
/* Unwrap the args and set up the correct parameterisation of
VG_(generic_match), using supploc_IsStar, supploc_IsQuery and
supp_pattEQinp. */
- /* note, StackTrace === Addr* */
- StackTrace ips = VG_(get_ExeContext_StackTrace)(err->where);
- UWord n_ips = VG_(get_ExeContext_n_ips)(err->where);
+ /* note, StackTrace ip2fo->ips === Addr* */
SuppLoc* supps = su->callers;
UWord n_supps = su->n_callers;
UWord szbPatt = sizeof(SuppLoc);
@@ -1468,8 +1559,9 @@
VG_(generic_match)(
matchAll,
/*PATT*/supps, szbPatt, n_supps, 0/*initial Ix*/,
- /*INPUT*/ips, szbInput, n_ips, 0/*initial Ix*/,
- supploc_IsStar, supploc_IsQuery, supp_pattEQinp
+ /*INPUT*/ip2fo->ips, szbInput, ip2fo->n_ips, 0/*initial Ix*/,
+ supploc_IsStar, supploc_IsQuery, supp_pattEQinp,
+ ip2fo
);
}
@@ -1506,14 +1598,38 @@
Supp* su;
Supp* su_prev;
+ IPtoFunOrObjCompleter ip2fo;
+ /* Conceptually, ip2fo contains an array of function names and an array of
+ object names, corresponding to the array of IP of err->where.
+ These names are just computed 'on demand' (so once maximum),
+ then stored (efficiently, avoiding too many allocs) in ip2fo to be re-usable
+ for the matching of the same IP with the next suppression pattern.
+
+ VG_(generic_match) gets this 'IP to Fun or Obj name completer' as one
+ of its arguments. It will then pass it to the function
+ supp_pattEQinp which will then lazily complete the IP function name or
+ object name inside ip2fo. Next time the fun or obj name for the same
+ IP is needed (i.e. for the matching with the next suppr pattern), then
+ the fun or obj name will not be searched again in the debug info. */
+
/* stats gathering */
em_supplist_searches++;
+ /* Prepare the lazy input completer. */
+ ip2fo.ips = VG_(get_ExeContext_StackTrace)(err->where);
+ ip2fo.n_ips = VG_(get_ExeContext_n_ips)(err->where);
+ ip2fo.fun_offsets = NULL;
+ ip2fo.obj_offsets = NULL;
+ ip2fo.names = NULL;
+ ip2fo.names_szB = 0;
+ ip2fo.names_free = 0;
+
/* See if the error context matches any suppression. */
su_prev = NULL;
for (su = suppressions; su != NULL; su = su->next) {
em_supplist_cmps++;
- if (supp_matches_error(su, err) && supp_matches_callers(err, su)) {
+ if (supp_matches_error(su, err)
+ && supp_matches_callers(&ip2fo, su)) {
/* got a match. Move this entry to the head of the list
in the hope of making future searches cheaper. */
if (su_prev) {
@@ -1522,10 +1638,12 @@
su->next = suppressions;
suppressions = su;
}
+ clearIPtoFunOrObjCompleter(&ip2fo);
return su;
}
su_prev = su;
}
+ clearIPtoFunOrObjCompleter(&ip2fo);
return NULL; /* no matches */
}
|