{"id":1824,"date":"2019-02-27T21:14:30","date_gmt":"2019-02-28T02:14:30","guid":{"rendered":"http:\/\/codinggorilla.com\/?p=1824"},"modified":"2019-03-13T20:03:14","modified_gmt":"2019-03-14T00:03:14","slug":"program-transformational-systems-coccinelle","status":"publish","type":"post","link":"http:\/\/165.227.223.229\/index.php\/2019\/02\/27\/program-transformational-systems-coccinelle\/","title":{"rendered":"Series on program transformation systems: Coccinelle (2006)"},"content":{"rendered":"\n

Due to my work on Piggy, I’m starting to do a thorough review of the literature on program transformation systems, how Piggy relates to prior research, and what improvements I can make to Piggy. Note, a good list to start from is in Wikipedia<\/a>: ASF+SDF, CIL (for C), Coccinelle (for C), DMS, Fermat, Spoon (for Java), Stratego\/XT, TXL). This is the first entry in the series, on Coccinelle<\/a>, a system that modifies C<\/g> source code.<\/p>\n\n\n\n\n\n\n\n

Coccinelle has its roots in the analysis of software for detecting bugs in device drivers in Linux [Padioleau, Lawall, Muller 2006]. In this work, the authors were trying to solve the problem of taking a bug fix of some code and applying the fix across the entire source code base. Coccinelle<\/g> represents the program as a control-flow graph (CFG), and a language used to make transformations, SmPL<\/a>, which represents computational tree logic (CTL). The pattern language uses a syntax that specifies the pattern and fix for source code transformations together. Patterns are written in C language, and the replacement code with “+” and “-“. So, patterns should be easy to construct. Note, Coccinelle does not guarantee semantics are preserved [Jones, Hansen 2007], but this isn’t usually a problem in practice. It also represents the C program prior to preprocessing in order to preserve the original look of the program.<\/p>\n\n\n\n

Taking a closer look at their example, the bug is in pcf8563_remove<\/a>(), where the function fails to clear the client data before calling kfree<\/g>(). This is a dangling pointer, which is usually fixed by just clearing the buffer that contains the pointer so that it is never used. Patch can’t be used because the format of the code may interfere with the problem being recognized. Further, it doesn’t allow one to express missing function calls and various ways of writing the code.<\/p>\n\n\n\n

    static int pcf8563_remove(struct i2c_client *client)\n    {\n        struct pcf8563 *pcf8563 = i2c_get_clientdata(client);\n\n        if (pcf8563->rtc)\n            rtc_device_unregister(pcf8563->rtc);\n\n        kfree(pcf8563);\n\n        return 0;\n    }<\/code><\/pre>\n\n\n\n
The pattern to correct the problem detects whether there isn’t a call to i2c_set_clientdata() before the kfree(). If the pattern is detected, the call to  
i2c_set_clientdata () is inserted.<\/p>\n\n\n\n
    @@\n    type T;\n    identifier client, data;\n    @@\n\n    \/\/ Check if function uses clientdata\n    (\n        i2c_set_clientdata(client, data);\n    |\n        data = i2c_get_clientdata(client);\n    |\n        T data = i2c_get_clientdata(client);\n    )\n        \/\/ Anything in between is OK\n        ...\n    (\n        \/\/ If this pattern is found, clientdata is set to NULL before data is freed.\n        \/\/ Do nothing and skip the rest of the alternation\n        i2c_set_clientdata(client, NULL);\n        ...\n        kfree(data);\n    |\n        \/\/ If this pattern is found, clientdata is set to NULL after data is freed.\n        \/\/ Move it to the front and skip the rest of the alternation\n    +\ti2c_set_clientdata(client, NULL);\n        kfree(data);\n        ...\n    -\ti2c_set_clientdata(client, NULL);\n    |\n        \/\/ Otherwise apply a fix if kfree() has been found in some code path\n        \/\/ (doesn't need to be in all paths).\n    +\ti2c_set_clientdata(client, NULL);\n    ? \tkfree(data);\n    )<\/code><\/pre>\n\n\n\n
Observations and notes<\/h2>\n\n\n\n