Add debug assertions to discourage violating dealloc/resize safety

[SFBdragon]

I'm the author of another allocator for WASM, talc. I'm assuming this is still the default allocator in WASM?

In issues SFBdragon/talc#17 and SFBdragon/talc#24 I've had devs assume my allocator had a bug. Both times it turned out that the issue was with incorrectly sized layouts being passed to dealloc. Talc relies on the invariant stipulated by the safety contract of dealloc, but dlmalloc ignored this value entirely. The lol_alloc crate also relies on this, but will usually just "leak" memory instead.

I think this is a problem: it allows devs to write concealed bugs that only manifest if they override the global allocator (or a crate that depends on the buggy crate does so). This is completely avoidable, by having a debug assertion that the layout.size() equals the size stored internally by dlmalloc. Same goes for resize, I believe.

Side effects may include breaking some crates that violate the safety contract of dealloc/resize but have only been used with dlmalloc. I think this is necessary though. This implementation is setting an expectation as the default global allocator on WASM, and this expectation is a safety violation.

Happy to submit a PR, although I can't do it right now.

[alexcrichton]

I think that this would be great to have! A PR would be most welcome here too!

This crate is indeed currently the default allocator for wasm and the main wrinkle in this is that the standard library is distributed in binary form with debug assertions disabled. This means that by default users would not get this assertion as a debug assert.

I'm not personally opposed to making it a runtime assertion, however, a single branch probably isn't gonna break the bank anywhere. While technically a "breaking" change in the sense that it could break things Rust has experience doing changes like this. I think it would be reasonable to ensure that there's a message in the release notes for this and otherwise users can recover the prior behavior with their own global allocator customization.

[khoover]

While technically a "breaking" change in the sense that it could break things

You can argue this is just a patch, anything that would trip the assert was already undefined behaviour.

[SFBdragon]

I think that this would be great to have! A PR would be most welcome here too!

Great, I'll submit one soon.

Release-mode assertions sound good to me. Assertions are maximally runtime-predictable branches so it'll be negligible.

I agree with @alexcrichton and @khoover. I'd also posit that it's better to explicitly break code with UB instead of just leave it be. Better to cause a few headaches now, rather than even more later down the line? Idealistic, for sure, but let's give it a shot.

[SFBdragon]

Here's a first stab at it. Unfortunately I'm only able to assert the size is within a certain range given certain conditions. It's not nearly as cheap as I feel comfortable with either.

I'm not 100% clear on whether I should be multiplying the chunk overhead by two, given malloc, to the best of my knowledge, puts a usize at the top and bottom of each allocation (but the overhead function by default only returns size_of::<usize>()), but the chunk's size might not be storing the full header-to-header size either.

In summary, the chunk might have to include extra space for:

• alignment
• metadata
• space on either side of the allocation that's too small to be freed as its own chunk (if I'm not mistaken)

And so the upper limit check is a sum of the worst of the combined overhead.

I've ran both through Talc's random actions benchmark preliminarily but the results are a little too noisy to see a clear difference in between the current and patched version. I suppose that's a good thing, but I want to run both through the microbenchmarks as well, as that may make the runtime cost clearer.

Here's the diff:

diff --git a/src/dlmalloc.rs b/src/dlmalloc.rs
index a4b4b71..a889ef6 100644
--- a/src/dlmalloc.rs
+++ b/src/dlmalloc.rs
@@ -1163,6 +1163,18 @@ impl<A: Allocator> Dlmalloc<A> {
         }
     }
 
+    pub unsafe fn validate_size(&mut self, mem: *mut u8, size: usize, alignment: usize) {
+        let p = Chunk::from_mem(mem);
+        let psize = Chunk::size(p);
+
+        let min_overhead = self.overhead_for(p);
+        assert!(psize >= size + min_overhead);
+
+        if !Chunk::mmapped(p) {
+            assert!(psize <= size + self.min_chunk_size() * 2 + (mem::align_of::<usize>()).max(alignment) - 1 + min_overhead);
+        }
+    }
+
     pub unsafe fn free(&mut self, mem: *mut u8) {
         self.check_malloc_state();
 
diff --git a/src/lib.rs b/src/lib.rs
index b972ccb..2ec68b8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -143,7 +143,7 @@ impl<A: Allocator> Dlmalloc<A> {
     /// method contracts.
     #[inline]
     pub unsafe fn free(&mut self, ptr: *mut u8, size: usize, align: usize) {
-        drop((size, align));
+        self.0.validate_size(ptr, size, align);
         self.0.free(ptr)
     }
 
@@ -164,6 +164,7 @@ impl<A: Allocator> Dlmalloc<A> {
         old_align: usize,
         new_size: usize,
     ) -> *mut u8 {
+        self.0.validate_size(ptr, old_size, old_align);
         if old_align <= self.0.malloc_alignment() {
             self.0.realloc(ptr, new_size)
         } else {

Regardless, this'll need to be tested on a few different platforms to guard against false positives. But even that might be jumping the gun: is this degree of overhead acceptable in the first place?

[alexcrichton]

It's been a long time since I originally ported dlmalloc from C to Rust and I've long since lost the knowledge from that time, so I'm unfortunately not sure whether that check is right or not. As for benchmarks and/or the overhead, I don't have any in this repository but I do think it'd be good to measure just to be sure.

[SFBdragon]

Fair enough.

Turns out psize can be equal to size + min_overhead, just 8 bytes. Reread the documentation in dlmalloc.c, it checks out, so we're good there. There's a benign error in the original though. I don't need to add the full alignment, as the wasted space below the allocation will become its own chunk (unless its too small, but that's covered by adding on the min_chunk_size for the bottom (*2 for the top)). This makes the check a bit cheaper too.

Finally, I've run the old and new versions side-by-side through talc's microbenchmarks and while there's a small difference (look at deallocs only, the average is slightly higher, but it's hard to see with the graphs being displayed smaller on GitHub), which stays consistent with re-runs of the benchmark, so its probably not just chance/noise. It's a tiny difference though.

I'll open a PR with the changes in the meantime.