typst / ecow

Compact, clone-on-write vector and string.
Apache License 2.0
208 stars 16 forks source link

Fix `EcoVec`'s `Send` and `Sync` bounds #11

Closed CosmicHorrorDev closed 1 year ago

CosmicHorrorDev commented 1 year ago

Last PR I can do for the day (got a lot of IRL stuff today), but it's another soundness fix

This fixes EcoVec's Send and Sync bounds to match the standard library's Arc

Arc-like constructs need both Send and Sync on the inner type to allow for Send or Sync. Without this it's trivial to violate the inner type's bound

E.g. a type can be Send + !Sync, but that would allow you to create two Arcs on the same thread and then pass one of the Arcs to another thread. From there you have a reference to the type from multiple threads even though it's !Sync. A simple example program that makes miri angry

use std::cell::Cell;

use ecow::eco_vec;

fn main() {
    let send_not_sync = Cell::new("foo");
    let one = eco_vec![send_not_sync];
    let another = one.clone();

    std::thread::spawn(move || loop {
        another[0].set("bar");
        another[0].set("foo");
    });

    // đŸ˜±
    loop {
        println!("{}", one[0].get());
    }
}
$ cargo +nightly miri run
// -- 8< -- build output -- 8< --
error: Undefined Behavior: Data race detected between (1) Read on thread `main` and (2) Write on thread `<unnamed>` at alloc1739+0x18. (2) just happened here
   --> /.../rustlib/src/rust/library/core/src/cell.rs:413:31
    |
413 |         mem::replace(unsafe { &mut *self.value.get() }, val)
    |                               ^^^^^^^^^^^^^^^^^^^^^^ Data race detected between (1) Read on thread `main` and (2) Write on thread `<unnamed>` at alloc1739+0x18. (2) just happened here
    |
help: and (1) occurred earlier here
   --> src/main.rs:17:24
    |
17  |         println!("{}", one[0].get());
    |                        ^^^^^^^^^^^^
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE (of the first span):
    = note: inside `std::cell::Cell::<&str>::replace` at /.../rustlib/src/rust/library/core/src/cell.rs:413:31: 413:53
    = note: inside `std::cell::Cell::<&str>::set` at /.../rustlib/src/rust/library/core/src/cell.rs:363:19: 363:36
note: inside closure
   --> src/main.rs:11:9
    |
11  |         another[0].set("bar");
    |         ^^^^^^^^^^^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error

For even more fun you can change one of the strings that get swapped to something really big and then you can get fun runtime issues.

$ # --release optimizes stuff away
$ # --show-all prevents arbitrary bytes from messing with my terminal session
$ cargo run | bat --show-all
// -- 8< -- searching for "home" -- 8< --
9962   │ foo#/rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/std/src/io/mod.rsfailed·to·write·whole·bufferfor
       │ matter·errorfatal·runtime·error:·␊
9963   │ thread·result·panicked·on·dropassertion·failed:·self.is_allocated()/.../ecow/s
       │ rc/vec.rsassertion·failed:·self.is_unique()assertion·failed:·target·>·
self.capacity()␀␀␀␀␀␀␀␀␀attempt·to·add
       │ ·with·overflow␀␀␀␀attempt·to·subtract·with·overflow␀␀␀␀␀%                                                   26;46m␀␀␀␀␀␀␀␀␀␀attempt·to·multiply·with·overflowreference
       │ ·count·overflow␀␀␀␀␀␀␀,O\xFC\xFFhO\xFC\xFFjO\xFC\xFFlO\xFC\xFFnO\xFC\xFFthere·is·no·such·thing·as·a·relaxed·
       │ fence␀␀␀/rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/core/src/sync/atomic.rs␀>P\xFC\xFFSP\xFC\xFF
       │ hP\xFC\xFF}P\xFC\xFF\x92P\xFC\xFFfailed·to·spawn·thread/rustc/fc594f15669680fa70d255faec3ca3fb507c3405/libra
       │ ry/std/src/thread/mod.rsthread·name·may·not·contain·interior·null·bytes␀␀\xA2e\xFC\xFF\xDAe\xFC\xFFie\xFC\xF
       │ F\x89e\xFC\xFF\xE2g\xFC\xFF\u{1a}h\xFC\xFF\xA9g\xFC\xFF\xC9g\xFC\xFFinternal·error:·entered·unreachable·code
       │ /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/std/src/io/error/repr_bitpacked.rs␀␀\xFEx\xFC\xFF\u{
       │ 12}y\xFC\xFF·y\xFC\xFF3y\xFC\xFF/.../Pro␊

(Being totally honest I'm just having fun seeing what wacky stuff can happen with Rust's UB. Sometimes I miss how cursed C programming can be)

laurmaedje commented 1 year ago

Thanks for the fix and thanks for spotting this! I copied this from Arc, but was apparently a bit too trigger-happy with my multi-cursor delete of the ?Sized bounds and stability attributes. But these kinds of things are exactly why I posted on reddit and waited with publishing to crates.io.

laurmaedje commented 1 year ago

Also, miri is absolutely awesome!

CosmicHorrorDev commented 1 year ago

Also, miri is absolutely awesome!

Can't be more true!