Native pointer vectors

[jwise]

Native pointer vectors

This bug is a request for comment. I am but a novice Rust developer, but I suspect that this would be a strong addition to the language.

The exact mechanics were fleshed out further in this bug; read down for more on what actually was implemented.

Motivation

While working on bindings for FFTW (the Fastest Fourier Transform in the West), I ran into the hairy issue that it doesn't seem possible to have Rust hold vector pointers to the outside world. What do I mean by this -- and why do we care? Well, I'll provide (a distilled version of) the FFTW APIs in question, by way of example:

double *fftw_malloc(size_t sz);
fftw_plan_t *fftw_plan_fft(size_t n, double *in, double *out, int flags); /* morally */
void fftw_execute(fftw_plan_t *plan);

The general course of action when using FFTW is to use fftw_malloc to get a chunk of space to store your inputs and outputs, then create a "plan" with fftw_plan (a potentially expensive operation, but if you intend to run many FFTs, ultimately time-saving), and then finally execute the plan with fftw_execute when you've populated your buffers. You can fftw_execute the same plan many times (and, in fact, if you can, you should!) after refilling the buffers and taking data out.

In FFTW-land, fftw_malloc is not strictly necessary as the only way to get memory, but it's a Damn Good Idea -- and as I'll discuss in a moment, not using it doesn't save us. fftw_malloc goes out of its way to obtain memory that has "nice" properties; for instance, it tries hard to align things not just to double boundaries, but also to cache lines, depending on how much memory you ask for. If it knows anything else interesting about your system, it takes that into account. So, it's not fatal to not use it, if that's the only thing you can do ... but it sure does hurt.

Currently, in Rust, there is no way to import a pointer from the outside world and use it mutably, nor is there a way to tell Rust that this pointer may be written to by an outside API. The closest thing that Rust has is vec::unsafe::from_buf, which in turn calls rustrt::vec_from_buf_shared, but the first thing that vec_from_buf_shared does is allocate a new space and copy the memory away! This makes it unsuitable for referencing both the in and the out pointers; changing a pointer that has been imported through this mechanism will cause changes not to get written back to the outside world, and executing a transform to (and overwriting the contents of) a pointer that has been imported through this mechanism will cause Rust to not see the changes that happen after the copy.

In this case, we have another option, though. We could create a vector inside Rust, and use vec::unsafe::to_ptr to create a pointer to it. This will work, but it is dangerously broken (violates safety) in three ways. In the first, Rust is not in control of the lifecycle of the external reference; Rust cannot know when the external reference no longer exists, and may prematurely garbage collect the vector. This can happen, for instance, in the case in which a reference to the out pointer is still live, and a reference to the plan is still live, but the reference to the in pointer is dead; calling fftw_execute on this plan will result in doing accesses to the dead in vector, which may have been garbage collected.

In the second, Rust may reallocate memory out from under the external application. The vector can be appended to, which may cause a reallocation to occur. The external application's pointer will not be updated, and when it goes to access that pointer, that memory will be dead. In the case of a "correct" usage, this will not occur (i.e., the programmer can be instructed not to do that), but this violates safety; at the very least, += now becomes an unsafe operation.

In the third, perhaps most compellingly, this locks Rust into a world in which it is not permissible to have a copying garbage collector. Right now, Rust does ref-counting and garbage collection with free()... but this need not always be the case! Another implementation of Rust could very conceivably experiment with garbage collection schemes for better performance. If the behavior of pointers were already specified, it would be one story, but currently that behavior is not -- and I argue, for the better.

In short, the language's existing capabilities for this are not sufficient to operate with at least one API.

Use cases

The FFTW API is not the only system in which the current capabilities for referring to native memory are insufficient. Consider also:

• A framebuffer interface, in which an external resource has mmap()ed some memory. Accesses must go to exactly those addresses; none else will do.
• A command queue interface, in which a set of commands are provided for an external device (say, a graphics card) to DMA to and from chunks of memory. (This is how modern graphics cards operate.) Accesses must go to some prescribed address, usually managed through a remote resource manager (DRI, et al); no other address will do.

These are both examples of requiring a specific address... recall, however, that there are surely many applications that require some mutable chunk of memory, any mutable chunk at all! Consider, for instance, the ioctl() interface on Linux, which has a similar "combination input/output buffer".

The FFTW API is one of many cases that require mutable memory accessible to the native system.

Proposed solution

I propose the addition of a vector qualifier, [native T]. The type [native T] does not unify with [T]; it is mainly distinct from the normal vector, but that dereferencing indexes in it and iterating over it both work.

The type [native T] has one introduction form:

unsafe fn std::vec::unsafe::native<T>(ptr: *T, elts: uint) -> [native T];

The following elimination forms of vectors function for native vectors:

• v[a] as an expression (with size checking)
• v[a] as an lvalue (with size checking)
• for t: T in v as a loop construct

Notably, the following form does not function:

• v += vp as an append

When a native vector goes out of scope, the native memory pointed to is not modified or otherwise operated upon.

These are the basic rules for a native vector.

Implementation

A native vector has the following internal representation:

type native_repr<T> = { len: uint, data: *T };

It is distinct in the type system because it does not share a representation with a Rust vector. This choice was made to avoid the performance cost of having to check at run time whether any given vector is a Rust vector or a native vector before accessing it.

Translation is presumably very similar to Rust vectors.

It could be the case that no rustrt support is needed for this, since the native_repr type can be constructed purely in Rust, and then can be reinterpret_casted into a native vector.

Extensions

The above describes a basic semantics for a native vector. It provides a semantics sufficient to behave safely, but missing are two potentially useful extensions. These are optional, and certainly not required for a first pass implementation, but would make the native vector substantially more usable.

[native? T] unification

There is currently a substantial vector library built up to operate on Rust vectors. Just because some operations do not apply, it does not make sense to have to duplicate the ones that do. For that, I propose the [native? T] qualifier, similar to [mutable? T]. Presumably a separate code path would have to be emitted at translate time. I do not know enough about the inner workings of mutable? to comment on how similar this might be, and how possible this might be given the existing Rust codebase.

Built in destructors

It can be potentially useful to have Rust take over lifecycle management of memory, if the FFI binding builder is careful. Classically, the mechanism by which one might do this is as such:

type mem = {
  vec : [native f64],
  dtor : @mem_res
};

fn malloc(n : uint) -> mem {
  let mem = fftw_native::fftw_malloc(n * 8u);
  ret { vec: unsafe { vec::unsafe::native(mem as *f64, n) }, dtor: @mem_res(mem) };
}

resource mem_res(mem: fftw_native::mem) {
  fftw_native::fftw_free(mem);
}

This has the unfortunate downside that a user of the API can extract the vec from the type mem, and let the type mem itself go out of scope (or otherwise become dead). When the type mem itself becomes dead, the resource can immediately be freed, even though the native vector may still be live; this can violate safety.

A native vector, then, may wish to have an introduction form that includes a resource pointer associated with it, for built-in cleanup.

Conclusion

In this document, I describe a new form of vector called the native vector. The native vector allows Rust to safely interact with external memory. The introduction form is unsafe, so although it would permit inter-task shared memory communication, it does not do so in a particularly novel fashion. This proposed solution addresses all of the mentioned use cases in what seems (to the untrained eye!) like an elegant, Rust-like fashion.

Thoughts?

[nikomatsakis]

First off, thanks for the well-reasoned and written up proposal. Here is another possible solution that seems a bit less invasive. First, we add the ability to dereference unsafe pointers using [] syntax. Therefore, for a value x of type *T, x[5] would do the same thing as in C, just as *x is currently permitted. Both of course are only legal in unsafe code.

Based on this, one can implement the proposed unsafe vectors as a library. Something like:

mod c_vec {
    type t<T> = { base: *T, size: uint };
    fn create<T>(base: *T, size: uint) -> @t<T> { ret @{ base:base, size:size}; }
    fn get<T>(v: t<T>, idx: uint) -> T unsafe { assert idx < v.size; ret v.base[idx]; }
}  

Now instances of c_vec can be used from safe code. Besides syntax, the one issue is the re-use of higher-order functions from the vec module and so forth. I think that this could be addressed with traits or other similar solutions.

[brson]

This is an important problem to solve, but I'm reluctant to solve it at the language level because vectors are likely going to change yet again and, as niko hinted, the language will probably become expressive enough solve it in std.

Eventually we should be able to implement c_vec and vec as implementations of a common interface and treat them more or less interchangeably.

Still, we need some solution now since people are going to be writing more and more interop code. Can we implement a stopgap c_vec module now that would make writing this kind of code more convenient?

[nikomatsakis]

so everything I described can be written today if the [] operation were added, which doesn't seem very difficult. You would end up with some code duplication, I guess. Also we need to think about when these arrays get freed---probably you want a resource?

[jwise]

Right. Well, yeah, I could add the [] operation if that seems like the Right Way to do it.

Resources seem like a solution, but the question is where the resource goes ... take a look at the "built in destructors" extension proposal in my original post?

[brson]

I think it could be done even without []. We have pointer math.

[msullivan]

Client code could be prevented from pulling out the vec by keeping mem abstract, I think?

(Where by abstract I mean "wrapping it in a tag and not exporting the constructor", unless we have added more real abstract types while I was gone)

[brson]

Yes, except that #818 is still not fixed. Could also put it in an obj if you don't mind the vtable.

[jwise]

@msullivan: That would work.

@brson: OK -- I can try hacking that up tomorrow or tomorrow evening.

I'm still not convinced, though, that not unifying with the existing vector bits isn't the right way. I thought about it some more today. Having to call out to a function to safely do a set and a get on a native vector -- an operation that we probably want to be fast! Adding typeclass dispatch for all vectors creates quite a bit of overhead... is that really the right thing to do?

I agree that where possible, "more general" solutions are better than "more specific". But I'm not totally convinced that in this specific case, typeclassing vectors will lead to acceptable performance...

[nikomatsakis]

There is no dynamic overhead to the categories that I proposed. All calls would be dispatched statically. I don't know the details of how Haskell typeclasses are implemented but I think categories are not 100% analogous. Without inlining, it's true that there is some function call overhead to do the get() operations. You will have overhead if you want to have some function that accepts either a native or a non-native vector and performs operations on it, because that will require an interface, which involves dynamic dispatch.

However, there is one limitation that I was thinking about with the categories. The implementations of higher-order functions like map() will be difficult to share because their type signatures are hard to express without knowledge the direct types involved. This is the precise issue that the Scala people addressed in their 2.8 collection rewrite.

For example, consider a trait vec_like:

trait vec_like<T> {
    req fn get(idx: uint) -> T;
    req fn set(idx: uint, T value);
    req fn len() -> uint;

    // foreach works great
    fn foreach(b: block(T) => ()) {
        let i = 0u, n = len();
        while i < n { b(get(i)); }
    }

    // map... not so great. what is the return type?
    fn map<S>(b: block(T) => S) -> ??? {
    }
}

The earlier versions of Scala addressed this problem through inheritance. The return type of map(), for example, would be vec_like<T>, and there would be a req fn clone() -> vec_like<T> function that duplicated the existing vector-like thing. This is ok but not great and doesn't apply to us very well since vec_like<T> is not a type. The newer versions use implicits to get much more precision but with much more complexity. You also need parameterization by type constructors, not just types. Again, another level of complexity.

I still think native vectors don't need to be built into the language more than they already are, and much of the code can be shared, but without some significant design work there will be more redundancy than I originally envisioned.

[nikomatsakis]

One "worse is better" solution to the problem I just described: functions like map() just return normal Rust vectors. Actually, I think this is what the original proposal specified as well.

trait vec_like<T> {
    ...
    fn map<S>(b: block(T) => S) -> [S] {
        let res = [];
        foreach { |e| res += [e]; }
        return e;
    }
}

This certainly works ok for this situation and may prove to be enough for us, depending on how rich our collections library becomes. It's not as great if you have a linked list, say, and you want it to act "vector-like" but still be a linked list after a map operation. Of course, then you can just redefine the map() function in your linked list library. But then your linked list doesn't have a compatible type signature, which is too bad.

[jwise]

Right, indeed, "map" just returned Rust vectors in the original implementation.

So here's what I'm hearing: either way, there should be a c_vec module with manual "get" and "set" that wrap the unsafeness inside of them. There is substantial pain involved in not being able to use [], but that pain might be resolved in the future by what you call traits (and what I call typeclasses). The c_vec needs no language extensions -- just basis extensions, and would be sufficient to unblock a user of fftw.

@brson commented that [] is not necessary on native pointers, but I'm not entirely convinced yet. Strictly, there are a lot of things that are not "needed" in a language, but not having sugar makes a lot of operations pretty disgusting...

I'll write a mod c_vec tonight, and see if using it makes me want to puke or not.

[jwise]

So here's one thing that we don't have exposed from the language that we certainly do need in order to have mod c_vec. In order to add pointers together, the best that we can get is something like:

fn p<T>(t: t<T>, ofs: uint) -> *mutable T {
    // I'd like to do the following, but FIXME #1173
    // (*t).base + (ofs as *T)
    ((*t).base as uint + ofs) as *mutable T
}

Specifically, I cannot write (*t).base + ofs directly, since if I do:

./c_vec.rs:36:17: 36:20 error: mismatched types: expected *ps0 but found uint (types differ)
./c_vec.rs:36     ((*t).base + ofs) as *mutable T

This would be by itself just an annoyance, but the fatality here is that we can't know the size of a T at compile time -- I believe there is no sizeof-like operator.

Thoughts for a workaround?

[nikomatsakis]

What you want to do, I believe, is this:

mod c_vec {
    import ptr;

    type t<T> = {
        base: *T;
        len: uint;
    };

    unsafe create(base: *T, len: uint) -> t<T> {
        ret { base: base, len: len };
    }

    fn get<T>(v: t<T>, idx: uint) -> T unsafe {
        assert idx < v.len;
        let ptr = ptr::offset(v.base, idx)
        ret *ptr;
    }

    fn set<T>(v: t<T>, idx: uint, value: T) unsafe {
        assert idx < v.len;
        let ptr = ptr::offset(v.base, idx)
        *ptr = value;
    }
}

The key here is the ptr::offset() function, which performs pointer arithmetic. I made the construction function unsafe because it has no way to verify the length or that the pointer is valid. I also didn't pay any attention to freeing the vector. I also didn't try to compile this, but it should work. :)

With respect to the annoyance of typing c_vec::get() and c_vec::set(), I hear you. I think the only solution to that is user-defined operators. I personally like the idea but others may disagree.

[jwise]

Right, ptr::offset() did the right thing -- sort of. There are a few other niggling details in there, but I have a pull request ready in pull request #1217. (Not ready to be pulled yet; an RFC at this stage.)

Of note, there are a few things that I'm not sure about in there. I'm not sure about whether <copy T> is the right thing -- this seems to be new as of this week? Similarly, I'm not convinced (or unconvinced) that the mutable T cast is the right thing. I asked Marijn about the copy T issue on IRC, so hopefully I'll get some clarification there.

I haven't written tests for it yet, but I could easily do so as needed.

[jwise]

I've renamed the pull request away from "do not merge"; I would say it is approaching ready.

[jwise]

Closed, pending rework in #1227 for get and set (and perhaps [] overloading).