[elysium-developers] Capabilities

[Kasper V. L. <ve...@da...>]

This posting describes some thoughts on handling capabilities in
Elysium. Comments are welcome and expected.

Capabilities in Elysium
=======================

Each process will have a list of capabilities (c-list), which can be
mapped read-only to the process (and other processes). The first entry
in the list (entry 0) will hold the process capability for the any given
process. To create new capabilities a process uses the (as of now
un-implemented) sys_cap_set() system call:

int
sys_cap_set(int cap_no, cap_t cap, int cap_dom_no)
{
  if (cap_no == 0 || cap_no > CLIST_LENGTH) return -1;
  if (!cap_dominates(clist[cap_dom_no], cap)) return -1;
  clist[cap_dom_no] = cap;
  return 0;
}

The cap_dominates() function returns true iff the first argument is a
capability that has more access rights than the second argument. This
way a process cannot create capabilities that extends the access rights
of the process. 

The capabilities are ordered in a hierarchy. One way of implemented the
capability would be:

typedef struct cap_s
{
  uint32_t perm_bits;
  uint8_t name_length;
  uint8_t name[8];
} cap_t;

If we disregard the permission bits for a moment the cap_dominates()
could be implemented like:

bool
cap_dominates(cap_t c1, cap_t c2)
{
  if (c1.name_length > c2.name_length) return false;
  if (c1.name[0..c1.name_length-1] == c2.name[0..c1.name_length-1])
    return true;
  else
    return false;
}

This means that the capability with the name 1.3 will dominate the
capabilities 1.3.1, 1.3.4.5.6, and 1.3.6 - but not 1.4 or 2.

Any process can request read-only access to the c-list of a given
process. A typical server can rely on the fact that capabilities cannot
be changed directly by applications, and can therefore do all
authentication itself. To transfer capabilites between two processes we
can implement system calls - sys_get_cap() and sys_transfer_cap() -
which can used like this:

* process A wants to transfer a capability to process B
* process A calls sys_transfer_cap() with the correct cap index, and the
pid of process B.
* process A uses some IPC mechanism to tell process B that the
capability is ready for it.
* process B calls sys_get_cap() with the two correct cap indices, and
the pid of process A.
* the capability from the clist of process A is copied to the clist of
process B.
* process B uses some IPC mechanism to tell process A that it has
claimed the capability.

Using the Capabilities
======================
The kernel should protect physical pages, I/O port ranges, and CPU
quantums with capabilities. As an example consider mapping in a page
from memory protected by a capability. The system call you should use is
sys_pte_set(). A protected implementation could look like this:

int
sys_pte_set(uint32_t ptbl, uint32_t pte, uint32_t entry, int cap_index)
{
  if (page[pte].status != PAGE_FREE)
    {
      if (!cap_dominates(current_process->clist[cap_index],
page[pte].cap_guard)) return -1;
    }
  else
    {
      page[pte].cap_guard = clist[cap_index];
    }
  ptbl[entry] = pte;
}

Issues with Capabilities
========================
It's obvious that one physical resource might be perfectly legal to read
from (requiring almost no access rights), but only accessible for
writing by a few processes. If a memory page only has one capability
guard it's difficult to handle this situation correctly.

Comments? Good ideas?

/Kasper

P.S.: The design described here is pretty close to the design used in
Xok (the MIT exokernel). 

P.P.S.: The term 'capability' might be a bit misused in this discussion.
Normally a capability encode an object, but the capabilities in this
design merely represents access rights. Maybe we should change the name
to EAR (a TLA, which means encoding of access rights). :-)

-- 
-------------------------------------------------------------------
Kasper Verdich Lund, Computer Science Department, Aarhus University
Office: 34P.218              | Phone: (+45) 8942 5680
Email:  ve...@da...  | WWW: http://www.daimi.au.dk/~verdich