Towards meaningful fancy pointers

For example, this grayed paragraph should be skipped on your first reading.

I propose a taxonomy of fancy pointer types into five not-mutually-exclusive categories, along the axes of storage representation, addressable range, and carried metadata.

• (A) Fancy pointers with a different bit-level representation than native pointers: offset pointers. This is explicitly supported today. Many types (std::vector) work already; some non-container types (std::shared_ptr) do not work.
• (B) Fancy pointers addressing a narrower range of memory (a Small Data Area): near pointers. This is plausible. Some containers (std::vector) implicitly work already; some (std::list) work only in certain runtime situations.
• (C) Fancy pointers addressing a wider range of memory: far pointers. This turns out to be impossible in C++ because every object must have a native address.
• (D) Augmented fancy pointers whose metadata affects arithmetic: fat pointers. This is plausible but expensive, and not worth the implementation effort for vendors.
• (E) Augmented fancy pointers whose metadata affects only deallocation: segmented pointers. This is plausible. Some containers (std::vector) work already; some (std::list) require only trivial modifications; some (std::shared_ptr) require major fixes.

I propose two self-consistent future directions for fancy pointers. In one direction, we keep the status quo that no scenario except (A) is supported, and perhaps move toward separation of the pointer storage type from the allocation mechanism. In my preferred direction, we require that vendors support scenarios (B) and (E) as well as (A).

In the sections that follow, I will lay out the case for these recommendations.

Sometimes we say that an object "has a value," or refer to an object's state as "its value." I will try not to do either of those things in this paper.

In C++, a handle is often represented in code by (the value of) a C++ native pointer. A handle does nothing but identify an object; therefore a handle can be copied; therefore a handle does not "own" its referent.

This definition of type is problematic in C++ because we are used to strong static typing, where a value really does "have a type." We want to say that the value 4 is representable in both digit and evendigit — that digit(4) and evendigit(4) represent "the same value," even though they have different C++ types and may not even be comparable via operator==. Therefore, C++ introduces the idea of casting.

For example, casting the value 3.00 from double to int and back will preserve its value, because the value "3" is representable in both types. Casting the value 3.14 from double to int and back will preserve part of its value but throw away some of it. In C++, "casting" of the kind we're talking about is usually represented via static_cast.

For example, double is more or less an augmented type with respect to int. Casting the value 3.14 from double to int will preserve the int part of its value but throw away the fractional part. (When considering double as an augmented int, the fractional part is the metadata.) Casting from int back to the augmented type double is possible, but will reconstitute the metadata as ".00" instead of the correct ".14".

Most well-known product types, such as std::tuple<U,V>, are not really augmented types because there is no "natural" mapping from std::tuple<U,V> to U. In C++ terms, static_cast'ing from std::tuple<U,V> to U will not compile. But the following Augmented<U, Meta> is definitely an augmented type with respect to U:

    template<class U, class Meta>
    struct Augmented {
        U u_;
        Meta meta_;
        Augmented(U u, Meta m) : u_(u), meta_(m) {}
        operator U() const { return u_; }
    };

In C++, a derived type is often an augmented type with respect to its public base type(s). Casting from derived to base results in slicing away of the "non-base parts" of the instance, but preserves the "base parts." If casting from derived to base is forbidden (for example by deleting the base type's copy constructor), then the derived type is not an augmented type with respect to the base type.

An example of significant storage representation is boost::interprocess::offset_ptr<T>, which has the same range of values as the native pointer type T* but a different bit-level storage representation. Since (T*)(&x) and offset_ptr<T>(&x) are the same value, we should expect that they can be interconverted using static_cast. In fact, under Boost 1.64, static_cast<offset_ptr<T>>((T*){}) is accepted but static_cast<int*>(offset_ptr<T>{}) is ill-formed. I believe this is a defect in the current implementation of boost::interprocess::offset_ptr.

Instances of types derived from std::pmr::memory_resource are memory resources. Instances of boost::interprocess::segment_manager_base are also memory resources. But another well-known memory resource is just "the heap." "The heap" doesn't exist as a concrete C++ object, but it still affords allocation via operator new and deallocation via operator delete. Therefore I say that "the heap" is a memory resource as well.

In C++ there is actually a whole family of concepts Allocator<T> each associated with allocating and deallocating C++ objects of type T. However, it is implicitly required that I can cast an object of type some_allocator<T> to type some_allocator<U>. Casting alters type without altering value; that is, casting a handle in this way produces a new handle which uniquely identifies the same memory resource.

This definition of rebinding is compatible with "slab allocator"-style memory resources, where SlabAllocator<int32_t>::allocate and SlabAllocator<int64_t>::allocate allocate chunks out of different, non-overlapping slabs of memory. A single memory resource then consists of a single complete set of slabs. The important thing is that we must be able to take a handle to this memory resource and cast it around without affecting its value (that is, the identity of the memory resource to which it refers).

    SlabResource mr1;
    auto a32 = SlabAllocator<int32_t>(&mr1);  // get a handle to the memory resource
    auto b64 = SlabAllocator<int64_t>(a32);  // cast that handle to a new C++ type
    auto c32 = SlabAllocator<int32_t>(b64);  // cast the handle back to the original type
    // At this point, a32 and c32 must both identify memory resource "mr1".
    // c32 is NOT ALLOWED to identify a different memory resource "mr2".
    // c32 is NOT ALLOWED to identify no memory resource (e.g. to have become "null" or otherwise unusable).
    // a32 and c32, being the same value in the same C++ type, must be truly interchangeable.

We can create an allocator type which has many possible values: for example, std::pmr::polymorphic_allocator. We can also create an allocator type whose set of possible values has only one member: for example, std::allocator is an allocator type whose only possible value is "the identity of 'the heap'." Since the set of possible values has size 1, an instance of the type contains log(1) = 0 bits of information and thus std::is_empty_v<std::allocator<T>>. Casting an std::allocator<T> to std::allocator<U> preserves its value, in that the value resulting from the cast continues to identify "the heap."

Fancy pointer types are described in [allocator.requirements]/5 as types modeling both NullablePointer and RandomAccessIterator; that is, in today's C++, a fancy pointer type must provide pointer arithmetic. I will argue that fancy pointer types have no philosophical need to provide pointer arithmetic.

In the native pointer type int*, we can construct non-dereferenceable values in at least the following ways:

    int arr[10];
    int *p1 = nullptr;   // the null pointer is never dereferenceable
    int *p2 = arr + 10;  // a "one-past-the-end" pointer is not dereferenceable

There are also ways to have an object p of type int* where the behavior of *p is undefined, such as

    int *p3 = new int; delete p3;  // a deallocated pointer is not dereferenceable
    int *p4;                       // an uninitialized pointer is not dereferenceable

but these examples are not interesting in the context of this paper. Philosophically it is arguable that these examples treat p3 and p4 as stateful objects, and that the names p3 and p4 do not identify pointer values at all. In this paper I am concerned with pointer values like p1 and p2; I do not consider p3 and p4 to be relevant.

Many dereferenceable pointers will not be deallocatable. (For example, any pointer identifying a non-allocated object will not be deallocatable by any allocator. Also, a pointer allocated by memory resource A is unlikely to be deallocatable by memory resource B.) Some deallocatable pointers will not be dereferenceable. (For example, the native pointer returned from malloc(0) on some implementations is deallocatable with respect to malloc()/free() but not dereferenceable.)

This means that the storage representation of a boost::interprocess::offset_ptr object depends on the object's own memory address. offset_ptr objects are not trivially copyable. Yet, at the Platonic level, offset_ptr can be said to have the same set of possible values as a native pointer type.

The benefit of boost::interprocess::offset_ptr is that if a memory region is mapped into the address space of two different processes, then every offset_ptr residing in the mapped region will identify the same object no matter which process is asking — as long as the identified object also resides in the mapped region.

For example, shared_ptr requires allocation (and supports allocation with an allocator via allocate_shared) but shared_ptr is not representation-aware. Vice versa, boost::interprocess::allocator is representation-aware (it contains a non-static data member of fancy pointer type) but not allocator-aware (the fancy pointer is not obtained via allocator_traits<A>::pointer for any type A, and does not point to an allocation).

It is a shame that the standard representation-aware types inherit their storage type from allocator_traits<A>::pointer instead of from a separate template parameter P. I don't see how to fix this without breaking ABI and requiring a lot of work from vendors. A small step in this direction would be to add an allocator adaptor std::storage_allocator_adaptor<P,A> identical to A except that its pointer typedef is pointer_traits<P>::rebind<A::value_type>. This would ease using offset_ptr with representation-aware containers; but not help with types that were not already representation-aware, such as shared_ptr.

On a 32-bit microcontroller, the programmer might define a frequently used list container like this:

    #include <list>
    #include <memory_resource>

    // Reserve representation 0x0000 for "null".
    std::pmr::monotonic_buffer_resource g_smallData((void*)0x0001, 32767, std::pmr::null_memory_resource());

    int main() {
        std::pmr::list<int32_t> widgets(&g_smallData);

        widgets.push_back(1);
    }

Any allocations made by widgets always reside within the "small data area," addresses 0x00000001 through 0x00007FFF. This means that in principle, each pointer should consume only 16 bits of memory footprint. Since each list node contains two pointers, this would be a savings of 4 bytes per node, allowing us to fit twice as many list elements into the small data area as we could naively fit.

The Standard Library doesn't provide a fancy-pointer version of memory_resource, but we can easily roll our own. We'd create a near fancy pointer type like this:

    template<class T>
    class NearPtr {
        int16_t ptr_ = 0;
    public:
        NearPtr() = default;
        NearPtr(std::nullptr_t) {}
        explicit NearPtr(T *p) : ptr_((int16_t)(intptr_t)p) {}
        T& operator*() const {
            return *(T*)(intptr_t)ptr_;
        }

        template<class U>
        explicit NearPtr(const NearPtr<U>& rhs) : ptr_(rhs.ptr_) {}
    };

    // Reserve representation 0x0000 for "null".
    std::pmr::monotonic_buffer_resource g_smallData((void*)0x0001, 32767, std::pmr::null_memory_resource());

    template<class T>
    struct NearAllocator {
        using value_type = T;
        using pointer = NearPtr<T>;
        using void_pointer = NearPtr<void>;

        pointer allocate(size_t n) {
            void *vp = g_smallData.allocate(n * sizeof(T), alignof(T));
            return static_cast<pointer>(static_cast<void_pointer>(vp));
        }
        void deallocate(pointer p, size_t n) {
            g_smallData.deallocate(static_cast<void*>(static_cast<T*>(p)), n * sizeof(T), alignof(T));
        }
    };

    int main() {
        std::list<int32_t, NearAllocator<int32_t>> widgets;

        widgets.push_back(1);
    }

A historical example is the 80286, where 16-bit native pointers could identify only the memory addresses between 0x0000 and 0xFFFF, but the computer itself had additional memory ranging from address 0x1'0000 to address 0xF'FFFF, and some models had a "high memory area" between 0x10'0000 and 0x10'FFEF. These additional addresses were not addressable with native pointers such as int*. Compilers of the day provided additional built-in types such as far int*, where sizeof(far int*) > sizeof(int*).

A possible future example is objects residing in some location which is not memory-mapped into the current process's virtual address space. Today this is unlikely to be a real problem for 64-bit address spaces — we just take anything we care about (including the OS kernel, and also GPU memory if I understand correctly) and map it into the current process's address space. It might be a problem looking forward into the future of enormous (>18 exabytes?) non-volatile storage, or more likely looking downward into the domain of 32-bit and 16-bit microcontrollers with smaller main memories.

Every fancy pointer type must provide an operator* that returns a reference to an object. That is, we must have a function definition along these lines:

    struct FancyPtrInt {
        int& FancyPtrInt::operator*() const {
            // some magic goes here
        }
        // ...
    };

The expression *fancyp returns a reference to its identified object as type int&. So its identified object must be addressable by a native pointer value — namely, std::addressof(*fancyp). Therefore, this attempt to use fancy pointers to address objects outside main memory has failed.

For example, here is one possible "fat" fancy pointer type.

    template<class T>
    class FatPtr {
        char *base_ = nullptr;
        int cur_ = 0;
        int max_ = 1;
    public:
        FatPtr() = default;
        FatPtr(std::nullptr_t) {}
        explicit FatPtr(T *p, int n) : base_((char*)p), max_(n * sizeof (T)) {}

        template<class U>
        explicit FatPtr(const FatPtr<U>& rhs) :
            base_(rhs.base_), cur_(rhs.cur_), max_(rhs.max_) {
            if (cur_ % sizeof(T) != 0) throw "misaligned";
        }

        T& operator*() const {
            if (base_ == nullptr) {
                throw "null";
            } else if (cur_ < 0 || max_ <= cur_) {
                throw "out of bounds";
            } else if (cur_ % sizeof(T) != 0) {
                throw "misaligned";
            } else {
                return *(T*)(base_ + cur_);
            }
        }

        auto& operator++() {
            if (base_ == nullptr) throw "null";
            if (max_ <= cur_ + sizeof(T)) throw "out of bounds";
            cur_ += sizeof(T);
            return *this;
        }

        // ...
    };

    template<class T>
    struct FatAllocator {
        using value_type = T;
        using pointer = FatPtr<T>;
        using void_pointer = FatPtr<void>;

        pointer allocate(size_t n) {
            T *p = std::allocator<T>().allocate(n);
            return pointer(p, n);
        }
        void deallocate(pointer p, size_t n) {
            if (p.cur_ != 0) throw "deallocating non-allocated pointer";
            std::allocator<T>().deallocate(p, n);
        }
    };

This fat-pointer type plays well with list-like containers because its range of values includes all of main memory.

In order to get the benefit of type-checking, the container must dereference only FatPtr values losslessly derived from the originally allocated FatPtr, which again implies doing pointer arithmetic only on FatPtr. This will generally have a performance cost, especially in debug mode. Worse, if we use fat pointers only for safety-checking, there will be no benefit to counter the performance cost, unless the standard container itself has bugs.

The fat-pointer scenario is the only scenario in this paper where it makes sense to do pointer arithmetic on fancy pointers. In every other case, it is equivalent — and generally more efficient, especially in debug mode — to do pointer arithmetic only on native pointers.

For example, here is one possible "segmented" fancy pointer type. A full implementation is available on my GitHub under the name scratch::pmr::segmented_resource.

    class Segment;

    template<class T>
    class SegmentedPtr {
        T *ptr_ = nullptr;
        Segment *seg_ = nullptr;
    public:
        SegmentedPtr() = default;
        SegmentedPtr(std::nullptr_t) {}
        explicit SegmentedPtr(T *p, Segment *seg) : ptr_(p), seg_(seg) {}

        template<class U>
        explicit SegmentedPtr(const SegmentedPtr<U>& rhs) :
            ptr_(rhs.ptr_), seg_(rhs.seg_) {}

        auto segment() const { return seg_; }
        T& operator*() const { return *ptr_; }
        auto& operator++() { ++ptr_; return *this; }

        // ...

        static auto pointer_to(T& r) { return SegmentedPtr(&r, nullptr); }
    };

    class Segment {
        char buffer[10000];
        int index = 0;
        int freed = 0;
    public:
        bool can_allocate(size_t bytes) {
            return (sizeof buffer - index) >= bytes;
        }
        auto allocate(size_t bytes) {
            index += bytes;
            void *p = &buffer[index - bytes];
            return SegmentedPtr<void>(p, this);
        }
        void deallocate(void *, size_t bytes) {
            freed += bytes;
            if (freed == index) {
                index = freed = 0;
            }
        }
    };

    class SegmentedResource {
        std::list<Segment> m_segments;
    public:
        SegmentedPtr<void> allocate(size_t bytes, size_t align) {
            assert(align <= alignof(std::max_align_t));
            bytes += -bytes % alignof(std::max_align_t);
            assert(bytes <= 10000);

            for (auto&& seg : m_segments) {
                if (seg.can_allocate(bytes)) {
                    return seg.allocate(bytes);
                }
            }
            return m_segments.emplace_back().allocate(bytes);
        }
        void deallocate(SegmentedPtr<void> p, size_t bytes, size_t) {
            bytes += -bytes % alignof(std::max_align_t);
            p.segment()->deallocate(static_cast<void*>(p), bytes);
        }
    };

    template<class T>
    class SegmentedAllocator {
        SegmentedResource *mr_;
    public:
        using value_type = T;
        using pointer = SegmentedPtr<T>;

        SegmentedAllocator(SegmentedResource *mr): mr_(mr) {}

        pointer allocate(size_t n) {
            return pointer(mr_->allocate(n * sizeof(T), alignof(T)));
        }
        void deallocate(pointer p, size_t n) {
            return mr_->deallocate(p, n * sizeof(T), alignof(T));
        }
    };

    int main() {
        SegmentedResource mr;
        std::list<int, SegmentedAllocator<int>> widgets(&mr);

        widgets.push_back(1);
    }

The important line is this one, in SegmentedResource::deallocate:

            p.segment()->deallocate(static_cast<void*>(p), bytes);

This line returns p's memory to the segment from which it was originally allocated. If the identity of that segment were not part of p's metadata, this code would not work. If p's metadata had been sliced away prior to deallocation (that is, if the pointer passed to the deallocation mechanism were not losslessly derived from the original allocation), this code would not work.

If the programmer cannot rely on the container to deallocate a pointer losslessly derived from the original allocation, then the programmer cannot use this kind of segmented memory resource.

For example, libc++'s promise(allocator_arg, _Alloc) looks effectively like this:

    template<class _Rp, class _Alloc>
    class __assoc_state_alloc : public __assoc_state<_Rp>
    {
        _Alloc __alloc_;
        void __on_zero_shared() noexcept override {
            using _Al = typename __allocator_traits_rebind<_Alloc, __assoc_state_alloc>::type;
            using _ATraits = allocator_traits<_Al>;
            using _PTraits = pointer_traits<typename _ATraits::pointer>;
            _Al __a(__alloc_);
            this->~__assoc_state_alloc();
            __a.deallocate(std::pointer_traits<_P>::pointer_to(*this), 1);
        }
 public:
        explicit __assoc_state_alloc(const _Alloc& __a)
            : __alloc_(__a) {}
    };

    template<class _Rp>
    template<class _Alloc>
    promise<_Rp>::promise(allocator_arg_t, const _Alloc& __a0)
    {
        using _State = __assoc_state_alloc<_Rp, _Alloc>;
        using _A2 = typename __allocator_traits_rebind<_Alloc, _State>::type;
        using _D2 = __allocator_destructor<_A2>;
        _A2 __a(__a0);
        unique_ptr<_State, _D2> __hold(__a.allocate(1), _D2(__a, 1));
        ::new(static_cast<void*>(std::addressof(*__hold.get()))) _State(__a0);
        __state_ = std::addressof(*__hold.release());
    }

The argument to __a.deallocate is the direct result of pointer_to; that is, it will fail to correctly reconstitute the metadata that was lost in the conversion from fancy pointer __hold.get() to native pointer this. To make this code work with segmented pointers, the __assoc_state_alloc struct must store a copy of the originally allocated pointer.

The reason we must use std::pointer_traits<FancyPtrT>::pointer_to(T& r) rather than the simpler static_cast<FancyPtrT>(T*) is that there may not be any natural mapping from T* values onto FancyPtrT values. In scenario (B), some values of T* do not have an image in FancyPtrT. In scenario (E), the operation requires us to invent the metadata part of a FancyPtrT value. In both cases a mapping is possible, but it is not a natural mapping, and thus must not be represented in C++ by static_cast.

It is a shame that the signature of pointer_to takes T&, thus requiring that the input native pointer be dereferenceable. This means there is no generic way to get the fancy-pointer value corresponding to a one-past-the-end pointer; and the generic way to get a fancy null pointer is FancyPtrT{} rather than pointer_to(nullptr). This does not seem to be a problem for containers in practice.

If scenario (A), offset pointers, is the only scenario in play, then static_cast<FancyPtrT>(T*) is perhaps an appropriate way to get the storage representation of a native pointer. Scenario (B), near pointers, is also relevant to storage representation.

Today, container implementations say std::addressof(*fancyPtrT) instead of static_cast<T*>(fancyPtrT). The latter is more philosophically appropriate. The former also has the potential problem that it can be used only for dereferenceable pointer values. std::addressof(*fancyPtrT) cannot safely be used when fancyPtrT == nullptr. This does not seem to be a problem for containers in practice.

Also, std::addressof(*fancyPtrT) cannot safely be used when fancyPtrT represents a "one-past-the-end" fancy pointer value; but such values arise only via fancy pointer arithmetic.

In my preferred solution (support A, B, and E but not D), every STL container needs to follow these rules:

1. Any dereferenceable pointer stored "within" the container must be stored as a fancy pointer. (Required by A; wanted by B.)
2. A dereferenceable pointer stored "outside" the container, such as in an iterator, may be stored as a fancy pointer or as a native pointer. (Relevant to A.)
3. Whenever you get a pointer from allocate(), hang onto it. You will never be able to reconstruct its metadata if you lose it. (Required by E.)
4. Assume that metadata is preserved via the fancy pointer type's special member functions, and via casting from one fancy pointer type to a rebound version of that type (e.g. static_cast<FancyPtrT>(fancyPtrU)). (This proposes a resolution to LWG 2260.) Do not assume that metadata is preserved via any other operations. (Required by E.)
5. Assume that static_cast<T*>(fancyPtrT) is a correct slicing expression. Prefer to avoid std::addressof(*fancyPtrT), which isn't going to work if fancyPtrT is not a dereferenceable value. (Required by A, B, and E.)
6. Assume that std::pointer_traits<FancyPtrT>::pointer_to(t) returns a dereferenceable pointer, but not a deallocatable one. Do not assume that static_cast<FancyPtrT>(std::addressof(t)) compiles; FancyPtrT might not have a one-argument constructor. (Required by E.)
7. Assume that the fancy pointer type models NullablePointer. (Construction from and comparison to nullptr ought to be supported.)
8. Do not assume that the fancy pointer type models RandomAccessIterator. For example, do not rely on operator++, operator[], or operator<. Slice to T* before attempting these operations. (Improves the performance and usability of A, B, and E. Precludes D.)

Appendix. Representation-awareness of container and iterator types, in some present-day library implementations.

The following table shows, for various container classes C across various common library implementations, the compatibility of C with boost::interprocess::offset_ptr. This demonstrates the current state of my Scenario A (offset pointers) across these implementations.

The "X" entries for basic_string indicate that the libraries require trivial constructibility, which offset_ptr does not have; but if the library vendors patched this one bug, then the libraries would be able to support offset_ptr with no further patches (as far as I know).

The following table shows, for various container classes C across various common library implementations, the compatibility of C::iterator with boost::interprocess::offset_ptr. This demonstrates the current state of my Scenario A (offset pointers) across these implementations.

GNU forward_list, list, map, and unordered_map iterators each hold a raw pointer to an allocated list node. MSVC deque's iterator holds a raw pointer to the deque itself, and an integer offset.

Appendix. References and further reading.

Boost.Interprocess offset_ptr documentation. https://www.boost.org/doc/libs/1_65_0/doc/html/interprocess/offset_ptr.html

Lance Diduck. N2486 "Alternative Allocators and Standard Containers." December 2007. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2486.pdf

Nevin Liber. N3884 "Contiguous Iterators: A Refinement of Random-Access Iterators." January 2014. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3884.pdf

Doug Judd. "Why pointer_traits was introduced in C++11." September 2015. http://blog.nuggetwheat.org/index.php/2015/09/01/why-pointer_traits-was-introduced-in-c11/

Mike Spertus. LWG 1521 "Requirements on internal pointer representations in containers." Opened 2010-10-16, last modified 2016-02-10. https://cplusplus.github.io/LWG/issue1521

Thomas Köppe. "A visitor's guide to C++ allocators." September 2016. https://rawgit.com/google/cxx-std-draft/allocator-paper/allocator_user_guide.html

Arthur O'Dwyer. "pointer-traits.md." August 2017. https://github.com/Quuxplusone/from-scratch/blob/master/include/scratch/bits/traits-classes/pointer-traits.md

Jonathan Wakely. LWG 2260 "Missing requirement for Allocator::pointer." Opened 2013-05-14, last modified 2017-07-30. https://cplusplus.github.io/LWG/issue2260

Acknowledgments.

Thanks to Alfredo Correa for identifying many confusing passages in drafts of this paper.