EROS retrospective -- memory tree
Sat, 25 Dec 1999 17:41:25 -0500
One thing I learned in the last hours of my dissertation work is that the
rules for traversing the memory tree hierarchy in EROS/KeyKOS are very
complicated. The amount of control flow that depends on values stored in
the individual capabilities is huge, with the consequence that the code
does not (and arguably cannot) run efficiently.
Data-driven "options" in the processing include:
Short-circuit traversals (levels skipped). This is surprisingly
Large trees where short trees are expected. This is not too bad.
Window capabilities. This is a total pain in the neck, as window
capabilities can cause the "offset" relative to the current segment to
Red segments, or rather the fact that red segment nodes need special
Multisize segments -- the fact that two capabilities indicating segments
of sizes X and Y (X != Y) can point to the same node. Actually *using*
this feature creates interesting difficulties.
Permissions management, though this isn't really a problem.
Tracking of the current "background segment" (necessary to support
window capabilities), the current keeper and the offset that should be
reported to that keeper.
The format capability is no fun at all.
While it's altogether likely that the code in the current EROS kernel to
manage all of this is more complex than it needs to be, it's still an awful
lot of complexity. I believe in particular that (5) could be eliminated
with little loss, and that this in turn would lend itself to eliminating
A lot of the problem lies in the format in which the information is
encoded: capabilities. Because nodes are used, there are some limits to
where memory-related information can be stored. On its face, the advantage
to the use of nodes is minimizing the number of data types known to the
kernel. This is a chimera, as it forces the kernel to have more
interconversion knowledge to replace the missing datatype. The *real*
advantage lies in limiting the number of different sizes of data structure
that can reside on the disk.
After thinking about how the L4 ideas could be adapted, I am sorely tempted
to make segment nodes a first class type disjoint from nodes, and to
introduce new permission attributes "metadata load/metadata store" which
would control whether the holder of a segment capability is entitled to
read/write the capabilities in the nodes that make up the tree. The
obvious operations would specify an offset (path through the tree), level
in hierarchy (lss) to read/write. This would also simplify some of the
segment keepers and speed them up by moving a multi-invocation operation
into the kernel. Note that the kernel has most of the necessary code to
implement this in place already.
If the segment data structure were separated into a distinct type in this
way, there would no longer be possible collisions between process and
segment objects, which would somewhat simplify dependency and hazard
management. If the set of legal capability types that can appear in such
an object is restricted (as it probably should be), the encoding of some
things can be simplified in ways that let various of the control flow
decisions be merged. Finally, note that if we do this we can *always*
place the segnode's LSS description in the segnode itself, which is a
considerable simplification. Can anyone give a *compelling* case for
building a capability whose embedded LSS does *not* correspond to the LSS
that would naturally emerge from an examination of the tree itself
(ignoring red seg LSS). The red segment case and the format capability can
then be handled by marker bits in the segnode object, and the keeper and
background capabilities can be given official slots in which to live.
Observation: there is no inherent reason why segnodes have to hold a number
of capabilities that is a power of two. It is only that they should hold a
natural power of two of *traversable* capabilities to simplify the memory
The main challenge in doing this is the funny level games. Given a
specification to store at LSS=4 in a given hierarchy, and a tree of LSS=5
appearing in an LSS=3 slot on the same path, there is an inherent ambiguity
about *which* LSS=4 node to store into. I believe that it should be the
earliest encountered, but... Also, what to do if no segnode corresponding
to LSS=4 exists?
Jonathan S. Shapiro, Ph. D.
Research Staff Member
IBM T.J. Watson Research Center
Phone: +1 914 784 7085 (Tieline: 863)
Fax: +1 914 784 6576