nimix 0.1.2

An allocator designed to be use by a GC
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

// The fuzzer bascially keeps an in memory copy of all values
//
// And does multi threaded mutation of the graph
use rand::prelude::*;
use std::collections::HashMap;
use std::alloc::Layout;
use std::num::NonZero;
use nimix::Heap;

unsafe impl Send for Fuzzer {}
unsafe impl Sync for Fuzzer {}

#[derive(Clone)]
struct Value {
    data: Vec<u8>,
}

impl Value {
    fn new(size: usize) -> Self {
        let mut data = Vec::with_capacity(size);
        let mut rng = rand::thread_rng();

        for _ in 0..size {
            let n: u8 = rng.gen();

            data.push(n);
        }

        Self {
            data
        }
    }
}

#[derive(Clone)]
struct Fuzzer {
    heap: Heap,
    values: HashMap<*const u8, Value>,
    marker: NonZero<u8>,
}

impl Fuzzer {
    fn new(heap: Heap, marker: NonZero<u8>) -> Self {
        Self {
            heap,
            values: HashMap::new(),
            marker
        }
    }

    fn assert(&self) {
        for (ptr, value) in self.values.iter() {
            for (i, v) in value.data.iter().enumerate() {
                unsafe { assert!(*ptr.add(i) == *v) }
            }
        }
    }

    fn alloc(&mut self) {
        let mut rng = rand::thread_rng();

        for _ in 0..ALLOC_LOOPS {
            let mut size = rng.gen_range(1..=4000);

            if size == 4000 {
                size = 1024 * 20;
            }

            let value = Value::new(size);

            unsafe {
                let power = rng.gen_range(0..=8);
                let align = 2usize.pow(power);
                let layout = Layout::from_size_align(size, align).unwrap();
                let dest = self.heap.alloc(layout).unwrap();

                for _ in 0..size {
                    let src = value.data.as_ptr();
                    std::ptr::copy_nonoverlapping(src, dest, size);
                }

                let coin_flip = rng.gen_range(0..100);
                if coin_flip < 5 {
                    self.values.insert(dest, value);
                    Heap::mark(dest, layout, self.marker).unwrap();
                } else {
                    // this is garbage and will be swept
                }
            }
        }
    }
}

const NUM_THREADS: usize = 16;
const MARK_LOOPS: usize = 10;
const SWEEP_LOOPS: usize = 20;
const ALLOC_LOOPS: usize = 500;

#[test]
fn fuzz() {
    let heap = Heap::new();

    for l in 1..=MARK_LOOPS {
        println!("=== MARK LOOP {l} ===");

        let marker = NonZero::new(l as u8).unwrap();
        let mut fuzzers = vec![];
        for _ in 0..NUM_THREADS {
            fuzzers.push(Fuzzer::new(heap.clone(), marker));
        }

        for _ in 0..SWEEP_LOOPS {
            let mut join_handles = vec![];

            for _ in 0..NUM_THREADS {
                let mut fuzzer = fuzzers.pop().unwrap();

                fuzzer.assert();
                
                let jh = std::thread::spawn(move || {
                    fuzzer.alloc();
                    fuzzer
                });

                join_handles.push(jh);
            }

            for jh in join_handles.into_iter() {
                fuzzers.push(jh.join().unwrap());
            }

            // sweep while fuzzers are marking!
            unsafe { heap.sweep(marker, || {}); }
        }

        let bytes: f64 = heap.size() as f64;
        let mb = (bytes / 1024.0) / 1024.0;

        println!("HEAP SIZE: {:.2} mb", mb);
    }
}