We treat our disk-store as a sequence of fixed-size, sequentially numbered pages. In memory, we maintain a ``working set'' of copies of some of the disk-pages. The size of the working set and the size of the individual pages (a multiple of the underlying OS page size) are determined during runtime initialization. To refer to data in a page, we use PgRef, which returns a pointer to an in-memory copy of the page. The memory at that address will not be replaced by another page from disk until PgUnref is called, and even then, it will be kept as long as possible. PgRefs accumulate, so a page remains ``locked'' in memory as long as the number of PgRefs exceeds the number of PgUnrefs. Much of the data access in our program is read-only, so we wish to avoid unnecessary copies back to disk. PgUnref takes an argument which states whether the caller has dirtied the page by modifying any data. Dirty bits from multiple PgUnref calls are OR-ed together. Before a dirty page is replaced in memory, its contents must be written back to disk.
We use an ad hoc, but effective least-recently-used policy to select pages for replacement. Every time PgRef is called, it increments a global counter which acts as a timestamp, and places the value in a structure associated with the page being referenced. When we need to replace a page, we examine all unreferenced paged, and choose the one with the oldest timestamp. To reduce the number of writes, we preferentially replace clean pages by dividing their age in half before comparison.
This defines an interface to page-sized units of storage. But our program works with bodies, sib_groups, moments and so forth (see Section 4), none of which are the same size, and all of which are far smaller than an entire page. Thus, we introduce a second layer, of ``out-of-core pointers'', oocptrs, which are implemented as a structure containing a page number and an offset. We use OOCRef to return a true pointer that corresponds to an oocptr, and OOCUnRef to signal that we are done with an oocptr. Oocptrs appear in several places in the library where an in-core implementation might use normal pointers. Explicit page numbers and PgRefs, on the other hand, are generally hidden behind the oocptr abstraction.