Semantic patching with Coccinelle

This happened to me last month when I was adding support for 64-bit file systems to e2fsprogs. I thought I was nearly finished when I discovered I needed to write (yet another) new interface and convert (yet another) several hundred lines of code to it. The changes were complex enough that I couldn't use a script, and simple enough that I wanted to claw my eyes out with the soul-killing boredom of doing it by hand. That's when the maintainer, Theodore Ts'o, suggested I look at Coccinelle (a.k.a., spatch).

Coccinelle

The input to the tool is the file(s) to be changed and a "semantic patch," written in SmPL (Semantic Patch Language). SmPL looks a like a unified diff (a patch) with some C-like declarations mixed in. Here's an example:

    @@
    expression E;
    identifier fld;
    @@

    - !E && !E->fld
    + !E || !E->fld

    --- a/drivers/pci/hotplug/cpqphp_ctrl.c
    +++ b/drivers/pci/hotplug/cpqphp_ctrl.c
    @@ -1139,7 +1139,7 @@ static u8 set_controller_speed(struct controller
    *ctrl, u8 adapter_speed, u8 hp_
            for(slot = ctrl->slot; slot; slot = slot->next) {
                    if (slot->device == (hp_slot + ctrl->slot_device_offset))
                            continue;
    -               if (!slot->hotplug_slot && !slot->hotplug_slot->info)
    +               if (!slot->hotplug_slot || !slot->hotplug_slot->info)
                            continue;
                    if (slot->hotplug_slot->info->adapter_status == 0)
                            continue;

Coccinelle is designed, written, and maintained by Julia Lawall at the Department of Computer Science at University of Copenhagen, Gilles Muller and Yoann Padioleau at the Ecole des Mines de Nantes, and René Rydhof Hansen at the Department of Computer Science of Aalborg University. Coccinelle is licensed under the GPL, however, it is written in OCaml, so the potential developer base is somewhat limited.

The original goal of Coccinelle was to automate as much as possible the task of keeping device drivers up to date with the latest kernel interfaces. But the end result can do far more than that, including finding and fixing bugs and coding style irregularities. Over 180 patches created using Coccinelle have been accepted into the Linux kernel to date.

Coccinelle quickstart

First, download Coccinelle and install it. I used the source version rather than any of the precompiled options. The Coccinelle binary is called spatch.

As our example, say we have program with a lot of calls to alloca() that we would like to replace with malloc(). alloca() allocates space on the stack and can be more efficient and convenient than malloc(), but it is also compiler-dependent, non-standard, easy to use incorrectly, and has undefined behavior on failure. (Replacing alloca() with malloc() isn't enough, we also have to check the return value — but that will come later.)

Here is the C file we are working on:

    #include <alloca.h>

    int
    main(int argc, char *argv[])
    {
            unsigned int bytes = 1024 * 1024;
            char *buf;

            /* allocate memory */
            buf = alloca(bytes);

            return 0;
    }

$ sed -i 's/alloca/malloc/g' test.c

    --- test.c
    +++ /tmp/test.c
    @@ -1,4 +1,4 @@
    -#include <alloca.h>
    +#include <malloc.h>
 
     int
     main(int argc, char *argv[])
    @@ -6,8 +6,8 @@
             unsigned int bytes = 1024 * 1024;
             char *buf;
 
    -        /* allocate memory */
    -        buf = alloca(bytes);
    +        /* mallocte memory */
    +        buf = malloc(bytes);
 
             return 0;
     }

    $ sed -i 's/alloca(/malloc(/g' test.c

In Coccinelle, we'd use the following semantic patch:

    @@ expression E; @@

    -alloca(E)
    +malloc(E)

    $ spatch -sp_file test.cocci test.c

    --- test.c
    +++ /tmp/cocci-output-17416-b5450d-test.c
    @@ -7,7 +7,7 @@ main(int argc, char *argv[])
             char *buf;
 
             /* allocate memory */
    -        buf = alloca(bytes);
    +        buf = malloc(bytes);
 
             return 0;
     }

    @@ expression E; @@

    -alloca(E)

    +malloc(E)

Now, we also want to check the return value of malloc() and return an error if it failed. We can do that too:

    @@
    expression E;
    identifier ptr;
    @@

    -ptr = alloca(E);
    +ptr = malloc(E);
    +if (ptr == NULL)
    +        return 1;

    --- test.c
    +++ /tmp/cocci-output-17494-22a573-test.c
    @@ -7,7 +7,8 @@ main(int argc, char *argv[])
             char *buf;
 
             /* allocate memory */
    -        buf = alloca(bytes);
    +        buf = malloc(bytes);
    +        if (buf == NULL)
    +                return 1;
 
             return 0;
 }

Experience

One of the first hurdles I had to overcome was teaching Coccinelle about the macros in my code. Coccinelle has to do all its own parsing and pre-processing — you can't just run the input C code through cpp because then you'd have to map the post-processor output back to the original code. Macros will sometimes confuse it enough that it gives up parsing a function until it reaches the next safe grammatical starting point (e.g., the next function) — which may mean that it doesn't process most of the file. To get around this, you can create a list of macros and feed them to spatch with the -macro_file option. (Yes, that's one dash — one of my pet peeves about Coccinelle is the non-standard command-line option style.) For example, here are a few lines from the macro file I used for e2fsprogs:

    #define EXT2FS_ATTR(a)
    #define _INLINE_ inline
    #define ATTR(a)

    EXT2FS_ATTR: present in 85 parsing errors
    example:

          static int check_and_change_inodes(ext2_ino_t dir,
                                      int entry EXT2FS_ATTR((unused)),
                                      struct ext2_dir_entry *dirent, int
                                      offset,
                                      int  blocksize EXT2FS_ATTR((unused)),

One thing I am absolutely certain of: learning Coccinelle and writing semantic patches was way more fun than making the changes by hand or using regular expressions. I also had much greater confidence that my changes were correct; it is remarkably pleasant to make several hundred lines of changes and have the result compile cleanly and pass the regression tests the first time.

Related work

In terms of power and flexibility, Coccinelle is similar to the Stanford compiler checker [PDF] (commercialized by Coverity). While the compiler checker is far more mature and has better flow analysis and parsing, Coccinelle can generate code to fix the bugs it finds. Most importantly, Coccinelle is open source, so developers can find and fix bugs themselves.

Some IDEs include tools to automatically refactor code, which is one aspect of what Coccinelle does. I have never personally used one of these IDE refactoring tools and can't compare it with Coccinelle, but my friends who have report that their stability leaves something to be desired. Xrefactory is a refactoring tool available on *NIX platforms which is fully integrated with Emacs and XEmacs. It is not open source and requires the purchase of a license, although one version is available for use free of charge.

Conclusion

@@
string A, B;
expression M, MBUF;
@@
-printk(... "%s" ..., ..., print_mac(MBUF, M), ...);
+printk(... "%pM" ..., ..., M, ...);