tlsf 1.1.0

An implementation of the Two-Level Segregated Fit (TLSF) allocator with optimized memory footprint
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

use crate::block::{Anchor, FreeBlock};
use crate::header::Header;
use crate::mapping::Indices;

impl<const FLL: usize> Header<FLL> {
    /// # Safety
    /// - `block` must be covered by `anchor`
    pub(super) unsafe fn push<'a>(&mut self, anchor: Anchor<'a>, block: FreeBlock<'a>) {
        let Indices { fl, sl } = Header::<FLL>::mapping_insert(block.usable_size());

        let free_list = unsafe { self.get_free_list(fl, sl) };

        if let Some(head) = free_list {
            #[cfg(all(test, not(miri)))]
            cov_mark::hit!(push_non_empty_list);

            let head = anchor.get_free_block(head);
            head.set_prev_free(anchor.offset_of(&block));
            block.set_next_free(anchor.offset_of(&head));
        } else {
            #[cfg(all(test, not(miri)))]
            cov_mark::hit!(push_empty_list);

            block.clear_next_free();
        }
        block.clear_prev_free();

        let new_free_list = Some(anchor.offset_of(&block));
        self.set_free_list(fl, sl, new_free_list);

        self.set_fl_bit(fl);
        self.set_sl_bit(fl, sl);
    }
}

#[cfg(test)]
mod tests {
    use core::mem::MaybeUninit;

    use super::*;
    use crate::helpers::FreeBlocks;

    #[test]
    fn one() {
        let mut header = Header::<1>::new();
        let mut memory = [MaybeUninit::uninit(); 3];
        let mut free_blocks = FreeBlocks::new(&mut memory);
        let anchor = free_blocks.anchor;
        unsafe {
            let block = free_blocks.next(4, true);

            {
                #[cfg(not(miri))]
                cov_mark::check!(push_empty_list);

                header.push(anchor, block);
            }
        }

        let blocks = unsafe { header.free_blocks(free_blocks.anchor) };
        assert_eq!(1, blocks.len());
        let [block] = blocks.try_into().unwrap();
        assert_eq!(4, block.usable_size());
        assert!(header.is_fl_bit_set(0));
        unsafe {
            assert!(header.is_sl_bit_set(0, 1));
        }
    }

    #[test]
    fn two_same_list() {
        let mut header = Header::<1>::new();
        let mut memory = [MaybeUninit::uninit(); 5];
        let mut free_blocks = FreeBlocks::new(&mut memory);
        let anchor = free_blocks.anchor;
        unsafe {
            let first = free_blocks.next(4, false);
            header.push(anchor, first);

            let second = free_blocks.next(4, true);
            {
                #[cfg(not(miri))]
                cov_mark::check!(push_non_empty_list);

                header.push(anchor, second);
            }
        }

        let blocks = unsafe { header.free_blocks(anchor) };
        assert_eq!(2, blocks.len());
        let [a, b] = blocks.try_into().unwrap();
        unsafe {
            assert_eq!(Some(anchor.offset_of(&a)), b.get_next_free());
            assert!(b.get_prev_free().is_none());

            assert!(a.get_next_free().is_none());
            assert_eq!(Some(anchor.offset_of(&b)), a.get_prev_free());
        }

        assert!(header.is_fl_bit_set(0));
        unsafe {
            assert!(header.is_sl_bit_set(0, 1));
        }
    }

    #[test]
    fn two_different_lists() {
        let mut header = Header::<1>::new();
        let mut memory = [MaybeUninit::uninit(); 6];
        let mut free_blocks = FreeBlocks::new(&mut memory);
        let anchor = free_blocks.anchor;
        unsafe {
            let first = free_blocks.next(4, false);
            header.push(anchor, first);

            let second = free_blocks.next(8, true);
            header.push(anchor, second);
        }

        let blocks = unsafe { header.free_blocks(anchor) };
        assert_eq!(2, blocks.len());
        assert_eq!(4, blocks[0].usable_size());
        assert!(header.is_fl_bit_set(0));
        unsafe {
            assert!(header.is_sl_bit_set(0, 1));
            assert!(header.is_sl_bit_set(0, 2));
        }
    }
}