Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Panic when trying to remove a node #21

Closed
mmmries opened this issue Aug 30, 2024 · 6 comments
Closed

Panic when trying to remove a node #21

mmmries opened this issue Aug 30, 2024 · 6 comments

Comments

@mmmries
Copy link

mmmries commented Aug 30, 2024 •
edited
Loading

I recently started using this library in a work project (thank you for making awesome open source ❤️ 💛 💙 💚 💜)

I got a few occurences of panics that happened in production and after some digging and attempted to reproduce locally I have come up with a minimal reproducible.

#[test]
fn collision_panic() {
    let mut set = SetU64::new();
    set.remove(90);
    set.insert(158);
    set.remove(90);
    set.insert(159);
    set.remove(90);
    set.insert(160);
    set.remove(90);
    set.insert(161);
    set.remove(90);
    set.insert(162);
    set.remove(90);
    set.insert(163);
    set.remove(90);
    set.insert(164);
    set.remove(90);
    set.insert(165);
    set.remove(90);
    set.insert(166);
    set.remove(90);
    set.insert(167);
    set.remove(90);
    set.insert(168);
    set.remove(90);
    set.insert(169);
    set.remove(90);
    set.insert(170);
    set.remove(90);
    set.insert(171);
    set.remove(90);
    set.insert(172);
    set.remove(90);
    set.insert(173);
    set.remove(151);
    set.remove(152);
    set.remove(153);
    set.remove(154);
    set.remove(155);
    set.remove(156);
    set.remove(157);
    set.remove(158);
    set.remove(159);
    set.remove(160);
    set.remove(161);
    set.remove(162);
    set.remove(163);
    set.remove(164);
    set.remove(165);
    set.remove(166);
    set.remove(167);
    set.remove(168);
    set.remove(169);
    set.remove(170);
    set.remove(171);
    set.remove(172);
    set.remove(173);
    set.remove(174);
    set.remove(175);
    set.remove(176);
    set.remove(177);
    set.remove(178);
    set.remove(179);
    set.remove(180);
    set.insert(90);
    set.remove(90);
    set.insert(85);
    set.insert(86);
    set.remove(181);
    set.remove(85);
    set.insert(182);
    set.remove(182);
    set.insert(86);
    set.remove(86);
    set.insert(10);
    set.remove(208);
    set.insert(209);
    set.remove(10);
    set.insert(8);
    set.remove(209);
    set.insert(210);
    set.remove(8);
    set.insert(211);
    set.remove(210);
    set.insert(209);
    set.remove(209);
    set.insert(208);
    set.remove(211);
    set.insert(8);
    set.remove(8);
    set.insert(5);
    set.remove(208);
    set.insert(207);
    set.remove(5);
    set.insert(1);
    set.remove(207);
    set.insert(212);
    set.remove(1);
    set.insert(0);
    set.remove(212);
    set.insert(213);
    set.remove(0);
    set.remove(213);
    set.insert(212);
    set.remove(212);
    set.insert(207);
    set.remove(207);
    set.insert(206);
    set.remove(206);
    set.insert(214);
    set.remove(214);
    set.insert(215);
    set.remove(215);
    set.insert(214);
    set.remove(214);
    set.insert(206);
    set.remove(206);
    set.insert(205);
    set.remove(205);
    set.insert(216);
    set.remove(216);
    set.insert(217);
    set.remove(217);
    set.insert(216);
    set.remove(216);
    set.insert(205);
    set.remove(205);
    set.insert(204);
    set.remove(204);
    set.insert(218);
    set.remove(218);
    set.insert(219);
    set.remove(219);
    set.insert(218);
    set.remove(218);
    set.insert(204);
    set.remove(204);
    set.insert(203);
    set.remove(203);
    set.insert(220);
    set.remove(220);
    set.insert(221);
    set.remove(221);
    set.insert(220);
    set.remove(220);
    set.insert(203);
    set.remove(203);
    set.insert(202);
    set.remove(202);
    set.insert(202);
    set.remove(202);
    set.insert(201);
    set.remove(201);
    set.insert(224);
    set.remove(224);
    set.insert(225);
    set.remove(225);
    set.insert(224);
    set.remove(224);
    set.insert(201);
    set.remove(201);
    set.insert(199);
    set.remove(199);
    set.insert(228);
    set.remove(228);
    set.insert(229);
    set.remove(229);
    set.insert(228);
    set.remove(228);
    set.remove(230);
    set.insert(198);
    set.remove(198);
    set.insert(197);
    set.remove(197);
    set.insert(187);
    set.remove(187);
    set.insert(186);
    set.remove(186);
    set.insert(258);
    set.remove(258);
    set.insert(61);
    set.remove(61);
    set.remove(262);
    set.insert(59);
    set.remove(61);
    set.insert(265);
    set.debug_me("set");
    set.remove(61);
}

On the last operation I get an error like this:

thread 'dag::tests::test_tiny_set' panicked at /Users/mries/code/peg/native/dag/vendor/tinyset/src/setu64.rs:2289:5:
bug: we should have had space in [265, 59] for 61
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

I'm continuing to look around in the code to understand why this happening, but I'm relatively new to rust. Hopefully this reproducible is useful to identify the root cause.
@droundy
Copy link
Owner

droundy commented Aug 30, 2024 via email

@mmmries
Copy link
Author

mmmries commented Aug 31, 2024

I made a bit of progress on this problem today. I was able to reduce the size of the reproducible, but it's pretty large. I was also able to determine that when this panic occurs, the SetU64 is using the Internal::Big structure and I got a debug output just before the final remove(61) that causes the panic. This is generated with the following line: set.debug_me("set")

set: big Sbeginning { sz: 2, cap: 2, bits: 16736232708690900706 }
    [265, 59]
     >>>[1, 1]

@mmmries
Copy link
Author

mmmries commented Sep 2, 2024

Looking at the debug output a bit more closely, it looks like we have a fully populated array of set entries. When we call set.remove(61) it's going to check 61 % 2 => 1 which contains the entry 59, and then it will scan through the rest of the array looking for an empty node or the number 61. But because the array is fully populated at this point, it doesn't find either of those things and instead reaches the panic.

Is a fully populate array supposed to be a valid state here? It seems to me like we should just be returning false rather than doing a panic since the 61 is not part of the set at all?

@mmmries
Copy link
Author

mmmries commented Sep 2, 2024

I was able to narrow this down even further. This only happens after the set transitions to using a "Big" internal representation and if you try to remove values where the initial guess for the location is not at the beginning of the array. Here's another example:

Most of the intial inserts/remove operations are just to get the set into the "Big" state. Then we fill up the two slots and try to remove something. If you do remove(1) it completes successfully, if you do remove(2) it will panic.

#[test]
fn collision_panic() {
    let mut set = SetU64::new();
    set.remove(90);
    set.insert(158);
    set.remove(90);
    set.insert(159);
    set.remove(90);
    set.insert(160);
    set.remove(90);
    set.insert(161);
    set.remove(90);
    set.insert(162);
    set.remove(90);
    set.insert(163);
    set.remove(90);
    set.insert(164);
    set.remove(90);
    set.insert(165);
    set.remove(90);
    set.insert(166);
    set.remove(90);
    set.insert(167);
    set.remove(90);
    set.insert(168);
    set.remove(90);
    set.insert(169);
    set.remove(90);
    set.insert(170);
    set.remove(90);
    set.insert(171);
    set.remove(90);
    set.insert(172);
    set.remove(90);
    set.insert(173);
    set.remove(151);
    set.remove(152);
    set.remove(153);
    set.remove(154);
    set.remove(155);
    set.remove(156);
    set.remove(157);
    set.remove(158);
    set.remove(159);
    set.remove(160);
    set.remove(161);
    set.remove(162);
    set.remove(163);
    set.remove(164);
    set.remove(165);
    set.remove(166);
    set.remove(167);
    set.remove(168);
    set.remove(169);
    set.remove(170);
    set.remove(171);
    set.remove(172);
    set.remove(173);
    set.remove(174);
    set.remove(175);
    set.remove(176);
    set.remove(177);
    set.remove(178);
    set.remove(179);
    set.remove(180);
    set.insert(90);
    set.remove(90);
    set.insert(85);
    set.insert(86);
    set.remove(181);
    set.remove(85);
    set.insert(182);
    set.remove(182);
    set.insert(86);
    set.remove(86);
    set.insert(10);
    set.remove(208);
    set.insert(209);
    set.remove(10);
    set.insert(8);
    set.remove(209);
    set.insert(210);
    set.remove(8);
    set.insert(211);
    set.remove(210);
    set.insert(209);
    set.remove(209);
    set.insert(208);
    set.remove(211);
    set.insert(8);
    set.remove(8);
    set.insert(5);
    set.remove(208);
    set.insert(207);
    set.remove(5);
    set.insert(1);
    set.remove(207);
    set.insert(212);
    set.remove(1);
    set.insert(0);
    set.remove(212);
    set.insert(213);
    set.remove(0);
    set.remove(213);
    set.insert(212);
    set.remove(212);
    set.insert(207);
    set.remove(207);
    set.insert(206);
    set.remove(206);
    set.insert(214);
    set.remove(214);
    set.insert(215);
    set.remove(215);
    set.insert(214);
    set.remove(214);
    set.insert(206);
    set.remove(206);
    set.insert(205);
    set.remove(205);
    set.insert(216);
    set.remove(216);
    set.insert(217);
    set.remove(217);
    set.insert(216);
    set.remove(216);
    set.insert(205);
    set.remove(205);
    set.insert(204);
    set.remove(204);
    set.insert(218);
    set.remove(218);
    set.insert(219);
    set.remove(219);
    set.insert(218);
    set.remove(218);
    set.insert(204);
    set.remove(204);
    set.insert(203);
    set.remove(203);
    set.insert(220);
    set.remove(220);
    set.insert(221);
    set.remove(221);
    set.insert(220);
    set.remove(220);
    set.insert(203);
    set.remove(203);
    set.insert(202);
    set.remove(202);
    set.insert(202);
    set.remove(202);
    set.insert(201);
    set.remove(201);
    set.insert(224);
    set.remove(224);
    set.insert(225);
    set.remove(225);
    set.insert(224);
    set.remove(224);
    set.insert(201);
    set.remove(201);
    set.insert(199);
    set.remove(199);
    set.insert(228);
    set.remove(228);
    set.insert(229);
    set.remove(229);
    set.insert(228);
    set.remove(228);
    set.remove(230);
    set.insert(198);
    set.remove(198);
    set.insert(197);
    set.remove(197);
    set.insert(187);
    set.remove(187);
    set.insert(186);
    set.remove(186);
    set.debug_me("dense?");
    set.insert(258);
    set.debug_me("big?");
    set.insert(260);
    set.debug_me("full?");
    set.remove(2);
}

@droundy droundy closed this as completed in cac7748 Sep 7, 2024
@droundy
Copy link
Owner

droundy commented Sep 7, 2024

Thanks so much for looking into this, it was really helpful!

@mmmries
Copy link
Author

mmmries commented Sep 7, 2024

Thanks @droundy glad our use-case could help to harden the project. We're very grateful for your open source work as it made our project a lot more efficient to represent directed edges as tinysets.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@mmmries @droundy