[RFC PATCH libiberty] Fix infinite recursion in demangler

[Mark Wielaard]

Hi,

On Thu, 2017-03-02 at 10:36 +0100, Markus Trippelsdorf wrote:
> The following patch from Mark Wielaard fixes many (all?) open demangler
> bugs that happen because we overflow the stack due to infinite
> recursion.
> 
> I'm not sure why Mark didn't post the patch himself.
> Anyway here it is.
> Any comments?

Thanks for poking at this issue. I didn't post it because I ran out of
time fully understanding why it works. I do believe this is the right
approach.  As far as I know the demangler can only be crashed by these
tricky endless recursion issues. All other crashers seem to have been
fixed already.

Below is some more explanation. More in the bug report:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70909
I would certainly not mind if someone ran with this patch and made sure
it is fully correct. But there is one "magic bit" in there, that I
cannot fully explain.

> @@ -5683,9 +5684,16 @@ d_print_comp_inner (struct d_print_info *dpi, int options,
>  
>  static void
>  d_print_comp (struct d_print_info *dpi, int options,
> -	      const struct demangle_component *dc)
> +	      struct demangle_component *dc)
>  {
>    struct d_component_stack self;
> +  if (dc == NULL || dc->d_printing > 1)
> +    {
> +      d_print_error (dpi);
> +      return;
> +    }
> +  else
> +    dc->d_printing++;
>  
>    self.dc = dc;
>    self.parent = dpi->component_stack;

The question is why must that be > 1, not >= 1 or some other constant?

In my local patch I added this comment:

+  /* We need to allow one level of recursion for function types,
+     which are printed recursively with different options depending
+     on whether or not the return type needs to be printed. And when
+     printing a lambda argument then we need to allow another level
+     of recursion to print it.  */

And to track that I introduced the following field in struct
d_print_info:

+  /* Whether a component has been pushed to the modifiers list to
+     print the function return type in the right place.  Used for
+     tracking allowed component recursion depth.  */
+  int func_ret_modifier;

Which is then initialized in d_print_init and incremented/decremented in
d_print_comp_inner around the recursive calls to d_print_comp to print
the return type.

To track the printing of lambda arguments the condition is then changed
to:

+  if (dc == NULL
+      || dc->d_printing > dpi->func_ret_modifier + dpi->is_lambda_arg)

I also added various testcases.

diff --git a/libiberty/testsuite/demangle-expected b/libiberty/testsuite/demangle-expected
index b65dcd3..5fc1b9a 100644
--- a/libiberty/testsuite/demangle-expected
+++ b/libiberty/testsuite/demangle-expected
@@ -4666,3 +4666,44 @@ void eat<int*, Foo()::{lambda(auto:1*, auto:2*)#6}>(int*&, Foo()::{lambda(auto:1
 
 _Z3eatIPiZ3BarIsEvvEUlPsPT_PT0_E0_EvRS3_RS5_
 void eat<int*, void Bar<short>()::{lambda(short*, auto:1*, auto:2*)#2}>(int*&, void Bar<short>()::{lambda(short*, auto:1*, auto:2*)#2}&)
+#
+# Test recursion PR67264
+
+_Z1KIStcvT_E
+_Z1KIStcvT_E
+
+_ZcvT_IIS0_EE
+_ZcvT_IIS0_EE
+
+_ZcvT_IZcvT_E1fE
+_ZcvT_IZcvT_E1fE
+
+_Z1gINcvT_EE
+_Z1gINcvT_EE
+
+_ZcvT_ILZcvDTT_EEE
+_ZcvT_ILZcvDTT_EEE
+
+_Z1gIJOOT_EEOT_c
+_Z1gIJOOT_EEOT_c
+
+_Z1KMMMMMMMMMMMMMMMA_xooooooooooooooo
+_Z1KMMMMMMMMMMMMMMMA_xooooooooooooooo
+
+_ZdvMMMMMMMMMMMMMrrrrA_DTdvfp_fp_Eededilfdfdfdfd
+_ZdvMMMMMMMMMMMMMrrrrA_DTdvfp_fp_Eededilfdfdfdfd
+#
+# Test for Infinite Recursion PR70909
+
+_Z1MA_aMMMMA_MMA_MMMMMMMMSt1MS_o11T0000000000t2M0oooozoooo
+_Z1MA_aMMMMA_MMA_MMMMMMMMSt1MS_o11T0000000000t2M0oooozoooo
+
+#
+# Test for allowing recursion when is_lambda_arg PR68700
+_ZN8futurizeI13frozen_schemaE5applyIRZN7seastar7shardedIN7service13storage_proxyEE9invoke_onIZZNS6_22init_messaging_serviceEvENKUljN5utils4UUIDEE8_clEjSA_EUlOT_E_6futureIJS0_EEEET0_jSD_EUlvE_JEEESG_SD_DpOT0_
+service::storage_proxy::init_messaging_service()::{lambda(unsigned int, utils::UUID)#10}::operator()(unsigned int, utils::UUID) const::{lambda(auto:1&&)#1} futurize<frozen_schema>::apply<future<frozen_schema> seastar::sharded<service::storage_proxy>::invoke_on<service::storage_proxy::init_messaging_service()::{lambda(unsigned int, utils::UUID)#10}::operator()(unsigned int, utils::UUID) const::{lambda(auto:1&&)#1}, future<frozen_schema> >(unsigned int, service::storage_proxy::init_messaging_service()::{lambda(unsigned int, utils::UUID)#10}::operator()(unsigned int, utils::UUID) const::{lambda(auto:1&&)#1})::{lambda()#1}&>(future<frozen_schema> seastar::sharded<service::storage_proxy>::invoke_on<service::storage_proxy::init_messaging_service()::{lambda(unsigned int, utils::UUID)#10}::operator()(unsigned int, utils::UUID) const::{lambda(auto:1&&)#1}, future<frozen_schema> >(unsigned int, service::storage_proxy::init_messaging_service()::{lambda(unsigned int, utils::UUID)#10}::operator()(unsigned int, utils::UUID) const::{lambda(auto:1&&)#1})::{lambda()#1}&)
+
+#
+# Test for allowing recursion when is_lambda_arg PR70517
+_ZSt4moveIRZN11tconcurrent6futureIvE4thenIZ5awaitIS2_EDaOT_EUlRKS6_E_EENS1_INSt5decayIDTclfp_defpTEEE4typeEEES7_EUlvE_EONSt16remove_referenceIS6_E4typeES7_
+std::remove_reference<tconcurrent::future<std::decay<decltype ({parm#1}(*this))>::type> tconcurrent::future<void>::then<auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}>(auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}&& const)::{lambda()#1}&>::type&& std::move<tconcurrent::future<std::decay<decltype ({parm#1}(*this))>::type> tconcurrent::future<void>::then<auto await<tconcurrent::future<void> >(tconcurrent::future<std::decay<decltype ({parm#1}(*this))>::type> tconcurrent::future<void>::then<auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}>(auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}&& const)::{lambda()#1}&)::{lambda(auto:1&& const&)#1}>(tconcurrent::future<std::decay<decltype ({parm#1}(*this))>::type> tconcurrent::future<void>::then<auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}>(auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}&& const)::{lambda()#1}& const)::{lambda()#1}&>(tconcurrent::future<std::decay<decltype ({parm#1}(*this))>::type> tconcurrent::future<void>::then<auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}>(auto await<tconcurrent::future<void> >(tconcurrent::future<void>&&)::{lambda(auto:1&& const&)#1}&& const)::{lambda()#1}& const)