Fix possible infinite loop in itanium demangler

[borman]

Summary

A libfuzzer run has discovered some inputs for which the demangler does not terminate.

When minimized, it looks like this: _Zcv1BIRT_EIS1_E

Deciphered:

_Z
cv    - conversion operator

      * result type
 1B   - "B"
 I    - template args begin
  R   - reference type              <.
   T_ - forward template reference   |  *
 E    - template args end            |  |
                                     |  |
      * parameter type               |  |
 I    - template args begin          |  |
  S1_ - substitution #1              * <'
 E    - template args end

The reason is: template-parameter refs in conversion operator result type create forward-references, while substitutions are instantly resolved via back-references. Together these can create a reference loop. It causes an infinite loop in ReferenceType::collapse().

I see three possible ways to avoid these loops:

1. check if resolving a forward reference creates a loop and reject the invalid input (hard to traverse AST at this point)
2. check if a substitution contains a malicious forward reference and reject the invalid input (hard to traverse AST at this point; substitutions are quite common: may affect performance; hard to clearly detect loops at this point)
3. detect loops in ReferenceType::collapse() (cannot reject the input)

This patch implements (3) as seemingly the least-impact change. As a side effect, such invalid input strings are not rejected and produce garbage, however there are already similar guards in if (Printing) return; checks.

Fixes: https://bugs.llvm.org/show_bug.cgi?id=51407

[borman]

llvm/include/llvm/Demangle/ItaniumDemangle.h

112–229

I could submit this change as a NFC to clean up the actual patch; however the move itself would be out of context.

[ldionne]

Thanks a lot for looking into this! When you re-upload the patch, can you please do it with arc diff so that context is included in the diff? See https://www.llvm.org/docs/Phabricator.html#requesting-a-review-via-the-command-line for instructions.

libcxxabi/test/test_demangle.pass.cpp

29847

We need to add this at the top of this file:

// https://llvm.org/PR51407 was not fixed in some previously-released demanglers, which
// causes them to run into the infinite loop.
// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx11.0

Otherwise, we'll try to run the test on those configurations and we'll run into the infinite loop. Incidentally, this just stalled the CI for 24 hours (I'll put a timeout on our tests).

29848

Please normalize to https://llvm.org/PR51407.

llvm/include/llvm/Demangle/ItaniumDemangle.h

112–229

I would rather the move be performed as a separate NFC. The commit message can mention it's for a follow-up change.

[borman]

llvm/include/llvm/Demangle/ItaniumDemangle.h

112–229

Separate review for the move: https://reviews.llvm.org/D107712

[borman]

rebase onto D107771, fix issues

[borman]

resubmit diff against main

[borman]

resubmit diff against D107771

[borman]

Unfortunately, Arcanist doesn't give me any options to send test_demangler.pass.cpp diff as text:

Diff for 'libcxxabi/test/test_demangle.pass.cpp' with context is
5,403,433 bytes in length. Generally, source changes should not be this
large. If the file is not a text file, you can mark it 'binary'. Mark
this file as 'binary' and continue? [y/N] y

Seems like enormous strings in test cases upset it and I'm not proficient enough with it to bypass this.

The actual diff is:

diff --git a/libcxxabi/test/test_demangle.pass.cpp b/libcxxabi/test/test_demangle.pass.cpp
index 1780e684cbb5..0744172a6cbb 100644
--- a/libcxxabi/test/test_demangle.pass.cpp
+++ b/libcxxabi/test/test_demangle.pass.cpp
@@ -9,6 +9,11 @@
 // The demangler does not pass all these tests with the system dylibs on macOS.
 // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}

+// https://llvm.org/PR51407 was not fixed in some previously-released
+// demanglers, which causes them to run into the infinite loop.
+// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
+// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx11.0
+
 #include "support/timer.h"
 #include <cassert>
 #include <cstdio>
@@ -29844,6 +29849,9 @@ const char* cases[][2] =

     {"_ZN3xxx3yyyIvNS_1AILm0EEEZNS_2bb2cc2ddILNS_1eE1EEEvRKNS_1fERKNS_1g1hINS_1iEEERKNS_1jEfRKNS_1kEiPhEUlvE_JEEEvT1_DpT2_", "void xxx::yyy<void, xxx::A<0ul>, void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h<xxx::i> const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'()>(void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h<xxx::i> const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'())"},

+    // This should be invalid, but it is currently not recognized as such
+    // See https://llvm.org/PR51407
+    {"_Zcv1BIRT_EIS1_E", "operator B<><>"},
 };

 const unsigned N = sizeof(cases) / sizeof(cases[0]);

[borman]

upload with reduced diff context

[borman]

upload with increased diff context

[ldionne]

This fell under my radar. I'm fine with this. I'll commit it for you, thanks!

[ldionne]

Oh, and thanks a lot for the great explanation of the problem and the fix, I really appreciate that.

libcxxabi/src/demangle/ItaniumDemangle.h

class ReferenceType : public Node {
   const Node *Pointee;
   ReferenceKind RK;
 
   mutable bool Printing = false;
 
   // Dig through any refs to refs, collapsing the ReferenceTypes as we go. The
   // rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any
   // other combination collapses to a lvalue ref.
+  //
+  // A combination of a TemplateForwardReference and a back-ref Substitution
+  // from an ill-formed string may have created a cycle; use cycle detection to
+  // avoid looping forever.
   std::pair<ReferenceKind, const Node *> collapse(OutputStream &S) const {
     auto SoFar = std::make_pair(RK, Pointee);
+    // Track the chain of nodes for the Floyd's 'tortoise and hare'
+    // cycle-detection algorithm, since getSyntaxNode(S) is impure
+    PODSmallVector<const Node *, 8> Prev;
     for (;;) {
       const Node *SN = SoFar.second->getSyntaxNode(S);
       if (SN->getKind() != KReferenceType)
         break;
       auto *RT = static_cast<const ReferenceType *>(SN);
       SoFar.second = RT->Pointee;
       SoFar.first = std::min(SoFar.first, RT->RK);
+
+      // The middle of Prev is the 'slow' pointer moving at half speed
+      Prev.push_back(SoFar.second);
+      if (Prev.size() > 1 && SoFar.second == Prev[(Prev.size() - 1) / 2]) {
+        // Cycle detected
+        SoFar.second = nullptr;
+        break;
+      }
     }
     return SoFar;
   }
 
 public:
   ReferenceType(const Node *Pointee_, ReferenceKind RK_)
       : Node(KReferenceType, Pointee_->RHSComponentCache),
         Pointee(Pointee_), RK(RK_) {}
 
   template<typename Fn> void match(Fn F) const { F(Pointee, RK); }
 
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Pointee->hasRHSComponent(S);
   }
 
   void printLeft(OutputStream &s) const override {
     if (Printing)
       return;
     SwapAndRestore<bool> SavePrinting(Printing, true);
     std::pair<ReferenceKind, const Node *> Collapsed = collapse(s);
+    if (!Collapsed.second)
+      return;
     Collapsed.second->printLeft(s);
     if (Collapsed.second->hasArray(s))
       s += " ";
     if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s))
       s += "(";
 
     s += (Collapsed.first == ReferenceKind::LValue ? "&" : "&&");
   }
   void printRight(OutputStream &s) const override {
     if (Printing)
       return;
     SwapAndRestore<bool> SavePrinting(Printing, true);
     std::pair<ReferenceKind, const Node *> Collapsed = collapse(s);
+    if (!Collapsed.second)
+      return;
     if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s))
       s += ")";
     Collapsed.second->printRight(s);
   }
 };
 
 class PointerToMemberType final : public Node {
   const Node *ClassType;

libcxxabi/test/test_demangle.pass.cpp

 //===-------------------------- test_demangle.cpp -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // The demangler does not pass all these tests with the system dylibs on macOS.
 // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
 
+// https://llvm.org/PR51407 was not fixed in some previously-released
+// demanglers, which causes them to run into the infinite loop.
+// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
+// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx11.0
+
 #include "support/timer.h"
 #include <cassert>
 #include <cstdio>
 #include <cstdlib>
 #include <cxxabi.h>
 #include <string>
 
 // Is long double fp80?  (Only x87 extended double has 64-bit mantissa)
//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     // See https://github.com/itanium-cxx-abi/cxx-abi/issues/106.
     {"_Z1h1XIJZ1fIiEDaOT_E1AZ1gIdEDaS2_E1BEE", "h(X<auto f<int>(int&&)::A, auto g<double>(int&&)::B>)"},
 
     {"_Z1fIL4Enumn1EEvv", "void f<(Enum)-1>()"},
 
     {"_ZN1A1gIiEEDTcldtptfpT1b1fIT_EEEv", "decltype(this->b.f<int>()) A::g<int>()"},
 
     // Optional template-args for vendor extended type qualifier.
     // See https://bugs.llvm.org/show_bug.cgi?id=48009.
     {"_Z3fooILi79EEbU7_ExtIntIXT_EEi", "bool foo<79>(int _ExtInt<79>)"},
 
     {"_ZN3xxx3yyyIvNS_1AILm0EEEZNS_2bb2cc2ddILNS_1eE1EEEvRKNS_1fERKNS_1g1hINS_1iEEERKNS_1jEfRKNS_1kEiPhEUlvE_JEEEvT1_DpT2_", "void xxx::yyy<void, xxx::A<0ul>, void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h<xxx::i> const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'()>(void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h<xxx::i> const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'())"},
 
+    // This should be invalid, but it is currently not recognized as such
+    // See https://llvm.org/PR51407
+    {"_Zcv1BIRT_EIS1_E", "operator B<><>"},
 };
 
 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];

llvm/include/llvm/Demangle/ItaniumDemangle.h

#define FOR_EACH_NODE_KIND(X) \
     X(FloatLiteral) \
     X(DoubleLiteral) \
     X(LongDoubleLiteral) \
     X(BracedExpr) \
     X(BracedRangeExpr)
 
 DEMANGLE_NAMESPACE_BEGIN
 
 template <class T, size_t N> class PODSmallVector {
   static_assert(std::is_pod<T>::value,
                 "T is required to be a plain old data type");
 
   T *First = nullptr;
   T *Last = nullptr;
   T *Cap = nullptr;
   T Inline[N] = {0};
 
   bool isInline() const { return First == Inline; }
 
   void clearInline() {
     First = Inline;
     Last = Inline;
     Cap = Inline + N;
   }
 
   void reserve(size_t NewCap) {
     size_t S = size();
     if (isInline()) {
       auto *Tmp = static_cast<T *>(std::malloc(NewCap * sizeof(T)));
       if (Tmp == nullptr)
         std::terminate();
       std::copy(First, Last, Tmp);
       First = Tmp;
     } else {
       First = static_cast<T *>(std::realloc(First, NewCap * sizeof(T)));
       if (First == nullptr)
         std::terminate();
     }
     Last = First + S;
     Cap = First + NewCap;
   }
 
 public:
   PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
 
   PODSmallVector(const PODSmallVector &) = delete;
   PODSmallVector &operator=(const PODSmallVector &) = delete;
 
   PODSmallVector(PODSmallVector &&Other) : PODSmallVector() {
     if (Other.isInline()) {
       std::copy(Other.begin(), Other.end(), First);
       Last = First + Other.size();
       Other.clear();
       return;
     }
 
     First = Other.First;
     Last = Other.Last;
     Cap = Other.Cap;
     Other.clearInline();
   }
 
   PODSmallVector &operator=(PODSmallVector &&Other) {
     if (Other.isInline()) {
       if (!isInline()) {
         std::free(First);
         clearInline();
       }
       std::copy(Other.begin(), Other.end(), First);
       Last = First + Other.size();
       Other.clear();
       return *this;
     }
 
     if (isInline()) {
       First = Other.First;
       Last = Other.Last;
       Cap = Other.Cap;
       Other.clearInline();
       return *this;
     }
 
     std::swap(First, Other.First);
     std::swap(Last, Other.Last);
     std::swap(Cap, Other.Cap);
     Other.clear();
     return *this;
   }
 
   // NOLINTNEXTLINE(readability-identifier-naming)
   void push_back(const T &Elem) {
     if (Last == Cap)
       reserve(size() * 2);
     *Last++ = Elem;
   }
 
   // NOLINTNEXTLINE(readability-identifier-naming)
   void pop_back() {
     assert(Last != First && "Popping empty vector!");
     --Last;
   }
 
   void dropBack(size_t Index) {
     assert(Index <= size() && "dropBack() can't expand!");
     Last = First + Index;
   }
 
   T *begin() { return First; }
   T *end() { return Last; }
 
   bool empty() const { return First == Last; }
   size_t size() const { return static_cast<size_t>(Last - First); }
   T &back() {
     assert(Last != First && "Calling back() on empty vector!");
     return *(Last - 1);
   }
   T &operator[](size_t Index) {
     assert(Index < size() && "Invalid access!");
     return *(begin() + Index);
   }
   void clear() { Last = First; }
 
   ~PODSmallVector() {
     if (!isInline())
       std::free(First);
   }
 };
 
 // Base class of all AST nodes. The AST is built by the parser, then is
 // traversed by the printLeft/Right functions to produce a demangled string.
 class Node {
 public:
   enum Kind : unsigned char {
 #define ENUMERATOR(NodeKind) K ## NodeKind,
class ReferenceType : public Node {
   const Node *Pointee;
   ReferenceKind RK;
 
   mutable bool Printing = false;
 
   // Dig through any refs to refs, collapsing the ReferenceTypes as we go. The
   // rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any
   // other combination collapses to a lvalue ref.
+  //
+  // A combination of a TemplateForwardReference and a back-ref Substitution
+  // from an ill-formed string may have created a cycle; use cycle detection to
+  // avoid looping forever.
   std::pair<ReferenceKind, const Node *> collapse(OutputStream &S) const {
     auto SoFar = std::make_pair(RK, Pointee);
+    // Track the chain of nodes for the Floyd's 'tortoise and hare'
+    // cycle-detection algorithm, since getSyntaxNode(S) is impure
+    PODSmallVector<const Node *, 8> Prev;
     for (;;) {
       const Node *SN = SoFar.second->getSyntaxNode(S);
       if (SN->getKind() != KReferenceType)
         break;
       auto *RT = static_cast<const ReferenceType *>(SN);
       SoFar.second = RT->Pointee;
       SoFar.first = std::min(SoFar.first, RT->RK);
+
+      // The middle of `Prev` is the 'slow' pointer moving at half speed
+      Prev.push_back(SoFar.second);
+      if (Prev.size() > 1 && SoFar.second == Prev[(Prev.size() - 1) / 2]) {
+        // Cycle detected
+        SoFar.second = nullptr;
+        break;
+      }
     }
     return SoFar;
   }
 
 public:
   ReferenceType(const Node *Pointee_, ReferenceKind RK_)
       : Node(KReferenceType, Pointee_->RHSComponentCache),
         Pointee(Pointee_), RK(RK_) {}
 
   template<typename Fn> void match(Fn F) const { F(Pointee, RK); }
 
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Pointee->hasRHSComponent(S);
   }
 
   void printLeft(OutputStream &s) const override {
     if (Printing)
       return;
     SwapAndRestore<bool> SavePrinting(Printing, true);
     std::pair<ReferenceKind, const Node *> Collapsed = collapse(s);
+    if (!Collapsed.second)
+      return;
     Collapsed.second->printLeft(s);
     if (Collapsed.second->hasArray(s))
       s += " ";
     if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s))
       s += "(";
 
     s += (Collapsed.first == ReferenceKind::LValue ? "&" : "&&");
   }
   void printRight(OutputStream &s) const override {
     if (Printing)
       return;
     SwapAndRestore<bool> SavePrinting(Printing, true);
     std::pair<ReferenceKind, const Node *> Collapsed = collapse(s);
+    if (!Collapsed.second)
+      return;
     if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s))
       s += ")";
     Collapsed.second->printRight(s);
   }
 };
 
 class PointerToMemberType final : public Node {
   const Node *ClassType;