Re: EROS/Coyotos address spaces

[Jonathan S. Shapiro]

On Thu, 2005-10-20 at 22:38 +0200, Bas Wijnen wrote:
> On Wed, Oct 19, 2005 at 03:42:12PM -0400, Jonathan S. Shapiro wrote:
> <an explanation about address spaces in EROS and COYOTOS>
> 
> I understood previously that everything always pays for its own storage.  That
> sounds good.  However, I don't see how this can work.
> 
> There is a top level memory supply (called "prime space bank" if I remember
> correctly).  I guess this space bank will give out parts of its storage to
> anyone holding a capability allowing them.  How is this recorded?  What
> happens when the client is destroyed?  That can happen without notifying the
> prime space bank.  I'm sure the prime space bank has some way to know that it
> can give out the memory to an other process, but I don't see how.
> 
> Could you please explain this?

Well, I can try. :-)

The easy part is the last part: what happens when a client exits. The
answer is "nothing". Client exit does not cause any reclamation of
space. The act that reclaims space is the destruction of the
client-specific space bank. Until this occurs, the space sits
unreclaimed. Reclaiming a bank causes all of its space and its
descendent banks to be reclaimed.

For orderly process exit, the tricky part is to answer "how does a
process that is running out of reclaimed storage issue its final exit
status in response to the destroy() request. The orderly teardown
protocol is that the process does its own cleanup as needed, and its
last step is to execute an indirect return via its ProcessCreator
(something I have not yet explained). The last request is:

  ProcessCreator->destroyMeAndReturn(myBank, myExitCode, returnToHim)

the process creator is able to destroy the caller (the program that is
exiting), issues a destroy to the space bank, and then returns to the
process named by "returnToHim" with the provided exit code.

Charlie Landau and I have just agreed that the function of process
creators should be merged into the space bank, which will simplify this
protocol a bit and speed up process creation.

Okay. On to the hard part: how do banks work?

Let me describe this only for pages. The story is a little more
complicated for nodes, but the idea is the same. The actual
implementation is considerably optimized relative to the version that I
am about to describe. You can see the actual code at:

http://www.opencm.org/opencm/~/PUBLIC/EROS/DEV/eros/787/src/base/domain/spacebank

At the start of the world, the bank has a large pool of unallocated
pages. Conceptually, each of these pages has a book-keeping structure.
The main job of the book-keeping structure is to serve as a B-Tree node.

When a new sub-bank is created, a Bank data structure is allocated from
the space bank. This structure lives in the prime bank's heap. The space
bank heap in the current implementation is potentially exhaustible by
denial of resource. The bank structure contains two B-Tree root pointers
(for pages and nodes), a parent pointer, and optional limits for nodes
and pages. A wrapper is allocated **from the newly created bank**. This
will become the space bank capability for this new space bank.

As pages (or nodes) are allocated, their overhead structures are used to
link them on to the B-Tree for the allocating bank. This is how the bank
can later find them in order to destroy them.

Logically, the way to think of these overhead structures is that they
are "built in" to the page. You cannot allocate one without allocating
the other.

In actual practice, this design would break if misused. It was never
intended to be a long-term implementation, but it is "good enough" up to
several hundred terabytes of storage. The DoR (Denial of Resource)
vulnerability is the Bank data structure. The fix is to allocate this
from per-bank storage so that it is properly accounted. The reason that
the current implementation does not do this is that I did not want to
write the complex code necessary to support multiple allocation heaps.
The bank sits at the bottom of the world. It does not (and cannot) have
a memory fault handler, so doing tricky things with heap allocation is
complex in this application.

I don't know if this supplies a sufficient start at an answer, but
before I put more time in to it let me wait for your response. I have
skipped over a lot of detail about tricks for improving locality and
amortizing storage better than this naive explanation would suggest, but
is this enough to give you the idea?

shap