mallockit 0.1.0

A framework for building malloc implementations in Rust
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

use super::super::SpaceId;
use super::PageResource;
use crate::space::meta::Meta;
use crate::util::mem::freelist::page_freelist::PageFreeList;
use crate::util::mem::heap::HEAP;
use crate::util::sys::raw_memory::RawMemory;
use crate::util::*;
use spin::mutex::Mutex;
use spin::rwlock::RwLock;
use spin::Yield;
use std::iter::Step;
use std::sync::atomic::AtomicU32;
use std::{
    ops::Range,
    sync::atomic::{AtomicUsize, Ordering},
};

const NUM_SIZE_CLASS: usize = SpaceId::LOG_MAX_SPACE_SIZE - Page::<Size4K>::LOG_BYTES;

pub struct FreelistPageResource {
    pub id: SpaceId,
    freelist: Mutex<PageFreeList<{ NUM_SIZE_CLASS }>, Yield>,
    reserved_bytes: AtomicUsize,
    meta: RwLock<Vec<AtomicU32, Meta>, Yield>,
    base: Address,
}

impl FreelistPageResource {
    pub fn new(id: SpaceId) -> Self {
        debug_assert!(id.0 < 0b0000_1111);
        let range = HEAP.get_space_range(id);
        let base = range.start;
        let mut freelist = PageFreeList::new(base);
        freelist.release_cell(base, 1 << (NUM_SIZE_CLASS - 1));
        let mut meta = Vec::<u32, Meta>::with_capacity_in(1 << 20, Meta);
        meta.resize(1 << 20, 0u32);
        Self {
            id,
            freelist: Mutex::new(freelist),
            reserved_bytes: AtomicUsize::new(0),
            meta: RwLock::new(unsafe {
                std::mem::transmute::<Vec<u32, Meta>, Vec<AtomicU32, Meta>>(meta)
            }),
            base,
        }
    }

    fn map_pages<S: PageSize>(&self, _start: Page<S>, pages: usize) {
        self.reserved_bytes
            .fetch_add(pages << S::LOG_BYTES, Ordering::SeqCst);
    }

    fn unmap_pages<S: PageSize>(&self, start: Page<S>, pages: usize) {
        RawMemory::madv_free(start.start(), pages << S::LOG_BYTES);
        self.reserved_bytes
            .fetch_sub(pages << S::LOG_BYTES, Ordering::SeqCst);
    }

    fn set_meta<S: PageSize>(&self, start: Page<S>, pages: usize) {
        debug_assert!(pages <= u32::MAX as usize);
        let index = (start.start() - self.base) >> Page::<Size4K>::LOG_BYTES;
        let meta = self.meta.upgradeable_read();
        if index >= meta.len() {
            let mut meta = meta.upgrade();
            let len = usize::max(meta.len(), index).next_power_of_two();
            meta.resize_with(len << 1, Default::default);
            meta[index].store(pages as _, Ordering::Relaxed);
        } else {
            meta[index].store(pages as _, Ordering::Relaxed);
        }
    }

    fn get_meta<S: PageSize>(&self, start: Page<S>) -> usize {
        let index = (start.start() - self.base) >> Page::<Size4K>::LOG_BYTES;
        self.meta.read()[index].load(Ordering::Relaxed) as _
    }
}

impl PageResource for FreelistPageResource {
    fn reserved_bytes(&self) -> usize {
        self.reserved_bytes.load(Ordering::Relaxed)
    }

    fn acquire_pages<S: PageSize>(&self, pages: usize) -> Option<Range<Page<S>>> {
        let pages = pages.next_power_of_two(); // FIXME
        let units = pages << (S::LOG_BYTES - Size4K::LOG_BYTES);
        let start = self.freelist.lock().allocate_cell(units)?.start;
        let start = Page::<S>::new(start);
        self.map_pages(start, pages);
        let end = Step::forward(start, pages);
        self.set_meta(start, units);
        Some(start..end)
    }

    fn release_pages<S: PageSize>(&self, start: Page<S>) {
        let pages = self.get_meta(start) >> (S::LOG_BYTES - Size4K::LOG_BYTES);
        self.unmap_pages(start, pages);
        self.freelist.lock().release_cell(start.start(), pages);
    }

    fn get_contiguous_pages<S: PageSize>(&self, start: Page<S>) -> usize {
        self.get_meta(start) >> (S::LOG_BYTES - Size4K::LOG_BYTES)
    }
}