[cap-talk] Claim: correct generic wrapping is not possible in principle
Jonathan S. Shapiro
shap at eros-os.com
Mon Jan 1 11:41:32 CST 2007
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
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
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
There may be one or two others. Here are some things to notice about
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
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
Jonathan S. Shapiro, Ph.D.
The EROS Group, LLC
+1 443 927 1719 x5100
More information about the cap-talk