orlp / slotmap

Slotmap data structure for Rust
zlib License
1.16k stars 70 forks source link

HopSlotMap segfaults when items are inserted and removed out of order #69

Closed ErikNatanael closed 3 years ago

ErikNatanael commented 3 years ago

HopSlotMap, not SlotMap or DenseSlotMap, segfaults on clear() or drain() when values have been inserted and removed out of order. Running the example below a few times give different kinds of segfault errors, most of them to do with double free. More info as comments in the MVC: https://github.com/ErikNatanael/slotmap_segfault

orlp commented 3 years ago

Well, that's embarrassing. I will investigate this in a bit and if valid fix and yank the affected versions.

orlp commented 3 years ago

I found the issue.

My freelist consists of contiguous blocks of slots. The metadata for such a contiguous block is stored entirely in the first element of the contiguous block, except that there is one member variable, other_end, that is maintained for both the first and last block, such that slots[first].other_end == last and slots[last].other_end == first. Note that if the contiguous block has size one that slots[i].other_end == i

This makes it possible with a bit of clever logic keep all this information this up to date and the blocks contiguous. The problem arises because the drain iterator assumes that after removing slot[i] that slot[i+1].other_end still points to the correct location, if slot[i+1] is vacant. However, in the event that slot[i+1] is a singleton vacant slot, after removing slot[i], in fact slot[i+1].other_end == i. Oops!

Unfortunately this affects all versions 0.3+, so I'll be yanking them. Looking at my usage charts it seems people pretty much exclusively use 0.4 and 1.0+, so I'll fix this in 0.4.1 and 1.0.4.

orlp commented 3 years ago

Done. Fixed in 1.0.4 and 0.4.1.

grovesNL commented 3 years ago

Would it be possible to backport this to a new release of 0.3? We use the yanked 0.3 release in older versions of glow https://github.com/grovesNL/glow/issues/179 We could workaround it in glow by updating all older releases of glow, but it would be nice if we could fix it here

orlp commented 3 years ago

Would it be possible to backport this to a new release of 0.3? We use the yanked 0.3 release in older versions of glow grovesNL/glow#179 We could workaround it in glow by updating all older releases of glow, but it would be nice if we could fix it here

I didn't realize slotmap 0.3 had active users, I can backport it yes, after 1.0.5, since a vulnerability to HopSlotMap::retain was found (with the same fundamental cause as this one, which I missed) by fuzzing. I'll unyank 0.3 for these couple of hours to ease the transition. I apologize for the inconvenience.

grovesNL commented 3 years ago

@orlp awesome, thank you! No problem – I wouldn’t have expected active projects to depend on older versions of glow either :)

orlp commented 3 years ago

@grovesNL 1.0.5 is released and the fixes in 1.0.4 and 1.0.5 are backported to 0.3.1 and 0.4.2. Vulnerable old versions are now again yanked.

grovesNL commented 3 years ago

Great, thanks again!