Crate ointers

source ·
Expand description

What do you call a pointer we stole the high bits off? An ointer.

Ointers is a library for representing pointers where some bits have been stolen so that they may be used by the programmer for something else. In effect, it’s a small amount of free storage

Fully supports no_std, dependency-free.

Ointers supports a handful of bit sources. It’s up to you to determine when it is safe to use them.

Alignment bits (const parameter A)

If we know that a pointer’s address will always be aligned to A bytes where A > 1, we can steal log2(A-1) bits. For an 8-byte aligned value, this provides a modest 3 bits.

If you have values aligned to some larger width, you could get even more. It’s common in parallel programming to pad data to a cache line by increasing its alignment requirements in order eliminate false sharing. Because a cache line on amd64 or aarch64 is effectively 128 bytes thanks to prefetching, you can reclaim a respectable 7 extra bits.

If your data is aligned wider still, the sky is the limit, but you could get an incredible 24 bits if you have 16MB-aligned data! Remember that the only alignment rust knows about is what is declared for the type, so you must create a newtype wrapper to take full advantage of large alignment sizes.

BitsMin alignment
12b
24b
38b
416b
532b
664b
7128b
8256b
9512b
101k
112k
124k
138k
1416k
1532k
1664k
17128k
18256k
19512k
201m
212m
224m
238m
2416m

Stealing bits from alignment is relatively innocuous, but we can only get the compiler to check it for you in dev mode as things stand in rust today.

Sign bit (parameter S)

The most commonly used operating systems arrange memory so that the high half of virtual memory space is reserved for the kernel and the low half is given to userspace.

Looked at as a signed integer, this makes the kernel half of address space negative and the userspace half positive.

Most programs do not deal with kernel addresses, thus giving us an extra bit to play with.

We can also get this extra bit in kernel mode if we know we will not be dealing with userspace addresses. We do this by taking a pointer to a value on the stack and stealing its sign bit.

If you know you will be dealing with userspace addresses in kernel space or kernel space addresses in userspace, or you are using or implementing a kernel which does not follow this convention, you must set S to false.

The S bit is currently only tested with userspace pointers in userspace. While we think it should work more generally, we currently haven’t got a test rig for other scenarios so we can’t promise it does.

Unused virtual address space (V)

In 64-bit mode, address space is plentiful: nobody has 64 bits’ worth of RAM and even if they did, their processor is unable to address it all. V is required to be 0 unless compiling for a 64bit target.

The number of bits that may be safely stolen by this method depends upon the microarchitecture in question and the page table depth.

For x86-64 and aarch64, the following sizes apply:

BitsPT depthSupport
253aarch64 only, uncommon, opt-in
164most common default
75some intel only, uncommon, opt-in

If you are made of money and need more than 128TB virtual address space, you should limit yourself to 7 bits for V. Likewise if you know you’ll be on 3-deep page tables, you can steal a whopping 25 bits. But you’re probably limited to 16 bits in general.

Structs

  • A non-null pointer that we stole the high bits off.
  • A pointer we stole the high bits off
  • A Box that we stole the high bits off.

Functions

  • Produces a mask where the stolen bits (at the top) are set
  • Produces a mask where the stolen bits (at the top) are set
  • pack
    Packs a pointer into the bottom sizeof(usize) - (a + s + v) bits of a usize.
  • Turns the sizeof(usize) - (a + s + v) bits of a usize (as returned from pack) back into a pointer.