Moss also describes another classification based on the strategy used for distinguishing between resident and non-resident data in the incremental approach. The persistent heap and various data structures are viewed as a directed graph, where data objects represent nodes and pointers between objects represent edges that connect the nodes. The address translation mechanisms are then classified as either node-marking or edge-marking schemes.
Figure 1 shows the basic structure for node-marking and edge-marking schemes. As the name suggests, edge-marking schemes mark the graph edges--the pointers between objects--to indicate whether they have been translated into local format and reference resident objects. In contrast, node-marking schemes guarantee that all references in resident objects are always translated, and the graph nodes themselves are marked to indicate whether they are non-resident. In other words, edges are guaranteed to be valid local references but the actual referents may be non-resident. Note that the marking applies only to non-resident entities, that is, either to nodes that are non-resident or to (untranslated) edges that reference non-resident nodes.
Figure 2 shows a classic implementation of a node-marking scheme; non-resident nodes are ``marked'' as such by using proxy objects, that is, pseudo-objects that stand in for non-resident persistent objects and contain their corresponding persistent identifiers. When an object is loaded from the database, all references contained in that object must be swizzled as per the definition of node-marking--pointers to resident objects are swizzled normally while pointers to non-resident objects are swizzled into references to proxy objects. When the application follows a reference to a proxy object, the system loads the referent (F in the figure) from the database and updates the proxy object to reference the newly-resident object (Figure 2b). Alternatively, the proxy object may be bypassed by overwriting the (old) reference to it with a pointer to the newly-resident object; if there are no other references to it, the proxy object may (eventually) be reclaimed by the system. Note, however, that the compiled code must still check for the presence of proxy objects on every pointer dereference because of the possibility that any pointer may reference a proxy object. This adds continual checking overhead, even when all pointers directly reference data objects without intervening proxy objects.
Pointer swizzling at page fault time is essentially a node-marking scheme, because swizzled pointers always correspond to valid virtual memory addresses, while the referents are distinguished on the basis of residency. However, it differs in an important way from the normal approach--unlike the classic implementation, there are no explicit proxy objects for non-resident in pointer swizzling at page fault time. Instead, access-protected virtual address space pages act as proxy objects.4 As the application progresses and more data is loaded into memory, the pages that were previously protected are now unprotected because they contain valid data. The major advantage of this approach is that there is no need to reclaim proxy objects (because none exist); consequently, there are no further indirections that must be dealt with by compiled code, avoiding continual format checks that would otherwise be necessary.
