[PATCH] Fix slowness in demangler

[Tim Rühsen <tim dot ruehsen at gmx dot de>]

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

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

Attachment: signature.asc
Description: OpenPGP digital signature