[cap-talk] Efficient Small Membranes in CapOS Systems

[Bill Frantz]

Note: Some of these ideas are built on a suggestion from Mark Miller.

First a few definitions:

  By "efficient", I mean not adding extra objects to the invocation
  path, and a (hopefully) minimal impact on that path.

  By "small", I mean only supporting a small number of membranes. 
  (Let's hope these ideas will generalize to larger numbers of
  membranes.)

  By "CapOS", I mean capability operating systems such as KeyKOS, EROS,
  Coyotos, and GuardOS with orthogonal persistence.

  The only membrane considered is a simple revocation membrane.  When
  the membrane is revoked, all capabilities that have passed through it
  become void.


We add a "membranes" field to the capability representation for each
capability in the system.  Each bit in the membranes field represents
membership in one membrane's revocation set.  If the membranes field is
32 bits long, the system will support a maximum of 32 membranes.

The invocation path is modified to:

  (1) When copying a parameter capability, make the copy's membranes
  field the logical OR of the field in the capability being invoked, and
  the field in the capability being copied.

  (2) Check all capabilities involved in the invocation, the target
  capability and the parameter capabilities, against a system-wide
  "revoked-membranes" mask with a logical AND.  If there are any
  non-zero bits in the result, replace the capability being checked by a
  void capability before further processing.

In addition, there are some special control capabilities:

  Membrane-Creator:
    Membrane-Controller = Membrane-Creator() - Creates new
      Membrane-Controllers or indicates the supported limit of membranes
      has been reached.

  Membrane-Controller:
    MC = Membrane-Controller.add(C) - Makes a copy of capability C which
      is a member of that membrane's revocation set.
    Membrane-Controller.revoke() - Revokes the Membrane-Controller and
      all capabilities in its revocation set.


Garbage Collection

Bits in the revoked-membranes mask can not be turned off until we are
sure that all copies of capabilities dependent on that membrane have
been replaced with void capabilities.  There are several possible ways
to limit the work necessary, although in the worst case, a full garbage
collection of capability space will be necessary.

The simplest way to limit the work is to have a mask of membranes which
have had capabilities written to the disk.  If a membrane is revoked,
and the mask shows that no keys in that membrane's revocation set have
been written to the disk, then the only copies are in memory and can be
garbage collected there.  Similar logic could have the migration process void
capabilities that had only been written to the swap area and not yet
migrated as they are written back to their home positions.

-- 
Text by me above is hereby placed in the public domain

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | I like the farmers' market   | Periwinkle 
(408)356-8506      | because I can get fruits and | 16345 Englewood Ave
www.pwpconsult.com | vegetables without stickers. | Los Gatos, CA 95032