What would a garbage collector do here?

Question

I saw this bit of code in another thread

void foo {
  int *n = malloc(sizeof(int)); 
  *n = 10; 
  n++;
  printf("%d", *n);
}

The mistake here is obvious. n isn't being dereferenced. There is a memory leak. Let's assume there is a garbage collector working here. The reference count to our initial value of n is zero now because n isn't referencing it anymore. So it's garbage and returned back. But what about the new location pointed by n? Technically this area of memory hasn't been allocated yet. So will the reference count be incremented here?

Answer 1

I changed my mind; I think yes. The problem is code like this:

int* n = malloc(sizeof(int));
n++;
int* o = n;
int* p = n;
n = malloc(sizeof(int));

Now there are three references to the memory pointed to by n, but the garbage collector only sees one. Doing n = NULL; would cause a cleanup despite existing o and p pointers. Pointer flexibility like this is the main reason a C garbage collector is so difficult; I'm not sure it's possible to have a flawless garbage collector in C, as you can have pointers whose addresses aren't known until runtime

Answer 2

A correctly implemented garbage collector would work as follows:

int *pi = malloc(sizeof int);
*pi = 10;

Everything's fine here.

pi++;

This statement lets pi point behind the allocated int, which is explicitly allowed by the ISO C99 standard (see 6.5.6p7, 6.5.6p8). Later in the code, there may be pi--, so the allocated int can still be accessed. Or it may be accessed by the expression pi[-1], which is perfectly valid at this point.

pi = NULL;

At this point, there is no way to ever access the allocated int anymore, so the garbage collector may collect the memory.

In summary: All pointers that point either to the beginning of an object, to somewhere in the middle of that object or to the location behind that object can be used to access the object. So if such a value exists in memory, the object must not be garbage collected.

Answer 3

C garbage collectors do not perform reference counting. They are typically mark-sweep, and they operate on blocks, not individual bytes. In your example, the gc would mark the block, not the address. Even so, the core of your question is still valid:

What does the mark phase do when it reaches a "bad" pointer?
A conservative collector simply ignores it. The memory in the initial malloc will be collected.