safa_api/
alloc.rs

1//! This module implements a high-level userspace allocator
2//! which internally uses the [`crate::syscalls::syssbrk`] syscall
3//! to allocate memory
4
5use crate::raw::{NonNullSlice, Optional};
6
7use super::syscalls;
8use core::{alloc::GlobalAlloc, cell::UnsafeCell, ptr::NonNull};
9
10#[derive(Debug, Default)]
11struct Block {
12    free: bool,
13    next: Option<NonNull<Block>>,
14    data_len: usize,
15}
16
17impl Block {
18    /// Asks the system for a new memory Block with a size big enough to hold `data_len` bytes
19    pub fn create(data_len: usize) -> Option<NonNull<Self>> {
20        let size = data_len + size_of::<Block>();
21        let size = size.next_multiple_of(align_of::<Block>());
22        assert!(size <= isize::MAX as usize);
23
24        let ptr = get_data_break() as *mut Block;
25        syscalls::process_misc::sbrk(size as isize).ok()?;
26        unsafe {
27            *ptr = Self {
28                free: true,
29                data_len: size - size_of::<Block>(),
30                ..Default::default()
31            };
32            Some(NonNull::new_unchecked(ptr))
33        }
34    }
35
36    #[inline(always)]
37    /// Gets the Block metadata of a data ptr,
38    /// unsafe because the pointer had to be made by calling `[Block::data_from_ptr]` on a valid pointer, otherwise the returned value is invalid
39    pub unsafe fn block_from_data_ptr(data: NonNull<u8>) -> NonNull<Self> {
40        unsafe { NonNull::new_unchecked((data.as_ptr() as *mut Block).offset(-1)) }
41    }
42
43    #[inline(always)]
44    /// Gets the data ptr from a pointer to Block
45    pub unsafe fn data_from_ptr(ptr: *const Self) -> NonNull<[u8]> {
46        unsafe {
47            let length = (*ptr).data_len;
48            let ptr_to_data = ptr.offset(1) as *const u8 as *mut u8;
49            NonNull::new_unchecked(core::slice::from_raw_parts_mut(ptr_to_data, length) as *mut [u8])
50        }
51    }
52}
53
54pub struct SystemAllocator {
55    head: Option<NonNull<Block>>,
56}
57
58fn get_data_break() -> *mut u8 {
59    // Should never fail
60    unsafe { syscalls::process_misc::sbrk(0).unwrap_unchecked() }
61}
62
63impl SystemAllocator {
64    const fn new() -> Self {
65        Self { head: None }
66    }
67
68    /// tries to find a block with enough space for `data_len` bytes
69    #[inline]
70    fn try_find_block(&self, data_len: usize) -> Option<NonNull<Block>> {
71        // To optimize the search for exact size we have to manipulate the data_len a bit
72        let size = data_len + size_of::<Block>();
73        let size = size.next_multiple_of(align_of::<Block>());
74        let data_len = size - size_of::<Block>();
75
76        let mut current = self.head;
77        let mut best_block: Option<(NonNull<Block>, usize)> = None;
78
79        while let Some(block_ptr) = current {
80            let block = unsafe { &*block_ptr.as_ptr() };
81            if !block.free {
82                current = block.next;
83                continue;
84            }
85
86            if block.data_len == data_len {
87                return Some(block_ptr);
88            }
89
90            if block.data_len > data_len
91                && best_block.is_none_or(|(_, bb_len)| bb_len > block.data_len)
92            {
93                best_block = Some((block_ptr, block.data_len));
94            }
95
96            current = block.next;
97        }
98
99        best_block.map(|(ptr, _)| ptr)
100    }
101
102    /// finds a block with enough space for `data_len` bytes
103    /// or creates a new one if there is no enough space
104    #[inline]
105    fn find_block(&mut self, data_len: usize) -> Option<NonNull<Block>> {
106        if let Some(block) = self.try_find_block(data_len) {
107            Some(block)
108        } else {
109            unsafe {
110                let new_block = Block::create(data_len)?;
111                let stolen_head = self.head.take();
112
113                (*new_block.as_ptr()).next = stolen_head;
114                self.head = Some(new_block);
115
116                Some(new_block)
117            }
118        }
119    }
120
121    fn allocate(&mut self, size: usize) -> Option<NonNull<[u8]>> {
122        let block = self.find_block(size)?;
123        unsafe {
124            let ptr = block.as_ptr();
125            (*ptr).free = false;
126            Some(Block::data_from_ptr(ptr))
127        }
128    }
129
130    unsafe fn deallocate(&mut self, block_data: NonNull<u8>) {
131        unsafe {
132            let block_ptr = Block::block_from_data_ptr(block_data).as_ptr();
133            let block = &mut *block_ptr;
134            block.free = true;
135        }
136    }
137}
138
139unsafe impl Send for SystemAllocator {}
140unsafe impl Sync for SystemAllocator {}
141
142// FIXME: implement locks before multithreading
143pub struct GlobalSystemAllocator {
144    inner: UnsafeCell<SystemAllocator>,
145}
146
147impl GlobalSystemAllocator {
148    const fn new() -> Self {
149        Self {
150            inner: UnsafeCell::new(SystemAllocator::new()),
151        }
152    }
153    #[inline]
154    pub fn allocate(&self, size: usize) -> Option<NonNull<[u8]>> {
155        unsafe { (*self.inner.get()).allocate(size) }
156    }
157    #[inline]
158    pub unsafe fn deallocate(&self, ptr: NonNull<u8>) {
159        unsafe { (*self.inner.get()).deallocate(ptr) }
160    }
161
162    // TODO: implement grow and shrink
163}
164
165unsafe impl Sync for GlobalSystemAllocator {}
166unsafe impl Send for GlobalSystemAllocator {}
167
168unsafe impl GlobalAlloc for GlobalSystemAllocator {
169    unsafe fn alloc(&self, layout: core::alloc::Layout) -> *mut u8 {
170        self.allocate(layout.size())
171            .map(|x| x.as_ptr() as *mut u8)
172            .unwrap_or(core::ptr::null_mut())
173    }
174
175    unsafe fn dealloc(&self, ptr: *mut u8, _: core::alloc::Layout) {
176        self.deallocate(NonNull::new_unchecked(ptr));
177    }
178}
179
180#[cfg_attr(
181    not(any(feature = "std", feature = "rustc-dep-of-std")),
182    global_allocator
183)]
184/// A high-level userspace allocator that internally uses the [`crate::syscalls::syssbrk`] syscall
185/// (rust wrapper)
186pub static GLOBAL_SYSTEM_ALLOCATOR: GlobalSystemAllocator = GlobalSystemAllocator::new();
187
188#[cfg(not(any(feature = "std", feature = "rustc-dep-of-std")))]
189#[unsafe(no_mangle)]
190/// Allocates an object sized `object_size` using [`GLOBAL_SYSTEM_ALLOCATOR`]
191pub extern "C" fn syscreate(object_size: usize) -> Optional<NonNullSlice<u8>> {
192    GLOBAL_SYSTEM_ALLOCATOR
193        .allocate(object_size)
194        .map(|mut x| unsafe {
195            let x = x.as_mut();
196            let len = x.len();
197            let ptr = NonNull::new_unchecked(x.as_mut_ptr());
198            NonNullSlice::from_raw_parts(ptr, len)
199        })
200        .into()
201}
202
203#[cfg(not(any(feature = "std", feature = "rustc-dep-of-std")))]
204#[unsafe(no_mangle)]
205/// Deallocates an object sized `object_size` using [`GLOBAL_SYSTEM_ALLOCATOR`]
206/// # Safety
207/// `object_ptr` must be a pointer to a valid object allocated by [`GLOBAL_SYSTEM_ALLOCATOR`]
208pub unsafe extern "C" fn sysdestroy(object_ptr: *mut u8) {
209    unsafe {
210        match NonNull::new(object_ptr) {
211            Some(ptr) => GLOBAL_SYSTEM_ALLOCATOR.deallocate(ptr),
212            None => (),
213        }
214    }
215}
safa_api/alloc.rs

safa_api/
alloc.rs
