[coyotos-dev] Guarded page tables

Jonathan S. Shapiro shap at eros-os.com
Thu Jun 14 16:41:38 EDT 2007

On Thu, 2007-06-14 at 10:47 -0700, Charles Landau wrote:
> [Replying to Coyotos-dev which seems more appropriate.]
> At 12:54 PM -0400 6/14/07, Jonathan S. Shapiro wrote:
> >HA/BG make GPT arity variable.
> "Arity" means the number of arguments to a function. I would call this fan-out.

Umm. Fan-out makes sense, but arity is also correct. People speak of the
arity of tree data structures, for example.

> >We are now evaluating the following decision tree:
> >
> >
> >1. Keep/Discard HA bit?
> >    => Discard
> >      2. Replace BG bit with index?
> >         => Yes
> >           All GPTs now same arity, BG cap can live in arbitrary slot
> Is the BG slot traversable? That's undesirable; one might not want it 
> to be accessible.

Not intended to be traversable. The point is merely to let that cap live
in any slot. In particular not to commit it to highest or lowest slots,
because you want to be able to do them in parts of the address space
where things are growing downwards.

> >         => No
> >           GPTs have dynamic arity. Complicates data/control
> >           dependencies.
> I don't see the complexity with variable fan-out.

Right. We didn't either. When it finally hit us, we were pretty

First: l2v in Coyotos does not mean what you described. l2v describes
the span of the *slots* within the GPT, not the span of the GPT. l2g
*also* does not describe the span of the GPT. It turns out that there is
no need to encode the span of the GPT explicitly anywhere.

Problem case: consider a GPT with l2v=2^j. There is a GPT above it with
l2v=2^k, such that (k-j = 17). Thus, the guard is covering 11 or 12
bits, depending on (BG|HA). We need to install a new GPT in order to
support a newly valid address that deviates from the existing valid
addresses in the subtree at bit j+7.

Note that l2v of the inserted GPT could be anything falling in the range
[j+4,j+7], because any of these choices spans the required bit
positions. In the absence of a crystal ball providing information about
future valid addresses, give the criteria for making an appropriate
choice of l2v for the new GPT.

> >    => Keep
> >       2. Replace BG/HA with indices, add walk validity bitmap?
> >         => Yes
> >           All GPTs now same arity, BG,HA cap can live in arbitrary slot
> I see no real benefit in allowing BG and HA to be in arbitrary slots.

They obviously shouldn't be in slots zero and one in spaces that grow
up. The obviously shouldn't be in slots 14,15 in spaces that grow down.
Where should they obviously live?

> >Removing HA eliminates the need for NC protection bit. It appears likely
> >that if HA is re-adopted, many of our applications will turn on NC at
> >their space roots in order to be able to self-manage their spaces.
> At 
> http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/29.html#noclapl 
> there are two arguments in support of no-call, both of which seem 
> weak, and one argument against it, which seems strong. I don't know 
> what we were thinking when we put it into KeyKOS.

If memory faults are delivered to memory keepers, NC is absolutely
required to build certain trust relationships. We simply could not have
done the trusted window system at all without it.


More information about the coyotos-dev mailing list