Avoiding double allocation for structs and data

By Jsanchez | June 26, 2020 | 4 minutes

Let’s say you want to allocate a struct that contains a pointer to other data that also needs allocation. The natural way to do it is calling malloc twice, one for the container and one for the data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/* The natural way to allocate a struct and its data */
struct sample_type
{
    float A;
    uint32_t B;
    uint8_t C;
    bool D;
    bool E;
    bool F;
    bool G;
};

struct sample_struct
{
    uint32_t Count;
    sample_type *Data;
};

uint32_t Count = 5;
sample_struct *Container = (sample_struct*)malloc(sizeof(sample_struct));
Container->Count = Count;
Container->Data = (sample_type*)malloc(sizeof(sample_type) * Count);

// Do something to the data
for(uint32_t i = 0; i < Container->Count; i++)
{
    Container->Data[i] = {};
}

free(Container->Data);
free(Container);

Something doesn’t feel right. These two allocations are going to be used together, one after the other, but there is no guarantee they will be next to each other in memory. On top of that you have two calls to malloc that can fail, two calls to free you need to remember, and twice the allocator overhead.

Here is one way to use just a single allocation for the container and its data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* Using a single allocation */
uint32_t Count = 5;
sample_struct *Container = (sample_struct*)malloc(sizeof(sample_struct) + sizeof(sample_type) * Count);
Container->Count = Count;
Container->Data = (sample_type*)(Container + 1);

// Do something to the data
for(uint32_t i = 0; i < Container->Count; i++)
{
    Container->Data[i] = {};
}

free(Container); // Frees both the container and the data

If you ask me the second version is better: a single call to malloc, a single call to free, and things that belong together are guaranteed to be adjacent in memory.

Watch out for alignment

There is something you need to be aware of while using this trick. Container + 1 points to the first byte after the struct, and that address has to be properly aligned for sample_type. In this example it works out, sizeof(sample_struct) is 16 on a 64 bit machine and sample_type only needs 4 byte alignment. But if sample_type ever needs a stricter alignment than the container (a SIMD type with alignas(16) for example) you’ll end up with a misaligned pointer and nobody is going to warn you about it.

The safe way is to round the offset up to the alignment of the data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


/* Single allocation with the data properly aligned */

// The alignment sample_type needs, in bytes. Alignments are always a
// power of two (1, 2, 4, 8, 16...).
size_t Align = alignof(sample_type);

// Offset is where the data will start, measured from the beginning of
// the allocation. It's sizeof(sample_struct) rounded up to the next
// multiple of Align.
//
// Since Align is a power of two, Align - 1 has all the bits below it
// set. For Align = 16, Align - 1 is 0b1111 and ~(Align - 1) is a mask
// with those 4 low bits cleared.
//
// Adding Align - 1 pushes the size past the next multiple of Align
// (unless it's already on one), and the & with the mask clears the low
// bits, rounding it back down to that multiple.
//
// Example with a 20 byte struct and Align = 16:
//   20 + 15 = 35
//   35 & ~15 = 32, the first multiple of 16 that fits the struct.
size_t Offset = (sizeof(sample_struct) + Align - 1) & ~(Align - 1);

// One allocation: the struct, any padding needed to reach Offset, and
// then the data. uint8_t* so pointer arithmetic is in bytes.
uint8_t *Memory = (uint8_t*)malloc(Offset + sizeof(sample_type) * Count);

// The struct lives at the start of the block.
sample_struct *Container = (sample_struct*)Memory;
Container->Count = Count;

// The data starts Offset bytes in, which is guaranteed to be aligned.
Container->Data = (sample_type*)(Memory + Offset);

On the other hand, where Data sits inside the struct doesn’t matter. The array always starts after the whole struct, so you can add members anywhere you want.

1
2
3
4
5
6


struct sample_struct
{
    uint32_t Count;
    sample_type *Data;
    float Other; // Fine, sizeof(sample_struct) grows and the array moves with it.
};

One last note for C++ folks: all of this works because sample_type is a trivial type. If your type has constructors or destructors you need to construct each element with placement new and destroy them yourself before calling free.