[lld-macho] Avoid using bump-alloc in TrieBuider

[oontvoo]

Summary

The code can be used in multi-threads and the allocator is not thread safe.

fixes PR/54378

[int3]

lld/MachO/ExportTrie.cpp

151–152

I don't think these calls are necessary; clear() will automatically happen when the std::vector destructors get called

153

nit: newline between functions

lld/MachO/ExportTrie.h

25

do we need this?

[oontvoo]

review comment

[int3]

lld/MachO/ExportTrie.h

25

sorry, I misread this as a ctor instead of a dtor. But I think explicit only applies to ctors, right?

[oontvoo]

removed explicit on dtor

[ronlieb]

breaking HIP and AMDGPU buildbots
https://lab.llvm.org/buildbot/#/builders/193/builds/8433
https://lab.llvm.org/buildbot/#/builders/165/builds/17691

please fix asap or revert
thx

[saugustine]

This change breaks the lld build with:

ERROR: /var/lib/buildkite-agent/.cache/bazel/_bazel_buildkite-agent/ac6467df252ff017b0d6ba076db369db/external/llvm-project/lld/BUILD.bazel:191:11: Compiling lld/MachO/ExportTrie.cpp failed: (Exit 1): clang failed: error executing command /usr/local/bin/clang -U_FORTIFY_SOURCE -fstack-protector -Wall -Wthread-safety -Wself-assign -fcolor-diagnostics -fno-omit-frame-pointer '-std=c++0x' -MD -MF ... (remaining 81 argument(s) skipped)
external/llvm-project/lld/MachO/ExportTrie.cpp:148:11: error: definition of implicitly declared destructor
TrieNode::~TrieNode() {
          ^
external/llvm-project/lld/MachO/ExportTrie.cpp:149:25: error: use of undeclared identifier 'nodes'; did you mean 'node'?
  for (TrieNode *node : nodes)
                        ^~~~~
                        node
external/llvm-project/lld/MachO/ExportTrie.cpp:149:18: note: 'node' declared here
  for (TrieNode *node : nodes)
                 ^
external/llvm-project/lld/MachO/ExportTrie.cpp:149:23: error: invalid range expression of type 'lld::macho::TrieNode *'; no viable 'begin' function available
  for (TrieNode *node : nodes)
                      ^ ~~~~~
3 errors generated.

Reverting shortly.

[saugustine]

Or, if you prefer the cmake version:

[159/255] Building CXX object tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.o
FAILED: tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.o 
/usr/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/usr/local/google/home/saugustine/llvm/build/tools/lld/MachO -I/usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO -I/usr/local/google/home/saugustine/llvm/llvm-project/lld/include -I/usr/local/google/home/saugustine/llvm/build/tools/lld/include -I/usr/local/google/home/saugustine/llvm/build/include -I/usr/local/google/home/saugustine/llvm/llvm-project/llvm/include -I/usr/local/google/home/saugustine/llvm/llvm-project/llvm/../libunwind/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -g  -fno-exceptions -fno-rtti -std=c++17 -MD -MT tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.o -MF tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.o.d -o tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.o -c /usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO/ExportTrie.cpp
/usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO/ExportTrie.cpp:148:11: error: definition of implicitly declared destructor
TrieNode::~TrieNode() {
          ^
/usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO/ExportTrie.cpp:149:25: error: use of undeclared identifier 'nodes'; did you mean 'node'?
  for (TrieNode *node : nodes)
                        ^~~~~
                        node
/usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO/ExportTrie.cpp:149:18: note: 'node' declared here
  for (TrieNode *node : nodes)
                 ^
/usr/local/google/home/saugustine/llvm/llvm-project/lld/MachO/ExportTrie.cpp:149:23: error: invalid range expression of type 'lld::macho::TrieNode *'; no viable 'begin' function available
  for (TrieNode *node : nodes)
                      ^ ~~~~~
3 errors generated.

[codemzs]

This change has broken windows builds:

FAILED: tools/lld/MachO/CMakeFiles/lldMachO.dir/ExportTrie.cpp.obj
C:\PROGRA2\MICROS1\2019\ENTERP1\VC\Tools\MSVC\14291.301\bin\Hostx64\x64\cl.exe /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -DSTDC_CONSTANT_MACROS -DSTDC_FORMAT_MACROS -DSTDC_LIMIT_MACROS -ID:\a_work\1\b\llvm\Debug\tools\lld\MachO -ID:\a_work\1\llvm-project\lld\MachO -ID:\a_work\1\llvm-project\lld\include -ID:\a_work\1\b\llvm\Debug\tools\lld\include -ID:\a_work\1\b\llvm\Debug\include -ID:\a_work\1\llvm-project\llvm\include -ID:\a_work\1\llvm-project\llvm..\libunwind\include /DWIN32 /D_WINDOWS /Zc:inline /Zc:cplusplus /Zc:strictStrings /Oi /Zc:rvalueCast /bigobj /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd4324 -w14062 -we4238 /MDd /Zi /Ob0 /Od /RTC1 -wd4530 -wd4062 /EHs-c- /GR- -std:c++14 /showIncludes /Fotools\lld\MachO\CMakeFiles\lldMachO.dir\ExportTrie.cpp.obj /Fdtools\lld\MachO\CMakeFiles\lldMachO.dir\lldMachO.pdb /FS -c D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): error C2600: 'lld::macho::TrieNode::~TrieNode': cannot define a compiler-generated special member function (must be declared in the class first)
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): error C2065: 'nodes': undeclared identifier
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): error C2672: 'begin': no matching overloaded function found
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C2893: Failed to specialize function template 'unknown-type std::begin(_Container &)'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\include\xutility(1916): note: see declaration of 'std::begin'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): note: With the following template arguments:
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): note: '_Container=unknown-type'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C2784: 'const _Elem *std::begin(std::initializer_list<_Elem>) noexcept': could not deduce template argument for 'std::initializer_list<_Elem>' from 'unknown-type'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\include\initializer_list(57): note: see declaration of 'std::begin'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): error C2672: 'end': no matching overloaded function found
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C2893: Failed to specialize function template 'unknown-type std::end(_Container &)'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\include\xutility(1926): note: see declaration of 'std::end'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): note: With the following template arguments:
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): note: '_Container=unknown-type'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C2784: 'const _Elem *std::end(std::initializer_list<_Elem>) noexcept': could not deduce template argument for 'std::initializer_list<_Elem>' from 'unknown-type'
C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\include\initializer_list(63): note: see declaration of 'std::end'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C3536: '$L0': cannot be used before it is initialized
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(150): error C3536: '$L0': cannot be used before it is initialized
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): error C2100: illegal indirection
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(148): note: This diagnostic occurred in the compiler generated function 'lld::macho::TrieNode::~TrieNode(void)'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): error C2440: 'initializing': cannot convert from 'int' to 'lld::macho::TrieNode *'
D:\a_work\1\llvm-project\lld\MachO\ExportTrie.cpp(149): note: Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast

[saugustine]

Reverted with ee7a286cd3e4364d2f7d5b6ba4b8a6fc0d524854

[codemzs]

In D121638#3380884, @saugustine wrote:

Reverted with ee7a286cd3e4364d2f7d5b6ba4b8a6fc0d524854

Thank you!

[oontvoo]

Thanks for the revert! @saugustine

[oontvoo]

Relanded at https://reviews.llvm.org/rGee7a286cd3e4

lld/MachO/ExportTrie.h

 namespace lld {
 namespace macho {
 
 struct TrieNode;
 class Symbol;
 
 class TrieBuilder {
 public:
+  ~TrieBuilder();
   void setImageBase(uint64_t addr) { imageBase = addr; }
   void addSymbol(const Symbol &sym) { exported.push_back(&sym); }
   // Returns the size in bytes of the serialized trie.
   size_t build();
   void writeTo(uint8_t *buf) const;
 
 private:
   TrieNode *makeNode();

lld/MachO/ExportTrie.cpp

void TrieNode::writeTo(uint8_t *buf) const {
   for (const Edge &edge : edges) {
     memcpy(buf, edge.substring.data(), edge.substring.size());
     buf += edge.substring.size();
     *buf++ = '\0';
     buf += encodeULEB128(edge.child->offset, buf);
   }
 }
 
+TrieNode::~TrieNode() {
+  for (TrieNode *node : nodes)
+    delete node;
+}
+
 TrieNode *TrieBuilder::makeNode() {
-  auto *node = make<TrieNode>();
+  auto *node = new TrieNode();
   nodes.emplace_back(node);
   return node;
 }
 
 static int charAt(const Symbol *sym, size_t pos) {
   StringRef str = sym->getName();
   if (pos >= str.size())
     return -1;