We need a mechanism for practical, safe and efficient destruction of hierarchical system resources

EDIT: Please forgive the bad example. Unloading libraries is super risky. My issue stems from using Vulkan, which is less risky.

System resources frequently have hierarchical relationships which cannot be adequately expressed using Rust's lifetime system. Consider the simple case of loading shared libraries at runtime. It typically goes like this:

  1. Load the library.
  2. Get function pointers from the library.
  3. Use the library through the function pointers.
  4. (Optional) Unload the library.

As long as the steps are performed in this order, all is well. Changing the order in any way results in catastrophe, however. In particular, we must never unload the library before we are done using it, since any function pointers after that point will be dangling. (Note that in this scenario, the library owns the functions pointed to by the function pointers. That is, the pointees are part of the library.)

Now, in Rust, the libloading crate provides an abstraction over OS-specific dynamic linking facilities. The Library and Symbol structs represent a loaded library and symbol from some library. To ensure that a Symbol cannot outlive the Library it is from, it contains a PhantomData reference to its source. Thanks to Rust's lifetime semantics, this ensures that steps 1-4 must be performed in order! Here is a simplified example (that does not compile):

Code
use std::marker::PhantomData;

struct Context {}

impl Context {
    fn create_handle<'a>(&'a self) -> Handle<'a> {
        Handle {
            marker_: PhantomData,
        }
    }
}

impl Drop for Context {
    fn drop(&mut self) { /* destroy context */ }
}

struct Handle<'a> {
    marker_: PhantomData<&'a Context>,
}

impl Drop for Handle<'_> {
    fn drop(&mut self) { /* destroy handle */ }
}

struct App<'a> {
    ctx: Context,
    handle: Handle<'a>,
}

impl<'a> App<'a> {
    fn new() -> App<'a> {
        let ctx = Context {};
        App {
            ctx,
            handle: ctx.create_handle(),
        }
    }
}

However, there is a catch: due to the phantom reference, getting a Symbol from a Library borrows the Library. This means the Library cannot be moved, even though the reference is phantom and we only care about the Library's overall lifetime as an object, rather than its lifetime at the memory location when we borrowed it. This severely restricts the ways in which we can organize code. In particular, we cannot store a Library and its Symbols in the same struct, due to the phantom circular reference. Essentially, we can only use them inside the same block.

The case of loading libraries is really the simplest kind. The main reason I bring this up is because I ran into this problem when trying to code with Vulkan in Rust, which is rife with these parent-child relationships. Furthermore, the Vulkan object model stipulates that, unless otherwise specified, children must be destroyed before their parents. The vulkano crate works around this and offers a safe interface by mandating that essentially everything is wrapped in Arc. This problem has also appeared in the SDL2 binding for Rust: Trouble with using `Texture` when bound by lifetime · Issue #351 · Rust-SDL2/rust-sdl2 · GitHub. I'm certain that others can contribute more examples.

What we really want here:

  1. That resources are automatically released in a correct order.
  2. That using such structs is safe.
  3. Ideally, that such structs can be specified and constructed safely.
  4. That no unnecessary allocations are made.
  5. That such structs are simple to specify and construct.

One potential solution (that would likely be overkill and possibly anathema to Rust's design) would be to enable us to tag values as immovable. This is possible in C++20, since it is possible to return types with no move, copy or assignment constructor. However, all we really need is that .drop() is called in the right order. There may well be simpler and better solutions. (I am not personally involved in Rust's development, nor am I intimately familiar with its design.)

However, this is overall a big ask. To the best of my knowledge, the following are the only current options for working with such quasi-self-referential structures:

Put everything on the stack. Pros: Safe and efficient. Cons: Makes code really awkward to write. Large allocations may cause stack overflow.

Leak the Library instance. Pros: We can give references to it a lifetime of 'static, allowing us to place its Symbols anywhere. Cons: We give up on the possibility of unloading (and possibly incur a heap allocation). Also, this does not work if .drop() needs to be called.

Use Rc or Arc to replace the phantom reference. Pros: No more worries about lifetimes. We can place Symbols freely. The Library will get dropped when appropriate. Cons: We incur a heap allocation and Symbol now contains two pointers instead of one. It is much harder to tell the order in which objects will be dropped.

Use unsafe interfaces to generate a safe and efficient combined Library and Symbol struct using a macro Pros: Does what we need. Cons: Doesn't generalize, since there are many more complex use cases. Need to put everything in a macro. Writing procedural macros is tricky, especially since it would need to unsafe itself.

Use rental, ouroboros or owning_ref Pros: Safe. Cons: They require heap allocation. rental (abandoned) and ouroboros use fairly complex macros.

I hope that with this post I can draw a bit more attention to this issue. Alternatively, it would also be good to know if there are any insurmountable obstacles with safety or Rust's design, so I can instead focus on making better workarounds.

8 Likes

Prior discussion:

1 Like

This option seems to only have the downside of a heap allocation to hold the function pointers struct. What is wrong with that? It won't be done in a loop or repeatedly so it seems like there is little to no downside. I think trying to overthink it while trying to prevent heap allocations seems like creating an artificial obstacle.

5 Likes

To be clear, unloading arbitrary dynamicly loaded code is and will always be unsafe. In fact, in certain cases on certain OSes, unloading libraries may even be a no-op.

And, if I understand the root desire here, you want to be able to have some

struct MyLib {
    imp: Library,
    fn1: Symbol,
    fn2: Symbol,
}

and dynamically own and manage that structure's lifetime, with the library being unloaded when MyLib drops.

And, fundamentally, I think that this isn't an expressible pattern with Rust's static lifetimes. A lifetime represents a borrow of some static resource, that we know will still be there at the end of the lifetime's static scope. Or sightly rephrased: when we start a borrow, we already know that we (the givers of the borrow) still own the resource when the lifetime ends.

There has to be some containing scope that owns the thing that's getting borrowed.

(If you encapsulate the whole thing as with ouroboros, it's possible to treat the library and function pointers as one resource unit. That could potentially be done with a single lifetimeless unit, but has to be a single unit. Likely, it'd be implemented as codegen for a given library binding set and use libloading internally with unsafely hacked in 'static lifetimes. I've long been a proponent of 'unsafe lifetimes for 'static-but-not-really-since-I'm-doing-funky-things, which would be perfect here.)


Ultimately, though: loading a dynamic library is an expensive operation. Just put it behind an Arc! You won't notice that cost compared to the cost of loading the library in the first place.

4 Likes

@CAD97 Yes, after reading through the thread @mathstuf linked, I can see why library unloading is fundamentally unsafe.

That said, as I stated in my post, my personal interest is in using Vulkan safely and efficiently in Rust (assuming such a thing is possible). Obviously, I could just use raw pointers everywhere and pretend I'm writing C, but that runs counter to my expectations for Rust.

@gbutler I want to have my cake and eat it too! One of Rust's selling points is getting both efficiency and safety. If I'm writing a game in Rust, wrapping everything in Arc is is a pretty big blow. Unless I use unsafe, it is a large step down from using C++. It also means possibly giving up on deterministic destruction, which I consider a big feature of Rust.

So, Vulkan has multiple such resource hierarchies 5+ levels deep. And, as stated earlier, children must be destroyed before their parents. There is, however, no fundamental unsafety as with loading or unloading arbitrary code.

In a basic attempt of mine to just get a triangle on the screen, written with the ash crate, and necessarily written using unsafe code, I have the following (read bottom to top):

struct Frame { // all from device
    framebuffer: vk::Framebuffer, // used by render_passes
    command_pool: vk::CommandPool,
    command_buffers: Vec<vk::CommandBuffer>, // interacts with queue
    fence: vk::Fence, // interacts with queue
}

struct Renderer {
    img_available_semaphore: vk::Semaphore, // used by render_passes, from device, interacts with queue
    render_finished_semaphore: vk::Semaphore, // used by render_passes, from device, interacts with queue
    render_passes: Vec<vk::RenderPass>, // from device, pipelines, shader_modules, frames
    pipelines: Vec<vk::Pipeline>, // from device and pipeline_layouts, depends on shader_modules
    pipeline_layouts: Vec<vk::PipelineLayout>, // from device
    shader_modules: Vec<vk::ShaderModule>, // from device
    frames: Vec<Frame>, // from device
    swapchain_views: Vec<vk::ImageView>, // from device
    swapchain: vk::SwapchainKHR, // from khr_swapchain
    khr_swapchain: ash::extensions::khr::Swapchain, // from device; a device extension, dynamically loaded as per spec
    queue: vk::Queue, // from device
    device: ash::Device, // from instance
    surface: vk::SurfaceKHR, // from khr_surface
    khr_surface: ash::extensions::khr::Surface, // from instance; an instance extension, dynamically loaded as per spec
    instance: ash::Instance, // from _entry; a driver instance, dynamically loaded as per spec
    _entry: ash::Entry, // dynamically loads Vulkan, per spec
}

This can be disentangled. The Drop implementation for Renderer looks like this:

impl Drop for Renderer {
    fn drop(&mut self) {
        unsafe {
            self.device.device_wait_idle().unwrap(); // wait for all queues to be empty

            for render_pass in self.render_passes.iter() {
                self.device.destroy_render_pass(*render_pass, None);
            }

            for pipeline in self.pipelines.iter() {
                self.device.destroy_pipeline(*pipeline, None);
            }

            for pipeline_layout in self.pipeline_layouts.iter() {
                self.device.destroy_pipeline_layout(*pipeline_layout, None);
            }

            for shader in self.shader_modules.iter() {
                self.device.destroy_shader_module(*shader, None);
            }

            for frame in self.frames.iter() {
                frame.destroy(&self.device);
            }

            self.device
                .destroy_semaphore(self.img_available_semaphore, None);
            self.device
                .destroy_semaphore(self.render_finished_semaphore, None);

            for view in self.swapchain_views.iter() {
                self.device.destroy_image_view(*view, None);
            }

            self.khr_swapchain.destroy_swapchain(self.swapchain, None);
            self.device.destroy_device(None);
            self.khr_surface.destroy_surface(self.surface, None);
            self.instance.destroy_instance(None);
        }
    }
}

Now, obviously, some unsafe code is necessary. However, it would be clearly preferable if we could split this Drop implementation into safe-to-use wrappers which automatically release their associated resources.

4 Likes

I really do think that runtime reference counting is the way to handle hierarchical resources like this, the same way that we just eat the cost of array bounds checking. The cost is minimal enough -- acquiring/releasing resources like this isn't hot code -- and guarantees safety while allowing arbitrarily complex ownership flow. The cost of reference counting can be further lowered by "+0 passing," where you pass &'_ T-but-with-permission-to-.to_owned() and bump the reference count (also eliminating the double indirection of e.g. &Arc<T>).

If having the child resource own handle pointer to the parent resource is problematic, you can have the parent own the number of children it's given out, and require the programmer to explicitly pass in the resource back to the owner to be released. If they've not all been released, the parent panics and leaks.

The static ownership/lifetime system requires a static outlives guarantee. That is, that an outside scope owns Parent, and Child is arbitrary-control-flow-without-path-analysis-guaranteed to be born and die in a scope strictly contained by the outside scope.

Perhaps a new version of ouroboros that uses Pin to avoid the need for heap allocation can be developed. But creating (and accessing) self-borrowing structures is going to take unsafe for a long time yet.

2 Likes

For example MUSL completely gave up on making dylib unloading work and defined dlclose as a no-op: dlclose.c\ldso\src - musl - musl - an implementation of the standard library for Linux-based systems

Or if you are using thread local storage (eg by statically linking libstd) most systems will refuse to unload your dylib.

3 Likes

Unloading dynamic libraries is extremely dangerous. You should just accept never to dlclose for cases like this where you really won't miss the memory and need it for essentially your whole program.

As one example of several: it's very easy for a library to accidentally end up with a destructor registered in the wrong way, which will cause serious problems if the library gets unloaded. For example std has this issue `thread_local!` dtor registration can pass wrong `__dso_handle` if dynamically linked · Issue #88737 · rust-lang/rust · GitHub, but the fact that std is usually statically linked means it doesn't blow up in practice.

IMO libloading shouldn't have an impl Drop that dlcloses — instead it should have added some unsafe fn for doing so, since 99% of the time the only time you need this is when you are loading many copies of the same library at runtime, and all other times the small benefit is massively outweighed by the risk. Especially given that most of the time the misuse will silently fail.

4 Likes

For completeness, there is https://crates.io/crates/self_cell which uses macro-rules and the implementation is considerably smaller and easier to understand, and much faster to compile at 0 dependencies. But it incurs a heap allocation too.

3 Likes

I understand how static lifetimes work here, but I am interested in probing what it would take to make this work safely in Rust. I do not know if this necessarily requires path analysis, but I hope that there is some syntactic trick which could be implemented to make this more usable. (Though the example I will give shortly gives me doubts about this.) Since PhantomData references are indistinguishable from real references as far as lifetimes are concerned, if we are to keep using it, what we really need is not the lifetime of a borrow of the parent, but the lifetime of that parent's existence. (I'm not yet sure how this would work, but I'm working on some ideas. I can't seem to avoid the need for a path analysis, though.)

Now, even if the cost of reference counting is small, it is still an unnecessary cost. (And again, I expect not to pay extra for safety in Rust.) It also prevents passing slices directly to Vulkan's API, since now their layout is incompatible. Unless the slice is of fixed size, this requires a heap allocation to copy out the relevant data, potentially for every such call.

It turns out you basically cannot easily use Vec in this situation at all. With Arc, you have to unsafely separate out the inner data pass it to the API as a slice. If you instead avoid Arc (e.g., by putting everything on the stack), if you have a vector of multiple parents, you find that you cannot use their children after modifying the vector:

use std::marker::PhantomData;

struct Parent;

impl Parent {
    fn create_child<'a>(&'a self) -> Child<'a> {
        Child {
            val: 0,
            _marker: PhantomData,
        }
    }
}

struct Child<'a> {
    val: i32,
    _marker: PhantomData<&'a Parent>,
}

fn main() {
    let mut parents = vec![Parent];
    let child1 = parents[0].create_child();
    parents.push(Parent);
    let child2 = parents[1].create_child();
    // If this could compile, the next line would be really bad.
    // parents.pop();
    // Commenting out the next line makes this compile because child1's last use
    // is before parents is borrowed mutably by .push().
    println!("child1.val = {}", child1.val);
    println!("child2.val = {}", child2.val);
}

If we view this purely as a problem of supplying the children with the correct lifetime for the phantom reference, then computing that lifetime seems impossible if we must only use lexical scoping. Moving parents into a container is fine, but destroying them from within the container is generally fraught, since we have to be sure that we won't destroy the parent of any existing child. I am still mulling over what to do about this.

However, this problem still seems tractable in the case that parents are stored as separate struct fields. If that is the case, we should be able to trace the identity of a parent through moves, since a parent could only be moved into a local variable or into a struct field with a compatible lifetime.

3 Likes

For a long time, sure. But you could say the same about any language feature that hasn't been designed or implemented yet.

Personally, I find myself wishing for self-referential data structures (in various flavors) quite often when I'm trying to write high-performance Rust code.

In addition, "self-borrowing structures" includes, of course, futures. Currently, in order to compose them, we have to use unsafe and/or ugly unusable macros. Not to mention Pin – it's about as nice as it can be for a pure-library implementation of immovable types, but it's a band-aid for a missing language feature, and it shows. We can do better.

11 Likes

Would path-dependent types be relevant for this use case?

The difference between the immediate use case and self-referential data structure is that the Drop call only needs the option to borrow to be available locally. It doesn't need to keep a pointer to the outer context for its lifetime, it would suffice to somehow receive a borrow to the sibling field in its own Drop.

This, probably, does not require any type system extensions. Would it be more appropriate to address it with a custom Drop-like trait and a macro instead? We need to ensure that the 'donator' field can't be diassociated from its children and that some code can run where a mutable reference to it is available:

trait DropWith<Ctx>: Drop {
    // Actually, does it need to be `unsafe`?
    unsafe fn drop_with(&mut self, ctx: &mut Ctx);
}

impl<T, Ctx> DropWith<Ctx> for Vec<T>
    where T: DropWith<Ctx>
{
    unsafe fn drop_with(&mut self, ctx: &mut Ctx) {
        self.iter_mut().for_each(|el| el.drop_with(ctx));
    }
}


/** Start of user code
 */

// Proc-macro to be implemented.
#[drop_with]
struct Renderer {
    #[drop_with(device)]
    render_passes: Vec<RenderPass>,
    #[drop_with(device)]
    pipelines: Vec<RenderPass>,
    // Probably should require this order for consistency.
    #[drop_with::donator]
    device: wgpu::Device,
}

impl DropWith<Device> for wgpu::Device {
    // ..
}

// Generated impl:
impl Drop for Renderer {
    fn drop(&mut self) {
        unsafe {
            DropWith::drop_with(&mut self.render_passes, &mut self.device);
            DropWith::drop_with(&mut self.pipelines, &mut self.device);
        }
    }
}

Sure this is a bit of a sketch and an exact set of safety requirements is missing but could it work?

1 Like

I like the idea, but there's nothing preventing us from, say, moving in a different parent of the same type or emptying the Vec of children without destroying them. We could perhaps use lifetime branding to protect parents, but I don't see how we could protect the children in the Vec.

It does raise a very good point, though: at least in Vulkan, all children must be returned to one or more of their ancestors to destroy them. This complicates the overall problem a fair bit. However, in any case, we still need to ensure that parents cannot be dropped before their children. In particular, this should make putting them in the wrong order in a struct a compile error.

I've skimmed the path-dependent lifetime paper and discussion, and it might solve this, but I'll have to dig a bit deeper to be sure.

1 Like

Alright, I think I might have come up with a solution using static path-dependent types and linear types. I'm still not 100% confident in my understanding of path-dependent types, so this may be all wrong. The key assumption I used (which I'm pretty sure is true) is this: you can't get two different objects from the same path at the same time. That is, if you have a: S and b: S, where S is a struct with fields tagged with self-paths, then the types of a and b are distinct subtypes of S. (I hope this makes sense; I don't really have a better explanation at this time.)

The key things to know if you haven't read the paper:

  1. T/x is the type T tagged with some access path x.
  2. T/x is a subtype of T. You can coerce T/x to T, but not the other way.
  3. You can tag fields in a struct with paths starting with self. Those paths are interpreted at use site.
  4. You can tag function parameters with a 0-based numerical index n, tagging it with the argument in the nth position.

Regarding linear types: I'm sure there are better thought-out versions for Rust, but the example here uses a !Drop bound to signify that this value cannot be dropped normally. That is, you cannot let it out of scope. You can get rid of it by consuming it either through destructuring or through a new unsafe function called forget_undroppable().

So, here goes:

// Handle is a linear type. It cannot be dropped. It must be passed back to the
// Context that created it for disposal.
struct Handle;
// Can never be boxed without consuming it. Can never be safely Rc'd at all.
// Should infect any type owning a value that is !Drop.
impl !Drop for Handle {}

struct Context {
    // Ensure that we can only move this into itself.
    //
    // If we have Contexts a and b, then the type of a._data should be ()/a
    // and the type of b._data should be ()/b. These are both distinct subtypes
    // of (). Since a move-in is a mutation, type invariance should prevent it,
    // since the types of a and b are not identical (given the dependent types).
    _data: ()/self;
}

impl Context {
    // Tag handles we create with the name of the Context.
    fn create_handle(&self) -> Handle/0 { Handle }
    
    // Only consume handles tagged with the same name as the Context.
    fn destroy_handle(&self, handle: Handle/0) {
        // Since they are safe, ManuallyDrop and forget() should refuse to take
        // !Drop values, since a !Drop value should never be destroyable, but
        // here we are. Maybe there's a better solution to prevent incorrect
        // safe disposal?
        unsafe { std::mem::forget_undroppable(handle); }
    }
}

// App is infectiously !Drop since Handle is !Drop.
struct App { 
    ctx: Context
    handle: Option<Handle/self.ctx>,
}

impl App {
    fn new() -> App {
        // Might be able to do this without the Option, depending on semantics.
        let mut app = App { ctx, handle: None };
        app.handle = app.ctx.create_handle();
        app
    }

    // App is !Drop, so we must consume it to destroy it.
    fn destroy(self) {
        let App {ctx, handle} = self; // Destructure self to consume it.
        for inner in handle.into_iter() {
            // Consume handle.
            ctx.destroy_handle(inner);
        }
        // All !Drop values have been consumed, so we're done.
    }
}

Now, our correctness condition is that all handles must be destroyed before their contexts are. Assuming only safe code uses Context and Handle, this should hold. The reasons why are the following:

  1. Handles cannot be dropped .
  2. Only contexts can consume handles irretrievably, and only through destroy_handle().
  3. Handles are tagged with the path to the context that produced them. Other contexts should reject incorrect handles.

Here's an attempt at a proof of this:

Proof (sketch): Suppose the program is well-typed, and suppose to the contrary that there is a failure of this condition. Then there is some c : Context that was dropped without consuming some h : Handle/π from c where π is an access path to c. Since h cannot be dropped and the program is well-typed, it must be that there is eventually a call ρ.destroy_handle(h) where ρ is an access path to some d : Context, such that π and ρ are equivalent (more precisely, unifiable) at the call site. Therefore, d lives at the same place as c did before it was dropped, and hence d was moved from its original place σ into π at some point prior. However, at that point, the storage of π would have the dependent type of c. Since the type of c._data is ()/π and the type of d._data is ()/σ, it follows that c and d have incompatible dependent types. Thus, since the program is well-typed, no such move could be made. Contradiction! Therefore the correctness condition holds. ∎

This approach also solves the issue of putting parents in a container by restricting the ways you can do that: if you're getting children from a parent, and you need to return them to the appropriate parent, then you need to somehow know which parent you're giving them back to. In my earlier example we had problems since we could not know for certain which parent a child belongs to. Implementing this approach would prevent that problem entirely by forcing you to group them together, so they cannot get lost.

Side note: we might be able to avoid using Option in App, but I don't know if renaming self through moves is sound.

struct A(i32/self);

fn f() {
    let a = A(0); // type of a.0 is i32/a
    let b = a; // is the type of b.0 i32/a or i32/b?
}

(not touching on the other parts)

Relying on linear types isn't great, because linear types are unlikely to be added to Rust for one primary big reason: panics. Any time you call any function, it could panic. This is an implicit point where all of your bindings could end up being dropped.

So effectively, to get linear types you have to either:

  • Say they're only "mostly" linear, and require them to be droppable during unwind
  • Prohibit calling functions that can panic, introducing a very complex effect system to track which functions panic, as well as a complex precondition system for tracking things like when arithmetic can overflow and panic
  • Declare that linear values are poisonous, and one existing on the stack means your program under that stack is effectively panic=abort instead of panic=unwind

The third is what we already have today for types that (double) panic on Drop, just without compiler help to avoid dropping them normally.

This also ignores the cost of introducing a new auto trait, and all of the problems that come with that.

2 Likes

I believe linear types (or something similar) are necessary here to ensure static safety without runtime cost or putting unsafe everywhere. Nevertheless, with just path-dependent types we statically ensure that we can never use (or dispose of) a handle with the wrong context. Now, we can dispense with linear types by doing one of the following:

  1. Marking create_handle() as unsafe.
    • This just passes the buck on safety to the user, so it's probably a non-solution.
  2. Panicking if Handle is ever dropped.
    • In the case of Vulkan, we must instead abort, since unwinding will cause undefined behavior by destroying the parent before all of its children have been destroyed.

In any case, we would definitely want to put #[must_use] on Handle (for whatever that's worth). This would still be worth it, in my opinion. Is it likely that something like this would make it into Rust's type system?

1 Like