Hi,
I've been adding mapping trees to my implementation of L4 and I have a question...
The L4 reference manual states that address spaces are constructed recursively. Up 'till now I'd assumed that this was merely notional and that in real systems address spaces would be strictly n-ary trees, not graphs with cycles.
Thinking it through however it's obvious that a task A can map a page P to task B which can then map it back to task A at a different virtual address. Is this allowed in L4? (I assume it is) Is it useful? Could I get away with not allowing it? I ask because my initial implementation includes a quick index from a taskid to a node in the mapping tree (to avoid recursion rather than for speed) but this requires that each task has only a single entry.
Additionally, what effect should an unmap have: if task A unmaped P from task B, would the second mapping in task A disappear? I'd imagine that it would indeed remove the second mapping.
I've had a look at the Fiasco souce and it wasn't clear to me where these situations are handled.
Thanks.
[Martin Young]
Hi, I've been adding mapping trees to my implementation of L4 and I have a question...
The L4 reference manual states that address spaces are constructed recursively. Up 'till now I'd assumed that this was merely notional and that in real systems address spaces would be strictly n-ary trees, not graphs with cycles.
Doesn't make sense to put these implementation restrictions on the system when the system is just as easily constructed without having the restrictions. Of course, the system will not really contain cycles since only one mapping to and address, X, in an address space can exist at a time. Someone mapping the same page back to the same address space further down the tree (or from some other location) would just extend the tree with one more node. (One can think of each physical page frame having a mapping tree associated with them, all frames having their root node located in sigma0's address space.)
Thinking it through however it's obvious that a task A can map a page P to task B which can then map it back to task A at a different virtual address. Is this allowed in L4?
Yes.
(I assume it is) Is it useful?
Yes. Say that a thread A has gotten some memory from somewhere. He doesn't know that it came from thread B, either directly or indirectly through a few other address spaces. Thread A needs to communicate with B and it is decided that the preferred protocol is to share data, i.e., map some memory from A to B. Other examples can easily be constructed. I can't think any place of importance in any current system where this kind of mapping occurs, though.
Could I get away with not allowing it?
That, of course, depends on what you're running on top of your kernel. You should expect, however, that people will come off accusing your kernel of being flawed. ;-)
I ask because my initial implementation includes a quick index from a taskid to a node in the mapping tree (to avoid recursion rather than for speed) but this requires that each task has only a single entry.
I have no idea of how this scheme of yours with an index from a taskid to a node in the mapping tree is supposed to work, but there *are* other well known ways of avoiding recursion. The very last slides on
http://i30www.ira.uka.de/courses/summer00/MicrokernelConstruction/
contains some more info on mapping database implementation techniques.
Additionally, what effect should an unmap have: if task A unmaped P from task B, would the second mapping in task A disappear? I'd imagine that it would indeed remove the second mapping.
Yes, if B had mapped the page back to A the second mapping in A would of course disappear. Conceptually, one shouldn't care which address space the mapping is part of.
I've had a look at the Fiasco souce and it wasn't clear to me where these situations are handled.
These are not special situations. It's just the normal mode of operation, so "these situations" would then be handled in the regular unmap code. On the other hand, I have no idea of how Fiasco works, so I might be happen to be throwing out a load of gobshite here.
eSk
l4-hackers@os.inf.tu-dresden.de