[PATCH] Fix slowness in demangler

[Jeff Law]

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