[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

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

2

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

100

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

100

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

100

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-tools-extra/clangd/test/repeated_includes.test

+# RUN: rm -rf %/t
+# RUN: mkdir -p %t && touch %t/t.h && touch %t/t2.h && touch %t/t3.h
+# RUN: echo '#pragma once' > %t/t.h
+# RUN: echo '#include "t2.h"' >> %t/t.h
+# RUN: echo 'void bar();' >> %t/t.h
+# RUN: echo '#pragma once' > %t/t2.h
+# RUN: echo 'void bar2();' >> %t/t2.h
+
+
+# Run clangd
+# RUN: clangd -lit-test -log error --path-mappings 'C:\client=%t' < %s | FileCheck -strict-whitespace %s
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"file:///C:/client/main.cpp","languageId":"cpp","version":1,"text":"#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\n#include \"t.h\"\nbar();\n"}}}
+---
+{"jsonrpc":"2.0","id":1,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///C:/client/main.cpp"},"position":{"line":40,"character":3}}}
+#      CHECK:  "id": 1
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": {
+# CHECK-NEXT:    "isIncomplete": false,
+# CHECK-NEXT:    "items": [
+# CHECK-NEXT:      {
+# CHECK-NEXT:        "detail": "void",
+# CHECK-NEXT:        "documentation": {
+# CHECK-NEXT:          "kind": "plaintext",
+# CHECK-NEXT:          "value": "From \"t.h\""
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "filterText": "bar",
+# CHECK-NEXT:        "insertText": "bar",
+---
+{"jsonrpc":"2.0","id":4,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

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

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;
 
   /// 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>>
-      IncludesByPriority;
+  std::unordered_map<int, llvm::SmallVector<Include, 8>> IncludesByPriority;
 
   int FirstIncludeOffset;
   // All new headers should be inserted after this offset (e.g. after header
   // guards, file comment).
   unsigned MinInsertOffset;
   // Max insertion offset in the original code. For example, we want to avoid
   // inserting new #includes into the actual code section (e.g. after a
   // declaration).

clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
 }
 
 // \p Offset: the start of the line following this include directive.
 void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
                                         unsigned NextLineOffset) {
   auto Iter =
       ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first;
   Iter->second.push_back(std::move(IncludeToAdd));
   auto &CurInclude = Iter->second.back();
   // The header name with quotes or angle brackets.
   // Only record the offset of current #include if we can insert after it.
   if (CurInclude.R.getOffset() <= MaxInsertOffset) {
     int Priority = Categories.getIncludePriority(
         CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0);
     CategoryEndOffsets[Priority] = NextLineOffset;
-    IncludesByPriority[Priority].push_back(&CurInclude);
+    IncludesByPriority[Priority].push_back(CurInclude);
     if (FirstIncludeOffset < 0)
       FirstIncludeOffset = CurInclude.R.getOffset();
   }
 }
 
 llvm::Optional<tooling::Replacement>
 HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
   assert(IncludeName == trimInclude(IncludeName));
HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
   StringRef QuotedName = Quoted;
   int Priority = Categories.getIncludePriority(
       QuotedName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
   auto CatOffset = CategoryEndOffsets.find(Priority);
   assert(CatOffset != CategoryEndOffsets.end());
   unsigned InsertOffset = CatOffset->second; // Fall back offset
   auto Iter = IncludesByPriority.find(Priority);
   if (Iter != IncludesByPriority.end()) {
-    for (const auto *Inc : Iter->second) {
-      if (QuotedName < Inc->Name) {
-        InsertOffset = Inc->R.getOffset();
+    for (const auto &Inc : Iter->second) {
+      if (QuotedName < Inc.Name) {
+        InsertOffset = Inc.R.getOffset();
         break;
       }
     }
   }
   assert(InsertOffset <= Code.size());
   std::string NewInclude =
       std::string(llvm::formatv("#include {0}\n", QuotedName));
   // When inserting headers at end of the code, also append '\n' to the code