[coyotos-dev] Fixing the kernel heap size

[Jonathan S. Shapiro]

On Wed, 2007-12-19 at 17:40 -0800, Charles Landau wrote:
> At 7:12 PM -0500 12/19/07, Jonathan S. Shapiro wrote:
> >The Coldfire port has brought an issue into sharp relief:
> 
> I'm keenly interested, since CapROS has the same issue, though 
> perhaps not as severely.

I think it will prove equally necessary. I agree that the per-frame
structure can be reduced, but I think you will end up needing a
per-frame structure of some sort. Unless the size of the per-frame
structure goes to zero you will still need late heap allocation of some
sort, so I think the best approach is to find a solution for that.

> >For device memory, the requirement on the heap is that each page of
> >device memory requires an associated "struct Page" overhead structure in
> >the kernel heap.
> 
> It's worth questioning this assumption.
> 
> Consider that device memory does not require many of the things in 
> the struct Page: it's never on the list of free RAM, it never needs 
> to be pinned, it never gets aged or paged, and its OID is a simple 
> function of the physical address. (I'm using CapROS concepts; 
> hopefully most apply to Coyotos.)

All of this is true, only some of this is helpful. I've been going
through the fields, and there are reductions that could be had, but not
enough to let the structure go away entirely. The only thing we could
entirely get rid of is the ageLink pointers, but that would break a type
pun that *everything* relies on, so it isn't worth it. Various other
fields can (and will) be reduced in size -- the current structure isn't
layout or storage optimized.

Two fields cannot be eliminated that you might think could be: oid and
PA. Because of fragmentation concerns, it is not generally possible to
establish an index-based 1:1 relationship between the vector of
StructPage structures and the corresponding vector of frames. The issue
is that hot-plug may cause device memory to come and go, and the
StructPage structures therefore cannot be relied on to remain
contiguous. In consequence, the StructPage structure must (at least in
Coyotos) contain an OID and a field giving the PA of the corresponding
frame. 

In our design, device frames are rescindable, so we nominally need an
allocation count. However, the corresponding capabilities are not
permitted to go to disk, so the allocation count will never (in
practice) be examined.

Bottom line is that I can see how to reduce the current structure to 48
bytes with some layout changes, but not much below that. It's clearly
not going to go to zero bytes, so its not enough to eliminate the need
for allocation of StructPage structures.

> In CapROS a page can sometimes give rise to a page table. You could 
> restrict the use of device memory so this doesn't happen.

This could be done, but I think that the maintainability hazards
entailed do not justify this.

> I don't see much left in the struct PageHeader that is needed.

Lock word, oid, pa, allocCount, type field, otIndex.

> >At present, these "struct Page" objects are dynamically
> >allocated by growing (but never shrinking) the kernel heap at run time.
> 
> It would be elegant to allocate the struct Page objects from the 
> device memory itself, but I'm sure there are good reasons why you 
> can't do this.

For hot plug RAM cards that is both possible and desirable. This does
not entirely reduce the problem, because *virtual* addresses still need
to be allocated.

For other devices: From which part of the video frame buffer can these
structures be allocated safely? Also, how do we deal with the fact that
the memory in question is on the wrong side of two bridge chips with
comparatively high latency?

> >There seem to be three classes of solution:
> >
> >   1. Have a tunable number of "reserved" device page frames. Allocate
> >      the "struct page" structures for these early. If you run out,
> >      the attempt to map the device memory fails and it is necessary to
> >      re-tune and re-boot.

Note that the re-tuning doesn't need to be done by the user. It can be
done automatically by the device discovery logic. The re-tune phase will
only trigger when the device configuration is substantially changed.

> >
> >   2. Separate the kernel heap into two parts. One is fixed at boot time
> >      by pre-sizing. The second is dynamically growable but falls outside
> >      of the direct-mapped kernel heap. This is, in essence, a hybrid
> >      strategy.
> 
> I prefer this option because it doesn't require tuning.

Unfortunately, it does not solve the space bank problem. The space bank
needs to know how many real memory frames are available for allocation.
Any kernel behavior that has the effect of claiming these frames out
from under the space bank violates the contract. The space bank could
obviously check back later, but a stable protocol needs to give the
space bank an initially conservative number followed by a more relaxed
constraint.

Further, with hot plug devices (PCI is a hot-plug bus) there exists in
principle no time when it becomes possible to declare that an upper
bound on device memory is known.

> >   3. Conservatively reserve excess kernel heap space so that you
> >      always have enough, then provide a mechanism to "release" this
> >      space after the device config has been determined.
> 
> This seems incompatible with hot-plugged devices.

Depends on how conservative you are. As long as the "released" memory is
not pinnable it can be re-assigned to the heap. The problem with that
will be dealing with the monotonicity requirements of the space bank.

> >      This could be combined with [1].
> 
> I suppose that's how you handle hot-plugged devices.

At the moment, I'm not sure *how* to deal with hot-plugged devices.
Fortunately most of those devices in today's world are USB and/or
firewire, and these don't have a footprint on the memory bus. CardBus
and PCI are the cases to watch out for here.

shap