Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2001-05-15
2004-11-30
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S200000, C711S202000, C711S163000
Reexamination Certificate
active
06826672
ABSTRACT:
BACKGROUND OF THE INVENTION
Since the advent of computers capable of running several programs concurrently, data security has been an important issue in system design. When different programs share the same hardware resources it is essential to ensure that they are not able to access or alter each other's data unless sharing is explicitly allowed by the programmer. Data security within a single program is also desirable to the developer, as it eliminates potential sources of program errors.
Traditionally, inter-process security has been addressed by maintaining a per-process page-table providing a translation from virtual address to physical location. This gives each process a separate address space and allows the operating system to ensure that it is impossible for data of a process to be inspected or corrupted by other applications. While such an approach is functional, there are three main objections to it. First, a process dependent address translation mechanism dramatically increases the amount of processor state associated with a given process. This makes context switching correspondingly slower, thus increasing system overhead and reducing efficiency. Second, data can only be shared between processes at the page granularity. Finally, this mechanism does not provide security within a single context; a program is free to create and use invalid pointers.
The idea of using capabilities for addressing first appeared formally in a paper by Jack B. Dennis, Earl C. Van Horn, “Programming Semantics for Multiprogrammed Computations,” Communications of the ACM, Vol. 9, No. 3, March 1966, pp. 143-155, and further developed by R. S. Fabry, “Capability-based addressing, Communications of the ACM,” 17(7):403-12, July 1974. In concept, each capability specifies a segment of memory and a set of permissions detailing the operations permitted upon that region. Fabry's scheme represents each capability as a set of permissions and a segment-identifying unique ID. A hash table keyed on UIDs contains segment base and bounds information; a small associative cache preserves mappings for the most recently accessed segments. Fabry's approach is thus efficient when using small numbers of segments but inappropriate to a system in which every independently-allocated object is placed in its own segment.
A number of early capability systems used centralized tables mapping from capabilities to segment addresses; several are described in Henry M. Levy, “Capability-based computer systems,” Digital Press, 1984. While some of these machines segregate non-capability data from capabilities in distinct segments, the evolutionary trend is clearly toward tagging capabilities in a hardware-recognizable fashion so that they may be freely intermingled with other data.
Most modern capability systems have avoided the centralized table by embedding object addresses directly in the capability representation. We will not attempt to list them all here, but rather to provide a small number of examples representing keypoints in the design spectrum.
In the ORSLA capability-system described in Peter B. Bishop. “Computer Systems With A Very Large Address Space and Garbage Collection,” PhD thesis, Massachusetts Institute of Technology, May 1977 a capability contains permissions bit, the address of the first word of an object, and a small size field (5-9 bits). With each memory reference, an offset is added to the base address in the capability.
The first bit of the size filed distinguishes small and large objects. For small objects, the remaining bits simply represent the size in words. For large objects, the remaining bits are divided into exponent and mantissa components, the exponent defining a block size and the mantissa defining a number of blocks in a segment. This floating-point number can describe (at coarser granularities) much larger segments than can an integer represented with the sane number of bits. Rather than setting the value of the size field to be slightly larger than the number of words in the contained object, ORSLA sets it to be slightly smaller; the object's precise size is stored in the object itself. When a reference to the last few words of a large object violates the capability's size field, microcode performs additional memory references to check the precise size stored in the object.
This scheme gives ORSLA precise object bounds at the cost of an extra memory reference for words toward the end of an object. Object allocation is extremely easy in ORSLA—objects may be allocated consecutively by simply advancing a shared allocation pointer.
The Symbolics 3600 Lisp Machine architecture (David A. Moon, “Architecture of the symbolic 3600,” 12th Annual International Symposium on Computer Architecture Conference Proceedings, pages 76-83, 1985) features per-object pointers which directly reference the first word of their target objects. Rather than encoding bounds information in these pointers, however, the object size is encoded in the object's first word; performing bounds-checking on object references requires an extra memory reference. Note, since a Symbolics pointer contains no permissions bits, it is a fairly degenerate form of “capability”—possession of a pointer implies permission to perform any and all operations on its target object.
The M-machine (Marco Fillo, Stephen W. Keckler, William J. Dally, Nicholas P. Carter, Andrew Change, Yevgeny Gurevich and Whay S. Lee, “The m-machine multicomputer,” in Proc. 28th Annual International Symposium on Microarchitecture, pages 146-156, 1995) uses a guarded pointer format (described in Nicholas P. Carter, Stephen W. Keckler and William J. Dally, “Hardware support for fast capability-based addressing,” in Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VI), pages 319-27, October 1994 and U.S. Pat. No. 5,845,331, which are incorporated by reference in their entireties) to encode permissions, an address, and a segment length descriptor L. The upper bits of the address are fixed, while the lower L bits are mutable by pointer arithmetic; the segment is thus of size and alignment 2
L
, and the capability may point to any address within it. The base address of a segment may be computed by simply setting the L tower bits to zero, and a user stays within the defined segment so long as the base bits remain unchanged. This scheme requires hardware-recognized (i.e., tagged) capabilities and a small amount of hardware support in the processor to verify bounds information in parallel with performing pointer arithmetic. Notably, it requires neither indirections through a central table, nor the embedding of size information in an object representation.
SUMMARY OF THE INVENTION
Two disadvantages of the M-machine approach both arise from the exponentiated segment sizes. First, for an object only slightly larger than some power of two, nearly half of the segment allocated to hold it will be unused; this internal fragmentation both wastes space and means that accesses which overrun the end of the object will not immediately be detected as they will still fall into the segment. Second, due to the strict alignment requirement, a simple allocation strategy based on advancing a pointer may wind up wasting nearly half of memory due to external fragmentation.
In accordance with the present invention, those disadvantages are reduced by defining a memory segment by a block size and a number of blocks in the segment. An index into the memory segment, which identifies the block to which an address of the pointer points, is also included in the pointer representation in order to allow computation of the full bounds of the segment relative to the pointed-to address.
In accordance with one aspect of the invention, a pointer representation within a data processing system comprises a block field which defines a block size and a length field which defines a number of blocks in a segment of memory. An address in the representation points into the segment of memory. A finger field de
Brown Jeremy H.
Grossman Jeffrey P.
Huang Andrew W.
Knight, Jr. Thomas F.
Hamilton Brook Smith & Reynolds P.C.
Massachusetts Institute of Technology
McLean-Mayo Kimberly
LandOfFree
Capability addressing with tight object bounds does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Capability addressing with tight object bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capability addressing with tight object bounds will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327654