Hardware support for fast capability-based addressing

ABSTRACT

Traditional methods of providing protection in memory systems do so at the cost of increased context switch time and/or increased storage to record access permissions for processes. With the advent of computers that supported cycle-by-cycle multithreading, protection schemes that increase the time to perform a context switch are unacceptable, but protecting unrelated processes from each other is still necessary if such machines are to be used in non-trusting environments.

This paper examines guarded pointers, a hardware technique which uses tagged 64-bit pointer objects to implement capability-based addressing. Guarded pointers encode a segment descriptor into the upper bits of every pointer, eliminating the indirection and related performance penalties associated with traditional implementations of capabilities. All processes share a single 54-bit virtual address space, and access is limited to the data that can be referenced through the pointers that a process has been issued. Only one level of address translation is required to perform a memory reference. Sharing data between processes is efficient, and protection states are defined to allow fast protected subsystem calls and create unforgeable data keys.

References

1. 1.ACCETTA, M., BARON, R., BOLOSKY, W., GOLUB, D., RASHID, R., TEVANIAN, A., AND YOUNG, M. Mach: A new kernel foundation for UNIX development. In Summer 1986 Usenix Conference (July 1986), pp. 93-112.
2. 2.AGARWAL, A., ET AL. The MIT Alewife machine: A htrge-scale distributed-memory multiprocessor. In Scalable Shared Memory Multiprocessors. Kluwer Academic Publishers, 1991.
3. 3.ALVERSON, R,, ET AL. The Tera computer system. In Proceedings of the 1990 International Conference on Supercomputing (Sept. 1990), ACM SIGPLAN Computer Architecture News, pp. 1-6.
4. 4.BENSOUSSAN, A., CLINGEN, C., AND DALEY, R. The Multics Virtual Memory: Concepts and Design. Communications of the ACM 15, 5 (May 1972), 308-318.
5. 5.CHASE, J. S., LEVY, H. M., FEELEY, M.J., AND LAZOWSKA, E. D. Sharing and protection in a single address space operating system. Tech. Rep. 93-04-02, Department of Computer Science and Engineering, University of Washington, Seattle, Washington, 1993.
6. 6.DALEY, R. C., AND DENNIS, J. B. Virtual Memory, Processes and Sharing in MULTICS. Communications ofthe ACM 11, 5 (May 1968), 306-312.
7. 7.DALLY, W. J. A fast translation method for paging on top of segmentation. IEEE Transactions on Computers 41, 2 (1992), 247-249.
8. 8.DALLY, W. J., AND KAJIYA, J. T. An object oriented architecture. In Proceedings of the 12th International Symposium on Computer Architecture (Boston, MA, June 1985), pp. 154-161.
9. 9.DALLY, W. J., KECKI~R, S. W., CARTER, N., CHANG, A., {~LLO, M., AND LEE, W. S. M-Machine architecture vl.0. Concurrent VLSI Architecture Memo 58, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, january 1994.
10. 10.DENNIS, J. B. Segmentation and the Design of Multiprogrammed Computer System. JACM 12, 4 (October 1965), 589-602.
11. 11.DIGITAL EQUIPMENT CORPORATION. Alpha Architecture ttandbook. Maynard, MA, 1992.
12. 12.FABRY, R. Capability-based addressing. Communications of the ACM 17, 7 (July 1974), 403-412.
13. 13.HOUDEK, M. E., SOLTIS, E G., AND HOFFMAN, R.L. IBM sys~ tem/38 support for capability-based addressing. In Proceedings of the 8th International Symposium on Computer Architecture (May 1981), pp. 341-348.
14. 14.iNTEL CORPORATION. The 8086 Family User ~ Manual. Saa~ta Clara, CA, Oct. 1979.
15. 15.INTEL CORPORATION. 80386 Programmer ~ Reference Manual. Santa Clara, CA, 1988.
16. 16.KECKLER, S. W., AND DALLY, W. J. Processor coupling: Integrating compile time and runtime scheduling for parallelism. In Proceedings of the 19th International Symposium on Computer Architecture (Queensland, Australia, May 1992), ACM, pp. 202-213.
17. 17.KOLDINGER, E. J., CHASE, J. S., AND EGGERS, S. J. Architectural support for single address space operating systems. In Fifth International Conference on ArchitecturaI Support for Programming Languages and Operating Systems (ASPLOS V)(October 1992), ACM, pp. 175-186.
18. 18.LEE, R.B. Precision architecture. IEEE Computer 22, { (January 1989), 78-91.
19. 19.LEVY, H.M. Capability-Based Computer Systems. Digital Press, 1984.
20. 20.LONERGAN, W., AND KING, P. Design of the B5000 system. Datarnation 7, 5 (May 1961), 28-32.
21. 21.MOON, D. A. Symbolics Architecture. IEEE Computer (1987), 43-52.
22. 22.MULLENDER, S. J., VAN ROSSUM, G., TANENBAUM, A. S., VAN RE- NESSE, R., AND VAN STAVEREN, H. Amoeba: A distributed operating system for the 1990s. IEEE Computer23 (May 1990), 44-53.
23. 23.ROSENBERG, J., AND ABRAMSON, D. MONADS-PC - a capabilitybased workstation to support software engineering. In Proceedings of the Eighteenth Annual Hawaii International Conference on System Sciences, 1985 (Clayton, Australia, 1985), Department of Computer Science, Monash University, pp. 222-231.
24. 24.TYNER, E iAXP 432 General Data Processor Architecture Reference Manual. Intel Corporation, Aloha, OR, 1981.
25. 25.WAHBE, R., LUCCO, S., ANDERSON, T. E., AND GRAHAM, S. L. Efficient software-based fault isolation. In Symposium on Operating System Principles (December 1993), pp. 203-216.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Very long instruction word

    • Serial architectures

      • Complex instruction set computing

      • Reduced instruction set computing

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network performance evaluation