Question about L4 address spaces

Jonathan S. Shapiro shap at
Fri Dec 5 19:38:02 CET 2003

Before sending out anything on the subject of address spaces, I've been
going through everything I could find on how L4 handles them. I now
(finally) understand guarded page tables, and it is *staggering* how
similar these are to EROS nodes -- something that I had assumed must not
be true because of the user-layer map/grant/unmap API. Regrettably, I
was in a very bad state when I first read this work years ago, and I
simply didn't understand it at the time.

For those unfamiliar with EROS, the way to think about EROS nodes is
that they are guarded page tables whose size is fixed at 32 entries, and
whose guard value is defined as:


where the number of x's is determined by the size of the subtree
described. If the maximum number of bytes in the described subtree is
2^k, then there will be log2(2^k) == k don't care bits in the guard

EROS chose to keep all nodes (GPTs) the same size, though Norm Hardy and
recently discussed changing this. The main reason for keeping them the
same size has to do with paging them -- it is convenient for all
pageable objects to be of uniform size. What Norm and I recently noticed
was that this was a restriction on representation size, not on the
logical data structure size -- this last point will make more sense in a

Note that the EROS guard values are significantly less flexible than
those of L4 -- a problem that I had been looking for a way to fix. The
fact that the guard value is restricted to be all zero's means that the
EROS address space tree favors compression of leftmost legs in the
mapping tree. This is useful for code and data regions, but useless for
stack regions and not as helpful as it could be for other sparsely
allocated regions.  I am not convinced that the EROS mapping structures
have any good place to insert a generalized guard value; I need to think
about this carefully.

The EROS wrapper node serves double duty, taking on both the role of the
"alias" GPT type and also something very similar to the
"call-on-reference" GPT type. EROS wrappers provide "call-on-exception"
rather than "call-on-reference". The call-on-exception node translates
no bits, but contains a pointer to a contained GPT that *may* translate
bits. This allows a partially populated space to behave as a normal
space in those regions where it is defined, but fall back to a process
where the underlying space is NOT defined. A similar effect can be
achieved in L4 by expanding a call-on-reference node recursively as
subregions are populated, but this is not exactly the same -- there is a
hierarchy of exception types (invalid -> read-only -> read-write), and
one would like to be able to invoke the exception handler for each. My
provisional belief is that the call-on-exception design is strictly more
general, but that the conceptual difference is quite minor.

So with all of the above being said, the *interesting* difference
between L4 address spaces and EROS address spaces may be reduced to
naming and implementation details. Which brings me to yet another
question (forthcoming).


More information about the l4-hackers mailing list