Capability-Based Addressing

R. S. Fabry @ UC-Berkeley

Communications of the ACM, July 1974, pages 403-412

Introduction

Capability: absolute address of and access permission for an object
Absolute address should be never changed nor reused even after the object gets deleted from the system
Capability as a protection mechanism has been discussed before, e.g., HYDRA
In this paper capability as an addressing scheme is discussed
Objects are addressed by capabilities
User program can read, store, and restore capabilities
to/from memory and register
to/from disk
Segmenting is a good mechanism to address and share objects among processes
Segments, however, are referenced by a virtual address, which is process-specific:
Each process has its own segment table which maps segments to process-specific segment number

The Problem of Shared Segment References
If segments are referenced by a process-dependent way, such as
segment number of process segment table,
sharing segments is impossible. See Fig 2.

Context-Independent Addresses

We need a scheme in which objects are addressed in a process-independent way and still relocatable

Solution 1: Uniform Address

Make shared segments referenced by the same way (such as the same seg #) by all processes sharing them
Segment numbers of shared segments should be assigned centrally
Ruled out the possibility of a process executing several independently constructed segments
Burrough System takes this approach
User should builds all her program at once -> Compiler assigns segment number and embeds the number within call statement

Solution 2: Indirect Evaluation - Multics approach

Introduce one more level of indirection: See Fig 4
Each independently written function has its own linkage segment per process
Addresses in the shared function are indexes into the linkage segment for the process
Entries of the linkage segment indexes back into the process's segment table
Linkage segment is dynamically created when the process executes the shared function first time
Cons
Extra space for linkage segments, extra overhead, extra memory reference
Inadequate
Different kind of segments: process segment & linkage segment
No provision for inter-related but independently prepared data segments

Solution 3: Multiple Segment Table

Segment table per the pair of (process, function)
Segment numbers appearing in a function index into the segment table of (the process, the function)
Cons
Process-wide information is lost
If a parameter being passed is an address (segment number + offset), the segment number is the index into the caller's segment table, but NOT the callee's segment table.

Solution 4: Capability Addressing

Use capabilities (= absolute address) to address anything
Process dependent object (data objects in Fig 6) can be correctly addressed by loading the absolute address into the predefined register--actually hard-coded in the program: register 0 in Fig 6
The array of registers can be used instead of segment table
Register (including PC) should be able to hold capability
Process independent object (= shared object) can be addressed by simply hard code the address

Comparison of Relative and Absolute Address

Multics's full path name is a kind of absolute address, but cumbersome because it is variable size
Lack of absolute address is one source of inefficiency in terms of linking cost and programming efforts

Hardware Implementation

Integrated solution is required
OS which supports capability mechanism for protection but runs on conventional machines is not sufficient
CAL_TSS, BCC, SUE, HYDRA, ...
Machines which are potential to support capability addressing but lacks of supporting OS are not sufficient either

Integrity of Capabilities

Because capabilities contains access control, they should be protected from user program creation and modification
No modification or arithmetic operation on capabilities should be allowed
Two approaches: Tagged & Partition
Tagged Approach
Tag each word as being data or capability
No arithmetic operation on capability
No copy from capability to data, vice versa
Cons:
Memory waste to store tag
Capability tends to be longer than data
Partition Approach
Partition segments into capability segments and data segments - determined at creation of a segment
Partition registers into capability registers and data registers
No cross partition operation is allowed
Cons
Most object needs data and capability at the same time -> two segments per object
Computations get complicated
May require extra disk access for capability segments

Address Translation

To users, capability is just an address
Address = capability of segment + offset
User program can manipulate capabilities as it does conventional address
The capability, however, given by user program should be translated into physical address!
Hardware suggested
Hardware assigns a unique key for each segment upon its creation
Hash Table in disk:
Hashed by the segment key
Each entry has the address of the segment in disk, its size, and access permissions
Hash Table in main memory - a cache of disk hash table for active segments:
Hashed by the segment key
Each entry has:
presence bit
the address of the segment in memory
the address of the segment in disk
segment size
access permissions
Given the capability of an object, which is (unique key of the segment + offset), address translation is obvious

Paging

When segments are allocated in terms of "natural" units for the problem, segments become fine-grained enough and mostly smaller than page size
Page is not always the best choice
Even inverse paging--having multiple segments in a page--should be considered

Instruction Sets

Instruction set should be extended so that capability manipulation may be allowed as that of ordinary addresses does
enter instruction suggested
Move the control to the first address of a subroutine
Change the process's capability to that of subroutine
enter access permission also suggested
weaker than read or execute
only allowed to enter the segment through entry points

Stack

Because the capability is embedded into each subroutine, using a single stack for a process is not adequate
Solution: each segment for stack frame (activation record) and discard the segment after returning to the caller -> great overhead
Somehow the stack frame of caller should be protected from callee and vice versa

Evaluation

Pros: Recognize the limits of the segment system--sharing segments in relocation system, which is still true
Cons:
What is absolute address is being challenged:
System-wide unique key is possible, but what if the segment should be shared or copied across systems
World-wide unique key can't be expected!