[mkc2008] Fwd: Mapping - Mapping DB

Marcus Voelp voelp at os.inf.tu-dresden.de
Thu Apr 9 12:07:24 CEST 2009

Jan Bierbaum wrote:
> Marcus Voelp meinte am 07.04.2009 09:02:
>>> A map could for example try to insert new nodes in a subtree
>>> currently being deleted by a concurrent unmap.
>> Yes, that's an issue and there are various possible solutions to this:
>> 1) don't worry, unmap will catch it (proper synchronization provided)
>> 2) remove rights in preorder pass => map can only establish nodes with
>>    reduced rights; unmap may just skip the node in its postorder traversal.
>> 3) prevent maps on a to be unmapped subtree
> I have some troubles with 2).
> Now we have two passes - the first pass (preorder) just reduces rights
> on MDB nodes. Why are there rights in the MDB nodes at all? 
I didn't say so.
> Isn't it
> enough to have them in the page tables? 
They are in the page table entries.
> What if a mapping is to be
> revoked - are all rights removed? 
Then all rights are removed but not the mapping. The mapping is only
removed in the postorder pass.
> When are the page table entries
> updated/deleted?
Possibly in both passes, but this depends on how you correlate mapping
nodes to their page table entries.
> The second pass (postorder) removes all nodes that don't hold rights
> anymore, I guess. 
> But if we skip nodes added between the passes, those
> would be "orphaned". 
Whether you are able to skip these nodes depends on your tree
representation. Skipping works for a child list representation but not
for linked list - depth.
> Except if there will be no new node created for any
> mapping originating from a node lacking rights (MDB node whose rights
> were removed completely in the first pass).
Right: There can't be orphaned nodes because to create a node you must
map at least one access right.
> Could you please give some more details about option 2? Or maybe an
> example...
A(rw) - B (r) - C (r)
           \ D(rw)

unmap (A, -r) || map B(rwx)-> E || map D(rwx) -> F

unmap removes r from each PTE corresponding to the nodes, assume the
maps are after the preorder pass then we have

A(w) - B() - C()

the postorder pass then just removes empty right nodes



More information about the mkc2008 mailing list