Check for pointers that appear twice in the same magazine of freed objects

[pkhuong]

We probably can't afford to check for double frees in the fast path, but a batch dup check when we flush a full magazine might be doable?

[mxxo]

Did you have something like this (naive impl) in mind?

diff --git a/src/magazine.rs b/src/magazine.rs
index 63c73c6..e99ba3e 100644
--- a/src/magazine.rs
+++ b/src/magazine.rs
@@ -398,7 +398,20 @@ impl crate::class::ClassInfo {
 
         if mag.is_empty() {
             self.rack.release_empty_magazine(mag);
-        } else if mag.is_full() {
+            return;
+        }
+
+        let mut set = std::collections::HashSet::new();
+        for i in 0..mag.0.len() {
+            if let Some(alloc) = mag.0.nth(i) {
+                let unique = set.insert(alloc.get().as_ptr());
+                if !unique {
+                    panic!("double free of {:p}", alloc.get().as_ptr());
+                }
+            }
+        }
+
+        if mag.is_full() {
             self.full_mags.push(mag);
         } else {
             self.partial_mags.push(mag);

This catches the following double free:

use slitter::{Class, ClassConfig};
use std::alloc::Layout;

struct C {
    a: i16,
    b: i32,
}

fn main() {
    let class_allocator = Class::new(ClassConfig {
        name: None,
        layout: Layout::new::<C>(),
        zero_init: true,
        mapper_name: None,
    })
    .unwrap();

    let alloc = class_allocator.allocate().unwrap();
    let double_free = alloc;

    class_allocator.release(alloc);
    class_allocator.release(double_free);
}

thread 'main' panicked at 'double free of 0x7f1f80000000', /home/max/projects/slitter/src/magazine.rs:409:21
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
fatal runtime error: failed to initiate panic, error 5
Aborted (core dumped)

When check-contracts is enabled this is caught already:

thread 'main' panicked at 'Pre-condition of release violated: Released blocks must match the class and not double-free.: debug_allocation_map :: mark_released(self, & block).is_ok()', /home/max/projects/slitter/src/individual.rs:54:16
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[pkhuong]

Yes, definitely something like that! I think ClassInfo::clear_magazine is a better place, since we're mostly concerned with catching user errors and not implementation bugs. We could however reuse the same logic in contracts, around ClassInfo::release_magazine.

The dup-checking logic has to be efficient. I think we'll want to have that in a separate file to make it easier to test and benchmark. Magazines can't hold more than 30 pointers, so we should be able to do something nice. A vectorised sort might work well, for example? @damageboy might have some ideas?

[pkhuong]

@pervognsen reports ~4.5 cycles/element to clear a small bitmap and populate it with indexes computed with multiply-shift hash (https://en.wikipedia.org/wiki/Universal_hashing#Avoiding_modular_arithmetic). That sounds reasonable to me, and doesn't involve anything exotic or unsafe.

Of course, there could still be false positive, but a 1024-2048 bit map should have rare enough collisions.

[mxxo]

And I guess if there's a collision we could then fall back to a slower, fully accurate method to ensure there's no false positives overall.

[pervognsen]

Yeah, my mock-up used 2048 bits and fell back to a nested-loop slow path. But I did the math and the false positive rate with 30 elements and 2048 slots is probably still too high at around 20%. But you can fix that by running the same code again with an independent hash seed. The false positive probability stacks multiplicatively, so the chance of getting a false positive a second time is only 4%. And given that the slow path is still pretty darn fast, hitting it 4% is probably fine.

[pkhuong]

Yeah, the orders of magnitude above make sense to me. We can compute multiple hashes with the same multiply-shift, although low-order bits are of lesser quality; I think it makes more sense to unconditionally perform 2-3 bitmap checks at once?

[mxxo]

Is there a potential issue here because allocations in a loop will be close together? Barring an issue with my quick implementation here, nearby allocations all get hashed with multiply-shift to the same value:

use slitter::{Class, ClassConfig};
use std::alloc::Layout;

struct C {
    a: i16,
    b: i32,
}

/// Hash `x` with seed `a` using multiply-shift to (2^11) 2048 bins.
fn hash(x: usize, a: usize) -> usize {
    a.wrapping_mul(x) >> (usize::BITS - 11)
}

fn main() {
    let class_allocator = Class::new(ClassConfig {
        name: None,
        layout: Layout::new::<C>(),
        zero_init: true,
        mapper_name: None,
    })
    .unwrap();

    let seed = 1265; // 2^11 = 2048 / golden ratio ~= 1265
    for _ in 0..30 {
        let alloc = class_allocator.allocate().unwrap();
        println!("allocated {:p}, hashed to {:?}", alloc, hash(alloc.as_ptr() as usize, seed));
    }
}

allocated 0x7f2b80000000, hashed to 19
allocated 0x7f2b800000f0, hashed to 19
allocated 0x7f2b800000e8, hashed to 19
...
allocated 0x7f2b80000010, hashed to 19

[pkhuong]

The multiplier is too small: it should be a pseudo-random odd usize value. If you want to use phi, you have to divide 2^64, or multiply by 2^64 and take the low bits. FWIW, I think it makes more sense to let the multiplier vary at runtime: we could regenerate it whenever we find a false positive.