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

vmgen: fix two overflow bugs with sets #801

Merged

Conversation

zerbina
Copy link
Collaborator

@zerbina zerbina commented Jul 16, 2023

Summary

Fix either the compiler crashing or the VM failing at run-time with an
over- or underflow defect for incl, contains, and construction
operations for sets where the element range crossed the int64 upper
boundary.

The fixed bugs only affected VM bytecode generation and code running in
the VM.

Details

There were two related problems:

  • the relevant vmgen logic performed all math with signed integer
    values
  • preparing (i.e., offsetting) a run-time value for a set operation
    always happened via SubInt (subtract signed integer), ignoring
    the signed-ness of the operands

When the lower bound of the elements' range was beyond the int64 upper
bound, this didn't cause problems: reinterpreting the integer bits
always yields negative values there. For example, for a set[Low..High]
where Low == high(uint64)-3 and High = high(uint), subtracting the
lower inclusive-bound (-4) from the upper inclusive-bound (-1) both
didn't cause and overflow and also resulted in the correct value (3).

However, when Low == uint64 high(int64) and High == Low + 4, this
doesn't work. When the operand to an operation involving such sets was a
literal integer outside the int64 range, the compiler crashed - when
it was a run-time value, the VM erroneously reported an overflow.

The logic for generating the code for loading set elements now uses
Int128 to get around over- and underflow problems, and the Subu
operation is emitted for offsetting unsigned run-time values.

In addition, generating the bytecode for loading literal unsigned
integers now happens via loadInt, meaning that the values are now
loaded via LdImmInt if they're less than 2^23. Previously, literal
unsigned integers were always loaded via the slightly less efficient
LdConst operation.

Summary
=======

Fix either the compiler crashing or the VM failing at run-time with an
over- or underflow defect for `incl`, `contains`, and construction
operations for `set`s where the element range crossed the `int64` upper
boundary.

The fixed bugs only affected VM bytecode generation and code running in
the VM.

Details
=======

There were two related problems:
- the relevant `vmgen` logic performed all math with signed integer
  values
- preparing (i.e., offsetting) a run-time value for a `set` operation
  always happened via `SubInt` (subtract signed integer), ignoring
  the signed-ness of the operands

When the lower bound of the elements' range was beyond the `int64` upper
bound, this didn't cause problems: reinterpreting the integer bits
always yields negative values there. For example, for a `set[Low..High]`
where `Low == high(uint64)-3` and `High = high(uint)`, subtracting the
lower inclusive-bound (-4) from the upper inclusive-bound (-1) both
didn't cause and overflow and also resulted in the correct value (3).

However, when `Low == uint64 high(int64)` and `High == Low + 4`, this
doesn't work. When the operand to operation involving such sets was a
literal integer (outside the `int64` range), the compiler crashed - when
it was a run-time value, the VM erroneously reported an overflow.

The logic for generating the code for loading set elements now uses
`Int128` to get around over- and underflow problems, and the `Subu`
operation is emitted for offsetting unsigned run-time values.

In addition, generating the bytecode for loading literal unsigned
integers now happens via `loadInt`, meaning that the values are now
loaded via `LdImmInt` if they're less than 2^23. Previously, literal
unsigned integers were always loaded via the slightly less efficient
`LdConst` operation.
@zerbina zerbina added bug Something isn't working compiler/backend Related to backend system of the compiler labels Jul 16, 2023
Copy link
Collaborator

@saem saem left a comment

Choose a reason for hiding this comment

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

Nice fix. That reminds me I should re-test release builds of the compiler to see if they're clean.

@saem
Copy link
Collaborator

saem commented Jul 16, 2023

/merge

@github-actions
Copy link

Merge requested by: @saem

Contents after the first section break of the PR description has been removed and preserved below:


Notes for Reviewers

  • I re-discovered the issue while experimenting with storing the value for unsigned integer literals as BiggestUInt

@chore-runner chore-runner bot added this pull request to the merge queue Jul 16, 2023
Merged via the queue into nim-works:devel with commit c0ba526 Jul 16, 2023
18 checks passed
@zerbina zerbina deleted the vmgen-fix-overflow-bugs-with-set branch July 17, 2023 16:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working compiler/backend Related to backend system of the compiler
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants