Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C best practice for using stack memory for incomplete structs

There are times when I want to have a struct which is incomplete (only a single C file knows about its members), so I can define an API for any manipulations and so developers can't easily manipulate it outside the API.

The problem with doing this, its it often means you need a constructor function, which allocates the data, and free it after (using malloc and free).

In some cases this makes very little sense from a memory management perspective, especially if the struct is small, and its allocated and freed a lot.

So I was wondering what might be a portable way to keep the members local to the C source file, and still use stack allocation.

Of course this is C, if someone wants to mess with the struct internals they can, but I would like it to warn or error if possible.

Example, of a simple random number generator (only include new/free methods for brevity).

Header: rnd.h

struct RNG;
typedef struct RNG RNG;

struct RNG *rng_new(unsigned int seed);
void        rng_free(struct RNG *rng);

Source: rnd.c

struct RNG {
    uint64_t X;
    uint64_t Y;
};

RNG *rng_new(unsigned int seed)
{
    RNG *rng = malloc(sizeof(*rng));
    /* example access */
    rng->X = seed;
    rng->Y = 1;
    return rng;
}

void rng_free(RNG *rng)
{
    free(rng);
}

Other source: other.c

#include "rnd.h"
void main(void)
{
    RND *rnd;

    rnd = rnd_new(5);

    /* do something */

    rnd_free(rnd);
}

Possible solutions

I had 2 ideas how it could be done, both feel a bit of a kludge.

Declare the size only (in the header)

Add these defines to the header.

Header: rnd.h

#define RND_SIZE      sizeof(uint64_t[2])
#define RND_STACK_VAR(var) char _##var##_stack[RND_SIZE]; RND *rnd = ((RND *)_##var##_stack)

void rnd_init(RND *rnd, unsigned int seed);

To ensure the sizes are in sync.

Source: rnd.c

#include "rnd.h"

struct RNG {
    uint64_t X;
    uint64_t Y;
};

#define STATIC_ASSERT(expr, msg) \
    extern char STATIC_ASSERTION__##msg[1]; \
    extern char STATIC_ASSERTION__##msg[(expr) ? 1 : 2]

/* ensure header is valid */
STATIC_ASSERT(RND_SIZE == sizeof(RNG))

void rng_init(RNG *rng, unsigned int seed)
{
    rng->X = seed;
    rng->Y = 1;
}

Other source: other.c

#include "rnd.h"

void main(void)
{
    RND_STACK_VAR(rnd);

    rnd_init(rnd, 5);

    /* do something */

    /* stack mem, no need to free */
}

Keeping the size in sync for large struct members may be a hassle, but for small struct's it's not such a problem.

Conditionally hide the struct members (in the header)

Using GCC's deprecated attribute, however if there is some more portable way to do this it would be good.

Header: rnd.h

#ifdef RND_C_FILE
#  define RND_HIDE /* don't hide */
#else
#  define RND_HIDE __attribute__((deprecated))
#endif

struct RNG {
    uint64_t X RND_HIDE;
    uint64_t Y RND_HIDE;
};

Source: rnd.c

#define RND_C_FILE
#include "rnd.h"

void main(void)
{
    RND rnd;

    rnd_init(&rnd, 5);

    /* do something */

    /* stack mem, no need to free */
}

This way you can use RND as a regular struct defined on the stack, just not access its members without some warning/error. But its GCC only.

like image 571
ideasman42 Avatar asked Apr 02 '14 02:04

ideasman42


Video Answer


2 Answers

You can accomplish this in standard C in a manner similar to your first example, though not without going through a great deal of pain to evade aliasing violations.

For now let's just look at how to define the type. In order to keep it fully opaque we'll need to use a VLA that takes the size from a function at runtime. Unlike the size, alignment can't be done dynamically, so we have to maximally align the type instead. I'm using C11's alignment specifiers from stdalign.h, but you can substitute your favorite compiler's alignment extensions if you want. This allows the type to freely change without breaking ABI just like a typical heap-allocated opaque type.

//opaque.h
size_t sizeof_opaque();
#define stack_alloc_opaque(identifier) \
    alignas(alignof(max_align_t)) char (identifier)[sizeof_opaque()]

//opaque.c
struct opaque { ... };
size_t sizeof_opaque(void) { return sizeof(struct opaque); }

Then, to create an instance blackbox of our faux type, the user would use stack_alloc_opaque(blackbox);

Before we can go any further we need to determine how the API is going to be able to interact with this array masquerading as a struct. Presumably we also want our API to accept heap allocated struct opaque*s, but in function calls our stack object decays to a char*. There are a few conceivable options:

  • Force the user to compile with an equivalent of -Wno-incompatible-pointer-types
  • Force the user to manually cast in every call like func((struct opaque*)blackbox);
  • Resort to redefining stack_alloc_opaque() to use a throwaway identifier for the array, and then assign that to a struct opaque pointer within the macro. But now our macro has multiple statements and we're polluting the namespace with an identifier the user doesn't know about.

All of those are pretty undesirable in their own way, and none address the underlying problem that while char* may alias any type, the inverse is not true. Even though our char[] is perfectly aligned and sized for a struct opaque, reinterpreting it as one through a pointer cast is verboten. And we can't use a union to do it, because struct opaque is an incomplete type. Unfortunately that means that the only alias-safe solution is:

  • Have every method in our API accept a char* or typedef to char* rather than struct opaque*. This allows the API to accept both pointer types, while losing all semblance of type safety in the process. To make matters worse, any operations within the API will require memcpying the function's argument into and back out of a local struct opaque.

Which is rather monstrous. Even if we disregard strict aliasing, the only way to maintain the same API for heap and stack objects in this situation is the first item (don't do that).

On the matter of disregarding the standard, there is one other thing:

  • alloca

It's a bad word, but I'd be remiss not to mention it. Unlike a char VLA, and like malloc, alloca returns a void pointer to untyped space. Since it has roughly the same semantics as malloc, its use doesn't require any of the gymnastics listed above. Heap and stack API could happily live side by side, differing only in object (de)allocation. But alloca is nonstandard, the returned objects have a slightly different lifetime than a VLA, and its use is near universally discouraged. Unfortunate that it is otherwise well suited to this problem.

As far as I can see, there is only one correct solution (#4), only one clean solution (#5), and no good solution. The way you define the rest of the API depends on which of those you choose.

like image 65
tab Avatar answered Oct 12 '22 22:10

tab


In some cases this makes very little sense from a memory management perspective, especially if the struct is small, and its allocated and freed a lot.

I don't see the problem here. In your example, someone probably will only use one RND for the lifetime of their program, or at least, a small number of them.

And if the struct is allocated and freed a lot then it makes no performance difference whether your library does all the allocating and freeing, or whether their code does it.

If you want to permit automatic allocation, then the caller will have to know the size of your struct. There is no way of getting around this. Also, this somewhat defeats the purpose of hiding your implementation, as it means you can't change the size of your struct without breaking the client code.

Further, they will have to allocate memory that is correctly aligned for your struct (i.e. they can't just go char foo[SIZE_OF_RND]; RND *rng = (RND *)foo; because of alignment issues). Your RND_STACK_VAR example ignores this problem.

Perhaps you could publish a SIZE_OF_RND that is the actual size, plus some allowance for alignment. Then your "new" function uses some hacks to find the right alignment location in that memory and returns a pointer.

If it feels kludgey, that's because it is. And there is nothing stopping them just writing the bytes inside the RND anyway. I would just use your first suggestion of RND_new() etc. unless there were a very strong reason why it wasn't suitable.

like image 25
M.M Avatar answered Oct 12 '22 22:10

M.M