7
\$\begingroup\$

(I created a GitHub repository; there are few improvements as suggested by other users in the comments)

As we know, C99 has no garbage collector. To address the problem of manually deallocate objects I wrote a little framework for reference counting. I would like to have comments about the style and clarity of the code and about the idea itself.

The main idea is to supersede malloc () function with a new function named alloc (). This function allocate the bytes needed for an object plus some meta information. The client of the library should follow this pattern:

  • Allocate objects with alloc () function instead of malloc ()
  • Whenever an object is assigned to a variable (e.g. v = object) the client should make a call retain(object)
  • Whenever a reference to an object is lost the client should call release(object)

The following figure shows what happens in memory after a call to alloc ():

+---+---+---------+
| 1 | 2 |    3    |
+---+---+---------+
  ^       ^
  p       q

Memory area noted with (1) is an integer, counting references to the object. Memory area noted with (2) is a pointer to the destructor function (typedef void (*Destructor) (void *object);); whenever the reference count reaches 0 this function is called. (1) and (2) form what the code calls ObjectRecord. Memory area noted with (3) represents the space needed by the actual object. The figure also shows two pointers, namely p and q. p is the pointer to the ObjectRecord and q is the pointer to the object. alloc () function returns q (the pointer to the actual object) so the client is not bothered by metadata.

The code uses two macros (OBJECT_TO_RECORD and RECORD_TO_OBJECT) to "translate" from p to q. mem.h library contains function malloc_or_die () that simply terminate the process upon failure.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "mem.h"
#include "object.h"

#define OBJECT_TO_RECORD(ptr) ((ObjectRecord *) (((char *) ptr) - sizeof (ObjectRecord)))
#define RECORD_TO_OBJECT(meta) ((void *) (((char *) meta) + sizeof (ObjectRecord)))

typedef struct {
  unsigned int count;
  Destructor destroy;
} ObjectRecord;

void *
alloc (size_t size, Destructor destroy)
{
  ObjectRecord *record = (ObjectRecord *) malloc_or_die (sizeof (ObjectRecord) + size);
  record->count = 0;
  record->destroy = destroy;
  return RECORD_TO_OBJECT (record);
}

unsigned int
refsof (void *ptr)
{
  ObjectRecord *record = OBJECT_TO_RECORD (ptr);
  return record->count;
}

void
release (void *ptr)
{
  ObjectRecord *record;

  record = OBJECT_TO_RECORD (ptr);
  assert (record->count > 0);
  record->count--;

  if (record->count == 0)
    {
      if (record->destroy != NULL)
        {
          record->destroy (ptr);
        }

      free (record);
    }
}

void
retain (void *ptr)
{
  ObjectRecord *record = OBJECT_TO_RECORD (ptr);
  record->count++;
}

Now, let me give you some examples. Imagine we are building a Java-like ArrayList. Our data type looks like:

typedef struct {
  void **elems;    /* Resizable array for the elements. */
  size_t size;     /* Number of elements actually in the array. */
  size_t capacity; /* Size of the array. */
} AList;

To create a new array list we use the function

AList *
alist_new ()
{
  AList *alist = (AList *) alloc (sizeof (AList), (Destructor) alist_destroy);
  alist->elems = malloc_or_die (ALIST_DEFAULT_CAPACITY * sizeof (void *));
  alist->size = 0;
  alist->capacity = ALIST_DEFAULT_CAPACITY;
  return alist;
}

static void
alist_destroy (void *alist)
{
  int i;

  for (i = 0; i < alist->size; i++)
    {
      release (alist->elems[i]);
    }

  free (alist->elems);
}

Since the array list is created with alloc () function, when the reference counter goes to 0, alist_destroy () is called automatically. alist_destroy () calls release () on each element it was holding. If the counter of one of these elements goes to 0, its destructor gets called automatically. Obviously, when we add an element to the ArrayList we should increment its counter.

void
alist_append_element (AList *alist, void *elem)
{
  /* Before appending the element to the array list, we ensure it can contain them. If not we let the array grow. */
  if (alist->capacity == alist->size)
    {
      alist_grow (alist);
    }

  retain (elem);
  alist->elems[alist->size++] = elem;
}

Now we can use our array list.

AList *alist = alist_new ();
retain (alist);

for (i = 0; i < N; i++)
  {
    /* The dummy element is retained by the array list. */
    alist_append_element (alist, dummy_new ());
  }

/* We release alist. Every element it contains will be released, too (see alist_destroy()) */
release (alist);

The example above is very simple and probably doesn't justify all the complexity introduced by the library. A slightly more complex example is shown below.

/* We have two array lists: alist_1 and alist_2. alist_1 is filled with some objects. */

/* We put the elements of alist_1 that satisfy the predicate into alist_2. */
for (i = 0; i < alist_size (alist_1); i++)
  {
    if (predicate (alist_get_element_at (alist_1, i)))
      {
        alist_append_element (alist_2, alist_get_element_at (alist_1, i));
      }
   }

/* Now we release alist_1. All the elements of alist_1 will be released, too. The
elements that we put in alist_2 have the reference counter set to 2; a call to
release () decrements the counter without freeing them. */
release (alist_1);

You probably noticed that in function alist_new () I used "standard" malloc_or_die () to instantiate elems array. I wrote this example by hand right now and I've been very lazy. In the real world I would probably create functions to allocate that array, like:

void **
array_new (int nmemb)
{
    return (void **) alloc (sizeof (void *) * nmemb, (Destructor) array_destroy);
}

And for primitive arrays:

int *
array_int_new (int nmemb)
{
    return (int *) alloc (sizeof (int) * nmemb, NULL);
}
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Simon Forsberg Nov 10 '16 at 12:24
3
\$\begingroup\$

A simpler way to write those macros would be

#define OBJECT_TO_RECORD(object) ((ObjectRecord*)(object) - 1)
#define RECORD_TO_OBJECT(record) ((void*)(record + 1))

This does the arithmetic directly in units of ObjectRecord, so you don't need the sizeof operator.

Functions are better than macros, and there's no reason that the object<->record conversions need to be macros. We should trust the compiler to inline these:

static ObjectRecord *toRecord(void *object) { return (ObjectRecord*)(object) - 1; }
static void *fromRecord(ObjectRecord *record) { return record + 1; }

In C, We don't normally cast the result of malloc(), so you should write:

  ObjectRecord *record = malloc_or_die (sizeof (ObjectRecord) + size);

or:

  ObjectRecord *record = malloc(size + sizeof *record);

(I don't like malloc_or_die() - guessing from the name, it sounds user-hostile. Terminating the entire application is definitely overkill for a fairly normal failure case, and not something that a library would want to be doing. And this is the kind of code that is otherwise useful for libraries, I think.)

There are other approaches (such as registering a failure handler), but I think it's best to copy the existing malloc() interface, and return a null pointer on failure. Every competent C programmer knows how to handle that.


My version

This has some additional changes, some of which are subjective preferences. As a C++ programmer, I obviously prefer prefix increment/decrement operators. I also find early exit preferable to conditionals, and don't like explicit comparisons against NULL. Your opinions may differ!

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

/* Internals */

typedef void (*Destructor)(void*);

typedef struct {
    unsigned int count;
    Destructor destroy;
} ObjectRecord;


static ObjectRecord *objectToRecord(void *p)
{
    return (ObjectRecord*)p - 1;
}
static void *recordToObject(ObjectRecord *r)
{
    return r + 1;
}

/* Public implementation */

void *alloc(size_t size, Destructor destroy)
{
    ObjectRecord *record = malloc(size + sizeof *record);
    if (!record)
        return record;

    record->count = 0;
    record->destroy = destroy;
    return recordToObject(record);
}

unsigned int refsof(void *p)
{
    return objectToRecord(p)->count;
}

void release(void *p)
{
    ObjectRecord *record = objectToRecord(p);
    assert(record->count > 0);

    if (--record->count)
        /* still referenced */
        return;

    if (record->destroy)
        record->destroy(p);
    free(record);
}

void retain(void *p)
{
    ++objectToRecord(p)->count;
}

(Compiled without warnings with my usual compiler: gcc -std=c11 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses).

\$\endgroup\$
  • \$\begingroup\$ Thank you for the valuable comments and this valuable reply. One thing that bother me is alignment of block (3). We know that in C structs fields are padded to make them start at fixed locations. Block (3) may be unaligned, right? Have you got any idea on how to fix this? \$\endgroup\$ – mneri Nov 10 '16 at 14:27
  • \$\begingroup\$ That's a good question, and one I didn't feel confident enough to answer. We do know that malloc() must return a pointer that can be legally converted to any pointer type (though there's a QoI issue lurking on platforms that allow unaligned access at a performance cost). You may be able to hint that Record needs the strictest possibly alignment, and I think that will pad sizeof (Record) to be a multiple of the alignment. Don't take my word for that, though - check on Stack Overflow or somewhere. \$\endgroup\$ – Toby Speight Nov 10 '16 at 15:11
  • \$\begingroup\$ It may be instructive to look at the implementation of malloc() in your favourite library. AIUI, most allocators do something similar internally to track allocation sizes, at least for larger allocations. There might be a lot of special-case code to skim-read, though. \$\endgroup\$ – Toby Speight Nov 10 '16 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.