Repository navigation
Segfaults and "internal errors" when vector slice overflows #257
Description
Activity
Looks to me like the bug is here:
vector/Data/Vector/Internal/Check.hs
Lines 147 to 151 in 46110b9
Specifically,
i+m <= nis subject to integer overflow. Instead, something likem <= n - ishould be applied.Reacted by Ömer Sinan AğacanThis is great, how many ways can we get the slice wrong? :)
Surprisingly, bug reported here is pretty hard to hit this in a
slicefunction. The uncommon ways you can trigger it is by compiling without optimizations, eg. ghci (how this bug was reported) or by constructing a vector by manually allocating it.Reason for this is that if a vector is constructed from a stream, or any other way really, this rewrite rule will get triggered and
sliceCheckwill no longer get triggered!"slice/new [Vector]" forall i n p. slice i n (new p) = new (New.slice i n p)So, if you put something fun like this instead into
slice.hsfile:main = do let xs = [1, 2, 3, 4, 5] :: [Int] v = V.slice 1 (maxBound `div` 8) (V.fromList xs) print $ V.length v
You'll get another very nice issue:
$ stack exec -- ghc slice.hs -O1 && ./slice [1 of 1] Compiling Main ( slice.hs, slice.o ) [Optimisation flags changed] Linking slice ... slice: Out of memoryBut what is even greater consequence of this, is that too large of the size parameter to
slicecan cause it to fail or not, depending on how the vector was constructed!main = do let xs = [1, 2, 3, 4, 5] :: [Int] mySlice = V.slice 1 8 v <- do mv <- MV.new $ List.length xs M.mapM_ (uncurry (MV.write mv)) $ List.zip [0..] xs V.freeze mv print $ mySlice $ V.fromList xs print $ mySlice v
This results in:
$ stack exec -- ghc slice.hs -O1 && ./slice [1 of 1] Compiling Main ( slice.hs, slice.o ) [Optimisation flags changed] Linking slice ... [2,3,4,5] slice: ./Data/Vector/Generic.hs:396 (slice): invalid slice (1,8,5) CallStack (from HasCallStack): error, called at ./Data/Vector/Internal/Check.hs:87:5 in vector-0.12.0.3-LfvlcMFJAcY18uD1Y2O5Ig:Data.Vector.Internal.Check
I got a fix partially implemented for the original issue: WIP in https://github.com/haskell/vector/tree/lehins/257-fix-slice-overflow
The follow up problem I described has to do with
dropfrom bundle, which I still need some tests for and a proper fix.I guess a serious question we collectively should answer, which semantics should we keep?
slice 10 k [0..k] == [10..k]or
slice 10 k [0..k] == errorReason why I bring it up is because it seems the former might be more prevalent in the wild and some people might even rely on it. I am slightly leaning towards it, since it reduces number of partial functions and sort of follows
dropandtakephilosophy from stream:vector/Data/Vector/Fusion/Stream/Monadic.hs
Lines 313 to 318 in 1bb6b5d
- Perhaps I’m slow, but could you explain what you mean in terms of start and end coordinates and arrays?…On Wed, Jan 29, 2020 at 10:33 PM Alexey Kuleshevich < ***@***.***> wrote: I guess a serious question we collectively should answer, which semantics we should keep? slice 10 k [0..k] == [10..k] or slice 10 k [0..k] == error Reason why I bring it up is because it seems the former might be more prevalent in the wild and some people might even rely on it. I am slightly leaning towards it, since it reduces number of partial functions and sort of follows drop and take philosophy. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#257?email_source=notifications&email_token=AAABBQUZMABFGWA5ZECPSULRAJDA5A5CNFSM4IZ476A2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJSHUI#issuecomment-580068305>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABBQR4W6O35HO2WGJEPILRAJDA5ANCNFSM4IZ476AQ> .
- Do you meant should we return an empty slice vs throw an error? On Wed, Jan 29, 2020 at 10:58 PM Carter Schonwald < [email protected]> wrote:…Perhaps I’m slow, but could you explain what you mean in terms of start and end coordinates and arrays? On Wed, Jan 29, 2020 at 10:33 PM Alexey Kuleshevich < ***@***.***> wrote: > I guess a serious question we collectively should answer, which semantics > we should keep? > > slice 10 k [0..k] == [10..k] > > or > > slice 10 k [0..k] == error > > Reason why I bring it up is because it seems the former might be more > prevalent in the wild and some people might even rely on it. I am slightly > leaning towards it, since it reduces number of partial functions and sort > of follows drop and take philosophy. > > — > You are receiving this because you are subscribed to this thread. > Reply to this email directly, view it on GitHub > <#257?email_source=notifications&email_token=AAABBQUZMABFGWA5ZECPSULRAJDA5A5CNFSM4IZ476A2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJSHUI#issuecomment-580068305>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAABBQR4W6O35HO2WGJEPILRAJDA5ANCNFSM4IZ476AQ> > . >
For the slow here is what I suggest. (just kidding ;)
Make
slicea total function instead of a current mess of potential partiality:================================================== slice (List): [1,2,3,4,5] normal: [2,3,4] negative ix: [1,2] negative size: [] negative ix and size: [] too large ix: [] too large size: [3,4,5] too large ix size: [] ================================================== slice (Vector proposed): [1,2,3,4,5] normal: [2,3,4] negative ix: [1,2] negative size: [] negative ix and size: [] too large ix: [] too large size: [3,4,5] too large ix size: [] ================================================== slice (Vector.Boxed current - fused): [1,2,3,4,5] normal: [2,3,4] negative ix: [1,2] negative size: [] negative ix and size: [] too large ix: [] too large size: [3,4,5] too large ix size: [] ================================================== slice (Vector.Primitive current - fused): [1,2,3,4,5] normal: [2,3,4] negative ix: [1,2] negative size: Primitive.basicUnsafeNew: negative length: -2 negative ix and size: Primitive.basicUnsafeNew: negative length: -1 too large ix: [] too large size: [3,4,5] too large ix size: [] ================================================== slice (Vector current - unfused): [1,2,3,4,5] normal: [2,3,4] negative ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,2,5) negative size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,-2,5) negative ix and size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,-1,5) too large ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,2,5) too large size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,6,5) too large ix size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,6,5)Code to reproduce above output:
{-# LANGUAGE LambdaCase #-} module Main where import Control.Exception import Control.Monad as M import Data.List as List import qualified Data.Vector as V import qualified Data.Vector.Generic as VG import qualified Data.Vector.Primitive as VP sliceList :: Int -> Int -> [a] -> [a] sliceList i n xs = List.take n (List.drop i xs) sliceVectorProposed :: VG.Vector v a => Int -> Int -> v a -> v a sliceVectorProposed i n xs = VG.take n (VG.drop i xs) tryErrorPrint :: Show a => String -> a -> IO () tryErrorPrint prefix doSlice = do putStr prefix try (pure $! doSlice) >>= \case Left (ErrorCall err) -> putStrLn ('\n':err) Right result -> print result printSlices :: (Show a, Show b) => String -> (Int -> Int -> b -> a) -> b -> IO () printSlices name sliceWith xs = do putStrLn $ replicate 50 '=' putStrLn $ "slice (" ++ name ++ "): " ++ show xs putStrLn $ " normal: " ++ show (sliceWith 1 3 xs) tryErrorPrint " negative ix: " (sliceWith (-2) 2 xs) tryErrorPrint " negative size: " (sliceWith 2 (-2) xs) tryErrorPrint " negative ix and size: " (sliceWith (-2) (-1) xs) tryErrorPrint " too large ix: " (sliceWith 6 2 xs) tryErrorPrint " too large size: " (sliceWith 2 6 xs) tryErrorPrint " too large ix size: " (sliceWith 6 6 xs) main = do let xs = [1, 2, 3, 4, 5] :: [Int] printSlices "List" sliceList xs printSlices "Vector proposed" sliceVectorProposed $ V.fromList xs printSlices "Vector.Boxed current - fused" (\i n -> V.slice i n . V.fromList) xs printSlices "Vector.Primitive current - fused" (\i n -> VP.slice i n . VP.fromList) xs printSlices "Vector current - unfused" V.slice (V.fromList xs)Of course on the other end of the spectrum is to always throw an error on invalid indices, but I suspect in order to achieve that we'll have to break fusion on slicing. The benefit would be that we would get the behavior that a lot of folks expect (but don't always get), namely this one:
================================================== slice (Vector current - unfused): [1,2,3,4,5] normal: [2,3,4] negative ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,2,5) negative size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,-2,5) negative ix and size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,-1,5) too large ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,2,5) too large size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,6,5) too large ix size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,6,5)I am rarely in favor of partial functions, therefore I lean towards fixing the arguments to
slicefunctions so they don't fail. All this conversation applies to mutable variants as well, but naturally not for the streaming ones.- There’s two legs to this conversation around the semantics of a fix 1) what’s the best possible array slice api. I’ve some strong opinions on this I’ll write down in a day or so. Juggling a few other commitments 2) making sure users benefit from great optimization as much as possible. My stance is that if we find fusion tools hindering our intent, then we should think about ways to change ghc so we can make a better vector. I started some rudimentary experiments in December. But we should have those technical barriers we hit be turned into optimization tech challenges we collectively change our tools to address.…On Thu, Jan 30, 2020 at 9:49 AM Alexey Kuleshevich ***@***.***> wrote: Of course on the other end of the spectrum is to always throw an error on invalid indices, but I suspect in order to achieve that we'll have to break fusion on slicing. The benefit would be that we would get the behavior that a lot of folks expect (but don't always get), namely this one: ================================================== sliceList(Vector current - unfused): [1,2,3,4,5] normal: [2,3,4] negative ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,2,5) negative size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,-2,5) negative ix and size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (-2,-1,5) too large ix: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,2,5) too large size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (2,6,5) too large ix size: ./Data/Vector/Generic.hs:396 (slice): invalid slice (6,6,5) I am rarely in favor of partial functions, therefore I lean towards fixing the arguments to slice functions so they don't fail. All this conversation applies to mutable variants as well, but naturally not for the streaming ones. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#257?email_source=notifications&email_token=AAABBQURCE6ECG6NYEODXOLRALSIXA5CNFSM4IZ476A2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKLIBYQ#issuecomment-580288738>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABBQXWM3PRD3F2P2ZKYYDRALSIXANCNFSM4IZ476AQ> .Reacted by Alexey Kuleshevich
for now / cutting a release:
current semantics fix for now? i do agree that theres good reasons to have different semantics or expose both flavors and or improvements to the underlying fusion framework are probably sensible long term directions, but less bugs now is best :). would like to make sure the next release is "minor bump" in spirit despite the piles of stuffSounds good. I'll then turn off fusion of the
slicefunction, which will give us semantics that most people would expect (error on invalid indices) and remove theSegfaultandOut of memorybugs. We can bikeshed about other semantics and alternative functions later :)i mean, it'd be great if we could hae fusion AND nice things, but that might be more involved?
Reacted by Alexey Kuleshevichlooking at the underlying code,
slice :: Vector v a => Int -> Int -> New v a -> New v a {-# INLINE_FUSED slice #-} slice i n m = apply (MVector.slice i n) mMVector codes never fuse, that fusion rule doesn't preclude
"slice/new [Vector]" forall i n p. slice i n (new p) = new (New.slice i n p)working.... if we somemthing something?
like, maybe some trick withseq?by which i mean, we want slice to check correctly whether or not it gets rewritten away ?
hrmm, i need to read through this all more
If it gets rewritten it can't be checked. In case you wanna have more fun with it like I did last night here are my notes:
slice i n (fromList xs) slice i n (unstream (Bundle.fromList xs)) -- INLINE slice i n (new (New.unstream (Bundle.fromList xs))) -- INLINE new (New.slice i n (New.unstream (Bundle.fromList xs))) -- REWRITE "slice/new [Vector]" new (New.unstream (Bundle.slice i n (Bundle.fromList xs))) -- REWRITE "slice/unstream [New]" new (New (MVector.vunstream (Bundle.slice i n (Bundle.fromList xs)))) -- INLINE -- INLINE: new (New (MVector.vmunstream (Bundle.lift (Bundle.slice i n (MBundle.unsafeFromList Unknown xs))))) -- INLINE: new (New (MVector.vmunstream (Bundle.lift (Bundle.take n (Bundle.drop i (MBundle.unsafeFromList Unknown xs)))))) -- INLINE: new (New (MVector.vmunstream (Bundle.lift (Bundle.take n (Bundle.drop i (Bundle.fromStream (S.fromList xs) Unknown)))))) -- EVAL: Bundle.fromStream Bundle.fromStream (S.fromList xs) Unknown == Bundle (Stream step t) (Stream step' t) Nothing Unknown -- EVAL: Bundle.drop i Bundle.drop i (Bundle (Stream step t) (Stream step' t) Nothing Unknown) == fromStream (S.drop i (Stream step t)) (clampedSubtract Unknown (Exact i)) == fromStream (S.drop i (Stream step t)) Unknown -- EVAL: fromStream Bundle.take n (fromStream (S.drop i (Stream step t)) Unknown) == Bundle.take n (Bundle (S.drop i (Stream step t)) (Stream step' t) Nothing Unknown) -- EVAL: Bundle.take Bundle.take n (Bundle (S.drop i (Stream step t)) (Stream step' t) Nothing Unknown) == fromStream (S.take n (S.drop i (Stream step t) Unknown)) (smaller (Exact n) Unknown) == fromStream (S.take n (S.drop i (Stream step t) Unknown)) (Max n) -- EVAL: fromStream fromStream (S.take n (S.drop i (Stream step t) Unknown)) (Max n) == Bundle (S.take n (S.drop i (Stream step t) Unknown)) (Stream step' t) Nothing (Max n) -- EVAL: lift new (New (MVector.vmunstream (Bundle.lift (Bundle (S.take n (S.drop i (Stream step t) Unknown)) (Stream step' t) Nothing (Max n))))) === new (New (MVector.vmunstream (Bundle (S.take n (S.drop i (Stream step t) Unknown)) (Stream step' t) Nothing (Max n)))) -- EVAL: vmunstream new (New (MVector.vmunstream (Bundle (S.take n (S.drop i (Stream step t) Unknown)) (Stream step' t) Nothing (Max n)))) == new (New (vmunstreamMax (Bundle (S.take n (S.drop i (Stream step t) Unknown)) (Stream step' t) Nothing (Max n))))
I reported this for GHC first. See https://gitlab.haskell.org/ghc/ghc/issues/17233 for full details (could be copied here if clearly a bug in vector). May be related to #188?