unmap() guaranteed to succeed?

[Marcus Brinkmann]

At Fri, 22 Dec 2006 12:36:56 -0500,
Eric Northup <digitale at digitaleric.net> wrote:
> 
> Marcus Brinkmann wrote:
> > At Wed, 13 Dec 2006 11:51:52 +0100,
> >  <voelp at os.inf.tu-dresden.de> wrote:
> >>  From a security perspective this may really be a problem. Do you know 
> >> how other systems solve it? Like Eros e.g., implements immediate 
> >> revocation by destruction of the intermediate objects. However, 
> >> internally they also have a list  in which address spaces a capability 
> >> is mapped.
> > 
> > Not really.  "Removing an object" in EROS/KeyKOS means incrementing
> > its allocation count, which immediately invalidates all keys pointing
> > to the object, as long as the keys are on disk (recall we are talking
> > about persistent systems).  The story is a bit different for objects
> > in memory ("prepared"): For this case, there is a table of
> > indirection, and the indirection entry is invalidated.  The rest is
> > done at the next checkpoint by the scavenger.
> 
> You are both correct here.  Prepared capabilities are most often found 
> in the address space definition tree of a process.  Objects which have 
> been cached in page tables must also invalidate the PTEs referencing 
> them in addition to the allocation count dance described above.  KeyKOS 
> and its successors (EROS, Coyotos, and CapROS)  use a hash table to 
> track the mapping from object -> list of PTEs which were produced by 
> that object.  It's called the "depends table", and is the list Marcus 
> Voelp mentioned.  The depends table is analogous to the mapping database 
> in L4.
> 
> The time needed to unmap an object's PTEs is bounded by the number of 
> entries in a hash bucket of the depends table (33 [start... end] ranges 
> in EROS).  On overflow during a page fault, an existing mapping must 
> reclaimed, though it can be faulted in again later.
> 
> Malicious processes could exploit this overflow to degrade performance, 
> and it formed part of an (overt) communication channel in the KeyKOS and 
> EROS specifications (corrected in CapROS and Coyotos).

Eric, thanks for correcting me and providing this information.
 
> > The details are a bit complicated.  The costs for keeping track of
> > everything are swallowed up and thus amortized by the object cache
> > magic.  I am not sure, but it might be possible for a malicious
> > process to try to screw with the checkpointing mechanism, for example
> > by forcing early checkpoints and thus degrading the performance of the
> > system, but if that is a possible threat scenario or just a paranoid
> > feeling is difficult for me to assess at this point, and may be
> > very difficult to analyse.  Eventually you will run out of allocation
> > counts, and then you can only recover object space by a garbage
> > collection on the object store.
> 
> Very few processes are given the capability to force a checkpoint.

I realize that, but my concern is not that they have a capability to
force a checkpoint, but that they can force a checkpoint simply by
exhausting the object table.  I am stretching out my neck here,
because I definitely don't have all the details.  Is it feasible that
there is a sequence of create and rescind operations one or multiple
cooperating programs could perform to spill the object table that
provides the indirection layer?  What happens in that case?  Also,
what happens if it happens at a time where a checkpoint is already in
progress.
 
> There were designs for both offline and incremental GC of allocation 
> counts, but none were implemented until a need came up - which never 
> happened.  With a 16 bit allocation court / 5 min. checkpoint interval 
> (original KeyKOS), it takes over 7 months  to wrap in the worst case. 
> With 24 bit / 1 min, it takes almost 32 years.

I agree that we can ignore the allocation count (for now :)

Thanks,
Marcus