[EROS-Arch] Extended node fetch/swap
Jonathan S. Shapiro
shap@eros-os.org
Sun, 23 Sep 2001 15:16:51 -0400
This is a multi-part message in MIME format.
------=_NextPart_000_01D7_01C14442.C5C755B0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
I want to propose that we add an operation to the node key that walks a =
node tree using the same algorithm as the current segment tree walker. =
The operation is:
extended_fetch(node, address) =3D> key
extended_swap(node, address, key) =3D> old_key
This should follow precisely the same LSS and windowing conventions as =
normal address spaces. In fact, it should be implemented by the same =
walker code and should implement the same access restrictions.
The walker will proceed through the node tree until it reaches a node =
whose LSS is PAGE_LSS. It will assume that this is a leaf node in the =
tree, and that the desired destination capability resides at some slot =
within this node.
Note that this termination condition has a slightly different logic from =
the one used for address spaces. In an address space, you could place an =
arbitrary further chain of nodes between the PAGE_LSS+1 node and the =
final page key, provided that all of those nodes had LSS > PAGE_LSS. The =
problem with following this logic in the extended fetch/store traversal =
is that if we follow the page translation rules exactly it would be =
impossible to store node keys at the leaves.
Credit where it is due: I believe that Charlie Landau proposed exactly =
this in a previous message at one point.
Jonathan
------=_NextPart_000_01D7_01C14442.C5C755B0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 5.50.4807.2300" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>I want to propose that we add an =
operation to the=20
node key that walks a node tree using the same algorithm as the current =
segment=20
tree walker. The operation is:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2> extended_fetch(node, =
address)=20
=3D> key</FONT></DIV>
<DIV><FONT face=3DArial size=3D2> extended_swap(node, =
address,=20
key) =3D> old_key</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>This should follow precisely the same =
LSS and=20
windowing conventions as normal address spaces. In fact, it should be=20
implemented by the same walker code and should implement the same access =
restrictions.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>The walker will proceed through the =
node tree until=20
it reaches a node whose LSS is PAGE_LSS. It will assume that this is a =
leaf node=20
in the tree, and that the desired destination capability resides at some =
slot=20
within this node.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Note that this termination condition =
has a slightly=20
different logic from the one used for address spaces. In an address =
space, you=20
could place an arbitrary further chain of nodes between the PAGE_LSS+1 =
node and=20
the final page key, provided that all of those nodes had LSS > =
PAGE_LSS. The=20
problem with following this logic in the extended fetch/store traversal =
is that=20
if we follow the page translation rules exactly it would be impossible =
to store=20
node keys at the leaves.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Credit where it is due: I believe that =
Charlie=20
Landau proposed exactly this in a previous message at one =
point.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Jonathan</FONT></DIV></BODY></HTML>
------=_NextPart_000_01D7_01C14442.C5C755B0--