std.math.big.Rational produces different results in non-safe build modes

[scheibo]

Zig Version

0.14.0-dev.994+9f46abf59

Steps to Reproduce and Observed Behavior

const std = @import("std");

fn update(r: *std.math.big.Rational, p: u8, q: u8) !void {
    var s = try std.math.big.Rational.init(r.p.allocator);
    defer s.deinit();
    try s.setRatio(p, q);
    try r.mul(r.*, s);
}

test update {
    var r = try std.math.big.Rational.init(std.testing.allocator);
    defer r.deinit();
    var s = try std.math.big.Rational.init(std.testing.allocator);
    defer s.deinit();

    try r.setInt(1);

    try update(&r, 1, 2);
    for (0..2) |_| {
        try update(&r, 1, 2);
        try update(&r, 1, 2);
        try update(&r, 3, 4);
        for (0..10) |_| {
            try update(&r, 9, 10);
            try update(&r, 1, 15);
            try update(&r, 1, 24);
            try update(&r, 9, 10);
        }
    }

    const ZEROS = std.math.pow(u310, 10, 31);
    const n = 36472996377170786403;
    const d: u310 = 146267071761884981524886149560653378220687632500762654519853056 * ZEROS;
    try s.setRatio(n, d);
    try std.testing.expect((try s.order(r)) == .eq);
}

$ zig test -OReleaseSafe test.zig
All 1 tests passed.
$ zig test -OReleaseFast test.zig
1/1 test.decltest.update...FAIL (TestUnexpectedResult)
0 passed; 0 skipped; 1 failed.
error: the following test command failed with exit code 1:
/Users/kjs/.cache/zig/o/d29b5fd88b270c8a1f7854ef13eb81ec/test --seed=0xdcdde35b

Expected Behavior

• adding a print reveals that in ReleaseFast the answer is math.big.rational.Rational{ .p = 109418989131512359209, .q = 562949953421312000000000000000000000000000000000000000000000000000000000000 }
• changing the bounds of the inner loop reveals that the modes match up to the 5th iteration, but 6 through 10 all differ

The results should be the same in both Debug/ReleaseSafe and ReleaseFast/ReleaseSmall - if there is undefined behavior involved in the answers being different then ReleaseSafe should catch it.

[pfgithub]

Simpler reproduction:

const std = @import("std");

fn mul(a: *std.math.big.int.Managed, b: std.math.big.int.Managed, c: std.math.big.int.Managed) !void {
    try a.mul(&b, &c);
}

test "bigint error" {
    var a = try std.math.big.int.Managed.init(std.testing.allocator);
    defer a.deinit();
    var b = try std.math.big.int.Managed.init(std.testing.allocator);
    defer b.deinit();

    try a.set(536870912000000000000000000000000000000);
    try b.set(10);
    try mul(&a, a, b);

    try b.set(5368709120000000000000000000000000000000);
    try std.testing.expect(a.order(b) == .eq);
}

Succeeds on ReleaseFast/ReleaseSmall, fails on Debug/ReleaseSafe

[pfgithub]

Issues:

• std.math.big.int.Managed.mul assumes that if the limbs array of rma aliases a then rma is the same pointer as a, but that is never asserted
  • Calling rma.ensureMulCapacity(a.toConst(), b.toConst()) reallocates rma.limbs. This invalidates the pointer to a.limbs if a is a copy of rma instead of the same pointer.
  • Fix:

    /// std.math.big.int.Managed.mul
    pub fn mul(rma: *Managed, a: *const Managed, b: *const Managed) !void {
    var alias_count: usize = 0;
    if (rma.limbs.ptr == a.limbs.ptr) {
        std.debug.assert(rma == a);
        alias_count += 1;
    }
    if (rma.limbs.ptr == b.limbs.ptr) {
        std.debug.assert(rma == b);
        alias_count += 1;
    }

• std.math.big.Rational.mul accepts a and b by value, rather than by reference. This means that a becomes a copy of r, and mutating r does not mutate a
  • Fix:

    pub fn mul(r: *Rational, a: *const Rational, b: *const Rational) !void {

• Debug mode does show some symptoms of there being an issue (a becomes 4184734490257787175890526282138444277401570296309356341930, which in hex is 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa), but I would expect it to crash when trying to access memory that was freed
  • GeneralPurposeAllocator tries to make sure that if freed memory is reused, the application will segfault in debug mode. I am not sure why it does not do that in this case.

    // in std.math.big.int.Managed.ensureCapacity
    pub fn ensureCapacity(self: *Managed, capacity: usize) !void {
    if (capacity <= self.limbs.len) {
        return;
    }
    const prev_limbs = self.limbs;
    std.log.err("{x}", .{prev_limbs[0]});
    self.limbs = try self.allocator.realloc(self.limbs, capacity);
    std.log.err("{x}", .{prev_limbs[0]});
    // ->
    [default] (err): 4800000000000000
    [default] (err): aaaaaaaaaaaaaaaa

  • When I try to do this myself in a test, it segfaults which is what I would expect

    test "dereferencing dead pointer" {
    const alloc = std.testing.allocator;
    const ptr1 = try alloc.alloc(usize, 4);
    ptr1[0] = 0x25;
    std.log.err("ptr1: {x}", .{ptr1[0]});
    const ptr2 = try alloc.realloc(ptr1, 5);
    std.log.err("ptr1: {x}", .{ptr1[0]});
    alloc.free(ptr2);
    }
    // ->
    Segmentation fault at address 0x70a7fc89e000
    a.zig:35:36: 0x103fe8a in test.dereferencing dead pointer (test)
    std.log.err("ptr1: {x}", .{ptr1[0]});
                                   ^

• It works correctly in ReleaseFast/ReleaseSmall because the invalidated memory is never zeroed, so the dead pointer still has the right values in it.