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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#[cfg(test)]
use crate::block::FreeBlock;
use crate::block::{Anchor, Offset};
use crate::header::Header;
use crate::{Block, Tlsf};

impl<const FLL: usize> Tlsf<'_, FLL> {
    /// Returns an iterator over all the memory blocks managed by the allocator
    ///
    /// The iteration order is from lowest memory address to highest memory address
    ///
    /// While the iterator is in scope it's not possible to request memory or return memory to the
    /// allocator
    pub fn blocks(&self) -> Blocks {
        if let Some(anchor) = self.anchor {
            self.header.blocks(anchor)
        } else {
            Blocks {
                anchor: Anchor::new(&mut []),
                current: None,
            }
        }
    }

    #[cfg(test)]
    pub fn free_blocks(&self) -> Vec<FreeBlock> {
        let Some(anchor) = self.anchor else {
            return vec![];
        };

        unsafe { self.header.free_blocks(anchor) }
    }
}

impl<const FLL: usize> Header<FLL> {
    fn blocks<'a>(&self, anchor: Anchor<'a>) -> Blocks<'a> {
        Blocks {
            anchor,
            current: Some(unsafe { Offset::compress(4) }),
        }
    }

    #[cfg(test)]
    pub unsafe fn free_blocks<'a>(&self, anchor: Anchor<'a>) -> Vec<FreeBlock<'a>> {
        self.blocks(anchor)
            .filter_map(|block| unsafe { block.try_into_free(anchor) })
            .collect()
    }
}

pub struct Blocks<'a> {
    anchor: Anchor<'a>,
    current: Option<Offset>,
}

impl<'a> Iterator for Blocks<'a> {
    type Item = Block<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let offset = self.current?;
        unsafe {
            let block = self.anchor.block_at(offset);
            let next = self.anchor.next_phys_block(&block);
            self.current = next.map(|block| self.anchor.offset_of(&block));
            Some(block)
        }
    }
}

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

    use super::*;

    #[test]
    fn it_works() {
        let mut tlsf = Tlsf::<1>::empty();
        let mut memory = [MaybeUninit::uninit(); 7];
        tlsf.initialize(&mut memory);

        let blocks = tlsf.blocks().collect::<Vec<_>>();
        assert_eq!(1, blocks.len());
        assert_eq!(24, blocks[0].total_size());

        let min_layout = Layout::new::<u8>();
        let first = tlsf.memalign(min_layout).unwrap();
        assert_eq!(1, first.len());

        let blocks = tlsf.blocks().collect::<Vec<_>>();
        assert_eq!(2, blocks.len());
        let [a, b] = blocks.try_into().unwrap();

        // OK to mutate memory previously returned by the allocator while the block _headers_ are
        // in scope
        first.iter_mut().for_each(|mu| {
            mu.write(!0);
        });

        assert!(!a.is_free());
        assert_eq!(4, a.usable_size());

        assert!(b.is_free());
        assert_eq!(16, b.total_size());

        let second = tlsf.memalign(min_layout).unwrap();
        assert_eq!(1, second.len());

        let blocks = tlsf.blocks().collect::<Vec<_>>();
        assert_eq!(3, blocks.len());
        let [a, b, c] = blocks.try_into().unwrap();

        first.iter_mut().for_each(|mu| {
            mu.write(!0);
        });
        second.iter_mut().for_each(|mu| {
            mu.write(!0);
        });

        assert!(!a.is_free());
        assert_eq!(4, a.usable_size());

        assert!(!b.is_free());
        assert_eq!(4, b.usable_size());

        assert!(c.is_free());
        assert_eq!(8, c.total_size());

        unsafe { tlsf.free(NonNull::from(first).cast()) }

        let blocks = tlsf.blocks().collect::<Vec<_>>();
        assert_eq!(3, blocks.len());
        let [a, b, c] = blocks.try_into().unwrap();

        second.iter_mut().for_each(|mu| {
            mu.write(!0);
        });

        assert!(a.is_free());
        assert_eq!(4, a.usable_size());

        assert!(!b.is_free());
        assert_eq!(4, b.usable_size());

        assert!(c.is_free());
        assert_eq!(8, c.total_size());
    }

    #[test]
    fn no_anchor() {
        let mut tlsf = Tlsf::<1>::empty();
        let mut memory = [MaybeUninit::uninit(); 2];
        tlsf.initialize(&mut memory);

        assert!(tlsf.blocks().next().is_none());
    }
}