Pointer swizzling

In computer science, pointer swizzling is the conversion of references based on name or position to direct pointer references. It is typically performed during the deserialization (loading) of a relocatable object from disk, such as an executable file or pointer-based data structure. The reverse operation, replacing pointers with position-independent symbols or positions, is sometimes referred to as unswizzling, and is performed during serialization (saving).

Example

For example, suppose we have the following linked list data structure:

 record node {
     int data
     node next
 }

We can easily create a linked list data structure in memory using such an object, but when we attempt to save it to disk we run into trouble. Directly saving the pointer values won't work on most architectures, because the next time we load it the memory positions the nodes now use may be in use by other data. One way of dealing this is to assign a number to each node and then unswizzle the pointers by turning them into a field indicating the number of the next node:

 record node_saved {
     int number
     int data
     int number_of_next
 }

We can save these records to disk in any order, and no information will be lost. Alternatives include saving the file offset of the next node or a number indicating its position in the sequence of saved records.

When we go to load these nodes, however, we quickly discover that attempting to find a node based on its number is cumbersome and inefficient. We'd like our original data structure back so we can simply follow next pointers to traverse the list. To do this, we perform pointer swizzling, finding the address of each node and turning the number_of_next fields back into direct pointers to the right node.

Methods of unswizzling

There are a potentially unlimited number of forms into which a pointer can be unswizzled, but some of the most popular include:

• The offset of the pointed-to object in the file
• The index of the pointed-to object in some sequence of records
• A unique identifier possessed by the pointed-to object, such as a person's social security number. In databases, all pointers are unswizzled in this manner, and are referred to as foreign keys.

Methods of swizzling

Swizzling can be a complicated problem, because we need to traverse, in general, a general reference graph of pointers which might contain cycles, while maintaining a mapping from the old unswizzled values to the new addresses. Associative arrays are useful for maintaining the mapping, while algorithms such as breadth-first search help to traverse the graph, although both of these require extra storage.

External links

• swizzle definition at FOLDOC
• Paul R. Wilson. Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware. ACM SIGARCH Computer Architecture News, Volume 19, Issue 4, pp. 6–13. June 1991.
• Alfons Kemper and Donald Kossman. Adaptable pointer swizzling strategies in object bases: design, realization, and quantitative analysis. The International Journal on Very Large Data Bases, Volume 4, Issue 3, pp.519–567. July 1995.