32-bit alloc counts as assertions Jonathan Shapiro (shap@viper.cis.upenn.edu)
Thu, 9 Feb 95 16:46:03 -0500

Per Charlie Landau's request, I'm going to try to restate the workings of the new approach to allocation counts as a collection of assertions and constraints.

What follows is the simple version. A hairy optimization that works, but may not be advisable, is at the bottom.

Background:

In this model, prepared keys carry the in-core allocation count, unprepared keys carry the on-disk allocation count. Prepared objects
(nodes, pages) carry both.

In general, the same constraints apply to call counts, with the additional interaction that if an allocation count is incremented on a domain the call count must also be incremented.

Key deprepare is done by a background scavenger. When an object needs to go out, it sets a bit saying so. The scavenger deprepares all of the keys that point to the object, and then schedules the object to go out. The scavenger runs semi-continuously, depreparing invalid keys to DK(0).

I. General

  1. Every object has an in-core and on-disk allocation count. For purposes of the following discussion, both are assumed to be 32 bit unsigned values,
  2. "Incrementing" an allocation count is performed using modulo 2^32 unsigned integer arithmetic. That is, incrementing is assumed to wrap in the obvious way.

II. Key Validity

II.A. Prepared Key

  1. If a key is prepared, the Node/Page to which it points is also prepared [enforced by the object deprepare logic, and I'm ignoring the convolutions that arise due to checkpoint for the moment]
  2. A prepared key's allocation count is interpreted as an in-core allocation count.
  3. A prepared key is valid IFF it's allocation count matches the in-core allocation count of the corresponding prepared object.
  4. When unprepared, an invalid key is deprepard to a NULL key [DK(0) for the KeyKOS folks].

II. B. Unprepared Key

  1. If a key is unprepared, the Node/Page to which it points can be either prepared or unprepared.
  2. An unprepared key's allocation count is interpreted as an on-disk allocation count.
  3. An unprepared key is valid IFF the following conditions hold:
  4. The on-disk allocation count of the object matches the on-disk allocation count of the key.
  5. The on-disk allocation count of the object matches the in-core allocation count of the object.
  6. When prepared, an invalid key is prepared as a NULL key. [This is an optimization, not a correctness requirement.]

III. Objects

III A. Unprepared Objects

  1. The in-core allocation count of an unprepared object is DEFINED to be equal to it's on-disk allocation count.
  2. An unprepared object can be rescinded simply be incrementing it's on-disk allocation count. Since an unprepared object has no explicit in-core allocation count, this implicitly increments the in-core alloction count by virtue of rule II-1.
  3. Preparing an object does not alter it's in-core or on-disk allocation count.

III B. Prepared Objects

  1. A prepared object can be trivially rescinded IFF the following constraint is true:

increment(in-core-alloc-count) != on-disk-alloc-count

2) A prepared object has been rescinded IFF the following

formula is true:

in-core-alloc-count != on-disk-alloc-count

3) When a prepared object is deprepared, it's on-disk allocation

count is incremented IFF it has been rescinded. 

      Note that this increment does not require further condition
      checking, as it does not violate any of the necessary
      constraints for validity checking.

IV. Scavenger Completion

There are various points at which you need to know if the scavenger is done with your object. The two important cases are when you need to know that all keys are deprepared and in support of the hairy optimization below. Here's how you handle it.

  1. At any given time, the scavenger is either making an odd pass or an even pass.
  2. Every object (Node, Page) has two bits in it's object header. One says that it is waiting for the scavenger to run. The other says which pass (odd or even) the scavenger was currently in when the waiting started.
  3. At the start of each pass, the scavenger runs through all in-core objects. If the scavenge-wait bit is set and the pass bit parity (odd/even) matches the parity of the pass being started, the scavenge-wait bit is cleared.

Actually, that would need to be expanded, since the scavenger performs multiple functions and needs to know whether it should be depreparing keys or merely validating them. It also needs to know what operation
(e.g. I/O) should be performed once the scavenge is complete.

In the above (simple) model, you simply deprepare an object if it's in-core count manages to hit the wall. In an optimized version, a full deprepare is not necessary.

HAIRY OPTIMIZATION:

The above constraints can be further hacked as follows to eliminate a bunch of difficulties.

when doing trivial rescind, if the in-core count ends up matching the on-disk count, just bump it twice.

ensure that the scavenger runs fast enough that invalid prepared keys are never more than 2^31 - 1 calls old. This requires that the scavenger make progress at a calculable rate, which doesn't seem unreasonable. In this even, the problem of wrapping in-core allocation counts in a way that happens to revalidate a prepared key does not arise, because the prepared key is guaranteed to be turned into a DK(0) before the in-core count can wrap that far.

Jonathan