Dispatch Objects

It seems like the next step in my OS development is going to be laying down some kernel work. I thought I'd be able to delay this, but doing so would only result in less useful work being done. A kernel is responsible for many things. I'm sure many more things than I even know about right now (such is the nature of this whole undertaking). However, my experience writing Windows drivers has offered a decent skeleton to start with.

One piece of this skeleton is dispatch objects. Basically, this is any sort of thing that can be waited upon. A timer, an event, a lock, a thread (joining a thread, etc.). I figure this is as decent a place to start as any. The way a dispatch object will work in my kernel is it will be a light weight structure containing a list of waiting threads. Of course, this means I need to start defining a thread structure as well. I imagine I'll continue to flesh out the guts of the kernel (or at least their structures) by jumping off on this one spot.

Since a dispatch object is essentially a list, the first structure I need to create is a list structure. There are many ways to create a list. You can create a linked list, a vector, or various other structures. Again, leaning on my Windows background I'll choose something very similar to the LIST_ENTRY structure in the NT kernel. In more data structure books I've seen a doubly-linked list defined as:

typedef struct _LIST_NODE
{
    struct _LIST_NODE* pPrev;
    struct _LIST_NODE* pNext;
    void* pData;
} LIST_NODE;

Here, I'll rely on something clever that Windows does with it's list structure -- there's no "data" pointer. The structure is intended to be embedded directly into any other data structure:

typedef struct _LIST_NODE
{
    struct _LIST_NODE* pPrev;
    struct _LIST_NODE* pNext;
} LIST_NODE;

typedef struct
{
    LIST_NODE  ThreadListHead;
    ...
} DISPATCH_HEADER;

typedef struct
{
    UINT32     ThreadId;
    ...
    LIST_NODE  DispatchListNode;
    ...
} THREAD_OBJECT;

The way this works is the list pointers are offset from to find the original object the list points to. In the DISPATH_HEADER above, this is simply the same address. However, say I had additional members before the ThreadListHead member, you'd then SUBTRACT back to get the original object pointer. This is done using a member offset macro, where the offset of a member into a structure is computed and then subtracted off the list pointer. While this may appear clunky at first it has one very nice advantage - you don't need to dynamically allocate small chunks of memory. In the example above, you would simply have a list insertion function that you'd pass a pointer to the THREAD_OBJECT::DispatchListNode member variable to.

There are multiple reasons this is a good thing. First, the previously mentioned avoidance of small memory allocations. Second, by not relying on any sort of memory allocation this data structure can be used in the kernel before memory allocation is even possible -- obviously, you need to write an allocator before you can use one. Third (but related to the first), the absence of smaller allocations for what is a widely used construct can add up to some pretty substantial memory savings. Any memory allocation will require a chunk of memory for bookkeeping. This is usually going to be at least the size of a few pointers. For small allocations of only 3 pointers (in the first list structure definition) the overhead of the allocation may very well be larger than the actual data usage. Considering how widely used the LIST_NODE structure will be, this is a substantial savings in memory as well as access speed (there isn't an indirect memory access to get to the actual structure, if you have the pointer to the list, it's only a subtraction to get the actual pointer versus another read).

So, there it is, the beginnings of a DISPATCH_HEADER, a THREAD_OBJECT, and a LIST_NODE. This kernel is practically writing itself...