A Tiny Garbage Collector for C

Related tags

Compilers tgc
Overview

Tiny Garbage Collector

About

tgc is a tiny garbage collector for C written in ~500 lines of code and based on the Cello Garbage Collector.

#include "tgc.h"

static tgc_t gc;

static void example_function() {
  char *message = tgc_alloc(&gc, 64);
  strcpy(message, "No More Memory Leaks!");
}

int main(int argc, char **argv) {
  tgc_start(&gc, &argc);
  
  example_function();

  tgc_stop(&gc);
}

Usage

tgc is a conservative, thread local, mark and sweep garbage collector, which supports destructors, and automatically frees memory allocated by tgc_alloc and friends after it becomes unreachable.

A memory allocation is considered reachable by tgc if...

  • a pointer points to it, located on the stack at least one function call deeper than the call to tgc_start, or,
  • a pointer points to it, inside memory allocated by tgc_alloc and friends.

Otherwise a memory allocation is considered unreachable.

Therefore some things that don't qualify an allocation as reachable are, if...

  • a pointer points to an address inside of it, but not at the start of it, or,
  • a pointer points to it from inside the static data segment, or,
  • a pointer points to it from memory allocated by malloc, calloc, realloc or any other non-tgc allocation methods, or,
  • a pointer points to it from a different thread, or,
  • a pointer points to it from any other unreachable location.

Given these conditions, tgc will free memory allocations some time after they become unreachable. To do this it performs an iteration of mark and sweep when tgc_alloc is called and the number of memory allocations exceeds some threshold. It can also be run manually with tgc_run.

Memory allocated by tgc_alloc can be manually freed with tgc_free, and destructors (functions to be run just before memory is freed), can be registered with tgc_set_dtor.

Reference

void tgc_start(tgc_t *gc, void *stk);

Start the garbage collector on the current thread, beginning at the stack location given by the stk variable. Usually this can be found using the address of any local variable, and then the garbage collector will cover all memory at least one function call deeper.


void tgc_stop(tgc_t *gc);

Stop the garbage collector and free its internal memory.


void tgc_run(tgc_t *gc);

Run an iteration of the garbage collector, freeing any unreachable memory.


void tgc_pause(tgc_t *gc);
void tgc_resume(tgc_t *gc);

Pause or resume the garbage collector. While paused the garbage collector will not run during any allocations made.


void *tgc_alloc(gc_t *gc, size_t size);

Allocate memory via the garbage collector to be automatically freed once it becomes unreachable.


void *tgc_calloc(gc_t *gc, size_t num, size_t size);

Allocate memory via the garbage collector and initalise it to zero.


void *tgc_realloc(gc_t *gc, void *ptr, size_t size);

Reallocate memory allocated by the garbage collector.


void tgc_free(gc_t *gc, void *ptr);

Manually free an allocation made by the garbage collector. Runs any destructor if registered.


void *tgc_alloc_opt(tgc_t *gc, size_t size, int flags, void(*dtor)(void*));

Allocate memory via the garbage collector with the given flags and destructor.

For the flags argument, the flag TGC_ROOT may be specified to indicate that the allocation is a garbage collection root and so should not be automatically freed and instead will be manually freed by the user with tgc_free. Because roots are not automatically freed, they can exist in normally unreachable locations such as in the static data segment or in memory allocated by malloc.

The flag TGC_LEAF may be specified to indicate that the allocation is a garbage collection leaf and so contains no pointers to other allocations inside. This can benefit performance in many cases. For example, when allocating a large string there is no point the garbage collector scanning this allocation - it can take a long time and doesn't contain any pointers.

Otherwise the flags argument can be set to zero.

The dtor argument lets the user specify a destructor function to be run just before the memory is freed. Destructors have many uses, for example they are often used to automatically release system resources (such as file handles) when a data structure is finished with them. For no destructor the value NULL can be used.


void *tgc_calloc_opt(tgc_t *gc, size_t num, size_t size, int flags, void(*dtor)(void*));

Allocate memory via the garbage collector with the given flags and destructor and initalise to zero.


void tgc_set_dtor(tgc_t *gc, void *ptr, void(*dtor)(void*));

Register a destructor function to be called after the memory allocation ptr becomes unreachable, and just before it is freed by the garbage collector.


void tgc_set_flags(tgc_t *gc, void *ptr, int flags);

Set the flags associated with a memory allocation, for example the value TGC_ROOT can be used to specify that an allocation is a garbage collection root.


int tgc_get_flags(tgc_t *gc, void *ptr);

Get the flags associated with a memory allocation.


void(*tgc_get_dtor(tgc_t *gc, void *ptr))(void*);

Get the destructor associated with a memory allocation.


size_t tgc_get_size(tgc_t *gc, void *ptr);

Get the size of a memory allocation.

F.A.Q

Is this real/safe/portable?

Definitely! While there is no way to create a completely safe/portable garbage collector in C this collector doesn't use any platform specific tricks and only makes the most basic assumptions about the platform, such as that the architecture using a continuous call stack to implement function frames.

It should be safe to use for more or less all reasonable architectures found in the wild and has been tested on Linux, Windows, and OSX, where it was easily integrated into several large real world programs (see examples) such as bzip2 and oggenc without issue.

Saying all of that, there are the normal warnings - this library performs undefined behaviour as specified by the C standard and so you use it at your own risk - there is no guarantee that something like a compiler or OS update wont mysteriously break it.

What happens when some data just happens to look like a pointer?

In this unlikely case tgc will treat the data as a pointer and assume that the memory allocation it points to is still reachable. If this is causing your application trouble by not allowing a large memory allocation to be freed consider freeing it manually with tgc_free.

tgc isn't working when I increment pointers!

Due to the way tgc works, it always needs a pointer to the start of each memory allocation to be reachable. This can break algorithms such as the following, which work by incrementing a pointer.

void bad_function(char *y) {
  char *x = tgc_alloc(&gc, strlen(y) + 1);
  strcpy(x, y);
  while (*x) {
    do_some_processsing(x);
    x++;
  }
}

Here, when x is incremented, it no longer points to the start of the memory allocation made by tgc_alloc. Then during do_some_processing, if a sweep is performed, x will be declared as unreachable and the memory freed.

If the pointer x is also stored elsewhere such as inside a heap structure there is no issue with incrementing a copy of it - so most of the time you don't need to worry, but occasionally you may need to adjust algorithms which do significant pointer arithmetic. For example, in this case the pointer can be left as-is and an integer used to index it instead:

void good_function(char *y) {
  int i;
  char *x = tgc_alloc(&gc, strlen(y) + 1);
  strcpy(x, y);
  for (i = 0; i < strlen(x); i++) {
    do_some_processsing(&x[i]);
  }
}

For now this is the behaviour of tgc until I think of a way to deal with offset pointers nicely.

tgc isn't working when optimisations are enabled!

Variables are only considered reachable if they are one function call shallower than the call to tgc_start. If optimisations are enabled somtimes the compiler will inline functions which removes this one level of indirection.

The most portable way to get compilers not to inline functions is to call them through volatile function pointers.

static tgc_t gc;

void please_dont_inline(void) {
  ...
}

int main(int argc, char **argv) {
  
  tgc_start(&gc, &argc);

  void (*volatile func)(void) = please_dont_inline;
  func();
  
  tgc_stop(&gc);

  return 1;
}

tgc isn't working with setjmp and longjmp!

Unfortunately tgc doesn't work properly with setjmp and longjmp since these functions can cause complex stack behaviour. One simple option is to disable the garbage collector while using these functions and to re-enable it afterwards.

Why do I get uninitialised values warnings with Valgrind?

The garbage collector scans the stack memory and this naturally contains uninitialised values. It scans memory safely, but if you are running through Valgrind these accesses will be reported as warnings/errors. Other than this tgc shouldn't have any memory errors in Valgrind, so the easiest way to disable these to examine any real problems is to run Valgrind with the option --undef-value-errors=no.

Is tgc fast?

At the moment tgc has decent performance - it is competative with many existing memory management systems - but definitely can't claim to be the fastest garbage collector on the market. Saying that, there is a fair amount of low hanging fruit for anyone interested in optimising it - so some potential to be faster exists.

How it Works

For a basic mark and sweep garbage collector two things are required. The first thing is a list of all of the allocations made by the program. The second is a list of all the allocations in use by the program at any given time. With these two things the algorithm is simple - compare the two lists and free any allocations which are in the first list, but not in the second - exactly those allocations which are no longer in use.

To get a list of all the allocations made by the progam is relatively simple. We make the programmer use a special function we've prepared (in this case tgc_alloc) which allocates memory, and then adds a pointer to that memory to an internal list. If at any point this allocation is freed (such as by tgc_free), it is removed from the list.

The second list is the difficult one - the list of allocations in use by the program. At first, with C's semantics, pointer arithematic, and all the crazy flexibility that comes with it, it might seem like finding all the allocations in use by the program at any point in time is impossible, and to some extent you'd be right. It can actually be shown that this problem reduces to the halting problem in the most general case - even for languages saner than C - but by slightly adjusting our problem statement, and assuming we are only dealing with a set of well behaved C programs of some form, we can come up with something that works.

First we have to relax our goal a little. Instead of trying to find all of the memory allocations in use by a program, we can instead try to find all the reachable memory allocations - those allocations which have a pointer pointing to them somewhere in the program's memory. The distinction here is subtle but important. For example, I could write a C program which makes an allocation, encodes the returned pointer as a string, and performs rot13 on that string, later on decoding the string, casting it back to a pointer, and using the memory as if nothing had happened. This is a perfectly valid, C program, and the crazy memory allocation is is use throughout. It is just that during the pointer's rot13 encoding there is no practical way to know that this memory allocation is still going to be used later on.

So instead we want to make a list of all memory allocations which are pointed to by pointers in the program's memory. For most well behaved C programs this is enough to tell if an allocation is in use.

In general, memory in C exists in three different segments. We have the stack, the heap, and the data segment. This means - if a pointer to a certain allocation exists in the program's memory it must be in one of these locations. Now the challenge is to find these locations, and scan them for pointers.

The data segment is the most difficult - there is no portable way to get the bounds of this segment. But because the data segment is somewhat limited in use we can choose to ignore it - we tell users that allocations only pointed to from the data segment are not considered reachable.

As an aside, for programmers coming from other languages, this might seem like a poor solution - to simply ask the programmer not to store pointers to allocations in this segment - and in many ways it is. It is never a good interface to request the programmer do something in the documentation - instead it is better to handle every edge case to make it impossible for them to create an error. But this is C - in C programmers are constantly asked not to do things which are perfectly possible. In fact - one of the very things this library is trying to deal with is the fact that programmers are only asked to make sure they free dynamically allocated memory - there is no system in place to enforce this. So for C this is a perfectly reasonable interface. And there is an added advantage - it makes the implementation far more simple - far more adaptable. In other words - Worse Is Better.

With the data segment covered we have the heap and the stack. If we consider only the heap allocations which have been made via tgc_alloc and friends then our job is again made easy - in our list of all allocations we also store the size of each allocation. Then, if we need to scan one of the memory regions we've allocated, the task is made easy.

With the heap and the data segment covered, this leaves us with the stack - this is the most tricky segment. The stack is something we don't have any control over, but we do know that for most reasonable implementations of C, the stack is a continuous area of memory that is expanded downwards (or for some implementations upwards, but it doesn't matter) for each function call. It contains the most important memory in regards to reachability - all of the local variables used in functions.

If we can get the memory addresses of the top and the bottom of the stack we can scan the memory inbetween as if it were heap memory, and add to our list of reachable pointers all those found inbetween.

Assuming the stack grows from top to bottom we can get a conservative approximation of the bottom of the stack by just taking the address of some local variable.

void *stack_bottom(void) {
  int x;
  return &x;
}

This address should cover the memory of all the local variables for whichever function calls it. For this reason we need to ensure two things before we actually do call it. First we want to make sure we flush all of the values in the registers onto the stack so that we don't miss a pointer hiding in a register, and secondly we want to make sure the call to stack_bottom isn't inlined by the compiler.

We can spill the registers into stack memory in a somewhat portable way with setjmp - which puts the registers into a jmp_buf variable. And we can ensure that the function is not inlined by only calling it via a volatile function pointer. The volatile keyword forces the compiler to always manually read the pointer value from memory before calling the function, ensuring it cannot be inlined.

void *get_stack_bottom(void) {
  jmt_buf env;
  setjmp(env);
  void *(*volatile f)(void) = stack_bottom;
  return f();
}

To get the top of the stack we can again get the address of a local variable. This time it is easier if we simply ask the programmer to supply us with one. If the programmer wishes for the garbage collector to scan the whole stack he can give the address of a local variable in main. This address should cover all function calls one deeper than main. This we can store in some global (or local) variable.

static void *stack_top = NULL;

int main(int argc, char **argv) {
  stack_top = &argc;
  run_program(argc, argv);
  return 1;
}

Now, at any point we can get a safe approximate upper and lower bound of the stack memory, allowing us to scan it for pointers. We interprit each bound as a void ** - a pointer to an array of pointers, and iterate, interpriting the memory inbetween as pointers.

void mark(void) {
  void **p;
  void **t = stack_top;
  void **b = get_stack_bottom();
  
  for (p = t; p < b; p++) {
    scan(*p);
  }
}
Issues
  • fix valgrind : Conditional jump or move depends on uninitialised

    fix valgrind : Conditional jump or move depends on uninitialised

    fix valgrind : Conditional jump or move depends on uninitialised

    [email protected]:~/tgc$ valgrind ./x
    ==3675== Memcheck, a memory error detector
    ==3675== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
    ==3675== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
    ==3675== Command: ./x
    ==3675== 
    ==3675== 
    ==3675== HEAP SUMMARY:
    ==3675==     in use at exit: 0 bytes in 0 blocks
    ==3675==   total heap usage: 4 allocs, 4 frees, 1,304 bytes allocated
    ==3675== 
    ==3675== All heap blocks were freed -- no leaks are possible
    ==3675== 
    ==3675== For lists of detected and suppressed errors, rerun with: -s
    ==3675== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
    
    opened by ClaudioDaffra 3
  • Stack iteration in tgc.c

    Stack iteration in tgc.c

    Hi! Firstly, thank you for doing this! I'm a student trying to learn how to implement a garbage collector and reading your code has a great way to learn!

    I have a question on how you go about traversing the gc roots in these lines. In the for loop, why do you update pointer p by doing p = ((char*)p) - sizeof(void*) instead of something like p = ((char*)p) - sizeof(char)?

    Perhaps my understanding of stack allocated variables is wrong, but why can you move the pointer 8 bytes down the stack instead of 1 byte? Why does this not cause you to overshoot pointing to the desired pointer value in some cases?

    opened by marcusblake 3
  • Tgc crashes when mallocing in a loop

    Tgc crashes when mallocing in a loop

    #include "tgc.c"
    
    void tgc_start2(tgc_t *gc) {
      void * stk;
      gc->bottom = &stk;
      gc->paused = 0;
      gc->nitems = 0;
      gc->nslots = 0;
      gc->mitems = 0;
      gc->nfrees = 0;
      gc->maxptr = 0;
      gc->items = NULL;
      gc->frees = NULL;
      gc->minptr = UINTPTR_MAX;
      gc->loadfactor = 0.9;
      gc->sweepfactor = 0.5;
    }
    #include <stdio.h>
    tgc_t Garbage_Collector_Program;
    
    static void Garbage_Collector_Dump_Mem(FILE *fp) { /*return tgc_dump(&Garbage_Collector_Program, fp); */}
    #define Garbage_Collector_Start() tgc_start2(&Garbage_Collector_Program)
    #define Garbage_Collector_Cleanup() tgc_run(&Garbage_Collector_Program)
    #define Garbage_Collector_Pause() tgc_pause(&Garbage_Collector_Program)
    #define Garbage_Collector_Resume() tgc_resume(&Garbage_Collector_Program)
    #define Garbage_Collector_Shutdown() tgc_stop(&Garbage_Collector_Program)
    
    #define malloc(size)  tgc_alloc(&Garbage_Collector_Program, size)
    #define calloc(num, size)  tgc_calloc(&Garbage_Collector_Program, num, size)
    #define realloc(ptr, size) tgc_realloc(&Garbage_Collector_Program, ptr, size)
    #define free(ptr)    tgc_free(&Garbage_Collector_Program, ptr)
    
    int main()
    {
    	printf("\ntest 1: shutdown and start up\n");
    	Garbage_Collector_Start();
    	Garbage_Collector_Shutdown();
    	Garbage_Collector_Start();
    	Garbage_Collector_Shutdown();
    	Garbage_Collector_Start();
    	printf("\ntest 2: malloc an area of 1, 10 times and clean up\n");
    	for (int i = 0, i < 1, i++) {
    		malloc(1); // seems to cause the program to crash and abort the compilation, even if done indirectly
    	}
    	Garbage_Collector_Shutdown();
    	Garbage_Collector_Start();
    	//Garbage_Collector_Cleanup();
    	/*
    	printf("\ntest 3: clean up on segfault\n");
    	printf("testing garbage collector and seg fault handler\n");
    	char * a = malloc(1);
    	a = realloc(a,2);
    	Garbage_Collector_Dump_Mem(a);
    	Garbage_Collector_Shutdown();
    	*/
    	return 0;
    }
    

    when attempting to compile with Mobile C (IOS APP) it crashes but does not happen normally if the tgc is not included or if malloc is outside of the for loop

    opened by mgood7123 3
  • But in tgc_mark with TGC_ROOT pointer?

    But in tgc_mark with TGC_ROOT pointer?

    First of all: thanks for sharing you GC. It is one of the easiest-but-functional ones around!

    I think this is a bug, but maybe I am not understanding the code correctly? The tgc_mark function contains this for loop:

      for (i = 0; i < gc->nslots; i++) {
        if (gc->items[i].hash ==        0) { continue; }
        if (gc->items[i].flags & TGC_MARK) { continue; }
        if (gc->items[i].flags & TGC_ROOT) {
          gc->items[i].flags |= TGC_MARK;
          if (gc->items[i].flags & TGC_LEAF) { return; }
          for (k = 0; k < gc->items[i].size/sizeof(void*); k++) {
            tgc_mark_ptr(gc, ((void**)gc->items[i].ptr)[k]);
          }
          return;
        }
      }
    

    Why does it always exit the function when the first TGC_ROOT pointer is encountered? This prevents marking other pointers and marking the stack later on. Shouldn't those two return statements be continue statements instead?

    opened by erikvanbilsen 3
  • Conditional jump or move depends on uninitialised value(s)

    Conditional jump or move depends on uninitialised value(s)

    // example conditional jump error

    #include "../lib/tgc.h"
    
    static tgc_t gc;
    
    static void example_function() {
      void *memory = tgc_alloc(&gc, 1024);
    }
    
    int main(int argc, char **argv) {
      
      tgc_start(&gc, &argc);
    
      example_function();
      
      tgc_stop(&gc);
      
      return 0;
    }
    

    valgrind error :

    [email protected]:~/cxx$ valgrind ./x
    ==2891== Memcheck, a memory error detector
    ==2891== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
    ==2891== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
    ==2891== Command: ./x
    ==2891== 
    ==2891== Conditional jump or move depends on uninitialised value(s)
    ==2891==    at 0x109BF5: tgc_mark_ptr (in /home/claudio/cxx/x)
    ==2891==    by 0x109E9A: tgc_mark_stack (in /home/claudio/cxx/x)
    ==2891==    by 0x10A12B: tgc_mark (in /home/claudio/cxx/x)
    ==2891==    by 0x10A863: tgc_run (in /home/claudio/cxx/x)
    ==2891==    by 0x10A948: tgc_add (in /home/claudio/cxx/x)
    ==2891==    by 0x10AC18: tgc_alloc_opt (in /home/claudio/cxx/x)
    ==2891==    by 0x10A9FB: tgc_alloc (in /home/claudio/cxx/x)
    ==2891==    by 0x10ADFB: example_function (in /home/claudio/cxx/x)
    ==2891==    by 0x10AE32: main (in /home/claudio/cxx/x)
    ==2891== 
    ==2891== Conditional jump or move depends on uninitialised value(s)
    ==2891==    at 0x109BF5: tgc_mark_ptr (in /home/claudio/cxx/x)
    ==2891==    by 0x109D94: tgc_mark_ptr (in /home/claudio/cxx/x)
    ==2891==    by 0x109E9A: tgc_mark_stack (in /home/claudio/cxx/x)
    ==2891==    by 0x10A12B: tgc_mark (in /home/claudio/cxx/x)
    ==2891==    by 0x10A863: tgc_run (in /home/claudio/cxx/x)
    ==2891==    by 0x10A948: tgc_add (in /home/claudio/cxx/x)
    ==2891==    by 0x10AC18: tgc_alloc_opt (in /home/claudio/cxx/x)
    ==2891==    by 0x10A9FB: tgc_alloc (in /home/claudio/cxx/x)
    ==2891==    by 0x10ADFB: example_function (in /home/claudio/cxx/x)
    ==2891==    by 0x10AE32: main (in /home/claudio/cxx/x)
    ==2891== 
    ==2891== Conditional jump or move depends on uninitialised value(s)
    ==2891==    at 0x109C0A: tgc_mark_ptr (in /home/claudio/cxx/x)
    ==2891==    by 0x109E9A: tgc_mark_stack (in /home/claudio/cxx/x)
    ==2891==    by 0x10A12B: tgc_mark (in /home/claudio/cxx/x)
    ==2891==    by 0x10A863: tgc_run (in /home/claudio/cxx/x)
    ==2891==    by 0x10A948: tgc_add (in /home/claudio/cxx/x)
    ==2891==    by 0x10AC18: tgc_alloc_opt (in /home/claudio/cxx/x)
    ==2891==    by 0x10A9FB: tgc_alloc (in /home/claudio/cxx/x)
    ==2891==    by 0x10ADFB: example_function (in /home/claudio/cxx/x)
    ==2891==    by 0x10AE32: main (in /home/claudio/cxx/x)
    ==2891== 
    ==2891== 
    ==2891== HEAP SUMMARY:
    ==2891==     in use at exit: 0 bytes in 0 blocks
    ==2891==   total heap usage: 5 allocs, 5 frees, 1,304 bytes allocated
    ==2891== 
    ==2891== All heap blocks were freed -- no leaks are possible
    ==2891== 
    ==2891== Use --track-origins=yes to see where uninitialised values come from
    ==2891== For lists of detected and suppressed errors, rerun with: -s
    ==2891== ERROR SUMMARY: 142 errors from 3 contexts (suppressed: 0 from 0)
    [email protected]:~/cxx$
    
    opened by ClaudioDaffra 2
  • What if `p->dtor` is `NULL` in `tgc_free`?

    What if `p->dtor` is `NULL` in `tgc_free`?

    I think the logic of tgc_free should changed to:

    void tgc_free(tgc_t *gc, void *ptr) {
        tgc_ptr_t *p  = tgc_get_ptr(gc, ptr);
        if (p) {
            if (p->dtor) {
                p->dtor(ptr);
            }
            free(ptr);
            tgc_rem(gc, ptr);
        }
    }
    
    opened by loggerhead 2
  • Need free the old memory if realloc failed.

    Need free the old memory if realloc failed.

    The old memory should freed in tgc_realloc because:

    For realloc(), the input pointer is still valid if reallocation failed.

      void *qtr = realloc(ptr, size);
    
      if (qtr == NULL) {
        // free(ptr);
        tgc_rem(gc, ptr);
        return qtr;
      }
    
    opened by loggerhead 2
  • Make free accept a const pointer

    Make free accept a const pointer

    Don't repeat the mistakes the standard library did, make free accept a const pointer, that the caller never has to cast their pointers.

    Rationale by Linus Torvalds why free (or in his case kfree) should accept const pointers: http://yarchive.net/comp/const.html

    opened by Leandros 2
  • Infinite loop in tgc_mark_stack

    Infinite loop in tgc_mark_stack

    Hi,

    I tried to adapt tgc for compilation under cc65. This C compiler doesn't support floats, so all I really did was "convert" all ops involving floats to properly scaled divisions or numbers - this part shouldn't be a problem (I guess...)

    The problem is that inside the first tgc_alloc the control reaches tgc_mark_stack, where it is stuck inside this loop forever:

    if (bot < top) { for (p = top; p >= bot; p = ((char*)p) - sizeof(void*)) { tgc_mark_ptr(gc, ((void*)p)); } }

    Could it be due to 8-bit architecture of the platform or rather anything I've messed up?

    opened by ssuukk 1
  • Could you please add more comments in the source so that this repo can be a material for studying?

    Could you please add more comments in the source so that this repo can be a material for studying?

    I currently have some trouble putting all the things together while reading the implementation. Could you please add documentation about the functionality and the meaning of arguments of static functions in tgc.c?

    opened by tjysdsg 1
  • How to deal with situations where setjmp/longjmp is used

    How to deal with situations where setjmp/longjmp is used

    Recently I've come into this access violation problem when I'm using tgc in combination with Bison, that when I free the internal state, it just tells me I cannot double-free a string while it is not in the root set nor was it in the freed set...

    It seems like the GLR parser uses setjmp to revert to another state for parallel scanning, and so the stack order is completely scrambled, the stack address is not guaranteed under this situation, am I right about this?

    opened by stevefan1999-personal 1
  • Sweep not work correctly on ESP8266

    Sweep not work correctly on ESP8266

    Thanks for this tiny GC implementation that I can use as an example in my book about implementing a mruby virtual machine.

    For the demo of my example, I run it on my macOS and ESP8266 chip. But the tgc_sweep never runs because the gc->nfrees always be 0 in ESP8266.

    The patch has removed this line to force it run sweep event nothing to be free. https://github.com/orangeduck/tgc/blob/35207051557c79ea25942c021fb18856c72af8e3/tgc.c#L249

    Does anyone have any idea about the root cause to let the GC never work?

    opened by elct9620 6
  • Problems with C++ virtual destructor

    Problems with C++ virtual destructor

    So I'm trying to exploit tgc for C++ automatic GC dream:

    class object {
    	public: object();
    	public: virtual ~object() {}
    };
    void* __cdecl operator new(unsigned int size) throw(std::bad_alloc) {
    	tgc_run(&gc);
    	return tgc_alloc(&gc, size);
    }
    
    void* __cdecl operator new[](unsigned int size) throw(std::bad_alloc)  {
    	tgc_run(&gc);
    	return tgc_calloc(&gc, 1, size);
    }
    
    void __cdecl operator delete(void *mem) throw()  {
    	tgc_run(&gc);
    	return tgc_free(&gc, ptr);
    }
    
    object::object() {
    	auto dtor = (void(*)(void*))**(void***)this;
    	tgc_set_dtor(&gc, this, dtor);
    }
    

    The dtor is virtualized. However, when the program is sweeping and deleting the object, the dtor was not able to be called, and instead a segfault occurred. Can someone figure out what's happening?

    opened by cia48621793 3
Owner
Daniel Holden
Animation Researcher at Ubisoft Montreal. Writer / Programmer.
Daniel Holden
C implementation of the Tiny BASIC compiler found in an article by Dr. Austin Henley

Teeny Tiny Basic A C implementation of the Tiny BASIC compiler found in this article and this github repo by Dr. Austin Henley. I did pretty well in A

Gavin Morris 5 Jun 12, 2022
A Tiny Garbage Collector for C

tgc is a tiny garbage collector for C written in ~500 lines of code and based on the Cello Garbage Collector.

Daniel Holden 695 Jun 22, 2022
The Boehm-Demers-Weiser conservative C/C++ Garbage Collector (libgc, bdwgc, boehm-gc)

Boehm-Demers-Weiser Garbage Collector This is version 8.1.0 (next release development) of a conservative garbage collector for C and C++. Download You

Ivan Maidanski 2k Jun 22, 2022
A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

A easy to use multithreading thread pool library for C. It is a handy stream-like job scheduler with an automatic garbage collector for non I/O bound computation.

Hyoung Min Suh 12 Jun 4, 2022
nanoc is a tiny subset of C and a tiny compiler that targets 32-bit x86 machines.

nanoc is a tiny subset of C and a tiny compiler that targets 32-bit x86 machines. Tiny? The only types are: int (32-bit signed integer) char (8-

Ajay Tatachar 16 Feb 13, 2022
Header-only, event based, tiny and easy to use libuv wrapper in modern C++ - now available as also shared/static library!

Do you have a question that doesn't require you to open an issue? Join the gitter channel. If you use uvw and you want to say thanks or support the pr

Michele Caini 1.5k Jun 24, 2022
Yocto/GL: Tiny C++ Libraries for Data-Driven Physically-based Graphics

Yocto/GL: Tiny C++ Libraries for Data-Oriented Physically-based Graphics Yocto/GL is a collection of small C++17 libraries for building physically-bas

Fabio Pellacini 2.3k Jun 26, 2022
Tiny ISO-compliant C++ EXIF and XMP parsing library for JPEG.

TinyEXIF: Tiny ISO-compliant C++ EXIF and XMP parsing library for JPEG Introduction TinyEXIF is a tiny, lightweight C++ library for parsing the metada

cDc 76 May 27, 2022
A tiny JSON library for C++11.

json11 json11 is a tiny JSON library for C++11, providing JSON parsing and serialization. The core object provided by the library is json11::Json. A J

Dropbox 2.3k Jun 22, 2022
tiny recursive descent expression parser, compiler, and evaluation engine for math expressions

TinyExpr TinyExpr is a very small recursive descent parser and evaluation engine for math expressions. It's handy when you want to add the ability to

Lewis Van Winkle 1.1k Jun 24, 2022
tiny HTTP parser written in C (used in HTTP::Parser::XS et al.)

PicoHTTPParser Copyright (c) 2009-2014 Kazuho Oku, Tokuhiro Matsuno, Daisuke Murase, Shigeo Mitsunari PicoHTTPParser is a tiny, primitive, fast HTTP r

H2O 1.5k Jun 22, 2022
Tiny XML library.

Mini-XML Version 3.2 Mini-XML is a small XML parsing library that you can use to read XML data files or strings in your application without requiring

Michael R Sweet 335 Jun 28, 2022
tiny recursive descent expression parser, compiler, and evaluation engine for math expressions

TinyExpr TinyExpr is a very small recursive descent parser and evaluation engine for math expressions. It's handy when you want to add the ability to

Lewis Van Winkle 1.1k Jun 24, 2022
JoyfulNoise Tiny Utility Board

JoyfulNoise Tiny Utility Board A versatile ATtiny85-powered Eurorack module in 4HP. License JoyfulNoise hardware and software is Open Source. The JNTU

Ben Reeves 21 Mar 31, 2022
Minimal Linux Live (MLL) is a tiny educational Linux distribution, which is designed to be built from scratch by using a collection of automated shell scripts. Minimal Linux Live offers a core environment with just the Linux kernel, GNU C library, and Busybox userland utilities.

Minimal Linux Live (MLL) is a tiny educational Linux distribution, which is designed to be built from scratch by using a collection of automated shell scripts. Minimal Linux Live offers a core environment with just the Linux kernel, GNU C library, and Busybox userland utilities.

John Davidson 1.3k Jun 20, 2022
Pipy is a tiny, high performance, highly stable, programmable proxy.

Pipy Pipy is a tiny, high performance, highly stable, programmable proxy. Written in C++, built on top of Asio asynchronous I/O library, Pipy is extre

null 454 Jun 24, 2022
Training and fine-tuning YOLOv4 Tiny on custom object detection dataset for Taiwanese traffic

Object Detection on Taiwanese Traffic using YOLOv4 Tiny Exploration of YOLOv4 Tiny on custom Taiwanese traffic dataset Trained and tested AlexeyAB's D

Andrew Chen 3 Mar 7, 2022
YOLOV4 tiny + lane detection on Android with 8 FPS!

YOLOV4 Tiny + Ultra fast lane detection on Android with 8 FPS! Tested with HONOR 20PRO Kirin 980

yq-pan 12 May 11, 2022
tiny game made in ~15 hours on stream

A small game made entirely on live stream over about 15 hours. I intend to add more documentation and clarify some of the code and assets over the next few days.

Noel Berry 171 Jun 19, 2022
TIC-80 is a fantasy computer for making, playing and sharing tiny games.

TIC-80 is a fantasy computer for making, playing and sharing tiny games.

Vadim Grigoruk 3.5k Jun 27, 2022
In this tutorial, we will use machine learning to build a gesture recognition system that runs on a tiny microcontroller, the RP2040.

Pico-Motion-Recognition This Repository has the code used on the 2 parts tutorial TinyML - Motion Recognition Using Raspberry Pi Pico The first part i

Marcelo Rovai 16 Jun 18, 2022
Elk is a tiny embeddable JavaScript engine that implements a small but usable subset of ES6

Elk is a tiny embeddable JavaScript engine that implements a small but usable subset of ES6. It is designed for microcontroller development. Instead of writing firmware code in C/C++, Elk allows to develop in JavaScript. Another use case is providing customers with a secure, protected scripting environment for product customisation.

Cesanta Software 1.4k Jun 27, 2022
QtLottie is a tiny C++ library that can render Adobe® After Effects™ animations exported as JSON with Bodymovin.

QtLottie QtLottie is a tiny C++ library that can render Adobe® After Effects™ animations exported as JSON with Bodymovin. Features Support many After

Yuhang Zhao 28 Jun 23, 2022
Tiny CUDA Neural Networks

This is a small, self-contained framework for training and querying neural networks. Most notably, it contains a lightning fast "fully fused" multi-layer perceptron as well as support for various advanced input encodings, losses, and optimizers.

NVIDIA Research Projects 1.4k Jun 22, 2022
Pipy is a tiny, high performance, highly stable, programmable proxy written in C++

Pipy is a tiny, high performance, highly stable, programmable proxy. Written in C++, built on top of Asio asynchronous I/O library, Pipy is extremely lightweight and fast, making it one of the best choices for service mesh sidecars.

null 454 Jun 24, 2022
Tiny FEL tools for allwinner SOC, support RISC-V D1 chip

XFEL Tiny FEL tools for allwinner SOC, support RISC-V D1 chip. How to build The xfel tools depends on the libusb-1.0 library, you need to install libu

xboot.org 100 Jun 21, 2022
A tiny example how to work with ZigBee stack using JN5169 microcontroller

Hello NXP JN5169 ZigBee World This is a tiny example how to work with ZigBee stack using JN5169 microcontroller. The example implements a smart switch

Oleksandr Masliuchenko 18 Feb 13, 2022
A tiny external monitor for PC using STM32 and ST7789. Connects to PC over USB and displays the captured screen on ST7789 (240x240) display.

STM32 Tiny Monitor A super tiny monitor for your PC, suitable for your pet ant. A python script sends the captured screen over USB to the STM32 microc

Avra Mitra 60 May 10, 2022
Tiny weather station based on TTGO T5 V2.3.1 (ESP32 with 2.13

Tiny weather station based on TTGO T5 V2.3.1 (ESP32 with 2.13" e-ink display) Features wireless and rechargable weather description including temperat

Piotr Kubica 17 Apr 3, 2022