How to test for double frees

gap · April 28, 2024, 2:27pm

I am trying to figure out how to detect a double free. The following code crashes with a segmentation fault when I run the test. I would like it to fail the test with information about where the problem might be.

const std = @import("std");

fn allocate_memory(allocator: std.mem.Allocator) ![]u8 {
    const memory = try allocator.alloc(u8, 100);

    errdefer allocator.free(memory);
    return memory;
}

fn memoryTest(allocator: std.mem.Allocator, result: usize) !void {
    // Allocate 100 units of 8 bits (u8)
    const memory = try allocate_memory(allocator);
    defer allocator.free(memory);
    // Comment in the following line to create a double free
    defer allocator.free(memory);

    try std.testing.expectEqual(@as(usize, result), memory.len);
}

test "allocation" {
    // Select an allocator to use
    const allocator = std.testing.allocator;

    try std.testing.checkAllAllocationFailures(
        allocator,
        memoryTest,
        .{ 100 },
    );
}

Can anyone help me write a test that reports a double free?

My next challenge will be a test for use after free.

Thanks!

 -Gary

dimdin · April 28, 2024, 3:09pm

std.mem.Allocator.free before actually freeing the memory, sets the bytes to undefined.
When the second free happens it tries to write to the freed memory and a segmentation fault happens, because this is a use after free.

There is a TODO in free for set memory to undefined in allocator implementations rather than interface that might fix this problem.

gap · April 28, 2024, 4:59pm

Dimdin,

Thanks for your response and you comment on the issue 4298.

My goal is to see if I can get a test to detect a double free. If I can’t then I will open an issue in the issue tracker. There should be good test tooling for

Memory Leaks
Double Frees
Use after free

Gary

AndrewCodeDev · April 28, 2024, 5:18pm

For memory leaks, you can use the deinit method on the GPA to see if you’ve actually freed everything. You can look at how that’s implemented here: zig/lib/std/heap/general_purpose_allocator.zig at master · ziglang/zig · GitHub

if (gpa.deinit() == .leak) { ...

Use after free is hard because it exists outside of the context of the allocator itself. You’d have to store some state that says whether or not something has been freed and then check onsite that the thing is being used. Unfortunately, that’s very hard for raw slices/pointers. What checks the following?

_ = slice[i]; // slice has already been freed

You’d have to wrap it with an accessor that does some sort of stateful debug solution…

inline pub fn access(slice: anytype, index: usize) std.meta.Child(@TypeOf(slice)) {
  if (debug) { // you can get this info in @import("builtin")
      // do your check here
  } 
  return slice[i];
}

// later...

const x = access(slice, i);

You’d need a setter for this approach too (or return a pointer to the element)… not very ergonomic but you could do checks with this.

Like @dimdin pointed out, if you’re checking for a double free at the time you’re passing the slice to the allocator, it’s too late. That’s a known issue with the allocator interface as was mentioned.

Edit: see How to test for double frees - #11 by squeek502

You could do something similar to the access method above for freeing but again… not very ergonomic.

dimdin · April 28, 2024, 5:54pm

const std = @import("std");

fn leak(allocator: std.mem.Allocator) !void {
    _ = try allocator.alloc(u8, 80);
}

fn use_after_free(allocator: std.mem.Allocator) !void {
    const buf = try allocator.alloc(u8, 80);
    allocator.free(buf);
    buf[0] = 0;
}

fn double_free(allocator: std.mem.Allocator) !void {
    const buf = try allocator.alloc(u8, 80);
    allocator.free(buf);
    // allocator.free(buf);
    allocator.rawFree(buf, std.math.log2(@alignOf(@TypeOf(buf))), @returnAddress());
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer {
        if (gpa.deinit() == .leak) {
            std.debug.print("LEAKED MEMORY\n", .{});
        }
    }
    const allocator = gpa.allocator();
    try leak(allocator);
    // try use_after_free(allocator);
    // try double_free(allocator);
}

As is the program, calls leak, detects the leak and displays:

error(gpa): memory address 0x7fb94500c000 leaked: 
/home/din/test.zig:4:28: 0x10363b2 in leak (test)
    _ = try allocator.alloc(u8, 80);
                           ^
/home/din/test.zig:29:13: 0x10366cc in main (test)
    try leak(allocator);
            ^
/home/din/zig-0.12.0/lib/std/start.zig:511:37: 0x10362c5 in posixCallMainAndExit (test)
            const result = root.main() catch |err| {
                                    ^
/home/din/zig-0.12.0/lib/std/start.zig:253:5: 0x1035de1 in _start (test)
    asm volatile (switch (native_arch) {
    ^

LEAKED MEMORY

Note: that you get a full stack trace that points to the leaked allocation.

By commenting the call to leak and uncommenting the call to use_after_free

    // try leak(allocator);
    try use_after_free(allocator);

A segmentation fault is generated with a stack trace from the location that used the free memory.

Segmentation fault at address 0x7f21e1e1c000
/home/din/test.zig:10:8: 0x103642a in use_after_free (test)
    buf[0] = 0;
       ^
/home/din/test.zig:30:23: 0x10369cc in main (test)
    try use_after_free(allocator);
                      ^
/home/din/zig-0.12.0/lib/std/start.zig:511:37: 0x10362c5 in posixCallMainAndExit (test)
            const result = root.main() catch |err| {
                                    ^
/home/din/zig-0.12.0/lib/std/start.zig:253:5: 0x1035de1 in _start (test)
    asm volatile (switch (native_arch) {
    ^

The normal double_free case is using allocator.free(buf); twice; it is also a segmentation fault that gives a stack trace.
When calling rawFree:

thread 765670 panic: Invalid free
/home/din/zig-0.12.0/lib/std/heap/general_purpose_allocator.zig:643:21: 0x106c07c in freeLarge (test)
                    @panic("Invalid free");
                    ^
/home/din/zig-0.12.0/lib/std/heap/general_purpose_allocator.zig:854:31: 0x103b050 in free (test)
                self.freeLarge(old_mem, log2_old_align, ret_addr);
                              ^
/home/din/zig-0.12.0/lib/std/mem/Allocator.zig:98:28: 0x1036492 in double_free (test)
    return self.vtable.free(self.ptr, buf, log2_buf_align, ret_addr);
                           ^
/home/din/test.zig:31:20: 0x10369dc in main (test)
    try double_free(allocator);
                   ^
/home/din/zig-0.12.0/lib/std/start.zig:511:37: 0x10362c5 in posixCallMainAndExit (test)
            const result = root.main() catch |err| {
                                    ^
/home/din/zig-0.12.0/lib/std/start.zig:253:5: 0x1035de1 in _start (test)
    asm volatile (switch (native_arch) {
    ^

a panic “Invalid free” with a stack trace showing the double_free call.
Note: You must not call rawFree! allocator.free is the correct API. I am using rawFree to demonstrate that zig allocator knows about the double free, but currently it is not working correctly.

dude_the_builder · April 28, 2024, 6:02pm

I think taht if you try all these within a test "foo" { ... } block using the std.testing.allocator it should behave the same since that’s just a pre-configured instance of the GPA, no?

dimdin · April 28, 2024, 6:04pm

Yes, std.testing.allocator is an instance of GeneralPurposeAllocator usable only when testing.
Actual source in std.testing:

pub const allocator = allocator_instance.allocator()

pub var allocator_instance = b: {
    if (!builtin.is_test)
        @compileError("Cannot use testing allocator outside of test block");
    break :b std.heap.GeneralPurposeAllocator(.{}){};
}

gap · April 28, 2024, 6:05pm

Andrew,

Thanks for you response. It is helpful. I want to be sure I understand what is going on and how to do things properly in Zig. I am a newbie.

It sounds like the way to track down double free’s is to use a c_allocator and then run valgrind on the code.

Gary

gap · April 28, 2024, 6:10pm

Dimdin,

Thanks for your response and your code and verifying that both double frees and use after free create segmentation faults. I think detection should be added to the tooling because they are difficult bugs to track down. AndrewCodeDev’s idea should work, but is not built in and not ergonomic, which means it is not a general purpose solution.

Gary

dimdin · April 28, 2024, 6:20pm

Also note that zig integrates with valgrind.
Zig by default sends valgrind client requests to annotate memory marked as undefined (undefined=0xAA=alternating 0 and 1 bits).

squeek502 · April 28, 2024, 8:02pm

GeneralPurposeAllocator does have support for detecting double frees:

github.com

ziglang/zig/blob/25f1526fe6424cef156724977b75a5b80a3d5833/lib/std/heap/general_purpose_allocator.zig#L493-L503


      
          fn reportDoubleFree(ret_addr: usize, alloc_stack_trace: StackTrace, free_stack_trace: StackTrace) void {
              var addresses: [stack_n]usize = [1]usize{0} ** stack_n;
              var second_free_stack_trace = StackTrace{
                  .instruction_addresses = &addresses,
                  .index = 0,
              };
              std.debug.captureStackTrace(ret_addr, &second_free_stack_trace);
              log.err("Double free detected. Allocation: {} First free: {} Second free: {}", .{
                  alloc_stack_trace, free_stack_trace, second_free_stack_trace,
              });
          }

but it needs the GeneralPurposeAllocator.Config to have retain_metadata = true and never_unmap = true:

github.com

ziglang/zig/blob/25f1526fe6424cef156724977b75a5b80a3d5833/lib/std/heap/general_purpose_allocator.zig#L142-L152


      
          /// This is a temporary debugging trick you can use to turn segfaults into more helpful
          /// logged error messages with stack trace details. The downside is that every allocation
          /// will be leaked, unless used with retain_metadata!
          never_unmap: bool = false,
          
          /// This is a temporary debugging aid that retains metadata about allocations indefinitely.
          /// This allows a greater range of double frees to be reported. All metadata is freed when
          /// deinit is called. When used with never_unmap, deliberately leaked memory is also freed
          /// during deinit. Currently should be used with never_unmap to avoid segfaults.
          /// TODO https://github.com/ziglang/zig/issues/4298 will allow use without never_unmap
          retain_metadata: bool = false,

Test code:

const std = @import("std");

test "double free" {
    var gpa = std.heap.GeneralPurposeAllocator(.{
        .safety = true,
        .never_unmap = true,
        .retain_metadata = true,
    }){};
    defer std.debug.assert(gpa.deinit() == .ok);
    const allocator = gpa.allocator();

    const alloc = try allocator.alloc(u8, 8);
    allocator.free(alloc);
    allocator.free(alloc);
}

For me on Windows this is outputting:

[gpa] (err): Double free detected. Allocation:
 First free:
 Second free:
C:\Users\Ryan\Programming\Zig\tmp\doublefree.zig:10:19: 0x7510f5 in test.double free (test.exe.obj)
    allocator.free(alloc);
                  ^
C:\Users\Ryan\Programming\Zig\zig\lib\compiler\test_runner.zig:158:25: 0x75bc1a in mainTerminal (test.exe.obj)
        if (test_fn.func()) |_| {
                        ^
C:\Users\Ryan\Programming\Zig\zig\lib\compiler\test_runner.zig:35:28: 0x751998 in main (test.exe.obj)
        return mainTerminal();
                           ^
C:\Users\Ryan\Programming\Zig\zig\lib\std\start.zig:350:53: 0x751713 in WinStartup (test.exe.obj)
    std.os.windows.ntdll.RtlExitUserProcess(callMain());
                                                    ^
???:?:?: 0x7ff91a157343 in ??? (KERNEL32.DLL)
???:?:?: 0x7ff91c0e26b0 in ??? (ntdll.dll)

unsure if the first free stack trace being empty is a Windows-only bug or a general regression.

(note: it looks like I may have accidentally regressed retain_metadata in GeneralPurposeAllocator: Considerably improve worst case performance by squeek502 · Pull Request #17383 · ziglang/zig · GitHub; if there are two allocations of 8 bytes in the above test, it hits an assertion failure during gpa.deinit())

AndrewCodeDev · April 28, 2024, 8:39pm

Nice! Lots of hidden gems with the GPA. I’ll update my comment.

dimdin · April 28, 2024, 9:21pm

Unfortunately by disabling unmap you loose the use after free crash.
Valgrind can catch this, because zig sets the freed area to undefined.

gap · April 29, 2024, 10:39pm

squeek502,

Thanks for your response. It is exactly what I am looking for!