Editing Pointer swizzling

{{Short description|Computer science term}}
{{No footnotes|date=May 2011}}
{{Use dmy dates|date=December 2021|cs1-dates=y}}
In [[computer science]], '''pointer swizzling''' is the conversion of references based on name or [[offset (computer science)|position]] into direct [[pointer (computer programming)|pointer]] references ([[memory address]]es). It is typically performed during [[deserialization]] or [[loader (computing)|loading]] of a relocatable object from a disk file, such as an [[executable file]] or pointer-based [[data structure]].

The reverse operation, replacing memory pointers with position-independent symbols or positions, is sometimes referred to as '''unswizzling''', and is performed during [[serialization]] (saving). Alternatively, both operations can also be referred to as swizzling.

==Example==
It is easy to create a [[linked list]] data structure using elements like this:

<syntaxhighlight lang=c>
struct node {
        int data;
        struct node *next;
};
</syntaxhighlight>

But saving the list to a file and then reloading it will (on most operating systems) break every link and render the list useless because the nodes will almost never be loaded into the same memory locations. One way to usefully save and retrieve the list is to assign a unique id number to each node and then '''unswizzle''' the pointers by turning them into a field indicating the id number of the next node:

<syntaxhighlight lang=c>
struct node_saved {
        int data;
        int id_number;
        int id_number_of_next_node;
};
</syntaxhighlight>

Records like these can be saved to a file in any order and reloaded without breaking the list. Other options include saving the file offset of the next node or a number indicating its position in the sequence of saved records, or simply saving the nodes in-order to the file.

After loading such a list, finding a node based on its number is cumbersome and inefficient (serial search). Traversing the list was very fast with the original "next" pointers. To convert the list back to its original form, or '''swizzle''' the pointers, requires finding the address of each node and turning the ''id_number_of_next_node'' 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 (see [[Foreign key]]).

==Methods of swizzling==
Swizzling in the general case can be complicated. The reference [[graph (abstract data type)|graph]] of pointers might contain an arbitrary number of [[cycle (graph theory)|cycle]]s; this complicates maintaining a mapping from the old unswizzled values to the new addresses. [[Associative array]]s 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. Various [[serialization]] [[library (computing)|libraries]] provide general swizzling systems. In many cases, however, swizzling can be performed with simplifying assumptions, such as a [[tree (data structure)|tree]] or [[list (abstract data type)|list]] structure of references.

The different types of swizzling are:
* Automatic swizzling <!--[EXPAND]-->
* On-demand swizzling <!--[EXPAND]-->

==Potential security weaknesses==
For security, unswizzling and swizzling must be implemented with great caution. In particular, an attacker's presentation of a specially crafted file may allow access to addresses outside of the expected and proper bounds. In systems with weak memory protection this can lead to exposure of confidential data or modification of code likely to be executed. If the system does not implement guards against execution of data the system may be severely compromised by the installation of various kinds of [[malware]].

Methods of protection include verifications prior to releasing the data to an application:
* That every offset lies within the bounds of the data read.
* That a table of indexes and the records pointed to is similarly constrained.
* That identifiers are unique and, if sensitive, encrypted.
* That all variable-length data is restrained to lengths not exceeding the actual allocation.
* That allocations are of reasonable size.
* That allocations made that are not loaded with data read are cleared, or loaded with some specific pattern.
{{Expand list|date=August 2011}}

==See also==
* [[Relocation (computing)|Relocation]], an eager form of pointer modification

==References==
{{Reflist|refs=}}

==Further reading==
* {{cite news |title=Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware |author-first=Paul R. |author-last=Wilson |newspaper=ACM SIGARCH Computer Architecture News |volume=19 |issue=4 |pages=6–13 |date=1991-07-01 |orig-date=June 1991 |doi=10.1145/122576.122577 |url=}}
* {{cite journal |title=Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis |author-first1=Alfons |author-last1=Kemper |author-first2=Donald |author-last2=Kossmann |journal=The International Journal on Very Large Data Bases |volume=4 |issue=3 |pages=519–567 |date=July 1995 |doi=10.1007/BF01231646 |s2cid=4556203 |url=http://www.vldb.org/journal/VLDBJ4/P519.pdf |access-date=2021-12-08 |url-status=live |archive-url=https://web.archive.org/web/20080725153221/http://www.vldb.org/journal/VLDBJ4/P519.pdf |archive-date=2008-07-25}} (49 pages)
* {{cite book |author-first=Derek |author-last=Crawford |title=Derek's ABC of C |volume=2 |pages=340–343 |date=June 1992}}

[[Category:Memory management]]
[[Category:Pointers (computer programming)]]