Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#10571 closed bug (fixed)

GHC 7.10.1 segfaults when shiftL-ing Integers by negative amounts

Reported by: anders_ Owned by:
Priority: high Milestone:
Component: Compiler Version: 7.10.1
Keywords: Cc: hvr
Operating System: MacOS X Architecture: x86_64 (amd64)
Type of failure: Runtime crash Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

For numbers other than 1, anyway.

$ ghc -e 'Data.Bits.shiftL 1 (-1)'
-9223372036854775808
$ ghc -e 'Data.Bits.shiftL 2 (-1)'
zsh: segmentation fault  ghc -e 'Data.Bits.shiftL 2 (-1)'
$ ghc -e 'Data.Bits.shiftL 100 (-1)'
zsh: segmentation fault  ghc -e 'Data.Bits.shiftL 100 (-1)'

This also happens with a compiled program. It doesn't with shiftR in either case though.

Side notes:

  • On OS X, when the first operand is also negative, I get a bus error instead of a segmentation fault. Linux gives segmentation fault on both.
  • On Linux, you have to use ghci instead of -e, for some (probably unrelated?) reason).

Change History (10)

comment:1 Changed 2 years ago by rwbarton

Cc: hvr added
Priority: normalhigh

The documentation for shiftL does say "the specified number of bits (which must be non-negative)", so the first case might be okay, but crashing is too much.

The whole shift/shiftL/shiftR thing seems a little dubious to me in general, but surely for Integer we should test the sign of the shift in shiftL/shiftR and produce the expected result.

comment:2 Changed 2 years ago by hvr

Right now,

instance Bits Integer where
   -- ...
   shift x i@(I# i#) | i >= 0    = shiftLInteger x i#
                     | otherwise = shiftRInteger x (negateInt# i#)
   shiftL x (I# i#) = shiftLInteger x i#
   shiftR x (I# i#) = shiftRInteger x i#
   -- ...

The simplest fix would be to simply rename shift{L,R} = ... to unsafeShift{L,R} = ...

Last edited 2 years ago by hvr (previous) (diff)

comment:3 Changed 2 years ago by rwbarton

I know unsafeShiftL has "unsafe" in the name, but it seems irresponsible to segfault on a negative argument when it would take one additional instruction to test for a negative shift (shiftLInteger already checks whether the shift is 0) in a function that is not cheap to begin with and is exposed as a "public" part of the Data.Bits API.

The Int instance of unsafeShiftL is sensible because the cost of testing whether the shift is in range could exceed the cost of actually doing the shift. That doesn't apply here to Integer.

comment:4 Changed 2 years ago by rwbarton

BTW, I'm curious why the program is segfaulting, rather than reporting an out-of-memory condition like it does if I try to evaluate 2 `shiftL` 1000000000000000.

comment:5 in reply to:  4 Changed 2 years ago by hvr

Replying to rwbarton:

BTW, I'm curious why the program is segfaulting, rather than reporting an out-of-memory condition like it does if I try to evaluate 2 `shiftL` 1000000000000000.

Most likely because integer_gmp_mpn_lshift gets called with unsound parameters, leading to memset(3) overwriting memory it isn't supposed to touch...

The low-level api in integer-gmp has very little safeguards (for one to avoid having to check the same conditions multiple times, but also because we can't report errors), I've tried to document all pre-conditions on input-arguments which are required to be satisfied to avoid segfaults. To some degree this also a result of having to use Int# for quantities which then are converted into a Word# rightaway...

comment:6 Changed 2 years ago by kanetw

Is there anything that prevents us from adding a guard that checks whether the shift amount is negative and giving an error when it is?

comment:7 Changed 2 years ago by rwbarton

Might not be possible inside integer-gmp for dependency reasons (error is defined in base which depends on integer-gmp) but certainly possible in the instance in Data.Bits. Having shiftLInteger itself crash on negative shifts is fine IMHO as it's not intended for end-user use.

comment:8 Changed 2 years ago by Ben Gamari <ben@…>

In ea4df12/ghc:

Ensure shiftL/shiftR arguments aren't negative

Fixes #10571.

comment:9 Changed 2 years ago by bgamari

Resolution: fixed
Status: newclosed

Fixed and merged to ghc-7.10 as ea4df12f7f3fc4d1d2af335804b8ec893f45550c.

comment:10 Changed 2 years ago by Ben Gamari <ben@…>

In 182c44da/ghc:

Keep `shift{L,R}` on `Integer` from segfaulting

This can happen because the underlying primitive operations in
`integer-gmp` don't support negative shift-amounts, and since
`integer-gmp` can't throw proper exceptions and just provides a
low-level API, it simply segfaults instead...

This patch simply removes the `shift{L,R}` method definitions (and
defines `unsafeShift{L,R}` instead) whose default-impls fallback on
using `shift` which properly handles negative shift arguments.

This addresses #10571

Test Plan: harbormaster can do it

Reviewers: hvr, austin, rwbarton

Subscribers: rwbarton, thomie, bgamari

Differential Revision: https://phabricator.haskell.org/D1018

GHC Trac Issues: #10571
Note: See TracTickets for help on using tickets.