[cap-talk] Memory Accounting without partitions

[Jonathan S. Shapiro]

On Mon, 2007-06-18 at 17:57 -0400, Sandro Magi wrote:
> Jonathan S. Shapiro wrote:
> > Remember: The case we were concerned about was the case where the client
> > was hostile.
> 
> Maybe we're talking about two different things. You brought up "denial
> of reclaim" and I pointed out that in the PLT Scheme paper, the server
> can just release its handle to the storage and the storage will be
> booked to the hostile client. So that case isn't a problem.
> 
> I then suggested a caretaker if explicit revocation is desired. In that
> case, the server can still release its handle on the caretaker once it
> revokes access to the storage, and the client is then booked for the
> caretaker storage. Again, I don't see a reclaim problem here, since the
> server has complete control over when and how much storage is booked to it.

Yes and no.

If there is any requirement that EQ work, then the server must use
(identically) the same caretaker for all capabilities handed out. In
this case it becomes unclear who will own the caretaker after the server
lets it go.

Also, this does not address the issue of quotas. Assume that the client
is the sole holder of any capability to the caretaker, and therefore
comes to "own" the storage. The problem is: we have no reason to expect
that the client has sufficient storage quota to own the storage. One
possibility is that the client is now over quota.

If the client was hostile, this is perfectly acceptable. The problem is
that this pattern of ownership transfer can violate the quotas of
well-behaved clients.

Rule: Accounting must be done at the time of creation, and transfer of
ownership for purposes of accounting must be explicit. The explicit
action need not occur at the moment of actual transfer, but the check
that the transferee has sufficient resource to *accept* the transfer
must be explicit, and must occur before the moment of transfer. All
other outcomes either (a) violate semantics w.r.t. storage
accountability, or (b) result in unpredictable client-side errors for
both well-behaved and ill-behaved clients.


> >> Allocation will check allocated memory against the quota, and if the
> >> allocation exceeds it, a collection is run; if the quota is still
> >> exceeded after the allocation, the process generates a fault.
> > 
> > That would work, but note it isn't as helpful as you think. The problem
> > here is that you have some classes of allocation that can fail through
> > hostility, but you may have other classes of allocation that you need to
> > do in order to recover.
> 
> Hmm, let's be more concrete so I understand. Suppose we have an
> EROS-like storage model in a language with Erlang-like lightweight
> processes, each of which are individually schedulable and run in their
> own GC'd heap. Each process is constructed with a custom allocation
> closure (space bank) which contains a quota.
> 
> The allocation function increments its allocation count on each
> successful allocation, and when that count exceeds the quota, a
> collection is performed which returns the real allocation count. If the
> requested allocation is still too large, the allocator closure can call
> out to a parent bank requesting more memory [1], or fail, etc.
> 
> Is this design sufficient [2]?

Note that there is a covert channel in any GC approach, but let me not
spend time on that issue.

There are problems with this design.

Suppose that processes A and B share a reference to an object. Process A
later becomes the sole holder, so the object becomes "charged" to
process A. This places process A over its quota. Because process A is
over its quota it cannot be permitted to run. Therefore, process A is
unable to recover.

My earlier thought that multiple heaps would help is wrong.

> Now, let's replace the separate heaps by a single heap, and use PLT
> Scheme's accounting technique. I don't see how this change compromises
> the system in any way.

Oh. That's very easy. If the heaps are disjoint, no object sharing is
possible. Object transfer necessarily occurs by copy, and accounting is
performed at the moment of allocation. It is not possible for any
process to exceed quota, because the accounting occurs eagerly at the
time of allocation.

There *is* a way to make the shared-heap model work if we introduce
domain boundaries. Whenever a reference is transferred in such a way
that the object becomes shared, we check the receiver's quota **as if**
a copy had been performed. That is: every domain that can reach object X
is charged for the storage of object X. This is conservatively correct,
in the sense that heap quotas cannot be exhausted if this method is
used.

The problem with this approach is under-utilization. If an object of K
bytes is referenced by two domains, and the GC accounting is correct, it
follows immediately that either (a) K bytes of real storage are unusable
until the second reference is dropped, or (b) the quota system
oversubscribes real memory. Option (a) leads to  performance issues.
Option (b) leads to correctness issues. Option (b) is probably the
correct option to adopt, but in this case some form of capacity reserve
scheme is probably required in order to ensure that critical programs
can execute reliably.

> [2] Caveat: accounting for stack space is tricky, and I'm still working
> on it.

Accounting for stack space is trivial. From a logical perspective, a
stack frame is a heap-allocated object that is accounted like any other
heap-allocated object. The decision to unbox this object onto the stack
is an implementation matter.

As you point out, stack-allocated frames make a mess for continuations,
but if you choose that implementation there is still a well-defined
point in the code where the continuation is formed (and therefore where
accounting must occur).

In fact, it is not obvious from the literature that the stack
"optimization" actually makes things any faster.


shap