22C:116, Lecture 38, Spring 2002

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Capability-based addressing

    When a paged MMU is used between the CPU and main memory, each program has access to a set of pages, but the program does not access that page using a globally meaningful name. Instead, it uses a virtual address that contains a page-number field. That page number is meaningful only in the context of that process. Page x of process A may reference one page, while page x of process B may reference an entirely different page.

    In the terminology used for discussions of protection, x is the index into the capability list of the process, and because processes A and B each have their own capability lists, there is no reason that entry x in one process should bear any relationship to entry x in another. We say that these processes use capability-based addressing because the addresses they use name capabilities in their local C-lists instead of naming the actual objects being addressed.

  2. Capability-based addressing for main memory

    In a system that uses capability-based addressing for main memory, there are two fundamentally distinct abstract data types in the system, the page and the C-list. Systems have been proposed since the late 1960's and built since the early 1970's where the hardware recognized this distinction -- typically, C-lists themselves are constrained to have the size of a page, but the hardware prevents programs from storing anything but capabilities in C-lists, and the hardware prevents programs from using a bit pattern from a page as a capability. Alternatively, we can have a tag field on each word to indicate whether that word is a data word or a capability. This requires fairly large words (capabilities in some systems are as large as 64 or 128 bits).

    The IBM AS-400 uses tagged memory. The Plessy System 250 (used only in telephone switching) distinguished between C-lists and pages, but both systems work quite well.

  3. Capability-based addressing for file systems

    In UNIX, the access rights associated with a file are stored in the I-node of that file, which is to say, the access rights are an attribute of the file. An alternative is to associate access rights with each directory entry, so the directory entry names a particular file and gives the user's access rights to the file.

    If this is done, the file system can be said to use capability-based addressing. A directory entry is a capability because, conceptually, it points to a file and gives the set of access rights granted to the user of that directory entry. If two users are to have two different sets of rights to a file, they must access that file through different directories. A file might be entered in the public directory, with very limited rights, and in the private directory of one user, the file's owner, with very general rights.

    In a capability-based file system, each user must come into the file system from a different root -- this is the home directory of that user, and it defines the domain of that user relative to the file system. Typically, each user will have, in his or her domain, an entry for the directory of public files.

    Many capability-based file systems have been made over the years, including the Cambridge Ring file system (a network file server) and Tannenbaum's Bullet file server for the Amoeba operating system.