[libcxxabi][demangler] Fix a crash in the demangler

[erik.pilkington]

Summary

This patch fixes a bug in the demangler where a pack expansion template parameter substitution with more than one element in a lambda's parameter list resulted in either a misdemangle or a crash. I'll commit this change to ItaniumDemangle.cpp as well, as it has the same problem.

rdar://32098667

Thanks for taking a look,
Erik

[compnerd]

src/cxa_demangle.cpp

3036 ↗

(On Diff #99625)

I'm not sure how k1 can be < than k0. Isn't this effectively always going down the == path? If I'm just mistaken, then I think that this needs a comment.

3042–3051 ↗

(On Diff #99625)

I think that using a bit of algorithm here might be nice.

std::ostringstream oss(db.names[lambda_pos]);
std::copy_if(db.names[k0], db.names[k1], std::ostream_iterator<std::string>(oss, ",  "),
             [](const std::string &s) -> bool { return !s.empty(); });

[dexonsmith]

src/cxa_demangle.cpp

3042–3051 ↗

(On Diff #99625)

Introducing a dependency on std::ostream would be awkward. libc++abi.dylib cannot link against libc++.dylib, and it would bloat libc++abi.dylib to use custom traits to pull in a full copy.

[erik.pilkington]

src/cxa_demangle.cpp

3036 ↗

(On Diff #99625)

I agree that it should be impossible, but the previous version handled this case with the if (db.names.size() < 2) check, when really db.names.size() can only be 1 or greater. I think it makes more sense to be paranoid here, I trust this file about as far as I can throw it (And I can't throw it very far, its not a tangible object).

[compnerd]

src/cxa_demangle.cpp

3036 ↗

(On Diff #99625)

Hmm, how about being paranoid, and converting that to an assertion and then doing the == check? This code is already incredibly complicated, so adding additional things like this only makes it harder to understand whats going on.

3042–3051 ↗

(On Diff #99625)

Ugh, thats a good point. Very well. However, there doesnt seem to be any iterator invalidation here, so we can still just iterate over a slice here, which would be nicer.

[erik.pilkington]

In this new patch:

• Add the testcase from https://reviews.llvm.org/D33393
• Add an assert() that k0 <= k1
• Use std::for_each instead of the for loop

Thanks for taking a look,
Erik

[dexonsmith]

src/cxa_demangle.cpp

3036 ↗

(On Diff #99930)

There's no #include <cassert> in this file. Depending on the standard library you're building against, you made need that here.

[erik.pilkington]

src/cxa_demangle.cpp

3036 ↗

(On Diff #99930)

Sure, I'll commit this with that change.

[kcc]

oss-fuzz finds the assertion failure in this new code:
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=1834

[erik.pilkington]

r303806 removes the assertion (instead just returning first). I though this should never happen, I'm looking into this testcase to see if there is another bug here.
Thanks,
Erik

[kcc]

I also encourage you to run the fuzzer on every change in this code.

[kcc]

Also, are you now maintaining this code?
I am trying to find someone who wants to be CC-ed to other demangler bugs automatically reported by oss-fuzz.

[erik.pilkington]

Also, are you now maintaining this code?
I am trying to find someone who wants to be CC-ed to other demangler bugs automatically reported by oss-fuzz.

I don’t think I’ll accept the title of maintainer, (I only have one commit in this file!) but I have some plans to work on it and would be interested in hearing about any bugs found in the fuzzer.
Can you add [e-mail] to your CC list?

[kcc]

Done (see https://github.com/google/oss-fuzz/blob/master/projects/llvm_libcxxabi/project.yaml)

libcxxabi/trunk/src/cxa_demangle.cpp

 #define _LIBCPP_NO_EXCEPTIONS
 
 #include "__cxxabi_config.h"
 
 #include <vector>
 #include <algorithm>
 #include <string>
 #include <numeric>
+#include <cassert>
 #include <cstdlib>
 #include <cstring>
 #include <cctype>
 
 #ifdef _MSC_VER
 // snprintf is implemented in VS 2015
 #if _MSC_VER < 1900
 #define snprintf _snprintf_s
if (last - first > 2 && first[0] == 'U')
                 db.names.pop_back();
                 return first;
             }
             first = t0 + 1;
           }
             break;
         case 'l':
           {
+            size_t lambda_pos = db.names.size();
             db.names.push_back(typename C::String("'lambda'("));
             const char* t0 = first+2;
             if (first[2] == 'v')
             {
                 db.names.back().first += ')';
                 ++t0;
             }
             else
             {
-                const char* t1 = parse_type(t0, last, db);
-                if (t1 == t0)
-                {
-                    if(!db.names.empty())
-                        db.names.pop_back();
-                    return first;
-                }
-                if (db.names.size() < 2)
-                    return first;
-                auto tmp = db.names.back().move_full();
-                db.names.pop_back();
-                db.names.back().first.append(tmp);
-                t0 = t1;
+                bool is_first_it = true;
                 while (true)
                 {
-                    t1 = parse_type(t0, last, db);
+                    long k0 = static_cast<long>(db.names.size());
+                    const char* t1 = parse_type(t0, last, db);
+                    long k1 = static_cast<long>(db.names.size());
                     if (t1 == t0)
                         break;
-                    if (db.names.size() < 2)
+                    assert(k0 <= k1 && "parse_type() mutated the name stack");
+                    if (k1 == k0)
                         return first;
-                    tmp = db.names.back().move_full();
-                    db.names.pop_back();
-                    if (!tmp.empty())
-                    {
-                        db.names.back().first.append(", ");
-                        db.names.back().first.append(tmp);
-                    }
+                    // If the call to parse_type above found a pack expansion
+                    // substitution, then multiple names could have been
+                    // inserted into the name table. Walk through the names,
+                    // appending each onto the lambda's parameter list.
+                    std::for_each(db.names.begin() + k0, db.names.begin() + k1,
+                                  [&](typename C::sub_type::value_type &pair) {
+                                      if (pair.empty())
+                                          return;
+                                      auto &lambda = db.names[lambda_pos].first;
+                                      if (!is_first_it)
+                                          lambda.append(", ");
+                                      is_first_it = false;
+                                      lambda.append(pair.move_full());
+                                  });
+                    db.names.erase(db.names.begin() + k0, db.names.end());
                     t0 = t1;
                 }
-                if(db.names.empty())
+                if (is_first_it)
+                {
+                    if (!db.names.empty())
+                        db.names.pop_back();
+                    return first;
+                }
+                if (db.names.empty() || db.names.size() - 1 != lambda_pos)
                   return first;
                 db.names.back().first.append(")");
             }
             if (t0 == last || *t0 != 'E')
             {
               if (!db.names.empty())
                 db.names.pop_back();
               return first;
struct string_pair
     string_pair() = default;
     string_pair(StrT f) : first(std::move(f)) {}
     string_pair(StrT f, StrT s)
         : first(std::move(f)), second(std::move(s)) {}
     template <size_t N>
         string_pair(const char (&s)[N]) : first(s, N-1) {}
 
     size_t size() const {return first.size() + second.size();}
+    bool empty() const { return first.empty() && second.empty(); }
     StrT full() const {return first + second;}
     StrT move_full() {return std::move(first) + std::move(second);}
 };
 
 struct Db
 {
     typedef std::basic_string<char, std::char_traits<char>,
                               malloc_alloc<char>> String;

libcxxabi/trunk/test/test_demangle.pass.cpp

//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     {"i", "int"},
 
     {"PKFvRiE", "void (*)(int&) const"},
     // FIXME(compnerd) pretty print this as void (*)(unsigned long &) volatile &&
     {"PVFvRmOE", "void (*)(unsigned long&)  volatile&&"},
     {"PFvRmOE", "void (*)(unsigned long&) &&"},
     {"_ZTW1x", "thread-local wrapper routine for x"},
     {"_ZTHN3fooE", "thread-local initialization routine for foo"},
+    {"_Z4algoIJiiiEEvZ1gEUlT_E_", "void algo<int, int, int>(g::'lambda'(int, int, int))"},
 };
 
 const unsigned N = sizeof(cases) / sizeof(cases[0]);
 
 struct FPLiteralCase {
     const char *mangled;
     // There are four possible demanglings of a given float.
     std::string expecting[4];
// The following test cases were found by libFuzzer+ASAN
     "\x44\x74\x70\x74\x71\x75\x32\x43\x41\x38\x65\x6E\x9B\x72\x4D\xC1\x43\x41\x72\x4D\x6E\x77\x38\x9A\x8E\x44\x6F\x64\xC3\x53\xF9\x5F\x70\x74\x70\x69\x45\x38\xD3\x73\x9E\x2A\x37",
     "\x4C\x5A\x4C\x55\x6C\x4D\x41\x5F\x41\x67\x74\x71\x75\x34\x4D\x41\x64\x73\x4C\x44\x76\x72\x4D\x34\x44\x4B\x44\x54\x6E\x61\x37\x47\x77\x78\x38\x43\x27\x41\x5F\x73\x70\x69\x45\x6D\x73\x72\x53\x41\x6F\x41\x7B",
     "\x44\x74\x70\x74\x71\x75\x32\x43\x41\x38\x65\x6E\x9B\x72\x4D\xC1\x43\x41\x72\x4D\x6E\x77\x38\x9A\x8E\x44\x6F\x64\x2C\x53\xF9\x5F\x70\x74\x70\x69\x45\xB4\xD3\x73\x9F\x2A\x37",
     "\x4C\x5A\x4C\x55\x6C\x69\x4D\x73\x72\x53\x6F\x7A\x41\x5F\x41\x67\x74\x71\x75\x32\x4D\x41\x64\x73\x39\x28\x76\x72\x4D\x34\x44\x4B\x45\x54\x6E\x61\x37\x47\x77\x78\x38\x43\x27\x41\x5F\x73\x70\x69\x45\x6F\x45\x49\x6D\x1A\x4C\x53\x38\x6A\x7A\x5A",
     "\x44\x74\x63*",
     "\x44\x74\x71\x75\x35\x2A\xDF\x74\x44\x61\x73\x63\x35\x2A\x3B\x41\x72\x4D\x6E\x65\x34\x9F\xC1\x63\x41\x72\x4D\x6E\x77\x38\x9A\x8E\x44\x6F\x64\x6C\x53\xF9\x5F\x70\x74\x70\x69\x45\x33\x44\x76\x35",
     "\x44\x74\x70\x74\x71\x75\x32\x43\x41\x38\x65\x6E\x9B\x72\x4D\xC1\x43\x41\x72\x4D\x6E\x77\x38\x9A\x8E\x44\x6F\x64\x6C\x53\xF9\x5F\x70\x74\x70\x69\x45\x38\xD3\x73\x9E\x2A\x37",
     "\x46\x44\x74\x70\x74\x71\x75\x32\x43\x41\x72\x4D\x6E\x65\x34\x9F\xC1\x43\x41\x72\x4D\x6E\x77\x38\x9A\x8E\x44\x6F\x64\x6C\x53\xF9\x5F\x70\x74\x70\x69\x45\x34\xD3\x73\x9E\x2A\x37\x72\x33\x8E\x3A\x29\x8E\x44\x35",
-  "_ZcvCiIJEEDvT__FFFFT_vT_v",
+    "_ZcvCiIJEEDvT__FFFFT_vT_v",
+    "Z1JIJ1_T_EE3o00EUlT_E0",
 };
 
 const unsigned NI = sizeof(invalid_cases) / sizeof(invalid_cases[0]);
 
 void test()
 {
     std::size_t len = 0;
     char* buf = nullptr;