Writing a Simple Garbage Collector in C
maplant.com
Writing a Simple Garbage Collector in C
1–10 of 24 posts
Re: Writing a Simple Garbage Collector in C
#2Would love to see a Windows-based version of this article. No sbrk() or mmap() in Windows makes the implementation a bit different.
Re: Writing a Simple Garbage Collector in C
#3Would love to see a Windows-based version of this article. No sbrk() or mmap() in Windows makes the implementation a bit different.
Windows has VirtualAlloc which is like mmap, but you're right that it has no concept of a "break"; in fact, the stack of the main thread is below (most of) the heap in Windows, below the executable itself. In pseudopictorial form,
Linux/most other *nix:
| executable | libs | heap---> |Re: Writing a Simple Garbage Collector in C
#4Would love to see a Windows-based version of this article. No sbrk() or mmap() in Windows makes the implementation a bit different.
Windows has VirtualAlloc which is like mmap, but you're right that it has no concept of a "break"; in fact, the stack of the main thread is below (most of) the heap in Windows, below the executable itself. In pseudopictorial form, Linux/most other *nix: | executable | libs | heap---> |
Does this picture change much between the 32-bit vs 64-bit world? How about if there are few vs many threads? (For instance, if a program on 32-bit windows spawns hundreds of threads, surely you can't squeeze all those stacks below the heap, can you?)
Re: Writing a Simple Garbage Collector in C
#5Earlier quoted context omitted.
Windows has VirtualAlloc which is like mmap, but you're right that it has no concept of a "break"; in fact, the stack of the main thread is below (most of) the heap in Windows, below the executable itself. In pseudopictorial form, Linux/most other *nix: | executable | libs | heap---> |
Does this picture change much between the 32-bit vs 64-bit world? How about if there are few vs many threads? (For instance, if a program on 32-bit windows spawns hundreds of threads, surely you can't squeeze all those stacks below the heap, can you?)
The 64-bit address space is much bigger and even more unpredictable when there's ASLR, but in my experience the main thread's stack still ends up below the executable; they're just much farther apart. I believe other threads' stacks also fit somewhere below, but with 32-bit it will start allocating them in areas that would've otherwise been heap once the area below the executable runs out.
Re: Writing a Simple Garbage Collector in C
#6Issues I found at a glance:
1. This uses unsigned int for the chunk size, so the allocator will overflow on requests of 4GB or more despite taking a size_t. It seems that this is 32-bit only.
2. Even on 32-bit, the num_units calculation will overflow if you request (for example) 0xffffffff bytes of memory instead of returning an error.
3. None of this is thread-safe. It needs a global mutex lock.
4. EBP cannot be relied upon to yield anything sensible with -fomit-frame-pointer, which is common on 32-bit x86 as it brings the number of GPRs from 6 to 7.
Re: Writing a Simple Garbage Collector in C
#7Issues I found at a glance: 1. This uses unsigned int for the chunk size, so the allocator will overflow on requests of 4GB or more despite taking a size_t. It seems that this is 32-bit only. 2. Even on 32-bit, the num_units calculation will overflow if you request (for example) 0xffffffff bytes of memory instead of returning an error. 3. None of this is thread-safe. It needs a global mutex lock. 4. EBP cannot be rel…
He uses 32 bit pointers for the scan also, I think 32 bit only is intended. It also won't detect unaligned pointers :-). But this is someone's first try while learning about C or GC, he does says there will be mistakes!
Re: Writing a Simple Garbage Collector in C
#8Issues I found at a glance: 1. This uses unsigned int for the chunk size, so the allocator will overflow on requests of 4GB or more despite taking a size_t. It seems that this is 32-bit only. 2. Even on 32-bit, the num_units calculation will overflow if you request (for example) 0xffffffff bytes of memory instead of returning an error. 3. None of this is thread-safe. It needs a global mutex lock. 4. EBP cannot be rel…
> None of this is thread-safe. It needs a global mutex lock.
Or have a separate allocation chain for each thread.
It would increase fragmentation, but not by a lot, and probably increase performance by more than enough to make up for it.
Re: Writing a Simple Garbage Collector in C
#9Issues I found at a glance: 1. This uses unsigned int for the chunk size, so the allocator will overflow on requests of 4GB or more despite taking a size_t. It seems that this is 32-bit only. 2. Even on 32-bit, the num_units calculation will overflow if you request (for example) 0xffffffff bytes of memory instead of returning an error. 3. None of this is thread-safe. It needs a global mutex lock. 4. EBP cannot be rel…
> None of this is thread-safe. It needs a global mutex lock. Or have a separate allocation chain for each thread. It would increase fragmentation, but not by a lot, and probably increase performance by more than enough to make up for it.
The problem is that you would still need to lock around sbrk.
Re: Writing a Simple Garbage Collector in C
#10This GC does not probably survive to pointer scrambling. If believe in C I can validly do something like
int *ptr = ...;
intptr_t iptr = (intptr_t) ptr;
ptr = NULL;
iptr ^= MAGIC;
// do something else
ptr = (int*) (iptr ^ MAGIC);
I don't think it is possible to write a GC for C if the program is allowed to do this kind of things, because there is too little structure at runtime. And in any case, this kind of GC is not a GC "for C", as it heavily relies on knowing the compiler internals.
EDIT: Re-reading, I didn't mean to be harsh. This is still interesting to read, I am just noting a weakness that is not mentioned in the article. BTW, I know that glibc actually does some pointer scrambling like I said to mitigate some types of attack.