Динамическое распределение памяти

Ранее в языках C/C++ мы использовали такие методы динамического распределения памяти, как malloc/free. По сравнению со статическим распределением памяти, которое выполняется во время компиляции, динамическое распределение позволяет изменять размер и момент выделения памяти в соответствии с состоянием программы во время выполнения. Это делает его более гибким, но требует поддержки операционной системы и может привести к дополнительным издержкам.

В нашем ядре также требуется динамическое распределение памяти. Типичные сценарии использования включают:

• Box<T> — можно рассматривать как аналог malloc;
• счётчик ссылок Rc<T>, атомарный счётчик ссылок Arc<T> — используются для автоматического освобождения объектов, когда они больше не упоминаются;
• некоторые структуры данных из стандартной библиотеки Rust, такие как Vec и HashMap.

Мы не можем напрямую использовать функции динамического распределения из стандартной библиотеки Rust в нашей операционной системе, поскольку эти функции требуют поддержки на уровне операционной системы, что создаёт конфликт циклических зависимостей. Чтобы обеспечить поддержку динамического распределения в нашем ядре, в языке Rust нам необходимо реализовать трейт GlobalAlloc, создать экземпляр этого класса и использовать атрибут #[global_allocator] для маркировки. В этом случае компилятор будет знать, как использовать предоставленную нами функцию распределения памяти для динамического распределения.

Для реализации трейта GlobalAlloc нам нужно поддерживать две функции:

unsafe fn alloc(&self, layout: Layout) -> *mut u8;
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

Здесь мы выделяем и освобождаем блок виртуальной памяти.

Что такое Layout? Из документации видно, что у него есть два поля: size, указывающее количество выделяемых байтов, и align, определяющее минимальное требование выравнивания виртуального адреса выделения, то есть адрес выделения должен быть кратен align. Здесь align должно быть степенью двойки.

Таким образом, наше требование заключается в выделении непрерывного блока виртуальной памяти размером не менее size байт и с требованием выравнивания align.

Алгоритм непрерывного распределения памяти

Предположим, у нас уже есть целый блок виртуальной памяти для распределения. Как мы можем распределить его?

Возможно, мы подумаем о некоторых простых и грубых методах, таких как выделение задачи в доступный наименьший адрес. Таким образом, память, которую мы выделяем, всегда непрерывна, и это кажется разумным использованием памяти.

Однако, если дело доходит до освобождения, предположим, что мы внезапно освобождаем часть памяти среди множества выделенных блоков. Хотя эта память доступна, она окружена уже выделенными блоками, поэтому её нельзя расширить. Мы называем такую доступную память «внешними фрагментами».

По мере того как всё больше фрагментов освобождается, в какой-то момент мы можем обнаружить, что нам нужно выделить довольно большой блок памяти, который состоит из нескольких фрагментов, но ни один отдельный фрагмент не подходит. Мы можем подумать об объединении нескольких фрагментов в один с помощью «сборки мусора». Однако этот процесс имеет значительные накладные расходы.

На курсе по операционным системам мы узнали о более эффективных алгоритмах распределения памяти, включая систему партнёров (Buddy System) и распределитель SLAB. Здесь мы используем Buddy System для решения этой проблемы.

Поддержка динамического распределения

Чтобы избежать дублирования работы, мы можем просто открыть статический массив размером 8M в качестве кучи и вызвать Buddy System Allocator, разработанный @jiege.

{% label %}os/src/memory/config.rs{% endlabel %}

/// Размер кучи, используемой для динамического распределения памяти операционной системой (8M)
pub const KERNEL_HEAP_SIZE: usize = 0x80_0000;

{% label %}os/src/memory/heap.rs{% endlabel %}

/// Пространство для динамического распределения памяти
///
/// Размер равен [`KERNEL_HEAP_SIZE`]
/// Эта область будет помещена в сегмент bss исполняемой программы после компиляции
static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];

/// Куча, динамический распределитель памяти
///
/// ### `#[global_allocator]`
/// [`LockedHeap`] реализует [`alloc::alloc::GlobalAlloc`] trait,
/// Может использоваться для выделения пространства в местах, где требуется куча, например, `Box` `Arc` и т. д.
#[global_allocator]
static HEAP: LockedHeap = LockedHeap::empty();

/// Инициализация пространства кучи операционной системы
pub fn init() {
    // Указать распределителю использовать эту зарезервированную область в качестве кучи
    unsafe {
        HEAP.lock().init(
            HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE
        )
    }
}

/// Обработчик ошибок при выделении памяти, сразу же вызывает панику и завершает работу
#[alloc_error_handler]
fn alloc_error_handler(_: alloc::alloc::Layout) -> ! {
    panic!("alloc error")
}

Есть и другие детали кода, связанные с модулями и вызовами, которые здесь не приводятся. Пожалуйста, обратитесь к коду в репозитории после завершения этой главы.

{% reveal %}

Подсказка:

1. Добавьте соответствующие зависимости в os/Cargo.toml;
2. Добавьте ссылку на новую функцию Rust alloc_error_handler в os/main.rs. {% endreveal %}

Тестирование динамического распределения памяти

Теперь давайте проверим, работает ли динамическое распределение, выделив динамический массив:

{% label %}os/src/main.rs{% endlabel %}

/// Функция входа в Rust
///
/// После серии подготовительных операций в `_start` это первая вызываемая функция Rust
#[no_mangle]
pub extern "C" fn rust_main() -> ! {
    // Инициализировать различные модули
    interrupt::init();
    memory::init();

    // Тестирование динамического выделения памяти
    use alloc::boxed::Box;
    use alloc::vec::Vec;
    let v = Box::new(5);
    assert_eq!(*v, 5);
    core::mem::drop(v);

    let mut vec = Vec::new();
    for i in 0..10000 {
        vec.push(i);
    }
    assert_eq!(vec.len(), 10000);
    for (i, value) in vec.into_iter().enumerate() {
        assert_eq!(value, i);
    }
    println!("тест кучи пройден");

    panic!()
}

После запуска вы увидите вывод, похожий на «тест кучи пройден». С этим инструментом мы сможем использовать ряд структур, основанных на динамическом распределении, таких как Vec, из библиотек в будущем.

Вопросы для размышления

В каком диапазоне адресов находится динамически выделенная память?