PXXXXR0
Laundering for Arrays of Unknown Bound

Draft Proposal,

This version:
http://example.com/url-this-spec-will-live-at
Author:
Jason Cobb <jason.e.cobb@gmail.com>
Project:
ISO/IEC JTC1/SC22/WG21 14882: Programming Language — C++

Abstract

This paper would ensure that allocators implemented by allocating byte arrays can be implemented, by permitting the template argument to std::launder to be an array of unknown bound.

1. Introduction

[P0593] introduced the ability for objects to be implicitly created under certain circumstances. In doing so, it added the requirement to allocators that, when allocate(n) is called, they create a T[n], without additionally creating any array elements. [N4910], in [allocator.requirements.general], provides the following as an example of a way to implement this: std::launder(reinterpret_cast<T*>(new (p) std::byte[n * sizeof(T)])).

This example is incorrect.

After the lifetime of the byte[] is begun, objects can be implicitly created ([intro.object]/13). There are two possible cases here, both of which result in UB.

First, if T is not an implicit-lifetime type, then only the array object can be created (since all array types are implicit-lifetime, even if the element type is not), and it must be created in order to satisfy the allocator requirements. This is the goal of the allocator, but in an attempt to obtain a pointer to the first element, it passes the pointer from new to std::launder.

std::launder has the following preconditions:

p represents the address A of a byte in memory. An object X that is within its lifetime and whose type is similar to T is located at the address A. All bytes of storage that would be reachable through the result are reachable through p (see below).

The result of new does not point to a T, and it cannot have created T, since it is not an implicit-lifetime type. The example therefore violates the preconditions of std::launder and has undefined behavior.

If T is an implicit-lifetime type, then implicit object creation must still create the array object in order to satisfy the allocator requirements, but it could also create a T object at the first byte in order to satisfy the preconditions of std::launder. However, this would violate the allocator requirements (since it creates an array element object, violating the requirements on allocate), yielding UB when used as a standard allocator per [res.on.functions]/2.3. No set of implicitly created objects would give the program defined behavior, so the program has undefined behavior ([intro.object]/10).

2. Problem

The fact that an example is incorrect is not a problem, since it can be fixed. The problem is that there is no proper way to do what the example hopes to accomplish. To the author’s knowledge, there is no reasonable standard way to allocate a T[n] for a runtime value of n, then get a pointer to storage for the first element, which is what is required to implement allocate.

This problem applies to any allocator which returns memory from an allocated std::byte[], unsigned char[], or char[].

Allocators based on operator new, operator new[], malloc, aligned_alloc, and calloc can be implemented in such a way as to have defined behavior. All of those functions return a pointer to a suitable created object ([intro.object]/13 and [c.malloc]/4), so a conforming allocate can be implemented as

T* allocate(size_type n) {
    return *reinterpret_cast<T(*)[]>(::operator new(sizeof(T) * n));
}

In this implementation, ::operator new returns a pointer to a suitable created T[], then a pointer to storage for its first element is achieved by dereferencing the T(*)[] and relying on array-to-pointer decay to produce the final pointer.

There is no equivalent for user-defined functions that create a std::byte[] for allocated objects. The only operations that return pointers to suitable created objects are invoking functions named operator new or operator new[] and invoking the standard functions named above (and realloc, but that’s not helpful here).

In addition to suitable created objects being insufficient, there is no other (reasonable) way to obtain a pointer to a T[] implicitly created in a std::byte[]. std::launder looks promising, but it cannot be used to form a pointer to a T[] because of [res.on.functions]/2.5:

In particular, the effects are undefined in the following cases:

No specific type T[n] can work for std::launder because T[x] and T[y] are not similar if x != y.

However, a non-constant template argument to std::launder can work:

template<typename T, std::size_t Min, std::size_t Max>
auto do_launder_array(void* p, std::size_t n) -> T(*)[] {
    if constexpr (Min == Max) {
        std::abort();
    } else {
        if (n == Min) {
            return std::launder(reinterpret_cast<T(*)[Min]>(p));
        } else {
            return ::do_launder_array<T, Min + 1, Max>(p, n);
        }
    }
}

inline constexpr std::size_t max_launder_array_size = 899;

template<typename T>
auto launder_array(void* p, std::size_t n) -> T(*)[] {
    return ::do_launder_array<T, 1, max_launder_array_size>(p, n);
}

// In some allocator:
T* allocate(size_type n) {
    return *::launder_array<T>(somehow_allocate_byte_array(n), n);
}

This works by determining, at runtime, the type T[n] that the allocated pointer should be laundered to. There are many issues with this solution, however. First, it can only operate for n that are less than some compile-time constant. Second, this requires deeply-nested recursive template instantiations. Finally, this code is unreasonably complex for a simple operation: "get a pointer to a T[] that I know exists", even if the fact that it is known to exist is due to implicit object creation.

3. Proposed Solution

The solution proposed here is to allow laundering pointers to arrays of unknown bound. This allows acquiring a pointer to an implicitly created array, without requiring that any elements have been created.

Since T[n] and T[] are similar, no further changes are needed to be able to satisfy the preconditions of std::launder.

With this change, the following would be a conforming implementation of allocate for an allocator that places objects into std::byte[]s:

T* allocate(size_type n) {
    return *std::launder(reinterpret_cast<T(*)[]>(somehow_allocate_byte_array(n)));
}

4. Proposed Wording

4.1. 17.6.5 Pointer optimization barrier [ptr.launder]

template<class T> [[nodiscard]] constexpr T* launder(T* p) noexcept;
Mandates: !is_function_v<T> && !is_void_v<T> is true.

Preconditions: p represents the address A of a byte in memory. An object X that is within its lifetime and whose type is similar to T is located at the address A. All bytes of storage that would be reachable through the result are reachable through p (see below).

Returns: A value of type T* that points to X.

Remarks:

T may be a type that is an array of unknown bound. An invocation of this function may be used in a core constant expression if and only if the (converted) value of its argument may be used in place of the function invocation. A byte of storage b is reachable through a pointer value that points to an object Y if there is an object Z, pointer-interconvertible with Y, such that b is within the storage occupied by Z, or the immediately-enclosing array object if Z is an array element.

References

Informative References

[N4910]
Thomas Köppe. Working Draft, Standard for Programming Language C++. 2022-03-17. URL: https://wg21.link/N4910
[P0593]
Richard Smith. Implicit creation of objects for low-level object manipulation. 2020-02-14. URL: https://wg21.link/p0593r6