[mkc2008] Fwd: Mapping - Mapping DB

Marcus Voelp voelp at os.inf.tu-dresden.de
Mon Apr 6 13:22:51 CEST 2009


> Hello!
> On slide 33 there's an approach of integrating the mapping database's
> nodes directly into the page table. Can this actually be done? 
Yes, some Sydney kernels are implemented this way.
> page tables are quite dense and since the structure is preset by the
> hardware it can't be changed.
On x86 and on ARM you are right, but there are also hardware
architectures such as Alpha that do not define the page-table format but
which instead rely on software to fill the MMU. On these architectures
it is possible to co-locate mapping nodes and page table entries,
however, keep in mind that this puts data that is used only for
revocation (the MDB node) next to data that needs to be accessed for
each page table walk into the same cacheline.

Colocation by a constant offset gives you the same advantage (no search)
without having to modify the page table.

> Which of the techniques for finding the root node (search, caching,
> linking, integration) is used by Fiasco?
> Also there are some issues regarding the helping lock approach.
> Unfortunately this part is very short in the slides (only slide 49) and
> not what is described in Marcus' diploma thesis.
Helping is described in Michael H. thesis. The idea is to have a lock
that when held knows its owner. Scheduling then works such that if a
thread needs this lock it will donate time to this lockholder thereby
helping it out of its critical section.
> Unmapping could take some time because it (potentially) has to remove a
> complete subtree from the MDB and the corresponding page table entries.
> But we want short interrupt latency hence unmapping has to be done
> preemptively. That's when these helping subtree locks come in. So the
> whole subtree to be unmapped is locked with such a lock. But who exactly
> will share this lock? All operations including mappings or only
> concurrent unmaps?
Currently, Fiasco implements such a helping lock at the page frame in
Sigma0 (and when splitting large pages but don't worry). Both map and
unmap grab this lock to modify the mapping database.

With a node based structure and side entries (as in Pistachio), map
needs not to search for mapping nodes and can thus be implemented
atomically. In this case, the framelock needs only to be grabbed during
unmap, provided that single node operations are synchronized in some
other way (e.g., by making them atomic). Subtree locks further increase
the number of parallel unmaps in the tree that corresponds to a single
frame. Only unmap operations, which enter the same subtree, must grab
this lock. This way unmaps that currently work on different subtrees may
proceed in parallel.

> Mapping on the other hand is supposed to happen atomically. But a map
> operation not only appends a node in the MDB but also has to change the
> receiver's page table(s). These are distinct memory operations so atomic
> CPU-instructions won't help. Or are there any atomic instruction that
> perform this task? So maps need to use acquire helping locks too, don't
> they?
Atomic does not necessarily mean implemented with atomic CPU
instructions. Disabling interrupts (possibly in combination with
non-helping ticket locks) are also means to execute code atomically
without having to acquire helping locks. You are right though that both
the insertion of the mapping nodes (which itself needs to update two
pointers) and the page table modifications must be part of the same
atomic operation.


More information about the mkc2008 mailing list