[cap-talk] CapROS checkpoint design available

[Jonathan S. Shapiro]

On Wed, 2008-04-09 at 18:43 -0700, Bill Frantz wrote:
> Charles Landau and I have produced a design for the checkpoint
> system on CapROS.au and I have produced a design for the checkpoint
> system on CapROS.ailed.


Bill, Charlie:

>From the time I started work on EROS in 1991 to 2006 when the CapROS
work forked the EROS tree, I was scrupulously careful about giving
credit to KeyKOS wherever it was due, and never claiming credit for work
that was not truly my own. Where there was doubt in my mind, I erred by
giving credit to KeyKOS.

The overwhelming majority of what is described in this checkpoint design
document is simply the EROS design as CapROS inherited it. The changes
are fairly insignificant. I am disappointed that the document
appropriates my work without giving proper credit. This design predates
CapROS by many years. It wasn't designed for CapROS or by the CapROS
team.

You cite the KeyKOS paper, but you do not cite the EROS paper on
checkpoint, which is significantly more detailed.


Some technical points:

Perhaps I am reading in because of some email exchanges, but the
document describes the in-place page rewrite decision in EROS as a big
deal. It isn't. This was purely a space optimization, and not in any way
fundamental to the design. You will find on measurement that the EROS
decision in this regard remains correct for disk checkpoint. But my main
point here is that this just isn't a big deal.

You should specify what is meant by the term "full size lid".


A couple of points on how EROS handled the log directory and lid ranges:

EROS's use of a two-level hierarchy was a pragmatic implementation
choice that was appropriate to the machines of the day. A different
design would certainly be appropriate now.

EROS did not linearize the directory because the long-term design
strategy envisioned log designs in which linear checkpoint image storage
in the log might not be possible. This is notably true if the Snocrash
design is adopted. The problem is that checkpoints in the Snocrash
design may be retired out of order, and it may not be possible to
guarantee linear storage of the log. I definitely agree that this is not
a factor for CapROS. I simply wanted to explain the motivation so that
the decision might make some sense.

I did consider non-linear numbering of log ranges, but all of the
practical implementations "resolve" the non-linear numbering by
re-introducing linearity. It really isn't a big deal to add sections to
the log in linearly numbered fashion. Removing sections is harder, but
not all that hard. You simply shrink the log down to the linear range
*beneath* the log range to be removed, remove the chunk you wish and all
chunks above that, and then re-add the surviving chunks in appropriate
linear positions. Dropping the first lid range is a special case, but
not a difficult one.

If holes are permitted in the lid range, note that removing a linear lid
range from the log can run you into situations where you are no longer
able to linearize the directory within any sequential lid range that is
actually available...


shap