Introduction

A design pattern is a general solution to a design problem, that has proven to be effective and can be reused when similar problems are encountered.

A system in which similar problems are always solved using the same patterns has a consistency and integrity of style that make it easier to understand, easier to modify, and generally more robust.

Studying the design patterns used in the Linux kernel leads to a better understanding the Linux kernel, and the ability to write better modules for it. It can also lead to greater skill as a designer programmer, which will transfer to other applications.

Neil Brown has written two articles on this subject, which should be considered as a starting point:

• Linux Kernel Design Patterns - Part 1
• Linux Kernel Design Patterns - Part 2

The following slides are intended summarize the design patterns described in those articles as well as others that we discover as our course progresses, with some specific illustrations from the Linux kernel sources. Unfortunately, the number of patterns is very large, and we have only been able to make the barest begining toward recording them. A lot more work is needed here.

Anti-Patterns

It is also useful to study anti-patterns, that is patterns of "solutions" to design problems that people seem to come up with frequently, that do not work well or are actually dangerous. Examples do tend to crop up in some device drivers, and especially in kernel code written by novices. As these notes evolve, it may be useful to also document some anti-patterns.

Neil Brown's Patterns

In the articles cited above, Neil Brown suggests the following patterns, which we can consider as a starting point.

• Reference count - a pattern, with some specific forms:
  • kref
  • kcref
  • plain
• Biases in reference counts - an anti-pattern
• Linked lists (list.h), including
  • "Embedded anchors"
  • "Tool box"
• RB trees
• Radix trees
• "Broad interfaces"
• Caller locks
• Preallocate outside locks

Several of the above are data structures, which are an important class of pattern in computer science.

Linux Red-Black Trees

A semi-balanced binary search tree Based on embedded struct rb_node in objects, similar to struct list_head in list.h lists Order log(n) search, insert, and delete - worst case Implemented in Linux as a toolkit, for performance reasons No insert or delete functions Used by block I/O schedulers and packet CD/DVD driver HR timer, ext3 filesystem VM areas, epoll file descriptors, cryptographic keys, network packets, etc.

See Trees II: red-black trees article by Jonathan Corbet, from which the above image is reproduced, for more detail on Linux usage of RB trees.

Linux Radix Trees

Not exactly what is usually meant by a "radix tree" Multi-branching tree, similar in structure to a multi-level page table Location of entry in tree based on partioning key into segments, one per level Not widely used in kernel Main use is to track pages that are dirty or under writeback

See Trees I: Radix trees article by Jonathan Corbet, from which the image above is reproduced, for more details on Linux usage of radix trees.

For interesting other forms of radix trees, see the Patricia Tree and also the the Judy Tred.

Hash Tables

• See hash.h
• hash_64() hashes an unsigned 64-bit integer down to a specified number of bits

Further Reading

See also the pages on locking patterns and miscellaneous patterns.