Mondrian memory protection

ABSTRACT

Mondrian memory protection (MMP) is a fine-grained protection scheme that allows multiple protection domains to flexibly share memory and export protected services. In contrast to earlier page-based systems, MMP allows arbitrary permissions control at the granularity of individual words. We use a compressed permissions table to reduce space overheads and employ two levels of permissions caching to reduce run-time overheads. The protection tables in our implementation add less than 9% overhead to the memory space used by the application. Accessing the protection tables adds than 8% additional memory references to the accesses made by the application. Although it can be layered on top of demand-paged virtual memory, MMP is also well-suited to embedded systems with a single physical address space. We extend MMP to support segment translation which allows a memory segment to appear at another location in the address space. We use this translation to implement zero-copy networking underneath the standard read system call interface, where packet payload fragments are connected together by the translation system to avoid data copying. This saves 52% of the memory references used by a traditional copying network stack.

REFERENCES

• 1: Adobe Systems Incorporated. Adobe PDF Plugin, 2002. http://www.adobe.com/.
• 2: Apache Software Foundation. mod_perl, 2002. http://perl.apache.org/.
• 3: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 4: ARM Ltd. ARM940T Technical Reference Manual (Rev 2), ARM DDI 0144B 2000.
• 5: Burroughs Corporation. The Descriptor--a Definition of the B5000 Information Processing System., 1961. http://www.cs.virginia.edu/brochure/images/manuals/b5000/descrip/descrip.html.
• 6: Martin Christopher Carlisle, Olden: parallelizing programs with dynamic data structures on distributed-memory machines, Princeton University, Princeton, NJ, 1996
• 7: Nicholas P. Carter , Stephen W. Keckler , William J. Dally, Hardware support for fast capability-based addressing, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.319-327, October 05-07, 1994, San Jose, California, United States
• 8: Jeffrey Scott Chase, An operating system structure for wide-address architectures, University of Washington, Seattle, WA, 1996
• 9: H. K. J. Chu. Zero-copy TCP in Solaris. In USENIX Annual Technical Conference, pages 253-264, 1996.
• 10: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• 11: Dirk Grunwald , Richard Neves, Whole-program optimization for time and space efficient threads, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.50-59, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: Germont Heiser , Kevin Elphinstone , Jerry Vochteloo , Stephen Russell , Jochen Liedtke, The Mungi single-address-space operating system, Software—Practice & Experience, v.28 n.9, p.901-928, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<901::AID-SPE181>3.0.CO;2-7]
• 13: Merle E. Houdek , Frank G. Soltis , Roy L. Hoffman, IBM System/38 support for capability-based addressing, Proceedings of the 8th annual symposium on Computer Architecture, p.341-348, May 12-14, 1981, Minneapolis, Minnesota, United States
• 14: Intel Corporation. Volume 1: Basic architecture, Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture, 1997.
• 15: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 16: Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.175-186, October 12-15, 1992, Boston, Massachusetts, United States
• 17: B. Lampson. Protection. In Proc. 5th Princeton Conf. on Information Sciences and Systems, 1971.
• 18: Henry M. Levy, Capability-Based Computer Systems, Butterworth-Heinemann, Newton, MA, 1984
• 19: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 20: K. Mackenzie , J. Kubiatowicz , M. Frank , W Lee , V Lee , A. Agarwal , M. Kaashoek, Exploiting Two-Case Delivery for Fast Protected Messaging, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.231, January 31-February 04, 1998
• 21: George C. Necula, Proof-carrying code, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.106-119, January 15-17, 1997, Paris, France [doi>10.1145/263699.263712]
• 22: NS Notes and Documentation. http://www.isi.edu/vint/nsnam/, 2000.
• 23: Vivek S. Pai , Peter Druschel , Willy Zwaenepoel, IO-Lite: a unified I/O buffering and caching system, ACM Transactions on Computer Systems (TOCS), v.18 n.1, p.37-66, Feb. 2000 [doi>10.1145/332799.332895]
• 24: Rational Software Corporation. Purify, 2002. http://www.rational.com/media/products/pqc/D610_PurifyPlus_unix.pdf.
• 25: M. Rinard and et al. The FLEX compiler infrastructure. 1999-2001. http://www.flex-compiler.lcs.mit.edu.
• 26: Jerome H. Saltzer, Protection and the control of information sharing in multics, Communications of the ACM, v.17 n.7, p.388-402, July 1974 [doi>10.1145/361011.361067]
• 27: Daniel J. Scales , Kourosh Gharachorloo , Chandramohan A. Thekkath, Shasta: a low overhead, software-only approach for supporting fine-grain shared memory, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.174-185, October 01-04, 1996, Cambridge, Massachusetts, United States
• 28: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• 29: Jonathan S. Shapiro , Jonathan M. Smith , David J. Farber, EROS: a fast capability system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.170-185, December 12-15, 1999, Charleston, South Carolina, United States
• 30: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 31: Thorsten von Eicken , Chi-Chao Chang , Grzegorz Czajkowski , Chris Hawblitzel , Deyu Hu , Dan Spoonhower, J-Kernel: a capability-based operating system for Java, Secure Internet programming: security issues for mobile and distributed objects, Springer-Verlag, London, 2001
• 32: D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Network and Distributed System Security Symposium, pages 3-17, San Diego, CA, February 2000.
• 33: Robert Wahbe, Efficient data breakpoints, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.200-212, October 12-15, 1992, Boston, Massachusetts, United States
• 34: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, ACM SIGOPS Operating Systems Review, v.27 n.5, p.203-216, Dec. 1993
• 35: C. Yarvin, R. Bukowski, and T. Anderson. Anonymous RPC: Low-latency protection in a 64-bit address space. In USENIX Summer, pages 175-186, 1993.
• 36: Craig B. Zilles, Benchmark health considered harmful, ACM SIGARCH Computer Architecture News, v.29 n.3, p.4-5, June 2001 [doi>10.1145/503205.503206]