[clangd] Crash in __memcmp_avx2_movbe

[ivanmurashko]

Summary

There is a clangd crash at __memcmp_avx2_movbe. Short problem description is below.

The method HeaderIncludes::addExistingInclude stores Include objects by reference at 2 places: ExistingIncludes (primary storage) and IncludesByPriority (pointer to the object's location at ExistingIncludes). ExistingIncludes is a map where value is a SmallVector. A new element is inserted by push_back. The operation might do resize. As result pointers stored at IncludesByPriority might become invalid.

Typical stack trace

    frame #0: 0x00007f11460dcd94 libc.so.6`__memcmp_avx2_movbe + 308
    frame #1: 0x00000000004782b8 clangd`llvm::StringRef::compareMemory(Lhs="
\"t2.h\"", Rhs="", Length=6) at StringRef.h:76:22
    frame #2: 0x0000000000701253 clangd`llvm::StringRef::compare(this=0x0000
7f10de7d8610, RHS=(Data = "", Length = 7166742329480737377)) const at String
Ref.h:206:34
  * frame #3: 0x00000000007603ab clangd`llvm::operator<(llvm::StringRef, llv
m::StringRef)(LHS=(Data = "\"t2.h\"", Length = 6), RHS=(Data = "", Length =
7166742329480737377)) at StringRef.h:907:23
    frame #4: 0x0000000002d0ad9f clangd`clang::tooling::HeaderIncludes::inse
rt(this=0x00007f10de7fb1a0, IncludeName=(Data = "t2.h\"", Length = 4), IsAng
led=false) const at HeaderIncludes.cpp:365:22
    frame #5: 0x00000000012ebfdd clangd`clang::clangd::IncludeInserter::inse
rt(this=0x00007f10de7fb148, VerbatimHeader=(Data = "\"t2.h\"", Length = 6))
const at Headers.cpp:262:70

A unit test test for the crash was created (HeaderIncludesTest.RepeatedIncludes). The proposed solution is to use std::list instead of llvm::SmallVector

Test Plan

./tools/clang/unittests/Tooling/ToolingTests --gtest_filter=HeaderIncludesTest.RepeatedIncludes

[ivanmurashko]

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

328 ↗

(On Diff #405153)

The crash is caused by vector resize initiated by this line

[DmitryPolukhin]

@ivanmurashko

Overall looks good to me but please re-upload patch on top of some stable revision where failed test passes (it seems unrelated to your changes).

struct Include is a light weight structure so having a copy seems to be the simplest solution.

[ivanmurashko]

rebase

[ivanmurashko]

rebase

[sammccall]

Thanks! This fix makes sense to me.

clang-tools-extra/clangd/test/repeated_includes.test

1 ↗

(On Diff #405886)

This should be tested more directly rather than via clangd, e.g. rather in clang/unittests/Tooling/HeaderIncludesTest.cpp

clang/include/clang/Tooling/Inclusions/HeaderIncludes.h

101–102

An alternative would be to use a std::forward_list<Include> here.

This guarantees pointer stability, it's an extra allocation but seems unlikely to matter.

It would be more robust if the data structure changes (e.g. becomes large, or is mutated after creation) but probably none of this will ever happen.

Up to you.

[ivanmurashko]

There are some changes:

• unit test for HeaderIncludes was added
• lit test for clangd was removed
• Solution uses std::list instead of copying by value

[ivanmurashko]

clang/include/clang/Tooling/Inclusions/HeaderIncludes.h

101–102

I changed my solution accordingly this suggestion.
Small note: The std::list seems to be more suitable here as soon as the last element of the structure is used at the code.

[sammccall]

Thanks, looks good!

[sammccall]

clang/include/clang/Tooling/Inclusions/HeaderIncludes.h

101–102

May be worth a comment here that std::list is used for pointer stability, since it looks a little odd at first glance.

[ivanmurashko]

Comment about std::list was added

[ivanmurashko]

comment update

[sammccall]

Do you have access to commit this or should I land it for you?

[ivanmurashko]

In D118755#3301776, @sammccall wrote:

Do you have access to commit this or should I land it for you?

@sammccall, I would appreciate your assistance in the land. You can use the following email address: ivan.murashko at gmail.com

clang/include/clang/Tooling/Inclusions/HeaderIncludes.h

 //===--- HeaderIncludes.h - Insert/Delete #includes for C++ code--*- C++-*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_INCLUSIONS_HEADERINCLUDES_H
 #define LLVM_CLANG_TOOLING_INCLUSIONS_HEADERINCLUDES_H
 
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Inclusions/IncludeStyle.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
+#include <list>
 #include <unordered_map>
 
 namespace clang {
 namespace tooling {
 
 /// This class manages priorities of C++ #include categories and calculates
 /// priorities for headers.
 /// FIXME(ioeric): move this class into implementation file when clang-format's
private:
   void addExistingInclude(Include IncludeToAdd, unsigned NextLineOffset);
 
   std::string FileName;
   std::string Code;
 
   // Map from include name (quotation trimmed) to a list of existing includes
   // (in case there are more than one) with the name in the current file. <x>
   // and "x" will be treated as the same header when deleting #includes.
-  llvm::StringMap<llvm::SmallVector<Include, 1>> ExistingIncludes;
+  // std::list is used for pointers stability (see IncludesByPriority)
+  llvm::StringMap<std::list<Include>> ExistingIncludes;
 
   /// Map from priorities of #include categories to all #includes in the same
   /// category. This is used to find #includes of the same category when
   /// inserting new #includes. #includes in the same categories are sorted in
   /// in the order they appear in the source file.
   /// See comment for "FormatStyle::IncludeCategories" for details about include
   /// priorities.
   std::unordered_map<int, llvm::SmallVector<const Include *, 8>>

clang/unittests/Tooling/HeaderIncludesTest.cpp

 
 TEST_F(HeaderIncludesTest, NoExistingIncludeWithoutDefine) {
   std::string Code = "int main() {}";
   std::string Expected = "#include \"a.h\"\n"
                          "int main() {}";
   EXPECT_EQ(Expected, insert(Code, "\"a.h\""));
 }
 
+TEST_F(HeaderIncludesTest, RepeatedIncludes) {
+  std::string Code;
+  for (int i = 0; i < 100; ++i) {
+    Code += "#include \"a.h\"\n";
+  }
+  std::string Expected = Code + "#include \"a2.h\"\n";
+  EXPECT_EQ(Expected, insert(Code, "\"a2.h\""));
+}
+
 TEST_F(HeaderIncludesTest, NoExistingIncludeWithDefine) {
   std::string Code = "#ifndef A_H\n"
                      "#define A_H\n"
                      "class A {};\n"
                      "#define MMM 123\n"
                      "#endif";
   std::string Expected = "#ifndef A_H\n"
                          "#define A_H\n"