In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, Sparse is a tool designed to find possible coding faults in the Linux kernel

Linux kernel

The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....

. This static analysis

Static code analysis

Static program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...

 tool differed from other such tools in that it was initially designed to flag constructs that were only likely to be of interest to kernel developers, e.g. mixing pointers to user address space

Address space

In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.- Overview :...

 and pointers to kernel address space.

Sparse contains built-in checks for known problematic and a set of annotations designed to convey semantic information about types

Data type

In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...

, such as what address space pointers point to, or what locks a function acquires or releases.

Linus Torvalds

Linus Torvalds

Linus Benedict Torvalds is a Finnish software engineer and hacker, best known for having initiated the development of the open source Linux kernel. He later became the chief architect of the Linux kernel, and now acts as the project's coordinator...

 started writing Sparse in 2003. Josh Triplett was the maintainer of Sparse from 2006, a role taken over by Christopher Li in 2009. Li is the current maintainer. Sparse is released under the Open Software License

Open Software License

The Open Software License is a software license created by Lawrence Rosen. The Open Source Initiative has certified it as an open source license, but the Debian project judged version 1.1 to be incompatible with the DFSG...

, version 1.1.

Annotations

Some of the checks performed by Sparse require annotating the source code using the __attribute__ GCC

GNU Compiler Collection

The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...

 extension, or the Sparse specific __context__ specifier. Sparse defines the following list of attributes:

• address_space(num)
• bitwise
• force
• context(expression,in_context,out_context)

When an API is defined with a macro, the specifier __attribute__((context(...))) can be replaced by __context__(...).

Linux kernel definitions

The Linux kernel defines the following short forms as pre-processor macros in files linux/compiler.h and linux/types.h (when building without the __CHECKER__ flag, all these annotations are removed from the code):

1. ifdef __CHECKER__
2. define __kernel __attribute__((address_space(0)))
3. define __user __attribute__((noderef, address_space(1)))
4. define __iomem __attribute__((noderef, address_space(2)))
5. define __percpu __attribute__((noderef, address_space(3)))
6. define __safe __attribute__((safe))
7. define __force __attribute__((force))
8. define __nocast __attribute__((nocast))
9. define __acquires(x) __attribute__((context(x,0,1)))
10. define __releases(x) __attribute__((context(x,1,0)))
11. define __acquire(x) __context__(x,1)
12. define __release(x) __context__(x,-1)
13. define __cond_lock(x,c) ((c) ? ({ __acquire(x); 1; }) : 0)

extern void __chk_user_ptr(const volatile void __user *);
extern void __chk_io_ptr(const volatile void __iomem *);

1. else
2. define __kernel
3. define __user
4. define __iomem
5. define __percpu
6. define __safe
7. define __force
8. define __nocast
9. define __acquires(x)
10. define __releases(x)
11. define __acquire(x)
12. define __release(x)
13. define __cond_lock(x,c) (c)
14. define __chk_user_ptr(x) (void)0
15. define __chk_io_ptr(x) (void)0
16. endif

1. ifdef __CHECKER__
2. define __bitwise__ __attribute__((bitwise))
3. else
4. define __bitwise__
5. endif

1. ifdef __CHECK_ENDIAN__
2. define __bitwise __bitwise__
3. else
4. define __bitwise
5. endif

Examples

The types __le32 and __be32 represent 32-bit integer types with different endianness

Endianness

In computing, the term endian or endianness refers to the ordering of individually addressable sub-components within the representation of a larger data item as stored in external memory . Each sub-component in the representation has a unique degree of significance, like the place value of digits...

. However, the C language does not allow to specify that variables of these types should not be mixed. The bitwise attribute is used to mark these types as restricted, so Sparse will give a warning if variables of these types or other integer variables are mixed:

typedef __u32 __bitwise __le32;
typedef __u32 __bitwise __be32;

To mark valid conversions between restricted types, a casting with the force attribute is used to avoid Sparse giving a warning.

External links

• Sparse web page
• Using sparse for typechecking, Linux Kernel Documentation