Show HN: A simple garbage collector for C
github.com
github.com
My (very surface level) understanding was always the trade off for the increased manual effort of using C - manual memory management being one example - was that you could tailor your solution exactly to your usecase for increased performance / lower resource use.
If you're going for a garbage collector, why not also benefit from some of the increased language power/features of a higher level language?
> The original motivation for gc is my desire to write my own LISP in C, entirely from scratch - and that required garbage collection.
Another reason would be in platforms where you cannot run the language of your choice (because lack of implementations of JVM / Python / whatever), although those would maybe not allow malloc either.
"Writing a GC in C" (or equivalent language) is not so much a strange thing as it is an inevitability.
E.g. Python objects are represented as PyObject values in CPython. Saying that Python is garbage collected is equivalent to saying PyObjects are garbage collected. Sure enough, PyObject contains the ref count necessary for its GC.
The Hotspot JVM is a C++ program, CPython is a C program that implements the Python language. Both CPython and Hotspot mostly manage their respective memory in the usual styles of their host languages, but they still need some sort of host language representation for their target language objects.
AIUI, this is less obvious with the JVM (where the runtime manages to avoid a lot of host language allocations), but CPython has an explicit PyObject type, and every target language allocation corresponds to a host level allocation in some way. Because the lifecycle of these allocations in C is inextricably linked to the Python-level objects' lifecycle, you don't explicitly allocate/deallocate those manually on an individual level, you let the GC (Refcount in this case) handle that instead. It just turns out that "letting the GC do it" is really just "letting some other logic in my program do it". This means that implementing the Python GC corresponds exactly to implementing GC for PyObject objects at the C level.
This is what Mono and Golang did. (They both used Boehm until they had time and resources to implement their own runtime-optimized GC.) I suspect Java did too, but I'm not sure.
In this case: "The original motivation for gc is my desire to write my own LISP in C, entirely from scratch - and that required garbage collection."
What basically happens is that gc (and Boehm) are "conservative garbage collectors." They treat all values in a data structure as a potential pointer, because they don't know the contents of the data structure. It's a good "quick and dirty" way to have garbage collection if you can accept the risk that some of your memory will remain uncollected if some of your data happens to have the same value as one of your pointers. In practice, it's a good tradeoff.
(Other tradeoffs are that you can't have things like real-time garbage collection, generational garbage collection, or compacting garbage collection.)
> If you're going for a garbage collector, why not also benefit from some of the increased language power/features of a higher level language?
Ironically, one of Boehm's use cases is looking for memory leaks. You basically #ifdef Boehm into a test build, and if a GC finds garbage, you know that you didn't free something correctly.
So a "garbage checker"? :) This is interesting, I never really thought about using it as a checking tool.
[0] https://web.archive.org/web/20180426195701/http://fdiv.net/2...
The magic is basically:
static inline void defer_cleanup(void (^*b)(void)) { (*b)(); }
#define defer_merge(a,b) a##b
#define defer_varname(a) defer_merge(defer_scopevar_, a)
#define defer __attribute__((cleanup(defer_cleanup))) void (^defer_varname(__COUNTER__))(void) =
FILE *a = fopen ("a.txt", "r");
if (!a)
return EXIT_FAILURE;
defer
{
fclose (a);
};
The original link works.
Regarding its use in the wild, I've encountered it exactly once, in the lastpass-cli (available on github). I personally wouldn't consider using it for one of my projects because it's too nonstandard, however I suppose that for a security-sensitive application it might reduce the likelihood of messing error handling and leaking things all over the place. That being said using non-standard features might also make it more likely for a contributor to misunderstand what the code does precisely and introduce a problem.
#define DEFER(EXPR) for(int _tmp=1; _tmp; _tmp=0,(EXPR))
char * data = malloc(32);
DEFER(free(data))
{
// do stuff
}Most of the challenge in writing code with a single return seems to come from the fact that I'm not used to doing it. Of course, sometimes it leads to heavily nested control flow, although I'm not sure yet whether or not I mind that. It does certainly simplify reasoning about control flow though, especially in large functions.
That all being said, I'd still rather just have defer.
For instance parameter validation is one instance where I think an early return is very much warranted. There you typically have no cleanup to do since it's effectively the prelude of the function.
Regarding nested error handling, I prefer the "goto fail" pattern. Some people are opposed to the use of goto as a matter of principle but I think in this case it's fine. It's effectively the poor man's RAII when you don't have destructors.
That's what the assert statement is for; checking pre- and postconditions.
Alternatively you might be able to use nested functions to guard against a stray return but that's not standard.
static unsigned int __deferDepth = 0;
#define RETURN return
#define return ((__deferDepth == 0) ? RETURN : break do_return)
#define DEFER(EXPR) \
__label__ do_return; \
for(int _tmp = 1; _tmp; _tmp = (do { \
__deferDepth += 1; \
EXPR; \
__deferDepth -= 1; \
break; \
do_return: \
RETURN; \
}while(0);))
Regardless, this isn’t C. Statement expressions (and __label_) are a gcc* extension, and if you’re willing to go there, __attribute__((cleanup)) seems the wiser route.
The implementation is very simple, it's just using a class for its destructor:
template <class F>
class final_act
{
public:
explicit final_act(F f) noexcept : f_(std::move(f)), invoke_(true) {}
final_act(final_act&& other) noexcept : f_(std::move(other.f_)), invoke_(other.invoke_)
{
other.invoke_ = false;
}
final_act(const final_act&) = delete;
final_act& operator=(const final_act&) = delete;
~final_act() noexcept
{
if (invoke_) f_();
}
F f_;
bool invoke_;Source: https://github.com/microsoft/GSL/blob/ebe7ebfd855a95eb937831...
Yep! I really like the defer pattern for those situations :)
You can "emulate" the defer statement with a Scope Guard[0], or if you're willing to use a macro, you can use the __COUNTER__ macro as an "anonymous" variable.
But the really classic way of doing "defer" in C is to do what Linux does:
int foo(void)
{
char *ptr = malloc(13);
int error = 0;
error = bar();
if (error < 0)
goto out_free;
// do something else
out_free:
free(ptr);
return error;
}
> The focus of gc is to provide a conceptually clean implementation of a mark-and-sweep GC, without delving into the depths of architecture-specific optimization (see e.g. the Boehm GC for such an undertaking). It should be particularly suitable for learning purposes and is open for all kinds of optimization (PRs welcome!).