[prev in list] [next in list] [prev in thread] [next in thread] 

List:       eros-arch
Subject:    Re: [EROS-Arch] Patent relevant to memory mapping
From:       "Jonathan S. Shapiro" <shap () eros-os ! org>
Date:       2001-09-04 3:18:25
[Download RAW message or body]

Charlie:

Very clever. I'm afraid I need to document some related prior art, though...


Years ago -- before you went to Tandem, in fact -- Norm and I discussed a
similar upward recursion strategy. We observed that a slot change in a node
could fall (possibly simultaneously) into only two cases:

1. The node was a producer of one or more tables, in which case the implied
evaluation is immediately determinate given only the node size, the page
table size, and the slot position -- these can be used to directly derive a
contiguous sequence of PTEs to be invalidated. Note that no recursion is
required at all for this case, because it is known that (a) all of the PTEs
will fall within a single table (b) the impacted PTEs are linear, and (c) it
is cheaper to simply iterate in the PTE table than to recurse -- there is no
benefit to filtering out the invalidation of entries that are not currently
valid (and therefore are uncached by any TLB).

2. The node was dominated by some set of higher nodes that was the producer.
As with case (1) there is some contiguous linear sequence of implicated
PTEs; the problem is to figure out where this sequence begins and how long
it is. The start/end of the sequence can be determined by key ring traversal
combined with an inverse walker in order to (a) locate all dominating
producer(s) of a page table whose LSS dominates the LSS of the containing
node, and (b) derive the path to the slot in question, and thereby determine
the range of PTEs to be invalidated.

As you say, the problem is to bound the traversal.

After thinking about it, my conclusion was that the upward traversal was a
worthwhile way to shrink the depend table drastically, but that the best
engineering tradeoff was to preserve the depend table for the hard cases. In
particular, there are two exceptionally common cases:

(a) The case in which the producer node is the parent of the node where the
slot is being changed, and
(b) The grandparent case

On balance, my conclusions at the time were as follows:

1. Avoiding the depend entry in the case where the containing node is the
producer is worthwhile, and imposes no loss of information. It
simultaneously eliminates the most expensive source of false invalidations.
2. Recursing up one level to find all parents that are producers is
possible, and probably desirable if a keyring-like data structure is
available.
3. Recursing up two levels to find the producer is probably not worth it in
EROS, because there are generally only two node levels per page table level.

In the final analysis, I did not implement this logic because I was
unconvinced (and I remain unconvinced) that keyrings as we now know them
would scale to large memories. I wanted to preserve the possibility of key
indirection (object) tables, and also the possibility of "chains of chains"
of keyrings.

However...


If the limited (recurse upwards to parent of containing node) strategy is
implemented, many of the depend entries evaporate -- there is an immediate
reduction of O(node-size^2) entries. Note that detecting when the depend
entries are needed is very simple -- as you walk downward to build the
mapping, you simply remember the last three *effective* node LSS values you
traversed. If parent-node or has an effective LSS corresponding to a page
directory LSS, the reverse recursion will work and you can skip building the
depend entry.

Two more tricks can be used during map construction to get the remaining
cases: create a depend entry for every node whose capability LSS was greater
than the expected LSS at  that point in the traversal. This allows you to
find a containing PTE range quickly in that case. Actually, these want to be
expressed as node dependency entries for uniformity -- see below.

Last trick, used only if node tree is very tall or using small nodes
relative to page tables: build a full **node** depend entry at alternating
nodes, provided that node is not already a producer and resetting the notion
of alternating at each producer. This ensures that there is always a depend
entry describing either the containing node or the parent of the containing
node.

This last optimization means that simply building depend entries for
alternating nodes that are not producers is sufficient to limit that
backwards recursion to depth 1 in all cases.

The solution in general requires a shift from building depend entries for
slots to building depend entries for nodes. The per-node depend entry is of
the form

    base pte *
    nPTE
    word (one bit per slot) indicating slots that have been traversed
        while building a mapping associated with this depend entry

This alternative dependency format -- which effectively includes the
"involved" bit (though places it in the depend entry) was described on the
eros-arch list years ago.

Finally, this strategy adapts gracefully for window keys.


Jonathan

_______________________________________________
eros-arch mailing list
eros-arch@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/eros-arch

[prev in list] [next in list] [prev in thread] [next in thread]