DWARFVerifier: Change vector of IntervalMap to vector of unique_ptrs

[kparzysz]

Summary

This is a workaround for compilation issue on FreeBSD. See comments in https://reviews.llvm.org/rG0d8cb8b399ad for more information.

This fixes https://github.com/llvm/llvm-project/issues/55414.

[dblaikie]

Some more details on the specifics in the patch description would be good - I'm still not 100% clear on the reproduction case to understand what we're working around, exactly. Do you have a godbolt reproduction/small example, by chance?

[dim]

In D125611#3517574, @dblaikie wrote:

Some more details on the specifics in the patch description would be good - I'm still not 100% clear on the reproduction case to understand what we're working around, exactly. Do you have a godbolt reproduction/small example, by chance?

Assuming there's a directory with llvm includes, this is enough to reproduce:

#include "llvm/ADT/IntervalMap.h"
#include <vector>

void f(std::size_t size)
{
  using namespace llvm;

  IntervalMap<uint32_t, uint64_t>::Allocator Alloc;
  std::vector<IntervalMap<uint32_t, uint64_t>> Sections(size, IntervalMap<uint32_t, uint64_t>(Alloc));
}

which will (on FreeBSD at least, where libc++ is the standard C++ library) result in something like:

$ clang++ -I llvm/include -c intervalmap.cpp
In file included from intervalmap.cpp:1:
In file included from llvm/include/llvm/ADT/IntervalMap.h:108:
In file included from llvm/include/llvm/ADT/SmallVector.h:19:
In file included from /usr/include/c++/v1/algorithm:643:
/usr/include/c++/v1/memory:1809:31: error: call to implicitly-deleted copy constructor of 'llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>'
            ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
                              ^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/v1/memory:1687:21: note: in instantiation of function template specialization 'std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>::construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
                __a.construct(__p, _VSTD::forward<_Args>(__args)...);
                    ^
/usr/include/c++/v1/memory:1538:14: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::__construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
            {__construct(__has_construct<allocator_type, _Tp*, _Args...>(),
             ^
/usr/include/c++/v1/vector:1066:25: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
        __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), __x);
                        ^
/usr/include/c++/v1/vector:1159:9: note: in instantiation of member function 'std::__1::vector<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::__construct_at_end' requested here
        __construct_at_end(__n, __x);
        ^
intervalmap.cpp:9:48: note: in instantiation of member function 'std::__1::vector<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::vector' requested here
  std::vector<IntervalMap<uint32_t, uint64_t>> Sections(size, IntervalMap<uint32_t, uint64_t>(Alloc));
                                               ^
llvm/include/llvm/ADT/IntervalMap.h:970:14: note: copy constructor of 'IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>' is implicitly deleted because variant field 'leaf' has a non-trivial copy constructor
    RootLeaf leaf;
             ^
1 error generated.

Ultimately, this is caused by _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR in /usr/include/c++/v1/__config (this was last modified by @EricWF, but a long time ago). If this setting is enabled (to preserve the old ABI), std::pair will always have a non-trivial copy constructor, and since IntervalMap contains a std::pair (via RootLeaf -> IntervalMapImpl::LeafNode -> NodeBase<std::pair<KeyT, KeyT>, ValT, N>), IntervalMap itself is also non-trivially copyable. std::vector in turn requires its value type to be copy-constructible (at least certainly when you use the constructor with a size).

I think this patch, using a unique_ptr sidesteps this issue by letting unique_ptr taking care of things. Another way would be to provide a hand-written copy constructor or move constructor for IntervalMap.

[dblaikie]

In D125611#3519571, @dim wrote:

In D125611#3517574, @dblaikie wrote:

Some more details on the specifics in the patch description would be good - I'm still not 100% clear on the reproduction case to understand what we're working around, exactly. Do you have a godbolt reproduction/small example, by chance?

Assuming there's a directory with llvm includes, this is enough to reproduce:

#include "llvm/ADT/IntervalMap.h"
#include <vector>

void f(std::size_t size)
{
  using namespace llvm;

  IntervalMap<uint32_t, uint64_t>::Allocator Alloc;
  std::vector<IntervalMap<uint32_t, uint64_t>> Sections(size, IntervalMap<uint32_t, uint64_t>(Alloc));
}

which will (on FreeBSD at least, where libc++ is the standard C++ library) result in something like:

$ clang++ -I llvm/include -c intervalmap.cpp
In file included from intervalmap.cpp:1:
In file included from llvm/include/llvm/ADT/IntervalMap.h:108:
In file included from llvm/include/llvm/ADT/SmallVector.h:19:
In file included from /usr/include/c++/v1/algorithm:643:
/usr/include/c++/v1/memory:1809:31: error: call to implicitly-deleted copy constructor of 'llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>'
            ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
                              ^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/v1/memory:1687:21: note: in instantiation of function template specialization 'std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>::construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
                __a.construct(__p, _VSTD::forward<_Args>(__args)...);
                    ^
/usr/include/c++/v1/memory:1538:14: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::__construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
            {__construct(__has_construct<allocator_type, _Tp*, _Args...>(),
             ^
/usr/include/c++/v1/vector:1066:25: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::construct<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, const llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>> &>' requested here
        __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), __x);
                        ^
/usr/include/c++/v1/vector:1159:9: note: in instantiation of member function 'std::__1::vector<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::__construct_at_end' requested here
        __construct_at_end(__n, __x);
        ^
intervalmap.cpp:9:48: note: in instantiation of member function 'std::__1::vector<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>, std::__1::allocator<llvm::IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>>>::vector' requested here
  std::vector<IntervalMap<uint32_t, uint64_t>> Sections(size, IntervalMap<uint32_t, uint64_t>(Alloc));
                                               ^
llvm/include/llvm/ADT/IntervalMap.h:970:14: note: copy constructor of 'IntervalMap<unsigned int, unsigned long, 12, llvm::IntervalMapInfo<unsigned int>>' is implicitly deleted because variant field 'leaf' has a non-trivial copy constructor
    RootLeaf leaf;
             ^
1 error generated.

Ultimately, this is caused by _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR in /usr/include/c++/v1/__config (this was last modified by @EricWF, but a long time ago). If this setting is enabled (to preserve the old ABI), std::pair will always have a non-trivial copy constructor, and since IntervalMap contains a std::pair (via RootLeaf -> IntervalMapImpl::LeafNode -> NodeBase<std::pair<KeyT, KeyT>, ValT, N>), IntervalMap itself is also non-trivially copyable. std::vector in turn requires its value type to be copy-constructible (at least certainly when you use the constructor with a size).

I was hoping something I could reproduce without having FreeBSD myself - either on godbolt (though godbolt might not have different OS platforms as a primary feature) or something like that. Or a brief example that emulates the quirk of FreeBSD to better understand what we're working around here.

I think this patch, using a unique_ptr sidesteps this issue by letting unique_ptr taking care of things. Another way would be to provide a hand-written copy constructor or move constructor for IntervalMap.

That seems likely to be a better solution - if that's closer to the root cause, less chance someone else will introduce a similarly problematic use of IntervalMap that way (since the use will be no longer problematic).

Oh, OK, so piecing this together from the various discussions: FreeBSD opted to not pickup an ABI-breaking fix to libc++'s std::pair that would've made std::pair of two trivially copyable types itself trivially copyable. And so without that fix, IntervalMap is not trivially copyable/implicitly copyable because it has a union over a non-trivial type (RootLeaf -> LeafNode -> NodeBase<pair<KeyT, KeyT>... -> which has a member of that pair<KeyT, KeyT> type (well, an array of them))

So, yeah, I guess adding a copy and/or move constructor to IntervalMap would be more suitable.

[dim]

In D125611#3520595, @dblaikie wrote:

In D125611#3519571, @dim wrote:

...

Ultimately, this is caused by _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR in /usr/include/c++/v1/__config (this was last modified by @EricWF, but a long time ago). If this setting is enabled (to preserve the old ABI), std::pair will always have a non-trivial copy constructor, and since IntervalMap contains a std::pair (via RootLeaf -> IntervalMapImpl::LeafNode -> NodeBase<std::pair<KeyT, KeyT>, ValT, N>), IntervalMap itself is also non-trivially copyable. std::vector in turn requires its value type to be copy-constructible (at least certainly when you use the constructor with a size).

I was hoping something I could reproduce without having FreeBSD myself - either on godbolt (though godbolt might not have different OS platforms as a primary feature) or something like that. Or a brief example that emulates the quirk of FreeBSD to better understand what we're working around here.

The original problem was more accurately described by Howard Hinnant in rL194536 (rGccad8c32e088):

Unfortunately (for libc++1) the Itanium ABI specifies different calling conventions for trivial and non-trivial copy constructors. Therefore currently the C++03 libc++ copy constructor for pair<int, int> is ABI incompatible with the C++11 libc++ copy constructor for pair<int, int>. This is Bad(tm).

This is the original reason for changing the std::pair copy constructor to be trivial in all cases. In a follow-up commit rL194742 (rGf9fd0d6d113c) Howard added a _LIBCPP_TRIVIAL_PAIR_COPY_CTOR define to be able to toggle this triviality on and off. Initially it was only turned off on Apple platforms, but later FreeBSD was added too.

Eventually the _LIBCPP_TRIVIAL_PAIR_COPY_CTOR define got renamed a few times, and then deprecated, but it is still carried around; I guess only libc++ ABI 2 will finally solve this for all downstream consumers. :-)

In any case, you can test this fairly easily on other platforms, assuming you can use libc++ headers, by compiling e.g. DWARFVerifier.cpp with -D_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR on the compiler command line. This should give you the same error as shown earlier.

I think this patch, using a unique_ptr sidesteps this issue by letting unique_ptr taking care of things. Another way would be to provide a hand-written copy constructor or move constructor for IntervalMap.

That seems likely to be a better solution - if that's closer to the root cause, less chance someone else will introduce a similarly problematic use of IntervalMap that way (since the use will be no longer problematic).

I guess a copy constructor for IntervalMap is not too hard, indeed.

Oh, OK, so piecing this together from the various discussions: FreeBSD opted to not pickup an ABI-breaking fix to libc++'s std::pair that would've made std::pair of two trivially copyable types itself trivially copyable. And so without that fix, IntervalMap is not trivially copyable/implicitly copyable because it has a union over a non-trivial type (RootLeaf -> LeafNode -> NodeBase<pair<KeyT, KeyT>... -> which has a member of that pair<KeyT, KeyT> type (well, an array of them))

Indeed, when _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR is defined (either manually, or in libc++'s __config header), all std::pair instances are non-trivially copyable.

[kparzysz]

In D125611#3520595, @dblaikie wrote:

That seems likely to be a better solution - if that's closer to the root cause, less chance someone else will introduce a similarly problematic use of IntervalMap that way (since the use will be no longer problematic).

I chose this approach because I wanted the workarounds to be "more superficial", and appear less like a design choice. I guess it will be a while before all supported FreeBSD versions no longer need it, so it likely does make sense to fix it in one place.

I'm abandoning this review, I have created a new one: https://reviews.llvm.org/D125899.

[dblaikie]

Looking at D125899 in more detail I'm OK with deciding that adding good quality copy/move semantics to IntervalMap is a bigger project than I'm up for right now & so let's go with this direction instead (sorry for the back and forth - thanks for understanding).

If you want to submit a follow-up patch to disable copy/move (construction and assignment) for IntervalMap, that'd be great, otherwise I can do that once this lands.

llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp

426

Perhaps this could be:

auto &M = *Sections[Col];

To keep the rest of the code simpler/without having to add a few ->?

[kparzysz]

Changed type of M.

[dblaikie]

Looks good - thanks for your patience & considering alternatives/helping me understand what was going on here.

[kparzysz]

In D125611#3535537, @dblaikie wrote:

If you want to submit a follow-up patch to disable copy/move (construction and assignment) for IntervalMap, that'd be great, otherwise I can do that once this lands.

Right here: https://reviews.llvm.org/D126401

[dim]

Thanks a lot. I'll make sure to put up a libc++ review now to get rid of the FreeBSD std::pair problem in the future! :)

llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp

unsigned DWARFVerifier::verifyIndex(StringRef Name,
                                     StringRef IndexStr) {
   if (IndexStr.empty())
     return 0;
   OS << "Verifying " << Name << "...\n";
   DWARFUnitIndex Index(InfoColumnKind);
   DataExtractor D(IndexStr, DCtx.isLittleEndian(), 0);
   if (!Index.parse(D))
     return 1;
-  IntervalMap<uint32_t, uint64_t>::Allocator Alloc;
-  std::vector<IntervalMap<uint32_t, uint64_t>> Sections(
-      Index.getColumnKinds().size(), IntervalMap<uint32_t, uint64_t>(Alloc));
+  using MapType = IntervalMap<uint32_t, uint64_t>;
+  MapType::Allocator Alloc;
+  std::vector<std::unique_ptr<MapType>> Sections(Index.getColumnKinds().size());
   for (const DWARFUnitIndex::Entry &E : Index.getRows()) {
     uint64_t Sig = E.getSignature();
     if (!E.getContributions())
       continue;
     for (auto E : enumerate(InfoColumnKind == DW_SECT_INFO
                                 ? makeArrayRef(E.getContributions(),
                                                Index.getColumnKinds().size())
                                 : makeArrayRef(E.getContribution(), 1))) {
       const DWARFUnitIndex::Entry::SectionContribution &SC = E.value();
       int Col = E.index();
       if (SC.Length == 0)
         continue;
+      if (!Sections[Col])
+        Sections[Col] = std::make_unique<MapType>(Alloc);
       auto &M = Sections[Col];
-      auto I = M.find(SC.Offset);
-      if (I != M.end() && I.start() < (SC.Offset + SC.Length)) {
+      auto I = M->find(SC.Offset);
+      if (I != M->end() && I.start() < (SC.Offset + SC.Length)) {
         error() << llvm::formatv(
             "overlapping index entries for entries {0:x16} "
             "and {1:x16} for column {2}\n",
             *I, Sig, toString(Index.getColumnKinds()[Col]));
         return 1;
       }
-      M.insert(SC.Offset, SC.Offset + SC.Length - 1, Sig);
+      M->insert(SC.Offset, SC.Offset + SC.Length - 1, Sig);
     }
   }
 
   return 0;
 }
 
 bool DWARFVerifier::handleDebugCUIndex() {
   return verifyIndex(".debug_cu_index", DWARFSectionKind::DW_SECT_INFO,