Wednesday, October 10, 2007

Linux Kernel Code: #define for loop

When competing in algorithm-type competitions, there tends to be a need for looping through structures. The infamous #define for loop comes to mind. Nearly all TC competitors use it, but the originality was unknown -- well, until a couple of days ago. Here I am studying on Linux Kernal Internals, and I come to what seems to be either a macro or an inline function:

for_each_task(p)

This segment of code is used a lot in the Linux Kernel. First and foremost, there is no notion of thread or process within the linux kernel. The single most basic unit idea of a transaction is a task. Therefore, the Linux Kernel has a table of tasks. Before, the Linux Kernel 2.4, the Linux Kernel would have a table or an array of task structures. Not anymore, it is constructed so that it holds a doubly circular linked list of tasks. Furthermore, the first task that gets inserted into this list is the kernel initialization. Therefore, it's name is such as "init_task" and so when you get back to this address, you know you have cycled around. Also, there is a notion of current -- the current task. Back to the point, since it is now a doubly circular linked list structure, the for_each_task(p) is defined as the following:

#define for_each_task(p) \
for (p = &init_task; (p = p->next_task) != &init_task; )

This is the first place where a #define is used where a for-loop is constructed. Therefore, many programmers nowadays use a #define in low-level systems programming. It's nothing new; it's been used since all kernel eternity...

No comments: