orangeduck/tgc

A Tiny Garbage Collector for C

tgc's Issues

Is embedded systems a goal?

I'm curious if you're targeting GC on microcontrollers. 64kb or less of memory, possibly 8-bit, etc.

For example, would you see this run on an AVR, i.e. Arduino? As more and more languages make their way onto MCUs, GC would be a useful addition.

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?

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?

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

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;
  }

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 :

claudio@xubuntu20vm:~/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)
claudio@xubuntu20vm:~/cxx$

many Conditional jump or move depends on uninitialised value(s) on examples

Hi!
I run make check with valgrind checking also for uninitialized values, and I noticed lots of errors.
Is there a reason for that?
I am trying to run the gc on some of my code and I noticed that some values corrupts and I think that the root cause is this.
This is a sample:

==20488== Conditional jump or move depends on uninitialised value(s)
==20488==    at 0x40EA36: tgc_mark_ptr (tgc.c:171)
==20488==    by 0x40EA36: tgc_mark_stack (tgc.c:201)
==20488==    by 0x40E0A1: tgc_mark (tgc.c:230)
==20488==    by 0x40ED77: tgc_run (tgc.c:329)
==20488==    by 0x40ED77: tgc_add (tgc.c:346)
==20488==    by 0x405C8C: mpc_undefined (mpc.c:1688)
==20488==    by 0x405C8C: mpc_new (mpc.c:1696)
==20488==    by 0x40DA75: main_mpc (mpc.c:3979)
==20488==    by 0x400C61: main (mpc.c:4026)
==20488== 
==20488== Use of uninitialised value of size 8
==20488==    at 0x40E9F8: tgc_mark_ptr (tgc.c:172)
==20488==    by 0x40E9F8: tgc_mark_stack (tgc.c:201)
==20488==    by 0x40E0A1: tgc_mark (tgc.c:230)
==20488==    by 0x40ED77: tgc_run (tgc.c:329)
==20488==    by 0x40ED77: tgc_add (tgc.c:346)
==20488==    by 0x405C8C: mpc_undefined (mpc.c:1688)
==20488==    by 0x405C8C: mpc_new (mpc.c:1696)
==20488==    by 0x40DA75: main_mpc (mpc.c:3979)
==20488==    by 0x400C61: main (mpc.c:4026)
==20488== 
==20488== Conditional jump or move depends on uninitialised value(s)
==20488==    at 0x40E9FB: tgc_mark_ptr (tgc.c:172)
==20488==    by 0x40E9FB: tgc_mark_stack (tgc.c:201)
==20488==    by 0x40E0A1: tgc_mark (tgc.c:230)
==20488==    by 0x40ED77: tgc_run (tgc.c:329)
==20488==    by 0x40ED77: tgc_add (tgc.c:346)
==20488==    by 0x405C8C: mpc_undefined (mpc.c:1688)
==20488==    by 0x405C8C: mpc_new (mpc.c:1696)
==20488==    by 0x40DA75: main_mpc (mpc.c:3979)
==20488==    by 0x400C61: main (mpc.c:4026)
==20488== 
==20488== Use of uninitialised value of size 8
==20488==    at 0x40EA70: tgc_mark_ptr (tgc.c:173)
==20488==    by 0x40EA70: tgc_mark_stack (tgc.c:201)
==20488==    by 0x40E0A1: tgc_mark (tgc.c:230)
==20488==    by 0x40ED77: tgc_run (tgc.c:329)
==20488==    by 0x40ED77: tgc_add (tgc.c:346)
==20488==    by 0x405C8C: mpc_undefined (mpc.c:1688)
==20488==    by 0x405C8C: mpc_new (mpc.c:1696)
==20488==    by 0x40DA75: main_mpc (mpc.c:3979)
==20488==    by 0x400C61: main (mpc.c:4026)

Stack Buffer Overflow in `tgc_mark_stack`

I am using tgc in my linked lists, and line 12 of my project causes me issues. This test fails randomly when running the program.

Running the test through --undef-value-errors=no returns no error.

Running the test through Asan returns this, there seems to be a stack buffer overflow in tgc_mark_stack:

=================================================================
==144486==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffff1081db8 at pc 0x00000040377f bp 0x7ffff1081d50 sp 0x7ffff1081d48
READ of size 8 at 0x7ffff1081db8 thread T0
    #0 0x40377e in tgc_mark_stack ../modules/tgc/tgc.c:202
    #1 0x403d8a in tgc_mark ../modules/tgc/tgc.c:231
    #2 0x404fa9 in tgc_run ../modules/tgc/tgc.c:330
    #3 0x40519f in tgc_add ../modules/tgc/tgc.c:347
    #4 0x405573 in tgc_alloc_opt ../modules/tgc/tgc.c:418
    #5 0x4052b9 in tgc_alloc ../modules/tgc/tgc.c:364
    #6 0x4019c4 in list_push ../src/linked_list.c:12
    #7 0x4019a3 in list_make ../src/linked_list.c:7
    #8 0x40132a in main /home/roland/Programming/c/lisp/test/test_linked_list.c:15
    #9 0x7f46c604a50f in __libc_start_call_main (/lib64/libc.so.6+0x2750f)
    #10 0x7f46c604a5c8 in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x275c8)
    #11 0x4011c4 in _start (/home/roland/Programming/c/lisp/test/a.out+0x4011c4)

Address 0x7ffff1081db8 is located in stack of thread T0 at offset 40 in frame
    #0 0x403641 in tgc_mark_stack ../modules/tgc/tgc.c:187

  This frame has 1 object(s):
    [32, 40) 'stk' (line 189) <== Memory access at offset 40 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow ../modules/tgc/tgc.c:202 in tgc_mark_stack
Shadow bytes around the buggy address:
  0x10007e208360: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208370: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208390: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e2083a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007e2083b0: 00 00 f1 f1 f1 f1 00[f3]f3 f3 00 00 00 00 00 00
  0x10007e2083c0: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f1 f1 00 f2
  0x10007e2083d0: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e2083e0: 00 00 00 00 00 00 00 00 00 00 00 f3 f3 f3 f3 f3
  0x10007e2083f0: f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==144486==ABORTING

Is this an issue on my end, or on tgc's end?

Specs:

• Compiler: gcc (GCC) 12.2.1 20221121 (Red Hat 12.2.1-4)
• TGC: f5a4884
• OS: Fedora Linux 37 6.2.7-200.fc37.x86_64
• Build system: cmake version 3.26.0
• Libasan version: 12.2.1

how do i override a pointer to avoid memory leak

e.g

char *  message;
 message = tgc_alloc(&gc, 10); // it allocate
 strcpy(message, "test"); 
 message ="update" // override the value, 

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?

LLVM Support

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?

main(void)

would it be possible to get it to start with main(void)

Consider extracting the repeating codes for finding a pointer in hash table to macro.

I find the code to search the hash table is repeated several times, maybe you can extract it to a macro like:

#define SEARCH_HTABLE(gc, ptr, call_if_not_find, call_when_find)               \
  do {                                                                         \
    size_t i, j, h;                                                            \
    i = tgc_hash(ptr) % gc->nslots; j = 0;                                     \
    while (1) {                                                                \
        h = gc->items[i].hash;                                                 \
        if (h == 0 || j > tgc_probe(gc, i, h)) call_if_not_find                \
        if (gc->items[i].ptr == ptr) call_when_find                            \
        i = (i + 1) % gc->nslots; j++;                                         \
    }                                                                          \
  } while (0)

And use it like:

static void tgc_mark_ptr(tgc_t *gc, void *ptr) {
    if ((uintptr_t)ptr < gc->minptr ||  (uintptr_t)ptr > gc->maxptr) {
        return;
    }

    SEARCH_HTABLE(gc, ptr, { break; }, {
        if (gc->items[i].flags & TGC_MARK) { return; }
        gc->items[i].flags |= TGC_MARK;
        if (gc->items[i].flags & TGC_LEAF) { return; }

        for (size_t k = 0; k < gc->items[i].size / sizeof(void*); k++) {
            tgc_mark_ptr(gc, ((void**)gc->items[i].ptr)[k]);
        }

        return;
    });
}

Although this is kind of ugly... but I think it's better than repeated code.

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

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?

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.

tgc/tgc.c

Line 249 in 3520705

if (gc->frees == NULL) { return; }

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

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?

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);
    }
}

Thank you

Seeing this, I suddenly got a feeling I want to do some C again, which I didn't do in some years. I find this gc awesome, because I like tiny C things, so keep up the good work and thank you for reviving my interest in C.

Have a nice day,

junk in examples/

while certainly of high historic value, the 46 MB .wav file with a JFK speech seems out-of-place, just like the source code of bzip2 and oggencoder.