System-wide compaction and specialization of the linux kernel

ABSTRACT

The limited built-in configurability of Linux can lead to expensive code size overhead when it is used in the embedded market. To overcome this problem, we propose the application of link-time compaction and specialization techniques that exploit the a priori known, fixed run-time environment of many embedded systems. In experimental setups based on the ARM XScale and i386 platforms, the proposed techniques are able to reduce the kernel memory footprint with over 16%. We also show how relatively simple additions to existing binary rewriters can implement the proposed techniques for a complex, very unconventional program such as the Linux kernel. Finally, we pinpoint an important code size growth problem when compaction and compression techniques are combined on the ARM platform.

REFERENCES

• 1: R. Cohn, D. Goodwin, P. Lowney, and N. Rubin. Spike: An optimizer for Alpha/NT executables. In Proceedings of the USENIX Windows NT Workshop, pages 17--24, 1997.
• 2: B. De Bus. Reliable, Retargetable and Extensible Link-Time Program Rewriting. PhD thesis, Ghent University, 2005.
• 3: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 4: Bruno De Bus , Daniel Kästner , Dominique Chanet , Ludo Van Put , Bjorn De Sutter, Post-pass compaction techniques, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859696]
• 5: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 6: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005 [doi>10.1145/1086642.1086645]
• 7: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 8: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 9: Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268948]
• 10: R. Flower, C.-K. Luk, R. Muth, H. Patil, J. Shakshober, R. Cohn, and G. Lowney. Kernel optimizations and prefetch with the spike executable optimizer. In Proc of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), 2001.
• 11: C.-T. Lee, J.-M. Lin, Z.-W. Hong, and W.-T. Lee. An application-oriented linux kernel customization for embedded systems. Journal of Information Science and Engineering, 20(6):1093--1107, 2004.
• 12: J. Levine. Linkers & Loaders. Morgan Kaufmann Publishers, 2000.
• 13: C. Linn, S. Debray, G. Andrews, and B. Schwarz. Stack analysis of x86 executables. Available at http://www.cs.arizona.edu/people/debray.
• 14: M. Madou, B. De Sutter, B. De Bus, L. Van Put, and K. De Bosschere. Link-time optimization of MIPS programs. In Proceedings of the 2004 International Conference on Embedded Systems and Applications (ESA'04), 2004.
• 15: L. McVoy and C. Staelin. lmbench: Portable tools for performance analysis. In USENIX Annual Technical Conference, 1996.
• 16: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 17: Robert Muth , Saumya K. Debray , Scott Watterson , Koen De Bosschere, Alto: a link-time optimizer for the Compaq alpha, Software—Practice & Experience, v.31 n.1, p.67-101, Jan. 2001 [doi>10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A]
• 18: K. Rajagopalan, S. Debray, M. Hiltunen, and R. Schlichting. Cassyopia: Compiler assisted system optimization. In Proc. 9th Usenix Workshop on Hot Topics in Operating Systems, 2003.
• 19: Montserrat Ros , Peter Sutton, Compiler optimization and ordering effects on VLIW code compression, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951725]
• 20: W. J. Schmidt , R. R. Roediger , C. S. Mestad , B. Mendelson , I. Shavit-Lottem , V. Bortnikov-Sitnitsky, Profile-directed restructuring of operating system code, IBM Systems Journal, v.37 n.2, p.270-297, April 1998
• 21: B. Schwarz, S. Debray, G. Andrews, and M. Legendre. PLTO: A link-time optimizer for the intel ia-32 architecture. In Proc. 2001 Workshop on Binary Rewriting (WBT-2001), 2001.
• 22: S. E. Speer, R. Kumar, and C. Partridge. Improving unix kernel performance using profile based optimization. In 1994 Winter USENIX, pages 181--188, 1994.
• 23: Ariel Tamches , Barton P. Miller, Fine-grained dynamic instrumentation of commodity operating system kernels, Proceedings of the third symposium on Operating systems design and implementation, p.117-130, February 1999, New Orleans, Louisiana, United States
• 24: A. Tamches and B. P. Miller. Dynamic kernel code optimization. In Workshop on Binary Translation (WBT-2001), 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Code generation

General Terms:
Experimentation, Performance

Keywords:
compaction, linux kernel, operating system, specialization, system calls