GlobalAlloc Trollocator can encounter segmentation fault and cause a panic.

[Elsklivet]

While messing around with test code using the GlobalAlloc I noticed that specific patterns of allocation/deallocation can result in segmentation faults (STATUS_ACCESS_VIOLATION on Windows) and infinite stack overflows of panics (since panic is using our allocator). I would normally just be like "well yeah, it's like, broken on purpose???" except that this is pretty consistent. You can run it over and over and it always fails in the same patterns, there's no RNG.

Here's some example main code that causes an infinite panic:

let _s = format!("hello world");
println!("{}", _s);
unsafe { println!("{}", ALLOCATOR.get_alloced_blocks()) };

let mut vec = vec![0u8];

for i in 0..=128u8 {
    vec.push(i as u8);
}

for i in 0..=127u8 {
    vec.push(i as u8);
}

let _s2 = format!("hello world 2"); // <----- this allocation can be moved to be between the loops to the same effect
println!("{}", _s2);                // commenting this allocation out, the program succeeds.

unsafe { println!("{}", ALLOCATOR.get_alloced_blocks()) };

core::mem::drop(vec); // <----- comment this out and the error changes to a normal segmentation fault

unsafe { println!("{}", ALLOCATOR.get_alloced_blocks()) };

I haven't really thought enough about what could be going on to have an idea of why this might be happening, but it probably should be fixed.

Output appears as follows:

hello world
5
error: process didn't exit successfully: `target\debug\trolloc.exe` (exit code: 0xc0000005, STATUS_ACCESS_VIOLATION)

[Elsklivet]

I started work on 5-globalalloc-trollocator-can-encounter-segmentation-fault to address this. I've added code to print the heap and found that coalesce is just not working. Printing after deallocation should finish, I sometimes see output like this:

--Allocating 512 (512) bytes
--Allocated block at 0x7ff7d0f8d8c0
--Deallocating 0x7ff7d0f8d7a8
--+ 0 @ 0x7ff7d0f8d150 (size: 16, free: false)
--+ 1 @ 0x7ff7d0f8d178 (size: 48, free: false)
--+ 2 @ 0x7ff7d0f8d1c0 (size: 64, free: false)
--+ 3 @ 0x7ff7d0f8d218 (size: 16, free: false)
--+ 4 @ 0x7ff7d0f8d240 (size: 1024, free: false)
--+ 5 @ 0x7ff7d0f8d658 (size: 72, free: true)   <----\
--+ 6 @ 0x7ff7d0f8d6b8 (size: 216, free: true)  <-----+ This should be impossible if coalesce is properly coalescing.
--+ 7 @ 0x7ff7d0f8d7a8 (size: 256, free: true)  <----/
--+ 8 @ 0x7ff7d0f8d8c0 (size: 512, free: false)
--+ 9 @ 0x7ff7d0f8dad8 (size: 63072, free: true)

I can look at coalesce next. dealloc is the last thing that seems to be called before the program segfaults. One thing that I think I'm noticing is that the underlying code (my code) for the allocator is calling into functions that themselves require allocation. I need to shave down use of Rust std APIs. I think they're causing a lot of trouble. The solution to this might ultimately be #![no_std].

As an aside, but I noticed it is never actually doing any trolling? Not sure if the condition I have is just exceedingly rare, but I should probably make it easier to get trolled, that's kind of the point.

[Elsklivet]

Commit f18e239 fixes this issue, I think. Coalesce was incorrectly not updating the previous pointer of the next block before trying to do a coalesce on it too (or, ever really) leading to future coalesces pointing into the middle of nowhere and blocks thinking the heap was smaller than it really was.

Resolving.