Track and trace allocations

Question

When testing or debugging allocator-aware objects, it can be useful to provide allocators that can provide insight into how they get called. The Tracing_alloc from A fixed-size dynamic array is a reasonable starting point, upon which I've built.

I provide four allocator adapters, which all modify an underlying allocator:

• logged, which records each operation to the standard log stream,
• checked, which ensures that operations are correctly paired,
• shared_copyable, which allows a move-only allocator to be used in objects that expect to copy it, and
• no_delete_exceptions, which converts exceptions in deallocate() and destruct() into messages directed to the error stream.

#ifndef ALLOCATOR_TRACING_HPP
#define ALLOCATOR_TRACING_HPP

#include <algorithm>
#include <format>
#include <iostream>
#include <map>
#include <memory>
#include <ranges>
#include <stdexcept>
#include <utility>
#include <vector>

namespace alloc {

    // Tracing allocator, based on a class written by L.F.
    // <URI: https://codereview.stackexchange.com/q/221719/75307 >

    template<typename Base>
    requires requires { typename std::allocator_traits<Base>; }
    struct logged : Base
    {
        using traits = std::allocator_traits<Base>;
        using value_type = traits::value_type;
        using pointer = traits::pointer;

        // Since our first (only) template argument is _not_ the same
        // as value_type, we must provide rebind.
        template<class T>
        struct rebind { using other = logged<typename traits::rebind_alloc<T>>; };

        using Base::Base;

        pointer allocate(std::size_t n)
        {
            std::clog << "allocate " << n;
            pointer p;
            try {
                p = traits::allocate(*this, n);
            } catch (...) {
                std::clog << " FAILED\n";
                throw;
            }
            const void *const pv = p;
            std::clog << " = " << pv << '\n';
            return p;
        }

        void deallocate(pointer p, std::size_t n)
        {
            const void *const pv = p;
            std::clog << "deallocate " << n << " @" << pv;
            try {
                traits::deallocate(*this, p, n);
            } catch (...) {
                std::clog << " FAILED\n";
                throw;
            }
            std::clog << '\n';
        }

        template <typename... Args>
        requires std::constructible_from<value_type, Args...>
        void construct(pointer p, Args&&... args)
        {
            const void *const pv = p;
            std::clog << "construct @" << pv;
            try {
                traits::construct(*this, p, std::forward<Args>(args)...);
            } catch (...) {
                std::clog << " FAILED\n";
                throw;
            }
            std::clog << '\n';
        }

        void destroy(pointer p)
        {
            const void *const pv = p;
            std::clog << "destroy @" << pv;
            try {
                traits::destroy(*this, p);
            } catch (...) {
                std::clog << " FAILED\n";
                throw;
            }
            std::clog << '\n';
        }
    };


    // Verifying allocator.
    // Diagnoses these common problems:
    //  - mismatched construction/destruction
    //  - attempts to operate on memory from other allocators.

    // N.B. contains no locking, as intended use in unit-test is
    // expected to be single-threaded.  If a thread-safe version
    // really is needed, write another wrapper for that!

    template<typename Base>
    requires requires { typename std::allocator_traits<Base>; }
    class checked : public Base
    {
    public:
        using traits = std::allocator_traits<Base>;
        using value_type = traits::value_type;
        using pointer = traits::pointer;

        template<class T>
        struct rebind { using other = checked<typename traits::rebind_alloc<T>>; };

#if __cplusplus < 2026'01L
        // prior to C++26, we could inherit incorrect type
        // (LWG issue 3170; https://wg21.link/P2868R1)
        using is_always_equal = std::false_type;
#endif

    private:
        enum class state : unsigned char { initial, alive, dead };

        // states of all allocated values
        std::map<pointer, std::vector<state>, std::greater<>> population = {};

    public:
        using Base::Base;

        // Move-only class - see shared_copyable below if copying is required.
        checked(const checked&) = delete;
        auto& operator=(const checked&) = delete;
        checked(checked&&) = default;
        checked& operator=(checked&&) = default;

        ~checked() noexcept
        {
            try {
                assert_empty();
            } catch (std::logic_error& e) {
                // We can't throw in a destructor, so print a message instead
                std::cerr << e.what() << '\n';
            }
        }

        pointer allocate(std::size_t n)
        {
            auto p = traits::allocate(*this, n);
            population.try_emplace(p, n, state::initial);
            return p;
        }

        void deallocate(pointer p, std::size_t n)
        {
            auto it = population.find(p);
            if (it == population.end()) [[unlikely]] {
                logic_error("deallocate without allocate");
            }
            if (std::ranges::contains(it->second, state::alive)) [[unlikely]] {
                logic_error("deallocate live objects");
            }
            if (n != it->second.size()) [[unlikely]] {
                logic_error(std::format("deallocate {} but {} allocated",
                                        n, it->second.size()));
            }
            traits::deallocate(*this, p, n);
            population.erase(it);
        }

        template<typename... Args>
        requires std::constructible_from<value_type, Args...>
        void construct(pointer p, Args&&... args)
        {
            auto& p_state = get_state(p);
            if (p_state == state::alive) [[unlikely]] {
                logic_error("construct already-constructed object");
            }
            traits::construct(*this, p, std::forward<Args>(args)...);
            // it's alive iff the constructor returns successfully
            p_state = state::alive;
        }

        void destroy(pointer p)
        {
            switch (std::exchange(get_state(p), state::dead)) {
            case state::initial:
                logic_error("destruct unconstructed object");

            case state::dead:
                logic_error("destruct already-destructed object");

            [[likely]]
            case state::alive:
                break;
            }
            traits::destroy(*this, p);
        }

        void assert_empty() const {
            if (population.empty()) [[likely]] {
                return;
            }
            // Failed - gather more information
            static auto const count_living = [](auto const& pair) {
                return std::ranges::count(pair.second, state::alive);
            };
            auto counts = population | std::views::transform(count_living);
            logic_error(std::format("destructing with {} block(s) still containing {} live object(s)",
                                    population.size(), std::ranges::fold_left(counts, 0uz, std::plus<> {})));
        }

    private:
        auto& get_state(pointer p) {
            auto it = population.lower_bound(p);
            if (it == population.end()) [[unlikely]] {
                logic_error("construct/destruct unallocated object");
            }
            auto second = it->first + it->second.size();
            if (std::greater {}(p, second)) [[unlikely]] {
                logic_error("construct/destruct unallocated object");
            }
            return it->second[p - it->first];
        }

        // A single point of tracing can be useful as a debugging breakpoint
        [[noreturn]] void logic_error(auto&& message) const {
            throw std::logic_error(message);
        }
    };

    // An allocator wrapper whose copies all share an instance of the
    // underlying allocator.  This can be needed for implementations
    // that assume all allocators are copyable.
    template<typename Underlying>
    requires requires { typename std::allocator_traits<Underlying>; }
    class shared_copyable
    {
        std::shared_ptr<Underlying> alloc;

    public:
        using traits = std::allocator_traits<Underlying>;
        using value_type = traits::value_type;
        using pointer = traits::pointer;
        using const_pointer = traits::const_pointer;
        using void_pointer = traits::void_pointer;
        using const_void_pointer = traits::const_void_pointer;
        using difference_type = traits::difference_type;
        using size_type = traits::size_type;
        using propagate_on_container_copy_assignment = traits::propagate_on_container_copy_assignment;
        using propagate_on_container_move_assignment = traits::propagate_on_container_move_assignment;
        using propagate_on_container_swap = traits::propagate_on_container_swap;
        using is_always_equal = traits::is_always_equal;

        template<class T>
        struct rebind { using other = shared_copyable<typename traits::rebind_alloc<T>>; };

        template<typename... Args>
        explicit shared_copyable(Args... args)
            : alloc {std::make_shared<Underlying>(std::forward<Args>(args)...)}
        {}

        pointer allocate(std::size_t n)
        {
            return alloc->allocate(n);
        }

        void deallocate(pointer p, std::size_t n)
        {
            alloc->deallocate(p, n);
        }

        template <typename... Args>
        requires std::constructible_from<value_type, Args...>
        void construct(pointer p, Args&&... args)
        {
            alloc->construct(p, args...);
        }

        void destroy(pointer p)
        {
            alloc->destroy(p);
        }
    };

    // This wrapper is needed for code (such as some implementations
    // of standard library) which assumes that allocator traits'
    // destroy() and deallocate() never throw, even though these
    // functions are not required to be noexcept.
    template<typename Base>
    requires requires { typename std::allocator_traits<Base>; }
    struct no_delete_exceptions : Base
    {
        using traits = std::allocator_traits<Base>;

        template<class T>
        struct rebind { using other = no_delete_exceptions<typename traits::rebind_alloc<T>>; };

        using Base::Base;

        void deallocate(traits::pointer p, std::size_t n) noexcept
        {
            try {
                traits::deallocate(*this, p, n);
            } catch (std::exception& e) {
                std::cerr << "deallocate error: " << e.what() << '\n';
            }
        }

        void destroy(traits::pointer p) noexcept
        {
            try {
                traits::destroy(*this, p);
            } catch (std::exception& e) {
                std::cerr << "destroy error: " << e.what() << '\n';
            }
        }
    };

} // namespace alloc

#endif

As well as using these objects to test the fixed-size dynamic array linked above, I also made some unit tests:

#include <gtest/gtest.h>

#include <string>

using checked = alloc::checked<std::allocator<std::string>>;

TEST(Alloc, DoubleDeallocate)
{
    checked a;
    auto p = a.allocate(1);
    EXPECT_THROW(a.assert_empty(), std::logic_error);

    EXPECT_NO_THROW(a.deallocate(p, 1));
    EXPECT_THROW(a.deallocate(p, 1), std::logic_error);

    EXPECT_NO_THROW(a.assert_empty());
}

TEST(Alloc, DeallocateWrongSize)
{
    checked a;
    auto p = a.allocate(1);
    EXPECT_THROW(a.deallocate(p, 2), std::logic_error);

    // clean up
    EXPECT_NO_THROW(a.deallocate(p, 1));
    EXPECT_NO_THROW(a.assert_empty());
}

TEST(Alloc, DoubleConstruct)
{
    checked a;
    auto p = a.allocate(1);
    EXPECT_NO_THROW(a.construct(p, ""));
    EXPECT_THROW(a.construct(p, ""), std::logic_error);

    // deallocate with live object
    EXPECT_THROW(a.deallocate(p, 1), std::logic_error);

    // clean up
    EXPECT_NO_THROW(a.destroy(p));
    EXPECT_NO_THROW(a.deallocate(p, 1));
    EXPECT_NO_THROW(a.assert_empty());
}

TEST(Alloc, ConstructAfterDeallocate)
{
    checked a;
    auto p = a.allocate(1);
    a.deallocate(p, 1);
    EXPECT_NO_THROW(a.assert_empty());
    EXPECT_THROW(a.construct(p, ""), std::logic_error);

    // clean up
    EXPECT_NO_THROW(a.assert_empty());
}

TEST(Alloc, DestroyWithoutConstruct)
{
    checked a;
    auto p = a.allocate(1);
    EXPECT_THROW(a.destroy(p), std::logic_error);

    // clean up
    EXPECT_NO_THROW(a.deallocate(p, 1));
    EXPECT_NO_THROW(a.assert_empty());
}

TEST(Alloc, DoubleDestroy)
{
    checked a;
    auto p = a.allocate(1);
    EXPECT_NO_THROW(a.construct(p, ""));
    EXPECT_NO_THROW(a.destroy(p));
    EXPECT_THROW(a.destroy(p), std::logic_error);

    // clean up
    EXPECT_NO_THROW(a.deallocate(p, 1));
    EXPECT_NO_THROW(a.assert_empty());
}
```

Answer 1

Missing thread-safety

The default allocator is thread-safe, and custom allocators might also be. So for your allocator adapters to not destroy the thread-safety, you need to make sure you handle that correctly.

• logged: while this doesn't break anything when used from multiple threads, it might cause the log messages from being mixed together. You could add a mutex to prevent that, but I suggest just making sure you do everything with a single use of <<, as then it is likely that the underlying stream will handle it as an atomic operation. So for example:

  std::clog << std::format("allocate {} = {}\n", n, pv);
  

  Also consider that other things might output to std::clog as well, not just your allocator adapters.
• checked: use a mutex to guard population.
• shared_copyable: despite std::shared_ptr being somewhat thread-safe, it's not safe to have two threads to access the exact same std::shared_ptr object at the same time. So consider whether you want to allow concurrent access to the same shared_copyable object.
• no_delete_exceptions: same issue as logged.

Check the return value of try_emplace()

In checked, consider checking the return value of try_emplace(). This could catch misbehaving allocators that return the same point for different allocations with overlapping lifetimes, but it could also still point to errors in the caller. Consider someone making two std::pmr::monotic_buffer_resource objects but accidentally giving them a pointer to the same buffer.

Note that this only catches errors if two allocations return exactly the same pointer. What if they have different pointers but the memory ranges overlap?

Interaction with placement-new/delete

The checked allocator also tracks construction and destruction using construct() and destroy(), but it might be legal to use bare placement-new instead of construct(), but still call destroy() afterwards. So your checker could return false positives, although for everyone's sanity of mind, it's of course much better to enforce that the same way is used to construct as to destroy.

Missing std::forward()

Not all your construct() functions use std::forward() to forward args. That brings me to:

Missing unit tests

There are lots of unit tests that need to be added. You should not only test for your allocator adapters performing their special functionality, but also that everything is passed to the underlying allocators correctly.

[[nodiscard]], constexpr and noexcept

C++20 made a lot of allocator operations constexpr, and added [[nodiscard]] to the return value of allocate().

While I don't think any of the STL's allocators have anything that is noexcept anymore, consider that someone might implement their own non-throwing allocator (for example, for use in real-time code). You could add noexcept(noexcept(…)) clauses to the members of logged and shared_copyable, but this won't work for checked as its use of a std::map means it cannot be noexcept.