• Home
• Teaching
• Research
• Publications

This paper deals with some of the issues that arise in the context of binary rewriting and instrumentation of an operating system kernel. OS kernels are very different from ordinary application code in many ways, e.g., they contain a significant amount of hand-written assembly code. Binary rewriting is an attractive approach for processing OS kernel code for several reasons, e.g., it provides a uniform way to handle heterogeneity in code due to a combination of source code, assembly code and legacy code such as in device drivers. However, because of the many differences between ordinary application code and OS kernel code, binary rewriting techniques that work for application code do not always carry over directly to kernel code. This paper describes some of the issues that arise in this context, and the approaches we have taken to address them. A key goal when developing our system was to deal in a systematic manner with the various peculiarities seen in low-level systems code, and reason about the safety and correctness of code transformations, without requiring significant deviations from the regular developmental path. For example, a precondition we assumed was that no compiler or linker modifications should be required to use it and the tool should be able to process kernel binaries in the same way as it does ordinary applications.

We have implemented a prototype kernel binary rewriter as an extension to the PLTO binary rewriting toolkit. PLTO takes as input a relocatable binary that it manipulates in various ways, e.g., to insert instrumentation code or to apply various optimizing transformations using optional execution profiles for guidance. It then updates code addresses as necessary, using relocation information to distinguish addresses from non-address values, and finally writes the resulting program out as an executable. PLTO currently supports the collection of several different kinds of execution profiles: basic block counts, edge counts, value profiles (especially important for resolving indirect function call targets), call-stack profiles, as well as profiles based on hardware performance counters, e.g., CPU cycles and i-cache misses. Our prototype has also been used to perform a number of program analyses and optimizations, including function inlining, guarded inlining (for indirect function calls---the inlined code is guarded by a test of the call target), constant propagation (for code specialization), dead and unreachable code elimination (especially important for code compaction), and profile-guided code layout. We have also used our system to carry out specialization and compaction of the Linux kernel. Some of this work is described in a companion paper.