backchains again Jonathan S. Shapiro ((no email))
Tue, 5 Dec 1995 00:22:32 -0500

I just tripped headlong into an unfortunate problem with having no key chains, and have a tentative solution. The solution may or may not be worse than the problem I was originally trying to solve, so I'ld like to describe it here for your amusement. I am not responsible for the consequences if you read this immediately after eating!

The problem: It begins to appear that invalidating the outstanding keys to an object must be an atomic operation. Any non-atomic solution admits of the possibility that a prepared key might be copied while the invalidation is in progress, and the copy might not get properly invalidated.

In the key chain design, the problem is most easily envisioned on an MP machine, where one processor might copy a key that was partially deprepared. Similar issues can arise in preemptively multithreaded kernels. I strongly suspect that an MP lock for chain walks would be a very high contention lock.

What is needed is a mechanism that allows us to promptly reclaim an aged object without having to wait for all of the outstanding keys to be deprepared. The solution I have in mind is to re-invent the object table.

Instead of pointing directly to the object, a prepared key points to an object table entry that in turn points to the object. Each object table entry contains two words:

  1. the low portion of the OID (cda), needed to deprepare the key.
  2. a pointer to the object header.

Each object header has exactly one current object table entry, and contains a pointer to that object table entry. A prepared key is valid iff the pointer field of the key's OT entry points to an object header.

When an object is paged out, the pointer to the object header in the corresponding object table entry is zeroed, indicating that keys should be deprepared. Any dependent mapping entries are also zapped, by taking advantage of the fact that the address of the object header is in the depend table.

When an object is rescinded, the object header pointer in the corresponding OT is set to the distinguished value 0x1, indicating that the OT entry denotes a rescinded object.

There are more OT entries than there are objects, (roughly 10-15% more, which should allow the scavenger to keep ahead of allocation).

Pros and Cons:

Performance Cost: Slight loss relative to KeyKOS.

References through a valid prepared key now require one additional load to indirect through/validate the OT. My (totally unsupported) guess is that this is not a measurable effect.

Key copies of prepared keys require a validity check against their OT entry.

Space: Net savings relative to KeyKOS

In-core keys are one word smaller than in the KeyKOS design. This saves (nNodes*16) words, or roughly (nObjects * 8) words, at the cost of approximately (nObjects * 2.2) words for the OT (20% extra OT entries). Object headers no longer require the doubly linked list header, but require a pointer to the OT entry which gives us back (nObjects * 1) words, so in aggregate we save

(nObjects * 6.8) words

Algorithmic Implications:

  1. Rescind is now an atomic operation, and does not trash the cache.
  2. OT entries must be reclaimed by scavenging.
  3. When copying a prepared key, must verify that it remains valid by checking the OT entry. This is avoidable through a multipass scavenger, but it's simpler this way.
  4. Objects can promptly be placed on the free list again!!!
  5. Preparing the first key to an object requires allocating an OT entry.
  6. The free list double linkage is maintained using spare OT table entries coupled with a flag bit in the object header. This is gross, but space efficient.
  7. Aging and scavenging should scale reasonably with increasing memory sizes again, which I was growing concerned about.