<html>
<body>
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "EmailMessage",
"potentialAction": {
"@type": "ViewAction",
"name": "View Issue",
"url": "https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=15022"
},
"description": ""
}
</script>
<div style="font-family: arial, sans-serif; white-space:pre"><br/>Comment #2 on issue 15022 by <a href="mailto:thakis@chromium.org">thakis@chromium.org</a>: llvm/llvm-microsoft-demangle-fuzzer: Out-of-memory in llvm_llvm-microsoft-demangle-fuzzer<br/><a href="https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=15022#c2">https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=15022#c2</a><br/><br/>The root cause here ultimately is that demangling output can be exponential in the size of the input, even for valid manglings. Consider:<br/><br/>$ cat test.cc<br/>template <class T1, class T2, class T3, class T4, class T5,<br/> class T6, class T7, class T8, class T9, class T10><br/>struct Fooob {};<br/><br/>using A0 = Fooob<int, int, int, int, int, int, int, int, int, int>;<br/>using A1 = Fooob<A0, A0, A0, A0, A0, A0, A0, A0, A0, A0>;<br/>using A2 = Fooob<A1, A1, A1, A1, A1, A1, A1, A1, A1, A1>;<br/>using A3 = Fooob<A2, A2, A2, A2, A2, A2, A2, A2, A2, A2>;<br/>using A4 = Fooob<A3, A3, A3, A3, A3, A3, A3, A3, A3, A3>;<br/>using A5 = Fooob<A4, A4, A4, A4, A4, A4, A4, A4, A4, A4>;<br/>using A6 = Fooob<A5, A5, A5, A5, A5, A5, A5, A5, A5, A5>;<br/>using A7 = Fooob<A6, A6, A6, A6, A6, A6, A6, A6, A6, A6>;<br/><br/>void f(A7 a) {}<br/><br/>$ out/gn/bin/clang-cl /c test.cc<br/>$ out/gn/bin/llvm-nm test.obj<br/>00000000 T ?f@@YAXU?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@HHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@@Z<br/>00000000 a @feat.00<br/>$ /usr/bin/time -l out/gn/bin/llvm-undname '?f@@YAXU?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@HHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@@Z' > tmp.txt<br/> 3.93 real 0.76 user 1.15 sys<br/>1459576832 maximum resident set size<br/> 0 average shared memory size<br/> 0 average unshared data size<br/> 0 average unshared stack size<br/> 516405 page reclaims<br/> 0 page faults<br/> 0 swaps<br/> 0 block input operations<br/> 0 block output operations<br/> 0 messages sent<br/> 0 messages received<br/> 0 signals received<br/> 943 voluntary context switches<br/> 62 involuntary context switches<br/>$ ls -hl tmp.txt<br/>-rw-r--r-- 1 thakis staff 625M Jun 5 08:36 tmp.txt<br/><br/><br/>This grows 10x with each additional A. I can make the backref entries lazy and that should save one level of memory use and for this example it'd probably cut memory use almost 10x -- but the cc file only needs to grow a single additional line to waste that again, and the mangled string will only grow by a few bytes for this.<br/><br/>This also isn't llvm-undname specific, llvm-cxxfilt has the same issue:<br/><br/><br/>$ out/gn/bin/clang -c test.cc<br/>$ out/gn/bin/llvm-nm test.o<br/>0000000000000000 T __Z1f5FooobIS_IS_IS_IS_IS_IS_IS_IiiiiiiiiiiES0_S0_S0_S0_S0_S0_S0_S0_S0_ES1_S1_S1_S1_S1_S1_S1_S1_S1_ES2_S2_S2_S2_S2_S2_S2_S2_S2_ES3_S3_S3_S3_S3_S3_S3_S3_S3_ES4_S4_S4_S4_S4_S4_S4_S4_S4_ES5_S5_S5_S5_S5_S5_S5_S5_S5_ES6_S6_S6_S6_S6_S6_S6_S6_S6_E<br/>$ /usr/bin/time -l out/gn/bin/llvm-cxxfilt _Z1f5FooobIS_IS_IS_IS_IS_IS_IS_IiiiiiiiiiiES0_S0_S0_S0_S0_S0_S0_S0_S0_ES1_S1_S1_S1_S1_S1_S1_S1_S1_ES2_S2_S2_S2_S2_S2_S2_S2_S2_ES3_S3_S3_S3_S3_S3_S3_S3_S3_ES4_S4_S4_S4_S4_S4_S4_S4_S4_ES5_S5_S5_S5_S5_S5_S5_S5_S5_ES6_S6_S6_S6_S6_S6_S6_S6_S6_E > tmp.txt<br/> 5.02 real 2.85 user 0.78 sys<br/>1159876608 maximum resident set size<br/> 0 average shared memory size<br/> 0 average unshared data size<br/> 0 average unshared stack size<br/> 316004 page reclaims<br/> 16 page faults<br/> 0 swaps<br/> 0 block input operations<br/> 0 block output operations<br/> 0 messages sent<br/> 0 messages received<br/> 0 signals received<br/> 671 voluntary context switches<br/> 189 involuntary context switches<br/>$ ls -hl tmp.txt<br/>-rw-r--r-- 1 thakis staff 552M Jun 5 08:39 tmp.txt<br/><br/><br/><br/>As said, the root cause here is that the output can be exponential in the input size. Nobody really wants to have exponentially-sized output from their demangler -- the following is just hard to read:<br/><br/>demumble '__Z1f5FooobIS_IS_IiiiiiiiiiiES0_S0_S0_S0_S0_S0_S0_S0_S0_ES1_S1_S1_S1_S1_S1_S1_S1_S1_E'<br/>f(Fooob<Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> >, Fooob<Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int>, Fooob<int, int, int, int, int, int, int, int, int, int> > >)<br/><br/><br/>So maybe we should change the demangler output for backreferences to instead produces something like this instead:<br/><br/>$ demumble '__Z1f5FooobIS_IS_IiiiiiiiiiiES0_S0_S0_S0_S0_S0_S0_S0_S0_ES1_S1_S1_S1_S1_S1_S1_S1_S1_E'<br/>#define S0 Foob<br/>#define S1 S0<int, int, int, int, int, int, int, int, int, int><br/>#define S2 S0<S1, S1, S1, S1, S1, S1, S1, S1, S1, S1><br/>f(S2)<br/><br/>which is a more direct translation of what's in the mangling and arguably easier to read. It has the advantage of needing storage that's linear in the input.<br/><br/>-- <br/>You received this message because:<br/> 1. You were specifically CC'd on the issue<br/><br/>You may adjust your notification preferences at:<br/><a href="https://bugs.chromium.org/hosting/settings">https://bugs.chromium.org/hosting/settings</a><br/><br/>Reply to this email to add a comment.</div>
</body>
</html>