• Immutable Page
  • Info
  • Attachments

JuliaLawall

About Me

I'm a researcher at Inria, in Paris France. I develop the tool Coccinelle, which allows easy matching and transformation of C code. Coccinelle has been designed with the goal of contributing to Linux development, but it can also be used on other C code.

Please write to me directly if you would like to apply to the Coccinelle OPW project.

Overview

These challenge problems are listed roughly in order of increasing difficulty. In particular, problems 1-3 go together, and problems 4-5 go together. It is not obligatory to do all of them. You may find other things that can be done with Coccinelle. Source of inspiration may be the results of checkpatch and patches that have been applied to the kernel in the past. Any kind of problem that occurs over and over might be amenable to being solved with Coccinelle.

These challenge problems may apply to many files in the kernel. Pick a few files, and send patches for those. Once they have been accepted, consider moving on to another challenge problem. You will get a better understanding of Coccinelle if you use it for many different thing than if you use it do one thing over and over.

Tutorial

A tutorial for Coccinelle is available here. These are slides that are intended to be presented, but they may be understandable independently of the presentation. Please note that the tutorial focuses on the source code of Linux 3.2, and so the patches created in doing the exercises of the tutorial are not suitable for submission to the opw-kernel mailing list. Doing the tutorial also does not count as a contribution to the project.

Coccinelle challenge problem 1

Consider the following function, from drivers/staging/vt6656/rf.c:

int vnt_rf_setpower(struct vnt_private *priv, u32 rate, u32 channel)
{
        int ret = true;
        u8 power = priv->cck_pwr;

        if (channel == 0)
                return -EINVAL;

        switch (rate) {
        case RATE_1M:
        case RATE_2M:
        case RATE_5M:
        case RATE_11M:
                channel--;

                if (channel < sizeof(priv->cck_pwr_tbl))
                        power = priv->cck_pwr_tbl[channel];
                break;
        case RATE_6M:
        case RATE_9M:
        case RATE_18M:
        case RATE_24M:
        case RATE_36M:
        case RATE_48M:
        case RATE_54M:
                if (channel > CB_MAX_CHANNEL_24G)
                        power = priv->ofdm_a_pwr_tbl[channel-15];
                else
                        power = priv->ofdm_pwr_tbl[channel-1];
                break;
        }

        ret = vnt_rf_set_txpower(priv, power, rate);

        return ret;
}

In this function, the last two lines could be compressed into one, as:

int vnt_rf_setpower(struct vnt_private *priv, u32 rate, u32 channel)
{
        int ret = true;
        u8 power = priv->cck_pwr;

        if (channel == 0)
                return -EINVAL;

        switch (rate) {
        ...
        }

        return vnt_rf_set_txpower(priv, power, rate);
}

The following semantic patch makes this change:

@@
expression ret;
identifier f;
@@

-ret =
+return
     f(...);
-return ret;

Do the following:

  1. Download and install Coccinelle. If you are using Linux, it should be available in your package manager. Any recent version is fine to start

with, but you may need to get the most recent version, which is 1.0.0-rc21. This is available on the Coccinelle webpage (coccinelle.lip6.fr) and on github.

  1. Download staging-next

  2. Save the above semantic patch in a file ret.cocci

  3. Run Coccinelle on ret.cocci and staging-next, ie spatch --sp-file ret.cocci --no-includes --dir {your staging-next path}/drivers/staging > ret.out. This may

take some time.

Do you find the result satisfactory? If so, submit some patches. If not, let us know!

Your code may now declare some variables that are never used. Remove them before submitting your patch.

If you do submit a patch based on the use of Coccinelle, please mention Coccinelle in your patch, and the semantic patch that you used.

Coccinelle challenge problem 2

In the following function, from drivers/staging/rtl8723au/os_dep/ioctl_cfg80211.c, the variable ret is not very useful.

static int
rtw_cfg80211_monitor_if_set_mac_address(struct net_device *ndev, void *addr)
{
        int ret = 0;

        DBG_8723A("%s\n", __func__);

        return ret;
}

The code would be simpler as:

static int
rtw_cfg80211_monitor_if_set_mac_address(struct net_device *ndev, void *addr)
{
        DBG_8723A("%s\n", __func__);

        return 0;
}

The following semantic patch makes this transformation:

@@
identifier ret;
@@

-int ret = 0;
 ... when != ret
     when strict
-return ret;
+return 0;

The code <code>... when != ret</code> means that between the int ret = 0; and the return at the end of the function, there should be no use of ret. The code <code>when strict</code> means that this should hold on every execution path, including those that abort the function (return in the middle of a function)

Test this semantic patch on the staging tree. Do you find any of the results surprising? Are the results correct? Did Coccinelle complain about anything or crash (if so, you may need to get a more recent version). Submit some patches based on your results.

Coccinelle challenge problem 3

If you look back at the code in == Coccinelle challenge problem 1, you will see that actually the only use of ret is the one at the end of the function, and the semantic patch gets rid of it. This suggests that it could be good to extend that semantic patch with another rule that would look for cases where a variable is never used, and then remove the declaration of the variable entirely. For this, the semantic patch rule shown in == Coccinelle challenge problem 2 can serve as inspiration, but needs to be somewhat modified. The goal is, as much as possible, to only remove a variable declaration when it becomes unnecessary due to the transformation described in challenge problem 1, not to remove all unused declarations like in challenge problem 2.

Submit patches, including your semantic patch, based on your results. Does your semantic patch do too much? Think about what information you would need to get a better result.

Coccinelle challenge problem 4

The lustre file system in the staging tree defines the following macro:

#define GOTO(label, rc)                                                 \
do {                                                                    \
        if (cfs_cdebug_show(D_TRACE, DEBUG_SUBSYSTEM)) {                \
                LIBCFS_DEBUG_MSG_DATA_DECL(msgdata, D_TRACE, NULL);     \
                libcfs_log_goto(&msgdata, #label, (long_ptr_t)(rc));    \
        } else {                                                        \
                (void)(rc);                                             \
        }                                                               \
        goto label;                                                     \
} while (0)

In practice, the "then" branch of the if is debugging code, and it is only the code in the else branch that is useful, as well as the goto that is after the if. To put it another way, you can pretend that the test expression of the "if" always has the value false. The GOTO macro is not standard in Linux, and it would be nice to get rid of it. Write a semantic patch to make the required transformation.

Coccinelle challenge problem 5

Continuing with the GOTO macro, you may find that in many cases the rc argument can be dropped completely. In what case should it be kept? In what case should it be dropped? Write a semantic patch that gives a pleasant result. <b>Hint:</b> it may be useful to consider the metavariable types identifier (a variable name like rc) and constant (a number like 0).

<b>Bigger hint:</b> A number of patches making this transformation using Coccinelle have been submitted already. If you are stuck, track them down in the git logs and try to understand what they do.

Coccinelle challenge problem 6

The lustre file system in the staging tree uses a number of macros related to locks. Find their definitions and use Coccinelle to replace them by the corresponding standard Linux functions.

Coccinelle challenge problem 7

If a variable has value 0, then there is no point in combining it with other things with |, as for any x, 0 | x is just x. The following semantic patch finds this problem.

@@
expression x,e,e1;
statement S;
@@

if (x == 0) {
  ... when != x = e1
      when != while(...) S
      when != for(...;...;...) S
(
*  x |= e
|
*  x | e
)
  ... when any
}
  1. Apply the semantic patch to the Linux kernel and make some corresponding changes by hand. Note that the result of a semantic patch that uses * is something like a patch with a - at the beginning of any line that contains a match of the starred pattern.

  2. Consider how you could extend the semantic patch to fix the code rather than just finding possible occurrences of the problem. Hint: it may work best to change the first "..." to <... and to change the "... when any" to just ...>.

Note that there are very few occurrences of this problem in staging. If someone else has done this problem, you may need to look elsewhere in the kernel.

Coccinelle challenge problem 8

The file include/linux/list.h contains some very useful functions for iterating over doubly linked lists. Some of these functions are <code>list_for_each</code>, <code>list_for_each_entry</code>, <code>list_for_each_safe</code>, and <code>list_for_each_entry_safe</code>. Some other functions related to doubly linked lists are <code>list_empty</code> and <code>list_entry</code>. Sometimes when <code>list_empty</code> is used in a loop, the code could be better rewritten using eg <code>list_for_each</code>, and sometimes when <code>list_entry</code> is used the code could be better written using eg <code>list_for_each_entry</code>.

Use Coccinelle to improve the code manipulating doubly linked lists, to remove when possible calls to <code>list_empty</code> and <code>list_entry</code>.

<bf>Note:</bf> This is a hard problem. You will need to study very carefully the definitions in include/linux/list.h and to study very carefully the code that uses these definitions, to be sure to be changing the code in the right way. Nevertheless, doubly linked lists are very widely used in the kernel, so it is useful to be familiar with how to manipulate them.

Other Coccinelle challenge problems

You can also try the Old Coccinelle challenge problems from round 8.

Contact info

Email: <Julia.Lawall AT lip6 DOT fr>

My IRC handle is jlawall.

Questions about using Coccinelle should go to the Coccinelle mailing list: <cocci AT systeme DOT lip6 DOT fr>


CategoryHomepage

Tell others about this page:

last edited 2014-09-27 16:11:53 by JuliaLawall