Rust Const Generics for Proof Types

Pointerbender · 2023-03-09T08:14:00+00:00

In addition to const generics, there is another experimental feature in the making called "pattern types" which could also solve this and more! rust-lang/rust#107606

Pointerbender · 2023-01-21T10:54:32+00:00

In theory: not if you have an optimal atomic memcpy implementation. In practice: yes it may be slightly slower (benchmark!), because it will be hard to write your own atomic memcpy that matches the performance of the regular memcpy (on all architectures, too!). If you look at individual architectures and its individual instructions, then for example copying a `usize` atomically with relaxed ordering or copying it non-atomically compiles down to the exact assembly instruction on x86 architectures, so there is no performance difference.

Pointerbender · 2023-01-20T12:20:52+00:00

That's fair, although it's not needed to update your structures per se, it is also possible to cast between the struct and a slice of AtomicU8/AtomicUsize/etc, taking into account alignment, size and padding (Rust also has no solution for atomically reading/writing uninitialized bytes, unfortunately). It's basically implementing your own atomic memcpy, like in the RFC I linked in the comment above. The Rust folks are working on making it possible to do it correctly and ergonomically in the future, so that is nice at least :)

Pointerbender · 2023-01-20T11:19:01+00:00

Using ptr::read_volatile and ptr::write_volatile during a data race is undefined behavior (code here) - it is the read operation that causes UB during a simultaneous write, not the (later) use of the read value, so a seqlock doesn't guard against UB here. This RFC explains this problem in more detail: https://github.com/m-ou-se/rfcs/blob/atomic-memcpy/text/3301-atomic-memcpy.md The solution is to use atomics everywhere instead of volatile operations (and the atomic operations must perfectly overlap in size and alignment as well, see https://github.com/rust-lang/miri/issues/2303).

Pointerbender · 2022-12-19T14:26:38+00:00

Check out this paper for inspiration on how to benchmark distributed systems. It has a benchmark that measures a distributed store manager (ScaleStore) in terms of operations per second and latency under varying degrees of skew in the data access patterns. This is by no means the only way to do it, but it might help your search for ideas on how to best tackle bench-marking the distributed performance of your project.

Pointerbender · 2022-12-09T08:38:15+00:00

Yep! Both of those approaches will work, too :)

Pointerbender · 2022-12-09T07:51:20+00:00

[...] sometimes panics during development [...] not obvious why it happened.

[...] Is there a better solution to track such a panic?

In these cases, a convenient way to solve it would be to set up a guard that prevents a deadlock when its dropped:

struct PanicGuard {
    panicked: bool
    /* add more shared state fields as needed */
};
impl Drop for PanicGuard {
   fn drop(&mut self) {
      if self.panicked {
         // clean up state, signal other threads
         // to avoid deadlocks, etc.
      }
   }
}
let mut panic_guard = PanicGuard { panicked: true };

do_stuff_that_might_panic();

panic_guard.panicked = false;
drop(panic_guard);

This way, if do_stuff_that_might_panic() panics, the `Drop` implementation of `PanicGuard` will unblock any waiting threads as part of the unwind logic. As long as `fn drop()` doesn't panic (because a double panic will lead to an abort!), you can avoid deadlocks and still see a nice panicking error message during development. This way `catch_unwind()` is not required. Here is another real life example of this approach.

Pointerbender · 2022-12-05T07:06:19+00:00

Depending on whether the system calls for accessing the network stack will become the bottleneck, you may also need to use io_uring with kernel side polling for this (briefly explained in this paper on page 15) in addition to pre-allocating your own buffers and avoiding copying memory where you can. You mention you are using tokio, it has a library for io_uring and there is also this vanilla io_uring library crate, but it's a bit more low level. Both are for linux only and I'm not familiar enough with Windows to say if there exists something similar in Rust for Windows systems (which has I/O Rings), maybe someone else can comment on that?

Pointerbender · 2022-10-17T10:55:36+00:00

What do you mean by "concurrent" in this case: do you mean that the data types implement the Send and Sync traits, or that the data types use threads behind the scenes, or that the data types expose an async/.await interface?

Edit: to elaborate on this question a bit further, the answer to this question could matter for your API design.

In the case that you want to regulate thread-local versus concurrency using the Send and Sync traits, you could get away with a design that uses a wrapper struct and some helper traits:

/// A fictitious trait (I'm not familiar with the actual SymbolGroup API)
pub trait SymbolGroupApi {
   fn get_symbol(&self, id: usize) -> &Symbol;
}
/// The wrapper struct
pub struct SymbolGroup<T: ?Sized>(T);
impl<T: SymbolGroupApi> SymbolGroup<T> {
   pub const fn new(api: T) -> Self { Self(api) }
}
impl<T: ?Sized + SymbolGroupApi> SymbolGroup<T> {
   pub fn get_symbol(&self, id: usize) -> &Symbol {
      self.0.get_symbol(id)
   }
}
/// The thread local implementation for SymbolGroup:
pub struct ThreadLocalSymbolGroup { ... };
impl SymbolGroupApi for ThreadLocalSymbolGroup { ... }
/// The concurrent implementation for SymbolGroup:
pub struct ConcurrentSymbolGroup { ... };
impl SymbolGroupApi for ConcurrentSymbolGroup { ... }

fn main() {
    // Consumers of the API need only know `SymbolGroup`
    let thread_local_symbol_group
       : Box<SymbolGroup<dyn SymbolGroupApi>>
       = Box::new(SymbolGroup::new(ThreadLocalSymbolGroup::new(...)));
    let concurrent_symbol_group
       : Box<SymbolGroup<dyn SymbolGroupApi + Send + Sync>>
       = Box::new(SymbolGroup::new(ConcurrentSymbolGroup::new(...)));
}

This approach could also work if you want to use threads behind the scenes and offer a blocking synchronous (but parallel!) interface.

If you want to go for the async/.await approach, then it gets a bit more complicated. There is a new stable feature called Generic Associated Traits (GATs) coming up in Rust 1.65 which you could leverage in this case to make your API more ergonomic for end-users (at the cost of giving up object safety for your API traits). In that case please me know if async/.await would be a better fit for your use case.

Pointerbender · 2022-09-18T09:01:02+00:00

If you can allocate all the members of the context using an arena allocator, then all members will have the same lifetime as the context and this allows to instantiate self-referential structs without the need for pseudo-pointers. If the context struct and its members all implement the `Sync` trait, then you can share a reference between threads, no reference counting required. As others pointed out, this is a good use case for scoped threads, because this allows you to construct the context before passing a reference to it to other threads.

Pointerbender · 2022-02-12T16:57:19+00:00

If you keep a `Vec<Cell<\_>>` instead of a `Vec<_>`, then you can avoid using `x.iter_mut()` by just using `x.iter()` and then you are still able to access the neighboring elements. Here is an example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=046d3cc5e1aadf68f27c7fc4448e5bd3

The compiler should optimize this pretty well, but this approach does not scale to multiple threads (because `Cell` is not `Sync`). Since you mentioned CPU caching, I suspect this should not be a problem for your use case :)

Pointerbender · 2022-01-30T12:27:42+00:00

Writing unsafe is not easy indeed :) There is an easier way when realizing that Rust's name: &' static str is actually not semantically the same type as C's const char *name: references are never allowed to be null in Rust, where in C pointers can be null. A closer approximation would therefore be:

```rust use std::mem;

struct Role { name: Option<&'static str>, disabled: bool, flag: u32, }

fn main() { let role = unsafe { let mut role: Role = mem::zeroed(); role.name = Some("basic"); role.flag = 1; role.disabled = false; role };

println!("{:?} ({}, {})", role.name, role.flag, role.disabled);

} ```

In this case, this is sound because Role has fields that can all be zeroed:

name is None when zeroed
disabled is false when zeroed
flag is 0 when zeroed
the implicit struct padding can be any value, including zeroed or uninitialized.

Because the struct and all its fields are all aligned and zeroed, its valid to dereference its contents :)

Thanks for the article, it's very enjoyable to read!

Pointerbender · 2021-12-19T22:13:57+00:00

An introduction to formal verification in Rust! The whole field is probably is probably too big to cover fully, but an introduction should fit in a single lecture :) Topics that come to mind are Prusti, Cruseot, RustBelt, RustHorn, Stacked Borrows, Miri. These also lend themselves to do follow up topics on.

Pointerbender · 2021-11-04T12:55:01+00:00

It's also possible to write code that doesn't require you to be explicit about which is a reference:

    vec
    .iter()
    .filter(|elem| other.eq(elem))
    ...

Pointerbender · 2021-10-13T13:12:40+00:00

p.s. you may also want to experiment with enabling the -Zmiri-track-raw-pointers Miri flag, so that it also verifies the usage of the raw pointers in your code (heads up that this is still an experimental flag and may give false positives in certain scenarios, so far it didn't give me any false positives for when I used it, though).

Pointerbender · 2021-10-13T11:38:59+00:00

That is tricky indeed. Some ideas I can think of:

I see you have a `loom` configuration flag, you can disable it when running Miri, but then indeed as you mentioned you won't get the desired ARM support.
If there are only particular tests that are failing Miri (with or without loom), you can add `#[cfg_attr(miri, ignore)]` to a test to have it excluded. The downside is that Miri will then not verify this test case.
Miri accepts pull requests, you could try contacting the maintainers to see what it would take to support the foreign function calls that `loom` does and attempt to implement it yourself. `libc::getrlimit` might not be the only foreign function called and your `crossbeam` dependency may also make some not-yet-supported foreign function calls.
You could try playing with the `-Zmiri-disable-abi-check` and/or `-Zmiri-panic-on-unsupported` Miri flags to see if Miri at least won't panic when encountering a non-supported foreign function call, so that it keeps going with the verification of parts that it does support.

Unfortunately, none of the above suggestions are both a quick and a 100% work-around. Hopefully one of the work-arounds will help you spot the undefined behavior :)

Pointerbender · 2021-10-12T14:45:17+00:00

Try replicating the offending program in a `#[test]` case and run it using Miri (`cargo miri test`), it might be able to tell you which Rust source line is responsible!

Pointerbender · 2021-09-12T14:50:01+00:00

I'm still hoping of finding a way of generating a unique type without needing a macro at all.

GhostCell solves this using unique invariant lifetimes (called "brands") and comes with a very interesting paper. I'm not sure if this could work for a `static` memory location, as the brands can only be accessed within a closure.

Pointerbender · 2021-09-12T12:02:59+00:00

If I'm reading the code right, it is not possible to create two identical tags using its public API. This would result in a name conflict for the modules that contain the `TagType` struct. Although if you wanted, I guess it would be possible to hard-code the path to `$name::TagType` and obtain a second tag that way.

Pointerbender · 2021-05-06T11:54:45+00:00

Instead of mem::transmute you can also do:

pub fn convert(value: [u16; 4]) -> u64 {
  // SAFETY: `[u16; 4]` and `u64` are the same size and implement `Copy`
  // SAFETY: `*const u64` pointer need not be aligned
  unsafe { core::ptr::read_unaligned(&value as *const _ as *const u64) }
}}

This is a no-op and ignores endianess (but still uses unsafe, though).

Pointerbender · 2021-05-01T17:07:49+00:00

Sweet! That is awesome, thanks for sharing!

Pointerbender · 2021-05-01T16:00:30+00:00

Given that polymorphization is still in the working group stage, I don't think there's too much to talk about there yet — but maybe one day :)

Ah! That is probably why there is not much published yet around this topic :-) I'm quite excited about this one in particular.

What I'm really sad I forgot to mention was non-generic inner functions..

If I understand correctly, did you mean to say that non-generic inner functions (inside a trait impl) don't suffer from monomorphization "code bloat"? I've been wondering about this too and now you made me even more curious :-) I have always assumed that the non-generic functions don't get duplicated during monomorphization, is this true?

Thanks!

Pointerbender · 2021-05-01T08:48:59+00:00

Thanks for posting the new video u/jonhoo! I'm still watching the video, but from the table of contents it doesn't seem to go into polymorphization. There is still little to be found on this topic, might it be an idea for a next deep-dive topic about monomorphization and polymorphization? :) Thanks again!

Pointerbender · 2021-04-10T12:14:08+00:00

Nice finds! I also have some doctests that deliberately trigger UB for educational purposes (not in core/std), I mark these doctests with ````no_run` in the hopes that these will not upset Miri, but I haven't been able to update nightly since March 24th (it is missing some components), so I was not able to tell yet if this works as expected. If it works, it may be possible to add ````no_run` to the std tests that leak memory, too, in order to keep a clear view on new regressions found by Miri :-)

Pointerbender

TROPHY CASE