[cap-talk] Claim: correct generic wrapping is not possible in principle

[Jonathan S. Shapiro]

On Mon, 2007-01-01 at 08:18 -0800, David Wagner wrote:
> Obviously, limiting the use of dynamic allocation to the bare minimum
> necessary makes it far easier to reason about dynamic allocation.  But I
> don't see why allocating out of a statically allocated array as opposed
> to out of the heap would change anything.

Let me expand a little more on what Bill and I have already said about
KeyKOS/EROS/Coyotos (and, I assume, CapROS). I will speak here about
EROS. In my next note I will talk about the changes in later versions of
EROS and in current Coyotos.

For reasons of implementation, it is usual for some of the object
vectors to get "split" because there are holes in the physical memory
layout. I will ignore this detail. It's a nuisance, but it has no
conceptual impact.

In EROS, the following vectors (typed object heaps) exist:

  Node Space     - A vector of Node structures

  Page Space     - A vector of pages. This vector is page aligned due to
                   hardware MMU requirements

  Page Headers   - A vector of ObjectHeader structures, having the same
                   size as the Page Space vector. Logically, 
                   PageHeader[i] is the book-keeping structure for
                   PageSpace[i]. In the case of Node Space, the
                   ObjectHeader is stored as part of the node.

  Depend Table   - A table of entries that record relationships between
                   capability addresses and mapping table addresses,
                   indexed by capability address. If overwriting a
                   capability slot requires invalidating a mapping
                   entry, there is a record here describing what to do.

                   This table is treated as a cache. When entries are
                   invalidated, the target page table entries are
                   invalidated as well.

                   Every (non-kernel) page table entry is pointed to by
                   at least one depend entry.

                   [I am ignoring a number of optimizations that reduce
                    the size of this table where the information is
                    otherwise recomputable.]

  Process Table  - A table of entries that cache process state. This
                   table is a cache. The definitive process state lives
                   in nodes. Process table entries can be flushed back
                   to nodes at will.

  Activity Table - A fixed-length table of stall queue entries, each
                   consisting of pointers for a doubly linked list,
                   and a process capability. If a process is enqueued
                   on a kernel stall queue, this is the least part
                   that must remain in memory.

  IOReq Table    - Fixed Size table of I/O request structures.

  Range Table    - Fixed-size table mapping object id ranges to
                   corresponding disk ranges.

  PhysRange Table- Fixed-size table describing available physical memory
                   ranges.
                   

There may be one or two others. Here are some things to notice about
this list:

  1. The only fixed size table that is architecturally observable is
     the activity table. This table sets a bound on the number of
     simultaneously running processes. There is an (unimplemented)
     mechanism for viewing this as a cache of a list maintained by a
     user-level agent.

  2. The remaining fixed-size tables either drain under kernel control
     (IOReq), or are things for which a rational fixed size can be
     selected (Range Table, PhysRange Table)

So you see, the model is even more restrictive than fixed-size vectors.
These are all *caches*. Allocations from these structures are not
durable.

shap  
 
-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100