В этой части мы напишем менеджер памяти для того, чтоб разблокировать использование Vec, String, HashMap и всего этого. Сразу после этого реализуем файловую систему FAT32 и подключим драйвер для EMMC (такая штука для общения с SD-карточками). В конце концов в нашей командной оболочке появятся пара новых команд: cd, pwd, cat, ls.

Нулевая лаба

Первая лаба: младшая половина и старшая половина

Полезности

• Книга по Rust версии 2. На русском языке перевод закончен не до конца. Так что только markdown.
• Справочник по стандартной библиотеке Rust.
• Мануал по периферии процессора BCM2837.
• Справка по ATAGS
• Краткое описание структур FAT
• Статейка про FAT32 из английской википедии.

Фаза 0: Начало работ

Для начала убеждаемся, что с самого начала в нашем окружении ничего не поменялось:

• Там Linux, BSD или macOS
• Оно 64-битное
• У вас есть USB-порт

Кроме того установлено вот это: git, wget, tar, screen, make и всё, что было за прошлые серии. Убеждаемся в стабильности и идём дальше.

Получение необходимого кода

Клонируем в нашу папочку по имени cs140e (или как вы её там назвали) вот этот репозиторий:

git clone https://web.stanford.edu/class/cs140e/assignments/2-fs/skeleton.git 2-fs

После всего этого внутре должно быть примерно такая структура:

cs140e
+-- 0-blinky
+-- 1-shell
+-- 2-fs
L-- os

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

cd os
git fetch
git checkout 2-fs
git merge master

Возможно вам придётся разрешать конфликты слияния. Вы можете увидеть что-то похожее на:

Auto-merging kernel/src/kmain.rs
CONFLICT (content): Merge conflict in kernel/src/kmain.rs
Automatic merge failed; fix conflicts and then commit the result.

Автоматически не получилось. Придётся руками. Для того, чтоб разрешить это, надо будет вручную изменить kmain.rs. Убедитесь, что сохранили таки все изменения из прошлой серии. Для устранения конфликтов надо пофикшеные файлики добавить при помощи git add и git commit. Всяческую годную инфу по решению конфликтов слияния и вообще про git можно читнуть в руководсве githowto.com. Этот туториал можно и пройти. Всяко пригодится.

Обновление прошивки

Требуется заново скачать прошивку при помощи команды make fetch из репы 2-fs. Команда сама всё скачает и распакует. Нам остаётся положить файлики из поддиректории files/ в корень нашей MicroSD-карточки. А именно файлы firmware/bootcode.bin, firmware/config.txt, firmware/fixup.dat и firmware/start.elf. Не забывайте, что если вы исползуете бутлоадер из прошлой части в качестве kernel8.img, то надо добавить вот эту строчку в config.txt:

kernel_address=0x4000000

Установка ttywrite

Теперь у Makefile из папочки os/kernel есть дополнительная цель install. Оная собирает ядро и отправляет оное прямо на малинку используя ttywrite из прошлой части. Соответственно если на малинке kernel8.img содержит бутлоадер, написанный в прошлой серии, этот самый бутлоадер примет и загрузит наш файлик с ядром. Для того, чтоб это запустить нам надо выполнить make install в папочке с кодом ядра.

При этом эта цель из Makefile вызывает ttywrite напрямую просто по имени. Т.е. ttywrite должен находиться в одном из мест, на которые указывает переменная окружения PATH. Для того, чтоб запихнуть ttywrite в одно из таких мест мы можем зайти в 1-shell/ttywrite и выполнить cargo install. Наша утилитка соберётся и скопируется в нужное место. Если всё правильно, то мы сможем вызвать ttywrite --help и оно выведет нам справку.

По умолчанию make install использует /dev/tty.SLAB_USBtoUART для имени устройства. Отредактируйте Makefile так, чтоб оно указывало на то, что вам необходимо. Т.е. какое у вас там устройство для вашего переходника. Там есть переменная с именем PI_TTY. Вот и присвойте ей другое значение.

ALLOCATOR.initialize() вызывает панику!
Наша оболочка должна была остаться работоспособной. Однако если вы попробуете протестировать цель make install, то обноружите, что оболочка не работает. Скорее всего дело в вызове ALLOCATOR.initialize(). Там нет распределителя памяти. Только заглушка, которая просто паникует при выполнении безо всяких предупреждений об этом. Чуть позже этот достадный факт мы исправим. Пока можно просто закоментировать эту строчку, чтоб всё более или менее, но работало.

Фаза 1: Линия памяти

В этой фазе мы воплотим два аллокатора памяти. Простейший bump-аллокатор и чуть более сложный bin-аллокатор. Это практически всё, что нам нужно для того, чтоб работало выделение памяти в куче. Другими словами Vec, Box и String таки заработают. Для того, чтоб определять количество доступной памяти мы будем использовать ARM-теги (ATAGS). Кроме того нам надо реализовать внутренности функции panic_fmt, которая в конечном итоге вызывается при вызове panic!.

Субфаза A: Паника!

Начнём с реализации panic_fmt. Работать будем с файлом kernel/src/lang_items.rs.

Языковые элементы (Language Items)

Когда компейлятор Rust настроен для компейляции программ для целей без операционной системы (типа нашей Raspberry Pi), компилятор просит у нас парочку функций. Их нам надо написать своими руками. Такие штуки называются языковыми элементами (language items). Эти элементы — функции, вызовы которых компилятор подставляет в определённых условиях. Мы можем определят такие функции для какого либо элементаязыка. Для этого нам нужно аннотировать такую функцию атрибутом #[lang_item].

На текущий момент Rust требует от нас всего двух таких функций:

• panic_fmt: (fmt: ::std::fmt::Arguments, file: &str, line: u32, col: u32) -> ! которая вызывается при вызове panic!. Аргументы panic! передаются в качестве параметра fmt. Помимо этого передаётся имя файла, номер строки и колонки того места, где был вызван panic!. Это соотвественно file, line и col.
• eh_personality: эта функция зависит от конкретной ОСи или ABI. Она вызывается при раскрутке стека или после abort, если это необходимо. Обычно всё это происходит при panic! или выходе из потока. Эту функцию мы реализовывать не будем.

Обе эти функции уже объявлены в kernel/src/lang_items.rs. Нам нужно дописать функцию panic_fmt, чтоб она выводила что-то полезное.

Реализация panic_fmt

Сейчас мы допишем эту функцию. Наша реализация должна выводить переданную информацию в нашу консоль, а затем в ходить в бесконечный цикл loop. Кстати. fmt::Arguments реализует трейт Display. Следовательно мы можем использовать kprintln!("{}", fmt). Сделайте вывод таким, какой он нравится лично вам. Для примера можно вдохновиться паниками ядра Linux:

            (
       (      )     )
         )   (    (
        (          `
    .-""^"""^""^"""^""-.
  (//\\//\\//\\//\\//\\//)
   ~\^^^^^^^^^^^^^^^^^^/~
     `================`

    The pi is overdone.

---------- PANIC ----------

FILE: src/kmain.rs
LINE: 40
COL: 5

index out of bounds: the len is 3 but the index is 4

Затем протестируйте реализацию panic_fmt какой либо паникой ядра. Напоминаю, что можно использовать make install для компиляции с последующим выполнением через бутлоадер. И да. ALLOCATOR.initialize() же вызывает panic! где-то внутри. Так что при её выполнени вы тоже должны увидеть сообщение об ошибке.

По мимо этого попробуйте вызвать панику разными способами. При помощи panic!(), при помощи других похожих макросов. И ещё как нибудь. Когда будете уверены в том, что ваша реализация вполне себе работает — переходите к следующей фазе.

Субфаза B: ATAGS

В этой подфазе мы запилим итератор над тегами ARM (ATAGS), которые нам предоставляет прошивка малинки. Использовать итератор мы будем для того, чтоб определять количество доступной памяти. Основная работа будет вестись в каталоге pi/src/atags и в файле kernel/src/allocator/mod.rs.

Теги ARM

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

Малинка помещает массив структур ATAG начиная с адреса 0x100. При этом каждый тег начинается с 8-битного заголовка:

struct AtagHeader {
    dwords: u32,
    tag: u32,
}

Поле dwords содержит размер всего тега включая и сам заголовок. При этом размер в двойных словах (double words, т.е. 32-битное слово). Минимальный размер равен 2 (в размер заголовка). Поле tag содержит тип ATAG. Всего есть около десятка таких в справке по ATAGS. Малинка использует только четыре из них. Нам они и интересны:

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

struct Mem {
    size: u32,
    start: u32
}

Теги лежат в памяти последовательно без какого либо заполнения между оными. Начинается этот список с тега CORE. А последний тег в этом списке это NONE. Всё остальное может быть в любом порядке. Для того, чтоб узнать, где начинается следующий тег, надо смотреть на содержимое dwords. Графически это всё выглядит примерно так:

Объединения (Union) и безопасность

Сырые структуры для ATAG тегов объявлены в файле pi/src/atags/raw.rs. При этом там используются union. Объединения в Rust практически идентичны объединениям в Няшном Си. Они определяют структуру, в которой некоторые поля имеют общую память.

pub struct Atag {
    dwords: u32,
    tag: u32,
    kind: Kind
}

pub union Kind {
    core: Core,
    mem: Mem,
    cmd: Cmd
}

Другими словами объединения позволяют записывать в память произвольные структуры без учёта правильности выбора. Получается, что доступ к конкретным полям объединения небезопасен в Rust.

Там уже есть обрёртки unsafe во многих местах. По крайней мере не нужно беспокоиться о том, как обращаться в объединениям самостоятельно. Тем не менее передача объединений конечным пользователям библиотеки это плохая идея. По этой причине там есть ещё одна структура Atag в файле pi/src/atags/atag.rs. Эта структура полностью безопасна для доступа. Именно её мы будем передавать внешнему коду. В процессе дописывания модуля atag вы напишете преобразование между внутренним представлением и этой структурой.

Почему передача объединений конечным пользователям будет плохой идеей? [enduser-unsafe]

Мы прилагаем достаточно много усилий для создания безопасного интерфейса для небезопасных структур. Вы ещё не один раз увидите подобное в Rust. Стандартная библиотека тоже хороший пример этого. Какая же польза от создания безопасной прослойки? Можем ли мы перенести подобный подход на такие языки, как Няшный Си?

Аргументы командной строки

Тег CMDLINE заслуживает дополнительного внимания. Объявлен этот самый тег таким образом:

struct Cmd {
    /// The first byte of the command line string.
    cmd: u8
}

Согласно комментарию, поле cmd содержит первый байт строки. Другими словами &cmd — это указатель на Си-подобную строку, которая в конце концов заканчивается нулевым байтом. Безопасной версией этого тега является Cmd(&'static str). Когда вы будете преобразовывать из raw-версии в безопасную, вам нужно будет определить размер этой строки. Т.е. найти нуль-терминатор (символ с кодом 0). После этого вы можете использовать адрес и размер для преобразования этого в слайс при помощи slice::from_raw_parts(). В свою очередь этот слайс можно преобразовать в строку при помощи str::from_utf8() или str::from_utf8_unchecked(). Вы уже использовали их в лабе 1.

Реализация atags

Чтож. Теперь у нас есть всё необходимое для того, чтоб реализовать модуль atags, который лежит в pi/src/atags. Начните с реализации raw::Atag::next() из atags/raw.rs. Этот метод определяет адрес следующего ATAG, после текущего. Тут придётся прибегнуть к unsafe коду. Затем реализуйте вспомогательные методы и свойства для преобразования из raw-структур в безопасные, которые можно найти в atags/atag.rs. При реализации From<&'a raw::Cmd> for Atag придётся использовать немного unsafe-кода. В конце реализуйте трейт Iterator для Atags, который можно найти в atags/mod.rs. Тут тоже может потребоваться чуточку unsafe-кода.

Подсказки:

Вы можете (по крайней мере попытайтесь!) реализовать метод Atags::next() в три строчки кода.

Вы можете преобразовать из x: &T в *const u32 при помощи x as *const T as *const u32.

Обратное преобразование из x: *const T в &T можно выполнить при помощи &*x.

Вы можете выполнять арифметические операции над сырыми указателями при помощи add() sub() или offset.

Тестирование atags

Протестируйте собсвенную реализацию ATAGS. Попробуйте получить все значения через итератор и выведите всё это дело в консоль. Прям в kernel/src/kmain.rs. Вы должны увидеть по меньшей мере один из трёх тегов, отличных от NONE. При этом всём убедитесь, что реализация каждого ATAG соотвествует вашим ожиданиям. Как только реализация будет выполнена — переходите к следующей подфазе.

Подсказка: Используйте `{:#?} для более красивого вывода структур на консольку.

Что содержат теги с типом CMDLINE? [atag-cmdline]

Есть ли какая либо ценность в этих тегах? Какие аргументы прошивка вам передала? Как вы думаете, откуда это всё взялось и как это можно использовать?

Сколько памяти вам доступно согласно тегу MEM? [atag-mem]

Каков точный начальный адрес и размер доступной памяти, который сообщается в теге MEM? Насколько всё это близко к 1 гигабайту памяти, которая имеется у малинки?

Субфаза C: Warming Up (разогрев)

В этой подфазе мы подготовим всё необходимое для последующего написания двух распределителей памяти. Мы реализуем функции align_up и align_down, которые выравнивают адреса до степеней двойки. Помимо этого мы реализуем функцию memory_map, которая возвращает начальный и конечный адреса из системной памяти. Эта функция будет использоваться обоими аллокаторами для определения того, сколько доступно памяти для выделения.

Выравнивание

Адрес в памяти называется выровненным по N байтам, когда он нацело делится на N. Другими словами для адреса k будет верно k % n == 0. Обычно нам не требуется беспокоиться о выравнивании нашей памяти. Однако сейчас мы системные программисты. Наше повышенное внимание к этой теме связанно с тем, что аппаратные средства, протоколы и всякое такое, предписывают вполне себе определённые свойсва с точки зрения выравнивания. Напримен для 32-биной архитектуры ARM требуется, чтоб указатель стека был выровнен по 8-байт. Архитектура AArch64 (наш случай) требует выравнивание для указателя стека по 16 байт. x86-64 требует примерно того же. Адреса страниц памяти должны быть выровнены по 4 килобайта. Есть ещё много разных примеров, но мы уже видим, что без этого нам не обойтись.

В Няшном Си адреса памяти, которые возвращает аллокатор из libC, будут гарантированно выровнены по 8 байт на 32-битной системе и по 16 байт на 64-битной системе. Помимо этого вызывающий не может особо контроллировать выравнивание возвращаемого адреса памяти и должен сам за себя заботиться. Для этого есть, например, функция posix_memalign из стандарта POSIX.

Почему для Няшного Си выбраны именно такие свойства выравнивания? [libc-align]

Выбор гарантии в 8 или 16 байт для выравнивания для сишной функции malloc небезоснавателен. Почему в стандартной библиотеке Си были выбранны именно такие гарантии?

В Няшном Си объявления malloc() и free() выглядят вот таким образом:

void *malloc(size_t size);

void free(void *pointer);

В Rust на низком небезопасном уровне используются alloc и dealloc, которые выглядят вот таким образом:

// `layout.size()` is the requested size, `layout.align()` the requested alignment
unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;

// `layout` should be the same as was used for the call that returned `ptr`
unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout);

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

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

Как вы думаете, почему Rust разделяет обязанности между аллокатором и вызывающим кодом именно так? [onus]

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

Полезности: align_up и align_down

Когда вы будете реализовывать аллокаторы в следующих подфазах, вам будет полезно определять следующий или предыдущий выровненный адрес. Т.е. для адреса u следующий >= или <= u, который будет выровнен по степеням двойки. Там уже есть (нереализованные разумеется) align_up и align_down. Найти их можно в файле kernel/src/allocator/util.rs. Объявлены они примерно таким образом:

/// Align `addr` downwards to the nearest multiple of `align`.
/// Panics if `align` is not a power of 2.
fn align_down(addr: usize, align: usize) -> usize;

/// Align `addr` upwards to the nearest multiple of `align`.
/// Panics if `align` is not a power of 2.
fn align_up(addr: usize, align: usize) -> usize;

Релизуйте эти функции прямо сейчас. Вы можете поверить правильность этого процесса при помощи вызова make test или cargo test из каталога kernel. Сами тесты можно найти в файле kernel/src/allocator/tests.rs. Если в этой части всё правильно, то все тесты из align_util должны пройти.

Внимание: в процессе тестирования kprint{ln}! превращаются в вызовы print{ln}!, так что всё должно работать.

Подсказки:

Реализация будет занимать одну или две строки.

Реализации align_up и align_down будут очень похожи между собой.

Потокобезопасность

Аллокаторы памяти вроде malloc() из libC и наших двух, которые мы будем реализовывать, являются глобальными. Т.е. они могут быть вызваны везде и в любое время. В том числе и в любом потоке. Таким образом аллокаторы должны быть потокобезопасными. Rust очень серьёзно относится к потокобезопастности. По этой причине сложно реализовать аллокатор, который таковым являться не будет, даже если наша система всё ещё не имеет механизма для обслуживания параллелизма (например потоков).

Тема потокобезопасных аллокаторов памяти достаточно обширна. По этой теме можно найти достаточно много исследовательских работ. На текущий момент этой темы мы не будем касаться. Просто обернём наш распределитель памяти в Mutex. Эта обёртка уже есть в kernel/src/allocator/mod.rs. Почитайте сейчас весь этот код. Обратите внимание, что там есть реализация трейта Alloc. Именно благодаря этому Rust будет знать, что это вполне себе валидный аллокатор. Реализация этого трейта требуется для таких штук, как #[global_allocator] (в kmain.rs). Собсна #[global_allocator] — аннотация, которая добавляется к статически объявленному аллокатору, чтоб сказать Rust-у использовать его для всех этих Vec, String и прочих Box. Т.е. все вызовы alloc() и dealloc(), будут перенаправляться туда.

Переключение между реализациями аллокаторов

Реализация Alloc для Allocator из kernel/src/allocator/mod.rs просто перенаправляет свои вызовы в imp::Allocator после того, как разберётся с блокировкой mutex. При этом модуль imp виртуален. Он не ведёт к какому либо файлу в древе файловой системы. Вместо этого оно использует аннотацию вроде #[path = "bump.rs"] для того, чтоб сказать Rust-у, где его искать на самом деле. Это позволяет нам переключаться между двумя реализациями просто назначив другой путь для #[path]. Для начала мы используем bump-аллокатор из файла bump.rs. Потом стоит переключиться на bin-аллокатор из файла bin.rs.

Полезности: memory_map

Последний кусочек в файле kernel/src/allocator/mod.rs — это функция memory_map. Эта функция вызывается из Allocator::initialize(), которая затем будет вызываться из kmain(). Эта самая initialize() создаёт экземпляр структуры imp::Allocator и помещяет её внутрь нашей обёртки.

Функция memory_map возвращает начальный и конечный адреса свободной памяти в системе. Обратите внимание, что свободная память и вся доступная память это не одно и тоже. Т.е. нам нужно определять это всё, используя ATAGS. При этом в качесве начала участка свободной памяти мы берём конец памяти, используемой для кода ядра. За это отвечает уже объявленая переменная binary_end. Она должна указывать примерно туда, куда указывает _end (объявленный в layout.ld).

Реализуйте memory_map, используя Atags из субфазы B и переменную binary_end. Убедитесь, что эта функция возвращает правильное значение. После этого попробуйте вызвать что-то вроде String::from("Hi!"). Или любой другой способ выделить память в куче на ваш вкус. Убедитесь, что при этом будет вызываться panic!() из bump-аллокатора. Если memory_map работает корректно, а паники вызывает вполне себе определённый код из bump-аллокатора — можно перейти к следующей подфазе. Будем писать код, который исправит это недоразумение с паниками.

Субфаза D: Bump-аллокатор

В этой части мы будем реализовывать самый простейший аллокатор. Bump-аллокатор. Основная работа идёт в файлике kernel/src/allocator/bump.rs.

Bump-аллокатор работает следующим образом. При alloc аллокатор возвращает current как указатель. При этом выравнивая его по необходимости. Сразу после этого он увеличивает current на запрошенный размер (с учётом необходимого выравнивания конечно). Если память заканчивается, то возвращается ошибка. При dealloc ничего не происходит.

Чуть ниже есть картинка, которая показывает, что происходит после того, как выделяется 1 килобайт памяти, а затем ещё 512 байт. Обратите внимание, что в данном случае никаких проблем с выравниванием.

Задача собсвенно в том, чтоб реализовать всё необходимое в kernel/src/allocator/bump.rs. Т.е. функции new(), alloc() и dealloc() для bump::Allocator. Используйте align_up и align_down для того, чтоб гарантировать правильное выравнивание адресов. Для самопроверки предоставлены юнит-тесты. Их можно выполнить при помощи make test или cargo test из каталога kernel. Собственно должны пройти по крайней мере все allocator::bump_* тесты.

Внимание. Убедитесь, что вы не выполняете каких либо операций, потенциально приводящих к переполнению!

Используйте методы saturating_add и saturating_sub для предотвращения переполнения.

Как только все юнит-тесты успешно пройдут, попробуйте немного потестить вашу реализацию из kmain(). Например вот таким образом:

let mut v = vec![];
for i in 0..1000 {
    v.push(i);
    kprintln!("{:?}", v);
}

Как только реализация будет готова — переходите к следующей подфазе.

Как выглядит цепочка вызовов alloc? [bump-chain]

Допустим вы приостановили выполнение программы при вызове bump::Allocator::alloc(). Как будет выглядеть цепочка вызовов в этом месте? Другими словами: подробно объясните, как вызов v.push(i) приводит к вызову bump::Allocator::alloc().

Субфаза E: Bin-аллокатор

В этой подфазе мы будем реализовывать более сложный аллокатор: bin-аллокатор. Основная работа в файлике kernel/src/allocator/bin.rs.

Bin-аллокатор разделяет память на сегменты, классифицируя их по размеру. Каждый отдельный размерный класс (или бин по другому) содержит в себе связанный список из ссылок на память размером, определяемым этим классом. Каждый кусочек выделенной памяти округляется до ближайшего бина. Если в связанном списке бинов есть элемент — он вынимается и возвращается. Если нет свободной памяти в бине, то новая память возвращается из глобального пула. Деаллокации добавляют элемент в связанный список соответствующего бина.

Одна из популярных хипстерских идей состоит в том, чтоб присвоить каждому бину размер, кратный степеням двойки. Например аллокатор может выбрать разделение памяти на k - 2 бинов с размерами 2^n для таких n, которые начинаются с 3 и до k (2^3, 2^4… 2^k). Любой запрос на выделение или освобождение памяти, равный 2^3, будет обрабатываться бином 2^3. Размером между 2^3 и 2^4 бином с размером 2^4 и так далее:

• bin 0 (2^3 байта) будет обрабатывать размеры в промежутке (0, 2^3]
• bin 1 (2^4 байта) будет обрабатывать размеры в промежутке (2^3, 2^4]
• bin 2 (2^5 байта) будет обрабатывать размеры в промежутке (2^4, 2^5]
• bin k (2^k байта) будет обрабатывать размеры в промежутке (2^(k - 1), 2^k]
• ну вы уловили суть...

Связанный список

Уже реализован интузивный (intrusive) связанный список для адресов. Найти его можно в файле kernel/src/allocator/linked_list.rs. Кроме того в файлике kernel/src/allocator/bin.rs можно найти импорт LinkedList, что какбэ намекает на полезность его использования.

Что за интузивный связанный список такой?

В интузивном связанном списке указатели next (и previous если нужно) хранятся в самих передаваемых значениях. При этом такой список не требует для своей работы отдельной дополнительной памяти. С другой стороны пользователь должен предоставить хранилище в самом элементе.

Новенький чистый список создаётся при помощи вызова LinkedList::new(). Добавить адрес можно при помощи push(). Первый адрес (если он есть), может быть удалён и возвращён при помощи pop(). Или просто возвращён без удаления при помощи peek(). Примерно вот таким образом:

let mut list = LinkedList::new();
unsafe {
    list.push(address_1);
    list.push(address_2);
}

assert_eq!(list.peek(), Some(address_2));
assert_eq!(list.pop(), Some(address_2));
assert_eq!(list.pop(), Some(address_1));
assert_eq!(list.pop(), None);

При этом LinkedList предоставляет два итератора. Первый можно получить вызовом iter(). Он возвращает адреса. Второй можно получить вызовом iter_mut(). Этот возвращает Node, который относится к каждому адресу в списке. Методы value() и pop() могут использоваться для считывания значения или для вынимания значения соотвественно.

let mut list = LinkedList::new();
unsafe {
    list.push(address_1);
    list.push(address_2);
    list.push(address_3);
}

for node in list.iter_mut() {
    if node.value() == address_2 {
        node.pop();
    }
}

assert_eq!(list.pop(), Some(address_3));
assert_eq!(list.pop(), Some(address_1));
assert_eq!(list.pop(), None);

Прочитайте код LinkedList прямо сейчас. Обратите особое внимание на свойства безопастности, которые необходимо предоставить для push(). Скорее всего вы захотите использовать именно предоставленый LinkedList для реализации бинов в вашем распределителе памяти.

Почему удобно будет использовать именно интузивный связанный список? [ll-alloc]

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

Фрагментация

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

Обычно выделяют два вида фрагментации:

• Внутренняя фрагментация. Это объём памяти, который тратится на внутренние расходы за счёт округления (для гарантии корректного выравнивания например). В случае bin-аллокатора это разница между размером распределения и размером класса бина в котором он обрабатывается.
• Внешняя фрагментация. Объём памяти, затрачиваемый распределителем из-за невозможности использования свободной памяти для новых распределений. Для нашего bin-аллокатора это эквивалентно количеству свободного места в каждом бине, которое не может использоваться для обработки запроса на распределение достаточно большого запроса. Даже если сумма всех кусочков свободной памяти соотвествует или превышает запрошенный размер.

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

Реализация

Реализуйте bin-аллокатор в файле kernel/src/allocator/bin.rs. Конкретная конструкция распределителя (помимо того, что это bin-подобный распределитель) полностью зависит от вас. При этом распределитель обязан иметь возможность повторно использовать освобождённую память. Кроме того распределитель не должен подвергаться чрезмерной внутренней или внешней фрагментации. Предоставленые юнит-тесты проверяют все эти штуки. Запустить тесты можно при помощи make test или cargo test. И не забудьте заменить bump.rs на bin.rs в аннотации #[path] в файлике kernel/src/allocator/mod.rs. Ну т.е. задействовать вместо bump-аллокатора, аллокатор типа bin, когда последний будет готов.

Как только все тесты пройдут и вы поставите bin-аллокатор в качесве глобального — можно переходить к следующей фазе.

Как выглядит ваш аллокатор? [bin-about]

Кратко объясните общий дизайн вашего распределителя памяти. По меньшей мере стоит ответить на эти вопросы:

• Какие размеры для каждого класса (бина) вы выбрали и почему?
• Как ваш аллокатор обрабатывает разные выравнивания?
• В каких границах будет внешняя и внутренняя фрагментации для вашего дизайна аллокатора?

Каким образом можно уменьшить фрагментацию? [bin-frag]

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

Следующая половинка лабы в пути.