Segfaults and "internal errors" when vector slice overflows #257

bjornbm · 2019-09-24T09:16:57Z

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?

snoyberg · 2019-09-24T10:11:36Z

Looks to me like the bug is here:

vector/Data/Vector/Internal/Check.hs

Lines 147 to 151 in 46110b9

    
           checkSlice :: String -> Int -> Checks -> String -> Int -> Int -> Int -> a -> a 
        
           {-# INLINE checkSlice #-} 
        
           checkSlice file line kind loc i m n x 
        
             = check file line kind loc (checkSlice_msg i m n) 
        
                                        (i >= 0 && m >= 0 && i+m <= n) x

Specifically, i+m <= n is subject to integer overflow. Instead, something like m <= n - i should be applied.

Fix the test case to trigger the sliceCheck

lehins · 2020-01-30T03:25:51Z

This is great, how many ways can we get the slice wrong? :)

Surprisingly, bug reported here is pretty hard to hit this in a slice function. 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 sliceCheck will 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.hs file:

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 memory

But what is even greater consequence of this, is that too large of the size parameter to slice can 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 drop from bundle, which I still need some tests for and a proper fix.

lehins · 2020-01-30T03:33:34Z

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] == 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 from stream:

vector/Data/Vector/Fusion/Stream/Monadic.hs

Lines 313 to 318 in 1bb6b5d

    
           slice :: Monad m => Int   -- ^ starting index 
        
                            -> Int   -- ^ length 
        
                            -> Stream m a 
        
                            -> Stream m a 
        
           {-# INLINE slice #-} 
        
           slice i n s = take n (drop i s)

cartazio · 2020-01-30T03:58:28Z

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> .

cartazio · 2020-01-30T04:25:45Z

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> > . >

lehins · 2020-01-30T13:48:48Z

For the slow here is what I suggest. (just kidding ;)

Make slice a 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)

lehins · 2020-01-30T14:49:46Z

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 slice functions so they don't fail. All this conversation applies to mutable variants as well, but naturally not for the streaming ones.

cartazio · 2020-01-30T19:01:37Z

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> .

cartazio · 2020-01-30T22:21:53Z

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 stuff

lehins · 2020-01-30T22:27:39Z

Sounds good. I'll then turn off fusion of the slice function, which will give us semantics that most people would expect (error on invalid indices) and remove the Segfault and Out of memory bugs. We can bikeshed about other semantics and alternative functions later :)

cartazio · 2020-01-30T22:30:01Z

i mean, it'd be great if we could hae fusion AND nice things, but that might be more involved?

cartazio · 2020-01-30T22:32:58Z

looking 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) m

MVector 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 with seq ?

cartazio · 2020-01-30T22:33:28Z

by which i mean, we want slice to check correctly whether or not it gets rewritten away ?

cartazio · 2020-01-30T22:35:09Z

hrmm, i need to read through this all more

lehins · 2020-01-30T22:36:02Z

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))))

* Streaming causing bounds to not be checked, thus not failing slicing. Which differed from the semantics of `slice` when compiled with -O0 * Out of memory explosion when size supplied to `slice` is too high

bjornbm mentioned this issue Sep 24, 2019

Move slice to Partial, add sliceMaybe function commercialhaskell/rio#201

Open

cartazio mentioned this issue Jan 21, 2020

vector Jan 2020 RC #266

Closed

lehins added a commit that referenced this issue Jan 30, 2020

WIP: Fix #257

2135f12

Fix the test case to trigger the sliceCheck

lehins added the bug label Jan 30, 2020

lehins added a commit that referenced this issue Jan 31, 2020

Implement tests for all discovered issues with slicing in #257

740c22f

lehins added a commit that referenced this issue Jan 31, 2020

Fixes the Int overflow that caused segfault reported in #257

b8362d7

lehins mentioned this issue Jan 31, 2020

Fix issues with vector slice function #279

Merged

cartazio mentioned this issue Jan 31, 2020

figure out how to thread checking information along fusion transformations #281

Closed

cartazio closed this as completed in #279 Jan 31, 2020

cartazio pushed a commit that referenced this issue Jan 31, 2020

Implement tests for all discovered issues with slicing in #257

52123c1

cartazio pushed a commit that referenced this issue Jan 31, 2020

Fixes the Int overflow that caused segfault reported in #257

50443e1

This was referenced Jan 31, 2020

semantics of slice, now and future (plus near term bug fixes) #276

Closed

Fusion of take can cause OutOfMemory #282

Closed

Shimuuar mentioned this issue Feb 1, 2020

Support for Safe Haskell #56

Closed

lehins mentioned this issue Jan 17, 2021

Release plan for 0.13 #357

Closed

6 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Segfaults and "internal errors" when vector slice overflows #257

Segfaults and "internal errors" when vector slice overflows #257

bjornbm commented Sep 24, 2019

snoyberg commented Sep 24, 2019

lehins commented Jan 30, 2020

lehins commented Jan 30, 2020 •

edited

Loading

cartazio commented Jan 30, 2020 via email

cartazio commented Jan 30, 2020 via email

lehins commented Jan 30, 2020 •

edited

Loading

lehins commented Jan 30, 2020 •

edited

Loading

cartazio commented Jan 30, 2020 via email

cartazio commented Jan 30, 2020

lehins commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

lehins commented Jan 30, 2020

Segfaults and "internal errors" when vector slice overflows #257

Segfaults and "internal errors" when vector slice overflows #257

Comments

bjornbm commented Sep 24, 2019

snoyberg commented Sep 24, 2019

lehins commented Jan 30, 2020

lehins commented Jan 30, 2020 • edited Loading

cartazio commented Jan 30, 2020 via email

cartazio commented Jan 30, 2020 via email

lehins commented Jan 30, 2020 • edited Loading

lehins commented Jan 30, 2020 • edited Loading

cartazio commented Jan 30, 2020 via email

cartazio commented Jan 30, 2020

lehins commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

cartazio commented Jan 30, 2020

lehins commented Jan 30, 2020

lehins commented Jan 30, 2020 •

edited

Loading

lehins commented Jan 30, 2020 •

edited

Loading

lehins commented Jan 30, 2020 •

edited

Loading