L4 Mapping question

[Michael Hohmuth]

Robert Kaiser <rob at sysgo.de> writes:

> I was aware that the bookkeeping would have to be in the kernel, otherwise
> flush couldn't work as described in the manual. Only, how does it work ?
> 
> Theoretically, each task could map each of it's pages to up to 2047 other
> tasks. So, the kernel would need to maintain ~2K entries per mapped page
> and task. This can't be! The only explanation I can think of right now
> is that the kernel allocates room for entries dynamically, assuming that
> the actual number of required entries will always be far less than
> the theoretical limit. But that would mean you can break the system
> simply by doing a big enough number of mappings.

Each mapping of a physical page from virtual address VA1 in a task T1
to VA2 in T2 is kept track of using a kernel data structure called
``mapping entry.''  This data structure is allocated dynamically, but
from a fixed-size pool (where the size can be specified at compile
time or boot time).

It's true that you can break the system by establishing an excessive
number of mappings.  There are several ways to deal with that, but I
don't think any of them has been implemented in the freely-available
research kernels; one way is detailed in Jochen Liedtke et al.'s paper
``Preventing Denial-of-Service Attacks on a µ-Kernel for WebOSes''
which is available from
<URL:http://os.inf.tu-dresden.de/papers_ps/jochen/Denhot.ps>.

> On Mon, 22 Feb 1999, Volkmar Uhlig wrote:

> > In the current L4-implementation of Jochen Liedtke, one mapping entry is 16 
> > Bytes.The Alpha implementation (done by me) needs 32 Bytes per entry (64 
> > bit address space - and a lot of trix). The Fiasco kernel does not use 
> > lists. They need about 4 Bytes per entry + an some overhead per frame (I 
> > left bevore it was finished)
> 
> I am getting the distinct feeling that I am missing something
> very simple :-(. So, at the risk of looking like a complete fool:
> How do you keep track of up to 2K tasks in a 16 Byte entry ?

The 16-bytes structure is what I described as a ``mapping entry''
above.  Mapping entries belonging to one physical page are linked to
each other in a binary-tree structure using pointers.

Michael
-- 
hohmuth at innocent.com, hohmuth at sax.de
http://www.sax.de/~hohmuth/