Automated reduction of the memory footprint 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 runtime 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. We note that even after specialization, a lot of seemingly unnecessary code remains in the kernel and propose to reduce the footprint of this code by applying code-compression techniques. This technique, combined with the previous ones, reduces the memory footprint with over 23% for the i386 platform and 28% for the ARM platform. Finally, we pinpoint an important code size growth problem when compaction and compression techniques are combined on the ARM platform.

REFERENCES

• 1: Anckaert, B., Vandeputte, F., De Bus, B., De Sutter, B., and De Bosschere, K. 2004. Link-time optimization of IA64 binaries. In Proceedings of the 2004 Euro-Par Conference. 284--291.
• 2: Sapan Bhatia , Charles Consel , Calton Pu, Remote customization of systems code for embedded devices, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017760]
• 3: Dominique Chanet , Bjorn De Sutter , Bruno De Bus , Ludo Van Put , Koen De Bosschere, System-wide compaction and specialization of the linux kernel, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 4: Daniel Citron , Gadi Haber , Roy Levin, Reducing program image size by extracting frozen code and data, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017800]
• 5: Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000 [doi>10.1145/353926.353933]
• 6: Robert Cohn , David Goodwin , P. Geoffrey Lowney , Norman Rubin, Spike: an optimizer for alpha/NT executables, Proceedings of the USENIX Windows NT Workshop on The USENIX Windows NT Workshop 1997, p.3-3, August 11-13, 1997, Seattle, Washington
• 7: Marc L. Corliss , E. Christopher Lewis , Amir Roth, A DISE implementation of dynamic code decompression, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 8: Cours, J., Navarro, N., and Hwu, W. 2004. Using coverage-based analysis to automate the customization of the Linux kernel for embedded applications. M.S. thesis, University of Illinois at Urbana-Champaign.
• 9: De Bus, B. 2005. Reliable, retargetable and extensible link-time program rewriting. Ph.D. thesis, Ghent University.
• 10: 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]
• 11: 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
• 12: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 13: 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
• 14: 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]
• 15: Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Bruno De Bus , Koen De Bosschere, Link-time compaction and optimization of ARM executables, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.1, February 2007 [doi>10.1145/1210268.1210273]
• 16: 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]
• 17: Saumya Debray , William Evans, Profile-guided code compression, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 18: 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]
• 19: G. Denys , F. Piessens , F. Matthijs, A survey of customizability in operating systems research, ACM Computing Surveys (CSUR), v.34 n.4, p.450-468, December 2002 [doi>10.1145/592642.592644]
• 20: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 21: William S. Evans , Christopher W. Fraser, Bytecode compression via profiled grammar rewriting, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.148-155, June 2001, Snowbird, Utah, United States
• 22: Jean-Philippe Fassino , Jean-Bernard Stefani , Julia L. Lawall , Gilles Muller, Think: A Software Framework for Component-based Operating System Kernels, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.73-86, June 10-15, 2002
• 23: Flower, R., Luk, C.-K., Muth, R., Patil, H., Shakshober, J., Cohn, R., and Lowney, G. 2001. Kernel optimizations and prefetch with the spike executable optimizer. In Proc of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4).
• 24: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• 25: Michael Franz, Adaptive Compression of Syntax Trees and Iterative Dynamic Code Optimization: Two Basic Technologies for Mobile Object Systems, Selected Presentations and Invited Papers Second International Workshop on Mobile Object Systems - Towards the Programmable Internet, p.263-276, July 08-09, 1996
• 26: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 27: Christopher W. Fraser, Automatic inference of models for statistical code compression, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.242-246, May 01-04, 1999, Atlanta, Georgia, United States
• 28: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 29: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 30: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 31: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 32: Chandra Krintz , Rich Wolski, Using Phase Behavior in Scientific Application to Guide Linux Operating System Customization, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 10, p.219.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.449]
• 33: Lee, C.-T., Lin, J.-M., Hong, Z.-W., and Lee, W.-T. 2004. An application-oriented Linux kernel customization for embedded systems. Journal of Information Science and Engineering 20, 6, 1093--1107.
• 34: Haris Lekatsas , Jörg Henkel , Srimat Chakradhar , Venkata Jakkula , Murugan Sankaradass, CoCo: a hardware/software platform for rapid prototyping of code compression technologies, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775912]
• 35: Levine, J. 2000. Linkers & Loaders. Morgan Kaufmann, San Matco, CA.
• 36: Linn, C., Debray, S., Andrews, G., and Schwarz, B. 2004. Stack analysis of x86 executables. Available from http://www.cs.arizona.edu/people/debray.
• 37: Madou, M., De Sutter, B., De Bus, B., Van Put, L., and De Bosschere, K. 2004. Link-time optimization of MIPS programs. In Proceedings of the 2004 International Conference on Embedded Systems and Applications (ESA'04).
• 38: Dylan McNamee , Jonathan Walpole , Calton Pu , Crispin Cowan , Charles Krasic , Ashvin Goel , Perry Wagle , Charles Consel , Gilles Muller , Renauld Marlet, Specialization tools and techniques for systematic optimization of system software, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.217-251, May 2001 [doi>10.1145/377769.377778]
• 39: Larry McVoy , Carl Staelin, lmbench: portable tools for performance analysis, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.23-23, January 22-26, 1996, San Diego, CA
• 40: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 41: 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]
• 42: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 43: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 44: 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]
• 45: 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
• 46: Schwarz, B., Debray, S., Andrews, G., and Legendre, M. 2001. PLTO: A link-time optimizer for the Intel IA-32 architecture. In Proc. 2001 Workshop on Binary Rewriting (WBT-2001).
• 47: Steven E. Speer , Rajiv Kumar , Craig Partridge, Improving UNIX kernel performance using profile based optimization, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.15-15, January 17-21, 1994, San Francisco, California
• 48: Amitabh Srivastava , David W. Wall, Link-time optimization of address calculation on a 64-bit architecture, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.49-60, June 20-24, 1994, Orlando, Florida, United States
• 49: 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
• 50: Tamches, A. and Miller, B. P. 2001. Dynamic kernel code optimization. In Workshop on Binary Translation (WBT-2001).
• 51: TriMedia Technologies Inc. 2000. TriMedia32 Architecture. TriMedia Technologies Inc.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

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

Keywords:
Linux kernel, compaction, compression, operating system, specialization, system calls