Zig and pointer provenance

Help
1

Yesterday on discord, fri3d(&stuff); kindly introduced me to the concepts of pointer provenance (the origin associated with a pointer) and leaking provenance (losing the origin, e.g. due to ptr → int → ptr conversions).

I needed to implement slice intersection. My original code (actually, already slightly improved) was the following:

pub fn intersection1(T: type, a: []const T, b: []const T) ?[]const T {
    const start = @max(@intFromPtr(a.ptr), @intFromPtr(b.ptr));
    const end = @min(@intFromPtr(a.ptr + a.len), @intFromPtr(b.ptr + b.len));
    if (end <= start) return null;

    const ptr: [*]T = @ptrFromInt(start);
    return ptr[0 .. end - start];
}

fri3d(&stuff); pointed out that this implementation “leaks” (loses) pointer provenance. He suggested an alternative approach using [*c] trick, which allows pointer comparison (which isn’t allowed for normal single/many-item pointers):

fn intersection2(T: type, a: []const T, b: []const T) ?[]const T {
    const start = if (@as([*c]const T, a.ptr) > @as([*c]const T, b.ptr)) a.ptr else b.ptr;
    const a_end = a.ptr + a.len;
    const b_end = b.ptr + b.len;
    const end = if (@as([*c]const T, a_end) < @as([*c]const T, b_end)) a_end else b_end;
    return if (@as([*c]const T, start) < @as([*c]const T, end))
        start[0 .. end - start]
    else
        null;
}

I then suggested: Why not just use @intFromPtr if we’re essentially just comparing two numbers? So, I rewrote his version as follows:

fn intersection3(T: type, a: []const T, b: []const T) ?[]const T {
    const start = if (@intFromPtr(a.ptr) > @intFromPtr(b.ptr)) a.ptr else b.ptr;
    const a_end = a.ptr + a.len;
    const b_end = b.ptr + b.len;
    const end = if (@intFromPtr(a_end) < @intFromPtr(b_end)) a_end else b_end;
    return if (@intFromPtr(start) < @intFromPtr(end))
        start[0 .. end - start]
    else
        null;
}

He argued that this approach still loses provenance. I replied that I thought provenance was only lost at the explicit ptr → int → ptr conversion step:

    const ptr: [*]T = @ptrFromInt(start);
    return ptr[0 .. end - start];

But he responded:

The leakage at the comparison point might affect things far after it (or, it might not …

That was essentially the end of our discussion. However, I still can’t fully wrap my head around whether, assuming there is provenance tracking support (which is highly doubted), provenance is actually lost at the comparison step. What do you think?

2

Since pointers are numbers, the logic is the same. Since you can do this logic with c pointers, doesn’t that mean you lose provenance when using c pointers. If that’s true, then there’s no reason to use one over the other (in this case).

I personally prefer casting to an integer

3

I just don’t think compiler is that smart to analyze that there is a comparison on pointers with future-wise implications. I think the compiler just takes it as “ok, there is some runtime op but the result of it is the pointer (optionally, with this-that provenance)”. And honestly, I also prefer casting to an integer.

4

why shouldn’t it, it’s genuinely useful, you have demonstrated that.

My point is that you still potentialy loose provenance when using c pointers.

1 Like
5

Provenance isn’t necessarily violated by casting a pointer to an int, I don’t think your final example code violates regular pointer provenance.

The idea of pointer provenance is that pointers come from somewhere (an allocator or stack-frame or data section etc.); that they’re not “just” numbers. For example, you cannot deallocate a pointer with a different allocator than the one you used to allocate it. Therefore, you should always be able to keep track of where each pointer you create “comes from”. Doing a round-trip ptr->int->ptr cast doesn’t destroy that information or anything (although you definitely can use int->ptr casts to mess up provenance).

There’s also this thing called strict provenance which is gaining traction over in rustland, which describes how you should reason about pointers on esoteric hardware where pointers have metadata attached to them describing who allocated the pointer with which permissions etc. On such hardware, casting a pointer to an integer is meaningless/disallowed, so you have to define a set of rules for dealing with pointer comparisons and arithmetic etc. without casting away the pointer metadata. To come back to your example: suppose you have two slices that overlap in address space but are allocated in physically separated/protected memory regions (as indicated by the pointer metadata). In such a case, it would always be incorrect to create a pointer to the overlap of the slices since it is ambiguous which metadata to give to that pointer. Does it belong to the first pointer’s region or the second pointer’s region? Where does the CPU have to look in order to find the data/check permissions? - it’s impossible to tell. In such a case your function should probably indicate that there is no overlap.

Anyways, strict provenance is a set of rules that makes sense for really uncommon/experimental hardware, so I would not worry about it too much beyond it just being an interesting idea.

6 Likes
6

If separate memory regions can overlap in address space, shouldn’t the CPU support pointers that overlap. Otherwise, it shouldn’t allow the address spaces to overlap in the first place.
I suppose the issue is regarding how the metadata is stored, which sounds like an oversight in design.
IDK am just confused at why it’s an issue.
Good explanation though

1 Like
7

If I remember correctly, in C pointers with different provenance do not compare. And it is expected from the programmer to not even try to compare pointers with different provenance. So if a C compiler sees a comparison between two pointers, it is free to assume they have the same provenance.

Translated to your intersection examples, it would be the programmers fault to pass in slices with different provenance.

From my practitioners point of view I stuck loss of provenance into the realm of potentially missed optimizations. That is as long as you don’t lie to the compiler:

fn f(ptr: *u32) bool {
    var x: u32 = 5;
    const px = &x;
    ptr.* = 10;
    return x == 5;
}

Imagine you pass this function a handcrafted pointer pointing to the stack memory location the variable x will be placed at. I would expect the compiler to reason that x clearly has a different provenance than ptr, because x is a new object. Therefore the assignment to ptr.* can’t alter the value of x. And indeed, Zig generates assembly simply returning true.

Let’s introduce an explicit check to compare the pointers:

fn f(ptr: *u32) bool {
    var x: u32 = 5;
    const px = &x;
    if(ptr == px) {
        ptr.* = 5;
    }
    ptr.* = 10;
    return px.* == 5;
}

The assembly stays the same. I assume it is provenance again. Since x clearly has different provenance than ptr, they can’t both point to the same thing, so there is no need to even look at the bit pattern.

1 Like
8

I’m being pedantic, I know

that’s what llvm generates in release safe
debug llvm build does compare the values,
and so does the custom backend

9

In OP’s second snippet, the final pointer comes from either a or b so I’d expect the provenance metadata be inherited from one of those two pointers. That part shouldn’t be a problem even on those esoteric research platforms like CHERI.

What would be an issue happens before that. @intFromPtr is ill-defined in a strict provenance environment, since pointers are more than just plain integers. However, even Rust folks do believe that they at least have a numeric address part, so those numbers could be extracted and compared.

Of course, if the slices are really in the physically disjoint regions of memory then the notion of “overlap”, while implementable, is not exactly useful, as it’s merely an accident of virtual address space.

10

This is intentionally. The function assumes these two slices come from the same origin (address space/region). I don’t do the check because it is invariant on the caller site.

“potentially missed optimization” is tbh the reason I asked.

Regarding the examples… I can’t believe the backend optimizes these functions to the bare true (making, in my opinion, unsafe assumptions).

const std = @import("std");

fn f(ptr: *u32) bool {
    var x: u32 = 5;
    const px = &x;
    ptr.* = 10;
    return px.* == 5;
}

fn getStackAddr() *u32 {
    var x: u32 = 5;
    return &x;
}

pub fn main() !void {
    const stack_x: *u32 = getStackAddr();
    std.log.err("{any}", .{f(stack_x)});
}

I tried the experiment above given your snippet and indeed:

zig run -O ReleaseFast tmp.zig
error: true
zig run -O Debug tmp.zig               
error: false

The behaviour changes, depending on the release mode. How is that? (Is it ok?)

11

The compiler may lose pointer provenance, or not, regardless of what you do. It all depends on how smart the compiler, and that changes all the time. There isn’t a surefire way to know if the compiler will or will not analyze some code in a certain way.
Instead of guessing whether or not the compiler is intepreting your code in a certain way, just look at the disassembly and see how it changes depending on the implementation.

12

$ zig run tmp.zig
error: true

$ zig run -O ReleaseFast tmp.zig
error: true

/$ zig run -O Debug tmp.zig
error: true

$ zig version
0.13.0

Regards !

13

Behaviour of this is not consistent across hardware, or operating systems.