rulloc/freelist.rs
1use std::ptr::NonNull;
2
3use crate::{
4 block::Block,
5 header::Header,
6 list::{LinkedList, Node},
7};
8
9/// See [`crate::block::Block`] and [`crate::region::Region`] first.
10/// When a block is free we'll use the content of the block to store a free
11/// list, that is, a linked list of _only_ free blocks. Since we want a doubly
12/// linked list, we need to store 2 pointers, one for the previous block and
13/// another one for the next free block. This is how a free block would look
14/// like in memory:
15///
16/// ```text
17/// +----------------------------+
18/// | pointer to next block | <--+
19/// +----------------------------+ |
20/// | pointer to prev block | |
21/// +----------------------------+ | Node<Block> struct.
22/// | rest of fields | |
23/// +----------------------------+ |
24/// | ...... | <--+
25/// +----------------------------+
26/// | pointer to next free block | <--+
27/// +----------------------------+ | Node<()> struct.
28/// | pointer to prev free block | <--+
29/// +----------------------------+
30/// | Rest of user data | <--+
31/// | ...... | | Rest of content. This could be 0 bytes.
32/// | ...... | <--+
33/// +----------------------------+
34/// ```
35///
36/// # Free blocks positioning
37///
38/// Free blocks may point to blocks located in different regions, since _all_
39/// free blocks are linked. See this representation:
40///
41/// ```text
42/// Points to free block in next region Points to same region
43/// +--------------------------------------+ +-----------------------+
44/// | | | |
45/// +--------+-----|------------------+ +--------+---|---|-----------------------|-----+
46/// | | +---|---+ +-------+ | | | +-|---|-+ +-------+ +---|---+ |
47/// | Region | | Free | -> | Block | | ---> | Region | | Free | -> | Block | -> | Free | |
48/// | | +-------+ +-------+ | | | +-------+ +-------+ +-------+ |
49/// +--------+------------------------+ +--------+-------------------------------------+
50/// ```
51///
52/// Also, note that the first free block doesn't have to be located in the
53/// first region, and the last free block doesn't have to be located in the last
54/// region either. Free blocks can be located anywhere. Consider this case:
55///
56/// 1. We get a new region from the kernel 4096 bytes in length.
57///
58/// 2. We create one single block in this region where we can allocate a maximum
59/// of 4096 - R - B bytes, where R = [`crate::region::REGION_HEADER_SIZE`] and
60/// B = [`crate::block::BLOCK_HEADER_SIZE`]. This would be the current state:
61///
62/// ```text
63///
64/// +--------+-------------------------------------+
65/// | | +---------------------------------+ |
66/// | Region | | Big Free Block | |
67/// | | +---------------------------------+ |
68/// +--------+-------------------------------------+
69/// ^
70/// |
71/// +--- Head of the free list points to this block.
72/// Tail also points here (only one node).
73/// ```
74///
75/// 3. The block takes up all the space, if a subsequent allocation is smaller
76/// than the block size, then the block will be split in two different blocks
77/// and the second block will become the first and only free block.
78///
79/// ```text
80/// +--------+-------------------------------------+
81/// | | +-------+ +--------------------+ |
82/// | Region | | Alloc | -> | Free | |
83/// | | +-------+ +--------------------+ |
84/// +--------+-------------------------------------+
85/// ^
86/// |
87/// +--- Head and tail of the free list.
88/// ```
89///
90/// 4. If the user makes another allocation that is smaller than our free block,
91/// the splitting algorithm does its job again:
92///
93/// ```text
94/// +--------+-------------------------------------+
95/// | | +-------+ +-------+ +-------+ |
96/// | Region | | Alloc | -> | Alloc | -> | Free | |
97/// | | +-------+ +-------+ +-------+ |
98/// +--------+-------------------------------------+
99/// ^
100/// |
101/// +--- Head and tail.
102/// ```
103///
104/// 5. Now the user deallocates the first block, se we have 2 free blocks:
105///
106/// ```text
107/// +-------------------------+
108/// | |
109/// +--------+-----|-------------------------|-----+
110/// | | +---|---+ +-------+ +---|---+ |
111/// | Region | | Free | -> | Alloc | -> | Free | |
112/// | | +-------+ +-------+ +-------+ |
113/// +--------+-------------------------------------+
114/// ^ ^
115/// | |
116/// +--- Tail +--- Head
117/// ```
118///
119/// At this point, if the user makes another allocation that doesn't fit any of
120/// the two free blocks that we have we'll need to request another region, so
121/// the current tail will point to the new tail located in the new region.
122/// Because of this, we cannot make any assumptions regarding positioning when
123/// it comes to free blocks. All this process of splitting blocks, merging them
124/// again and updating the free list is handled at [`crate::bucket::Bucket`].
125///
126/// # Free list implementation
127///
128/// Now, going back to the inernals of the free list, there's a little catch. As
129/// you can see we use [`Node<()>`] to represent a node of the free list. That's
130/// because, first of all, we want to reuse the [`LinkedList<T>`]
131/// implementation. Secondly, there's no additional metadata associated to free
132/// blocks other than pointers to previous and next free blocks. All other data
133/// such as block size or region is located in the [`Node<Block>`] struct right
134/// above [`Node<()>`], as you can see in the memory representation.
135///
136/// The [`Node<T>`] type stores the pointers we need plus some other data, so if
137/// we give it a zero sized `T` we can reuse it for the free list without
138/// declaring a new type or consuming additional memory. But this has some
139/// implications over simply storing `*mut Node<Block>` in the free block
140/// content space.
141///
142/// [`Node<T>`] can only point to instances of itself, so [`Node<()>`] can only
143/// point to [`Node<()>`], otherwise [`LinkedList<T>`] implementation won't work
144/// for this type. Therefore, the free list doesn't contain pointers to the
145/// headers of free blocks, it contains pointers to the *content* of free
146/// blocks. If we want to obtain the actual block header given a [`Node<()>`],
147/// we have to substract [`crate::block::BLOCK_HEADER_SIZE`] to its address and
148/// cast to [`Header<Block>`] or [`Node<Block>`].
149///
150/// It's not so intuitive because the free list should be [`LinkedList<Block>`],
151/// it's list of free blocks after all, so it should point to blocks themselves.
152/// But with this implementation it becomes [`LinkedList<()>`] instead. This,
153/// however, allows us to reuse [`LinkedList<T>`] without having to implement
154/// traits for different types of nodes to give us their next and previous or
155/// having to rely on macros to generate code for that. The only incovinience is
156/// that the free list points to content of free blocks instead of their header,
157/// but we can easily obtain the actual header.
158///
159/// Note that generally we never store pointers to the contents of a block
160/// because the user also has pointers to those addresses, so we don't want
161/// aliasing because that would probably cause issues with references. However,
162/// if a block has been deallocated, we can actually point to its content
163/// because the user doesn't have pointers to the content address anymore, all
164/// of them should have been dropped. If users still maintain pointers to
165/// deallocated addresses they will run into use after free, so they better not
166/// use such pointers! For finding bugs related to this kind of problems,
167/// [Miri](https://github.com/rust-lang/miri) is really helpful.
168pub(crate) type FreeListNode = Node<()>;
169
170/// See [`FreeListNode`].
171pub(crate) type FreeList = LinkedList<()>;
172
173impl FreeList {
174 /// Helper function for adding blocks to the free list. `block` must be
175 /// valid.
176 pub unsafe fn append_block(&mut self, mut block: NonNull<Header<Block>>) {
177 self.append((), Header::content_address_of(block));
178 block.as_mut().data.is_free = true;
179 }
180
181 /// Removes `block` from the free list. `block` must be valid.
182 pub unsafe fn remove_block(&mut self, mut block: NonNull<Header<Block>>) {
183 self.remove(Header::content_address_of(block).cast());
184 block.as_mut().data.is_free = false;
185 }
186
187 /// Returns a reference to the block header of the first block in the free
188 /// list. Not used internally, for now we only need it for testing.
189 #[cfg(test)]
190 pub unsafe fn first_free_block(&self) -> Option<&Header<Block>> {
191 self.first().map(|node| {
192 let block = Header::<Block>::from_free_list_node(node);
193 block.as_ref()
194 })
195 }
196
197 /// Free list nodes are a little bit harder to iterate because they don't
198 /// point to block headers, so let's make it easier.
199 pub unsafe fn iter_blocks(&self) -> impl Iterator<Item = NonNull<Header<Block>>> {
200 self.iter()
201 .map(|node| Header::<Block>::from_free_list_node(node))
202 }
203}