VLA reserve()/shrink_to_fit() byte-relocate non-trivially-copyable elements via allocator reallocate (UB) #213

// VLA reserve()/shrink_to_fit() relocate live non-trivially-copyable elements with a byte copy.
#include "cetl/pf17/cetlpf.hpp"
#include "cetl/pf17/sys/memory_resource.hpp"
#include "cetl/variable_length_array.hpp"

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>

// An element whose invariant depends on its own address, the way libstdc++'s SSO std::string does.
struct SelfRef
{
    int  value;
    int* self;

    explicit SelfRef(int v) noexcept
        : value{v}
        , self{&value}
    {
    }
    SelfRef(const SelfRef& rhs) noexcept
        : value{rhs.value}
        , self{&value}
    {
    }
    SelfRef(SelfRef&& rhs) noexcept
        : value{rhs.value}
        , self{&value}
    {
    }
    SelfRef& operator=(const SelfRef& rhs) noexcept
    {
        value = rhs.value;
        return *this;
    }
    ~SelfRef() = default;

    bool intact() const noexcept
    {
        return self == &value;
    }
};

// A conforming memory_resource whose reallocate always moves the block, as std::realloc may.
class AlwaysMovingResource final : public cetl::pf17::pmr::memory_resource
{
    void* do_allocate(std::size_t size_bytes, std::size_t) override
    {
        return std::malloc(size_bytes);
    }
    void do_deallocate(void* p, std::size_t, std::size_t) override
    {
        std::free(p);
    }
    void* do_reallocate(void* p, std::size_t old_size_bytes, std::size_t new_size_bytes, std::size_t) override
    {
        void* moved = std::malloc(new_size_bytes);
        std::memcpy(moved, p, (old_size_bytes < new_size_bytes) ? old_size_bytes : new_size_bytes);
        std::free(p);
        return moved;
    }
    bool do_is_equal(const memory_resource& rhs) const noexcept override
    {
        return &rhs == this;
    }
};

template <typename T>
using Vla = cetl::VariableLengthArray<T, cetl::pf17::pmr::polymorphic_allocator<T>>;

static int broken(const Vla<SelfRef>& vla)
{
    int n = 0;
    for (const auto& e : vla)
    {
        n += e.intact() ? 0 : 1;
    }
    return n;
}

int main()
{
    int failures = 0;

    // 1. reserve() growth with a resource that moves on reallocate.
    {
        AlwaysMovingResource resource;
        Vla<SelfRef>         vla{cetl::pf17::pmr::polymorphic_allocator<SelfRef>{&resource}};
        vla.reserve(2);
        vla.emplace_back(1);
        vla.emplace_back(2);
        vla.reserve(64);
        const int b = broken(vla);
        std::printf("reserve, moving resource:        %d of %zu elements broken\n", b, vla.size());
        failures += b;
    }

    // 2. shrink_to_fit() with a resource that moves on reallocate.
    {
        AlwaysMovingResource resource;
        Vla<SelfRef>         vla{cetl::pf17::pmr::polymorphic_allocator<SelfRef>{&resource}};
        vla.reserve(64);
        vla.emplace_back(1);
        vla.emplace_back(2);
        vla.shrink_to_fit();
        const int b = broken(vla);
        std::printf("shrink_to_fit, moving resource:  %d of %zu elements broken\n", b, vla.size());
        failures += b;
    }

    // 3. CETL's default pf17 new_delete_resource(), which reallocates with std::realloc. Whether realloc moves
    //    the block is up to the C library; growing well past the original size usually forces it.
    {
        Vla<SelfRef> vla{cetl::pf17::pmr::polymorphic_allocator<SelfRef>{cetl::pf17::pmr::new_delete_resource()}};
        vla.reserve(1);
        vla.emplace_back(1);
        const void* before = vla.data();
        vla.reserve(1U << 20U);
        const int b = broken(vla);
        std::printf("reserve, new_delete_resource():  %d of %zu elements broken (block %s)\n",
                    b,
                    vla.size(),
                    (before == vla.data()) ? "extended in place" : "moved");
        failures += b;
    }

    // 4. A real standard type. libstdc++'s std::string points into its own SSO buffer; libc++'s does not.
    {
        AlwaysMovingResource resource;
        Vla<std::string>     vla{cetl::pf17::pmr::polymorphic_allocator<std::string>{&resource}};
        vla.reserve(1);
        vla.emplace_back("short");
        vla.reserve(64);
        // With libstdc++ the string's data pointer now refers to the freed old block: reading it is a use after free.
        const bool dangling = (static_cast<const void*>(vla[0].data()) != static_cast<const void*>(&vla[0]) &&
                               vla[0].size() < 15U &&
                               (reinterpret_cast<const char*>(vla[0].data()) < reinterpret_cast<const char*>(&vla[0]) ||
                                reinterpret_cast<const char*>(vla[0].data()) >=
                                    reinterpret_cast<const char*>(&vla[0] + 1)));
        std::printf("reserve, std::string (SSO):      %s\n",
                    dangling ? "data() points outside the object (dangling SSO pointer)" : "not affected on this library");
        failures += dangling ? 1 : 0;
    }

    return (failures == 0) ? 0 : 1;
}