Tuesday, June 18, 2013

Kung-f00: surviving in the kernel

There are two level of programming in an environment like the Linux Kernel, imho: survival and release. Survival programming is what you will do when you need to prototype or a proof-of-concept. Release programming (or refactoring) takes place when you want your code to be accepted in the kernel as a patch or another driver. Here are some ancient, half-forgotten programming techniques that could help you survive.

If you have been raised in OOP, you may need to un-learn a few things to survive in the kernel. Especially your habits on constructors. Every time you can define an initial value at compile time rather than at run-time, you save yourself from the need to check your initialisation has indeed happened, and you avoid the risk that some mistake you’ve made could prevent the system from booting altogether. You don’t necessarily need to pollute the top-level name space for that:

   static int reported=0;
   if (!reported && my_page(p)) {
       printk("my page got swapped.\n");

The static reported variable will have block-limited scope (so you could have as many such block as you need, and always use the name ‘reported’), but program-wide lifetime (and thus its value will persist across function calls). I believe this saves us from many __init functions.

just useless ...

Do you need a reference to some kernel object X? Save yourself the problem of figuring out whether that object will be ready when your __init function would be called. Use a NULL value as initialisation and ensure that you properly use lazy initialization
   if (!backing_device) backing_device=find_swap_device(0);
Downside is that you’ll have to repeat this line in every access point of your code. That’s unacceptable at the scope of a corporate business logic, but perfectly maintainable at the size of a prototype.

Do you need N bytes of memory to be available and can’t afford using kmalloc because your lazy initialization could take place at a moment where it could require memory that isn’t available right now (yup, even the kernel could be low on memory) ? Well, just be plain 8-bit style and go
   byte mySpace[N];
that will be set in the bss segment of your kernel, wiped with zeroes by the loader, and don’t take extra space on the vmlinux kernel image.

Probe System Call

Ideally, when you want a feature to be optional in the Linux Kernel, you wrap it in a module that can be loaded and unloaded. The price to pay for that is a more sophisticated template to follow and significant attention to memory management to ensure whatever your module doesn’t let dangling pointers when it’s gone. Core kernel functionalities typically get enabled/disabled through system control variable in /proc, just like support for the “magic SysRq key”. That’s the good way to go for a release. During prototyping, we can be old-school and define a new system call that we’ll use for invoking late initialisation in contexts where the initialisation, and otherwise enable communication from our user-world.

The /proc filesystem requires a significant amount of support data structure to work properly, yet if using /proc/kernel/myprobe is fine and if a mere int is enough for your communication needs, it comes down to
  • locate the appropriate place to add a entry in kern_table[], with .procname=”myprobe”;
  • mimmic sysrq_sysctl_handler, and add your own static int to receive the value decoded by proc_dointvec;
  • use a clone of the sysrq_sysctl_handler() function: let proc_dointvec deal with the buffer that comes from user-space, and just launch your code logic if the user is writing to your control variable.
Dynamic Allocation within a Table

You’re used to linked list, hash tables, trees, stacks and other dynamic data structures but realise that allocating cells wouldn’t be a wise idea in the kernel ? Congrats. Kernel developer put significant effort in crafting the slab and kernel object caches to reduce allocation costs, but at a prototype scale, it isn’t clear it’s worth learning how to master it. The “16-bit style” solution to this, given that you have a static table of N elements and that “N shall be enough for everybody and we guarantee there will be at least N slots available” is to embed a linked list of free slots within your table.

You don’t even need pointers for that: simply one field in your table slot that can hold an integer index to the next free slot.
int free_slot=-2;
int allocate_slot() {
   int al;
   if (free_slot==-1) return -1; // all slots used
   if (free_slot==-2) { // lazy init: chain all entries
      for (int i=0;i<N-1;i++) table[i].next=i+1;
   al=free_slot; free_slot=table[al].next;
   return al;
Now you can focus on the real problem of guaranteeing that this table won’t suffer concurrent allocation issues :P

No comments: