Crash after interned reuse

[puuuuh]

    #[test]
    fn repro() {
        #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
        struct BadHash(String);

        impl std::hash::Hash for BadHash {
            fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
                0.hash(state);
            }
        }

        #[salsa::input]
        struct Input {
            field: String
        }

        #[salsa::interned]
        struct Interned {
            field: String
        }

        #[salsa::tracked]
        struct Output<'db> {
            pub id: String,

            #[tracked]
            field: Interned<'db>
        }


        #[salsa::tracked]
        fn outer_query<'db>(db: &'db dyn Database, input: Input) -> Vec<Output<'db>> {
            let res: Vec<Output<'_>> = inner_query(db, input)
                .into_iter()
                .map(|i| Output::new(db, input.field(db), i))
                .collect();
            sleep(Duration::from_millis(500));
            db.unwind_if_revision_cancelled();
            for r in &res {
                r.id(db);
                r.field(db);
            }
            res
        }

        #[salsa::tracked]
        fn inner_query<'db>(db: &'db dyn Database, input: Input) -> Vec<Interned<'db>> {
            let res: Vec<Interned<'db>> = (0..10).map(|i| {
                Interned::new(db, format!("{}_{i}", input.field(db)))
            }).collect();
            res
        }


        tracing_subscriber::fmt()
            .with_max_level(Level::ERROR)
            .with_ansi(false)
            .with_writer(std::io::stderr)
            .init();
        let mut threads = vec![];
        let mut db = salsa::DatabaseImpl::default();
        let i1 = Input::new(&db, "i1".to_owned());
        let i2 = Input::new(&db, "i2".to_owned());
        let i3 = Input::new(&db, "i3".to_owned());
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i1);
        }));
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i2);
        }));
        sleep(Duration::from_millis(1000));
        db.synthetic_write(Durability::HIGH);
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i2);
        }));
        sleep(Duration::from_millis(250));
        db.synthetic_write(Durability::HIGH);
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i2);
        }));
        sleep(Duration::from_millis(250));
        db.synthetic_write(Durability::HIGH);
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i3);
        }));
        sleep(Duration::from_millis(250));
        db.synthetic_write(Durability::HIGH);
        let d = db.clone();
        threads.push(spawn(move || {
            outer_query(&d, i1);
        }));
        sleep(Duration::from_millis(0));
        db.synthetic_write(Durability::HIGH);
        for t in threads {
            t.join();
        }
        for t in outer_query(&db, i1) {
            t.field(&db).field(&db);
        }
    }

Repro is a little bit messy, ill try to reduce it more
Bug introduced in 15c28cd

[MichaReiser]

CC: @ibraheemdev

[puuuuh]

    #[test]
    fn repro() {
        #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
        struct BadHash(String);

        impl std::hash::Hash for BadHash {
            fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
                0.hash(state);
            }
        }

        #[salsa::input]
        struct Input {
            field: String
        }

        #[salsa::interned]
        struct Interned {
            field: String
        }

        #[salsa::tracked]
        struct Output<'db> {
            pub id: String,

            #[tracked]
            field: Interned<'db>
        }


        #[salsa::tracked]
        fn outer_query<'db>(db: &'db dyn Database, input: Input) -> Vec<Output<'db>> {
            let res: Vec<Output<'_>> = inner_query(db, input)
                .into_iter()
                .map(|i| Output::new(db, input.field(db), i))
                .collect();
            res
        }

        #[salsa::tracked]
        fn inner_query<'db>(db: &'db dyn Database, input: Input) -> Vec<Interned<'db>> {
            let res: Vec<Interned<'db>> = (0..10).map(|i| {
                Interned::new(db, format!("{}_{i}", input.field(db)))
            }).collect();
            res
        }


        tracing_subscriber::fmt()
            .with_max_level(Level::DEBUG)
            .with_ansi(false)
            .with_writer(std::io::stderr)
            .init();
        let mut db = DatabaseImpl::default();
        let i1 = Input::new(&db, "i1".to_owned());
        let i2 = Input::new(&db, "i2".to_owned());
        let i3 = Input::new(&db, "i3".to_owned());

        outer_query(&db, i1);
        outer_query(&db, i2);
        db.synthetic_write(Durability::HIGH);

        outer_query(&db, i2);
        db.synthetic_write(Durability::HIGH);

        outer_query(&db, i2);
        db.synthetic_write(Durability::HIGH);

        outer_query(&db, i3);
        db.synthetic_write(Durability::HIGH);
        outer_query(&db, i3);

        for t in outer_query(&db, i1) {
            assert!(t.field(&db).field(&db).starts_with("i1_"));
        }
    }

The same issue without unwinding
Seems like tracked function not being invalidated after GC on interned values?

[ibraheemdev]

This is interesting. When we create a new interned value, we record a dependency with Revision::start(). This worked previously because any new interned values that are created in a subsequent run of a query must have been as a result of some input changing, in which case we would also record a dependency on that input. However, it is now possible that we are recreating a value that was previously interned without any inputs having changed, so while the memo has not "changed" the IDs have, so the memo cannot be discarded. In the above test case the inner_query is re-executed and the values are re-interned, but no new inputs were read since the previous execution, so the new memo is discarded.

The easy fix is just to use current_revision but I'm not sure if that is correct.

[MichaReiser]

is re-executed and the values are re-interned, but no new inputs were read since the previous execution, so the new memo is discarded.

What's the reason for discarding the memo? Isn't the result of inner_query different due to the id changes?

The easy fix is just to use current_revision but I'm not sure if that is correct.

That's undesired because it has a propagating effect on all dependents. But I can't say without a better understanding of the error

[ibraheemdev]

I don't believe we check the value of the memo, we discard it based on changed_at (which is equal to R1 in this case despite the new interned value being created after GC). Maybe "discard" isn't entirely correct, but at least the outer query is not re-executed so the old inner memo is reused. In some sense this is another case of GC being "impure", triggering changes without the inputs having changed.

[puuuuh]

Why we even execute inner_query, if its inputs the same as before?

[puuuuh]

Just checked with Durability::HIGH in inner_query and Durability::LOW in outer_query and synthetic_write

[ibraheemdev]

Why we even execute inner_query, if its inputs the same as before?

Because one of the interned dependencies was reused, so maybe_changed_after returns true. It is correct to re-execute it, the problem is that we don't actually end up using the new memo.

[puuuuh]

mod tests {
    use salsa::{tracked, Database, DatabaseImpl, Durability};
    use tracing::Level;

    #[test]
    fn repro() {
        #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
        struct BadHash(String);

        impl std::hash::Hash for BadHash {
            fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
                0.hash(state);
            }
        }

        #[salsa::input(debug)]
        struct Input {
            field: String
        }

        #[salsa::interned(debug)]
        struct Interned {
            field: String
        }

        #[salsa::tracked(debug)]
        struct Output<'db> {
            pub id: String,

            #[tracked]
            field: Interned<'db>
        }


        #[salsa::tracked]
        fn outer_query<'db>(db: &'db dyn Database, non_durable_input: Input, input: Input) -> Vec<Output<'db>> {
            let res: Vec<Output<'_>> = inner_query(db, input)
                .into_iter()
                .map(|i| Output::new(db, input.field(db), i))
                .collect();
            res
        }

        #[salsa::tracked ]
        fn intern_low_durable<'db>(db: &'db dyn Database, input: Input) -> Vec<Interned<'db>> {
            input.field(db);
            (0..10).map(|i| {
                Interned::new(db, format!("i1_{i}"))
            }).collect()
        }

        #[salsa::tracked]
        fn inner_query<'db>(db: &'db dyn Database, input: Input) -> Vec<Interned<'db>> {
            let res: Vec<Interned<'db>> = (0..10).map(|i| {
                Interned::new(db, format!("{}_{i}", input.field(db)))
            }).collect();
            res
        }


        tracing_subscriber::fmt()
            .with_max_level(Level::INFO)
            .with_ansi(false)
            .with_writer(std::io::stderr)
            .init();
        let mut db = DatabaseImpl::default();
        let i1 = Input::builder("i1".to_owned()).durability(Durability::HIGH).new(&db);
        let i2 = Input::builder("i2".to_owned()).durability(Durability::LOW).new(&db);
        let i3 = Input::builder("i3".to_owned()).durability(Durability::LOW).new(&db);
        let i4 = Input::builder("i4".to_owned()).durability(Durability::LOW).new(&db);
        let i5 = Input::builder("i5".to_owned()).durability(Durability::LOW).new(&db);
        let i6 = Input::builder("i6".to_owned()).durability(Durability::LOW).new(&db);
        let i7 = Input::builder("i7".to_owned()).durability(Durability::LOW).new(&db);

        let a = intern_low_durable(&db, i7);
        let b = outer_query(&db, i7, i1);

        outer_query(&db, i7, i2);
        db.synthetic_write(Durability::LOW);

        outer_query(&db, i7, i3);
        db.synthetic_write(Durability::LOW);

        outer_query(&db, i7, i4);
        db.synthetic_write(Durability::LOW);

        outer_query(&db, i7, i5);
        db.synthetic_write(Durability::LOW);
        outer_query(&db, i7, i6);
        for a in outer_query(&db, i7, i1) {
            dbg!(a.field(&db).field(&db));
        }
    }
}

In this case it wont even execute outer_query in for loop

[puuuuh]

And this one can't be fixed by current_revision in changed_at

[MichaReiser]

I don't believe we check the value of the memo, we discard it based on changed_at (which is equal to R1 in this case despite the new interned value being created after GC). Maybe "discard" isn't entirely correct, but at least the outer query is not re-executed so the old inner memo is reused. In some sense this is another case of GC being "impure", triggering changes without the inputs having changed.

Oh I see. I was thinking you were talking about the similar logic in execute:

https://github.com/MichaReiser/salsa/blob/8d3455f0e6451c0dd6f88412db2aa9c49f41bc3f/src/function/backdate.rs#L34-L35

the backdating logic runs before the changed_at check in maybe_changed_after cold and we skip it because the results aren't equal.

I haven't looked at why the last case is failing but setting changed_at to the current revision when we reuse a slot seems reasonable.

[ibraheemdev]

And this one can't be fixed by current_revision in changed_at

Ah I think this one is a simpler bug, we have to remove the value from the LRU if the durability increases (we shouldn't be collecting high durability values).