Fix slowness in demangler
diff mbox series

Message ID 1a6ab914-e2b9-8735-deda-246c7afb9ccc@gmx.de
State New
Headers show
Series
  • Fix slowness in demangler
Related show

Commit Message

Tim Rühsen Nov. 12, 2019, 2:15 p.m. UTC
Hi,

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.

Regards, Tim

Comments

Ian Lance Taylor via gcc-patches Nov. 12, 2019, 3:15 p.m. UTC | #1
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
Tim Rühsen Nov. 12, 2019, 4:39 p.m. UTC | #2
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
Jeff Law Nov. 16, 2019, 5:14 p.m. UTC | #3
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
Tim Rühsen Nov. 19, 2019, 7 p.m. UTC | #4
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
Jeff Law Nov. 19, 2019, 7:01 p.m. UTC | #5
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
Tim Rühsen Nov. 19, 2019, 7:08 p.m. UTC | #6
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
Alan Modra Nov. 20, 2019, 10:41 p.m. UTC | #7
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.

Patch
diff mbox series

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