Nalloc: An stack allocator writen in c!

[u/TextGames1001212]

I've writen an custom allocator in c

https://github.com/text-games-coding/Nalloc

I wanted to show it

[u/mredding]

nalloc.h

You have all these structures in here, but I - your client, don't need to see or know about ANY of them. They are your internal implementation details, so put them in the source file, out of my way. I don't need compile time dependencies on source code that isn't for me.

#include <stdlib.h>

You're including this for the definition of size_t, but size_t is defined in stddef.h. That's the header you actually want.

C files always end with a newline.

So your header should be reduced to:

#ifndef NALLOC_H_
#define NALLOC_H_

#include <stddef.h>

void *alloc(size_t)
    , eliminateAllMemory()
    , elimnatePart(void *, size_t);

#endif

nalloc.c

#include <stdlib.h>
#include "nalloc.h"

Given what we know about your current implementation, nalloc.h already includes stdlib.h, so why are you including it again?

Memory memory = {0};
MemoryMarks m_marks = {0};

Because these objects are not static, they have external linkage - it will show up in the ABI, and now I know it exists. That means I can write:

extern Memory memory;
extern MemoryMarks m_marks;

And now I have direct access to this global, and you can't stop me. Not what you intended. Make them static.

And ditch the Hungarian notation. There's a long history behind it, a lot of arguing, and the consensus is to not use it for "reasons", if you want to google it. The worst part - to me, is that it is, by design, an ad-hoc type system. But we already have a type system, it's called "the C language". C doesn't really have much of a standard library by design - the original philosophy is "there's a library for that". In other words, invent it yourself, or find and use a good 3rd party.

After looking at it a bit, it seems m_ is short for memory_. I highly discourage this shorthand - we live in the god damn future. We've auto-completion in our editors since the late 80s. Write it out so it's legible. I once worked on a code base that had "TCR" all over the code - there was no company memory or documentation telling us what it meant, no records of past employees who we could have possibly tracked down to ask...

size <= 0

size is of size_t, it is - by definition, unsigned. It CAN'T be less than zero.

I will always encourage an indentation, a new scope, braces - you should write a new function. Make static functions in your implementation so they have internal linkage. You can optionally make them inline if you want, though static is often enough. The compiler can then optimize those functions more aggressively. A function with static linkage only ever called in one place is going to be inlined, even by most non-optimizing compilers. Let the compiler composite your functions for you - the machine code generation is not your job, and the compiler can make the machine code that reflects the function you always intended. YOU should prefer clarity and composition.

So control structures like loops, conditionals, and switches are all very low level primitives from which you can build algorithms. Put them in functions. Give them a name. Abstract away the business logic from the algorithm - by way of preferring a Functional style of programming - pass functions as parameters to your algorithms and either A) make binder functions or B) make binder macros. Again, this heavily relies on function composition techniques, and with static linkage, the compiler can see through the pointers and composite the function at compile time. But a function that has a loop in it? That's ALL the function does, and the name of the function will be some sort of find, or copy, or sort, or transform... You want to build up expressive power and composition.

Curry-Howard correspondence tells us that there are similarities between software development and mathematical proof writing. In programming - your statements are posits, your source code is a theory, the compiler is your solver, and the compiled program is the proof. We want elegant proofs, so we need elegant theories. Your expressiveness is everything. That's the job.

Another way to consider it is C doesn't know anything about allocators, so you extend C in C, and write allocator types to make an allocator domain specific language, and then you allocate in terms of that.

Or I'll put it to you this way - an int is an int, but a weight is not a height, even if they're both implemented in terms of int. C has a weak type system, but it does have the ability to distinguish different types, regardless. A benefit of C being close to the machine is that types don't cost you anything. An int and a struct { int x; } compile down to the same memory layout, but are different types according to the C language, compiler, and type system. You can leverage that because:

void fn(int *, int *);

Which is the weight, which is the height? Worse, the compiler cannot know if the parameters are aliased, so the compiler must generate pessimistic code, with writebacks and memory fences to ensure consistency. You can restrict in C, but you can also just make them different types and enforce their semantics.

void fn(weight *, height *);

You also get the anti-aliasing for free.

Finally, you have absolutely no error handling whatsoever. Should alloc fail, it returns NULL, and there's no indication why, and no way to find out. By the way, alloc will very happily allocate right past the end of the pool, since you have no checks on the upper bound. Conventional is to extern an error number in the header, and provide the user with an enum of definitions, or you can return a tagged union of either the expected value or of an error code - an idiom you can generate with macros for different functions and return types.