| Message ID | 1a6ab914-e2b9-8735-deda-246c7afb9ccc@gmx.de |
|---|---|
| State | New |
| Headers | show |
| Series | Fix slowness in demangler | expand |
On Tue, Nov 12, 2019 at 6:15 AM Tim Rühsen <tim.ruehsen@gmx.de> wrote: > > this is a proposal to fix > https://sourceware.org/bugzilla/show_bug.cgi?id=25180 > > In short: > cxxfilt > _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo > > takes several minutes with 100% CPU before it comes back with a result. > > With this patch the result is returned immediately. The test suite in > binutils-gdb/libiberty/ throws no error. > > I'd like to note that I am not subscribed to the list, so please add me > to CC when replying. Thanks in advance. This is OK with an appropriate ChangeLog entry. Thanks. Ian
On 11/12/19 4:15 PM, Ian Lance Taylor wrote: > On Tue, Nov 12, 2019 at 6:15 AM Tim Rühsen <tim.ruehsen@gmx.de> wrote: >> >> this is a proposal to fix >> https://sourceware.org/bugzilla/show_bug.cgi?id=25180 >> >> In short: >> cxxfilt >> _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo >> >> takes several minutes with 100% CPU before it comes back with a result. >> >> With this patch the result is returned immediately. The test suite in >> binutils-gdb/libiberty/ throws no error. >> >> I'd like to note that I am not subscribed to the list, so please add me >> to CC when replying. Thanks in advance. > > This is OK with an appropriate ChangeLog entry. Thanks for feedback, Ian. Attached is the patch with a ChangeLog entry. Regards, Tim
On 11/12/19 9:39 AM, Tim Rühsen wrote: > On 11/12/19 4:15 PM, Ian Lance Taylor wrote: >> On Tue, Nov 12, 2019 at 6:15 AM Tim Rühsen <tim.ruehsen@gmx.de> wrote: >>> this is a proposal to fix >>> https://sourceware.org/bugzilla/show_bug.cgi?id=25180 >>> >>> In short: >>> cxxfilt >>> _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo >>> >>> takes several minutes with 100% CPU before it comes back with a result. >>> >>> With this patch the result is returned immediately. The test suite in >>> binutils-gdb/libiberty/ throws no error. >>> >>> I'd like to note that I am not subscribed to the list, so please add me >>> to CC when replying. Thanks in advance. >> This is OK with an appropriate ChangeLog entry. > Thanks for feedback, Ian. > > Attached is the patch with a ChangeLog entry. > > Regards, Tim > > > 0001-Fix-demangler-slowness-issue.patch > > From 1311f0499ff0a5353e3201587e1e50c9b9cc58c2 Mon Sep 17 00:00:00 2001 > From: =?UTF-8?q?Tim=20R=C3=BChsen?= <tim.ruehsen@gmx.de> > Date: Tue, 12 Nov 2019 13:10:47 +0100 > Subject: [PATCH] Fix demangler slowness issue > > Fixes #25180 (binutils bugtracker) > > The demangler works with two passes. The first one is for counting > certain items. It was missing the protection against traversing subtrees > multiple times without reaching the recursion limit. The second pass > had this protection. > Without the protection it was possible to craft input that excessively > used the CPU. > > The fix uses the same mechanism as pass 2 to counterfeit this kind > of (malicious) input. > --- > include/demangle.h | 1 + > libiberty/ChangeLog | 18 ++++++++++++++++++ > libiberty/cp-demangle.c | 15 +++++++++++---- > libiberty/cp-demint.c | 3 +++ > 4 files changed, 33 insertions(+), 4 deletions(-) > > diff --git a/include/demangle.h b/include/demangle.h > index f5d9b9e8b5..3b00dbc31a 100644 > --- a/include/demangle.h > +++ b/include/demangle.h > @@ -481,6 +481,7 @@ struct demangle_component > Initialize to zero. Private to d_print_comp. > All other fields are final after initialization. */ > int d_printing; > + int d_counting; > > union > { > diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog > index 95cb1525f2..c86b06f0bf 100644 > --- a/libiberty/ChangeLog > +++ b/libiberty/ChangeLog > @@ -1,3 +1,21 @@ > +2019-11-12 Tim Ruehsen <tim.ruehsen@gmx.de> > + > + * ../include/demangle.h (struct demangle_component): > + Add member d_counting. > + * cp-demangle.c (d_print_init): Remove const from 4th param. > + (cplus_demangle_fill_name): Initialize d->d_counting. > + (cplus_demangle_fill_extended_operator): Likewise. > + (cplus_demangle_fill_ctor): Likewise. > + (cplus_demangle_fill_dtor): Likewise. > + (d_make_empty): Likewise. > + (d_count_templates_scopes): Remobe const from 3rd param, > + Return on dc->d_counting > 1, > + Increment dc->d_counting. > + * cp-demint.c (cplus_demangle_fill_component): Initialize d->d_counting. > + (cplus_demangle_fill_builtin_type): Likewise. > + (cplus_demangle_fill_operator): Likewise. > + This fixes bug #25180 (binutils bugtracker) THanks. Installed after minor twiddling of the ChangeLog. jeff
On 16.11.19 18:14, Jeff Law wrote: > On 11/12/19 9:39 AM, Tim Rühsen wrote: >> On 11/12/19 4:15 PM, Ian Lance Taylor wrote: >>> On Tue, Nov 12, 2019 at 6:15 AM Tim Rühsen <tim.ruehsen@gmx.de> wrote: >>>> this is a proposal to fix >>>> https://sourceware.org/bugzilla/show_bug.cgi?id=25180 >>>> >>>> In short: >>>> cxxfilt >>>> _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo >>>> >>>> takes several minutes with 100% CPU before it comes back with a result. >>>> >>>> With this patch the result is returned immediately. The test suite in >>>> binutils-gdb/libiberty/ throws no error. >>>> >>>> I'd like to note that I am not subscribed to the list, so please add me >>>> to CC when replying. Thanks in advance. >>> This is OK with an appropriate ChangeLog entry. >> Thanks for feedback, Ian. >> >> Attached is the patch with a ChangeLog entry. >> >> Regards, Tim ... > THanks. Installed after minor twiddling of the ChangeLog. > > jeff Thanks. Where exactly did it go ? Still can't see it in git://sourceware.org/git/binutils-gdb.git. Is there another repository ? Regards, Tim
On 11/19/19 12:00 PM, Tim Rühsen wrote: > On 16.11.19 18:14, Jeff Law wrote: >> On 11/12/19 9:39 AM, Tim Rühsen wrote: >>> On 11/12/19 4:15 PM, Ian Lance Taylor wrote: >>>> On Tue, Nov 12, 2019 at 6:15 AM Tim Rühsen <tim.ruehsen@gmx.de> wrote: >>>>> this is a proposal to fix >>>>> https://sourceware.org/bugzilla/show_bug.cgi?id=25180 >>>>> >>>>> In short: >>>>> cxxfilt >>>>> _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo >>>>> >>>>> takes several minutes with 100% CPU before it comes back with a result. >>>>> >>>>> With this patch the result is returned immediately. The test suite in >>>>> binutils-gdb/libiberty/ throws no error. >>>>> >>>>> I'd like to note that I am not subscribed to the list, so please add me >>>>> to CC when replying. Thanks in advance. >>>> This is OK with an appropriate ChangeLog entry. >>> Thanks for feedback, Ian. >>> >>> Attached is the patch with a ChangeLog entry. >>> >>> Regards, Tim > ... > >> THanks. Installed after minor twiddling of the ChangeLog. >> >> jeff > > Thanks. Where exactly did it go ? Still can't see it in > git://sourceware.org/git/binutils-gdb.git. Is there another repository ? It's in the GCC repo. binutils-gdb will (at some point) pull it from GCC. jeff
On 19.11.19 20:01, Jeff Law wrote: > On 11/19/19 12:00 PM, Tim Rühsen wrote: >> Thanks. Where exactly did it go ? Still can't see it in >> git://sourceware.org/git/binutils-gdb.git. Is there another repository ? > It's in the GCC repo. binutils-gdb will (at some point) pull it from GCC. > jeff Thanks, good to know, will clone it from there :-) Tim
On Tue, Nov 19, 2019 at 08:00:22PM +0100, Tim Rühsen wrote: > Thanks. Where exactly did it go ? Still can't see it in > git://sourceware.org/git/binutils-gdb.git. Is there another repository ? It will appear in the binutils repo when someone syncs libiberty with the master sources in the gcc repo.
From 27f770b2d9ff4e381431612c41ce18d4b44a6667 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Tim=20R=C3=BChsen?= <tim.ruehsen@gmx.de> Date: Tue, 12 Nov 2019 13:10:47 +0100 Subject: [PATCH] [libiberty] Fix demangler slowness issue Fixes #25180 The demangler works with two passes. The first one is for counting certain items. It was missing the protection against traversing subtrees multiple times without reaching the recursion limit. The second pass had this protection. Without the protection it was possible to craft input that excessively used the CPU. The fix uses the same mechanism as pass 2 to counterfeit this kind of (malicious) input. --- include/demangle.h | 1 + libiberty/cp-demangle.c | 15 +++++++++++---- libiberty/cp-demint.c | 3 +++ 3 files changed, 15 insertions(+), 4 deletions(-) diff --git a/include/demangle.h b/include/demangle.h index f5d9b9e8b5..3b00dbc31a 100644 --- a/include/demangle.h +++ b/include/demangle.h @@ -481,6 +481,7 @@ struct demangle_component Initialize to zero. Private to d_print_comp. All other fields are final after initialization. */ int d_printing; + int d_counting; union { diff --git a/libiberty/cp-demangle.c b/libiberty/cp-demangle.c index aa78c86dd4..f7c4dbbd11 100644 --- a/libiberty/cp-demangle.c +++ b/libiberty/cp-demangle.c @@ -517,7 +517,7 @@ d_growable_string_callback_adapter (const char *, size_t, void *); static void d_print_init (struct d_print_info *, demangle_callbackref, void *, - const struct demangle_component *); + struct demangle_component *); static inline void d_print_error (struct d_print_info *); @@ -864,6 +864,7 @@ cplus_demangle_fill_name (struct demangle_component *p, const char *s, int len) if (p == NULL || s == NULL || len <= 0) return 0; p->d_printing = 0; + p->d_counting = 0; p->type = DEMANGLE_COMPONENT_NAME; p->u.s_name.s = s; p->u.s_name.len = len; @@ -880,6 +881,7 @@ cplus_demangle_fill_extended_operator (struct demangle_component *p, int args, if (p == NULL || args < 0 || name == NULL) return 0; p->d_printing = 0; + p->d_counting = 0; p->type = DEMANGLE_COMPONENT_EXTENDED_OPERATOR; p->u.s_extended_operator.args = args; p->u.s_extended_operator.name = name; @@ -900,6 +902,7 @@ cplus_demangle_fill_ctor (struct demangle_component *p, || (int) kind > gnu_v3_object_ctor_group) return 0; p->d_printing = 0; + p->d_counting = 0; p->type = DEMANGLE_COMPONENT_CTOR; p->u.s_ctor.kind = kind; p->u.s_ctor.name = name; @@ -920,6 +923,7 @@ cplus_demangle_fill_dtor (struct demangle_component *p, || (int) kind > gnu_v3_object_dtor_group) return 0; p->d_printing = 0; + p->d_counting = 0; p->type = DEMANGLE_COMPONENT_DTOR; p->u.s_dtor.kind = kind; p->u.s_dtor.name = name; @@ -937,6 +941,7 @@ d_make_empty (struct d_info *di) return NULL; p = &di->comps[di->next_comp]; p->d_printing = 0; + p->d_counting = 0; ++di->next_comp; return p; } @@ -4068,11 +4073,13 @@ d_growable_string_callback_adapter (const char *s, size_t l, void *opaque) static void d_count_templates_scopes (struct d_print_info *dpi, - const struct demangle_component *dc) + struct demangle_component *dc) { - if (dc == NULL) + if (dc == NULL || dc->d_counting > 1 || dpi->recursion > MAX_RECURSION_COUNT) return; + ++ dc->d_counting; + switch (dc->type) { case DEMANGLE_COMPONENT_NAME: @@ -4202,7 +4209,7 @@ d_count_templates_scopes (struct d_print_info *dpi, static void d_print_init (struct d_print_info *dpi, demangle_callbackref callback, - void *opaque, const struct demangle_component *dc) + void *opaque, struct demangle_component *dc) { dpi->len = 0; dpi->last_char = '\0'; diff --git a/libiberty/cp-demint.c b/libiberty/cp-demint.c index 950e4dc552..16bf1f8ce6 100644 --- a/libiberty/cp-demint.c +++ b/libiberty/cp-demint.c @@ -125,6 +125,7 @@ cplus_demangle_fill_component (struct demangle_component *p, p->u.s_binary.left = left; p->u.s_binary.right = right; p->d_printing = 0; + p->d_counting = 0; return 1; } @@ -149,6 +150,7 @@ cplus_demangle_fill_builtin_type (struct demangle_component *p, p->type = DEMANGLE_COMPONENT_BUILTIN_TYPE; p->u.s_builtin.type = &cplus_demangle_builtin_types[i]; p->d_printing = 0; + p->d_counting = 0; return 1; } } @@ -176,6 +178,7 @@ cplus_demangle_fill_operator (struct demangle_component *p, p->type = DEMANGLE_COMPONENT_OPERATOR; p->u.s_operator.op = &cplus_demangle_operators[i]; p->d_printing = 0; + p->d_counting = 0; return 1; } } -- 2.24.0