C++ fixed size allocator: is this UB?

Question

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". — Goswin von Brederlow, Jul 19 '22 at 14:51
1. casting between ```Chunk*``` and ```T*``` where ```Count``` may not be 1 / 2. writing ```chunk->next_``` as ```chunk_ptr + Count``` — frozenca, Jul 19 '22 at 14:52
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). — Pepijn Kramer, Jul 19 '22 at 15:19
constructing object is not an allocator's duty, it is ```std::construct_at```'s duty. That's why ```std::allocator::construct()``` has been removed and ```std::allocator_traits>::construct()``` has been changed to just a call to ```std::construct_at``` (https://en.cppreference.com/w/cpp/memory/allocator) — frozenca, Jul 19 '22 at 15:21
@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_cast```s are OK here — frozenca, Jul 19 '22 at 15:35
@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. — Goswin von Brederlow, Jul 19 '22 at 15:43
```unsigned char*``` to ```T*``` is OK, the problem is dereferencing that ```T*``` if an object of type ```T``` is not constructed yet. — frozenca, Jul 19 '22 at 15:47
@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. — Goswin von Brederlow, Jul 19 '22 at 15:48
@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. — Goswin von Brederlow, Jul 19 '22 at 15:50
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? — frozenca, Jul 19 '22 at 15:56
@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. — Pepijn Kramer, Jul 19 '22 at 15:57
@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. — Jon Reeves, Jul 19 '22 at 16:04
@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, Jul 19 '22 at 16:05
@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. — Jon Reeves, Jul 19 '22 at 16:08
aliasing rule for ```union``` is more relaxed, as I know for ```union```s, "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*``` — frozenca, Jul 19 '22 at 16:10
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. — Jon Reeves, Jul 19 '22 at 16:16
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... — frozenca, Jul 19 '22 at 16:28
`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. — Goswin von Brederlow, Jul 19 '22 at 16:28
```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 a```class``` — frozenca, Jul 19 '22 at 16:30
```concept DiskAllocable T``` enforces ```sizeof(T) % alignof(T) == 0```, I think there is no padding — frozenca, Jul 19 '22 at 16:35
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. — Jon Reeves, Jul 19 '22 at 16:43
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 — frozenca, Jul 19 '22 at 16:49
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](https://stackoverflow.com/questions/3025125/cpu-and-data-alignment) — Jon Reeves, Jul 19 '22 at 16:55
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 — frozenca, Jul 19 '22 at 16:56
I think I'd better to add another safeguard ```pool_byte_size_ % sizeof(T*) == 0```, because of ```next_``` in ```Chunk``` — frozenca, Jul 19 '22 at 17:04
@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. — Jon Reeves, Jul 19 '22 at 17:29
```std::aligned_storage``` is deprecated in C++23 because any attempt to use it is technically UB. — frozenca, Jul 19 '22 at 17:41
Fair enough, then use `aligneof(T) std::byte[]` as recommended for migration. — Jon Reeves, Jul 19 '22 at 18:08
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. — KamilCuk, Jul 19 '22 at 19:50

Jon Reeves · Answer 1 · 2022-07-19T18:22:53.460

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, Jul 19 '22 at 17:44
@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()`. — Jon Reeves, Jul 19 '22 at 17:58
I added another check ```(std::bit_cast(pool_ptr) % sizeof(T)) || (std::bit_cast(pool_ptr) % sizeof(T*))``` — frozenca, Jul 20 '22 at 04:31

C++ fixed size allocator: is this UB?

1 Answers1