Overflow and underflow in Rust

In mathematics, addition usually used over integers. The set of integers is infinite. In computer science, we don't have infinite memory for every integer, so all of the programming languages had some solution to approximate real integers as much as they can. There are two methods for this approximation:

• Some (mostly interpreted) languages like JavaScript and Python have unbounded integers. (The default integer type of Python is unbounded and JavaScript has BigInt, which is also unbounded.) The problem whith unbounded integers are that they can't programmed effectively. We have to pay the cost of the possibility of infinitly huge integers (almost) after every mahtematical operation.
• Most languages have bounded integer types with different bitlength. Using bounded integers are effective but they have to use modular arithmetic instead of ordinary arithmetic.

If you choose your numeric types correctly, you won't notice a difference between ordinary and modular arithmetic, but even biggest companies can make mistakes wich results overflow or underflow in commercial systems, so we shouldn't underestimate this source of errors.

Rust was designed for programming critical systems in resource-poor environment, so the designers of Rust invented a third method for dealing overflow and underflow: The Rust has bounded integer types, but they don't support modular arithmetic. If your code causes an overflow or underflow, the program panics and exists. (If you need overflow or underflow, check the Wrapping struckt.) Sadly, this only works in debug build and not in release build. Please, try to run the following code with cargo run and cargo run --release

fn main() {
    let mut a : u8 = 0;
    for _i in 0..300 { 
        a += 1;
    }
    println!("{}", a);
}

Building and running the code with cargo run produces a debug binary you can find in target/debug/<project_name>.exe It produces the following output:

PS D:\rust\draft\hello_cargo> cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target\debug\hello_cargo.exe`
thread 'main' panicked at 'attempt to add with overflow', src\main.rs:4:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: process didn't exit successfully: `target\debug\hello_cargo.exe` (exit code: 101)

Building and running the code with cargo run --release produces an optimized, release binary you can find in release/debug/<project_name>.exe It compiles and runs without error and its output will be 44. (44 is equal to 300 in modular 256 arithmetic.) The reason behind this is that checking overflow and underflow after every arithmetic operation has a huge cost.

To explore how much is this cost, we need a disassembler. I am not particulary familiar with Asm codes (I programmed PIC in Assembly ten years ago), so if you know nothing about Asm, don't be afraid, we won't go too deep inside it and you don't really need any previous experience about it. Firstly, we will need a Disassembler. I can recommend onlinedisassembler.com, you don't have to download anything and it has some nice features. You can start the work by pressing the Start Disassembling! button. After this, you have to upload your binary, but before we do it, please change the code to the following:

fn main() {
    let mut a : u8 = 0;
    for _i in 0..300 { 
        a += 39; // 39 == 0x27
    }
    println!("{}", a);
}

The generated code will contain a lot of operations where something will be increased by one. It will be hard to find this for cycle except we use some rare magic number in it. 39 is a good choice (67 would be also a good choice, there is nothing special with 39), we will find it easly in the assembly code. (This strategy can be handy if you would like to reverse engineering anything, like communication protocols of compilers. You can use some magic number which you will find in the communication stream. So first compile this code with the command cargo run and upload the produced binary from the debug folder.

You can upload it by selecting "Upload file" from the file menu and select the your binary. After that you should press Ok, and Ok again. (You should left everything in its default value.) The online interface is too slow, so I recommend to download the asm code from File/Download Disassembly and save the asm into the project directory.

After opening the file, we can see the 74000 lines long something. Now we have to search to the number 0x27 (0x27 is the hexadecimal value of 39) and we will easly find our for cycle. Or maybe not so easly, because there are 75 appearance of 0x27. Let's check them. Luckly, there is only one line where add operand and 0x27 occures. You can verify it by changing 39 to anything else and do the disassembly again. Our for-cycle is somewhere around the red 0x27. (I put the comments there and exchanged the memory addresses for labels after every jump instruction.) If you need a reference for the Asm instructions, I can recommend you this.

  sub    $0xd8,%rsp          # Reducing rsp by 216. Rsp points to the top of the current stack frame
  movb   $0x0,0x5f(%rsp)     # This is an indirect addressing. We move 0 to memory address 0x5f after the current value of rsp. 0x5f(%rsp) is the address of our a variable.
  movl   $0x0,0x60(%rsp)     # The difference between movl and movb is that movb only moves 8 bits, movl moves 32 bits
  movl   $0x12c,0x64(%rsp)   # So this 3 instructions set bits to zero between 0x5f and 0x68 after the value of rsp
  mov    0x60(%rsp),%ecx
  mov    0x64(%rsp),%edx
  callq  0x140001970
  mov    %eax,0x58(%rsp)
  mov    %edx,0x54(%rsp)
  mov    0x58(%rsp),%eax
  mov    %eax,0x68(%rsp)
  mov    0x54(%rsp),%ecx
  mov    %ecx,0x6c(%rsp)
Label5:                      # This is where our loop starts
  lea    0x68(%rsp),%rcx
  callq  0x1400018d0
  mov    %edx,0x74(%rsp)
  mov    %eax,0x70(%rsp)
  mov    0x70(%rsp),%eax
  mov    %eax,%ecx
  test   %rcx,%rcx
  je     Label1
  jmp    Label2
Label2:
  jmp    Label3
Label1:
  mov    0x1bbd7(%rip),%rax     
  lea    0x5f(%rsp),%rcx
  mov    %rcx,0xb8(%rsp)
  mov    0xb8(%rsp),%rcx
  mov    %rcx,0xd0(%rsp)
  lea    0x199c3(%rip),%rdx     
  mov    %rax,0x48(%rsp)
  callq  0x140001120
  mov    %rax,0x40(%rsp)
  mov    %rdx,0x38(%rsp)
  jmp    Label6
  ud2   
Label3:
  mov    0x74(%rsp),%eax
  mov    %eax,0xc4(%rsp)
  mov    %eax,0xc8(%rsp)
  mov    %eax,0xcc(%rsp)
  mov    0x5f(%rsp),%cl     # we transfer the value of a to %c1
  add    $0x27,%cl      # Here is our increasing. It sets CF (carrier flag) to one if overflow occures
  
  setb   %dl                # This instruction sets %dl to 1, if the CF (carrier flag) is one.
  test   $0x1,%dl           # It sets ZF (zero flag) if the value of %dl is not equal to 1, so if there were overflow, ZF is 0.
  mov    %cl,0x37(%rsp)     # We move the modified value to a temporarly memory address (0x37 from rsp)
  jne    Label4             # This instruction jumps to an error handling rutine if overflow occured (ZF=0)
  mov    0x37(%rsp),%al     # There were no error, we move the increased value of c back to al
  
  mov    %al,0x5f(%rsp)     # and we move al back to 0x5f
  jmpq   Label5             # This is just an unconditional jump. (Like goto.)
Label6:
  mov    0x40(%rsp),%rax
  mov    %rax,0xa8(%rsp)
  mov    0x38(%rsp),%rcx
  mov    %rcx,0xb0(%rsp)
  lea    0xa8(%rsp),%rdx
  lea    0x78(%rsp),%rcx
  mov    0x48(%rsp),%r8
  mov    %rdx,0x28(%rsp)
  mov    %r8,%rdx
  mov    $0x2,%r8d
  mov    0x28(%rsp),%r9
  movq   $0x1,0x20(%rsp)
  callq  0x140001180
  lea    0x78(%rsp),%rcx
  callq  0x140006780
  nop
  add    $0xd8,%rsp
  retq   
Label4:
  lea    0x1babb(%rip),%rcx     
  lea    0x1ba94(%rip),%r8      
  mov    $0x1c,%edx
  callq  0x140016e20
  ud2    

This asm block shows that to detect overflow and underflow, we need 5 instructions (the gray ones) after every arithmetic operation. This won't cause too much problem in a testing environment, but it's not acceptable in production for a hardware programming language, so the compiler has to remove the checks during optimization.