Reclaiming Storage from Activities/Space Banks

[Neal H. Walfield]

In this note, I explore some of the issues surrounding the reclamation
of storage associated with an activity when it is destroyed.  In
particular, I am concerned about reclaiming disk storage quickly.


One of the main ideas behind the space bank design is that when a
space bank is destroyed, the resources allocated to the bank are
immediately freed.  I have adopted this idea in my design of
activities.  In this note, I am exploring how to reclaim the disk
space allocated to an activity when that activity is destroyed.  My
assumption is that creating and destroying activities happens
relatively often.  A requirement, as always, is that all resources be
accounted upfront.

In terms of accounting memory, I think that the only objects that need
to be accounted are pages and cap pages¹; all other objects can be
composed out of these.  There are a number of relevant considerations:

 - how to indicate to which activity a page belongs
 - how to destroy a page
 - what to do when destorying an activity, and
 - how to find unallocated pages (or, how to allocate a page)

(Is this list exhaustive?)

Assuming that the grain of allocation is a single page, it appears to
me that the best solution may be to keep one bit per page to indicate
whether a page is free and an additional two pointers to link the page
to the owner activity.  (Keeping the pages on a singly linked list is
problematic as when a page is destroyed, it must be unlinked.)  When
an activity is destroyed, we simply walk the list and destroy the
pages (e.g., by bumping the page's alloc count).  This has, however,
the disadvantage that when a page is freed, the pointers associated
with the previous and the next pages must be updated, however, these
pages may have nothing (in terms of locality of reference) to do with
each other.

An alternative design is to associate a word (or capability)
designating the owner activity with each page.  Destroying a single
page is easy and does not cause gratuitous references, however, when
an activity is destroyed, we might have to scavenge the disk to find
all pages owned by the activity.  Assuming a simple table holding the
owners, 4 bytes to identify the owner and 4kb pages, the tables
require 1 MB per GB of disk storage.  Based on personal experience,
today's computers have about 250GB storage per GB of main memory.
When we destroy an activity, we would then have to scour 250MB of
tables per GB of main memory.  Although the tables fit in memory, they
represent, I think, a huge overhead in particular given the assumption
that activities are created and destroyed frequently.  There are a
number of possible optimizations for this strategy.  We could use a
single bit to track whether an activity has any pages on backing store
(or whether the page has been migrated to long term storage from the
checkpoint area).  If not, then there is no need to scan backing store
for pages owned by the activity.  Another optimization is to only
scavenge periodically.  That is, to accumulate destroyed activities
and to purge pages belonging to them all at once.  Alternatively, we
just free pages lazily.  We simply destroy activites and ensure that
an activity designator is not reused until to page on disk references
designates it.  Then, we periodically scavenge the disk looking for
allocated pages owned by invalid activities.

EROS, according to §5 of [1], keeps track of extents (64 physically
contiguous pages) in an RB-tree.  When a bank is destroyed, the pages
are freed by walking the tree.  Why the extents are kept in an RB-tree
in not justified, as far as I can see.  In particular, when does this
list need to be searched?  What is also not clear is how pages in an
extent can be allocated to multiple banks.  Presumably there is
sufficient reserved space to attach an extent to 64 RB-trees (the
worst-case when each page is allocated to a different bank).  As the
pages are stored in an RB-tree, it appears that deallocating a page
from or allocating a page to an activity can be very expensive as many
unrelated on-disk pages may have to be brought into memory (think
rotations).  In my proposed approach, adding pages to a linked list
should be relatively cheap as they can just be added to the head of
the list and the activity is almost certainly in memory and the last
allocated page is also often in memory and hot.

Comments and corrects are as usual welcome.

Thanks,
Neal

¹ For the rest of the text, I use the term page generically to refer
to either a data page or a capability page.

[1] Design Evolution of the EROS Single-Level Store by Jonathan
    Shapiro and Jonathan Adams, 2002.