F23 Online Resources

There are numerous web sites devoted to Linux kernel development which provide useful information. Because of the web's rapidly changing structure, it does not really make sense to present a comprehensive survey here, since most links will tend to become outdated rather quickly. However, relying only on your favorite search engine to grab useful links about kernel development is also not the easiest path to success, especially when it comes to judging relevance and quality of the results. Therefore, the following list presents a selection of some fine links that are among the author's personal favorites (naturally, this selection is subjectively biased, but it's a good starting point):

□ The current kernel source code as well as many essential userspace tools are available from www.kernel.org. Numerous git source code repositories are listed on git.kernel.org.

www.lwn.net is the premier source for regular, weekly updates on the kernel development process. And these updates are not just for the kernel. Interesting news about all aspects of Linux development and related events in the IT community are collected on this site, and well-researched articles provide insightful updates on the state of the art of various projects.

Content is provided free of charge one week after it has been published initially, but the most current information is available to subscribers only. Since the fee is small, I highly recommend that you subscribe as soon as possible!3

□ Full-scale change logs of the kernel can easily take a number of megabytes in size. Although they meticulously register every commit that was accepted since the last release, it is practically not possible to get a broad overview of what has happened in kernel development. Thankfully, www.linuxnewbies.net provides less-detailed change logs that put more emphasis on the big picture than small individual details.

□ The Linux Foundation provides a ''weather forecast'' service that tries to predict which patches and features are going to be accepted into future kernel versions. This is as close to a road map as the Linux kernel can get, and provides valuable information on the direction that development is heading in. The URL is www.linux-foundation.org/en/Linux_Weather_Forecast.

F.3 The Structure of Patches

Kernel developers expect that good patches fulfill certain fixed criteria. Although this puts more load onto the preparer of a patch, it makes things much easier for maintainers, reviewers, and testers because less time is required to understand individual changes if they all follow identical conventions. The kernel includes detailed instructions on how to prepare patches, which can be found in Documentation/SubmittingPatches. This section summarizes the essential points, but be sure to read the whole SubmittingPatches document before you send code to any maintainer or mailing list. Further advice is given in Andrew Morton's ''The Perfect Patch'' document, available on www.zip.com.au/~akpm/linux/patches/stuff/tpp.txt, and on the web site linux.yyz.us/patch-format.html.

First and foremost, it is essential to break larger changes into pieces that are easier to digest than a single patch that touches 10 million files across 50,000 subdirectories. A patch should do one logical change to the source code, even if that means that more than one patch in a patch series changes the same file. Ideally, patches should be stackable — that is, it should be possible to apply them independent of each other. However, owing to the nature of changes, this is not always possible, and in this case, the correct temporal ordering of the patches should be documented.

In principle, patch series can be created by hand using diff and patch as described in Appendix 2. This can become quite tedious after a while, but the quilt toolbox available on http://savannah.nongnu.org/projects/quilt provides some relief here by automating most of the process of managing patch stacks.

F.3.1 Technical Issues

As for the technical format of a patch, notice that a unified patch that includes information on the C functions being changed is required. Such a patch can be generated using diff -up. If the patch adds new files or concerns files in multiple subdirectories, then diff -uprN must be used to account for these cases. Appendix 2 discusses what the resulting patch looks like and which information it contains.

3 And, no, I have no commercial interests nor any relation to LWN whatsoever. But the site is just awesome.

Coding Style

The kernel has some coding style requirements, which are defined in Documentation/CodingStyle. Although not all developers agree about each requirement in this file, many are very sensitive about coding-style violations. Having a common coding style is a good thing. The kernel contains vast amounts of code, and digging through patches and files that use all different conventions can become a real nuisance. Thankfully, the kernel displays less-religious zeal about coding style than other projects, but there is a clear opinion on what is not the ultimate fashionable style, as you can see in the following documentation snippet:

Documentation/CodingStyle

First off, I'd suggest printing out a copy of the GNU coding standards, and NOT read it. Burn them, it's a great symbolic gesture.

But what do developers expect? The essential points are as follows:

□ Different levels are always one tab apart, and one tab is always eight spaces long. This might seem quite excessive for programmers who've had much exposure to userland code before, but this is different in the kernel world. Naturally, code will tend to shift quickly to the right side of the screen after a few indentation levels, but this serves as a warning sign: Code that needs too many levels of indention should usually be replaced with something cleaner, or be split into functions, and then the problem will automatically go away.

Large indentations often cause strings and procedure arguments to exceed the 80-column boundary, and they must be sensibly broken into chunks. You have seen numerous examples of this all over the book.

In addition to the aforementioned reasons, many kernel developers tend to have rather unusual working practices, and long hacking sessions are not uncommon. After having written tons of beautiful code three days in a row without a break, vision tends to get blurred, and large indentations do definitely help in this situation (along with copious amounts of caffeinated beverages).

□ Opening braces are put last on the line they are contained in, and closing braces are put first on their line. When a control statement is continued (as for else branches, or while conditionals in do loops), the continuation statement is not put on a new line, but after the closing brace. If a block contains only a single statement, no extra braces are necessary. In fact, they are even discouraged (just think of how much typing you will save over your whole life by this convention).

Functions follow a separate convention: The opening and closing brackets are both on separate lines.

The following code contains examples for the above rules: kernel/sched.c static void update rq clock(struct rq *rq) {

u64 prev_raw = rq->prev_clock_raw; u64 now = sched_clock();

* Catch too large forward jumps too:

if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) { if (clock < rq->tick_timestamp + TICK_NSEC)

clock = rq->tick_timestamp + TICK_NSEC;

if (unlikely(delta > rq->clock_max_delta))

□ No surrounding space should be used inside parentheses, so if ( condition ) is frowned upon, while if (condition) will be universally loved. Keywords like if are followed by a space, whereas function definitions and functions calls are not. The preceding code excerpt also contains examples of these rules.

□ Constants should be represented by macros or elements in enum enumerations, and their names should be in all capital letters.

□ Functions should typically not be longer than one screen (i.e., 24 lines). Longer code should be broken into multiple functions, even if the resulting auxiliary functions will have only a single caller.

□ Local variable names should be short (and firm), and not tell the story of a complete novel like OnceUponATimeThereWasACounterWhichMustBelntializedWithZero. You can also use tmp, which also protects you from breaking your fingers during interaction with the keyboard.

Global identifiers should tell a little more about themselves because they are visible in all contexts. prio_tree_remove is a fine name for a global function, whereas cur and ret are only apt for local variable names. Names composed of multiple expressions should use underscores to separate the constituents, and not employ mixed lower/uppercase letters.

□ Typedefs are considered to be an incarnation of the devil because they hide the actual definition of an object, so they should usually not be employed. It might save the creator of a patch some typing, but will make reading harder for all other developers.

However, sometimes it is necessary to hide the definition of a data type, such as when a quantity must be implemented differently depending on the underlying architecture, but common code should not notice this. For instance, consider the atomic_t type used for atomic counters, or the various page table elements like pte_t, pud_t, and so on. They must not be accessed and modified directly, but only via special auxiliary functions, so their definition must not be visible to generic code.

All these rules and more are discussed in depth in the coding style document Documentation/ CodingStyle, together with the rationale behind them (including the all-important rule number 17: Don't re-invent the wheel!) Accordingly, it does not make sense to repeat the information in the coding style here — the document comes with every kernel, so go and enjoy it there! Besides, when reading through the kernel sources, you will familiarize with the desired style very quickly.

The following two utilities can help to obey the desired coding style:

□ Lindent, located in the kernel's scripts/ directory, feeds GNU indent with command-line options to re-indent a file according to the indentation settings preferred by the kernel.

□ checkpatch.pl, likewise located in the scripts/ directory of the kernel source tree, scans a patch for violations of the coding style and can provide appropriate diagnostics.

Portability

The kernel runs across a wide range of architectures, and these differ widely in the various restrictions they impose on C code. One of the prerequisites for new code is that it is portable and will run on all supported architectures as far as this is possible in principle. This book has previously covered the differences between architectures and ways to circumvent those differences. Here is a reminder of some important issues that must be considered when code is written for the kernel:

□ Use proper locking to ensure that your code runs safe in multiprocessor environments. Thanks to the preemptible kernel, this is also important on uniprocessor systems.

□ Always write code that is neutral with respect to endianess. Your code must function on both little and big endian machines.

□ Do not assume that page frames are 4 KiB in size, but employ page_size instead.

□ Do not assume any specific bit widths for any data type. When a fixed number of bits is required, always use explicitely sized types like u16, s64, and so on. However, you can always assume that sizeof(long) == sizeof(void *).

□ Do not use floating point calculations.

□ Keep in mind that the stack size is fixed and limited.

Documenting Code

In addition to documenting patch submissions, it is also important to document your code — especially functions that can be called from other subsystems or drivers. The kernel uses the following special form of C comments for this purpose:

fs/char_dev.c

* register_chrdev() - Register a major number for character devices.

* @major: major device number or 0 for dynamic allocation

* @name: name of this range of devices

* @fops: file operations associated with this devices

* If @major == 0 this functions will dynamically allocate a major and return

* its number.

* If @major > 0 this function will attempt to reserve a device with the given

* major number and will return zero on success.

* Returns a -ve errno on failure.

* The name of this device has nothing to do with the name of the device in

* /dev. It only helps to keep track of the different owners of devices. If

* your module name has only one type of devices it's ok to use, for example, the name

* of the module here.

* This function registers a range of 256 minor numbers. The first minor number

int register_chrdev(unsigned int major, const char *name, const struct file_operations *fops)

Notice that the comment line starts with two asterisks. This identifies the comment as a kerneldoc comment. Functions prefixed by such comments will be included in the API reference, which can be created with make htmldocs and similar commands. Variable names must be prefixed with the @ sign and will be formatted accordingly in the generated output. The comment should include the following:

□ A description of the parameters that specifies what the function does (as opposed to how the function does this).

□ The possible return codes and their meanings.

□ Any limitations of the function, the range of valid parameters, and/or any special considerations that must be taken into account.

F.3.2 Submission and Review

This section describes two important social components of kernel development: Submitting patches to mailing lists, and the subsequent review process.

Preparing Patches for a Mailing List

Most patches are submitted to the mailing list of the respective subsystem before they are considered for inclusion into any kernel tree — unless you are a top-notch kernel contributor who submits patches directly to Linus or Andrew (in which case, you would probably not be reading this anyway ... ). Again, there are some conventions that should be obeyed as described here:

□ Subject lines start with [patch] , and the rest of the subject should give a concise description of what the patch is all about. A good subject is very important because it is not only used on the mailing list, but in the case of an acceptance, it will appear in the git change logs.

□ If a patch is not supposed to be applied directly, or if it requires more discussion, it can be marked with an additional identifier such as [RFC] .

□ Larger changes should be split up into multiple patches with one logical change per patch. Likewise, you should send only one patch per e-mail. Each should be numbered as [patch m/N], where m is a counter and N is the total number of patches . [patch 0/n] should contain an overview about the follow-up patches.

□ A more detailed description of each patch should be contained in the e-mail body. Again, this text will not get lost after the patch is integrated, but will find its way into the git repository where it serves to document the changes.

□ The code itself should be directly present in the e-mail, without using any form of base64

encoding, compression, or other fancy tricks. Attachments are also not particularly favored, and the preferred way is to include the code directly. Any material that should be included in the description but is not supposed to go into the repository must be separated from the patch by three dashes on a single line.

Naturally, the code should not be line-wrapped by the e-mail client as there are rumors that compilers sometimes have a very hard time accepting randomly wrapped code. And after all that has been said, a remark that HTML e-mails are inappropriate is likely superfluous.

Below the e-mail subject lines of the submission of an experimental patch are shown. They obey all the conventions discussed before:

[PATCH 0/4] [RFC] Verification and debugging of memory initialisation Mel Gorman (Wed Apr 16 2008 - 09:51:19 EST)

[PATCH 1/4] Add a basic debugging framework for memory initialisation Mel Gorman (Wed Apr 16 2008 - 09:51:32 EST)

[PATCH 2/4] Verify the page links and memory model Mel Gorman (Wed Apr 16 2008 - 09:51:53 EST) [PATCH 3/4] Print out the zonelists on request for manual verification Mel Gorman (Wed Apr 16 2008 - 09:52:22 EST)

[PATCH 4/4] Make defencive checks around PFN values registered for memory usage Mel Gorman (Wed Apr 16 2008 - 09:52:37 EST)

Notice that the four messages containing the actual code have been posted as replies to the first, introductory message. This allows many mailer clients to group the posts, which makes it easier to recognize the patches as one entity.

Take a look at the contents of the first mail:

This patch creates a new file mm/mm_init.c which memory initialisation should be moved to over time to avoid further polluting page_alloc.c. This patch introduces a simple mminit_debug_printk() function and an (undocumented) mminit_debug_level command-line parameter for setting the level of tracing and verification that should be done.

Signed-off-by: Mel Gorman <[email protected]>

mm/mm_init.c | 40 ++++++++++++++++++++++++++++++++++++++++

4 files changed, 60 insertions(+), 7 deletions(-)

(PATCH)

After an overview about the code, the diff statistics produced by diffstat are attached. These allow to quickly identify how many changes a patch introduces in terms of added and deleted lines, and where these changes are bound to happen. This statistical information is interesting for discussion of the code, but has no purpose in long-term changelogs (after all, the information can be generated from the patch), so it is placed after a three-dash line. This is followed by the patch as generated by diff, but as this is not relevant to this discussion, it is not reproduced here.

Origin of Patches

The description also contains a signed-off line, which identifies who wrote the patch, and serves as a bona fide statement that the author has the right to publish the code as open source, usually covered by the GNU General Public License (GPL), version 2.

Multiple persons can sign off a patch, even if they are not direct authors of the code. This signals that the signer has reviewed the patch, is intimately acquainted with the code, and believes to the best of his knowledge that it will work as announced and not cause data corruption, set your laptop on fire, or do other nasty things. It also tracks the path a patch has made through the developer hierarchy before it finally ended up in the vanilla kernel. Maintainers are heavily involved in signing off, because they have to review a fair amount of code that they have not written themselves for inclusion in their subsystems.

Only real names will be accepted for signed-off-lines — pseudonyms and fictitious names must not be used. Formally, signing off a patch means that the signer can certify the following:

Documentation/SubmittingPatches

Developer's Certificate of Origin 1.1

By making a contribution to this project, I certify that:

(a) The contribution was created in whole or in part by me and I have the right to submit it under the open source license indicated in the file; or

(b) The contribution is based upon previous work that, to the best of my knowledge, is covered under an appropriate open source license and I have the right under that license to submit that work with modifications, whether created in whole or in part by me, under the same open source license (unless I am permitted to submit under a different license), as indicated in the file; or

(c) The contribution was provided directly to me by some other person who certified (a), (b) or (c) and I have not modified it.

(d) I understand and agree that this project and the contribution are public and that a record of the contribution (including all personal information I submit with it, including my sign-off) is maintained indefinitely and may be redistributed consistent with this project or the open source license(s) involved.

Signing patches off was introduced to kernel development at a rather late stage, essentially as a reaction to a claim by a ''three-letter company'' that for various reasons assumed the impression that they would own all the code of the kernel, and therefore all Linux users should give them all their money. Naturally, some developers did not quite agree with this point of view, including Linus Torvalds himself:4

Some of you may have heard of this crazy company called SCO (aka "Smoking

Crack Organization") who seem to have a hard time believing that open

4Accusing people of smoking crack is, by the way, not completely uncommon on the Linux kernel mailing list, where conversations can sometimes be rough.

source works better than their five engineers do. They've apparently made a couple of outlandish claims about where our source code comes from, including claiming to own code that was clearly written by me over a decade ago.

In fact, this case is mostly history now, and people (with the possible exception of the CEO of the aforementioned company) are universally convinced that a simple first-fit allocator whose copyright you might possibly own is not quite a complete Unix kernel... Nevertheless, thanks to Signed-off-by tags, it is now possible to precisely identify who wrote which patch.

There are also two weaker forms of marking patches:

□ Acked-by means that a developer is not directly involved with the patch, but nevertheless deems it correct after some review.

This does not necessarily imply that the ACK-ing developer has worked through the complete patch, but may just indicate compliance with the parts that touch the respective field of competence.

If, for instance, an architecture maintainer acknowledges a patch that looks fine with respect to all changes performed in the arch/xyz directory, but that also contains code in fs/ that fries all strings composed of an odd number of chars in files that start with an M, you cannot blame the ACK-ing developer for this.

However, it's highly unlikely that this will ever happen, because architecture maintainers are all very good at what they do, and would detect the subversive wickedness of the patch already by the smell of the file — this example just serves to explain the concept.

□ CC is used to signify that a person has at least been informed about the patch, so he should theoretically be aware of the patch's existence, and had a chance to object.

During the development of kernel 2.6.25, a discussion arose, about the value of code review and how credit should be given to reviewers and one solution to which people agreed was to introduce the Reviewed-By patch tag. The tag states the following:

Documentation/SubmittingPatches

Reviewer's statement of oversight

By offering my Reviewed-by: tag, I state that:

(a) I have carried out a technical review of this patch to evaluate its appropriateness and readiness for inclusion into the mainline kernel.

(b) Any problems, concerns, or questions relating to the patch have been communicated back to the submitter. I am satisfied with the submitter's response to my comments.

(c) While there may be things that could be improved with this submission, I believe that it is, at this time, (1) a worthwhile modification to the kernel, and (2) free of known issues which would argue against its inclusion.

(d) While I have reviewed the patch and believe it to be sound, I do not (unless explicitly stated elsewhere) make any warranties or guarantees that it will achieve its stated purpose or function properly in any given situation.

Another new tag introduced in this context is Tested-by, which — you guessed it — states that the patch has been tested by the signer, and that the test has left enough of the machine to add a Tested-by tag to the patch.

F.4 Linux and Academia

Writing an operating system is not an easy task — as I'm sure you'll agree, it is one of the most involved challenges for software engineers. Many of the developers participating in the creation of the Linux kernel are among the most knowledgeable in their field, given that Linux is one of the best operating systems available. Academic degrees are not uncommon among developers, and computer science degrees are surely not underrepresented degrees.5

Operating systems are also the subject of active academic research. As with every other research field, there's a certain amount of theory that goes along with OS research, and this is just natural — you cannot tackle all problems in a practical way. In contrast to many other research areas that are concerned with fundamental problems, however, OS research works on inherently practical problems, and should therefore have an impact on practical things. What is OS research good for if it does not help to improve operating systems? And because an operating system is an inherently practical product (who, after all, would need a theoretical operating system? Hypothetical computers certainly have no use for an operating system, and even less do real computers require a theoretical OS), the outcome of OS research has to influence practice. People working on loop quantum gravity might be exempted from having to consider the practical impact of their work, but this is certainly not the case for OS research.

With this in mind, one could expect that Linux and the academic community are closely associated, but unfortunately, this is not the case. Quoting academic work in the kernel sources is a rare occurrence, and seeing the kernel being quoted in research papers is also not something that happens every day.

This is especially astonishing because the academic world used to have a close affiliation with Unix, particularly with the Berkeley System Distribution (BSD) family. It's fair to say that BSD is the product of academic research, and for a long time, academia was the driving force behind this project.

A study published by the Linux Foundation [KHCM] has shown that contributions from academia account for 0.8 percent of all changes in recent kernel versions. Considering that a large number of ideas circulate in the academic community, this ratio is astonishingly low, and it would be worthwhile to improve the situation — for the benefit of both the kernel and academia. Open source is all about sharing things, and sharing good ideas is also a worthy goal.

Linux had a slightly bumpy start in its relations with academia. One of Linus Torvalds's initial motivations to write Linux was his dissatisfaction with Minix, a simple teaching operating system designed to educate students. This led to a famous debate between Torvalds and Andrew Tanenbaum, the creator of Minix. Tanenbaum suggested that Linux was obsolete because its design would not comply with

5Notice that I did not perform any quantitative analysis on this, but the curricula vitae of many developers are readily available on the Internet that support this suspicion (as does common sense.)

what the academic world envisioned to be suitable for future operating systems, and his arguments were collected in a Usenet newsgroup posting titled ''Linux is obsolete.'' This, naturally, caused Linus Torvalds to reply, and one of his statements was the following:

Re 2: your job is being a professor and researcher: That's one hell of a good excuse for some of the brain-damages of minix.

Although it was soon admitted that the message was a little rash, it reflects the attitude that is sometimes displayed by the kernel community toward academic research. Real-world operating systems and OS research are perceived as things that don't quite fit together.

This may indeed be true sometimes: Much academic research is not supposed to be integrated into real-world products, especially when it is concerned with fundamental issues. But as mentioned previously, there are also practical components of research, and these could often help to improve the kernel. Unfortunately, OS researchers and OS implementors have somewhat lost connection with each other, and Rob Pike, a member of the former Unix team at Bell Labs, has gone so far as to make the pessimistic claim that systems software research is irrelevant.6

Contributing code to the kernel is hard for researchers for many reasons, one of which is that they have to take many different operating systems into account. It is already hard to keep up with the pace of Linux kernel development, but it is virtually impossible to chase all important operating systems in use today. Therefore, researchers usually cannot provide more than proof-of-concept implementations of their ideas. Integrating these into the kernel requires some effort from both communities. Consider, for instance, the integration of the swap token mechanism into the kernel. This was proposed in research as discussed in the next section, but has been implemented for the kernel by Rik van Riel, a kernel developer working in the area of memory management. The approach has proved to be quite successful, and could well serve as a role model for further collaboration.

Interaction between both communities is complicated by the following two aspects of kernel development:

□ Many developers do not consider proposals without concrete code, and refuse to discuss the issue any further.

□ Even if code is submitted to the mailing lists, a good part of the work will start only after the initial submission. Adaption of proposed code to a specific system is not highly credited in academia, so researchers have a natural tendency to avoid this step.

Ultimately, this leads to the conclusion that the interface between kernel development and academic research ideally requires one individual from each side collaborating with each other. If this is not possible, then it is a definitive advantage and surely worth the effort if researchers try to adapt to the culture of kernel development as much as possible.

F.4.1 Some Examples

This section presents some examples of when research results have been turned into kernel code and could help to improve particular aspects of Linux. Note that the presented selection is naturally not

6See www.cs.bell-labs.com/who/rob/utah2000.pdf. Since Pike also claims that the only progress in the operating system area comes from Microsoft, I certainly don't believe all his claims, but the talk nevertheless contains many noteworthy and valid ideas.

comprehensive, and the impact of academic research would be really negligible if it ever could be. It is primarily used to highlight that both worlds can benefit from each other.

□ The swap token as discussed in Chapter 18 was first described in the paper ''Token-Ordered LRU: An Effective Replacement Policy and its Implementation in Linux Systems'' by S. Jiang and X. Zhang (Performance Evaluation, Vol. 60, Issue 1-4, 2005). Subsequently, it was implemented in kernel 2.6.9 by Rik van Riel. Interestingly, the paper extended kernel 2.2.14 to demonstrate the usefulness of the approach, but the corresponding code was never included in the mainline kernel.

□ The slab allocator as discussed in Chapter 3 is directly based on a paper that describes the implementation of the slab system in Solaris: ''The Slab Allocator: An Object-Caching Kernel Memory Allocator,'' Proceedings of the Summer 1994 USENIX Conference.

□ The techniques of the anticipatory I/O scheduler (which was mentioned in Chapter 6, but not discussed in detail) were first presented in ''Anticipatory Scheduling: A Disk Scheduling Framework to Overcome Deceptive Idleness in Synchronous I/O,'' 18th ACM Symposium on Operating Systems Principles, 2001.

□ As discussed in Chapter 18, Linux employs a variant of the least-recently used technique to identify active pages and distinguish them from inactive pages. The paper ''CLOCK-Pro: An Effective Improvement of the CLOCK Replacement'' by S. Jiang, F. Chen, and X. Zhang (Proceedings of 2005 USENIX Annual Technical Conference) describes a page-replacement algorithm that not only prioritizes pages based on the time of their last access, but also incorporates the frequency with which pages are accessed. Patches have been designed by Rik van Riel and Peter Zijlstra, and the method has also been considered as a possible merge candidate (see www.lwn.net/Articles/147879/). The reason why you have read nothing about this technique in the preceeding chapters is simple: The patches have not yet made it into mainline. They are, however, examples of how Linux developers do sometimes actively try to integrate research results into the kernel.

The ideas presented in these papers have been directly integrated into the Linux kernel as direct extensions of existing code. Some examples of older papers that have had an indirect influence on the kernel include the following:

□ The generic structure of the block layer that acts as a level of indirection between filesystems and disks is described in ''The Logical Disk: A New Approach to Improving File Systems,'' by W. de Jonge, M. F. Kaashoeck, and W. C. Hsieh. Essentially, it describes techniques to decouple blocks on physical disks from logical disks as observed by the operating system, and this builds the fundament for the logical volume manager and the device mapper.

□ Many key concepts of the extended filesystem family originate from other filesystems, and one particular example is the paper ''A Fast File System for UNIX'' by M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry (ACM Transactions on Computer Systems, 1984). It describes the use of multiple possible block sizes on disk, and introduces the idea of mapping a logical sequence of data to a sequential series of blocks on disk.

Tracking the indirect influence of older papers is naturally much harder than seeing ideas from research being directly integrated. The more generic an idea is, the more ubiquitous it will become if it prevails, and the harder it becomes to recognize the idea as such. At some point, it will have been absorbed into the field, and be indistinguishable from common knowledge. Or would you deem it necessary to quote any paper on the fact that computers tend to work with binary digits?

Essentially, most core ideas of the Unix operating system are also present in Linux. Many of these ideas are today ubiquitous, but were new at the time Unix was invented. This includes, for instance, the idea that nearly everything can be represented by a file as discussed in Chapter 8. Namespaces are another example for a technology that does indirectly stem from academic research: They were introduced as an integral part of Plan 9 — the successor to Unix co-developed by some of the inventors of Unix — many years before they were adopted into the mainline kernel.7 The /proc filesystem is also modeled by the example of Plan 9.

Many other fundamental ideas of Unix appear as integral parts of Linux without being recognized as research results, but this is not the direct concern of this section. However, it is interesting to observe where many concepts of Linux have their roots, such as in Vahalia's highly recommended technical discussion of Unix internals for many flavors of the system [Vah96]. The account by Salus [Sal94] illuminates the history of Unix, and allows for understanding why many things are designed the way they are.

F.4.2 Adopting Research

The preceding examples demonstrate that it is possible to integrate research results with the Linux kernel. But considering the magnitude of OS research, and the number of results integrated into the kernel, there seem to be some obstacles to transferring results from one world into another. One essential factor is that each community functions quite differently from each other. To my knowledge this point has not received the consideration it deserves (at least not in writing); therefore, this section highlights some of the essential differences.

Notice that the kernel sources contain some interesting information on how the kernel developers deal with project management issues in Documentation/ManagementStyle. The document also addresses some of the questions discussed here.

Different Communities

Software development and OS research seem to be dry and purely technical to many people, but both have an enormous social component: The acceptance of any work is based on its acceptance in the community, which is nothing else than acceptance by individual developers and researchers. This requires that individuals judge the contributions of other individuals, and as most readers will agree, this is always a difficult thing in a world of colorful, different, and sometimes complicated characters. In an ideal world, judgment would be solely based on objective criteria, but this is not the case in reality: People are only human, and sympathy, personal tastes, acquaintances, dislikes, bias, and the ability to communicate with each other play a crucial role.

One approach to this problem is to simply ignore it — pretend that we live in an ideal world where judgment is done on a purely technical and objective level, and all problems automatically disappear. This solution is adopted astonishingly often, especially in ''official'' statements.

7Notice that Plan 9 was not developed at a ''classical'' academic institution, but at the research division of Bell Labs, which is nowadays affiliated with Lucent Technologies. However, the methodology used is very similar to that of academic institutions: Papers are published about Plan 9, talks are held, and conferences are organized. Therefore, this appendix subsumes it under the same category as academia. The web site cm.bell-labs.com/plan9 contains more information about Plan 9.

But even if the problem is acknowledged, it is not easy to solve. Consider how decisions are often made in the research community to decide if a work is worthwhile (and should be credited by being admitted to a conference, or published in a paper) or not:

1. After research results have (hopefully) been obtained, they are written up in a paper and submitted to a journal (or conference, or similar, but this discussion will focus on publication for simplicity's sake).

2. The paper is submitted to one or more referees who have to evaluate the work. They have to judge correctness, validity, and scientific importance, and can point to weaknesses or things that should be improved. Usually reviewers are anonymous, and should not be directly related with the author personally or professionally.

3. Depending on the referee's appraisal, the editor can decide to reject or accept the paper. In the latter case, the editor may require the author to incorporate improvements suggested by the referees. Another round of peer review may take place after the improvements have been made.

Usually, the identity of authors is known to the referee, but not vice versa.

Work is considered worthwhile in the kernel community if it is included into some official tree. The way to achieve such an inclusion goes essentially along these lines:

□ Code is submitted to an appropriate mailing list.

□ Everyone on the mailing list can request changes to the code, and desired improvements are discussed in public.

□ The code is adapted to the desires of the community. This can be tricky because there are often orthogonal opinions as to what constitutes an improvement and what will deteriorate the code.

□ The code is re-submitted, and discussion starts anew.

□ Once the code has achieved the desired form and a consensus is reached, it is integrated into official trees.

Notice that it is possible for people with high and long-standing reputations in their fields (which is, again, a social factor) to shortcut the process in both areas, but these cases are not of interest here.

There are similarities between the academic and kernel development communities, and both have their strengths and weaknesses. For example, there are some important differences between the review process in each community:

□ Reviewing code for the kernel is not a formalized process, and there is no central authority to initiate code review. Review is performed completely voluntarily and uncoordinated — if no one is interested in the submitted code, the mailing lists can remain silent.

Although review in the academic world is usually also performed voluntarily and without payment, it is impossible for submissions to be completely ignored. Papers are guaranteed to get some feedback, although it can be very superficial.

□ The identities of the submitter and reviewer are known to each other in the kernel world, and both can interact directly. In the academic world, this is usually not the case, and conversation between the author and reviewer is mediated by the editor. Additionally, only a few rounds of exchanging arguments between the author and reviewers are possible before the editor decides to either accept or reject a submission.

□ The result of a review is only known to the submitter, referees, and editor in the academic world. Usually the whole review process is public in the kernel world, and can be read by everyone.

In both worlds, reviewers can pass harsh criticism to the submitter. In the academic world, formulations in the inverse direction are usually chosen with much more care, while this depends on the identity of the submitter and reviewer in the kernel world.

Critique is certainly valuable and essential to improve the quality of any work, but receiving critique is a complicated matter. How this is handled is another important difference between kernel development and the academic world.

Harassing people verbally in various creative, and often insulting, ways has become a trademark of some kernel developers — and the corresponding statements are publically available on the Internet. This poses a serious problem, because nobody likes to be insulted in public, and developers can be driven away by this fairly quickly. This concern is shared by several leading Linux developers, but because all people on the mailing lists are grown-ups, it is not possible to solve this problem in any other form than appealing for more fairness, which is not always accepted.

Receiving a harsh critique by an anonymous referee in the academic world is certainly not particularly enjoyable, but it is much easier to be accused of having failed in private than in public.

As you can see from the following documentation excerpt, kernel developers do not strive for complete political correctness as a means of solving this problem:

Documentation/ManagementStyle

The option of being unfailingly polite really doesn't exist. Nobody will trust somebody who is so clearly hiding his true character.

Pulling each other's legs can be a good thing, and is something of an intellectual challenge when properly employed. But it's also very easy to overdo it and end up with insulting accusations, which nobody likes to receive but unfortunately, everyone should be prepared for in the kernel world.

While the review process of the kernel world can be considerably more challenging socially than the academic counterpart, it also tends to be much more effective, taken that people are not driven away by the approach: Patches on the kernel mailing list usually go through many iterations before they are deemed to be acceptable, and in each iteration step remaining problems are identified by reviewers and can be changed by the authors. Because the goal of the kernel is to be the best in the world, it is important that only really good code is integrated. Such code is usually not created from the very beginning, but only after a period of improvement and refinement. The whole point of the review process is to generate the best possible code, and this often succeeds in practice.

The effect of review on academic papers is usually different. If a submission is rejected by one journal, it will certainly be revised by the authors to address the shortcomings. However, readers are invited to judge on their own how big the probability is that really substantial revisions are made considering that on the one hand, there is considerable pressure to publish as many papers as possible for gaining scientific reputation, and on the other hand, there are a large number of different (possibly less-renowned) journals to which the work can alternatively be submitted — and that these journals rely as their economic foundation on submissions by authors who pay(!) for being published. This is different with kernel code: Either you get code into the kernel, or a considerable amount of effort has been wasted.8 This naturally provides a large incentive to put effort into improving the code.

Although the approaches employed by the academic and kernel communities to assess and ensure the quality of submissions are similar at first glance, there are numerous differences between them. Different cultures can be a considerable barrier for the exchange of ideas and code between both worlds, and should be taken into account when it comes to a collaboration between kernel and academia.

F.5 Summary

As one of the largest open source efforts in the world, the Linux kernel is not just interesting from a technological perspective, but also because a novel and unique way of distributed development across the whole world and between otherwise competing companies is employed. This appendix described how the process is organized, and what the requirements for contribution are. It also analyzed the connection between kernel development and academic research. In this appendix, you learned how the two worlds interact, how differences can arise from different ''cultures,'' and how these are best bridged.

8It is surely possible to maintain code out-of-tree, and this has proven useful in many cases, but the final and most rewarding goal for developers (and their employers!) is nevertheless to get work into the mainline kernel.

Continue reading here: References

Was this article helpful?

0 0