Linux Kernel unit testing.

Most software engineers, when asked how they would approach designing and implementing a particular component, will always say something about unit tests. Especially so if put on the spot in an interview setting. Yet, examining something like the Linux kernel, Xen or Tiano Core UEFI, you see plenty of new complex code that has no unit or component testing anywhere in sight.

Granted, testing is hard. It's hard to test hardware/software interactions. But there is no excuse for not testing driver and component interactions. A good example is something like the virtual HCI driver (/drivers/bluetooth/hci_vhci.c), which would allow an enterprising BlueZ developer to inject bogus HCI messages and catch bugs, but I digress :-). And there is little excuse for not testing self-contained code, especially the algorithmic variety, like trees, lists, caches, and so on. Sure, it has no bugs when you wrote it originally, but can you say the same after "changing it slightly" in six months? Unit testing also lets you more critically think about edge cases - implementing your tests BEFORE you start instead of AFTER you get a kernel panic will save you a lot of time.

I needed to store sector ranges sparsely for something related to Software RAID that I'll blog about soon, so basing my work on an augmented rb-tree seemed like a good fit. So how do I unit test? I have two operations to test - marking ranges and unmarking ranges. Testing this involves going from some intial state to a post-operation state. Thus I need to describe the initial state of the object, i.e. the range tree, and be able to easy compare against the post-operation state. I decided that serializing the object as a string makes the most sense. Anyway, here is my approach. Hopefully it will be useful for someone doing something similar with rb-trees and wanting to test :-).

/*
 * Parses a string like "[start-end][start-end][start-end]..." to
 * add new ranges to a ranges object.
 */
static int __init ranges_create(struct ranges *ranges,
    char *buf)
{
 int ret, read;
 sector_t start, end;

 while (1) {
  ret = sscanf(buf, "[%lu-%lu]%n", &start, &end, &read);
  if (ret != 2)
   return 0;

  ret = mark(ranges, start, end);
  if (ret)
   return ret;
  buf += read;
 }

 return ret;
}

/*
 * Dumps the ranges object as a string in the form
 * "[start-end][start-end][start-end]...", where described
 * ranges are in increasing order.
 */
static void __init ranges_dump(struct ranges *ranges,
          char *buf, size_t len)
{
 struct rb_node *node;
 int off = 0;

 for (node = rb_first(&ranges->root); node;) {
  off += snprintf(buf + off, len - off, "[%lu-%lu]",
    rb_entry(node, struct range, node)->start,
    rb_entry(node, struct range, node)->end);
  node = rb_next(node);

  /* More nodes than expected. */
  if ((off + 1) == len &&
      node &&
      len > 1) {
   buf[len - 2] = '+';
   break;
  }
 }
 buf[len - 1] = '\0';
}

/*
 * Discard ranges unit test. Creates a ranges object
 * based on the spec string in, performs operation
 * specified by fn on range [start, end], and compares the
 * resulting discard tree against the spec string expected.
 */
static __init int ut(int (*fn)(struct ranges *,
          sector_t, sector_t),
       sector_t start, sector_t end,
       char *in,
       char *expected,
       char *name)
{
 int len;
 int ret = 0;
 char *out = NULL;
 char *pre = NULL;
 struct ranges ranges;
 static unsigned test = 0;

 printk("[%04u] - ", test);

 len = strlen(expected) + 1;
 out = kzalloc(len, GFP_KERNEL);
 if (!out) {
  ret = -ENOMEM;
  pre = "kzalloc fail";
  goto out;
 }

 ranges_prep(&ranges);
 ret = ranges_create(&ranges, in);
 if (ret) {
  pre = "ranges_create fail";
  goto out;
 }

 ret = fn(&ranges, start, end);
 ranges_dump(&ranges, out, len);
out:
 ranges_clean(&ranges);
 if (!ret && !strncmp(out, expected, len))
  printk("PASS - %s\n", name);
 else {
  printk("FAIL - %s(%lu, %lu) - %s\n--> ",
         fn == mark ? "mark" : "unmark",
         start, end, name);

  if(pre)
   printk("%s: %d\n", pre, ret);
  else {
   printk("expected %s\n"
          "--> got      %s\n"
          "--> retval   %d\n",
          expected, out, ret);
   if (!ret)
    ret = -EINVAL;
  }
 }

 if (out)
  kfree(out);
 test++;
 return ret;
}

/*
 * Main unit test driver.
 */
int __init ranges_test(void)
{
 int err = 0;
 bool clean_slab = false;

 printk("range tree sanity tests\n");
 printk("----------------------- \n");

 if (!range_cache) {
  BUG_ON(ranges_init());
  clean_slab = true;
 }

 /* Marking tests. */
 err |= ut(mark, 50, 100,
     "",
     "[50-100]",
     "first");
 err |= ut(mark, 50, 100,
     "[50-100]",
     "[50-100]",
     "duplicate");
 /* And so on.... */
 err |= ut(unmark, 10, 350,
     "[20-30][50-100][200-300]",
     "",
     "unmark all overlap");
 if (err)
  panic("range tests failed\n");

 if (clean_slab) {
  ranges_fini();
  BUG_ON(range_cache);
 }
 return 0;
}

subsys_initcall(ranges_test);
#endif

If a test fails, you'll get something like:

[    0.130990] [0039] - PASS - unmark middle
[    0.131992] [0040] - PASS - unmark middle
[    0.132989] [0041] - FAIL - unmark(21, 300) - unmark middle
[    0.133445] --> expected [20-21]
[    0.133989] --> got      [20-20]
[    0.133990] --> retval   0
[    0.135989] [0042] - PASS - unmark all overlap
[    0.136989] Kernel panic - not syncing: range tests failed
[    0.136990]