FFI: Iterator, MaybeUninit<T> reuses the same T instance with each iteration

[npiaddo]

Hi,

I am currently wrapping an external C library using FFI (generated by bindgen).
This library has two structs that I will name c_table, and c_line.
c_table is a linked list with c_line items.

These types have their respective constructors struct c_table* table_new(),
and struct c_line* line_new(). I use wrapper types to store the pointers
returned by the constructors:

#[repr(transparent)]
pub struct Table {
  inner: *mut c_table,
}

#[repr(transparent)]
pub struct Line {
  inner: *mut c_line,
}

The library provides a function to iterate over the c_lines in the c_table:
int table_next(struct* table, struct* gen_iter, struct ** c_line) which takes a c_table, a gen_iter (manages the state between iterations), writes a pointer to the next c_line and outputs a return code (0 on success, 1 if we are at the end of the list, and a negative number in case of error).

To have a nice rust API, I created a structure TableIter that implements the Iterator trait.

pub struct TableIter<'a> {
  table: &'a Table,
  state: *mut gen_iter,
}

impl<'a> TableIter<'a> {
  pub fn new(table: &'a Table) -> TableIter<'a> {
    let state = new_gen_iter();

    Self { table, state }
  }
}

impl<'a> Iterator for TableIter<'a> {
  type Item = &'a Line;

  fn next(&mut self) -> Option<Self::Item> {
    unsafe {
      let mut line = MaybeUninit<*mut c_line>::uninit();

      match table_next(self.table.inner, self.state, line.as_mut_ptr()) {
        // next line
        0 => {
           // We take the address of the `*mut c_line` received from
           // `table_next` (`*const *mut c_line`), cast it to a `*const Line`
           // (allowed since Line is defined as #[repr(transparent)]), then at
           // last turn it into an Option<&'a Line>
           line.as_ptr().cast::<Line>().as_ref();

        }
        // reached end of table
        1 => None,
        // error
        _ => None,
      }
    }
  }
}

So far, so good! However, this problem crops up when I use TableIter:

// Assuming `table` is initialized with at least two lines
let iter = TableIter::new(table);

let first: &Line = iter.next().unwrap();
// first  = 0x7f54abbaca70  first.inner = 0x7f54a4001100

let second: &Line = iter.next().unwrap();
// second = 0x7f54abbaca70  second.inner = 0x7f54a40012b0

You might have noticed the references first and second are pointing to the same instance of Line, however the values of their inner fields are different.

From what I understand, the uninitialized *mut c_line constructed by

let mut line = MaybeUninit<*mut c_line>::uninit();

resides at the same memory location between calls to TableIter::next. So, each call overwrites the value of the previous item returned by TableIter::next.

I would like first and second to point to different instances of Line.

Therefore, my questions are:

• what/where is the flaw in my code?
• how do I prevent MaybeUninit from reusing the same memory address between
  calls to TableIter::next?

Thanks for taking the time to read this (very long?) description, and for your help!

[nerditation]

@npiaddo

           line.as_ptr().cast::<Line>().as_ref();

this line is unsound, you are creating a borrow out of thin air (well, in this case, not actually "thin air", but dead stack frame).

in order for TableIter<'a> to yield &'a Line as an Iterator, the lifetime of the return value must be derived from the same 'a lifetime, which in your code is the field: table: &'a Table, but you are reborrowing a (dangling) raw pointer that's derived from a local variable (via MaybeUninit::as_mut_ptr()).

note: it's not wrong to reuse the same MaybeUninit<T>, as long the lifetimes is correct. for example, if you change the local variable line: MaybeUninit<*mut c_line> into a field of the Table struct, then your code will be sound:

but I would suggest you rethink how you define the wrapper types. for the c_table, it's ok to have an "box-like" wrapper with owned semantic, but for the c_line, if I understand the ffi API correctly, you don't need a wrapper for the pointer, you can just use &c_line (if you don't like the "snake_case" type name, you can rename it in bindgen, or create aliases, or use a #[repr(transparent)] wrapper).

side note: always minimize the scope of unsafe, and make sure you understands the safety invariant. in your example, the same unsafe keyword conflates two different safety concerns: one for the ffi call of table_next(), another for the raw pointer as_ref().

if you write it separately, it would be immediately obvious where the UB is:

// SAFETY: ffi function, the documentation requires ...
match unsafe { table_next(...) } {
    // SAFETY: as_ref() requires the pointer must be valid for lifetime 'a
    // opps! it's a local variable!
    0 => unsafe {
        line.as_ptr().cast().as_ref()
    }
    //...
}

[SkiFire13]

@npiaddo

what/where is the flaw in my code?

You are returning a reference to the MaybeUninit which is a local variable, and thus becomes invalid when next returns.

Fundamentally you don't have anything you can borrow a &Line from, so you should not return that. You could however make the Line struct hold a lifetime (e.g. by adding a PhantomData<&'a Table> field) and then return Line<'a> from your iterator.

[paramagnetic]

@npiaddo

line.as_ptr().cast::<Line>().as_ref();

You probably meant

line.assume_init().cast::<Line>().as_ref()

You don't want to return a pointer to the MaybeUninit. You want to return the value in the MaybeUninit, which itself happens to be a pointer.

[kornel]

When you return &T it means it already has a permanent storage location for long enough, and that the user of the temporary loan never has to worry about freeing the T.

In your case it's false, because returning from next destroys the object.

Remember that Rust doesn't have garbage collection, which means it can't make any temporary reference live longer. It's your responsibility to ensure it's valid for long enough, or you can't use temporary references for it.

[cg909]

To elaborate a bit on nerditation's comment: as C doesn't handle ownership as strictly as Rust, *mut c_line can encode multiple different things with regards to ownership. It could be

• an owned line on the heap, e.g. returned by line_new() or
• a (mutable) reference to a line that's part of a c_table, e.g. provided by table_next().

I'd write two types to represent lines depending on the ownership situation:

// An owned line on the heap, with a Drop implementation
// that frees the line and Deref/DerefMut implementations
// with target type `Line`.
#[repr(transparent)]
pub struct LineBox {
  inner: NonNull<c_line> // or `*mut c_line`, if that's easier for you
}

// Wrapper type for lines used only behind references
//
// Only neccessary if you want to hide the bindgen'd implementation
// details. Otherwise you can use `&c_line` directly instead of `&Line`.
#[repr(transparent)]
pub struct Line {
  inner: c_line
}

Then your iterator's next function may look like this:

  fn next(&mut self) -> Option<Self::Item> {
    
      let mut line_ptr = MaybeUninit::<*mut c_line>::uninit();
      
      // Safety: Calling table_next with these arguments is sound because of TODO
      let result = unsafe { table_next(self.table.inner, self.state, line_ptr.as_mut_ptr()) };

      match result {
        // next line
        0 => {
           // Safety: Turning the pointer into a `&Line` is allowed since the
           // `*mut c_line` was initialized to a valid and correctly aligned
           // `c_line` pointer by `table_next()` if it returned 0 and `Line`
           // is defined as a transparent wrapper around `c_line`.
           unsafe { line_ptr.assume_init().cast::<Line>().as_ref() }
        }
        // reached end of table
        1 => None,
        // error
        _ => None,
      }
  }

[npiaddo]

Thank you for your replies! Let me see if I understand them correctly.

From the replies of SkiFire13, and @nerditation I understand that in my code,

let mut line = MaybeUninit<*mut c_line>::uninit();

is local to TableIter::next so trying to return a reference to it would be tantamount to writing this code

#[repr(transparent)]
pub struct Table {
  pub(crate) inner: *mut c_table,
}

#[repr(transparent)]
pub struct Line {
  pub(crate) inner: *mut c_line,
}

pub struct TableIter<'a> {
  table: &'a Table,
  state: *mut gen_iter,
}

impl<'a> TableIter<'a> {
  pub fn new(table: &'a Table) -> TableIter<'a> {
    let state = new_gen_iter();

    Self { table, state }
  }
}

impl<'a> Iterator for TableIter<'a> {
  type Item = &'a Line;

  fn next(&mut self) -> Option<Self::Item> {
		let mut line = MaybeUninit<*mut c_line>::uninit();

		let result = unsafe { table_next(self.table.inner, self.state, line.as_mut_ptr()) };
		match result {
			// next line
			0 => {
			     let inner = line.assume_init();
				 let line = Line { inner };

				 Some(&Line)
			}
			// reached end of table
			1 => None,
			// error
			_ => None,
		}
  }
}

which the compiler duly rejects with

error[E0515]: cannot return value referencing local variable `line`

Am I right on this?

From the replies of kornel, and @cg909, I gather that to return a reference, I need to create a permanent storage location first, which I did not. The best solution would be to return an new object that will keep a copy of the value in the variable line.

let mut line = MaybeUninit<*mut c_line>::uninit();

Which means, I need to create a new struct, let's call it TableItem, that TableIter::next will return.

pub struct TableItem <'a> {
  inner: *mut c_line,
  _marker: PhantomData<&'a Table>,
}

impl<'a> TableItem<'a> {
	pub fn new(_: &'a Table, inner: *mut c_line) -> TableItem<'a> {
	  Self { inner, _marker: PhantomData }
	}
}

pub struct TableIter<'a> {
  table: &'a Table,
  state: *mut gen_iter,
}

impl<'a> TableIter<'a> {
  pub fn new(table: &'a Table) -> TableIter<'a> {
    let state = new_gen_iter();

    Self { table, state }
  }
}

impl<'a> Iterator for TableIter<'a> {
  type Item = TableItem<'a>;

  fn next(&mut self) -> Option<Self::Item> {
		let mut line = MaybeUninit<*mut c_line>::uninit();

		let result = unsafe { table_next(self.table.inner, self.state, line.as_mut_ptr()) };
		match result {
			// next line
			0 => {
			     let inner = line.assume_init();
				 let item = TableItem::new(self.table, inner);

				 Some(item)
			}
			// reached end of table
			1 => None,
			// error
			_ => None,
		}
  }
}

Did I get it right?

[SkiFire13]

Yeah this is was I meant.

[npiaddo]

Wonderful!

The initial idea was to have Table mimic the API of Vec.

	Vec<Line>	Table
Iter::next	Option<&'a Line>	Option<TableItem>
IterMut::next	Option<&'a mut Line>	Option<TableItemMut>

But apparently, I can't, due to language limitations.

I will be compelled to create two new types TableItem, and TableItemMut to express the semantics of &Line and &mut Line, instead of using them directly. Which is a shame

And to add insult to injury, creating new types implies either duplicating the code of Line's' getters, setters, and mutators (a maintenance nigthmare!), or use traits and lose the benefit of private, and crate-level public methods (another headache!).

Anyway, thank you all for clearing up a few misconceptions I had about Rust objects. You are life-savers!

Now, back to the drawing board...

Good night!

[nerditation]

@npiaddo

I will be compelled to create two new types TableItem, and TableItemMut to express the semantics of &Line and &mut Line

part of the reason is due to how you define the Line type. the ffi API table_next() returns a pointer to c_line, which, in rust semantics, is totally OK to reintepret as a reference (to c_line or a transparent wrapper), assuming the returned pointer has "non-owning" semantics which points to internal states owned by the c_table.

but your Line wrapper is already a pointer, thus a reference to it (&Line or &mut Line) is actually a pointer to a pointer (i.e. struct c_line ** in C), which requires you store the single level pointer somewhere so the reference is not dangling.

this is not a limitation imposed by the language, but your design choices. as already pointed out, if you make Line a transparent wrapper for the (possibly opaque) C struct, then your iterator can yield &Line (or &c_line directly) without any problem.

[npiaddo]

Ok! Saying that it was due to language limitations wasn't a fair characterization. My apologies!

How would you suggest I proceed from here, keeping in mind that I do not have control over the C library which is a third-party component? Can you point me to code examples where this problem or a similar instance has been solved, that I can take inspiration from?

I am fairly new to Rust, thus should not have made such a sweeping statement. Again, my apologies!

ETA: Apart the offending statement, does the code in my first reply match what you were trying to convey?

[paramagnetic]

@npiaddo

How would you suggest I proceed from here, keeping in mind that I do not have control over the C library which is a third-party component?

What is the semantics of the pointer returned by the library? Does it own the pointed allocation? If so, you'll have to create a wrapper type for it, store the raw pointer, implement functionality such as Deref to actually access the data, and implement Drop to clean it up once appropriate.

[npiaddo]

int table_next(struct c_table *tb, struct gen_iter *iter, struct c_line **ln) returns what is essentially a const struct c_line * since a c_table keeps ownership of its content, and manages its items' life cycle.

bindgen translates it to pub unsafe extern "C" fn table_next(tb: *mut c_table, itr: *mut gen_iter, ln: *mut *mut c_line) -> c_int.

c_lines are reference counted. When a c_table is freed, it decrements reference counts of the items it holds, freeing the ones that reach 0. I already implemented Drop for Table, and Line (not shown in the code examples I provided, for concision).

It dawned on me, while writing this, that I can simply increment the reference count of the * mut c_line returned by table_next , wrap it in a Line, and let TableIter::next return an Option<Line>. It will not be freed by Table when it eventually goes out of scope.

This design has however several drawbacks:

• I can't rely on the compiler to warn me about lifetime violations,
• a Line is an owned object so I won't be able to enforce the same shared reference semantics of a &Line (i.e. data immutability) as if I were to return an Option<&Line>,
• TableIter::iter and TableIter::iter_mut are indistinguishable from one another,
• I don't see how I can easily implement Index and IndexMut by leveraging TabIter with this modification.

[nerditation]

@npiaddo

I do not have control over the C library which is a third-party component

that's ok. you can even use opaque types. for example, suppose you have some C APIs in Object-Oriented style:

// foo.h
/// all APIs accept a pointer to an opaque `Foo` type
typedef struct Foo *FooPtr;
/// a `Foo` may contain several `Bar`s
typedef struct Bar *BarPtr;

/// constructor of `Foo`:
/// allocate and construct a owned pointer to the opaque `Foo` type
/// return nullptr if fails
FooPtr new_foo();

/// destructor of `Foo`:
/// release the resource managed by `foo` and deallocate the memory
void delete_foo(FooPtr foo);

/// get a non-owning `Bar` pointer given its ID
/// returns nullptr if ID does not exist
BarPtr foo_get_bar(FooPtr foo, char const *id);

/// example method for `Bar` objects:
char const *bar_get_name(BarPtr bar);

// more "methods" for `Foo`, `Bar`, etc
// ...

I would probably do the ffi binding in this way:

// src/lib.rs

pub mod sys {
    // generated in `build.rs` using bindgen
    include!(concat!(env!("OUT_DIR"), "/bindings.rs"));
    // possible example of generated code below:
    // for illustration only, actual code depends your bindgen config
    #[repr(C)]
    pub struct Foo {
        __opaque_blob: [u8; 0]
    }
    #[repr(C)]
    pub struct Bar {
        __opaque_blob: [u8; 0]
    }
    type FooPtr = *mut Foo;
    type BarPtr = *mut Bar;
    extern "C" {
        pub fn new_foo() -> FooPtr;
        pub fn delete_foo(foo: FooPtr);
        pub fn foo_get_bar(foo: FooPtr, id: *const c_char);
        pub fn bar_get_name(bar: BarPtr) -> *const c_char;
    }
}

// re-export the ffi type directly as public API
// they cannot be constructed, only way to get a pointer is through the API
pub use sys::Foo;
pub use sys::Bar;

/// an RAII wrapper for an owned `Foo` pointer.
/// use `NonNull` so niche optmization is enabled
pub struct FooBox(NonNull<sys::Foo>);

// note we don't have a owned wrapper for `Bar`, intentionally

impl Drop for FooBox {
    fn drop(&mut self) {
        // SAFETY: calling ffi destructor with pointer obtained from ffi constructor
        unsafe { sys::delete_foo(self.0.as_mut_ptr() }
    }
}

// implements `Deref` (and `DerefMut` if required) so we can call `Foo`'s methods
impl Deref for FooBox {
    type Target = sys::Foo;
    fn deref(&self) -> &sys::Foo {
        // SAFETY: pointer is obtained from ffi constructor so it's initialized
        // lifetime is correct because self owns the pointer
        unsafe {
            self.0.as_ref()
        }
    }
}
// wrapper for `Foo`'s methods.
// use `&self` (or `&mut self` if appropriate) as receiver argument
impl sys::Foo {
    /// wrapper for the constructor
    pub fn new() -> Option<FooBox> {
        // SAFETY: constructor is safe to call, returns nullptr on fail instead of throw
        let raw_ptr = unsafe {
            sys::new_foo()
        };
        NonNull::new(raw_ptr).map(FooBox)
    }
    /// wrapper for `foo_get_bar`, `id` is a string in utf8
    /// note this returns a reference of `Bar` which borrows `self`
    /// alternatively, use `&str` as `id` and create a `CString` internally
    pub fn get_bar(&self, id: &CStr) -> Option<&sys::Bar> {
        // SAFETY: ffi API is safe to call, because `CStr` is properly null terminated
        let raw_ptr = unsafe {
            sys::foo_get_bar(self, id.as_ptr().cast())
        };
        // SAFETY: returned pointer is either nullptr or points to internal data of `self` with correct lifetime
        unsafe {
            raw_ptr.as_ref()
        }
    }
}

// wrapper for `Bar`'s methods
impl sys::Bar {
    // wrapper for `bar_get_name()`
    // use rust reference `&self`, not raw pointers
    pub fn get_name(&self) -> &CStr {
        // SAFETY: bar_get_name() will not fail, returned pointer points to internal data of `self` which has the correct lifetime
        let raw_ptr = unsafe {
            sys::bar_get_name(self)
        };
        // SAFETY: the returned pointer should point to a null terminated string, otherwise, it's a bug of the C library and will cause UB
        unsafe {
            CStr::from_ptr(raw_ptr.cast())
        }
    }
}

it can be used like this:

fn main() {
    let foo = foo::Foo::new().expect("failed to create new Foo");
    let bar = foo.get_bar(c"this.is.a.bar.id").expect("the bar ID doesn't exist");
    let name = bar.get_name();
    println!("name of `bar` is {}", name.to_string_lossy());
}

[npiaddo]

Very interesting! I might steal the design for future devs. Thank you!

[npiaddo]

Sorry for the late reply, I had to deal with an incident that required my full attention.
It took the major part of my weekend, but I think I found a solution.

TLDR, I improvised a garbage collector, and broke a promise
Feel free to provide some feedback.

pub struct Table {
  pub(crate) inner: *mut c_table,
  // Improvised GC, to collect the locations of temporary *mut c_table copies
  // kept on the heap.
  pub(crate) gc: Vec<*mut *mut c_table>,
}

impl Drop for Table {
  fn drop(&mut self) {
    // Free the c_table
    unsafe { unref_table(self.inner) };

    // Free the `Box`ed pointers on the heap
    while let Some(boxed_ptr) = self.gc.pop() {
      let _ = unsafe { Box::from_raw(boxed_ptr) };
    }
  }
}

#[repr(transparent)]
pub struct Line {
  pub(crate) inner: *mut c_line,
}

pub struct TableIter<'a> {
  table_ptr: NonNull<Table>,
  state: *mut gen_iter,
  _marker: PhantomData<&'a Table>,
}

impl<'a> TableIter<'a> {

  pub fn new(table: &'a Table) -> TableIter<'a> {
    // A NonNull pointer gives the freedom to break the promise of data
    // immutability made by the reference.
    let table_ptr = NonNull::from(table);

    let state = new_gen_iter();

    Self { table_ptr, state, _marker: PhantomData }
  }
}

impl<'a> Iterator for TableIter<'a> {
  type Item = &'a Line;

  fn next(&mut self) -> Option<Self::Item> {
    let mut line = MaybeUninit<*mut c_line>::uninit();

    let result = unsafe { table_next(self.table_ptr.as_ref().inner, self.state, line.as_mut_ptr()) };

    match result {
      // next line
      0 => {
         let ptr = unsafe { line.assume_init() };

         // Creates a copy of ptr on the heap
         let boxed = Box::new(ptr);

         // Prevents the program from freeing the boxed pointer when
         // `TableIter::next` returns.
         let boxed_ptr = Box::into_raw(boxed);

         // Keeps a copy of the pointer to the boxed pointer for later disposal.
         // Here I break the promise of data immutability, which might lead to
         // surprising results down the line(?).
         //
         // The documentation says
         // > while this reference exists, the memory the pointer points to
         // > must not get accessed (read or written) through any other pointer
         //
         // https://doc.rust-lang.org/std/ptr/struct.NonNull.html#method.as_mut
         //
         // I may be wrong, but I think in a single-threaded program, that condition
         // should hold.
         unsafe { self.table_ptr.as_mut().gc.push(boxed_ptr) };

         // This type coercion is `unsafe` due to dereferencing the pointer,
         // not the conversion per-se.
         let item = unsafe { &*(boxed_ptr as *const *mut c_line as *const Line) };

         Some(item)
      }
      // reached end of table
      1 => None,
      // error
      _ => None,
    }
  }

  // The default implementation calls `TableIter::next` n times, discarding n-1
  // items. In the worst case scenario, with the current version of
  // `TableIter::next`, each invocation will cost 8*n bytes; growing the size
  // of the "GC" quadratically.
  //
  // Overriding the default with this code should set a fixed 8-byte cost per call.
  fn nth(&mut self, n: usize) -> Option<Self::Item> {
    let mut line = MaybeUninit<*mut c_line>::uninit();
    let mut result;

    for _ in 0..n {
      result = unsafe { table_next(self.table_ptr.as_ref().inner, self.state, line.as_mut_ptr()) };

      if result != 0 { return None; }

    }

    self.next()
  }
}