Stack Exchange
C++ fixed size allocator: is this UB?
I'm writing a fixed size allocator. I'm curious what I'm doing is UB.
#include <type_traits>
#include <stdexcept>

template <typename T>
concept DiskAllocable = std::is_same_v<std::remove_cvref_t<T>, T>
&& std::is_trivially_copyable_v<T> && (sizeof(T) % alignof(T) == 0);

template <DiskAllocable T, size_t Count = 1> class AllocatorFixed {
  static_assert(Count > 0, "count should be nonzero");
  static constexpr size_t block_size_ = (sizeof(T) * Count);
  static_assert(block_size_ >= sizeof(T *),
                "block size should be at least pointer size");

  union Chunk {
    T *next_;
    T object_[Count];
  };

  T *pool_ = nullptr;
  size_t pool_size_ = 0;
  Chunk *free_ = nullptr;

public:
  using value_type = T;

  AllocatorFixed(unsigned char *pool_ptr, size_t pool_byte_size) {
    if (!pool_ptr) {
      throw std::invalid_argument("pool ptr is null");
    }
    if (pool_byte_size < block_size_) {
      throw std::invalid_argument("pool byte size is too small");
    }
    pool_ = reinterpret_cast<T *>(pool_ptr);
    pool_size_ = pool_byte_size / block_size_;

    T* chunk_ptr = pool_;
    for (size_t i = 0; i < pool_size_; i++, chunk_ptr += Count) {
      auto chunk = reinterpret_cast<Chunk *>(chunk_ptr);
      chunk->next_ = chunk_ptr + Count;
    }
    free_ = reinterpret_cast<Chunk *>(pool_);
  }

 // ... other details ...

};

I'm using Chunk as a union of actual chunk block and T*, and I'm writing all Chunk.next_ as the pointer value to the next Chunk. I'm worried if this is UB.

What part are you worried about? All your reinterpret_cast look UB but we can't tell without "other details".


casting between Chunk* and T* where Count may not be 1 / 2. writing chunk->next_ as chunk_ptr + Count


I bet you are misssing a lot of construct_at calls.

Don't confuse programming errors (out of contract use, of say std::reinterpret_casts) with UB.  (I sometimes think ppl are to obsessed with the UB word). Seems your allocator in the end will only be able to allocate memory for POD's and will not actually construct objects (I think that's what @GoswinvonBrederlow is also trying to tell you).

constructing object is not an allocator's duty, it is std::construct_at's duty. That's why std::allocator<T>::construct() has been removed and std::allocator_traits<std::allocator<T>>::construct() has been changed to just a call to std::construct_at (https://en.cppreference.com/w/cpp/memory/allocator)

@GoswinvonBrederlow Since you've been commenting unhelpful (and mostly  wrong), I've searched cppreference: https://en.cppreference.com/w/cpp/language/reinterpret_cast#Type_aliasing / "AliasedType is std::byte, (since C++17) char, or unsigned char: this permits examination of the object representation of any object as an array of bytes." so unsigned char* to T* is not UB, "they are both arrays of the same size or at least one of them is array of unknown bound, and the array element types are similar." so T* to Chunk* is not UB, so all reinterpret_casts are OK here

@frozenca You can cast any value pointer to unsigned char * to inspect the object representation. You can not cast any object representation to T* unless an object of type T lives at that place and your pointer was cast from T* before. Unless you constructed T or Chunk objects or you have implicit lifetimes with C++20 your casts are UB. I believe your code is always UB before C++20, because that's the thing they had to fix. It was impossible to write an allocator / new to exact standards before C++20.

unsigned char* to T* is OK, the problem is dereferencing that T* if an object of type T is not constructed yet.

@PepijnKramer T is any typename so you have to assume the worst. The fix might be to add requires to limit T to something the code can handle but I think the problem goes deeper. Note: I used UB loosely to include implementation defined behavior.

@frozenca The cast alone is implementation defined. I included that when I said UB. Strictly speaking those are 2 different things. IDB is probably OK since you didn't add the language-lawyer tag. But that's for you to decide.

When did the C++ standard changed pointer conversions without dereferencing to UB? When did the standard changed implementation defined behaviors to UB? Did I ask you implementation defined behaviors?

@GoswinvonBrederlow Yes that's what I meant, assuming the worst (writing libraries will teach you that, the wealth of creative uses by develors is nearly endless). And I refered to the use of UB by OP not you :) OP would do well to create unit tests as well.

@frozenca you're reading the note on AliasedType backwards. You're allowed to read an object's storage through a char or unsigned char pointer, not the other way around. The description and intention is very clear, you're allowed to read the contents of an existing object as an array of bytes. That rule does not apply to casting a char * to an arbitrary object as you've done here.

@JonReeves You're right, but you can see that my code isn't actually dereferencing T*. It only converts unsigned char* to T*, and converts it to Chunk* again. Chunk is a union of T* and T[].

@frozenca but you do dereference it later using chunk_ptr. It doesn't matter how many intermediate pointers you pass it through, in the end, there is an incompatible lookup. FWIW I'm not the sort of person to go nuts on language lawyerisms, I've written dozens of object allocators just like yours in my time, the biggest issue you're overlooking here is alignment, which is also easy to fix, but not easy to write up in a comment.

aliasing rule for union is more relaxed, as I know for unions, "Any member of an object that has an effective union type can be accessed at any time, provided the byte representation amounts to a valid value of the access type" Here the access type is T*

That is true for an existing object of union type, i.e. a variable which was declared as a union to begin with. But you don't have an object of union type here. You have a character array that you're type punning to a union. There is a very significant difference.

Hmm, rethinking what I said, I think you're right. https://eel.is/c++draft/basic#compound-4 says that there should be two objects in advance before interconverting pointer to pointers even without dereferencing. Looks like a pretty silly requirement...

chunk->next_ = chunk_ptr + Count; points to the last T in the chunk, not the next chunk. You forgot to add the offset of Chunk::object_ to skip over the T* next; You also have to add any padding after object_ to the get address of the next chunk. Why didn't you write chunk->next_ = chunk + 1;? Or is that tracking how much space is left free in each chunk? Then only the first part applies.

chunk_ptr is T*, not Chunk*, the naming was mistake. anyway chunk_ptr + Count points to the beginning of the next Chunk, Chunk is a union, not aclass

concept DiskAllocable T enforces sizeof(T) % alignof(T) == 0, I think there is no padding

The issue with alignment is that there is no enforcement on pool_ptr. A user of your allocator could declare any arbitrary character array and pass it in as the backing storage, regardless of how that memory was allocated and aligned.

As I know alignof(unsigned char) is 1. and since pool_size_ = pool_byte_size / block_size_ and there is a check if pool_size_ < 1, the remainder bytes are just ignored. For example, if sizeof(T) == 16, alignof(T) == 8, Count == 3, pool_byte_size_ == 200, in this case block_size_ == sizeof(Chunk) == 48, alignof(Chunk) == 8, and pool_size_ == 4, and the remaning 8 bytes will not be used

When we talk about alignment, it's not padding we worry about. We worry about the numeric address that is used to refer to an object. You probably want to read up on this topic a bit. Per usual some people have asked similar questions

Uh, yes, I missed something. I must ensure pool_byte_size_ % block_size_ == 0 (or at least pool_byte_size_ % sizeof(T) == 0) otherwise comparing with something like T* pool_end_ = pool_ + pool_size_ will make a big problem, good catch. thanks

I think I'd better to add another safeguard pool_byte_size_ % sizeof(T*) == 0, because of next_ in Chunk

@frozenca that still won't guarantee alignment. For example it T is int, you could have pool_byte_size_ be 8, which will pass your test, but pool_ptr could be 1, which will result in unaligned access. I strongly suggest you change your implementation to have the allocator itself allocate and own the pool of memory, and use std::aligned_storage as the backing store.

std::aligned_storage is deprecated in C++23 because any attempt to use it is technically UB.

Fair enough, then use aligneof(T) std::byte[] as recommended for migration.

The code is incomplete. Where does pool_ptr points to? How was it constructed? What is inside "other details"? Please post a more of the program to be able to analyze the whole flow.

Just to close the loop on the long discussion in the comments, I strongly suggest that you make the pool ownership part of the AllocatorFixed class itself. This will allow you to avoid all of the problems you're asking about with aliasing, and greatly simplify the code in the process. For example:
template <DiskAllocable T, size_t Count = 1, size_t NumChunks = 1> class AllocatorFixed {
  union Chunk {
    Chunk *next_;
    std::aligned_storage<sizeof(T), alignof(T)> object_[Count];
  } chunks_[NumChunks];

  Chunk *free_ = nullptr;

public:
  using value_type = T;

  AllocatorFixed() {
    for (size_t i = 0; i < NumChunks - 1; i++) {
      chunks_[i].next_ = &chunks_[i+1];
    }
    chunks_[NumChunks-1].next_ = nullptr;
    free_ = &chunks_[0];
  }

 // ... other details ...

};


Everything here is perfectly defined and legal, construction is trivial, and the rest of your implementation should be extremely straightforward.
You could even adapt this to mmapped files as requested using placement new. For example:

using MyAllocator = AllocatorFixed<int, 2, 20>;

...

    MyAllocator *pAllocator = nullptr;
    char *ptr = (char *)mmap(...);
    pAllocator = ::new(ptr) MyAllocator();

...


Disclaimer: this is one suggestion to get around the specific problems you asked about. I doubt this will apply perfectly to your exact motivating situation, but hopefully it gives you a few additional tools to consider.

There is a good reason behind getting a memory pool as constructor argument. I'm using a memory mapped disk file (possibly gigabytes sized) as memory pool and this will be my main use case

@frozenca you can still use this implementation exactly as it is with an mmapped file. Construct it using placement new with the pointer obtained via mmap().

I added another check (std::bit_cast<size_t>(pool_ptr) % sizeof(T)) || (std::bit_cast<size_t>(pool_ptr) % sizeof(T*))
