Re: self-paging

[Emmanuel Colbus]

On Sun, 04 Dec 2005 14:26:28 -0500, Jonathan S. Shapiro wrote:

> On reflection, There may be a way to give Bas what he seems to want.
>
> We've agreed that notification is a separate problem, so I'm not talking
> about that right now.
>
> W.r.t. residency pools, we can potentially separate two things:
>
>    1. Specifying the group of pages that compete with each other. 
>       This is the part that the EROS frame pool deals with well.
>
>    2. Specifying which page to shoot down when the pool is full and 
>       a new page must come in.
>
> I provisionally believe that if we want to use any sort of LRU, the
> gathering of age data must be performed by the kernel. Since the kernel
> needs to collect this data anyway, 

Why does it?

> I think that *one* of the policies we
> should have is "LRU w.r.t. the rest of the pool" and that this should be
> directly implemented by the kernel.

Doesn't it suffers from the same covert channel problem? I'm thinking about
two applications which would manage to always have their pages very recently
used, and to use each one nearly the half of the memory. With this policy,
if one of them starts using a little bit more pages, the second one will 
notice that some of its pages have been swapped out (because of the 
latencies), so the covert channel seems me to be the same as 
with self-paging. Well, maybe with a littler bandwith, as the application
will have to detect latencies instead of being directly notified by the
kernel, but a covert channel anyway.

I think a "take a random (or random-like) page and unbind it" policy 
should also be considered; what do you think about it? (I think its 
advantages would be especially in a far greater channel establishment
time - time to wait for a random algorithm to swap out all pages
used by apps who haven't used them for long, but which presence disturbs
the communication. Also, it's a little bit like Bas' proposition : it
gives the kernel a worse response time to memory pressure (the system needs
more time to go to its final state).) 

> But it is also possible to have a protocol in which the kernel turns to
> a "keeper" associated with the pool. Basically, the kernel upcalls the
> keeper (very much like fault handling) and says "make some room in this
> pool".
>
> The keeper can then shoot down member frames explicitly by naming their
> virtual address, using a call of the form
>
>         pool->unbind(va);
>
> One part of this differs from what Bas seems to be proposing: we want to
> be able to associate pools with regions of the virtual space as opposed
> to the entire space. The issue is that we may want to manage the
> residency of shared objects on some collective basis, and to do this, we
> need to be able to associate pools with memory objects. 

Yes, but how would this be an issue?
To handle object sharing, we just need to tell the keeper "the age
of this page has to be recorded HERE (a location which is the same
for anybody sharing the page)"; and the LRU algorithm will work
just fine (well, the swapping out will maybe be more difficult, as 
the page should be swapped out for anybody sharing it, but the kernel 
would have needed a method to swap out shared objects anyway, 
doesn't he?).

> The second issue
> is that I haven't thought through how to go about getting *inbound*
> information to the pool keeper. Does the keeper need to know about the
> order of page inserts?

I don't think so - what would it be good for? Also, the more the keeper 
will know, the most easy it will be to build a covert channel.

> shap

Emmanuel