5 ms·

Now call qsort with a closure.

by tedunangst 7y ago

jstarks 7y ago
I’m sure we could have rustc generate a trampoline function directly on the stack like gcc can. What could go wrong?
- saagarjha 7y ago
  Nothing, if your Rust implementation is bug-free ;)
kazinator 7y ago
This is the TXR Lisp interactive listener of TXR 228. Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet. 1> (with-dyn-lib nil (deffi qsort "qsort" void ((ptr (array wstr)) size-t size-t closure)) (deffi-cb qsort-cb int ((ptr wstr-d) (ptr wstr-d)))) #:lib-0005 2> (let ((vec #("the" "quick" "brown" "fox" "jumped" "over" "the" "lazy" "dogs"))) (prinl vec) (qsort vec (length vec) (sizeof wstr) [qsort-cb (lambda (a b) (cmp-str a b))]) (prinl vec)) #("the" "quick" "brown" "fox" "jumped" "over" "the" "lazy" "dogs") #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the") #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the") The lambda is pointless; we could create the FFI closure directly from cmp-str with [qsort-cb cmp-str]. It shows more clearly that we can use any closure.
rabidferret 7y ago
`void ()(void, everything_else)` is in my personal experience a much more common API than that of `qsort` (probably for exactly the point you're pedantically trying to make), so I chose to focus on that API for this article. There's really no reason to pass a rust closure to `qsort` instead of sorting in Rust. That said, if there's demand for real world use cases that require passing Rust closures to C APIs that take only a function pointer and not a data pointer, I'll be happy to write a follow up.
- tedunangst 7y ago
  XSetErrorHandler for instance.
  - kazinator 7y ago
    signal, sigaction.
- kazinator 7y ago
  In any decent language, all functions are first-class, so if you want to use them as callbacks, you need that to work. That's still true even if the API takes a separate context pointer that is given to your function as an argument. There is still a function pointer there, and what you'd like to use as a function pointer is a function in your local language, and that's an object with an environment. Even if some instances of it have no environment, the FFI mechanism might want to tack on its own. For instance, the FFI needs to be able to route the callback to the appropriate function. Whatever function pointer FFI gives to the C function, when the C library calls that function, FFI has to dispatch it back to the original high level function. That requires context. Now that context could be shoehorned into that context parameter, but it could be inconvenient to do so; that parameter belongs to the program and to the conversation that program is having with the C API.
  - comex 7y ago
    Generating native function pointers on the fly: - is inherently slow, because CPUs have separate data and instruction caches; - is extra slow in practice because you need a separate allocation for executable memory (unless your stacks and heap are RWX, which is a terrible idea); - is not portable, requiring architecture- and OS-specific code; and - is not supported at all in many environments (of varying levels of braindeadness). For a statically compiled language like Rust, it makes much more sense to use the context pointer.
richardwhiuk 7y ago
Just stash the data in a stack in thread local storage. Problem solved.
- gpderetta 7y ago
  Then it wouldn't be a lexical closure.
  - richardwhiuk 7y ago
    It can be from the perspective of the calling code. Roughly speaking: thread_local! { static CBQ: Option<Box<impl FnMut(i32, i32) -> i32>>; } #[no_mangle] extern "C" fn qsort(array: *mut i32, val: usize, callback: impl FnMut(i32, i32) -> i32); pub fn rust_qsort(array : Vec<i32>, callback: impl FnMut(i32, i32) -> i32){ CBQ.replace(Box::new(callback)).unwrap_none(); unsafe { qsort(array.as_mut_ptr(), array.len(), &rust_qsort_callback); } CBQ.take().unwrap(); } fn rust_qsort_callback(a: *mut i32, b: *mut i32) -> i32 { let callback = CBQ.take().unwrap(); let (a, b) = unsafe { (*a, *b) }; let result = callback(a, b); CBQ.replace(callback).unwrap_none(); result } fn main() { let a = vec![4,5,6,3,2]; rust_qsort(a, |a, b| { if a < b { -1 } else if a > b { 1 } else { 0 } }) } ought to work. (There's some fun with generics and panics, which is some fun to solve, but nothing which breaks the premise above).
    - a1369209993 7y ago
      This fails horribly if called recursively (or from a signal handler). You need something like: wrapped_qsort(/* array,callback */) { auto tmp = CBQ; CBQ = wrap(callback); qsort(array.ptr,array.len,cbq_callback); CBQ = tmp; /* pop old value from stack */ }
      - richardwhiuk 7y ago
        It'll fail from a signal handler inside qsort, or inside the callback function. It won't fail recursively - while the second call is happening, the first will be stored on the stack (see the take and replace in the callback shim function)
loeg 7y ago
I don't think qsort changes anything about the mechanism described in the blog post, but maybe I'm missing something. (I.e., use qsort_r...) (qsort is really only for C. Other languages can potentially inline the comparison function, so using FFI for that is kind of insane.)
- 0db532a0 7y ago
  Gets me thinking: I wonder how good Intel CPUs are with dealing with this sort of thing. Can the CPU detect repeated jumps to comparators and in-line them from there? I’d be interested to see a comparative benchmark.
dfox 7y ago
qsort(3) or even ftw(3) is the simple case. You can either dynamically generate trampoline code with exactly bounded dynamic scope (and even do the gcc-style executable stack hack) or simply stash the whole context in some TLS region and completely sidestep the whole issue. Side point: ftw(3) is much more interesting unix API to call from some FFI layer than qsort(3). And I spent about a year pestering people from Sun with you should implement fts_open(3) and friends because it presents more sane API for FFIs for the same functionality.
- wahern 7y ago
  And it appears that you succeeded. Awesome! It seems Solaris has been adding many BSD and, especially, Linux compatibility APIs lately. It seems too little, too late; or perhaps the initiative is part of their effort to EoL Solaris, providing an upgrade path to Linux.
  - dfox 7y ago
    Well in fact I gave up about 10 years ago :)
comex 7y ago
If a Rust closure doesn’t actually close over any variables, it can be coerced to a function pointer. Otherwise, you’re stuck with the workarounds others have mentioned.
marcan_42 7y ago
Use `qsort_r()`, which gives you an extra argument for your closure.
imstuff 7y ago
ok extern "C" { #![allow(improper_ctypes)] fn qsort( ptr: *mut (), count: usize, size: usize, comp: extern "C" fn (*const (), *const ()) -> i32, ); fn qsort_r( ptr: *mut (), count: usize, size: usize, comp: extern "C" fn (*const (), *const (), *mut ()) -> i32, context: *mut () ) -> usize; } #[derive(Debug)] pub struct CQsortError; /// calls qsort or qsort_r from libc pub fn rust_qsort<T, F: FnMut(&T, &T) -> i32>(items: &mut [T], mut compare: F) -> Result<(), CQsortError> { #![allow(improper_ctypes)] extern "C" fn call_cmp_fn_with_context<T, Out, F: FnMut(&T, &T) -> Out>( a: *const (), b: *const (), context: *mut () ) -> Out { unsafe { (context as *mut F).as_mut().unwrap()( (a as *const T).as_ref().unwrap(), (b as *const T).as_ref().unwrap(), ) } } /// for zero-sized F extern "C" fn call_cmp_fn_static<T, Out, F: FnMut(&T, &T) -> Out>( a: *const (), b: *const (), ) -> Out { unsafe { // HACK: // if we use core::ptr::null_mut, the compiler thinks it's invalid and makes the funtion always crash // however, it can be anything since it "points" to a zst // the compiler thinks 1 is a valid pointer std::mem::transmute::<_, &mut F>(1_usize)( (a as *const T).as_ref().unwrap(), (b as *const T).as_ref().unwrap(), ) } } unsafe { // it doesn't have any state, call qsort without context if std::mem::size_of::<F>() == 0 { qsort(items.as_mut_ptr() as *mut (), items.len(), std::mem::size_of::<T>(), call_cmp_fn_static::<T, i32, F>); Ok(()) } else { if qsort_r(items.as_mut_ptr() as *mut (), items.len(), std::mem::size_of::<T>(), call_cmp_fn_with_context::<T, i32, F>, &mut compare as *mut _ as *mut ()) == 0 { Ok(()) } else { Err(CQsortError) } } } } Does anyone know how to use a "proper" ctype instead of *{const|mut} T so rustc doesn't warn about it? And is calling functions on invalid references to zero-sized types like that safe?

Now call qsort with a closure.

jstarks 7y ago

I’m sure we could have rustc generate a trampoline function directly on the stack like gcc can. What could go wrong?

saagarjha 7y ago
Nothing, if your Rust implementation is bug-free ;)

kazinator 7y ago

This is the TXR Lisp interactive listener of TXR 228. Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet. 1> (with-dyn-lib nil (deffi qsort "qsort" void ((ptr (array wstr)) size-t size-t closure)) (deffi-cb qsort-cb int ((ptr wstr-d) (ptr wstr-d)))) #:lib-0005 2> (let ((vec #("the" "quick" "brown" "fox" "jumped" "over" "the" "lazy" "dogs"))) (prinl vec) (qsort vec (length vec) (sizeof wstr) [qsort-cb (lambda (a b) (cmp-str a b))]) (prinl vec)) #("the" "quick" "brown" "fox" "jumped" "over" "the" "lazy" "dogs") #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the") #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the") The lambda is pointless; we could create the FFI closure directly from cmp-str with [qsort-cb cmp-str]. It shows more clearly that we can use any closure.

rabidferret 7y ago

`void ()(void, everything_else)` is in my personal experience a much more common API than that of `qsort` (probably for exactly the point you're pedantically trying to make), so I chose to focus on that API for this article. There's really no reason to pass a rust closure to `qsort` instead of sorting in Rust. That said, if there's demand for real world use cases that require passing Rust closures to C APIs that take only a function pointer and not a data pointer, I'll be happy to write a follow up.

tedunangst 7y ago
XSetErrorHandler for instance.
- kazinator 7y ago
  signal, sigaction.
kazinator 7y ago
In any decent language, all functions are first-class, so if you want to use them as callbacks, you need that to work. That's still true even if the API takes a separate context pointer that is given to your function as an argument. There is still a function pointer there, and what you'd like to use as a function pointer is a function in your local language, and that's an object with an environment. Even if some instances of it have no environment, the FFI mechanism might want to tack on its own. For instance, the FFI needs to be able to route the callback to the appropriate function. Whatever function pointer FFI gives to the C function, when the C library calls that function, FFI has to dispatch it back to the original high level function. That requires context. Now that context could be shoehorned into that context parameter, but it could be inconvenient to do so; that parameter belongs to the program and to the conversation that program is having with the C API.
- comex 7y ago
  Generating native function pointers on the fly: - is inherently slow, because CPUs have separate data and instruction caches; - is extra slow in practice because you need a separate allocation for executable memory (unless your stacks and heap are RWX, which is a terrible idea); - is not portable, requiring architecture- and OS-specific code; and - is not supported at all in many environments (of varying levels of braindeadness). For a statically compiled language like Rust, it makes much more sense to use the context pointer.

richardwhiuk 7y ago

Just stash the data in a stack in thread local storage. Problem solved.

gpderetta 7y ago
Then it wouldn't be a lexical closure.
- richardwhiuk 7y ago
  It can be from the perspective of the calling code. Roughly speaking: thread_local! { static CBQ: Option<Box<impl FnMut(i32, i32) -> i32>>; } #[no_mangle] extern "C" fn qsort(array: *mut i32, val: usize, callback: impl FnMut(i32, i32) -> i32); pub fn rust_qsort(array : Vec<i32>, callback: impl FnMut(i32, i32) -> i32){ CBQ.replace(Box::new(callback)).unwrap_none(); unsafe { qsort(array.as_mut_ptr(), array.len(), &rust_qsort_callback); } CBQ.take().unwrap(); } fn rust_qsort_callback(a: *mut i32, b: *mut i32) -> i32 { let callback = CBQ.take().unwrap(); let (a, b) = unsafe { (*a, *b) }; let result = callback(a, b); CBQ.replace(callback).unwrap_none(); result } fn main() { let a = vec![4,5,6,3,2]; rust_qsort(a, |a, b| { if a < b { -1 } else if a > b { 1 } else { 0 } }) } ought to work. (There's some fun with generics and panics, which is some fun to solve, but nothing which breaks the premise above).
  - a1369209993 7y ago
    This fails horribly if called recursively (or from a signal handler). You need something like: wrapped_qsort(/* array,callback */) { auto tmp = CBQ; CBQ = wrap(callback); qsort(array.ptr,array.len,cbq_callback); CBQ = tmp; /* pop old value from stack */ }
    - richardwhiuk 7y ago
      It'll fail from a signal handler inside qsort, or inside the callback function. It won't fail recursively - while the second call is happening, the first will be stored on the stack (see the take and replace in the callback shim function)

loeg 7y ago

I don't think qsort changes anything about the mechanism described in the blog post, but maybe I'm missing something. (I.e., use qsort_r...) (qsort is really only for C. Other languages can potentially inline the comparison function, so using FFI for that is kind of insane.)

0db532a0 7y ago
Gets me thinking: I wonder how good Intel CPUs are with dealing with this sort of thing. Can the CPU detect repeated jumps to comparators and in-line them from there? I’d be interested to see a comparative benchmark.

dfox 7y ago

qsort(3) or even ftw(3) is the simple case. You can either dynamically generate trampoline code with exactly bounded dynamic scope (and even do the gcc-style executable stack hack) or simply stash the whole context in some TLS region and completely sidestep the whole issue. Side point: ftw(3) is much more interesting unix API to call from some FFI layer than qsort(3). And I spent about a year pestering people from Sun with you should implement fts_open(3) and friends because it presents more sane API for FFIs for the same functionality.

wahern 7y ago
And it appears that you succeeded. Awesome! It seems Solaris has been adding many BSD and, especially, Linux compatibility APIs lately. It seems too little, too late; or perhaps the initiative is part of their effort to EoL Solaris, providing an upgrade path to Linux.
- dfox 7y ago
  Well in fact I gave up about 10 years ago :)

comex 7y ago

If a Rust closure doesn’t actually close over any variables, it can be coerced to a function pointer. Otherwise, you’re stuck with the workarounds others have mentioned.

marcan_42 7y ago

Use `qsort_r()`, which gives you an extra argument for your closure.

imstuff 7y ago

ok extern "C" { #![allow(improper_ctypes)] fn qsort( ptr: *mut (), count: usize, size: usize, comp: extern "C" fn (*const (), *const ()) -> i32, ); fn qsort_r( ptr: *mut (), count: usize, size: usize, comp: extern "C" fn (*const (), *const (), *mut ()) -> i32, context: *mut () ) -> usize; } #[derive(Debug)] pub struct CQsortError; /// calls qsort or qsort_r from libc pub fn rust_qsort<T, F: FnMut(&T, &T) -> i32>(items: &mut [T], mut compare: F) -> Result<(), CQsortError> { #![allow(improper_ctypes)] extern "C" fn call_cmp_fn_with_context<T, Out, F: FnMut(&T, &T) -> Out>( a: *const (), b: *const (), context: *mut () ) -> Out { unsafe { (context as *mut F).as_mut().unwrap()( (a as *const T).as_ref().unwrap(), (b as *const T).as_ref().unwrap(), ) } } /// for zero-sized F extern "C" fn call_cmp_fn_static<T, Out, F: FnMut(&T, &T) -> Out>( a: *const (), b: *const (), ) -> Out { unsafe { // HACK: // if we use core::ptr::null_mut, the compiler thinks it's invalid and makes the funtion always crash // however, it can be anything since it "points" to a zst // the compiler thinks 1 is a valid pointer std::mem::transmute::<_, &mut F>(1_usize)( (a as *const T).as_ref().unwrap(), (b as *const T).as_ref().unwrap(), ) } } unsafe { // it doesn't have any state, call qsort without context if std::mem::size_of::<F>() == 0 { qsort(items.as_mut_ptr() as *mut (), items.len(), std::mem::size_of::<T>(), call_cmp_fn_static::<T, i32, F>); Ok(()) } else { if qsort_r(items.as_mut_ptr() as *mut (), items.len(), std::mem::size_of::<T>(), call_cmp_fn_with_context::<T, i32, F>, &mut compare as *mut _ as *mut ()) == 0 { Ok(()) } else { Err(CQsortError) } } } } Does anyone know how to use a "proper" ctype instead of *{const|mut} T so rustc doesn't warn about it? And is calling functions on invalid references to zero-sized types like that safe?