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


Нулевая лаба


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


Полезности



Фаза 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. Малинка использует только четыре из них. Нам они и интересны:


Имя Тип (tag) Размер Описание
CORE 0x54410001 5 или 2 (если пустой список) Используется как стартовый
NONE 0x00000000 2 Означаяет конец
MEM 0x54410002 4 Описывает кусочек физической памяти
CMDLINE 0x54410009 различный Передача аргументов ядру

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


struct Mem {
    size: u32,
    start: u32
}

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


ATAGS


Объединения (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 байт. Обратите внимание, что в данном случае никаких проблем с выравниванием.


BUMP


Задача собсвенно в том, чтоб реализовать всё необходимое в 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^42^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, что какбэ намекает на полезность его использования.


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

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

Новенький чистый список создаётся при помощи вызова 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]

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




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

Комментарии (30)


  1. Foror
    01.04.2018 13:51

    Собрать статистику паттернов работы? И в последствии генерировать код алокатора под конкретный паттерн?


    1. lain8dono Автор
      01.04.2018 14:54

      Это нереалистичная идея. Вычислительная сложность огромная. Условия меняются.


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


      1. Foror
        01.04.2018 18:41
        -1

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

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


        1. lain8dono Автор
          01.04.2018 22:20

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

          Отлично же! Проведите такое исследование. Я уже жду статью по этой теме и с удовольствием её почитаю.


  1. AngReload
    01.04.2018 18:54
    +2

    Последняя картинка несчастливая, следующую часть можно долго ждать (:


    1. lain8dono Автор
      01.04.2018 22:29

      Неа. Пока особых проблем со следующей частью не предвидится.


  1. vlad9486
    01.04.2018 22:01

    > cd, pwd, cat, ls.
    Зачем еще одна юникс подобная ОС? Если уж писать с нуля, то что то новое. Много проектов осдев пересмотрел, везде одно и тоже.


    1. lain8dono Автор
      01.04.2018 22:24

      А вот это годно. Есть какие либо мысли в развитие этой темы? Просто другие названия команд точно не подойдут. Что-то в замен концепции командной строки?


      1. vlad9486
        01.04.2018 22:38

        * система типов раста на уровне ОС, гарантии раста между исполняемыми файлами;
        * типизированные бинарники;
        * запуск кода на safe rust без аппаратной защиты;
        www.linux.org.ru/forum/talks/13995742


        1. lain8dono Автор
          01.04.2018 23:26
          +1

          запуск кода на safe rust без аппаратной защиты

          Это называется "модули ядра". Только для доверенного кода. Т.е. только то, что целиком контролируется. Все third-party драйвера яб вынес в пользовательское пространство (как в микроядрах).


          типизированные бинарники

          Они и так типизированы все. См. спецификацию ELF например. Или что-то ещё?


          система типов раста на уровне ОС, гарантии раста между исполняемыми файлами

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


          1. vlad9486
            01.04.2018 23:42

            > Это называется «модули ядра»
            Я знаю что такое модуль ядра и предлагал другое.

            > Они и так типизированы все
            Они не типизированны вообще. По ельфу нельзя проверить что функция принимает инт и указатель, а не три флота.

            > Нет идей, зачем это нужно
            Я же написал: гарантии. Зачем тогда раст нужен, если его гарантии не нужны? Сейчас же, как только другой бинарник, сразу же FFI и unsafe. Интерфейс должен быть простым, но, гораздо важнее что бы он был документированным. Статическая типизация прямо в бинарнике — часть документации. Это декларация протокола, которую может проверять ОС, почему бы нет?


            1. lain8dono Автор
              01.04.2018 23:51

              Я знаю что такое модуль ядра и предлагал другое.

              Что? Всмысле ПОДРОБНО.


              По ельфу нельзя проверить что функция принимает инт и указатель, а не три флота.

              Можно впихнуть раздел в ELF с информацией об этом.


              Я же написал: гарантии.

              Пользователь может менять бинарник любым доступным способом. Ваши действия?


              1. vlad9486
                01.04.2018 23:58

                Можно впихнуть раздел в ELF с информацией об этом.

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

                Ваш пользователь крут. А еще пользователь может разбить компьютер молотком. ОС и от этого должна защищать? Я би предложил такое: пользователь ставит пакеты из репозитория или стора, бинарники подписанны и менять их нельзя. В идеале, бинарники вообще содержат не машинный код, а некоторый байткод, по которому можно валидировать type-safety, который компилируется во время установки пакета.


                1. lain8dono Автор
                  02.04.2018 00:10

                  Мне жаль вас разочаровывать, но я ничего не понял. Напишите ПОДРОБНОЕ описание того, чего вы хотите запилить. А пока держите эту тематическую картинку:



                  1. vlad9486
                    02.04.2018 00:50

                    Отвечу в одном посте.

                    Чувствую, что модераторы не похвалят за картинку, но мне лично все равно.

                    Смотрите: задача микроядра — организовать общение между процессами. Когда общение идет по фиксированному протоколу — оно безопасно и надежно. Когда общение — это jmp на адресс, у нас нету гарантий, компилятор не может проверить типы и все, приплыли, раст не дает ничего. Фишка раста — статическая верификация всего что только можно, он в этом впереди многих языков. Но ОС ему мешает.

                    А теперь конкретика, как я это вижу. Интерфейс — это список сигнатур функций, он характеризуется своим UUID, ОС держит список интеррфейсов и соответствующих UUID. Нужно бинарное представление сигнатур, типа этого developer.apple.com/library/content/documentation/Cocoa/Conceptual/ObjCRuntimeGuide/Articles/ocrtTypeEncodings.html что бы можно было сохранять это. Каждый файл с машинным кодом декларирует интерфейсы и зависит от интерфейсов, соответствующие UUID хранятся в хедере. Ядро, когда грузит бинарник, грузит зависимости, если нужно. Конечно же, программист генерирует UUID для своих интерфейсов. Когда меняется API, UUID тоже меняется.
                    (Всюду UUID можно заменить на человекочитаемое имя с версией, это уже по вкусу).

                    Опишите, как вы будете реализовывать гарантии того, что пользователь не может нарушать эти гарантии.

                    Компилятор раста проверяет типы. Будет ошибка компиляции.

                    Если же юзер может модифицировать бинарник руками и у него декларация (UUID) не сходится с тем что внутри — это его проблема. Он так же может и «rm -Rf /» сделать, и вообще, использовать молоток.


                    1. lain8dono Автор
                      02.04.2018 02:05

                      Это не ПОДРОБНО. Это даже не подробно. Это даже на общие идеи не тянет. ПОДРОБНО — это примерно под 100 страниц A4 (я по минимуму беру). подробно — тоже принимается. Это примерно 20-30 страниц. Примерно на хорошую годную публикацию.


                      Чувствую, что модераторы не похвалят за картинку, но мне лично все равно.

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



                      задача микроядра — организовать общение между процессами

                      А ещё изолировать процессы друг от друга. Микроядро тоже занимается этим.


                      Фишка раста — статическая верификация всего что только можно, он в этом впереди многих языков.

                      Вы не понимаете, какие гарантии даёт Rust. Вы читали книгу версии 2 и номикон? Перечитайте.


                      Нужно бинарное представление сигнатур, типа этого

                      Я не понял намёка.


                      Компилятор раста проверяет типы. Будет ошибка компиляции.

                      А что с кодом на Няшном? Или на Крестах? Или на асме? Или на хачкеле? Или на [любой другой ЯП]? Я тоже люблю заниматься таким бесполезным делом, как переписывание с одного ЯП на другой, но желания переписать абсолютно всё у меня както не возникает.


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


                      С uuid тоже не понел. Что это даёт кроме того, что эти uuid надо генерировать зачем-то?


                      1. vlad9486
                        02.04.2018 11:37

                        Что то лень писать 100 страниц :)

                        А ещё изолировать процессы друг от друга. Микроядро тоже занимается этим.
                        Да. Но виртуальные адрессные пространства — не единственный способ сделать это.

                        А что с кодом на Няшном? Или на Крестах? Или на асме? Или на хачкеле? Или на [любой другой ЯП]?
                        Все заработает. Любой другой ЯП предоставляет что то вроде
                        int main(int argc, char* argv[]) { ... }

                        Это одна функция, которой соответствует дефолтный интерфейс. Я же всего лишь предлагаю отказаться от динамической типизации здесь. Массив строк — это динамический тип, который превращается в рантайме во что угодно. А нужно что бы функции принимали настоящие типы и ассоциированные лайфтаймы (если раст).


          1. vlad9486
            01.04.2018 23:47

            > яб вынес в пользовательское пространство
            Ну так одно другому не мешает. Микроядра — это не только отдельные адресные пространства, а в первую очередь изоляция. Для safe rust кода можно статически доказать эту самую изоляцию не используя аппаратную защиту. Это очень в духе раста и c++, проверять статически и не тратить ресурсы в рантайме.


            1. lain8dono Автор
              01.04.2018 23:54

              Для safe rust кода можно статически доказать эту самую изоляцию не используя аппаратную защиту.

              Зачем? Профита никакого. Про производительность можно говорить, когда есть бенчмарки. И не секундой раньше.


              1. vlad9486
                02.04.2018 00:09

                Не нужна причина что бы что-то не делать. Зачем защищать память процесса, если того от чего защищаемся гарантированно не будет?


                1. lain8dono Автор
                  02.04.2018 00:15

                  чего защищаемся гарантированно не будет

                  Опишите, как вы будете реализовывать гарантии того, что пользователь не может нарушать эти гарантии.


        1. lain8dono Автор
          01.04.2018 23:33

          www.linux.org.ru/forum/talks/13995742
          Профит: небольшое увеличение производительности

          Когда будет бенчмарк, тогда и поговорим.


        1. lain8dono Автор
          01.04.2018 23:48

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


          1. lain8dono Автор
            02.04.2018 00:17

            А хотя нет. Можно чутка побеседовать.


      1. vlad9486
        01.04.2018 22:41

        Взамен коммандной строки ничего не хочу. Но язык (bash) поменять нужно, урезанный хаскель взять, например. И сделать ядро, которое будет всего лишь jit компилятором этого языка. Саму ОС писать на нем.


        1. lain8dono Автор
          01.04.2018 23:30

          Но язык (bash) поменять нужно

          bash менять не нужно. Пусть себе лежит. У нас кстати нет чего либо похожего. Тупо интерактивная строка.


          урезанный хаскель взять

          Яб tcl взял.


          которое будет всего лишь jit компилятором этого языка

          Как на счёт wasm? У меня есть идея запилилить песочницу с wasm в качестве байткода и чем-то вроде cloudabi в качестве набора системных вызовов.


          1. vlad9486
            01.04.2018 23:49
            +1

            > У нас кстати нет чего либо похожего
            Подозреваю, что создатели баша думали так же… поначалу. А потом было уже поздно, народ накостылил кучу всего.
            > Яб tcl взял.
            на вкус и цвет…
            > У меня есть идея
            нету возражений, пилите.


            1. lain8dono Автор
              01.04.2018 23:56

              нету возражений, пилите.

              Запилю, если не будет лень. Может что-то похожее.


              А потом было уже поздно, народ накостылил кучу всего.

              Предполагается, что ОС сможет выполнять любые проги. В том числе и bash. Это полностью на совести клиента.


              1. vlad9486
                02.04.2018 00:00

                И в мыслях не было запрещать пользователю что-то выполнять.


                1. lain8dono Автор
                  02.04.2018 00:28

                  А у меня в мыслях есть одна такая, которая желает зарезать возможности пользователя на столько, насколько это вообще в принципе возможно. Желательно без потерей производительности. И при этом всё предоставить минимально необходимый функционал.