Jon Chesterfield Jon Chesterfield - 11 days ago 6
C Question

Implement a struct type on top of void *

Simple sanity check question here. The underlying requirement is to put two flexible array members in a struct to reduce the number of calls to malloc for performance reasons.

Given that a struct instance is a block of aligned memory containing a number of fields at constant offsets, can one implement functionality semantically equivalent to a struct by writing the offset calculations and casting?

void f()
{
typedef struct
{
double x;
char y;
int32_t foo;
double z;
} equivalent;
equivalent * e = malloc(sizeof(equivalent));
free(e);

static_assert(sizeof(equivalent) == 24,"");
char* memory = malloc(24);
double* x = (double*) ( 0 + memory);
char* y = (char *) ( 8 + memory);
int32_t* foo = (int32_t*) (12 + memory);
double* z = (double*) (16 + memory);
free(memory);
}


Keeping the alignment / offset calculations consistent is tedious, but assuming the type is opaque anyway the client code doesn't have to see any of that. Similarly the syntactic overhead is hidden.

I've read through the aliasing rules as clarified by C11 (the "effective type" part) and think I'm in the clear there.

Is this fair game? I thought I'd seek a second opinion prior to writing a lot of very dull code.

Cheers

edit: As a response to Jonathan Leffler, this is a quick & dirty sketch of how I intend to put a couple of arrays of runtime determined length into the single block of memory.

I prefer storing an integer which is used to calculate the location of the array, as opposed to storing a pointer which is already aimed at the array, because it makes copying the structure simpler. Storing appropriately initialised pointers and relocating them on copy is probably faster though.

void* g(uint64_t N_first, uint64_t N_second)
{
// desired representation:
// uint64_t N_first;
// int32_t first[N_first];
// uint64_t N_second;
// double second[N_second];
// this function doesn't populate the arrays, only
// allocates storage and sets up the length fields

uint64_t bytes_for_lengths = 16;

char* bytes = malloc(bytes_for_lengths + bytes_for_first(N_first) +
bytes_for_second(N_second));

uint64_t* ptr_N_first = get_N_first(bytes);
*ptr_N_first = N_first;

uint64_t* ptr_N_second = get_N_second(bytes);
*ptr_N_second = N_second;

return (void*)bytes;
}

// I haven't decided how best to factor out the field access
// and associated functions yet, so this is not optimal

uint64_t* get_N_first(void* vdata)
{
char* data = (char*)vdata;
return (uint64_t*)(data + 0);
}
int32_t* get_first(void* vdata)
{
char * data = (char*)vdata;
return (int32_t*)(data + 8);
}
uint64_t bytes_for_first(uint64_t N_first)
{
// first is an int32_t
// the next field needs to be 8 byte aligned
uint64_t bytes = 4 * N_first;
if (bytes % 8 != 0)
{
bytes += 4;
}
return bytes;
}

uint64_t* get_N_second(void* vdata)
{
uint64_t n_first = *get_N_first(vdata);
uint64_t first_bytes = bytes_for_first(n_first);
char* data = (char*)vdata;
return (uint64_t*)(data + 8 + first_bytes);
}
double* get_second(void* vdata)
{
char * data = (char*)vdata;
uint64_t n_first = *get_N_first(vdata);
uint64_t first_bytes = bytes_for_first(n_first);
return (double*)(data + 8 + first_bytes + 8);
}
uint64_t bytes_for_second(uint64_t N_second)
{
// second is a double
return 8 * N_second;
}

Answer

I can't help but feel that it would be cleaner to use a straight-forward structure to achieve your 'double VLA' structure type. More or less like this:

// desired representation:
// uint64_t N_first;
// int32_t first[N_first];
// uint64_t N_second;
// double second[N_second];

#include <assert.h>
#include <inttypes.h>
#include <stdalign.h>
#include <stdio.h>
#include <stdlib.h>

struct DoubleVLA
{
    uint64_t  N_first;
    int32_t  *first;
    uint64_t  N_second;
    double   *second;
    //double    align_32[];     // Ensures alignment on 32-bit
};

extern struct DoubleVLA *alloc_DoubleVLA(uint64_t n1, uint64_t n2);

struct DoubleVLA *alloc_DoubleVLA(uint64_t n1, uint64_t n2)
{
    struct DoubleVLA *dv = malloc(sizeof(*dv) + n1 * sizeof(dv->first) + n2 * sizeof(dv->second));
    if (dv != 0)
    {
        dv->N_first = n1;
        dv->N_second = n2;
        if (alignof(dv->second) >= alignof(dv->first))
        {
            dv->second = (double *)((char *)dv + sizeof(*dv));
            dv->first  = (int32_t *)((char *)dv + sizeof(*dv) + n2 * sizeof(dv->second));
        }
        else
        {
            dv->first  = (int32_t *)((char *)dv + sizeof(*dv));
            dv->second = (double *)((char *)dv + sizeof(*dv) + n1 * sizeof(dv->first));
        }
    }
    return dv;
}

int main(void)
{
    struct DoubleVLA *dv = alloc_DoubleVLA(UINT64_C(11), UINT64_C(32));
    for (uint64_t i = 0; i < dv->N_first; i++)
        dv->first[i] = i * 100 + rand() % 100;
    for (uint64_t j = 0; j < dv->N_second; j++)
        dv->second[j] = j * 1000.0 + (rand() % 100000) / 100.0;
    for (uint64_t i = 0; i < dv->N_first; i++)
        printf("%.2" PRIu64 " = %12" PRId32 "\n", i, dv->first[i]);
    for (uint64_t j = 0; j < dv->N_second; j++)
        printf("%.2" PRIu64 " = %12.2f\n", j, dv->second[j]);
    free(dv);
    return 0;
}

Even on a 32-bit platform, there should be enough padding at the end of the structure to make its size such that it will be appropriately aligned for an array of double immediately after the structure and an array of int32_t after that. However, there would be unnecessary padding that could be avoided by putting the two sizes first and the two pointers last in the structure. That isn't a problem on a 64-bit platform. The optional align_32 VLA assumes that the alignment requirement of int32_t is not greater than the alignment requirement of double; it would ensure that the structure is padded correctly, even if there was some weird alignment restrictions or requirements. It would be possible to provide a static assertion that the constraints are met.

The alignof material is from C11; it allows you to work with two types with different alignment requirements and automatically selects the better layout (more stringently aligned array before less stringent one).

With this organization, there's no need for a functional interface to the sections of the structure. Direct access is simple and readily comprehended.