Re: l4ka Digest, Vol 30, Issue 12

[Frank Mehnert]
> Espen,
> On Friday 02 June 2006 15:58, Espen Skoglund wrote:
>>> Sure, Pistachio sigma0 can map pages it can't access, it just
>>> means that you complicate the issue of setting up and managing
>>> page attributes (uncached, write-through etc) since sigma0 can't
>>> modify the attributes of those pages.
>> 
>> I wouldn't say that it complicates the issue more than it already
>> is.  Mind you, MemoryControl() is really badly defined right now.
>> The way you describe things with page attributes assumes one
>> particular definition of how these things are supposed to work.  If
>> you remember the proposed MapControl() syscall (internal mail, not
>> on l4ka@ mailing list), you might also remember a lengthy mail
>> where I among other things described how managing page attributes
>> from sigma0 is a terribly, terribly bad idea.

> would appreciate some more comments on this from you. Naively
> spoken, different physical frames can have different page
> attributes. It is not necessary (as far as I can see) that the same
> physical frame is mapped cacheable to one address space and
> non-cacheable to another address space.  The same applies for write
> through / write back.

> Since Sigma0 is the ``creator'' of physical pages it should be able
> to manage page attributes and could do this using
> MemoryControl. Other servers asking Sigma0 to map a specific page
> specify their wishes for the attribute of the corresponding physical
> frame. Sigma0 is also able to setup MTRRs if requested since it is a
> privileged task.

I've attached the text I sent out together with the proposed MapCtrl
syscall in June 2004.  Hope it helps clear up some of the ideas.  I
should note that after I sent out this mail I also realized that you
need to associate some maximum rights with each mapping in addition to
in-bound and out-bound rights.  This is required to enable IPC to
still be used for enforcing security policies.

The "new" mapping database which has been in the Pistachio kernel
since January last year implements the proposed changes.  It has been
heavily tested for stability through a test suite running millions
upon millions of random operations (maps, unmaps, different page
sizes, reading and resetting reference bits, etc.)  I would go as far
as to say that it is "known" to be more stable than the old MDB.

	eSk


================================================================

1. DEALING WITH SUBPAGES

During the discussion about whether sigma0 should perform
MemoryControl before of after mapping the page to the client, the
question was raised what to do when performing MemoryControl on a
smaller page size than what was currently mapped into the current
address space (e.g., performing memctrl on a 4KB page when there
exists only a 4MB mapping in the space).

After reasoning about it, the appropriate way to solve the problem is
to do the same thing as when the problem is encountered during Unmap.
Now, as discussed several times before, there are basically three
things that can happen for the Unmap case:

  1. The operation is void.
  2. The large page is split into smaller pages and the operation is
     performed.
  3. The larger page is unmapped.

Since a Map operation implicitly performs and unmap first, the same
options also apply to the Map.

Currently, the Pistachio implementation takes the first approach (and
enters kernel debugger to inform the user).  The spec, however, says
that the operation is undefined.  As several people have suggested
earlier, it would probably be a better idea to specify that option 3
should be taken.  Of course, in the spec this would have to be
expressed in the form of fpages.  The current snippet is an example of
how this could be specified (taken from the V5e branch of the refman):

  Mapped fpages are considered inseparable objects.  That is, if an
  fpage is mapped, the mapper or the mappee can not later partially
  unmap the mapped page; the whole fpage must be unmapped in a single
  operation.  The mappee can, however, partially *map* fpages
  (objects) of smaller size.  Upon partially unmapping an fpage of
  size s' out of an fpage of size s (i.e., s > s'), the kernel only
  guarantees to unmap an fpage of size u where s >= u >= s'.  The
  actual size of the unmapped fpage depends on the kernel
  implementation.

The above snippet could be extended so that it also works for other
memory operations (i.e., memctrl).  The memctrl syscall would then
signal an error if the user tries to apply memctrl to a page size
which is too small (silently failing in this case would be a bad
idea).  The only thing the user has to do is to know what the size of
the object (fpage) it got mapped to itself is, and use this size to
ensure that memctrl succeeds.

2. ENTER GLOBAL MEMORYCONTROL

The reason why the above scheme to deal with smaller page sizes works
is because the user knows what page size he is operating on; either by
inspecting the page size of a received mapping or by the means of some
other protocol established with the pager.  If we perform a memctrl
operation with the global bit set, this no longer applies.  That is,
the global memctrl operation also works upwards in the mapping
hierarchy, and there is no way to infer what fpage sizes (object sizes)
are being operated on higher up in the hierarchy.  Or more accurately,
there is no way for a user to infer whether a page higher up in the
hierarchy is operated on using a larger page size.

The conclusion is that being able to perform global memctrl operations
is a bad idea.  It breaks things in uncontrollable ways.  We must get
rid of it.

The question now is: why did we introduce the global operation in the
first place.  The answer is twofold:

  1. It allows us to achieve correctness and avoid memory paradoxes.

  2. It allows user-level to limit the cache usage (e.g., for ensuring
     that certain data will not be evicted from the cache).

What we propose is to slightly change the definition of the global bit
so that it only applies downward in the hierarchy (i.e., a sticky bit,
enforce memory attribute bit, or whatever one would like to call it
bit).  Such a solution would still be able to achieve the two goals
above.

To make the new bit more alike the permission bits of fpages it would
also be a good idea to invert the semantics of the new bit---if (and
only if) the bit is set is the child allowed to change the memory
attribute.

3. OBJECT SIZES IN SIGMA0

The main idea presented above is that the object (fpage) sizes that
are mapped into address spaces are well known and can be used to
ensure proper Unamp/MemoryControl semantics.  A still existing problem
is that sigma0 does not receive mappings from anyone---it magically
owns all memory upon startup.

Since sigma0 magically owns all memory there is no way for sigma0 to
infer what its object (fpage) sizes are, and thus figure out how to
achieve the desired semantics for memctrl.  (Side note: Is sigma0
allowed to flush memory from itself?  What happens if it does?)  Now,
if sigma0 is "granted" one single fpage that spans the whole memory,
sigma0 can not perform memctrl unless it performs it on the whole
memory.  The natural choice is therefore to define that sigma0
"receives" memory in fpages of the smallest possible granularity.
This, however, has its limitations; mainly related to
implementation/optimization choices:

  - If sigma0 is allowed to do memctrl, the kernel must offer some way
    to store this within sigma0.  This implies that the kernel must
    either implement a page table for sigma0 (not needed on
    architectures with software loaded TLBs), or some other (variable
    sized) data structure.

  - Upon TLB faults, the kernel must inspect the above mentioned
    structures to set the appropriate memory attribute on TLB
    insertion.

  - Since memory attributes are inherited on mapping, the fpage
    mapping algorithm must inspect the above structures on mappings
    from sigma0.

To avoid the memctrl problems with sigma0 we propose to specify that
the memctrl operation in sigma0 is undefined.  Some implementations
may define it, others may not.  Defining memctrl for sigma0 may be
necessary, e.g., if sigma0 needs to access the screen memory
uncacheable for debug output.  Whether the kernel allows memctrl for
sigma0 can be signaled via a kernel feature string (see pages 5 and 9
in the reference manual).

Now, since sigma0 is not allowed to perform memctrl, requesting memory
attributes through the sigma0 protocol no longer makes sense.  Memctrl
must be performed by the requesting client instead.

4. MAPCONTROL: UNIFYING MEMORYCONTROL AND UNMAP

Having the new memctrl operation work recursively on subtrees makes
the memctrl operation very similar to Unmap.  The only difference
being that Unmap is only able to rescind, not to extend or change the
attributes/permissions of a subtree.

The logical step to take is to unify Unamp and MemoryControl so that
Unmap now can be used to extend access rights as well as revoking
them.  To avoid name confusion we propose to call the new system call
MapControl.  MemoryControl is not used since we also want to use the
same system call for managing the I/O port space, etc.  The Unmap and
Flush convenience functions can be used unmodified to achieve the same
results as today.

5. TRANSITIVE UPGRADES VS. LOCAL POLICY

A really nice thing about allowing extension of access rights via
MapControl is that one can perform access rights extensions
asynchronously and transitively (i.e., throughout a whole subtree).

Of course, there are problems with the new semantics (or else we would
probably have had it specified a long time ago).  For recursive
mappings it might be that the child mapping only wanted to map the
page further on with a read-only mapping.  Someone higher up in the
hierarchy should not be allowed to override this local policy by
performing a MapControl operation.  Likewise, a child mapping may have
good reasons for marking its own memory as read-only.  Someone higher
up in the hierarchy should not be allowed to override this.

The crux of the problem is that the MapControl operation is
asynchronous---there is no agreement required from the mappee side.
We have chosen to solve the problem by separating access rights into
inbound and outbound rights.  [In-space and cross-space permissions in
the proposed spec.]  Both inbound and outbound rights are specified
during the map operation; the outbound rights are specified by the
sender (via fpage rights in the mapitem) and the inbound rights are
specified by the receiver (currently hardcoded to complete rights).
The following example illustrates a setup where A has mapped a page to
B, and B has mapped the same page to C and D.

      IR:OR         IR:OR         IR:
        A     --->    B     --->    C

                      :OR         IR:
                            --->    D

The effective access rights of a mapping (i.e., the access rights
recorded in the page table) are calculated recursively upwards in the
hierarchy by the intersection of all relevant inbound and outbound
rights.  The definition of the effective access rights is as follows:

   ER[current] = ER[parent] & OR[parent->current] & IR[current]

The MapControl syscall can change either its own inbound rights or the
outbound rights of all its mappings.  It can *not* change the inbound
rights of its child mappings or the outbound rights of its parent
mapping.  One way to look at this is that a thread can only change its
own part of the contract negotiated with its map partners.  Note that
the MapControl operation to change the access rights is in itself not
recursive, but since the definition of the effective access rights is
recursive the kernel must parse through the mapping tree to perform
the necessary updates on the effective rights.

The new scheme for dealing with access rights solves the problems of
asynchronous modification and transitivity.  It is very similar to
the way Andy handled access rights in the Strawberry kernel.

6. MP SCALABILITY AND OPTIMIZATION HINTS

The new MapControl syscall additionally handles two issues relating to
scalability in MP systems and allowing the user to specify
optimization hints.

The MP scalability aspect comes from not needing to report back the
reference bits unless explicitly specified.  The optimization hints (in
addition to not needing to report reference bits) comes from having
reference bits being undefined until they are reset for the first
time.  This allows a newly created address spaces to be created with
reference bits set to avoid expensive bus locks or traps upon first
access to a page.  In addition, one can avoid resetting the reference
bits if one are not interested in them.

7. MAPCONTROL IMPLEMENTATION ISSUES

The new inbound/outbound permission scheme implies that eight new bits
must be recorded in the mapping database and/or page tables.  Four
bits for the inbound rights and four bits for the outbound rights (the
fourth bit being the permission to modify the memory attributes).
Some of these bits are not necessary on certain architectures.  IA32
does for instance unify the read and the execute bit.

Storage for the bits can be allocated in multiple ways:

  - There's one more bit available in the mapnode pointers (pointers
    must be aligned to at least 4 bytes).  On 64-bit architectures two
    more bits can be taken from the pointer values (pointers are 8
    byte aligned).

  - On some implementations the pointer values have certain bits
    hardwired.  E.g., all in-kernel pointers always have the two
    uppermost bits set.

  - Some architectures have free bits in the page table entries.

  - Some architectures can take some bits from the space identifier.
    E.g., on IA32 the space identifier is a pointer to the page table
    (which must be 4KB aligned).

  - If no other bits are available, take some bits from the tree depth
    field (current default is 11 bits).  It should be noted that this
    does not mean that one limits the depth of a mapping tree.  Even
    if one has 11 bits for encoding the depth, the kernel must have
    some way to deal with a tree which has a depth > 2048.  This is
    achieved by "re-inserting" another tree below a mapping node, much
    the same way that one branches off new trees from rootnodes in the
    current implementation.  [Note that this is not yet implemented in
    Pistachio.]

The algorithmic changes to deal with the new permission model should
be straight forward to implement.  One basically needs to perform some
more ANDing when setting the effective access rights within a subtree.

8. CONCLUSION

The new unified Unmap/MemoryControl system call integrates two closely
related mechanisms provided by the kernel.  It also extends the
flexibility by allowing to transitively and asynchronously extend
access rights within a subtree.  Such an operation is extremely
helpful when implementing stuff like fork-followed-by-exec.  The new
mechanism should prove easy to implement and require non-substantial
modifications to the kernel.