Laplace: Basic Merge Format

It is sometimes desirable to ignore scheduling issues and simply treat a reference sequence as an immutable string of requests to be managed. Uniprogrammed simulations are often performed in this manner, where a simulator expects only a sequence of memory references, and then handles thoses references for a simulated memory using some policy. There is no attempt to simulate scheduling or to acknowledge that the sequence of references may change in a real system as a result of page faults.

While it is an oversimplification to handle a multiprogrammed reference sequence as immutable, that simplification makes it possible to use a multiprogrammed trace in a number of existing replacement policy simulators. Because the original reference sequence is derived from a multiprogrammed execution, we must be concerned with the use of shared pages and of the filesystem cache. As the merge is performed, Laplace-merge reconstructs the memory mappings of the system so that the resultant basic merged trace identifies those shared and filesystem cache pages.

Canonical pages and the trace format

We would like to have a single kind of page identifier such that each anonymous, shared, or file page can be uniquely referenced. We cannot use virtual page numbers, as those are dependent on the virtual mappings of the moment -- For example, a particular file page may be mapped into one virtual location at one moment, and into another virtual location at the next.

We therefore use the canonical address space, where each unique page is given a canonical page number by which it can be referenced irrespective of its virtual and physical mappings at each moment. More details on the canonical address space can be taken from our paper on Laplace that can be obtained by request.

In short, during the basic merge, each virtual page number is replaced with the appropriate canonical page number. The resultant trace is stored as text, where one reference is stored in each record, and each record takes the following form:

    R 5647abcd3829ef10
    I 1038293ff
    W 4547738abab392
      

1. Type tag: An 8-bit character that indicates what kind of reference is performed:
   • An R indicates that a read (load) operation was performed.
   • A W indicates that a write (store) operation was performed.
   • An I indicates that an instruction fetch was performed.
2. Canonical page number: A 64-bit, hexidecimal number of the referenced page within the canonical space. Note that each anonymous page, each file page, each IPC shared memory segment page, and each filesystem cache page is assigned a canonical page number. These numbers are assigned linearly as they are encountered during the merging process, and so the spatial locality of reference within the various virtual address spaces of the original processes is not preserved here. Also note that with a 64-bit space for page numbers, the canonical address space is effectively 2⁷⁶ bytes if 4 KByte pages are used. If that space is (somehow) exhausted, the merging utility aborts.