3
\$\begingroup\$

I am trying to write a custom stack allocator for a game I am working on. To deal with memory alignment, I am using C11's stdalign.h header; however, since I do not have prior experience with alignment issues, I'd like a expert opinion on whether I am doing it right.

The majority of the alignment stuff happens in alignup and aligndown macros. Specifically, in alignup, I try to go up to the nearest multiple of alignof(max_align_t) (unless we were already a multiple) by shooting past it by adding alignof(max_align_t) - 1 and then coming back using the bitwise AND. In aligndown, I first go below the last multiple of alignof(max_align_t) and then come up using alignup.

NOTE: The stack is in a memory arena and it grows down in memory instead of going up.

#define alignup(p) ((void*)((((char*)(p)) + (alignof(max_align_t) - 1)) & (~ (alignof(max_align_t) - 1))))

#define aligndown(p) ((void*)(alignup((((char*)(p)) - (alignof(max_align_t) - 1)))))

struct Mem_Stack_Header {
    size_t allocation_size;
    size_t total_size;
};

// This contains the "head" of the stack. The stack grows down, instead of up.
extern void *stack_head;


void* memPush (size_t s)
{
    void *head = stack_head;

    void *mem = (char*)head - s;
    mem = aligndown(mem);

    struct Mem_Stack_Header *h = (struct Mem_Stack_Header*)((char*)mem - sizeof(*h));
    h =  aligndown(h);
    h->allocation_size = s;
    h->total_size = (uintptr_t)((char*)head - (char*)h);

    stack_head = h;

    return mem;
}


void memPop (void)
{
    struct Mem_Stack_Header *h = stack_head;

    stack_head = (char*)stack_head + h->total_size;

    return;
}

Is this the correct way of doing this kind of stuff? Any improvements I can make?

\$\endgroup\$
  • \$\begingroup\$ What is internal_function? You don't seem to define it anywhere. \$\endgroup\$ – Ben Steffan Dec 31 '17 at 13:33
  • \$\begingroup\$ @BenSteffan Oh, that's just static. static has so many meanings in C, I define internal_function, persistent_value and global_variable to static to give some semantic context. \$\endgroup\$ – strNOcat Dec 31 '17 at 13:35
  • 1
    \$\begingroup\$ I see. Besides, are you aware that your code contains undefined behavior due to your use of a reserved identifier (_Mem_Stack_Header is reserved because it begins with an underscore immediately followed by a capital letter)? \$\endgroup\$ – Ben Steffan Dec 31 '17 at 13:39
  • \$\begingroup\$ @BenSteffan No, I thought two underscores were not allowed. Just googled and found out about one underscore at file scope too. Thanks. \$\endgroup\$ – strNOcat Dec 31 '17 at 13:43
  • \$\begingroup\$ "Is this the correct way of doing this kind of stuff?" No. Code is broken with the first call of memPush()and void *mem = (char*)head - s; as that is pointer arithmetic on an invalid pointer (stack_head == NULL). VTC \$\endgroup\$ – chux - Reinstate Monica Jan 1 '18 at 19:58
1
\$\begingroup\$

Is this the correct way of doing this kind of stuff? Any improvements I can make?

  1. The role of member allocation_size is unclear. It appears to represent the raw alignment with h->allocation_size = s;. Later use with stack_head = (char*)stack_head + h->total_size; could then result in an unaligned stack_head. I recommend that void* memPush (size_t s) first take s and increment it as needed to an aligned size and then save that value in allocation_size. This will simplify subsequent code too especially the macro aligndown()

    s = (s + alignof(max_align_t) - 1) & ~(alignof(max_align_t) - 1u);
    
  2. There is no protection against pushing too much. I'd expect the size of memory available with stack_head to be provided and memPush() to code against overflow. In any case, OP should provide documentation concerning what happens when too much memory is requested.

  3. There is no clear functionality against popping too much. I'd expect either an error return or a perhaps the equivalent of the top allocation having size 0.

  4. Some compilers will warn about mixed signed/unsigned math. As the return type from alignof() is some unsigned type, use unsigned constants throughout.

    //alignof(max_align_t) - 1
    alignof(max_align_t) - 1u
    
  5. The name stack_head is a global object that could easily collide with other code. Its name does not suggest that is is part of the memPop(), memPush() functions. Recommend a name aligned with the funcitons like mem_stack_head.

  6. A use of memPush(0) needs special consideration. I recommend that such usage returns the same as memPush(alignof(max_align_t)) to provide unique allocations. In any case, OP should provide documentation concerning the special case.

  7. uintptr_t is an optional type and not the best to use here. (char*)head - (char*)h results in type ptrdiff_t, simply cast it to the destination type. Alternative:

    //h->total_size = (uintptr_t)((char*)head - (char*)h);
    h->total_size = (size_t)((char*)head - (char*)h);
    
  8. Code could reduce explicit coding of cast (char *) by using char *head = stack_head;

  9. Alternative idea to this line of code:

    // struct Mem_Stack_Header *h = (struct Mem_Stack_Header*)((char*)mem - sizeof(*h));
    struct Mem_Stack_Header *h = (struct Mem_Stack_Header*)mem - 1;
    
  10. A simple test harness would help in evaluation of this code.

  11. alignof is not valid without #include <stdalign.h>. Other include files missing too.

\$\endgroup\$
  • \$\begingroup\$ Regarding 1, allocation_size is essentially requested_size to track how much memory the client code asked for and would actually use (I've renamed it). total_size is the size that includes actual memory allocated and it is used to deallocate (which means it will always be aligned properly since it was assigned to after aligning the pointers). \$\endgroup\$ – strNOcat Jan 2 '18 at 5:54
  • \$\begingroup\$ WRT 5, ignore issues about stack_head, it was added as a placeholder in this code, the actual code uses a Engine_State struct which is kind of irrelevant to the question and would just add noise. Thanks for the other points. \$\endgroup\$ – strNOcat Jan 2 '18 at 5:56
  • \$\begingroup\$ Yes I agree #1 is erroneous with regard to stack_head = (char*)stack_head + h->total_size; \$\endgroup\$ – chux - Reinstate Monica Jan 2 '18 at 5:59
  • \$\begingroup\$ Can you please provide some feedback on whether the alignup and aligndown macros are correct and whether this is right way to deal with alignment in custom allocators? That's the part of the code that I don't have any experience with and would like to be sure about. \$\endgroup\$ – strNOcat Jan 2 '18 at 6:08
  • \$\begingroup\$ Aside from #4, I do not see a problem with aligndown(). It appears functionally correct, yet could be simplified. Example the final (void*) is not needed. Further, IMO, it is the wrong approach. Instead, insure stack_head is aligned and adjust size_t s to an align multiple. \$\endgroup\$ – chux - Reinstate Monica Jan 2 '18 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.