A few thoughts on memory management in grail

Posted: Thursday, 2009-12-10 09:42 | Tags: Programming, Grail

In D we had a garbage collector that made things really easy: Just allocate an object and never think about what happens to the memory of that object again, the gc does it for you. In C++ there is no garbage collector built in so you have to delete old objects yourself. That per se is not so much a problem as long as the question of ownership is always cleared.

Ownership means: Object a has a reference to object b and is responsible for deleting it. Normally with a little thought its easy to say which object should own which one(s). However, if you let the user allocate and play around with objects in lua, things can get a little more complicated.

Current non-solution

Currently I'm using a thingy I call "registry". This holds references to all objects allocated in lua and destroys them when they aren't useful anymore. To find out when that is, you tell it to the registry. There are two possible scopes: CHAPTER and APPLICATION. Objects with CHAPTER scope exist until the current chapter runs. This is most useful for scenes and the actors running around in them.

The APPLICATION scope holds objects as long as the program runs. This can be useful for the main menu or other user interface stuff.

However this approach now leads to some Problems:

  • Currently it can happen that a Scene "s" holds an actor "a" and its not in general known if "a" is in the registry. In this case its not known if the scene should destroy "a" when its destroyed itself or if the registry would do it. Also it might be that the user wants a longer lifetime for "a" than "s" has.
  • The user has a lot of ways to fuck up everything when creating an object with chapter scope. For example what happens when a chapter-scope object is created outside of any running chapter? What if the user by accident holds a reference to a chapter-object after the object has been destroyed?
  • Its annoying to always have to write "chapter" or "application" for each object you create.

Possible solution 1: Register everything

Just force everything to be in the registry for example by giving the user no way to create an object without registering it. Especially when objects internally create other objects, put them in the registry too, "inheriting" scope from the parent object. Then no object would ever use delete, that would completely be Registry s job.

Problem: This still allows the user to reference objects beyond their lifetime and to produce similar fuckups. And its still annoying to always tell the scope when creating an object.

Possible solution 2: Register only certain object types

We could only register Scene s and let them have ownership for things like actors etc... However there is no guarantee that the user doesn't try to use the same image in two different scenes and there we have the double free corruption again. So this one is really a no-go

Possible solution 3: Use reference counting

Build a simple reference counting mechanism so each object knows how many places reference to it. This would mostly make the registry unecessary, except maybe for holding scenes for the current chapter and giving names to objects for the user. The only problem with reference counting is that it can't handle reference circles well (ie A has a pointer to B and B has a pointer to A), so I have to think about the whole structure a little more to guarantee there won't be such circles (although I'm already pretty sure there won't).

Below is a little examplary code. I didn't even try to compile it so forgive me if its not correct, it should just illustrate the idea.

class ReferenceCounted {
  public:
    unsigned int referenceCount;

    ReferenceCounted() : referenceCount(0) { }
};

template <typename T>
class Reference {
    T* obj;

    // Forbid copying of references
    Reference(const Reference<T>& other) { }
    Reference<T> operator=(const Reference<T>& other) { }

  public:
    Reference() : obj(0) { }

    Reference(T* obj) : obj(obj) {
      (obj->referenceCount)++;
    }

    virtual ~Reference() {
      if(obj) {
        (obj->referenceCount)--;
        if(obj->referenceCount == 0) {
          delete obj;
        }
      }
    }

    void ref(T* o) {
      if(obj) {
        (obj->referenceCount)--;
        if(obj->referenceCount == 0) {
          delete obj;
        }
      }
      obj = o;
      (obj->referenceCount)++;
    }

    T& operator*() { return *obj; }
    T* operator->() { return obj; }
};

// Usage:

class Foo : public ReferenceCounted {
  public:
    void foo() { ... }
}

void f() {
  Reference<Foo> r;

  r.ref(new Foo());
  r->foo();

} // "r" is removed from the stack here
// that reduces the reference count for the Foo
// object and thus deletes it! Nice isn't it?