Implementation

P1144R2 Object relocation in terms of move plus destroy

1.2. The most important benefit

But this merely encourages the programmer to add the warrant and continue. An incorrect warrant will be discovered only at runtime, via undefined behavior. (See Allocated memory contains pointer to self and [FollyIssue889].)

    class Gadget {
        std::list<int> lst_;
    };
    // sigh, add the warrant on autopilot
    template<> struct folly::IsRelocatable<Gadget> : std::true_type {};

    folly::fbvector<Gadget> vec;  // CRASHES AT RUNTIME due to fraudulent warrant

If this proposal is adopted, then Folly can start using static_assert(std::is_trivially_relocatable_v<T>) in the implementation of fbvector, and the programmer can stop writing explicit warrants. Finally, the programmer can start writing assertions of correctness, which aids maintainability and can even find real bugs. Example:

    class Widget {
        std::vector<int> lst_;
    };
    static_assert(std::is_trivially_relocatable_v<Widget>);  // correctly SUCCEEDS

    class Gadget {
        std::list<int> lst_;
    };
    static_assert(std::is_trivially_relocatable_v<Gadget>);  // correctly ERRORS OUT

The improvement in user experience for real-world codebases (such as [Folly], [EASTL], BDE, Qt, etc.) is the most important benefit to be gained by this proposal.

Allocated memory contains pointer to self

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.

Traditional implementations of std::set and std::map also store a "past-the-end" node inside themselves and thus also fall into this category.

struct node
{
    node *prev_ = nullptr;
    node *next_ = nullptr;
};
struct list
{
    node n_; // sentinel node
    iterator begin()
    {
        return iterator(n_.next_);
    }
    iterator end()
    {
        return iterator(&n_);
    }
    list(list &&l)
    {
        if (l.n_.next_)
            l.n_.next_->prev_ = &n_;  // fixup
        if (l.n_.prev_)
            l.n_.prev_->next_ = &n_;  // fixup
        n_ = l.n_;
        l.n_ = node { };
    }
    // ...
};

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

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.)

NOTE:

1、Allocated memory contains pointer to self

2、导致dangling

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++.

Quuxplusone commented on 31 Jul 2018

Hi Nathan,

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

Contrast these two diagrams from P0773R0:

[

NOTE:

1、从上述的picture来看，std::forward_list不是sentinel-node container，这意味着: 它的move可以是trivial的，因为通过copy即可以实现ownership transfer，不需要像std::list那样进行fixup。

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:

#include <cstdio>
#include <cstring>
#include <forward_list>
#include <list>
#include <set>
#include <unordered_set>
#include <vector>

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);
    }
}

int main()
{
    examine<std::forward_list<int>>();  // OK
    examine<std::vector<int>>();  // OK
    //examine<std::list<int>>();  // infinite loop
    //examine<std::set<int>>();  // segfault
}
// g++ test.cpp --std=c++11 -pedantic -Wall