article

Automated reduction of the memory footprint of the Linux kernel

Authors:

Koen De BosschereAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 6, Issue 4

Pages 23 - es

https://doi.org/10.1145/1274858.1274861

Published: 01 September 2007 Publication History

Get Access

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.

Crossref

Google Scholar

[2]

Bhatia, S., Consel, C., and Pu, C. 2004. Remote customization of systems code for embedded devices. In EMSOFT '04: Proceedings of the 4th ACM international conference on Embedded software. ACM Press, New York. 7--15.

Digital Library

Google Scholar

[3]

Chanet, D., De Sutter, B., De Bus, B., Van Put, L., and De Bosschere, K. 2005. System-wide compaction and specialization of the Linux kernel. In Proc. of the 2005 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES). 95--104.

Digital Library

Google Scholar

[4]

Citron, D., Haber, G., and Levin, R. 2004. Reducing program image size by extracting frozen code and data. In EMSOFT '04: Proceedings of the 4th ACM international conference on Embedded software. ACM Press, New York. 297--305.

Digital Library

Google Scholar

[5]

Clausen, L., Schultz, U., Consel, C., and Muller, G. 2000. Java bytecode compression for low-end embedded systems. ACM Transactions on Programming Languages and Systems 22, 3 (May), 471--489.

Digital Library

Google Scholar

[6]

Cohn, R., Goodwin, D., Lowney, P., and Rubin, N. 1997. Spike: An optimizer for Alpha/NT executables. In Proceedings of the USENIX Windows NT Workshop. 17--24.

Digital Library

Google Scholar

[7]

Corliss, M., Lewis, E., and Roth, A. 2003. A DISE implementation of dynamic code decompression. In Proceedings of the ACM SIGPLAN 2003 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'03). 232--243.

Digital Library

Google Scholar

[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.

Google Scholar

[9]

De Bus, B. 2005. Reliable, retargetable and extensible link-time program rewriting. Ph.D. thesis, Ghent University.

Google Scholar

[10]

De Bus, B., Kästner, D., Chanet, D., Van Put, L., and De Sutter, B. 2003. Post-pass compaction techniques. Communications of the ACM 46, 8 (Aug.), 41--46.

Digital Library

Google Scholar

[11]

De Bus, B., De Sutter, B., Van Put, L., Chanet, D., and De Bosschere, K. 2004. Link-time optimization of ARM binaries. In Proc. of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES). 211--220.

Digital Library

Google Scholar

[12]

De Sutter, B., De Bus, B., De Bosschere, K., and Debray, S. 2001. Combining global code and data compaction. In Proc. of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems. 29--38.

Digital Library

Google Scholar

[13]

De Sutter, B., De Bus, B., and De Bosschere, K. 2002. Sifting out the mud: low level C++ code reuse. In Proceedings of the 17th ACM SIGPLAN conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 275--291.

Digital Library

Google Scholar

[14]

De Sutter, B., De Bus, B., and De Bosschere, K. 2005. Link-time binary rewriting techniques for program compaction. ACM Transactions on Programming Languages and Systems 27, 5 (9), 882--945.

Digital Library

Google Scholar

[15]

De Sutter, B., Van Put, L., Chanet, D., De Bus, B., and De Bosschere, K. 2006. Link-time compaction and optimization of ARM executables. ACM Transactions on Embedded Computing Systems. To appear.

Digital Library

Google Scholar

[16]

Debray, S., Muth, R., and Weippert, M. 1998. Alias analysis of executable code. In Proceedings of the ACM 1998 Symposium on Principles of Programming Languages (POPL'98). 12--24.

Digital Library

Google Scholar

[17]

Debray, S. and Evans, W. 2002. Profile-guided code compression. In PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation. ACM Press, New York. 95--105.

Digital Library

Google Scholar

[18]

Debray, S., Evans, W., Muth, R., and De Sutter, B. 2002. Compiler techniques for code compaction. ACM Transactions on Programming Languages and Systems 22, 2 (3), 378--415.

Digital Library

Google Scholar

[19]

Denys, G., Piessens, F., and Matthijs, F. 2002. A survey of customizability in operating systems research. ACM Comput. Surv. 34, 4, 450--468.

Digital Library

Google Scholar

[20]

Ernst, J., Evans, W., Fraser, C., Lucco, S., and Proebsting, T. 1997. Code compression. In Proceedings of the 1997 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'97). 358--365.

Digital Library

Google Scholar

[21]

Evans, W. S. and Fraser, C. W. 2001. Bytecode compression via profiled grammar rewriting. In PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation. ACM Press, New York. 148--155.

Digital Library

Google Scholar

[22]

Fassino, J.-P., Stefani, J.-B., Lawall, J. L., and Muller, G. 2002. Think: A software framework for component-based operating system kernels. In Proceedings of the General Track: 2002 USENIX Annual Technical Conference. USENIX Association, Berkeley, CA. 73--86.

Digital Library

Google Scholar

[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).

Google Scholar

[24]

Ford, B., Back, G., Benson, G., Lepreau, J., Lin, A., and Shivers, O. 1997. The flux oskit: a substrate for kernel and language research. In SOSP '97: Proceedings of the 16th ACM symposium on Operating systems principles. ACM Press, New York. 38--51.

Digital Library

Google Scholar

[25]

Franz, M. 1997. Adaptive compression of syntax trees and iterative dynamic code optimization: Two basic technologies for mobile-object systems. In Mobile Object Systems: Towards the Programmable Internet, J. Vitek and C. Tschudin, Eds. Number 1222 in LNCS. Springer, New York. 263--276.

Digital Library

Google Scholar

[26]

Franz, M. and Kistler, T. 1997. Slim binaries. Communications of the ACM 40, 12 (Dec.), 87--94.

Digital Library

Google Scholar

[27]

Fraser, C. 1999. Automatic inference of models for statistical code compression. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation (PLDI'99). 242--246.

Digital Library

Google Scholar

[28]

Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., and Culler, D. 2003. The nesC language: A holistic approach to networked embedded systems. In PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation. ACM Press, New York. 1--11.

Digital Library

Google Scholar

[29]

Hind, M. 2001. Pointer analysis: Haven't we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01). Snowbird, UT.

Digital Library

Google Scholar

[30]

Kemp, T. M., Montoye, R. M., Harper, J. D., Palmer, J. D., and Auerbach, D. J. 1998. A decompression core for PowerPC. IBM J. Research and Development 42, 6 (Nov.).

Digital Library

Google Scholar

[31]

Kirovski, D., Kin, J., and Mangione-Smith, W. H. 1997. Procedure based program compression. In Proceedings of the 30th Annual International Symposium on Microarchitecture (MICRO-30).

Digital Library

Google Scholar

[32]

Krintz, C. and Wolski, R. 2005. Using phase behavior in scientific application to guide Linux operating system customization. In IPDPS '05: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05)---Workshop 10. IEEE Computer Society, Washington, DC. 219.1.

Digital Library

Google Scholar

[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.

Google Scholar

[34]

Lekatsas, H., Henkel, J., Chakradhar, S., Jakkula, V., and Sankaradass, M. 2003. Coco: a hardware/software platform for rapid prototyping of code compression technologies. In Proceedings of the 40th conference on Design Automation (DAC). 306--311.

Digital Library

Google Scholar

[35]

Levine, J. 2000. Linkers & Loaders. Morgan Kaufmann, San Matco, CA.

Google Scholar

[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.

Google Scholar

[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).

Google Scholar

[38]

McNamee, D., Walpole, J., Pu, C., Cowan, C., Krasic, C., Goel, A., Wagle, P., Consel, C., Muller, G., and Marlet, R. 2001. Specialization tools and techniques for systematic optimization of system software. ACM Trans. Comput. Syst. 19, 2, 217--251.

Digital Library

Google Scholar

[39]

McVoy, L. and Staelin, C. 1996. lmbench: Portable tools for performance analysis. In USENIX Annual Technical Conference.

Digital Library

Google Scholar

[40]

Muchnick, S. S. 1997. Advanced Compiler Design & Implementation. Morgan Kaufmann, San Matco, CA.

Digital Library

Google Scholar

[41]

Muth, R., Debray, S., Watterson, S., and De Bosschere, K. 2001. Alto: a link-time optimizer for the Compaq Alpha. Software---Practice and Experience 31, 1, 67--101.

Digital Library

Google Scholar

[42]

Proebsting, T. 1995. Optimizing an ANSI C interpreter with superoperators. In Proceedings of the ACM SIGPLAN-SIGACT 1995 Symposium on Principles of Programming Languages (POPL'95). 322--332.

Digital Library

Google Scholar

[43]

Pugh, W. 1999. Compressing Java class files. In Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99). 247--258.

Digital Library

Google Scholar

[44]

Ros, M. and Sutton, P. 2003. Compiler optimization and ordering effects on VLIW code compression. In Proceedings of the 2003 International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES). 95--103.

Digital Library

Google Scholar

[45]

Schmidt, W., Roediger, R., Mestad, C., Mendelson, B., Shavit-Lottem, I., and Bortnikov-Sitnitsky, V. 1998. Profile-directed restructuring of operating system code. IBM Systems Journal 37, 2.

Digital Library

Google Scholar

[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).

Google Scholar

[47]

Speer, S. E., Kumar, R., and Partridge, C. 1994. Improving UNIX kernel performance using profile based optimization. In 1994 Winter USENIX. 181--188.

Digital Library

Google Scholar

[48]

Srivastava, A. and Wall, D. 1994. Link-time optimization of address calculation on a 64-bit architecture. In Proc. of the 1994 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 49--60.

Digital Library

Google Scholar

[49]

Tamches, A. and Miller, B. P. 1999. Fine-grained dynamic instrumentation of commodity operating system kernels. In Operating Systems Design and Implementation. 117--130.

Digital Library

Google Scholar

[50]

Tamches, A. and Miller, B. P. 2001. Dynamic kernel code optimization. In Workshop on Binary Translation (WBT-2001).

Google Scholar

[51]

TriMedia Technologies Inc. 2000. TriMedia32 Architecture. TriMedia Technologies Inc.

Google Scholar

Cited By

View all

Marwedel PMarwedel P(2021)System SoftwareEmbedded System Design10.1007/978-3-030-60910-8_4(203-237)Online publication date: 26-Jan-2021
https://doi.org/10.1007/978-3-030-60910-8_4
de Hoz Diego JSaldana JFernandez-Navajas JRuiz-Mas J(2020)Decoupling Security From Applications in CoAP-Based IoT DevicesIEEE Internet of Things Journal10.1109/JIOT.2019.29513067:1(467-476)Online publication date: Jan-2020
https://doi.org/10.1109/JIOT.2019.2951306
Kaur JReddy S(2020)Implementation of Linux Optimization Technique for ARM Based System on ChipProcedia Computer Science10.1016/j.procs.2020.04.191171(1780-1789)Online publication date: 2020
https://doi.org/10.1016/j.procs.2020.04.191
Show More Cited By

Index Terms

Automated reduction of the memory footprint of the Linux kernel

Recommendations

System-wide compaction and specialization of the linux kernel
LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

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 ...
Memory footprint reduction for embedded systems
SCOPES '08: Proceedings of the 11th international workshop on Software & compilers for embedded systems

The memory footprint is considered an important constraint for embedded systems. This is especially important in the context of increasing sophistication of embedded software, and the increasing use of modern software engineering techniques like ...
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

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 ...

Reviews

Reviewer: Olivier Louis Marie Lecarme

Nowadays, when one gigabyte (GB) of memory storage is considered much too small, one would be surprised to know that it is important to reduce the size of a program when it reaches about one megabyte (MB). To an old computer scientist, this may recall the times when a full operating system resident part would need no more than 100 kilobytes (KB). When using a monolithic kernel like Linux on an embedded platform with 64 MB of storage, it is important to reduce the memory footprint of the kernel as much as possible, even if this slightly reduces performance. Instead of trying to customize the kernel source code, or to parametrize it at compile time, Chanet et al. want to be able to automate the compaction techniques in order to operate at link time. Because of the very special nature of a kernel, they have to employ various techniques: eliminating unused system call handlers; specializing system calls in order to use available optimization techniques; specializing boot time parameters; moving initializing code to the part freed after initialization time; and compressing unexecuted code that could be called in abnormal situations only. They have to take into account several kernel code peculiarities, such as memory-mapped input/output (MMIO) or very low-level special instruction sequences, as well as multithreading. All these techniques are assessed separately, and their effect is clearly evaluated. The detailed results are significantly different on a CISC processor (x86) and a RISC one (ARM), but the overall footprint reduction is 23.3 percent on the first one, and 28.0 percent on the second one. I wonder whether using Hurd’s idea of a nonmonolithic kernel would avoid all this work. However, this 25-page paper makes a very interesting read, from cover to cover. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 6, Issue 4

Special Section LCTES'05

September 2007

352 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1274858

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 September 2007

Published in TECS Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
1,194
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Marwedel PMarwedel P(2021)System SoftwareEmbedded System Design10.1007/978-3-030-60910-8_4(203-237)Online publication date: 26-Jan-2021
https://doi.org/10.1007/978-3-030-60910-8_4
de Hoz Diego JSaldana JFernandez-Navajas JRuiz-Mas J(2020)Decoupling Security From Applications in CoAP-Based IoT DevicesIEEE Internet of Things Journal10.1109/JIOT.2019.29513067:1(467-476)Online publication date: Jan-2020
https://doi.org/10.1109/JIOT.2019.2951306
Kaur JReddy S(2020)Implementation of Linux Optimization Technique for ARM Based System on ChipProcedia Computer Science10.1016/j.procs.2020.04.191171(1780-1789)Online publication date: 2020
https://doi.org/10.1016/j.procs.2020.04.191
Yuan PGuo YZhang LChen XMei H(2018)Building application-specific operating systems: a profile-guided approachScience China Information Sciences10.1007/s11432-017-9418-961:9Online publication date: 13-Aug-2018
https://doi.org/10.1007/s11432-017-9418-9
Keulenaer RMaebe JBosschere KSutter B(2016)Link-time smart card code hardeningInternational Journal of Information Security10.1007/s10207-015-0282-015:2(111-130)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10207-015-0282-0
Shen BHsu WYang W(2014)A Retargetable Static Binary Translator for the ARM ArchitectureACM Transactions on Architecture and Code Optimization10.1145/262933511:2(1-25)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2629335
Paroczi Z(2013)x86 instruction reordering for code compressionActa Cybernetica10.14232/actacyb.21.1.2013.1321:1(177-190)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.14232/actacyb.21.1.2013.13
Fang ZZhao LJiang XLu SIyer RLi TLee S(2013)Reducing cache and TLB power by exploiting memory region and privilege level semanticsJournal of Systems Architecture10.1016/j.sysarc.2013.04.00259:6(279-295)Online publication date: Jun-2013
https://doi.org/10.1016/j.sysarc.2013.04.002
Paleari RMartignoni LFresi Roglia GBruschi DTonella POrso A(2010)N-version disassemblyProceedings of the 19th international symposium on Software testing and analysis10.1145/1831708.1831741(265-274)Online publication date: 12-Jul-2010
https://dl.acm.org/doi/10.1145/1831708.1831741
Courbot AGrimaud GVandewalle J(2010)Efficient off-board deployment and customization of virtual machine-based embedded systemsACM Transactions on Embedded Computing Systems10.1145/1698772.16987799:3(1-53)Online publication date: 5-Mar-2010
https://dl.acm.org/doi/10.1145/1698772.1698779
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

System-wide compaction and specialization of the linux kernel

Memory footprint reduction for embedded systems

System-wide compaction and specialization of the linux kernel

Reviews

Access critical reviews of Computing literature here