Coder Corner

Some time ago I mentioned the ICE kernel and somebody asked me about the source code. Well sorry, I’m not going to release this just yet. It’s not secret or anything, it’s just extremely ugly-looking source code. You have to realize: this is the first part of the engine I wrote, somewhere around 2000. I won’t release this without a serious cleaning / refactoring pass first.

However I can briefly describe what it does. It’s nothing special, really. To be perfectly honest I was just experimenting with random ideas, to see if they would work, etc. I never imagined I would still be using this stuff almost 10 years later. Also, even if I’m still using this at home, it doesn’t mean I would ever want to replicate this in a “real” engine at work, or on a console.

So anyway it all started as a reaction to the vanilla reference counting that we’d been using before, in “Irion“. In that engine we had manual, explicit “IncRef” and “DecRef” calls. You couldn’t delete an object directly (private dtor), instead you DecRef, and if the counter reaches 0 the object deletes itself. Standard stuff. But we had a lot of issues with that, people forgot to call “IncRef” or “DecRef”, unused objects that should have been deleted were found in memory alive and well, or quite simply we got many crashes from dangling pointers. Typical BS.

After the death of Irion I started my engine from scratch at home, and I really didn’t want to end up with the same mess (*). So I was looking for a solution to this, that’s the context. At the time the information about engine architecture on the Internet was scarce, or maybe I didn’t look well enough, in any case I don’t remember finding anything very useful online. So I started to build something, probably more out of boredom and curiosity than necessity.

First of all, it only works for objects inheriting a base class. For historical reasons, this base class is called “Cell” (why this is so is another, completely different story). Cell objects register themselves to the “kernel” in their ctor. They unregister themselves from the kernel in their dtor. The kernel is a singleton, for better or for worse (it was almost 10 years ago, I didn’t care about multiple threads).

Now when you create a “reference”, you still have an explicit function to call: “AddRef”. As the same suggests, it does not increase a simple reference counter (as “IncRef” was doing), it keeps track of the “owning object”, or simply owner, and the “referenced object”, or simply reference. Those couples of (owner, reference) are stored inside the kernel, in something called “reference tracker”.

If there is any intelligence in the system, it might be in the reference tracker. This is a somewhat creative data structure designed to keep track of those pairs efficiently, both in terms of speed and memory. A  (owner, reference) pair is simply a DWORD, made of two 16-bit IDs. The number of objects is limited to 64K, yes. The pairs are simply stored in a contiguous amount of memory, like a vector of DWORDs. Given an input Cell, the structure otherwise provides O(1) access to:

• its number of owners, and the set of owners
• its number of references, and the set of references

So, in a standard system you would get a Cell object and you could only do something like “GetRefCount”. It would return “3″, and you would know that this Cell is referenced by 3 other Cells somewhere. In ICE, you can easily ask for the “ref counter” (= the number of owners), but also who the owners are. That’s the first building block.

The second step is to investigate what happens when you actually delete an object. As we saw before, on deletion a Cell unregisters itself from the Kernel. The Kernel in turns tells the Reference Tracker about this deleted Cell. And since the Reference tracker knows what other Cells are still referencing the deleted one, well, from this point it’s easy to call the owners for notification. That function is called “OnInvalidReference”, IIRC.

So, for example:

• you have a Material, 3DS-MAX style
• it has a Reference to a Diffuse texture
• if you delete the texture (and I mean really, a savage “delete ptr” anywhere), the system calls Material::OnInvalidReference(), with the deleted Cell (the texture) as a parameter. From here, the Material can fix its dangling pointer (at least it was the original idea, but it evolved a lot afterwards)

There are a bunch of technical issues here with circular references and how to implement all this efficiently, but those are details “beyond the scope of the discussion”. The question was about containers, remember? Well it should be obvious what the next part was: of course I made a Cell-based container. Completely customized object, STL-Vector-style, that can hold Cell pointers, nothing else. The benefit, as you already guessed from the previous post and previous paragraph, is that if I ever carelessly delete a Cell object stored anywhere else in one of those containers, the kernel will know, it will call the container’s “OnInvalidReference”, and the container will remove the bad pointer from itself, automatically. Done!

This, unfortunately, was only the beginning of my weird architecture experiments.

Not long after that, I tried to fix the other main pain in the butt that had plagued Irion since the beginning: serialization. Oh man how I hated writing serialization code in Irion. In ICE, I really wanted to have an automatic mechanism to do that for me. IIRC the idea came from the Half-Life SDK: they had this great “offset of” macro that would give the offset of a member within a class. It’s pretty standard and well-known those days, but at the time, and for me, it was a mini revolution. The serialization code in Irion had to be written manually and painfully. Thanks to this single macro, suddenly it was possible to automate a large part of it. I’ll spare you the details as I’m sure you’re all aware of this stuff now, it’s used and over-used for serialization, meta-data, scripting, etc. The point to take home here is that the kernel suddenly knew about Cell classes’ members… and in particular, about other Cell pointers stored within Cell classes. Which opened a whole brand new Pandora’s box.

Remember, I was only toying at home. This was not production stuff. The ICE engine has never been used commercially or anything. No harm done.

Let’s face it: what’s the point of calling “OnInvalidReference” for a given Cell to clean its dangling pointers… if you can do it yourself? “If you want something done correctly, do it yourself”. Right. So that’s basically what I did. Provided you declared members with the correct serialization macros, the kernel does not call objects anymore to tell them to clean an invalid pointer. The kernel cleans the invalid pointer all by itself. It knows where it is! So it just clears it. Zero it. Nullify it.

That’s usually the point where type-safety zealots and other fans of “clean C++” (talk about an oxymoron) give up and start throwing rotten tomatoes at my indecent lack of concern for “proper OO ways”. (But then again, if “Boost” is the “proper” infant of the OO way, I’ll more than gladly remain a non-believing maverick. Boost! What a joke!)

But wait! I’m not done! I still have to tell you how discovering handle-based “weak pointers” changed the picture over again! And how the kernel can “remap” itself and move objects in memory under the hood to reduce fragmentation!

Come back! It’s fun!

Hello …?

(*) I failed

This entry was posted on Saturday, August 22nd, 2009 at 3:12 pm and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.