Integer overflow when calculating number of bytes

[mkitti]

The length and number of byte calculations are subject to integer overflow.

https://wiki.sei.cmu.edu/confluence/display/c/MEM07-C.+Ensure+that+the+arguments+to+calloc%28%29%2C+when+multiplied%2C+do+not+wrap

julia> using StaticTools

julia> malloc(typemax(Int)) # malloc returns a C_NULL when it fails
Ptr{UInt8} @0x0000000000000000

julia> ma = MallocArray{Int}(zeros, (3000,typemax(Int),typemax(Int)));

julia> sizeof(ma)
24000

julia> size(ma)
(3000, 9223372036854775807, 9223372036854775807)

julia> MallocArray{Int}(zeros, (3000,typemax(Int)))
3000×9223372036854775807 MallocMatrix{Int64}:

signal (11): Segmentation fault
in expression starting at none:0
unsafe_load at ./pointer.jl:105 [inlined]
unsafe_load at ./pointer.jl:105 [inlined]

Julia deals with integer overflow via this code as of Julia 1.8: https://github.com/JuliaLang/julia/blob/0b9eda116d88cf472df2d485cfd366bfab17afa8/src/array.c#L79-L96

[brenhinkeller]

One possible approach would be #23. Another would be just documenting something like "Attempting to create a MallocArray with more than typemax(Int) bytes will result in undefined behavior".

[mkitti]

Another approach might using Base.Checked.checked_mul or perhaps mul_with_overflow if we cannot throw.

function checked_mul(x::T, y::T) where T<:Integer
    @_inline_meta
    z, b = mul_with_overflow(x, y)
    b && throw_overflowerr_binaryop(:*, x, y)
    z
end

...

mul_with_overflow(x::T, y::T) where {T<:SignedInt}   = checked_smul_int(x, y)
mul_with_overflow(x::T, y::T) where {T<:UnsignedInt} = checked_umul_int(x, y)
mul_with_overflow(x::Bool, y::Bool) = (x*y, false)

julia> Base.Checked.mul_with_overflow(5,6)
(30, false)

julia> Base.Checked.mul_with_overflow(5,typemax(Int))
(9223372036854775803, true)

julia> @code_llvm Base.Checked.mul_with_overflow(5,6)
;  @ checked.jl:234 within `mul_with_overflow`
; Function Attrs: uwtable
define void @julia_mul_with_overflow_293({ i64, i8 }* noalias nocapture sret({ i64, i8 }) %0, i64 signext %1, i64 signext %2) #0 {
top:
  %3 = call { i64, i1 } @llvm.smul.with.overflow.i64(i64 %1, i64 %2)
  %4 = extractvalue { i64, i1 } %3, 0
  %5 = extractvalue { i64, i1 } %3, 1
  %6 = zext i1 %5 to i8
  %.sroa.0.0..sroa_idx = getelementptr inbounds { i64, i8 }, { i64, i8 }* %0, i64 0, i32 0
  store i64 %4, i64* %.sroa.0.0..sroa_idx, align 8
  %.sroa.2.0..sroa_idx = getelementptr inbounds { i64, i8 }, { i64, i8 }* %0, i64 0, i32 1
  store i8 %6, i8* %.sroa.2.0..sroa_idx, align 8
  ret void
}

[brenhinkeller]

mul_with_overflow does appear to be StaticCompiler safe so that could work if we want

[mkitti]

If LLVM already has a nice implementation, via https://llvm.org/docs/LangRef.html#llvm-smul-with-overflow-intrinsics we should consider using mul_with_overflow. Here's a replacement for prod.

julia> function prod_with_overflow(itr)
           p = one(eltype(itr))
           for v in itr
               p, f = Base.Checked.mul_with_overflow(p, v)
               if f
                   return p, true
               end
           end
           return p, false
       end
prod_with_overflow (generic function with 1 method)

julia> prod_with_overflow(2:10)
(3628800, false)

julia> prod_with_overflow(2:100000)
(-4249290049419214848, true)

[brenhinkeller]

Ah yeah, I just tried that as https://github.com/brenhinkeller/StaticTools.jl/pull/23/commits/b292167e443c15dfc2d4c1d367caa7cca82c9782#diff-bc676878ee7fa70f16534c2e6baa1df2e5e141f52b2343b57f602c09bde25aaeR135-R142

    @inline function prod_with_overflow(x)
         p, f = one(eltype(x)), false
         for i ∈ eachindex(x)
             p, fᵢ = Base.Checked.mul_with_overflow(p, x[i])
             f |= fᵢ
         end
         p, f
     end

which perhaps counterintuitively ends up being a bit faster than the branching version because of unrolling

[brenhinkeller]

Looks like Base.Checked.mul_with_overflow is part of the documented Julia API: https://docs.julialang.org/en/v1/base/math/#Base.Checked.mul_with_overflow

so if anyone breaks it in 1.x we can be suitably mad at them. That's more or less good enough for me

[brenhinkeller]

Fixed by #23 updated to use the Base.Checked.mul_with_overflow approach