News for hackers. Stuff that matters.
Re:Writing a Simple Garbage Collector in C by pcwalton on Sunday December 15, 2019 @01:30AM (#21794813)
Issues 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 by masklinn on Sunday December 15, 2019 @06:34AM (#21795726)
TBF the author is pretty clear in their introduction:

> our code will be dependent on the Linux kernel […] 32-bit and not one bit more […] Please don't use this code. I did not intend for it to be wholly correct and there may be subtle bugs I did not catch.

because the use of sbrk also seems like a pretty bad idea.

Re:Writing a Simple Garbage Collector in C by earenndil on Sunday December 15, 2019 @02:40AM (#21795011)
> 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 by pcwalton on Sunday December 15, 2019 @03:21AM (#21795132)
The problem is that you would still need to lock around sbrk.
Re:Writing a Simple Garbage Collector in C by earenndil on Sunday December 15, 2019 @03:06PM (#21798628)
Fair enough. You would probably switch to mmap, though, which works across threads.
Re:Writing a Simple Garbage Collector in C by abcdef123xyz2 on Sunday December 15, 2019 @01:42AM (#21794851)
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 by stevefan1999 on Sunday December 15, 2019 @12:39PM (#21797529)
This really reminds me of a project called TinyGC/tgc[0], made by Daniel Holden who is currently a Ubisoft researcher. I have also tried his Cello[1] framework for C99 which also incorporated a garbage collector similar to tgc. Cello is pretty fun to use but the syntax was still limiting.

[0]: https://github.com/orangeduck/tgc

[1]: https://github.com/orangeduck/Cello

Re:Writing a Simple Garbage Collector in C by RodgerTheGreat on Sunday December 15, 2019 @08:43AM (#21796166)
As another example, here's a simple GC I wrote quite a while ago in Forth: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith...

This one is a precise, copying GC, with a reserved arena for persistent references into garbage-collected objects (in addition to the stacks). Pointers are identified by reserving a high bit in words.

Re:Writing a Simple Garbage Collector in C by eru on Sunday December 15, 2019 @09:00AM (#21796245)
In C that's hard to to do in general, because people do pointer arithmetic, and they sometimes abuse that pointers often come aligned (eg 3 byte aligned), so they re-use the extra two bits for various flags and mask them out before de-referencing.

But compare https://news.ycombinator.com/item?id=19182779

Re:Writing a Simple Garbage Collector in C by giomasce on Sunday December 15, 2019 @04:09AM (#21795247)
This 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);
At the end of this ptr is again a valid pointer to the same thing it was pointing at the beginning. However, if a GC scan will happen during the "do something else" block, it won't see the actual pointer value and it might free the pointed object.

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.

Re:Writing a Simple Garbage Collector in C by beefhash on Sunday December 15, 2019 @04:23AM (#21795279)
You're allowed to do that, but the standard is making no guarantees: C11, § 6.3.2.3(6) “Any pointer may be converted to an integer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.”

I'd consider pointer scrambling to be a pathological case because of that.

Similarly, C11, § 6.5.11(2) constrains XOR to be only valid on integer types, but not on pointer types, further suggesting that you're not really supposed to be doing this.

Re:Writing a Simple Garbage Collector in C by hvdijk on Sunday December 15, 2019 @05:21AM (#21795457)
intptr_t is special though. intptr_t has the property that any void pointer can be converted to it and back again to produce the original value. This is in the specification for intptr_t (7.20.1.4), not the general language rules, so it is easy to miss. (Edit: GP used an int pointer, but the example can be trivially modified.)
Re:Writing a Simple Garbage Collector in C by giomasce on Sunday December 15, 2019 @07:41AM (#21795943)
Also, I believe that you can also access the object representation of the pointer and scramble it. If you fix it up later, I believe it will have to represent the original pointer, by C11 6.2.6.1 (4).
Re:Writing a Simple Garbage Collector in C by INTPenis on Sunday December 15, 2019 @04:11AM (#21795255)
I had a co-worker who was a sysadmin and was writing a GC on his own time. Just for fun. The guy was seriously over qualified but I guess he chose to work with simple stuff for his own sanity.
Re:Writing a Simple Garbage Collector in C by chousuke on Sunday December 15, 2019 @04:56AM (#21795390)
Might be he enjoys coding, but not software projects. Personally I can program adequately when needed, but I ended up working as a sysadmin because I determined I don't have the right temperament to deal with software projects. I prefer dealing with systems as a whole instead of focusing on individual pieces of software.
Re:Writing a Simple Garbage Collector in C by stevedekorte on Sunday December 15, 2019 @01:04PM (#21797726)
It's great to see tutorials like this. FWIW, here's a tiny incremental (baker treadmill) collector[0] library I wrote. It was used in the implementation of the Io programming language.

[0] https://github.com/stevedekorte/garbagecollector

Re:Writing a Simple Garbage Collector in C by jimbob45 on Saturday December 14, 2019 @11:34PM (#21794472)
Would 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 by userbinator on Sunday December 15, 2019 @12:13AM (#21794589)
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---> <--- stack |

    Windows:
    | <--- stack | heap | executable | heap | libs | heap---> |
Re:Writing a Simple Garbage Collector in C by marvy on Sunday December 15, 2019 @12:38AM (#21794665)
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 by userbinator on Sunday December 15, 2019 @01:16AM (#21794780)
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 by marvy on Monday December 16, 2019 @10:28PM (#21810248)
thanks!
Re:Writing a Simple Garbage Collector in C by zerr on Sunday December 15, 2019 @05:56AM (#21795584)
Btw brk and sbrk are deprecated in POSIX anyway.
Re:Writing a Simple Garbage Collector in C by matheusmoreira on Sunday December 15, 2019 @07:41AM (#21795944)