erikd / vector-algorithms

Other
23 stars 15 forks source link

Fix out-of-bounds in Timsort #24

Closed Bodigrim closed 4 years ago

Bodigrim commented 4 years ago

It appears that Timsort implementation accesses memory out-of-bounds, as can be witnessed by enabling vector +unsafechecks flag: https://travis-ci.org/Bodigrim/vector-algorithms/jobs/618361005#log-container

The tricky part is that while the algorithm reads some memory garbage, the latter never makes way into the final result. That is why the bug remained unspotted for so long. In its essence mergeLo and mergeHi execute the following recursive function:

iter :: MVector s a -> Int -> a -> ST s ()
iter vec i vi
  | i < 0 = return ()
  | otherwise = do
    doSmthWith vi
    vi' <- unsafeRead vec (i - 1)
    iter vec (i - 1) vi'

As one can see, iter reads vec ! (-1), but never actually uses it, so the output remains correct. However, if you are unlucky, unsafeRead will trigger a memory access violation.


This PR is just a straightforward fix. I understand that it may lack some elegance, and I believe that in future Timsort implementation may benefit from more love. But at the moment I would appreciate a reasonably quick turnaround, because for certain inputs this bug causes a segfault in poly package, which may affect its downstream dependencies (CC @sdiehl @Multramate).

Bodigrim commented 4 years ago

Can we have it released on Hackage please?

erikd commented 4 years ago

Done!

Bodigrim commented 4 years ago

Huge thanks for quick responses!