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.
Writing a Simple Garbage Collector in C
11–20 of 24 posts
Re: Writing a Simple Garbage Collector in C
#12This 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 a…
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
#13I 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.
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
#14This 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 a…
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,…
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
#15Would love to see a Windows-based version of this article. No sbrk() or mmap() in Windows makes the implementation a bit different.
Btw brk and sbrk are deprecated in POSIX anyway.
Re: Writing a Simple Garbage Collector in C
#16Issues 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…
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
#17Earlier quoted context omitted.
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,…
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.)
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
#18Another great article on the subject:
http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...
Re: Writing a Simple Garbage Collector in C
#19As 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
#20As 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.
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