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

Fix potential undefined behaviour when using OverflowSafeInt #9451

Merged
merged 5 commits into from Jul 20, 2021

Conversation

LordAro
Copy link
Member

@LordAro LordAro commented Jul 19, 2021

Fixes #8284
Closes #8285

Motivation / Problem

OverflowSafeInt can actually underflow.

Description

Changes completely copied from inspired by JGR's work:
JGRennison/OpenTTD-patches@6821c0e
JGRennison/OpenTTD-patches@bb8d2c3
JGRennison/OpenTTD-patches@609f37c
JGRennison/OpenTTD-patches@db0e25f

But mildly neatened and modernised.

Limitations

Checklist for review

Some things are not automated, and forgotten often. This list is a reminder for the reviewers.

  • The bug fix is important enough to be backported? (label: 'backport requested')
  • This PR affects the save game format? (label 'savegame upgrade')
  • This PR affects the GS/AI API? (label 'needs review: Script API')
    • ai_changelog.hpp, gs_changelog.hpp need updating.
    • The compatibility wrappers (compat_*.nut) need updating.
  • This PR affects the NewGRF API? (label 'needs review: NewGRF')

src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
src/core/overflowsafe_type.hpp Show resolved Hide resolved
@TrueBrain
Copy link
Member

TrueBrain commented Jul 19, 2021

I am really certain I do not understand this code, so I just brute-forced it what I could think of:

https://godbolt.org/z/KE3qc1cqq

If you think I missed cases, feel free to add them and post the new link ;)

Seems all cases I could come up with work fine.

Edit: just to smoketest the compiler built-in variants: https://godbolt.org/z/5T8bPeYKe . Also shows no issues for the cases I came up with.

@rubidium42
Copy link
Contributor

Edit: just to smoketest the compiler built-in variants: https://godbolt.org/z/5T8bPeYKe . Also shows no issues for the cases I came up with.

Maybe guard against the built-in variant being used when min/max are not the min/max of the type? For example, the following works with the original code, but fails with the built-in variant.

OverflowSafeInt<int8_t, 5, 3> c = 3;
assert(c + 3 == 5);

@LordAro
Copy link
Member Author

LordAro commented Jul 19, 2021

Is it worth supporting that though? We can get rid of the extra 2 tparams with std::numeric_limits these days

@rubidium42
Copy link
Contributor

Is it worth supporting that though? We can get rid of the extra 2 tparams with std::numeric_limits these days

Knowing that std::numeric_limits exists was kind of the reason I was trying this as I (naively) assumed that it might have worked. After all, why have those parameters. Though removing the parameters seems another viable solution to the problem.

@TrueBrain
Copy link
Member

I think using numeric_limits would be great. I just worry about the depth of this rabbithole you found. Also:

return ::Company::Get(company)->cur_economy.delivered_cargo.GetSum<OverflowSafeInt<int32, INT32_MAX, INT32_MIN> >();
}
return ::Company::Get(company)->old_economy[quarter - 1].delivered_cargo.GetSum<OverflowSafeInt<int32, INT32_MAX, INT32_MIN> >();

Can we address those 2 instances while at it? Seems it should just be OverflowSafeInt32 :)

INT64_MIN negated is above INT64_MAX, and would overflow.
Instead, when negating INT64_MIN make it INT64_MAX.
This does mean that -(-(INT64_MIN)) != INT64_MIN.
@LordAro LordAro force-pushed the overflow-fixes branch 2 times, most recently from af1e8c3 to e6dc779 Compare July 20, 2021 07:48
TrueBrain
TrueBrain previously approved these changes Jul 20, 2021
Copy link
Member

@TrueBrain TrueBrain left a comment

Choose a reason for hiding this comment

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

For future-us: the mistake made here is that -T_MAX != T_MIN, but the code did assume it. In essence, that is what broke underflow protection, and what this PR addresses.

Notably, a company with an extremely negative amount of money would
suddenly become very rich
TrueBrain
TrueBrain previously approved these changes Jul 20, 2021
Copy link
Member

@TrueBrain TrueBrain left a comment

Choose a reason for hiding this comment

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

Nice.

@LordAro LordAro merged commit f1dfc2f into OpenTTD:master Jul 20, 2021
@LordAro LordAro deleted the overflow-fixes branch July 20, 2021 09:42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Negating or taking absolute values of maximally-negative OverflowSafeInt may result in undefined behaviour
3 participants