News for hackers. Stuff that matters.
Re:Baby's First Garbage Collector by rayiner on Sunday December 08, 2013 @05:11PM (#6871670)
You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC.

Some of the things that break GC aren't even technically valid C code. For example, say I allocate three memory areas with malloc() then hold on only to the area with the lowest address, and reference the other two areas with offsets relative to the first area. This is illegal in C, though it will work on most existing implementations, because it's illegal to dereference a pointer past the end of an allocation.

Specific GC algorithms might not be able to handle say pointers into the interiors of objects, but that's not a general limitation for GC.

Re:Baby's First Garbage Collector by cperciva on Sunday December 08, 2013 @05:20PM (#6871707)
it's illegal to dereference a pointer past the end of an allocation.

Yes, but there's a legal way to do this.

reference the other two areas with offsets relative to the first area

If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer type with all the flexibility of unsigned integers, and if x = (uintptr_t)p then it's guaranteed that p == (void * )x.

In other words:

    char * x = malloc(100);
    char * y = malloc(100);
    ptrdiff_t yminusx = y - x;

    x[yminusx] = '\0'
is undefined behaviour, but

    char * x = malloc(100);
    char * y = malloc(100);
    uintptr_t yminusx = (uintptr_t)(y) - (uintptr_t)(x);

    *(char *)(void *)((uintptr_t)(x) + yminusx) = '\0'
is valid C (and has the same meaning on a DWIM compiler).
Re:Baby's First Garbage Collector by bcoates on Sunday December 08, 2013 @05:41PM (#6871797)
It looks like the second is still valid C, but a C++11 compiler is allowed to break it if it declares "strict pointer safety" rules are in effect at runtime (which a GC implementation would presumably do)
Re:Baby's First Garbage Collector by logancapaldo on Sunday December 08, 2013 @05:49PM (#6871828)
What if it's not a DWIM compiler? I'm pretty sure (happy to be corrected) pointer <-> integer conversions are implementation defined. Therefore casting between could perform some reversible operation that ensured round tripping worked, but does not require that ptr(a - b) == a - b even though a == int(ptr(a)) holds.
Re:Baby's First Garbage Collector by cperciva on Sunday December 08, 2013 @07:23PM (#6872220)
I'm pretty sure (happy to be corrected) pointer <-> integer conversions are implementation defined.

Quite correct, subject to the requirement that converting the same uintptr_t value back to (void ) will return the original pointer. So the conversion could be implemented as a hash table if the compiler author wanted.

But if you look carefully at what I wrote, I'm never converting a value which was not previously returned by a (void )->(uintptr_t) conversion.

Re:Baby's First Garbage Collector by logancapaldo on Sunday December 08, 2013 @08:22PM (#6872391)
I see. What I was worried about was a version of the code you didn't actually write (casting the ptrdiff_t result to a [u]intptr_t, not casting the pointers first).
Re:Baby's First Garbage Collector by rayiner on Sunday December 08, 2013 @05:36PM (#6871779)
Right. You could also convert a pointer to a uintptr_t, XOR it with some value, then at some later point XOR it again to get back the original address and cast it back to a pointer and dereference it, and it would be legal despite breaking GC. However, a number of things that also break GC, like your first example, also happen not to be legal C even though they'll probably work on any existing implementation.
Re:Baby's First Garbage Collector by Someone on Sunday December 08, 2013 @06:38PM (#6872030)
That's very close to the classical example of code that maims pointers: the doubly linked list that uses only one 'pointer' in each node (http://www.geeksforgeeks.org/xor-linked-list-a-memory-effici...)
Re:Baby's First Garbage Collector by city41 on Sunday December 08, 2013 @05:16PM (#6871689)
Does this still work if the GC compacts memory? I don't know much about GCs, but it seems like once your GC is advanced enough with generational collecting, compacting, etc, then allowing raw pointers seems at odds with what the GC is trying todo. I'm sure it's possible, but it's probably a heck of a lot easier just to not allow pointers.
Re:Baby's First Garbage Collector by rayiner on Sunday December 08, 2013 @05:39PM (#6871789)
It works fine as long as you have enough type information to know what is and is not a pointer.