slopfront
preferences

Pattern for allocation of a objects from non-standard allocators

5 points · submitted Jul 2024 by u/tstanisl

Many non-standard allocators (like arenas) tend to provide two functions/macros for allocation of objects. One for allocation of a single object and another for allocation of an array of objects. Usually those function follow the pattern below:

#define NEW(T) (T*)alloc(sizeof(T))
#define NEW_ARRAY(T,n) (T*)alloc(n * sizeof(T))

int * scalar = NEW(int);
int * array  = NEW_ARRAY(int, 10);

However, the same effect can be achieved with a single helper by using a pointer to an array. I mean:

int * array = *NEW(int[n]);

The NEW(int[n]) would return a pointer to the whole array ( int*[n]). After dereferencing it with * it forms a value of an array type that implicitly decays to more common int* type. However, T* would not work because int[n]* is not a valid type. The issue can be fixed with a popular typeof extension (feature in C23) to reliably convert array type T to array pointer as typeof(T)*.

#define NEW(T) (typeof(T)*)alloc(sizeof(T))

This pattern works quite well with C23's auto to provide concise type-safe pattern for allocation of scalar and multidimensional arrays.

// scalars
typedef struct { ... } S;
auto foo = NEW( S );
S * bar = NEW( typeof(*bar) );

// arrays
S * baz = *NEW( S[n] );
auto baq = *NEW( S[n] );
S * bar = *NEW( typeof(*bar)[n] );

auto arr_1d = *NEW( int[n] );
auto arr_2d = *NEW( int[n][n] );
auto arr_3d = *NEW( int[n][n][n] );

arr_1d[x] = arr_2d[x][y] = arr_3d[x][y][z] = 42;

What do you think about this pattern?

7 comments · 100% upvoted · other discussions

comments

skeeto 4 points · Jul 2024

Getting error-prone size calculations out of normal code and replacing it with an interface that operates with types is a great idea. Getting rid of the implicit void * cast will catch some mistakes, too. Most programs ought to be using NEW macros like these.

One problem with NEW(T[n]) versus NEW_ARRAY(T, n) is that former offers no opportunities to check for overflow. The expression itself would be undefined behavior before allocation occurs. Your current NEW_ARRAY definition doesn't check either — not all programs have this concern — but that could be addressed with an "array-aware" function in the macro, with no call site changes:

#define NEW_ARRAY(T, n)  (T *)calloc(n, sizeof(T))

NEW could use the same function, but with n = 1. If your allocator is alignment-aware, you could take this even further with alignof(T).

Another problem is that it requires an implementation with VLA support. I know C23 makes it mandatory again, but at least one major C implementation is ignoring that requirement just as it did last time VLAs were mandatory.

tstanisl [OP] 1 points · Jul 2024

former offers no opportunities to check for overflow

I hope that forming a valid T[n] type will be one day delegated to sanitizers.

I know C23 makes it [VLA] mandatory again, but at least one major C implementation

C23 makes only VLA types mandatory. The most controversial feature which is allowing VLA objects with automatic storage, stays optional in C23. Even though I don't think that MSVC will support Variably Modified Types (VMTs) any soon. It's because VMTs do not integrate well into C++ typing system. MSVC is essentially C++ compiler with C++-only features disabled when compiling C files.

skeeto 3 points · Jul 2024

delegated to sanitizers

This touches on the difference between assertions and error handling. Sanitizers are the former, and if the goal is to push overflow checks into the allocator — which I think it should be — then overflow checks are the latter. That is, a size overflow is just one way to run out of memory. In that case sanitizers are the wrong tool.

For example, suppose you're reading float data from a packet or whatever, and the data is prefixed with a 32-bit count to tell you how much to read. That's fairly common. That might look like (skipping read error checks):

float *readfloats(int fd)
{
    uint32_t len  = read32le(fd);
    float   *nums = NEW_ARRAY(float, len);
    if (!nums) {
        return 0;  // could not allocate buffer
    }
    fullread(fd, nums, sizeof(*nums)*len);
    return nums;
}

On a 32-bit host sizeof(float)*len might overflow, as in it's an impossible allocation. That's an error, not a program defect. A T[n] interface can't handle this situation.

tstanisl [OP] 1 points · Jul 2024

I am still not convinced if it is allocator's duty to make such a check. Allocator allocates the memory for a type. Checking if the type is valid is the callers problem because the caller is the user of this type. Though I understand that it is convenient to delegate checking to the allocator in a typical application of plain 1d array.

My argument against is allocation of 2D array with NEW_ARRAY(float, n * n) or NEW_ARRAY(float[n], n). The n * n or sizeof(float[n]) could overflow. There is no way to make such a check on allocator's side. The check can be done either explicitly by a caller or implicitly by a sanitizer.

If one wants to be explicit then the caller could do:

if (nums > SIZE_MAX / sizeof(float))
  return 0;
float * nums = *ALLOC(float[num]);

Alternatively, one could add "multidimensional" interfaces like ALLOC_NDARRAY(float, n, n) and do all the size checks inside a macro. It is going to be convoluted but likely do-able.

flatfinger 2 points · Jul 2024

Does anything in the Standard specify for what range of n the evaluation of sizeof (T[n]) would need to be treated as defined behavior? The constant SIZE_MAX doesn't specify the largest allowable object size, but rather the maximum value of an object of type size_t, which may be larger.

tstanisl [OP] 1 points · Jul 2024

Ok.. but does the C standard tell anything about the largest size that a valid object can have? Could in theory int[42] be too large even if SIZE_MAX is 264-1?

flatfinger 1 points · Jul 2024

The C Standard requires hosted implementations support objects of at least 65,535 bytes. For freestanding implementations there is no such requiremenet (target platforms might not even have a tenth that much RAM in total).