Архитектуры Аллокаторов

Jan 20, 2020

В этом посте объясняется, как реализовать heap-аллокатор с нуля. Здесь представлены и обсуждаются различные конструкции, а именно bump-аллокатор, linked list и fixed-sized. Для каждой из трех конструкций мы создадим базовую реализацию, которую можно использовать для ядра нашей системы.

Этот блог открыто разрабатывается на GitHub. Если у вас есть какие-либо проблемы или вопросы, пожалуйста, создайте issue. Вы также можете оставлять комментарии внизу страницы. Полный исходный код для этого поста можно найти в ветке post-11.

Содержание

• Введение
  • Design Goals
• Bump Allocator
  • Идея
  • Реализация
  • Реализация GlobalAlloc
  • Используем Это
  • Обсуждение
• Linked List Allocator
  • Реализация
  • Используем Это
  • Обсуждение
• Fixed-Size Block Allocator
  • Введение
  • Реализация
  • Используем Это
  • Обсуждение
  • Вариации
• Итоги
• Что Далее?
• Комментарии

🔗Введение

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

В этом посте мы покажем, как создать собственный аллокатор для кучи с нуля, вместо того чтобы полагаться на существующий крейт-аллокатор. Мы обсудим различные конструкции аллокаторов, включая упрощенный bump allocator и базовый fixed-size block allocator, и воспользуемся этими знаниями для реализации аллокатора с улучшенной производительностью (по сравнению с крейтом linked_list_allocator).

🔗Design Goals

Ответственность аллокатора - управление доступной памятью в куче. Он должен возвращать неиспользуемую память при вызовах alloc и отслеживать память, освобожденную с помощью dealloc, чтобы ее можно было использовать повторно. Самое главное, он никогда не должен выделять память, которая уже где-то используется, поскольку это приведет к неопределенному поведению (undefined behavior).

Помимо корректности, существует множество второстепенных целей проектирования. Например, аллокатор должен эффективно использовать доступную память и поддерживать низкий уровень фрагментации. Кроме того, он должен хорошо работать в приложениях с распараллеливанием задач и масштабироваться до любого количества ядер. Для максимальной производительности он может даже оптимизировать структуру памяти (memory layout) с учетом кэшей ЦП, чтобы улучшить локальность кэша и избежать false sharing.

примечание: memory layout в русском встречается как “структура памяти”, но устоявшегося термина нету, обычно пишут memory layout если это важно для контекста. Под этим понимается размер, выравнивание, начало и конец участка памяти. Описывает то, как аллокатор выделяет память.

Эти требования могут сделать хорошие аллокаторы очень сложными. Например, jemalloc имеет более 30 000 строк кода. Такая сложность часто нежелательна в коде ядра, где одна ошибка может привести к серьезным уязвимостям безопасности. К счастью, паттерны аллокации памяти в ядра часто гораздо проще по сравнению с userspace кодом, поэтому относительно простых аллокаторов часто достаточно.

Ниже мы представляем три возможных архитектуры аллокатора для ядра и объясняем их преимущества и недостатки.

🔗Bump Allocator

Самая простая конструкция аллокатора - это bump allocator (также известный как stack allocator). Он выделяет память линейно и отслеживает только количество выделенных байтов и количество аллокаций. Он полезен только в очень конкретных случаях, поскольку имеет серьезное ограничение: он может освободить только всю память за раз.

🔗Идея

Идея bump-аллокатора заключается в линейном выделении памяти через увеличение (“bumping”) переменной next, которая указывает на начало неиспользуемой памяти. В начале next указывает на начало кучи. При каждом выделении next увеличивается на размер аллокации, так что она всегда указывает на границу между использованной и неиспользованной памятью:

Указатель next движется только в одном направлении и поэтому никогда не выделяет одну и ту же область памяти дважды. Когда он достигает конца кучи, больше нельзя выделить память, что приводит к ошибке нехватки памяти при следующем выделении.

Bump-аллокатор часто реализуется с помощью счетчика аллокаций, который увеличивается на 1 при каждом вызове alloc и уменьшается на 1 при каждом вызове dealloc. Когда счетчик аллокаций достигает нуля, это означает, что все выделения в куче были освобождены. В этом случае указатель next может быть сброшен на начальный адрес кучи, так что вся память кучи снова становится доступной для аллокации.

🔗Реализация

Мы начинаем реализацию с объявления нового подмодуля allocator::bump:

// src/allocator.rs

pub mod bump;

Содержимое подмодуля находится в новом файле src/allocator/bump.rs, который мы создаем с содержанием:

// src/allocator/bump.rs

pub struct BumpAllocator {
    heap_start: usize,
    heap_end: usize,
    next: usize,
    allocations: usize,
}

impl BumpAllocator {
    /// создаем новый, пустой bump-аллокатор.
    pub const fn new() -> Self {
        BumpAllocator {
            heap_start: 0,
            heap_end: 0,
            next: 0,
            allocations: 0,
        }
    }

    /// Инициализирует bump-аллокатор с заданными границами кучи.
    ///
    /// Этот метод небезопасен, поскольку вызывающая сторона должна убедиться, что заданный
    /// диапазон памяти не используется. Кроме того, этот метод должен вызываться только один раз.
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        self.heap_start = heap_start;
        self.heap_end = heap_start + heap_size;
        self.next = heap_start;
    }
}

Поля heap_start и heap_end отслеживают нижнюю и верхнюю границы области памяти кучи. Вызывающая сторона должна убедиться, что эти адреса действительны, иначе аллокатор вернет недействительную память. По этой причине функция init должна быть помечена как unsafe.

Цель поля next - всегда указывать на первый неиспользуемый байт в куче, т.е. на начальный адрес следующей аллокации. В функции init оно устанавливается в значение heap_start, поскольку в начале вся куча не используется. При каждом выделении это поле увеличивается на размер аллокации («bumped»), чтобы гарантировать, что мы не вернем одну и ту же область памяти дважды.

Поле allocations - это простой счетчик активных аллокаций, цель которого - сбросить аллокатор после освобождения последней выделения. Оно инициализируется со значением 0.

Мы решили создать отдельную функцию init вместо того, чтобы выполнять инициализацию непосредственно в new, чтобы интерфейс оставался идентичным аллокатору, предоставляемому крейтом linked_list_allocator. Благодаря этому, аллокаторы можно переключать без дополнительных изменений кода.

🔗Реализация GlobalAlloc

Как объяснялось в предыдущем посте, все аллокаторы кучи должны реализовывать трейт GlobalAlloc, который определен следующим образом:

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

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { ... }
    unsafe fn realloc(
        &self,
        ptr: *mut u8,
        layout: Layout,
        new_size: usize
    ) -> *mut u8 { ... }
}

Необходимы только методы alloc и dealloc; другие два обладают реализацией по умолчанию и могут быть опущены.

🔗Первая попытка реализации

Попробуем реализовать метод alloc для нашего BumpAllocator:

// src/allocator/bump.rs

use alloc::alloc::{GlobalAlloc, Layout};

unsafe impl GlobalAlloc for BumpAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // TODO: проверка выравнивания и границ
        let alloc_start = self.next;
        self.next = alloc_start + layout.size();
        self.allocations += 1;
        alloc_start as *mut u8
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        todo!();
    }
}

Сперва мы используем поле next в качестве начального адреса для нашей аллокации. Затем мы обновляем его, чтобы оно указывало на конечный адрес выделения, который является следующим неиспользуемым адресом в куче. Перед тем, как вернуть начальный адрес аллокации в виде указателя *mut u8, мы увеличиваем счетчик allocations на 1.

Обратите внимание, что мы не выполняем никаких проверок границ или корректировок выравнивания, поэтому эта реализация еще не является безопасной. Это не имеет большого значения, поскольку в любом случае она не компилируется из-за ошибки:

error[E0594]: cannot assign to `self.next` which is behind a `&` reference
  --> src/allocator/bump.rs:29:9
   |
29 |         self.next = alloc_start + layout.size();
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be written

(Та же ошибка будет возникать для строки self.allocations += 1. Мы опустили это здесь для краткости.)

Ошибка возникает т.к. методы alloc и dealloc трейта GlobalAlloc работают только с неизменяемой ссылкой &self, поэтому обновление полей next и allocations невозможно. Это создает проблему, поскольку обновление next при каждой аллокации является основным принципом работы bump-аллокатора.

🔗GlobalAlloc и Мутабельность

Прежде чем рассматривать возможное решение этой проблемы мутаблельности, давайте попробуем понять, почему методы трейта GlobalAlloc определены с аргументами &self: как мы видели в предыдущем посте, глобальный аллокатор кучи определяется добавлением атрибута #[global_allocator] к static, который реализует трейт GlobalAlloc. Статические переменные в Rust иммутабельны, поэтому нет возможности вызвать метод, принимающий &mut self, на статическом аллокаторе. По этой причине все методы GlobalAlloc принимают только неизменяемую ссылку &self.

К счастью, есть способ получить ссылку &mut self из ссылки &self: мы можем использовать синхронизированную внутреннюю изменяемость, обернув аллокатор в спинлок spin::Mutex. Этот тип предоставляет метод lock, который выполняет взаимное исключение (мьютекс) и, таким образом, безопасно превращает ссылку &self в ссылку &mut self. Мы уже несколько раз использовали тип оболочки в нашем ядре, например, для текстового буфера VGA.

🔗Обертка Типа Locked

С помощью обертки spin::Mutex мы может реализовать трейт GlobalAlloc для нашего bump-аллокатора. Фокус в том, что реализация трейта не для BumpAllocator, а для обернутого типа spin::Mutex::<BumpAllocator>:

unsafe impl GlobalAlloc for spin::Mutex<BumpAllocator> {…}

К сожалению, это все еще не работает, т.к. компилятор Rust не разрешает реализации трейта для типов определенных в других крейтов:

error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
  --> src/allocator/bump.rs:28:1
   |
28 | unsafe impl GlobalAlloc for spin::Mutex<BumpAllocator> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^--------------------------
   | |                           |
   | |                           `spin::mutex::Mutex` is not defined in the current crate
   | impl doesn't use only types from inside the current crate
   |
   = note: define and implement a trait or new type instead

Что бы поправить это, мы должны создать нашу собственную обертку вокруг spin::Mutex:

// src/allocator.rs

/// Обертка вокруг spin::Mutex для доступа к реализации.
pub struct Locked<A> {
    inner: spin::Mutex<A>,
}

impl<A> Locked<A> {
    pub const fn new(inner: A) -> Self {
        Locked {
            inner: spin::Mutex::new(inner),
        }
    }

    pub fn lock(&self) -> spin::MutexGuard<A> {
        self.inner.lock()
    }
}

Этот тип является общей оберткой для spin::Mutex<A>. Он не налагает никаких ограничений на тип A, поэтому его можно использовать для обертки всех типов, а не только аллокаторов. Он предоставляет простую функцию-конструктор new, которая оборачивает заданное значение. Для удобства он также предоставляет функцию lock, которая вызывает lock на обёрнутом Mutex. Поскольку тип Locked достаточно общий, чтобы быть полезным и для других реализаций аллокаторов, мы поместили его в родительский модуль allocator.

🔗Реализация для Locked<BumpAllocator>

Тип Locked определен в нашем собственном крейте (в отличие от spin::Mutex), поэтому мы можем использовать его для реализации GlobalAlloc для нашего bump-аллокатора. Полная реализация выглядит следующим образом:

// src/allocator/bump.rs

use super::{align_up, Locked};
use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr;

unsafe impl GlobalAlloc for Locked<BumpAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        let mut bump = self.lock(); // получаем мутабельную ссылку

        let alloc_start = align_up(bump.next, layout.align());
        let alloc_end = match alloc_start.checked_add(layout.size()) {
            Some(end) => end,
            None => return ptr::null_mut(),
        };

        if alloc_end > bump.heap_end {
            ptr::null_mut() // out of memory
        } else {
            bump.next = alloc_end;
            bump.allocations += 1;
            alloc_start as *mut u8
        }
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        let mut bump = self.lock(); // получаем мутабельную ссылку

        bump.allocations -= 1;
        if bump.allocations == 0 {
            bump.next = bump.heap_start;
        }
    }
}

Первым шагом как для alloc, так и для dealloc является вызов метода Mutex::lock через поле inner, чтобы получить мутабельную ссылку на тип аллокатора. Экземпляр остается заблокированным до конца метода, это нужно чтобы не было состояния гонки (race condition) в многопоточном контексте (скоро мы добавим поддержку многопоточности).

По сравнению с предыдущим прототипом, реализация alloc теперь учитывает требования к выравниванию и проверяет границы, чтобы гарантировать, что аллокации остаются в пределах области кучи. Первый шаг - округлить адрес next до значения выравнивания, указанного аргументом Layout. Код функции align_up будет показан чуть позже. Затем мы добавляем запрошенный размер аллокации к alloc_start, чтобы получить конечный адрес блока. Чтобы предотвратить переполнение integer при больших аллокациях, мы используем метод checked_add. Если происходит переполнение или если результирующий конечный адрес блока больше конечного адреса кучи, мы возвращаем нулевой указатель, указывающий на нехватку памяти. В противном случае мы обновляем адрес next и увеличиваем счетчик allocations на 1, как и раньше. Наконец, мы возвращаем адрес alloc_start, преобразованный в указатель *mut u8.

Функция dealloc игнорирует заданные аргументы указателя и Layout. Вместо этого она просто уменьшает счетчик allocations. Если счетчик снова достигает значения 0, это означает, что все выделенные области памяти были снова освобождены. В этом случае она сбрасывает адрес next в адрес heap_start, чтобы снова сделать доступной всю память кучи.

🔗Выравнивание Адреса

Функция align_up достаточно универсальна, чтобы мы могли поместить ее в родительский модуль allocator. Базовая реализация выглядит следующим образом:

// src/allocator.rs

/// выравнивание addr по align до верхнего значения
fn align_up(addr: usize, align: usize) -> usize {
    let remainder = addr % align;
    if remainder == 0 {
        addr // addr уже выровнен
    } else {
        addr - remainder + align
    }
}

Функция сначала вычисляет остаток (переменная remainder) от деления addr на align. Если remainder равен 0, то адрес уже выровнен по заданному выравнивания (переменная align). В противном случае мы выравниваем адрес, вычитая remainder (чтобы новый remainder стал равен 0), а затем прибавляя значение align (чтобы адрес не стал меньше исходного).

Заметьте, это не самый эффективный способ реализации этой функции. Гораздо более быстрая реализация выглядит так:

/// выравнивание addr по align до верхнего значения.
///
/// требуется что бы `align` был кратен 2.
fn align_up(addr: usize, align: usize) -> usize {
    (addr + align - 1) & !(align - 1)
}

Этот метод требует, чтобы align было степенью двойки, что можно гарантировать с помощью трейта GlobalAlloc (и его параметра Layout). Это позволяет создать bitmask для выравнивания адреса очень эффективным способом. Чтобы понять, как это работает, давайте пройдемся по нему шаг за шагом, начиная с правой стороны:

• Поскольку align является степенью двойки, его двоичное представление имеет только один установленный бит (например, 0b000100000). Это означает, что align - 1 имеет все нижние биты установленными (например, 0b00011111).
• Создавая битовое NOT с помощью оператора !, мы получаем число, в котором установлены все биты, кроме битов, меньших, чем align (например, 0b…111111111100000).
• Выполняя битовое AND над адресом и !(align - 1), мы выравниваем адрес вниз. Это работает путем очистки всех битов, которые ниже align.
• Поскольку мы хотим выровнять вверх, а не вниз, мы увеличиваем addr на align - 1 перед выполнением битового AND. Таким образом, уже выровненные адреса остаются прежними, а невыровненные адреса округляются до следующей границы выравнивания.

Какой вариант выбрать, решать вам. Оба дают одинаковый результат, только используют разные методы.

🔗Используем Это

Чтобы использовать bump-аллокатор вместо крейта linked_list_allocator, нам нужно обновить статическую переменную ALLOCATOR в файле allocator.rs:

// src/allocator.rs

use bump::BumpAllocator;

#[global_allocator]
static ALLOCATOR: Locked<BumpAllocator> = Locked::new(BumpAllocator::new());

Здесь важно, что мы объявили BumpAllocator::new и Locked::new как const функции. Если бы они были обычными функциями, произошла бы ошибка компиляции, поскольку выражение инициализации static должно быть вычислимым во время компиляции.

Нам не нужно изменять вызов ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE) в нашей функции init_heap, т.к. bump-аллокатор предоставляет тот же интерфейс, что и аллокатор, из linked_list_allocator.

Теперь наше ядро использует наш bump-аллокатор! Все должно работать как и раньше, включая тесты heap_allocation, которые мы создали в предыдущем посте:

> cargo test --test heap_allocation
[…]
Running 3 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]

🔗Обсуждение

Большим преимуществом bump-аллокатора является ее высокая скорость. По сравнению с другими архитектурами аллокаторов (см. ниже), которые должны активно искать подходящий блок памяти и выполнять различные задачи учета в alloc и dealloc, bump-аллокатор может быть оптимизирован до нескольких ассемблерных инструкций. Это делает bump-аллокаторы полезными для оптимизации производительности аллокации, например, при создании виртуальной библиотеки DOM.

Хотя bump-аллокатор редко используется в качестве глобального аллокатора, принцип bump-аллокации часто применяется в форме арены аллокаций, которая в основном объединяет отдельные аллокации в пакеты для повышения производительности. Пример аллокатора арены для Rust есть в крейте toolshed.

🔗Недостатки Bump-Аллокатора

Основное ограничение bump-аллокатора это то, что он можено использовать освобожденную память только после того, как все будет освобождено. То есть одной долговечной аллокации достаточно, чтобы заблокировать повторное использование памяти. Мы можем увидеть это добавив вариацию теста many_boxes:

// tests/heap_allocation.rs

#[test_case]
fn many_boxes_long_lived() {
    let long_lived = Box::new(1); // new
    for i in 0..HEAP_SIZE {
        let x = Box::new(i);
        assert_eq!(*x, i);
    }
    assert_eq!(*long_lived, 1); // new
}

Как и тест many_boxes, этот тест создает большое количество аллокаций и если не переиспользовать освобожденную память, то это приведет к ошибке out-of-memory. Кроме того, тест создает long_lived аллокацию, которая существует в течение всей работы цикла.

Когда мы запускаем наш новый тест, мы видим, что он действительно завершается с ошибкой:

> cargo test --test heap_allocation
Running 4 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [failed]

Error: panicked at 'allocation error: Layout { size_: 8, align_: 8 }', src/lib.rs:86:5

Давайте подробно разберём, почему это происходит. Во-первых, аллокация long_lived создаётся в начале кучи, тем самым увеличивая счётчик allocations на 1. На каждой итерации цикла создаётся короткоживущее выделения, которые сразу же освобождаеются до начала следующей итерации. Это означает, что счётчик allocations временно возрастает до 2 в начале итерации и возвращается к 1 в её конце. Проблема в том, что bump-аллокатор может повторно использовать память только тогда, когда все аллокации освобождены, то есть когда счётчик allocations достигает 0. Поскольку это не происходит до окончания цикла, каждая итерация выделяет новый участок памяти, что в итоге приводит к ошибке нехватки памяти после нескольких итераций.

🔗Исправляем Тест?

Есть два возможных трюка, которые мы могли бы использовать что бы поправить наш bump-аллокатор:

• Мы могли бы обновить dealloc, чтобы проверить, было ли освобожденная аллокация последней, возвращенной alloc, путем сравнения его конечного адреса с указателем next. В случае, если они равны, мы можем безопасно сбросить next обратно к начальному адресу освобожденной аллокации. Таким образом, каждая итерация цикла будет переиспользовать один и тот же блок памяти.
• Мы могли бы добавить метод alloc_back, который выделяет память с конца кучи, используя дополнительное поле next_back. Затем мы могли бы вручную применять этот метод ко всем всех долгоживущим аллокациям, тем самым разделяя кратковременные и долговечные аллокации в куче. Заметьте, что такое разделение работает только в том случае, если заранее известно, как долго будет существовать каждая аллокация. Еще один недостаток этого подхода в том, что, что ручное управление аллокациями является трудоемким и потенциально небезопасным.

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

🔗Переиспользование Освобожденной Памяти?

Как мы узнали в предыдущей статье, аллокации могут существовать произвольно долго и освобождаться в произвольном порядке. Это означает, что нам необходимо отслеживать потенциально неограниченное количество непрерывных и несвязанных участков неиспользуемой памяти, как показано в следующем примере:

На графике показано состояние кучи в динамике. В начале вся куча неиспользуется, и указатель next равен heap_start (линия 1). Затем происходит первая аллокация (линия 2). На линии 3 мы освобождаем первый блок и аллоцируем второй. На линии 4 добавляется ещё множество блоков, половина из которых короткоживущие и уже освобождаются на линии 5, где одновременно выделяется ещё один новый блок.

Линия 5 демонстрирует фундаментальную проблему: у нас есть пять неиспользуемых областей памяти разного размера, но указатель next может указывать только на начало последней из них. Хотя в данном примере мы могли бы хранить начальные адреса и размеры остальных неиспользуемых регионов в массиве размером 4, это не является универсальным решением, поскольку мы легко можем создать пример с 8, 16 или 1000 неиспользуемыми областями памяти.

Обычно, когда у нас есть потенциально неограниченное количество элементов, мы используем коллекцию, аллоцированную в куче. Однако в нашем случае это невозможно, т.к heap-аллокатор не может зависеть от самого себя (это привело бы к бесконечной рекурсии или взаимоблокировке, она же deadlock). Поэтому нам нужно найти другое решение.

🔗Linked List Allocator

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

Наиболее частый подход к реализации - создание связанного списка (linked list) в освобожденной памяти, где каждый узел представляет собой свободную область памяти:

Каждый узел списка содержит два поля: размер свободного региона и указатель на следующий свободный регион памяти. При таком подходе нам достаточно хранить лишь указатель на первый свободный регион (называемый head), чтобы отслеживать все свободные области, независимо от их количиства. Получившаяся структура данных часто называется cписок свободной памяти

Как вы, вероятно, уже догадались по названию, именно этот метод используется крейтом linked_list_allocator. Аллокаторы, применяющие этот подход, также часто называются pool-аллокаторы (pool allocators)

🔗Реализация

Далее мы создадим свой собственный простой тип LinkedListAllocator, который использует вышеупомянутый подход для отслеживания освобожденных областей памяти. Эта часть поста не является обязательной для будущих постов, поэтому вы можете пропустить детали реализации, если хотите.

🔗Тип Аллокатора

Начнем с создания приватной структуры ListNode в новом подмодуле allocator::linked_list:

// src/allocator.rs

pub mod linked_list;

// src/allocator/linked_list.rs

struct ListNode {
    size: usize,
    next: Option<&'static mut ListNode>,
}

Как показано на рисунке, узел списка имеет поле size и опциональный указатель на следующий узел как тип Option<&'static mut ListNode>. Тип &'static mut семантически описывает владеемый объект за указателем. По сути, это Box без деструктора, который освобождает объект в конце области видимости.

Мы реализуем следующий метод для ListNode:

// src/allocator/linked_list.rs

impl ListNode {
    const fn new(size: usize) -> Self {
        ListNode { size, next: None }
    }

    fn start_addr(&self) -> usize {
        self as *const Self as usize
    }

    fn end_addr(&self) -> usize {
        self.start_addr() + self.size
    }
}

Тип имеет простую функцию-конструктор с именем new и методы для вычисления начального и конечного адресов представленной области. Мы делаем функцию new const function, которая понадобится позже при создании статического односвязного аллокатора.

Используя структуру ListNode в качестве строительного блока, мы можем создать структуру LinkedListAllocator:

// src/allocator/linked_list.rs

pub struct LinkedListAllocator {
    head: ListNode,
}

impl LinkedListAllocator {
    /// создаем пустой LinkedListAllocator.
    pub const fn new() -> Self {
        Self {
            head: ListNode::new(0),
        }
    }

    /// Инициализируем аллокатор с границами кучи.
    ///
    /// Эта ф-ция unsafe т.к. вызывающий должен гарантировать ,что полученные
    /// границы кучи будет корректны и куча не используется.
    /// Этот метод должен вызываться один раз
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        unsafe {
            self.add_free_region(heap_start, heap_size);
        }
    }

    /// Добавляет полученную память к концу списка.
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        todo!();
    }
}

Структура содержит узел head, указывающий на первый регион кучи. Нас интересует только значение указателя next, поэтому в функции ListNode::new мы устанавливаем size в 0. То, что head является экземпляром ListNode, а не просто &'static mut ListNode, обладает плюсом в том, что реализация метода alloc станет проще.

Как и в случае с bump-аллокатором, функция new не инициализирует аллокатор с границами кучи. Помимо сохранения совместимости API, причина в том, что процедура инициализации требует записи узла в память кучи, что возможно только во время выполнения. Однако функция new должна быть [константой](const function), то есть, что бы ее можно было вычислить на этапе компиляции, т.к она будет использоваться для инициализации статической переменной ALLOCATOR. По этой причине мы снова предоставляем отдельный, не-константный метод init.

Метод init использует метод add_free_region, реализация которого будет показана через мгновение. Пока что мы используем макрос todo!, он укажет что реализация еще не готова и при достижении будет вызывать панику.

🔗Метод add_free_region

Метод add_free_region обеспечивает основную операцию push в связанном списке. В настоящее время мы вызываем этот метод только из init, но он также будет важным методом для нашей реализации dealloc. Помните, что метод dealloc вызывается, при освобождении выделенной области памяти. Чтобы отслеживать этот освобожденный участок, мы хотим добавить его в связанный список.

Рассмотрим реализацию метода add_free_region:

// src/allocator/linked_list.rs

use super::align_up;
use core::mem;

impl LinkedListAllocator {
    /// Добавить полученную область памяти к концу списка.
    unsafe fn add_free_region(&mut self, addr: usize, size: usize) {
        // проверим, что освобожденная область может хранить ListNode
        assert_eq!(align_up(addr, mem::align_of::<ListNode>()), addr);
        assert!(size >= mem::size_of::<ListNode>());

        // создадим новый узел и добавим его к началу списка
        let mut node = ListNode::new(size);
        node.next = self.head.next.take();
        let node_ptr = addr as *mut ListNode;
        unsafe {
            node_ptr.write(node);
            self.head.next = Some(&mut *node_ptr)
        }
    }
}

Метод принимает в качестве аргумента адрес и размер области памяти и добавляет ее в начало списка. Сначала он проверяет, что данная область имеет необходимый размер и выравнена для хранения ListNode. Затем он создает узел и вставляет его в список, выполняя следующие шаги:

Шаг 0 показывает состояние кучи перед вызовом add_free_region. На шаге 1 метод вызывается с областью памяти, помеченной на рисунке как freed. После начальных проверок метод создает новый node в своем стеке с размером освобожденной области. Затем он использует метод Option::take, чтобы установить указатель next на текущий указатель head, тем самым сбрасывая указатель head в None.

На шаге 2 метод записывает вновь созданный node в начало освобожденной области памяти с помощью метода write. Затем он указатель head указывает на новый улез. Результирующая структура указателей выглядит немного хаотично, т.к. освобожденная область всегда вставляется в начало списка, но если мы проследим за указателями, то увидим, что каждая свободная область по-прежнему доступна из указателя head.

🔗Метод find_region

Вторая основная операция над связанным списком - поиск записи и ее удаление из списка. Это важная операция, необходимая для реализации метода alloc. Мы реализуем эту операцию в виде метода find_region:

// src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// Смотрим свободную область заданного размера и выравнивания и
    /// удаляем ее из списка.
    ///
    /// Возвращаем кортеж из списка и начального адреса аллокации.
    fn find_region(&mut self, size: usize, align: usize)
        -> Option<(&'static mut ListNode, usize)>
    {
        // ссылка на текущий узел, обновляемая при каждой итерации
        let mut current = &mut self.head;
        // поиск достаточно большого участка памяти в связанном списке
        while let Some(ref mut region) = current.next {
            if let Ok(alloc_start) = Self::alloc_from_region(&region, size, align) {
                // область подходит для аллокации -> удалить узел из списка
                let next = region.next.take();
                let ret = Some((current.next.take().unwrap(), alloc_start));
                current.next = next;
                return ret;
            } else {
                // облать не подходит ->  перейти к следущей
                current = current.next.as_mut().unwrap();
            }
        }

        // подходящей области не найдено
        None
    }
}

В этом методе используется переменная current и цикл [while let] для итерации по элементам списка. В начале current устанавливается в (фиктивный) узел head. При каждой итерации он обновляется до поля next текущего узла (в блоке else). Если область подходит для выделения с заданным размером и выравниванием, она удаляется из списка и возвращается вместе с адресом alloc_start.

Когда указатель current.next становится None, цикл заканчивается. Это означает, что мы прошли весь список, но не нашли подходящей области для аллокации. В этом случае мы возвращаем None. Подходит ли область, проверяет функция alloc_from_region, реализация которой будет показана чуть позже.

Давайте более подробно рассмотрим, как подходящая область удаляется из списка:

Шаг 0 показывает ситуацию до каких-либо корректировок указателей. Области region и current, а также указатели region.next и current.next отмечены на графике. На шаге 1 оба указателя region.next и current.next сбрасываются в None используя Option::take. Исходные указатели хранятся в локальных переменных с именами next и ret.

На шаге 2 указатель current.next устанавливается на локальный указатель next, который является исходным указателем region.next. В результате current теперь напрямую указывает на область после region, так что region больше не является элементом связанного списка. Затем функция возвращает указатель на region, хранящийся в локальной переменной ret.

🔗Функция alloc_from_region

Функция alloc_from_region возвращает значение, указывающее, подходит ли область для выделения памяти заданного размера и выравнивания. Она определена следующим образом:

// src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// попытка использовать регион для выделения памяти заданного размера и выравнивания.
    ///
    /// В случае успеха возвращает начальный адрес выделенной памяти.
    fn alloc_from_region(region: &ListNode, size: usize, align: usize)
        -> Result<usize, ()>
    {
        let alloc_start = align_up(region.start_addr(), align);
        let alloc_end = alloc_start.checked_add(size).ok_or(())?;

        if alloc_end > region.end_addr() {
            // region too small
            return Err(());
        }

        let excess_size = region.end_addr() - alloc_end;
        if excess_size > 0 && excess_size < mem::size_of::<ListNode>() {
            // остальная часть области слишком маленькая чтобы хранить listNode
            // это необходимо, т.к. аллокация делит область на использованную и свободную
            return Err(());
        }

        // область подходит для аллокации
        Ok(alloc_start)
    }
}

Сначала функция вычисляет начальный и конечный адрес потенциальной аллокации, используя функцию align_up, описанную выше, и метод checked_add. Если происходит переполнение или конечный адрес находится за конечным адресом области, аллокация не помещается в области, и мы возвращаем ошибку.

После этого функция выполняет менее очевидную проверку. Эта проверка необходима, поскольку в большинстве случаев выделение не вписывается в подходящую область идеально, так что часть области остается доступной для использования после аллокации. Эта часть области должна хранить свой собственный ListNode после выделения, поэтому она должна быть достаточно большой для этого. Проверка проверяет именно это: либо аллокация вписывается идеально (excess_size == 0), либо избыточный размер достаточно велик для хранения ListNode.

🔗Реализация GlobalAlloc

С помощью операций, предоставляемых методами add_free_region и find_region, мы можем реализовать трейт GlobalAlloc. Как и в случае с bump-аллокатором, мы не реализуем trait напрямую для LinkedListAllocator, а только для обернутого Locked<LinkedListAllocator>. Обертка [Locked] добавляет внутреннюю мутабельность с помощью спинлока, это позволяет нам изменять сам экземпляр аллокатора, даже если методы alloc и dealloc принимают только ссылки &self.

примечание перевода: спинлок - механизм синхронизации для эксклюзивного доступа к ресурсу, при этом, если не получается захватить доступ к ресурсу код не останавливается, а “крутиться” (spin) в цилке.

Реализация выглядит так:

// src/allocator/linked_list.rs

use super::Locked;
use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr;

unsafe impl GlobalAlloc for Locked<LinkedListAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // скорректируем memory layout
        let (size, align) = LinkedListAllocator::size_align(layout);
        let mut allocator = self.lock();

        if let Some((region, alloc_start)) = allocator.find_region(size, align) {
            let alloc_end = alloc_start.checked_add(size).expect("overflow");
            let excess_size = region.end_addr() - alloc_end;
            if excess_size > 0 {
                unsafe {
                    allocator.add_free_region(alloc_end, excess_size);
                }
            }
            alloc_start as *mut u8
        } else {
            ptr::null_mut()
        }
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        // скорректируем memory layout
        let (size, _) = LinkedListAllocator::size_align(layout);

        unsafe { self.lock().add_free_region(ptr as usize, size) }
    }
}

Начнём с метода dealloc, поскольку он проще: сначала выполняется корректировка структуры памяти (adjustment memory layout), которую мы объясним чуть позже. Затем вызываем Mutex::lock обертке [Locked] что бы получить ссылку на аллокатор - &mut LinkedListAllocator. В завершение вызываем функцию add_free_region, чтобы добавить освобождённую область в список свободной памяти (free list).

Метод alloc немного сложнее. Он начинается с тех же корректировок структуры и также вызывает Mutex::lock, чтобы получить мутабельную ссылку на аллокатор. Затем он использует метод find_region, чтобы найти подходящую область памяти для аллокации и удалить его из списка. Если поиск возвращает None, неуспешен, метод возвращает null_mut, сигнализируя об ошибке - подходящей области памяти не найдено.

В случае успеха метод find_region возвращает кортеж из подходящей области (уже удалённого из списка) и начального адреса выделения. Используя alloc_start, размер аллокации и конечный адрес региона, он заново вычисляет конечный адрес области и размер излишка. Если излишек не равен нулю, вызывается add_free_region, чтобы вернуть оставшуюся часть региона обратно в список свободных блоков. Наконец, метод возвращает alloc_start, приведённый к типу *mut u8.

🔗Корректировка Структуры Памяти

Так что же это за корректировка структуры памяти (layout adjustment), которые мы делаем в начале как в alloc, так и в dealloc? Они гарантируют, что каждый выделенный блок способен хранить ListNode. Это важно, потому что блок памяти в какой-то момент будет освобожден, и мы хотим записать в него ListNode. Если блок меньше, чем ListNode, или не имеет правильного выравнивания, может произойти неопределенное поведение (undefined behavior).

Корректировка структуры выполняются функцией size_align, которая определена следующим образом:

// src/allocator/linked_list.rs

impl LinkedListAllocator {
    /// Поправить полученный layout так, что бы в выделенная область памяти
    /// также могла хранить `ListNode`.
    ///
    /// Возвращает скорректированный размер и выравнивание в виде кортежа (размер, выравнивание).
    fn size_align(layout: Layout) -> (usize, usize) {
        let layout = layout
            .align_to(mem::align_of::<ListNode>())
            .expect("adjusting alignment failed")
            .pad_to_align();
        let size = layout.size().max(mem::size_of::<ListNode>());
        (size, layout.align())
    }
}

Сначала функция использует метод align_to на переданном как аргумент Layout, чтобы при необходимости увеличить выравнивание до выравнивания ListNode. Затем используется метод pad_to_align, чтобы округлить размер до кратного выравниванию, чтобы гарантировать, что начальный адрес следующего блока памяти также будет иметь правильное выравнивание для хранения ListNode. На втором этапе она использует метод max, чтобы обеспечить минимальный размер аллокации mem::size_of::<ListNode>. Таким образом, функция dealloc может безопасно записать ListNode в освобожденный блок памяти.

🔗Используем Это

Теперь мы можем обновить статическую переменную ALLOCATOR в модуле allocator, чтобы использовать наш новый LinkedListAllocator:

// src/allocator.rs

use linked_list::LinkedListAllocator;

#[global_allocator]
static ALLOCATOR: Locked<LinkedListAllocator> =
    Locked::new(LinkedListAllocator::new());

Поскольку функция init ведет себя одинаково для аллокаторов типа bump и linked list, нам не нужно изменять вызов init в init_heap.

Когда мы снова запускаем тесты heap_allocation, мы видим, что все тесты проходят успешно, включая тест many_boxes_long_lived, который не прошел с bump-аллокатором:

> cargo test --test heap_allocation
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [ok]

Это показывает, что наш linked list аллокатор способен повторно использовать освобожденную память для последующих выделений.

🔗Обсуждение

В отличие от bump-аллокатора, аллокатор на основе связанного списка гораздо более подходит в качестве универсального аллокатора, главным образом потому, что он может напрямую повторно использовать освобожденную память. Однако у него есть и некоторые недостатки. Некоторые из них вызваны только нашей базовой реализацией, но есть и фундаментальные минусы самой архитектуры.

🔗Слияние Освобожденных Блоков

Основная проблема нашей реализации заключается в том, что она только разбивает кучу на блоки, но никогда не объединяет их обратно. Рассмотрим следующий пример:

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

Чтобы решить эту проблему, нам нужно объединить соседние освобожденные блоки. Для приведенного выше примера это будет означать следующее:

Как и раньше, два из трех блоков освобождаются в строке 2. Вместо того, чтобы сохранять кучу фрагментированной, теперь мы выполняем дополнительный шаг в строке 2a, чтобы снова объединить два крайних правых блока. В строке 3 освобождается третья область (как и раньше), в результате чего получается полностью неиспользуемая куча, представленная тремя отдельными блоками. В дополнительном шаге слияния, на строке 3a, мы снова объединяем три соседних блока.

Крейт linked_list_allocator реализует эту стратегию слияния следующий образом: вместо вставки освобожденных блоков в начало связанного списка при вызове deallocate, он всегда поддерживает список отсортированным по начальному адресу. Благодаря этому слияние можно выполнять непосредственно в процессе вызова deallocate, просто проанализировав адреса и размеры двух соседних блоков в списке. Конечно, операция деаллокации в этом случае выполняется медленнее, но это предотвращает фрагментацию кучи, о которой мы говорили выше.

🔗Производительность

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

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

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

🔗Fixed-Size Block Allocator

Далее, мы рассмотрим архитектуру аллокатора основанного на аллокациях фиксированного размера (fixed-size block allocator) для выполнения запросов на выделение памяти. Таким образом, аллокатор часто возвращает блоки, которые больше, чем необходимо для выделения, что приводит к потере памяти из-за [внутренней фрагментации]. С другой стороны, это значительно сокращает время, необходимое для поиска подходящего блока (по сравнению с аллокатором связанного списка), что приводит к значительному улучшению производительности выделения памяти.

🔗Введение

Основная идея аллокатора блоков фиксированного размера: вместо того, что бы выделять ровно столько памяти, сколько запрошено, мы определяем небольшое кол-во размеров блоков и округляем каждый блок до верхнего размера блока. Например, при размерах 16, 64 и 512 байт запрос на 4 байта вернет блок размером 16 байт, выделение 48 байт - блок в 64 байта, а выделение 128 байт - блок размером 512 байт.

Как и при использовании связанного списка, мы отслеживаем неиспользуемую память, создавая связанный список в неиспользуемой памяти. Однако вместо использования одного списка с разными размерами блоков мы создаем отдельный список для каждого класса размеров. Затем каждый список хранит только блоки одного размера. Например, при размерах блоков 16, 64 и 512 в памяти будет три отдельных связанных списка:

.

Вместо одного указателя head у нас есть три указателя head head_16, head_64 и head_512, каждый из которых указывает на первый неиспользуемый блок соответствующего размера. Все узлы в одном списке имеют одинаковый размер. Например, список, начинающийся с указателя head_16, содержит только 16-байтовые блоки. Это означает, что нам больше не нужно хранить размер в каждом узле списка, поскольку он уже указан в имени указателя head.

Поскольку каждый элемент в списке имеет одинаковый размер, каждый элемент списка одинаково подходит для запроса на выделение памяти. Это означает, что мы можем эффективно аллоцировать память, выполняя следующие шаги:

• Округлить вверх запрошенный размер памяти до размера поддерживаемого блока. Например, когда запрашивается выделение 12 байт, мы выберем размер блока 16 в приведенном выше примере.
• Получить указатель на нужный список, например для блока в 16 байт, нам нужно использовать head_16.
• Удалить первый блок из списка и вернуть его.

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

🔗Блочные Размеры и Потраченная Память

В зависимости от размера блоков, мы теряем много памяти из-за округления. Например, для аллокации в 128 байт вернется блок в 512 байт, три четверти выделенной памяти остаются неиспользованными. Определив разумные размеры блоков, можно в некоторой степени ограничить количество потраченной впустую памяти. Например, при использовании степеней числа 2 (4, 8, 16, 32, 64, 128, …) в качестве размеров для блоков мы можем ограничить потерю памяти до половины размера выделения в худшем случае и до четверти размера аллокации в среднем случае.

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

🔗Деаллокация

Подобно аллокации, деаллокация также производительна. Она следует следующим шагам:

• Округление размера освобожденной памяти до размера следующего блока. Это необходимо, поскольку компилятор передает в dealloc только запрошенный размер памяти, а не размер блока, возвращенный alloc. Используя одну и ту же функцию выравнивания размера в alloc и dealloc, мы можем быть уверены, что всегда освобождаем правильный объем памяти.
• Получить указатель на соответствующий head-список.
• Добавить освобожденный блок в начало списка, обновив указатель на начало.

Что примечательно, для деаллокации также не требуется обход списка. Это означает, что время, необходимое для вызова dealloc, остается неизменным независимо от длины списка.

🔗Fallback Allocator

Учитывая, что большие аллокации (>2 KB) встречаются довольно редко, особенно в ядре операционных систем, для таких блоков может иметь смысл иметь другой аллокатор. Например, мы могли бы использовать linked list аллокатор для выделений более 2048 байт, чтобы уменьшить потерю памяти. Поскольку ожидается очень мало блоков такого размера, связанный список останется небольшим, а выделение и освобождение памяти по-прежнему будут достаточно быстрыми.

🔗Создание Новых Блоков

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

• Выделить новый блок из fallback-аллокатора (если он есть).
• Взяв блок другой размерности и разделить его. Это лучше всего работает, если размеры блоков являются степенями двойки. Например, 32-байтовый блок можно разделить на два 16-байтовых блока.

Для нашей реализации мы будем выделять новые блоки из fallback-аллокатора, поскольку такая реализация гораздо проще.

🔗Реализация

Теперь, когда мы знаем, как работает фиксированный аллокатор, можем приступить к реализации. Мы не будем полагаться на реализацию linked list аллокатора, созданного в предыдущем разделе, поэтому вы можете следовать этой части, даже если пропустили реализацию аллокатора связанного списка.

🔗List Node

Начнем с создания типа ListNode в новом модуле allocator::fixed_size_block:

// src/allocator.rs

pub mod fixed_size_block;

// src/allocator/fixed_size_block.rs

struct ListNode {
    next: Option<&'static mut ListNode>,
}

Этот тип аналогичен типу ListNode нашей реализации linked list аллокатора, с той разницей, что у нас нет поля size. Оно не нужно, поскольку каждый блок в списке имеет одинаковый размер при использовании аллокатора блоков фиксированного размера.

🔗Block Sizes

Далее мы определяем константу BLOCK_SIZES с размерами блоков, используемыми в нашей реализации:

// src/allocator/fixed_size_block.rs

/// Размеры блоков, которые будут использоваться.
///
/// Каждый размер должен быть степенью числа 2, поскольку они используются и для 
/// выравнивания блоков (оно всегда должно быть степенью числа 2).
const BLOCK_SIZES: &[usize] = &[8, 16, 32, 64, 128, 256, 512, 1024, 2048];

В качестве размеров блоков мы используем степени числа 2, начиная с 8 и заканчивая 2048. Мы не определяем размеры блоков меньше 8, поскольку каждый блок должен быть способен хранить 64-битный указатель на следующий блок при освобождении. Для выделения памяти размером более 2048 байт мы будем использовать аллокатор связанного списка.

Чтобы упростить реализацию, мы определяем размер блока как его требуемое выравнивание в памяти. Таким образом, 16-байтовый блок всегда выравнивается по границе 16 байт, а 512-байтовый блок - по границе 512 байт. Поскольку выравнивание всегда должно быть степенью числа 2, это исключает любые другие размеры блоков. Если в будущем нам понадобятся размеры блоков, не являющиеся степенями числа 2, мы все равно сможем адаптировать нашу реализацию для этого (например, определив второй массив BLOCK_ALIGNMENTS).

🔗Тип Аллокатора

Используя тип ListNode и срез BLOCK_SIZES, мы теперь можем определить наш тип аллокатора:

// src/allocator/fixed_size_block.rs

pub struct FixedSizeBlockAllocator {
    list_heads: [Option<&'static mut ListNode>; BLOCK_SIZES.len()],
    fallback_allocator: linked_list_allocator::Heap,
}

Поле list_heads представляет собой массив указателей head, по одному для каждого размера блока. Это реализуется с помощью len() от BLOCK_SIZES в качестве длины массива. В качестве fallback-аллокатора, для объектов превышающих максимальный размер блока, мы используем аллокатор, предоставляемый linked_list_allocator. Мы также могли бы использовать LinkedListAllocator, который мы реализовали сами, но он имеет недостаток, заключающийся в том, что он не объединяет освобожденные блоки.

Для построения FixedSizeBlockAllocator мы предоставляем те же функции new и init, которые мы реализовали и для других типов аллокаторов:

// src/allocator/fixed_size_block.rs

impl FixedSizeBlockAllocator {
    /// Создает пустой FixedSizeBlockAllocator.
    pub const fn new() -> Self {
        const EMPTY: Option<&'static mut ListNode> = None;
        FixedSizeBlockAllocator {
            list_heads: [EMPTY; BLOCK_SIZES.len()],
            fallback_allocator: linked_list_allocator::Heap::empty(),
        }
    }

    /// Инициализирует аллокатор с заданными границами кучи.
    ///
    /// unsafe, т.к. вызывающая сторона должна гарантировать, что заданные
    /// границы кучи действительны и куча не используется. Этот метод должен быть
    /// вызван только один раз.
    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
        unsafe { self.fallback_allocator.init(heap_start, heap_size); }
    }
}

Функция new просто инициализирует массив list_heads пустыми узлами и создает аллокатор связанного списка empty в качестве fallback_allocator. Константа EMPTY нужна, чтобы сообщить компилятору Rust, что мы хотим инициализировать массив постоянным значением. Инициализация массива напрямую как [None; BLOCK_SIZES.len()] не работает, потому что тогда компилятор требует, чтобы Option<&'static mut ListNode> реализовывал трейт Copy, чего он не делает. Это текущее ограничение компилятора Rust, которое может исчезнуть в будущем.

Небезопасная функция init вызывает только функцию init из fallback_allocator, не выполняя дополнительной инициализации массива list_heads. Вместо этого мы будем инициализировать списки по мере необходимости при вызовах alloc и dealloc.

Для удобства мы также создаем приватный метод fallback_alloc, который выполняет аллокацию с помощью fallback_allocator:

// src/allocator/fixed_size_block.rs

use alloc::alloc::Layout;
use core::ptr;

impl FixedSizeBlockAllocator {
    /// Аллокация через fallback-allocator.
    fn fallback_alloc(&mut self, layout: Layout) -> *mut u8 {
        match self.fallback_allocator.allocate_first_fit(layout) {
            Ok(ptr) => ptr.as_ptr(),
            Err(_) => ptr::null_mut(),
        }
    }
}

Тип Heap из крейта linked_list_allocator не реализует трейт GlobalAlloc (поскольку это невозможно без блокировки). Вместо этого он предоставляет метод allocate_first_fit с немного иным интерфейсом. Вместо возврата *mut u8 и использования нулевого указателя для сигнализации об ошибке, он возвращает Result<NonNull<u8>, ()>. Тип NonNull - это абстракция для сырого указателя (raw pointer), которая гарантирует, что указатель не может быть нулевым. Преобразуя случай Ok через метод NonNull::as_ptr и случай Err в нулевой указатель, мы можем легко преобразовать это обратно в тип *mut u8.

🔗Вычисление Индекс Списка

Прежде чем реализовать трейт GlobalAlloc, мы определяем вспомогательную функцию list_index, которая возвращает минимально возможный размер блока для заданного Layout:

// src/allocator/fixed_size_block.rs

/// Выбирает предпочитаемый размер блоков для полученного структуры памяти
///
/// Возвращает индекс от массива `BLOCK_SIZES`.
fn list_index(layout: &Layout) -> Option<usize> {
    let required_block_size = layout.size().max(layout.align());
    BLOCK_SIZES.iter().position(|&s| s >= required_block_size)
}

Блок должен иметь как минимум размер и выравнивание, требуемые полученным Layout. Поскольку мы определили, что размер блока равен его выравниванию, это означает, что required_block_size является максимальным значением атрибутов size() и align(). Чтобы найти следующий по величине блок в срезе BLOCK_SIZES, мы сначала используем метод iter(), чтобы получить итератор, а затем метод position(), чтобы найти индекс первого блока, размер которого не меньше required_block_size.

Обратите внимание, что мы возвращаем не сам размер блока, а индекс в срезе BLOCK_SIZES. Причина в том, что мы хотим использовать возвращаемый индекс в качестве индекса в массиве list_heads.

🔗Реализация GlobalAlloc

Последний шаг - реализация трейта GlobalAlloc:

// src/allocator/fixed_size_block.rs

use super::Locked;
use alloc::alloc::GlobalAlloc;

unsafe impl GlobalAlloc for Locked<FixedSizeBlockAllocator> {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        todo!();
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        todo!();
    }
}

Как и в случае с другими аллокаторами, мы не реализуем trait GlobalAlloc напрямую для нашего типа аллокатора, а используем обертку Locked, чтобы добавить синхронизированную внутреннюю мутабельность. Поскольку реализации alloc и dealloc относительно велики, мы напишем их по очереди ниже.

🔗alloc

Реализация метода alloc выглядит следующим образом:

// `impl` блок в src/allocator/fixed_size_block.rs

unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
    let mut allocator = self.lock();
    match list_index(&layout) {
        Some(index) => {
            match allocator.list_heads[index].take() {
                Some(node) => {
                    allocator.list_heads[index] = node.next.take();
                    node as *mut ListNode as *mut u8
                }
                None => {
                    // в списке нет блока => выделить новый блок
                    let block_size = BLOCK_SIZES[index];
                    // работает только тогда, когда размеры блоков являются степенью числа 2
                    let block_align = block_size;
                    let layout = Layout::from_size_align(block_size, block_align)
                        .unwrap();
                    allocator.fallback_alloc(layout)
                }
            }
        }
        None => allocator.fallback_alloc(layout),
    }
}

Давайте разберем это шаг за шагом:

Сначала мы используем метод Locked::lock, чтобы получить мутабельную ссылку на объект-обертку аллокатора. Затем мы вызываем только что определённую функцию list_index, чтобы вычислить подходящий размер блока для данной компоновки и получить соответствующий индекс в массиве list_heads. Если этот индекс равен None, то ни один размер блока не подходит для выделения памяти, поэтому мы используем fallback_allocator с помощью функции fallback_alloc.

Если индекс списка равен Some, мы пытаемся удалить первый узел в соответствующем списке, начинающемся с list_heads[index], с помощью метода Option::take. Если список не пустой, мы входим в ветвь Some(node) оператора match, где устанавливаем указатель head списка на следующий элемент после извлеченного node (снова используя take). Наконец, мы возвращаем удаленный указатель node как *mut u8.

Если заголовок списка равен None (список блоков пуст), нам нужно создать новый блок, как описано выше. Для этого мы сначала получаем текущий размер блока из среза BLOCK_SIZES и используем его как для размера, так и для выравнивания нового блока. Затем мы создаём из него новый Layout и вызываем метод fallback_alloc для аллокации. Причина корректировки структуры памяти и выравнивания в том, что блок будет добавлен в список блоков при освобождении памяти.

🔗dealloc

Реализация метода dealloc выглядит следующим образом:

// src/allocator/fixed_size_block.rs

use core::{mem, ptr::NonNull};

// внутри блока `unsafe impl GlobalAlloc`

unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
    let mut allocator = self.lock();
    match list_index(&layout) {
        Some(index) => {
            let new_node = ListNode {
                next: allocator.list_heads[index].take(),
            };
            // Убедитесь, что блок имеет размер и выравнивание, необходимые для хранения узла.
            assert!(mem::size_of::<ListNode>() <= BLOCK_SIZES[index]);
            assert!(mem::align_of::<ListNode>() <= BLOCK_SIZES[index]);
            let new_node_ptr = ptr as *mut ListNode;
            unsafe {
                new_node_ptr.write(new_node);
                allocator.list_heads[index] = Some(&mut *new_node_ptr);
            }
        }
        None => {
            let ptr = NonNull::new(ptr).unwrap();
            unsafe {
                allocator.fallback_allocator.deallocate(ptr, layout);
            }
        }
    }
}

Как и в alloc, сначала мы используем метод lock чтобы получить мутабельную ссылку на аллокатор, а затем ф-цию list_index для получения списка блоков, соответствующего заданному Layout. Если индекс равен None, значит в BLOCK_SIZES нет подходящего по размеру блока, а это значит, что аллокация памяти была выполнена fallback-аллокатором. Поэтому мы используем его метод deallocate что бы освободить память обратно. Метод ожидает NonNull вместо *mut u8, поэтому нам необходимо сначала преобразовать указатель. (Вызов unwrap завершается ошибкой только в случае нулевого указателя, что не должно происходить, когда компилятор вызывает dealloc.)

Если list_index возвращает индекс блока, нам нужно добавить освобожденный блок памяти в список. Для этого мы сначала создаем новый ListNode, указывающий на текущий заголовок списка (снова используя Option::take). Прежде чем записывать новый узел в освобожденный блок памяти, мы проверяем, что текущий размер блока, указанный в index, имеет требуемый размер и выравнивание для хранения ListNode. Затем мы выполняем запись, преобразуя заданный указатель *mut u8 в указатель *mut ListNode и вызывая на нем unsafe метод write. Последний шаг - установить указатель head списка, который в данный момент равен None, поскольку мы вызвали take, на наш только что записанный ListNode. Для этого мы преобразуем исходный new_node_ptr в мутабельную ссылку.

Стоит отметить несколько моментов:

• Мы не различаем блоки, выделенные из списка блоков, и блоки, полученные из fallback-аллокатора. Это означает, что новые блоки, созданные в alloc, добавляются в список блоков в dealloc, тем самым увеличивая количество блоков этого размера.
• Метод alloc - единственное место в нашей реализации, где создаются новые блоки. Это означает, что изначально мы начинаем с пустых списков блоков и заполняем их лениво только при выделении памяти размером с блок.
• Нам не нужны unsafe блоки в alloc и dealloc, даже несмотря на то, что мы выполняем некоторые небезопасные операции. Причина в том, что Rust в настоящее время рассматривает весь набор небезопасных функций как один большой unsafe блок. Поскольку использование явных блоков unsafe имеет то преимущество, что очевидно, какие операции являются небезопасными, а какие нет, существует предложенный RFC, который изменит это поведение.

🔗Используем Это

Для использования нашего нового FixedSizeBlockAllocator необходимо обновить статическую переменную ALLOCATOR в модуле allocator:

// src/allocator.rs

use fixed_size_block::FixedSizeBlockAllocator;

#[global_allocator]
static ALLOCATOR: Locked<FixedSizeBlockAllocator> = Locked::new(
    FixedSizeBlockAllocator::new());

Поскольку функция init ведет себя одинаково для всех реализованных нами распределителей памяти, нам не нужно изменять вызов init в init_heap.

Теперь, когда мы снова запустим наши тесты heap_allocation, все тесты должны пройти успешно:

> cargo test --test heap_allocation
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]
many_boxes_long_lived... [ok]

Наш новый аллокатор, похоже, работает!

🔗Обсуждение

Хотя подход с блоками фиксированного размера демонстрирует гораздо лучшую производительность, чем подход со связанным списком, он приводит к потере до половины памяти при использовании степеней двойки в качестве размеров блоков. Целесообразность такого компромисса во многом зависит от типа приложения. Для ядра операционной системы, где производительность имеет решающее значение, подход с блоками фиксированного размера представляется лучшим выбором.

Что касается реализации, то в нашей текущей версии можно улучшить ряд моментов:

• Вместо того чтобы выделять блоки только лениво, используя fallback-аллокатор, возможно, лучше предварительно заполнять списки, чтобы повысить производительность первоначальных аллокаций.
• Для упрощения реализации мы разрешили только размеры блоков, являющиеся степенями двойки, чтобы мы могли использовать их также в качестве выравнивания блоков. Сохраняя (или вычисляя) выравнивание другим способом, мы могли бы также разрешить произвольные размеры блоков. Таким образом, мы могли бы добавить больше размеров блоков, например, для распространенных размеров выделения памяти, чтобы минимизировать ее потери.
• В настоящее время мы только создаем новые блоки, но никогда их не освобождаем. Это приводит к фрагментации и в конечном итоге может привести к сбою выделения памяти при больших аллокациях. Возможно, имеет смысл ввести максимальную длину списка для каждого размера блока. Когда максимальная длина достигается, последующие выделения освобождаются с помощью fallback-аллокатора, а не добавляются в список.
• Вместо того, чтобы переходить к аллокатору связанного списка, мы могли бы использовать специальный аллокатор для выделения памяти размером более 4 КБ. Идея заключается в использовании страничной организации памяти, которая работает со страницами размером 4 КБ, для маппинга непрерывного блока виртуальной памяти на не непрерывные физические фреймы. Таким образом, фрагментация неиспользуемой памяти больше не будет проблемой для аллокаций больших объемов памяти.
• С таким аллокатором страниц может иметь смысл добавить размеры блоков до 4 КБ и полностью отказаться от аллокатора связанных списков. Основными преимуществами этого будут уменьшение фрагментации и улучшение предсказуемости производительности, т. е. лучшая производительность в худшем случае.

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

🔗Вариации

Существует также множество вариаций конструкции фиксированных аллокаторов. Двумя популярными примерами являются аллокатор slab и аллокатор buddy, которые также используются в популярных ядрах, таких как Linux. Ниже мы дадим краткое введение в эти две конструкции.

🔗Slab Allocator

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

Slab-аллокаторы часто сочетаются с другими аллокаторами. Например, его можно использовать вместе с аллокатором блоков фиксированного размера для дальнейшего разделения выделенного блока с целью сокращения потерь памяти. Его также часто используют для реализации паттерна “объектный пул” поверх одного большого выделения.

🔗Buddy Allocator

Вместо использования связанного списка для управления освобожденными блоками, в конструкции buddy allocator используется бинарное дерево вместе с размерами блоков, кратными 2. Когда требуется новый блок определенного размера, он разделяет блок большего размера на две половины, создавая тем самым два дочерних узла в дереве. Каждый раз, когда блок снова освобождается, анализируется его соседний блок в дереве. Если соседний блок также свободен, два блока снова объединяются, образуя блок в два раза большего размера.

Преимущество этого процесса объединения заключается в том, что внешняя фрагментация уменьшается, так что небольшие освобожденные блоки могут быть повторно использованы для большого выделения. Кроме того, он не использует резервный аллокатор, поэтому производительность более предсказуема. Самым большим недостатком является то, что возможны только размеры блоков, кратные 2, что может привести к большому количеству потраченной впустую памяти из-за внутренней фрагментации. По этой причине аллокаторы типа buddy часто сочетаются с аллокатором типа slab для дальнейшего разделения выделенного блока на несколько меньших блоков.

🔗Итоги

В этой статье был представлен обзор различных конструкций аллокаторов. Мы узнали, как реализовать базовый bump allocator, который распределяет память линейно, увеличивая один указатель next. Хотя bump-аллокатор работает очень быстро, он может повторно использовать память только после того, как все выделенные блоки будут освобождены. По этой причине он редко используется в качестве глобального аллокатора.

Затем мы создали linked list-аллокатор, который использует освобожденные блоки памяти для создания связанного списка, так называемого список свободной памяти. Этот список позволяет хранить произвольное количество освобожденных блоков разного размера. Хотя при этом не происходит потери памяти, этот подход страдает низкой производительностью, поскольку запрос на выделение памяти может потребовать полного прохождения списка. Наша реализация также страдает от внешней фрагментации, поскольку не объединяет соседние освобожденные блоки обратно вместе.

Чтобы устранить проблемы с производительностью, связанные с использованием связанных списков, мы создали аллокатор фиксированных блоков, который заранее определяет фиксированный набор размеров блоков. Для каждого размера блока существует отдельный список свободной памяти, так что для выделения и освобождения памяти достаточно просто вставить/удалить элемент в начале списка, что делает этот процесс очень быстрым. Поскольку каждое выделение округляется до следующего большего размера блока, часть памяти тратится впустую из-за внутренней фрагментации.

Существует множество других конструкций аллокаторов с различными компромиссными решениями. Slab allocation хорошо подходит для оптимизации распределения общих структур фиксированного размера, но применимо не во всех ситуациях. Buddy allocation использует двоичное дерево для объединения освобожденных блоков, но тратит большое количество памяти, поскольку поддерживает только размеры блоков, кратные 2. Также важно помнить, что каждая реализация ядра имеет уникальную рабочую нагрузку, поэтому не существует «лучшей» реализации аллокатора, подходящей для всех случаев.

🔗Что Далее?

Этим постом мы на данный момент завершаем реализацию управления памятью. Далее мы начнем изучать многозадачность, начиная с кооперативной многозадачности в форме async/await. В последующих постах мы затем рассмотрим потоки, многопроцессорность и процессы.