How to implement Reference counting in C?

Question

read about it here.

I need to implement a variation of such an interface, say we are given a large memory space to manage there should be getmem(size) and free(pointer to block) functions that has to make sure free(pointer to block) can actually free the memory if and only if all processes using that block are done using it.

What I was thinking about doing is to define a Collectable struct as pointer to block, size of it, and process using it count. then whenever a process using a Collectable struct instance for the first time it has to explicitly increment the count, and whenever the process free()'s it, the count is decremented.

The problem with this approach is that all processes must respond to that interface and make it explicitly work : whenever assigning collectable pointer to an instance the process must explicitly inc that counter, which does not satisfy me, I was thinking maybe there is a way to create a macro for this to happen implicitly in every assignment?

I'm seeking of ways to approach this problem for a while, so other approaches and ideas would be great...

EDIT : the above approach doesn't satisfy me not only because it doesn't look nice but mostly because I cant assume a running process's code would care for updating my count. I need a way to make sure its done without changing the process's code...

Answer 1

An early problem with reference counting is that it is relatively easy to count the initial reference by putting code in a custom malloc / free implementation, but it is quite a bit harder to determine if the initial recipient passes that address around to others.

Since C lacks the ability to override the assignment operator (to count the new reference), basically you are left with a limited number of options. The only one that can possibly override the assignment is macrodef, as it has the ability to rewrite the assignment into something that inlines the increment of the reference count value.

So you need to "expand" a macro that looks like

a = b;

into

if (b is a pointer) { // this might be optional, if lookupReference does this work
  struct ref_record* ref_r = lookupReference(b);
  if (ref_r) {
    ref_r->count++;
  } else {
    // error
  } 
}
a = b;

The real trick will be in writing a macro that can identify the assignment, and insert the code cleanly without introducing other unwanted side-effects. Since macrodef is not a complete language, you might run into issues where the matching becomes impossible.

(jokes about seeing nails where you learn how to use a hammer have an interesting parallel here, except that when you only have a hammer, you had better learn how to make everything a nail).

Other options (perhaps more sane, perhaps not) is to keep track of all address values assigned by malloc, and then scan the program's stack and heap for matching addresses. If you match, you might have found a valid pointer, or you might have found a string with a luck encoding; however, if you don't match, you certainly can free the address; provided they aren't storing an address + offset calculated from the original address. (perhaps you can macrodef to detect such offsets, and add the offset as multiple addresses in the scan for the same block)

In the end, there isn't going to be a foolproof solution without building a referencing system, where you pass back references (pretend addresses); hiding the real addresses. The down side to such a solution is that you must use the library interface every time you want to deal with an address. This includes the "next" element in the array, etc. Not very C-like, but a pretty good approximation of what Java does with its references.

Answer 2

Semi-serious answer

#include "Python.h"

Python has a great reference counting memory manager. If I had to do this for real in production code, not homework, I'd consider embedding the python object system in my C program which would then make my C program scriptable in python too. See the Python C API documentation if you are interested!