Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Prevent Time::Span overflow #5306

Closed
wants to merge 13 commits into from
Closed

Conversation

petoem
Copy link
Contributor

@petoem petoem commented Nov 16, 2017

While fixing multiply and divide by numbers, I noticed that there are a lot of possible overflows.
The biggest problem is that a lot of .to_i64 etc. are used and the general type restriction Int or Number for methods.
eg. This makes it possible to pass in a BigInt, which could overflow if .to_i64 is invoked on it.

Related to #5272 and possibly others.
This is a work-in-progress PR.

src/time/span.cr Outdated
)
end

def initialize(*, seconds : Int, nanoseconds : Int)
# check for possible overflow
# seconds could be too big
if Int64::MIN > seconds || seconds > Int64::MAX
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe unless Int64::MIN <= seconds <= Int64::MAX is easier to understand?

src/time/span.cr Outdated
# check for possible overflow
# seconds could be too big
if Int64::MIN > seconds || seconds > Int64::MAX
raise ArgumentError.new "Time::Span too big or too small"
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not sure about raising a runtime error... it would be safer to enforce value range through type safety. Meaning, a BigInt would need to be cast to Int64 by the user.

src/time/span.cr Outdated
seconds: to_i.to_i64 * number,
nanoseconds: nanoseconds.to_i64 * number,
)
(total_nanoseconds * number).nanoseconds
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This method should still return a Time::Span, not nanoseconds as Int.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It does return Time::Span, because (Float64 * Number) results in a Float64 and invoking Float#nanoseconds method returns a Time::Span.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh, my bad.

src/time/span.cr Outdated
seconds: seconds,
nanoseconds: nanoseconds,
)
(total_nanoseconds / number).nanoseconds
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

@bcardiff
Copy link
Member

This is more related to #3103 that other issue. If implicit safe / explicit unsafe if chosen, then there would nothing to be done here. And if the oposite (explicit safe / implicit unsafe), then a safe { } could be used to avoid handmade overflow guard conditions.

@petoem
Copy link
Contributor Author

petoem commented Nov 18, 2017

@bcardiff Actually there are two things that overflow/wraparound here.

  • the arithmetic operations like adding Time::Span together
  • and calling .to_i32 or .to_i64 on a variable with possible wider range.

I would like to avoid handmade overflow guard conditions as much as possible. I see crystal currently does not have a built-in overflow detection, so I would leave Time::Span as is to overflow on arithmetic operations.

But I would like to fix the second issue. So trying to create an invalid Time::Span should raise or be at least harder to do. (eg. as @straight-shoota said to enforce value range through type safety)
Allowing Int and Number is nice, but mercilessly cutting it down to Int32 or Int64 is not.

For example, doing BigInt#nanoseconds is possible, which is ok as long as it is within Int64 range, because on Line 448 it does self.to_i64.

Anyway, I will fix Time::Span#* and Time::Span#/ for Float and see whether I can eliminate point two without having to use to many conditions (maybe instead using type safety).

src/time/span.cr Outdated
# seconds could be too big
unless Int64::MIN <= seconds <= Int64::MAX
raise ArgumentError.new "Time::Span too big or too small"
end
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Does a negative Time::Span make sense?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sure, why wouldn't it? If you subtract an earlier instance from a later one, the difference is a negative duration.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think it does. Otherwise some operations are a bit hard to do.

@bcardiff
Copy link
Member

@petoem thanks for the interest of the safeness in the numbers realm. It think the second item.

and calling .to_i32 or .to_i64 on a variable with possible wider range.

Is just another case of implicit overflow. Don't you think? Otherwise whatever fix you accomplish for Time::Span would be required to be applied in other places.

I use to_* methods to 1) increase beforehand the precision of the arithmetic to be done, and to 2) ensure the final type to store in var/ivar. I agree that for this second case a safer thing to do is to raise if the receiver is wider than the final range.

@RX14
Copy link
Contributor

RX14 commented Nov 19, 2017

Perhaps, something to think about is to make to_i32 raise if the number will overflow, and provide a to_i32! which does overflow. Perhaps landing that without any other related overflow-handing options would be kinda pointless though.

@petoem
Copy link
Contributor Author

petoem commented Nov 19, 2017

I have removed the overflow detection I added on arithmetic operations, because I think that llvm provided ones are better and faster.

Following changes/improvement are still in this PR:

  • initialize only checks types with a wider range than Int64 to avoid overflow it raises
  • fixed multiply and divide methods Time::Span#*, Time::Span#/ for Float (Int uses the old method)
  • Float#nanoseconds and Float#seconds now check whether the resulting seconds fit into a Time::Span
  • Float#nanoseconds and Float#seconds use .trunc instead of .to_i64 to avoid overflow
  • its now possible to do Time::Span.new and Time::Span.new seconds: 2
  • Added some more documentation

@petoem
Copy link
Contributor Author

petoem commented Nov 19, 2017

@RX14 This is a great idea! Maybe the other way around is better (easier to understand), to make .to_i32! raise and .to_i32 overflow.

@RX14
Copy link
Contributor

RX14 commented Nov 19, 2017

I'd rather have the "default" be safer.

Copy link
Contributor

@RX14 RX14 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not too sure about all this overflow handling, i'd rather implement it at the language level, since it's painful and error-prone to implement it manually.

LLVM has the intrinsics, and it does two's complement overflow always by default (it's not undefined like C) and so it should be failry easy to implement. We just need to work out what to do.

src/time/span.cr Outdated
)
end

def initialize(*, seconds : Int, nanoseconds : Int)
def initialize(*, seconds : Int8 | Int16 | Int32 | Int64 | UInt8 | UInt16 | UInt32, nanoseconds : Int = 0)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please just leave this as Int and place the unless/raise block from the Int restricted method in this method. It's cleaner, and it'll get easilly optimized out when the compiler can prove it's in range (i.e. the right datatype) anyway.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You are right, it's cleaner.

# Normalize nanoseconds in the range 0...1_000_000_000
seconds += nanoseconds.tdiv(NANOSECONDS_PER_SECOND)
# check for possible overflow seconds could become too big
sec = nanoseconds.tdiv(NANOSECONDS_PER_SECOND)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that sec itself could be > Int64::MAX here. That overflow case isn't handled (i think?)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It could be, but then nanoseconds would need to be really big. tdiv returns the result value with the type of nanoseconds, so sec will have the same possible range as nanoseconds.
But because sec will be smaller than nanoseconds it fits and doesn't overflow.

src/time/span.cr Outdated
@@ -262,6 +278,7 @@ struct Time::Span
Time.now - self
end

# Returns the result of subtracting `self` and *other*.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we leave doc changes to another PR?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sure.

src/time/span.cr Outdated
Span.new(
seconds: -to_i,
nanoseconds: -nanoseconds,
)
end

# Returns the result of adding `self` and *other*.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

src/time/span.cr Outdated
@@ -286,20 +303,27 @@ struct Time::Span
)
end

# Returns self.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

src/time/span.cr Outdated
@@ -435,6 +464,7 @@ struct Int

# Returns a `Time::Span` of `self` milliseconds.
def milliseconds : Time::Span
# this might overflow
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This comment isn't really helpful

@RX14
Copy link
Contributor

RX14 commented Nov 22, 2017

Can't this PR just be adding multiply and divide for timespan? It's too many things at once: docs, overflow, new methods.

@Groogy
Copy link

Groogy commented Jan 6, 2018

Curious if anything still happening with this PR? Would be quite useful for me to get this in :)

@petoem
Copy link
Contributor Author

petoem commented Jan 6, 2018

@Groogy The thing is, that this PR does not prevent Time::Span from overflowing.
It raises if you try to create a Time::Span that would be bigger than Time::Span::MAX or smaller than Time::Span::MIN.
Which in some cases prevents it from "overflow" e.g. UInt64::MAX.nanoseconds.
As @RX14 said, a language level implementation would be better e.g. using LLVM intrinsics would solve it for all cases and not just Time::Span.

Something like the checked { } keyword from C# would be a good possible solution too.
Anyway, this topic needs more discussion and the solution should not be limited to Time::Span.

Maybe I should rename this PR to something else. 🤔
Merging this wouldn't hurt, but if it is not merged I will split of the fix for #5272 into another separated PR.

@straight-shoota
Copy link
Member

Yes, let's have a fix for the method arguments now in a separate PR 👍

@petoem
Copy link
Contributor Author

petoem commented Jan 9, 2018

@straight-shoota #5272 fixed in PR #5563 .

@sdogruyol
Copy link
Member

Let's give this PR a bit more ❤️

@petoem
Copy link
Contributor Author

petoem commented Apr 16, 2018

@sdogruyol the initial issue #5272 was fixed, now only the overflow part remains.
overflow is an issue that affects other parts of crystal too, not just Time::Span.
I have played with the thought of adding support for Int overflow checking myself, because the gist in #3103 is pretty much usable.
But the problem is there seems to be no consensus on how to add overflow checking to crystal.

bcardiff commented on Nov 18, 2017
If implicit safe / explicit unsafe if chosen, then there would nothing to be done here. And if the oposite (explicit safe / implicit unsafe), then a safe { } could be used to avoid handmade overflow guard conditions.

Whether it should be implicit or explicit safe and how it should look, needs more discussion.
Anyway, we should definitely get Int overflow checking, in some form, into crystal.

@jkthorne
Copy link
Contributor

@petoem I am just looking through some PRs. Are you still working on this?

@petoem
Copy link
Contributor Author

petoem commented May 25, 2018

I am closing this, because #5272 is fixed and int overflow is out of this PRs scope.

@petoem petoem closed this May 25, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Numbers
Awaiting triage
Development

Successfully merging this pull request may close these issues.

None yet

8 participants