Efficient Support of Position Independence on Non-Volatile Memory

---

- Hide Paper Summary

---

This paper proposes an efficient pointer representation scheme to be used in NVM as a replacement for raw volatile pointers. Using raw volatile pointers for NVM memory regions is risky, because almost all currently proposed methods for accessing NVM is through Operating System’s mmap() system call. On calling mmap(), the OS finds a chunk of virtual pages in the calling process’s address space, and then assigns physial NVM pages to the allocated vierual addresses. On future calls to mmap(), either by the same process or a different process, however, there is no guarantee that the two mmap() calls will put the NVM region on the same virtual address. Imagine the case where raw pointers are used within a persistent data structure, and the persistent object is copied to another machine. When the user open this object via mmap(), the base address of the mapped NVM region might change, which makes pointers in the data structure invalid, because the address they point to may be no longer valid. In addition, cross-region reference (i.e. pointers from one mmap’ed region pointing to another mmap’ed region) will not work if the target region is relocated or does not exist. All these properties of NVM pointers motivate the development of position independent pointers.

Two prior designs are discussed in the paper: fat pointers and based pointer. Fat pointer is a struct consisting of two fields: Region ID and Region offset. The region ID field identifies which NVM region the pointer is based on. The base address is implicitly defined as a region property, and is maintained by the OS. The offset field specifies a byte within the region. For every memory access using the fat pointer, a virtual address must be generated and provided to the memory instruction. To achieve this, the NVM library maintains a hash table mapping region IDs to region properties. When a new region is mapped by the OS, the NVM library also adds an entry for the region into the hash table. On every memory access using fat pointers, the programmer or compiler must issue statements/instructions to invoke the NVM library, which fetches the base address of the region. The virtual address is generated by adding the base address with the offset, only after which the data item on the NVM region can be accessed. Although fat pointer is compatible with the current architecture, and is straightforward to understand, its hash table lookup overhead on every memory access lies on the critical path, and may take hundreds of extra instructions to complete. This severely reduces the efficiency of NVM-based system, because read/write operations on NVM are supposed to be fast. In addition, fat pointers are usually larger than a machine word (64 Bytes), which requires more storage and introduces cache pollution problem for pointer-based data structures. Based pointers, on the other hand, are compiler assisted fat pointers. Instead of storing the region ID and offset in one struct, with special compiler support, a pointer can be declared to use a second pointer as its “base pointer”. When a based pointer is dereference for memory accesses, the compiler automatically generates code to add the value of the “base pointer” onto the pointer being dereference. Similarly, when a normal volatile pointer is assigned to a based pointer, the base value is deducted from the volatile pointer to generate the value of the based pointer. This way, if the base pointer points to the starting address of a NVM region (which is obtained via the NVM library during run time), programmers can assign to and from based pointers stored in NVM without any manual effort of type conversion. The compiler takes care of pointer compatibilities with type inference, and convers between different pointers if necessary. Based pointers improve over fat pointer in a way that the compiler is aware of the special access semantics of NVM, and could process common usages of fat pointers seamlessly. The problem, however, arises when a based pointer is incremented, decremented, or passed as arguments. The paper claims that these operations are difficult to reason about and use correctly.

Beyond what we have discussed above, the paper also points out that data structures can also be stored without any relocation problem by serializing and deserializing them after and before use. This process is similar to the OS loader relocating all absolute pointers in a binary, or more commonly, a dynamic library, before executing the binary or library. This mechanism has been implemented by several commercial systems. The overhead of (de)serialization depends on the usage pattern of the non-volatile data structure. If a NVM region is only loaded once and used during a long period of time, the overhead of relocation can be largely amortized, in which case this might actually be a good choice. The paper does not give muct attention to this option, though.

This paper proposes two solutions: off-holder and Region ID in Value (RIV). One important observation made by the paper is that, in order for a NVM pointer to be both efficient and convenient to use, three requirements must be satisfied. First, the pointer must be of the same length as a native volatile pointer. This excludes extra storage overhead and cache pollution problem incurred by a fat pointer. Second, the pointer itself must contain all information needed for generating the target virtual address, i.e. the pointer must be self-contained. A non-self-contained pointer may require extra variables to be passed or stored when the pointer is passed around as function arguments or stored on the NVM. The last requirement is that programmers must be able to use the non-volatile pointer in the same way (except declaration) as a volatile pointer. To achieve this, the compiler must be able to infer type information of the non-volatile pointers, and whenever they are beging assigned or dereferenced, a special routine for type conversion is called automatically by the compiler.

Off-holders are pointer variables that store an offset value. Instead of using an second variable or environmental value as its “base variable”, as is the case for based pointers, an off-holder pointer uses its own address as the base, and stores the offset from its own address to the target address. Note that since off-holder pointers must have an address, they can only be used as l-values. In addition, off-holder pointers cannot be used as local variables, because the storage for the pointer itself will change when the copy is made. Although the paper does not mention this explicitly, off-holders can only be declared for pointer fields whose nodes are stored on the NVM. When reading from an off-holder pointer, the compiler recognizes its type as off-holders, and generates the address by taking the address of the pointer variable on the NVM (which must be a valid address on mapped NVM region), and then adding the value of the pointer variable to the address. The pointer must then be passed around and stored locally in the form of volatile pointers using absolute addresses as a regular pointer. When an off-holder pointer is written, the programmer must first ensure that the pointer is allocated on the NVM. The compiler will then generate the off-holder value by subtracting the pointer variable’s address from the absolute address, and store the value into the off-holder pointer. An off-holder pointer cannot be directly assigned using another off-holder pointer, because the base address of the two variables differ. A type cast to volatile pointer and then back to off-holder pointer is necessary, which can be performed by the compiler.

The second proposal is RIV, which is quite similar to a “shorter” version of fat pointer: Instead of storing the region ID and offset in two separate fields, an RIV pointer stores each of them as a 32 bit sub-word, totalling 64 bits which fits into a machine word. The difference between RIV and fat pointer is how region ID to base address mapping works. Recall that for fat pointers, the library must maintain a hash table mapping regions IDs to base addresses, and that the hash table must be queried before every memory access, which may take hundreds of extra cycles in the worst case (e.g. the query is not cached). RIV solves this problem by direct mapping: A mapping between region IDs and base addresses can be obtained by simple bit arithmetics and one memory access. This is achieved based on the observation that there are abundant number of virtual addresses on 64 bit architectures. It is therefore possible for us to dedicate a potentially large chunk of virtual addresses to store the mapping, while only populating these VA with physical pages when they are actually used. We describe the mapping schemes as follows. The virtual address space is divided into segments of large sizes (larger than the largest of supported NVM regions). NVM regions can only be mapped within a single segment, and the starting address of the region must align with the segment head it is in. In addition, to reduce the number of bits for representing a segment, NVM regions must be mapped to the upper part of the virtual address space, which indicates that the leading bits of a VA in any NVM region must be all 1s. We denote the number of 1s in such a VA as L1, and the number of bits to represent a segment is L2. The number of bits to represent an offset within segments is hence 64 - L1 - L2, denoted as L3. Two mapping tables are maintained at the bottom of this area, i.e. staring from VA = 0x11..100..0, in which the number of 1s is L1. The first mapping table maps segment base addresses to region IDs. There are 2^L2 entries in the table, because it is direct mapping and every segment has an entry in the table. The second mapping table maps region IDs back to segment addresses in a similar way. There are 2^L4 entries in the second table where L4 is the number of bits in the region ID which is supposed to be small because typically users will not open many NVM objects in one session. Overall speaking, since both L4 and L2 are significantly smaller than 64, and that only a small subset of all possible values are used in practice, as long as we only allocate pages for these two tables on-demand, the actual physical storage requirement can be as small as several KBs. The second table does not immediately begin after the first table, because it would involve an extra step in the runtime to compute the base of the second table. To obtain the base address of the second table, we first round the size of both tables to a power of two, and depending on which table is larger (we denote the larger size after rounding as SZ), assign the begin address of the second table as (0x11..100..0 + SZ). Note that, first, SZ is a power of two, and has only 1 bit set in its binary representation. The starting address of (0x11..100..0 + SZ) is therefore of the form 0x11..100..010..0, which can be computed easily by a bit flip. Second, since L1, L2 and L4 are all static values fixed during the session, the hardware can precompute the values of these two tables, and use them from a cached register during execution. It only takes one memory access to convert between region IDs and base addresses, which enables fast translation between a RIV pointer and a volatile pointer.