IntSet crashes Julia 0.6.1

General Usage
1

Dearests,

The following

julia> N=2^10; a= rand(UInt64,N);  sa=IntSet(a); #gives an error ... which is fine
ERROR: InexactError()
....
julia> a= rand(UInt32,N);  sa=IntSet(a); #now the system crashes
signal (11): Segmentation fault: 11
...

Note that the segfault occurs (systematically) only after the the first error is produced. Indeed, the help on IntSet constructor says

  [...] Only Ints greater than 0 can be stored. If the set
  will be sparse (for example holding a few very large integers), use Set
  instead.

and perhaps it is not a bug. However, let me know it you think it’s worth reporting upstream…

I’m on

Version 0.6.1 (2017-10-24 22:15 UTC)
x86_64-apple-darwin15.6.0

Cheers

Andrea

2

I get various errors, but never manage to crash Julia (v0.6.1, on Linux). These are typical:

julia> N=2^10; a= rand(UInt64,N);  sa=IntSet(a);
ERROR: OutOfMemoryError()
Stacktrace:
 [1] resize!(::BitArray{1}, ::UInt64) at ./bitarray.jl:836
 [2] _resize0!(::BitArray{1}, ::UInt64) at ./intset.jl:35
 [3] _setint! at ./intset.jl:25 [inlined]
 [4] push! at ./intset.jl:69 [inlined]
 [5] union!(::IntSet, ::Array{UInt64,1}) at ./intset.jl:95
 [6] IntSet(::Array{UInt64,1}) at ./intset.jl:7

julia> N=2^10; a= rand(UInt64,N);  sa=IntSet(a);
ERROR: InexactError()
Stacktrace:
 [1] resize!(::BitArray{1}, ::UInt64) at ./bitarray.jl:834
 [2] _resize0!(::BitArray{1}, ::UInt64) at ./intset.jl:35
 [3] _setint! at ./intset.jl:25 [inlined]
 [4] push! at ./intset.jl:69 [inlined]
 [5] union!(::IntSet, ::Array{UInt64,1}) at ./intset.jl:95
 [6] IntSet(::Array{UInt64,1}) at ./intset.jl:7

julia> N=2^10; a= rand(UInt64,N);  sa=IntSet(a);
ERROR: ArgumentError: elements of IntSet must be between 1 and typemax(Int)
Stacktrace:
 [1] _throw_intset_bounds_err() at ./intset.jl:64
 [2] push! at ./intset.jl:68 [inlined]
 [3] union!(::IntSet, ::Array{UInt64,1}) at ./intset.jl:95
 [4] IntSet(::Array{UInt64,1}) at ./intset.jl:7

Perhaps to make the error reproducible you could include a random seed.

3

Same as @Tamas_Papp, I get the correct errors (oxy moron?), but Julia doesn’t crash. This on x86_64 Linux.

In the past I’ve noticed that segfaults can pop up at very unexpected times in Julia; is it possible you ran some other code prior to this that was the real cause?

4

The second time shoul be run with UInt32 as in my example … an yes it is in a fresh session.

5

Yes, there’s likely something fishy going on here with UInt32 arithmetic in the internals of the IntSet.

julia> IntSet(UInt32(2^32-1))
IntSet([])

julia> IntSet((2^32-1))
IntSet([4294967295])

Edit: caught it:

julia> Base._setint!(IntSet(), UInt32(2^32-10), true)

signal (11): Segmentation fault: 11
while loading no file, in expression starting on line 0
unsafe_bitsetindex! at ./bitarray.jl:675 [inlined]
setindex! at ./bitarray.jl:682 [inlined]
_setindex! at ./abstractarray.jl:979 [inlined]
setindex! at ./abstractarray.jl:967 [inlined]
_setint! at ./intset.jl:27

Note that those stack traces are actually very helpful!

And with --check-bounds=yes:

julia> Base.push!(IntSet(), UInt32(2^32-10), true)
ERROR: BoundsError: attempt to access 2147483633-element BitArray{1} at index [4294967286]
Stacktrace:
 [1] throw_boundserror(::BitArray{1}, ::Tuple{Int64}) at ./abstractarray.jl:433
 [2] checkbounds at ./abstractarray.jl:362 [inlined]
 [3] setindex! at ./bitarray.jl:681 [inlined]
 [4] _setindex! at ./abstractarray.jl:979 [inlined]
 [5] setindex! at ./abstractarray.jl:967 [inlined]
 [6] _setint! at ./intset.jl:27 [inlined]
 [7] push!(::IntSet, ::UInt32) at ./intset.jl:69
 [8] push!(::IntSet, ::UInt32, ::Bool) at ./intset.jl:71
6

I’m confused

julia> IntSet(UInt32(2^32-1))
ERROR: ReadOnlyMemoryError()
Stacktrace:
 [1] unsafe_bitsetindex! at ./bitarray.jl:675 [inlined]
 [2] setindex! at ./bitarray.jl:682 [inlined]
 [3] _setindex! at ./abstractarray.jl:980 [inlined]
 [4] setindex! at ./abstractarray.jl:968 [inlined]
 [5] _setint! at ./intset.jl:27 [inlined]
 [6] push! at ./intset.jl:69 [inlined]
 [7] union!(::IntSet, ::UInt32) at ./intset.jl:95
 [8] IntSet(::UInt32) at ./intset.jl:7

julia> IntSet((2^32-1))
IntSet([4294967295])

julia> Base._setint!(IntSet(), UInt32(2^32-10), true)
IntSet([])
7

IntSet isn’t allocating enough space for the large UInt32 because it’s overflowing when it tries to compute how much space is required. So then it ends up writing out of bounds inside an @inbounds block. The behavior you see will vary depending upon where that out-of-bounds write lands: It could be in a read-only memory area, or it could silently corrupt something else, or it could crash.

https://github.com/JuliaLang/julia/pull/24365

4 Likes
8

Wow … quite a lot of activity on this! @mbauman, thanks a lot for detecting and solving the problem

A