[coyotos-dev] Guarded page tables

Charles Landau clandau at macslab.com
Thu Jun 14 17:09:53 EDT 2007


At 4:41 PM -0400 6/14/07, Jonathan S. Shapiro wrote:
>On Thu, 2007-06-14 at 10:47 -0700, Charles Landau wrote:
>  > 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.

I see - binary tree. But it's the tree that is binary, not the nodes.

>  > I don't see the complexity with variable fan-out.
>
>Right. We didn't either. When it finally hit us, we were pretty
>surprised.
>
>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.

That problem is a result of allowing GPTs to have any l2v, not a 
result of allowing GPTs to have a fan-out of either 8 or 16.

>  > 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?

In spaces that grow, they obviously shouldn't be in any slot, because 
the space could grow to include that slot.

But point taken. You can optimize a few cases by allowing an arbitrary slot.


More information about the coyotos-dev mailing list