Coccinelle - Semantic Patch Examples
This document describes a collection of semantic patches that we have used to find and fix bugs in the Linux kernel. Some of them are Linux specific, while others should be applicable to other software. It should be possible to use these examples as a starting point to solve other, similar, problems.- Making use of available macros
- Nonsensical or useless code
- Dereferences of NULL pointers
- Dereferences of invalid pointers
- Resource allocation
- Updating API usage
Making use of available macros
The kernel defines a number of generally useful macros. Some code however either uses the expansion of these macros directly, or defines local macros that do the same thing. To convert this code to use the existing abstractions, we define a semantic patch that has the form of the right-hand side of the macro, with some generalization.ARRAY_SIZE
(array.html, array.cocci). This semantic patch first checks that the header filekernel.h
definingARRAY_SIZE
is included, then converts various code patterns to calls toARRAY_SIZE
and finally removes local macros.The semantic patch could be extended to cases where
kernel.h
is not already included, but it is not easy to add a new include file in the "right" place.The rules for introducing calls to
ARRAY_SIZE
contain parentheses around the matched expression. The isomorphismparen
causes code where these parentheses are absent to also be considered. The isomorphism is applied after the parse tree is constructed for the rule, so dropping the parentheses does not introduce the possibility of associativity problems.One of the rules in this semantic patch checks for a case where the size of the array is divided by the size of the type of its elements. The required type information is often stored in header files. To improve performance, Coccinelle normally only considers the header files in the current directory and those in the include path whose name corresponds to the name of the given C file. The option
-all_includes
causes all of the header files mentioned in the C file to be included. When treating a directory, a header file is processed each time it is included. If there are transformations that affect the header file, these will appear more than once in the output.roundup
andDIV_ROUND_UP
(round.html, round.cocci). This semantic patch is similar to the one for introducingARRAY_SIZE
.BUG_ON
(bugon.html, bugon.cocci). When debugging is enabled,BUG_ON
expands to a conditional that invokesBUG
if its argument is true. The advantage of usingBUG_ON
rather than such a conditional is that when debugging is not desired,BUG_ON
can be defined to expand to nothing at all. This semantic patch converts a conditional that has onlyBUG
in its then branch to a call toBUG_ON
. This transformation, however, is only safe when the tested expression has no side effects. SinceBUG_ON
can discard its argument, the rule checks that this expression does not contain any function calls or assignments. A more complicated rule could be written that would lift such a term out of the conditional test and rewrite the conditional to test the result. In the case of a test expression that does not involve an assignment, this would require introducing a new variable to store the result. Such a variable could be declared as a SmPL metavariable usingfresh identifier
, in which case the user would be prompted for the identifier name.One "function call" that does not have a side effect and is often used in conjunction with
BUG
isunlikely
. The first rule of the semantic patch treats cases involving such calls. It disables the isomorphismunlikely
, which can cause some redundant matches, as anunlikely
expression is an expression itself.
Nonsensical or useless code
Occasionally, one finds code patterns that are just strange or unnecessary. A semantic patch can be used to see whether these patterns occur elsewhere. Some examples are:- The pattern
!x&y
(notand.html, notand.cocci). An expression of this form is almost always meaningless, because it combines a boolean operator with a bit operator. In particular, if the rightmost bit ofy
is 0, the result will always be 0. This semantic patch focuses on the case wherey
is a constant. Another possibility is to consider the case wherey
is an arbitrary expression (notand_exp.html, notand_exp.cocci). This rule contains a disjunction that causes it not to perform the transformation wheny
is itself negated, as an expression of the form!x&!y
can make sense. - The pattern
!E && E1
orE || E1
, whereE1
containsE->fld
(andand.html, andand.cocci). In either case,E->fld
represents a NULL pointer dereference. In each rule of the semantic patch, the header makes it explicit that the body of the rule represents an expression, which solves a SmPL parsing problem. - Two comparisons of the same expression to different constants, connected by a conjunction (andconst.html, andconst.cocci). This rule was contributed by Diego Liziero. It also considers an equivalent case involving disjunction.
-
Applying
sizeof
to the result ofsizeof
(sizeof.html, sizeof.cocci). The rule considers separately the cases where the argument is a type or an expression. It would not be sufficient to replace the argument of the innersizeof
by "...
", because that would only match an expression. -
Checking that an unsigned variable is less than 0 (find_unsigned.html, find_unsigned.cocci). This semantic patch
focuses on expressions that have any kind of unsigned type. A difficulty
is to determine what types are unsigned. Sometimes new type names are
defined using typedef to be some sort of unsigned type, often in a header
file. Running spatch with the option -all_includes, and -I to specify an
inclusion path, if needed, will process those header files that are
explicitly included in the C file. The header files that define types such
as
u8
, however, are sometimes not included directly in the C file, but in some file that the C file includes. Since spatch has no option to include files recursively, it would be necessary to write extra rules to find bugs in the use of these types. -
Applying spin lock operations to a mutex (mutex2.html, mutex2.cocci). This semantic patch fixes cases
where spin lock operations are applied to a variable declared using
DEFINE_MUTEX
.DEFINE_MUTEX
is declared among the metavariables as adeclarer name
meaning that theDEFINE_MUTEX
pattern should be parsed as a variable declaration rather than as a function call. - Converting a string to a signed integer when an unsigned value is
desired (simple.html, simple.cocci). The functions
simple_strtol
andstrict_strtol
convert a string to a signed integer. Sometimes, however, the result is stored in a location having an unsigned type. This semantic patch translates such calls tosimple_strtoul
andstrict_strtoul
, respectively. It considers a type to be unsigned if it is anything other thanint
,long
, ors32
, thus getting around the problem of typedefs in header files encountered in the case of (find_unsigned.html, find_unsigned.cocci). False positives are, however, possible, if some other signed type is used. - A
continue
at the bottom of afor
loop (continue.html, continue.cocci). This semantic patch removes acontinue
in a conditional at the bottom of afor
loop. Unfortunately, due to the control-flow based nature of Coccinelle, this semantic patch sometimes considers a continue to be at the bottom of afor
loop when actually it is not. - A NULL test on an already tested value (notnull.html, notnull.cocci). The first rule in this semantic
patch detects a case where a NULL test on some value
x
is preceded by another NULL testx
that causes a return ifx
is NULL. The next three rules consider whether the NULL test is useful because of some other control-flow path. For NULL tests that are useless, the rulefix
then rewrites some cases where the NULL test is straightforward to eliminate. The Python rule at the end of the semantic patch prints out some information about cases that were not possible to fix. - Zero-testing a pointer-typed value (badzero.html, badzero.cocci). To improve code readability, it
seems better not to compare a pointer-typed value to 0. This semantic
patch distinguishes between two cases: 1) the pointer-typed value is the
result of a function call, and 2) the pointer-type value is something else.
In the former case, the semantic patch uses
!
, with the intuition that the NULL value reflects the failure of the function call, and in the latter case, it uses a comparison to NULL. Other strategies could be implemented. Both rules in the semantic patch disable the isomorphisms is_zero and isnt_zero, which convert comparisons to 0 to simpler expressions involving just the compared value or its negation. For this transformation, we only want cases where there is an explicit comparison to 0. -
Initializing a variable whose value is never used (unused.html, unused.cocci). The first rule finds cases where
the declaration of the variable is labeled
extern
, in which case the initialization may be more useful than it appears locally. This rule records the position of any such initialization in the position metavariablep
. The second rule finds a declaration of a variable that is at a position that is different from any of the recorded ones, and then checks that the only subsequent references to the variable simply initialize it to a constant. In this case, the declaration and all of the initializations are deleted.Other variations could be considered. This semantic patch focuses on constants, because they have no side effects. Variables, however, would have the same property. Another variation would be when a variable is assigned to the result of calling a function, but the value is never used. In this case, the function call cannot be deleted, but it is at least possible that the variable is holding some sort of error code that should be checked or freshly allocated memory that should be stored or freed.
- (Linux specific) A NULL test or
memset
0 after a call toalloc_bootmem
(bootmem.html, bootmem.cocci). The Linux functionalloc_bootmem
and variants all initialize the allocated data to 0 and panic if the allocation is not possible. This semantic patch removes any subsequent NULL test ormemset
when there is no previous reference to allocated data. The constraint that there be no previous reference to the allocated data is particularly important in thememset
case, as thememset
could be useful if it serves to reset the allocated memory to 0. In the NULL test case, the constraint could be relaxed to check only that there is no intervening reassignment, but it does not seem likely that this would find more bugs, since normally a NULL test would come before any accesses.
Dereferences of NULL pointers
The first of the following semantic patches detects the general case where a pointer is dereferenced and then compared to NULL. Such a comparison is ineffective, because if the value is NULL the kernel has already crashed at the point of the dereference. The remaining semantic patches consider some frequent cases that are possible to fix automatically.- A semantic match that detects a dereference followed by a test for NULL
(null_ref.html, null_ref.cocci). The first rule is a disjunction
that detects a variety of patterns that may involve a dereference. The
first 6 disjuncts consider cases that are not bugs. The last finds a
dereference followed by a NULL test and stores the position of each in
p1
andp2
, respectively. The first two disjuncts seem redundant, since one matches an assignment as a statement and the other matches an assignment of the same form, but as an expression. The first case actually only serves to indicate to the SmPL parser that this rule is a disjunction of statements, as is needed to parse the final disjunct containing "...
", and not a disjunction containing only expressions.The next two rules consider the possibility that the NULL test is there because of some other path that does not go through the dereference. In the first case, the path starts with an assignment of the location of interest, while in the second case there is no assignment and the path starts at the beginning of the function definition.
The last rule prints out the result in emacs org mode format, providing links to the dereference and the NULL test.
-
A semantic patch that corrects a common case where the dereference is in
the initialization of a local variable and the NULL test is at the
beginning of the function body (mini_null_ref.html, mini_null_ref.cocci). Unlike the previous
semantic match, which only collects the locations of the bug sites, this
semantic patch corrects the bug, by moving the initialization after the
NULL test. The conditional in this semantic patch matches any of the
following cases: 1) The then branch is a
return
, with or without an argument, 2) The then branch is a sequence of statements ending in areturn
, with or without an argument, 3) The then branch is a sequence of statements ending in agoto
, which ultimately leads to a return. - A semantic patch that corrects an occasional typographical error, where a test compares a structure to NULL rather than comparing its recently initialized field. (mini_null_ref2.html, mini_null_ref2.cocci).
- A semantic patch that corrects a common case where the dereference is in the argument of a function call which appears just before a NULL test (mini_null_ref3.html, mini_null_ref3.cocci). In practice, the function call is typically debugging code. In this semantic patch, we have not tried to be very general, but instead search only for the case where the function call is immediately before the NULL test. This is the case that seems to occur frequently, according to the output of the above null_ref semantic patch.
- A semantic patch that detects a case where a value is tested for NULL and then dereferenced within the "then" branch of the same test (isnull.html, isnull.cocci).
Dereferences of invalid pointers
Linux uses both NULL and values created using ERR_PTR to indicate a failed operation. A value created using ERR_PTR can also contain a negative integer giving some information about the kind of error that has occurred. This value can be extracted using PTR_ERR. Dereferencing a value created using ERR_PTR is invalid, and thus we can define rules similar to the ones for the NULL case.- (Linux specific) Detect a dereference followed by an IS_ERR test (iserr_ref.html, iserr_ref.cocci). This rule is simpler than the one for the NULL case (null_ref.html, null_ref.cocci), and thus it could potentially find more false positives. However, IS_ERR is less common than a test for NULL, so the simpler rule seems to work well enough in practice. This rule could certainly be extended to the cases considered by the one for the NULL case if desired.
- (Linux specific) A semantic patch correcting a case where a value is compared to NULL and subsequently passed to PTR_ERR (ptr.html, ptr.cocci).
Resource allocation
Resources that are allocated should be deallocated. Some resources, such as locks or mutexes, are typically acquired and released within a single function. Others, such as memory, are often held beyond the lifetime of the allocating function, but should be freed in an error situation. The semantic patches for finding resource allocation bugs are Linux specific, in that the API functions considered are specific to the Linux kernel. Nevertheless, these rules can easily be adapted to other APIs.- (Linux specific) A semantic patch detecting a case where a mutex is not
released in error handling code (mut.html, mut.cocci). This rule matches the case where a call
to
mutex_lock
is followed on every control-flow path either by a call tomutex_unlock
or a conditional ending in a return, which is assumed to represent error-handling code. If such a conditional does not contain a call tomutex_unlock
, then this is assumed to be a bug, and one is added by the semantic patch. - (Linux specific) A semantic patch detecting a case where a call to
kmalloc
or a related function is not followed by a call tokfree
(kmalloc.html, kmalloc.cocci). This semantic patch makes the constraints that the variable storing the result of callingkmalloc
is a local variable and that the only reference to this variable between the allocation point and the return is an initialization of its fields. The former constraint ensures that at the point of the allocation, there is no pointer accessible from outside the function to the allocated data. The latter constraint ensures that no such pointer is created, eg by passing the allocated data to another function which stores it in a global data structure.Often, Linux error handling code performs a goto to a label at the end of the function that performs a sequence of deallocations. The matching of a goto in the first rule of this semantic patch only serves to record its position to be used in creating the subsequent output, to make it easier to see what control-flow path was used in detecting the bug. The semantic patch contains two rules for printing out the results. The first rule is used only if the position,
p3
, of a goto is available. This rule ends incocci.include_match(False)
, indicating the bindings used in this rule should be discarded. The second rule is then used for the other possible bindings, for the cases where there is no goto. - (Linux specific) Missing calls to
pci_dev_put
(add_pci_dev.html, add_pci_dev.cocci).pci_get_device
and some related functions have the property that they take an argument that is the starting point of a search, and after completing the search they decrement the reference count of this argument. This behavior is particularly convenient for iterating over a sequence of objects, as when the iteration completes all objects have been freed without any explicit reference count manipulation. When there is an early return from within such a loop, however, it may be necessary to decrement the reference count explicitly. This semantic patch detects and fixes such returns forwhile
andfor_each_pci_dev
loops. In each case, the iteration variable is declared aslocal idexpression
, to ensure that it is a local variable, and thus not visible from outside the function.for_each_pci_dev
is declared as aniterator name
in the second rule, so that it will be parsed correctly. - (Linux specific) Missing calls to
of_node_put
andscsi_device_put
(missing_put.html, missing_put.cocci). This rule is similar to the previous one, but it focuses on loop types that imply different reference count functions. Each of the various loop types is declared usingiterator name
in only the first rule in which it appears. It is then considered to be aniterator name
throughout the rest of the semantic patch. - (Linux specific) Missing calls to
local_irq_restore
(local.html, local.cocci). A call tolocal_irq_save
should normally be followed by a call tolocal_irq_restore
along all paths. This rule useswhen any
to allow any number of conditionals to appear between then call tolocal_irq_restore
and the matched conditional (otherwise matching would stop at the first conditional, due to the shortest path constraint on "...
"), andwhen strict
to ensure that all paths are checked, even those that are considered to be error paths (normally constraints on error paths are relaxed, as the code cannot be expected to eg free something if its allocation has failed). - Other missing deallocations (alloc_free.html, alloc_free.cocci). This can be viewed as a
semantic match template rather than a semantic match; it contains
the tokens
ALLOC
andFREE
that have to be manually replaced by the name of an allocation function and its corresponding deallocation function before using the sematic match. This semantic match targets more specialized resource allocation protocols thankmalloc
/kfree
. It puts fewer constraints on what it reports as bugs, and thus may return more false positives, in particular because it allows the allocated value to be passed to another function, which may save it in some way, implying there is no need for a deallocation. However, the more specialized allocation functions are used less often, and thus we have not found the number of false positives to be burdensome in practice. If desired, one could replacekmalloc
andkfree
in the kmalloc rule by the names of other allocation and deallocation functions and obtain potentially fewer false positives, but potentially more false negatives as well.Concretely, the semantic match focuses on the allocation site (storing the result in a local variable) and each subsequent return that does not return either 0, some expression involving the allocated value, or some other non-NULL pointer. Between these points, the semantic match checks that there is no call to the deallocation function, either directly or under a conditional, that the return is not in a control-flow path that checks that the result of the allocation function is NULL, and that the allocated value has not been stored somewhere or overwritten. If these cases are satisfied, the Python script prints the position of the call to the allocation function and of the return.
The constraints on a return that is considered of interest and the path between the call to the allocation function are purely heuristic and may give good or bad results depending on how the allocation function is expected to be used. For example, the constraint that a return of 0 is not of interest derives from the assumption that 0 represents success and in a success case, all allocated memory has been saved or freed in some way, even if it is not apparent to the semantic patch. This assumption may be reasonable in the case of an allocation function that is based on
kmalloc
, but we have found that it is less likely to be valid in the case of an "allocation" function whose effect is to increment a reference count. Often a reference count should be both incremented and decremented within a single function (similar to a lock), and thus should in particular be decremented even if the containing function succeeds.Some pairs of allocation and deallocation functions that we have considered are
ioremap
/iounmap
,auth_domain_find
/auth_node_put
,of_find_node_by_name
/of_node_put
, andpci_get_slot
/pci_dev_put
. Semantic patches for these, that are slightly different from alloc_free.cocci in that they try to correct the bug when possible, are available in (iounmap_check.html, iounmap_check.cocci), (auth.html, auth.cocci), (ofname1.html, ofname1.cocci), (get_slot.html, get_slot.cocci), respectively. By trying to correct the bug, however, these semantic patches may be less successful than the corresponding instantiations of alloc_free.cocci, because they can fail when multiple control-flow paths reach a return, as this is considered to provide inconsistent information as to how the return should be updated.
Updating API usage
- (Linux specific)
SPIN_LOCK_UNLOCKED
(sl.html, sl.cocci).SPIN_LOCK_UNLOCKED
is deprecated, as described in the Linux fileDocumentation/spinlocks.txt
. The semantic patch handles the case of a variable declaration or a dynamic initialization.DEFINE_SPINLOCK
is declared as adeclarer name
so that the SmPL parser knows that it is a valid replacement for a variable declaration; ifDEFINE_SPINLOCK
were considered to be the name of a function, it would not satisfy this constraint, resulting in a parse error.The case where
SPIN_LOCK_UNLOCKED
is used in a structure initialization cannot be handled in general, because it would be necessary to accumulate an arbitrary number of structure fields as the argument of__SPIN_LOCK_UNLOCKED
. Coccinelle could be used to find such uses ofSPIN_LOCK_UNLOCKED
, which then could be updated by hand. - (Linux specific)
kmalloc/memset
conversion (kzalloc.html, kzalloc.cocci). This semantic patch translates a call tokmalloc
followed by a call tomemset
into a single call tokzalloc
that performs both operations. Many cases are considered to ensure that the call tomemset
is intended to initialize to zero the complete allocated data, rather than e.g., to reinitialized it after performing some other operations. The semantic patch also converts calls tokzalloc
where the first argument is a product of the size of a structure and some other value to a call tokcalloc
. The latter function performs an overflow check before performing the multiplication.