Re: self-paging

[Bas Wijnen]

On Wed, Nov 30, 2005 at 08:14:32PM +0100, ness wrote:
> Bas Wijnen wrote:
> >On Wed, Nov 30, 2005 at 03:49:48PM +0100, Marcus Brinkmann wrote:
> >[...]
> >So strictly speaking it may not be self paging.  But it is much stronger 
> >than
> >advisory.  The system is not allowed to swap out pages in a different order
> >than the process indicates.
> >[...]
> >>It seems to me that apart from this difference, your proposal boils
> >>down to: "Add noise to the system to reduce the bandwidth of covert
> >>channels", which is the typical approach if all else fails.
> >
> >
> >I wouldn't call the delays noise, but rather a low-pass filter.
> 
> I don't understand this.

The covert channel consists of seeing changes in system load, in particular
memory pressure.  If one process can make sure an other process is instantly
having a page swapped out (or in), then there can be a lot of changes per
second: that is a high-frequency signal.  By delaying the effect using a decay
and redistribution system, the number of bits you can transfer per second goes
down.  That is, high frequencies (fast changes in memory pressure) don't reach
other processes at all, while low frequencies (a process allocates a huge
chunk of memory and keeps it for some time) do, but only slowly.

> To my view, there are several levels of (self-) paging:
> 
> - the OS completely does paging
>  -> the applications don't know whether a particular page is in memory
>     or not and cannot decide in what order pages are to evict

Right.  The "traditional" approach, which we don't like.

> - the app indicates in what order to page out pages (but still doesn't
>   know whether a particular page is in memory or not)
> - the application is involved into the complete paging process
>  -> the app knows what pages are in memory and what not and decides the
>     order of page-out (this _can_ be realized by notizing the
>     application on memory pressure and requesting it to evict a page)

According to this classification, my proposal falls in the third category.
The application decides which pages are in memory and which aren't, but within
limits: no more than its quota may be in memory.  The process is not requested
to evict a page, because it may refuse to do so, resulting in denial of
resource, and this cannot be detected.  However, the process is requested to
prepare its list of pages in the order they should be evicted.  You could see
this as a request to tell which page to evict, except that the actual eviction
may be delayed for a long time.

> I think we have a covert channel whenever an application knows whether a 
> particular page is in memory or not (because it then can count the pages 
> in memory and this is sth. the OS has to change on the behaviour of 
> other applications).

There is a covert channel whenever one process has any influence at all on the
other.  This is not related to self-paging.  If the process doesn't know which
pages are in memory, it can still find out by reading from the page and
checking if it took nanoseconds or milliseconds.  If the system is noisy (on
purpose or not), then the process may need to average over a number of tries.
This makes the communication slower, but it can still take place.

The only way to close this channel is to never change a physical memory quota
which has been given out.  In practice this means that either we will not be
able to start new processes really soon, or memory-intensive processes will
run much slower than needed (because they have to swap their pages out, even
if there is free memory available, because it's not available _to them_).
This may be acceptable for systems which need hard real time (I think they
don't really have a choice), but it isn't for the Hurd.

> So there still is a covert channel in your proposal (it only needs some 
> time to transfer the "messages").

Definitely.  I never thought otherwise.  I'm sorry if that wasn't clear from
the start.  What I was talking about was narrowing the channel, not closing
it.

Thanks,
Bas

-- 
I encourage people to send encrypted e-mail (see http://www.gnupg.org).
If you have problems reading my e-mail, use a better reader.
Please send the central message of e-mails as plain text
   in the message body, not as HTML and definitely not as MS Word.
Please do not use the MS Word format for attachments either.
For more information, see http://129.125.47.90/e-mail.html

signature.asc
Description: Digital signature