Traits.h marks std::list as trivially relocatable, but in fact it is not

[Quuxplusone]

Hi folks,

https://github.com/facebook/folly/blob/8fb5c15272a0dcdc/folly/Traits.h#L712 should be removed, as std::list<T> is never trivially relocatable on libstdc++ nor libc++. (The last heap-allocated element of the list holds a pointer into the list object itself; memcpying the list will break this pointer.)

Oh, and similarly, https://github.com/facebook/folly/blob/8fb5c15272a0dcdc/folly/Traits.h#L716 is wrong for at least libc++; I'm not sure about libstdc++.

Also, hi, this is Arthur O'Dwyer. I've got a WG21 proposal to standardize the Folly/EASTL/BSL notion of "trivially relocatable" into C++2a. I have wording and an implementation and everything. I am looking for coauthors, particularly coauthors who have been involved with the prior art in Folly. If you'd like to contribute and/or lend your support to P1144 Object relocation in terms of move plus destroy, please shoot me an email!

[Quuxplusone]

(See also: #35, #316, #498.)

[nbronson]

Hi Quuxplusone,

Can you give us more information about how you reached your conclusion for std::list? The heap allocated nodes form a circular list; there is no pointer back to the list object itself. When the list has one element, for example, it points to itself. This is true in both libstdc++ and libc++.

I don't know about std::function.

Thanks,
Nathan

[Quuxplusone]

Hi Nathan,

Right, the "circular" part of "circular list" is what causes the trouble.

Contrast these two diagrams from P0773R0:

The trick with std::list (and std::map and std::set, which were dealt with in #35) is that the heap-allocated nodes contain both forward ("next") and backward ("prev") pointers. The "prev" pointer of the first node, and the "next" pointer of the last node, both point to the node that is stored within the stack-allocated object itself. Quoting from P1144R0 draft revision 10:

std::list needs somewhere to store its "past-the-end" node, commonly referred to as the "sentinel node," whose prev pointer points to the list’s last node. If the sentinel node is allocated on the heap, then std::list can be trivially relocatable; but if the sentinel node is placed within the list object itself (as happens on libc++ and libstdc++), then relocating the list object requires fixing up the list’s last node’s next pointer so that it points to the new sentinel node inside the destination list object. This fixup of an arbitrary heap object cannot be simulated by memcpy.

You can verify for yourself the memcpyability of std::forward_list and std::vector, and the non-memcpyability of std::list and std::set, like this:

template<class Ctr>
void examine()
{
    Ctr a {1, 2, 3};
    alignas(Ctr) char buffer[sizeof(Ctr)];
    Ctr& b = *(Ctr*)buffer;
    
    memcpy(&b, &a, sizeof (Ctr));
    
    printf("Printing the elements of b:\n");
    for (auto&& elt : b) {
        printf("  %d\n", elt);
    }
}

[nbronson]

Thanks for the clarification, I was mistaken.

[Quuxplusone]

@nbronson: I've got a relatively exhaustive list of "what's trivially relocatable and what's not" for libc++, here: https://github.com/Quuxplusone/libcxx/blob/trivially-relocatable/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

(Godbolt)

I'd like to talk more via email and see if we can combine efforts. I'm coming around to the idea that the primary benefit of putting is_trivially_relocatable into the C++ Standard would be that library vendors are in a better position to judge the relocatability of their types than forcing that burden onto end-users like Folly, and I'm looking for evidence (anecdotal like #35, #316, #498, #889; or perhaps more-than-anecdotal if possible!) to support that general line of attack.

[yfeldblum]

I would love to see some common way for library authors to mark their own types as trivially-relocatable. And to see encouragement for types to be trivially-relocatable, and library optimizations for types which are trivially-relocatable.

Q: "trivially" modifies "relocatable" - what does it mean for a type to be relocatable but not trivially-relocatable? (Does a type being relocatable just mean it has both a destructor and a move-or-copy-constructor?)

[nbronson]

Could making relocation a first-class entity help with another problem we have, which is how to relocate a std::pair<const A,B> without copying the A (and without relying on a UB const_cast)?

[Quuxplusone]

Q: "trivially" modifies "relocatable" - what does it mean for a type to be relocatable but not trivially-relocatable? (Does a type being relocatable just mean it has both a destructor and a move-or-copy-constructor?)

Yes, that's how my paper defines it. The operation in general is "relocation"; a type that supports relocation is "relocatable"; and if relocation is tantamount to memcpy then it's "trivially relocatable." (And yes that's a bit different from how Folly calls it, but I think it is more consistent with the other C++11 type traits.)

Could making relocation a first-class entity help with another problem we have, which is how to relocate a std::pair<const A,B> without copying the A (and without relying on a UB const_cast)?

No, not as my paper defines it (because I don't really define it as a first-class entity). I'm not sure that we ought to be able to "relocate out of" const-qualified objects... I discuss this briefly in my blog post here in the context of swap: swap can be implemented in terms of relocate, instead of assignment. Does that mean we should be able to swap unassignable objects? I think not. Stealing-the-guts-out-of a const object, even as part of a relocate operation, seems kind of analogous, at least.