Various length structure in C for memory manager?

Question

I practice in realization a memory manager in C.

I want the structure, that has a various length and self-described. So, I peep at a POSIX textbook something, like that:

struct layout
{
 uint32_t  size; // array size in bytes, include space after the struct
 uchar_t   data[1];
};

// But, is next line correct?
layout *val = malloc (array_memory_in_bytes + sizeof (uint32_t) - 1);
// Where does a static array keep the pointer for using it? 

If I have several these structures one-after-one in uninterrupted piece of memory, and I want be able to iterate through them. Can I write something, like that:

layout *val1 = pointer;
layout *val2 = val1 + val1.size + sizeof (val1.size);

Or can you recommend me a better approach?

Answer 1

The Standard C version of this is called flexible array member and it looks like:

struct layout
{
    uint32_t size;
    uchar_t data[];
};

// allocate one of these blocks (in a function)
struct layout *val = malloc( sizeof *val + number_of_bytes );
val->size = number_of_bytes;

---

The code val1->data + val1->size will get you a pointer one-past-the-end of the space you just malloc'd.

However you cannot iterate off the end of one malloc'd block and hope to hit another malloc'd block. To implement this idea you would have to malloc a large block and then place various struct layout objects throughout it, being careful about alignment.

In this approach, it's probably best to also store an index of where each struct layout is. In theory you could go through the list from the start each time, adding on size and then doing your alignment adjustment; but that would be slow and also it would mean you could not cope with a block in the middle being freed and re-"allocated".

If this is meant to be a drop-in replacement for malloc then there are in fact two alignment considerations:

• alignment for struct layout
• data must be aligned for any possible type

The simplest way to cope with this is to align struct layout for any possible type also. This could look like (note: #include <stdint.h> required):

struct layout
{
    uint64_t size;    // may as well use 64 bits since they're there
    _Alignas(max_align_t) uchar_t data[];
};

An alternative might be to keep size at 32-bit and throw in a pragma pack to prevent padding; then you'll need to use some extra complexity to make sure that the struct layout is placed 4 bytes before a max_align_t-byte boundary, and so on. I'd suggest doing it the easy way first and get your code running; then later you can go back and try this change in order to save a few bytes of memory if you want.

---

Alternative approaches:

• Keep each instance of a struct layout plus its trailing data in a separate allocation.
• Change data be a pointer to malloc'd space; then you could keep all of the struct layout objects in an array.

Answer 2

The general idea will work, but that specific struct will only work if the most-severe boundary alignment case is an int.

A memory manager, particularly one that might be a back-end for an implementation of malloc(), must know what that worst-case boundary is. The actual start of data must be on that boundary in order to satisfy the general requirement that the allocated memory be suitably aligned for the storage of any data type.

The easiest way to get that done is to make the length allocation header described by the layout struct and the actual allocation sizes all multiples of that alignment unit.

No matter what, you can't describe the start of data as a struct member and have the size of that struct be the size of the header. C doesn't support zero-length fields. You should use something to put that array on boundary, and use the offsetof() macro from <stddef.h>.

Personally, I'd use a union, based on both old habits and occasional use of Visual C++ for C. But uint32_t is a C99 type and if you also have C11 support you can use _Alignas(). With that, your struct could look something like:

#define ALIGN_TYPE double /* if this is the worst-case type */
#define ALIGN_UNIT ((sizeof)(ALIGN_TYPE))
#define ALIGN_SIZE(n) (((size_t)(n) + ALIGN_UNIT - 1) & ~(ALIGN_UNIT-1))

typedef struct layout
{
    size_t size; /* or use uint32_t if you prefer */
    _Alignas(ALIGN_UNIT) char data[1];

} layout;

#define HEADER_SIZE (offsetof(layout, data))

That makes most everything symbolic except for the worst-case alignment type. You'd allocate the combined header plus data array with:

layout *ptr = (layout*) malloc(HEADER_SIZE + ALIGN_SIZE(number_of_bytes));
ptr->size = HEADER_SIZE;

The ALIGN_SIZE type really isn't a symbolic constant, though, unless C99/C11 changed the definition of sizeof. You can't use to compute ordinary array dimensions, for example. You can hard code a literal number, like 8 for a typical double, if that's a problem. Beware that long double has a problematical size (10 bytes) on many x86 implementations. If you're going to base the allocation unit on a type, then long double might not be your best choice.