Comments 35
Упc :-)
Спасибо за материал.
Будет ли в некст статьях, как к кастомному аллокатору прикрутить leak, address санитайзеры ?
Велкам.
По идее санитизеры должны само приделаться в случае если библиотека оверрайдит malloc/free.
https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html#index-fsanitize_003dleak
По запросам трудящихся могу посмотреть, но после юнит теста и дальше по плану еще кое какие вещи есть :-)
А в чем профит придерживать внутреннего GNU codestyle?
Считается что не будет совпадений с идентификаторами в коде пользователей либы.
Наоборот, считается, что такой код будет конфликтовать с кодом стандартной библиотеки. Стандарт запрещает использовать идентификаторы __put_to_header, __size, _MemoryBlock_t в пользовательском коде. Дополнительно POSIX запрещает использовать суффикс _t в пользовательском коде.
Мы сейчас говорим про os dev. Стандартная библиотека не используется, правила POSIX не применимы. Идеологически этот код - скорее часть той самой стандартной библиотеки, чем пользовательского кода.
Но при том используется C++, а поэтому 1) часть стандартной библиотеки (freestanding) все же может использоваться, и 2) нет такой проблемы с потенциальными конфликтами - достаточно положить всю требуху в namespace или там в класс и называть нормально (поскольку код аллокатора не включает пользовательские хедеры, то пересечения с "левыми" макросами не будет, а остальное будет скрыто пространством имен), а вне нее вынести только malloc/free/тд публичные аксессоры. А вот сам namespace/class стоит назвать как зарезервированное слово.
Стандартная библиотека не используется
Откуда тогда взялись uint8_t, std::size_t и др. И потом #include <vector> #include "allocator.h" using namespace std; Такой код никогда не прошёл бы ревью.
нет такой проблемы с потенциальными конфликтами - достаточно положить всю требуху в namespace
И это не так. Такие идентификаторы запрещённы в любых namespace.
Это код теста что бы запустить у себя и проверить. Далее будет юнит тест. Тоже будет проходиться в системе. using namespace std уйдет в итоговой демке которая будет грузится в эмуляторе только. Но до этого еще далеко.
Зависимости cstring и cerrno будут предоставлены, если нужно я расскажу в отдельной статье как
Откуда тогда взялись uint8_t, std::size_t и др
Либо из freestanding части c++, либо сделано самостоятельно
#include <vector> #include "allocator.h" using namespace std;
Это вырожденный случай - тест части библиотеки target os в тестовом бинаре на host os.
Такие идентификаторы запрещённы в любых namespace.
Вы не поняли мой посыл. Я имел в виду, что в C++ можно использовать "пользовательские" идентификаторы в библиотечном коде (точнее, его непубличной части, которая компилируется отдельно от пользовательского кода и которую пользователь библиотеки никак и никогда не увидит и которая сама никогда не увидит ни строчки пользовательского кода - даже через предефайны в опциях компилятора), если положить их в namespace. Сам namespace нужно назвать зарезервированным словом, но это единственное потенциальное пересечение с "чужой"/host библиотекой.
Я разрабатывал стандартрую библиотеку для ОС и использовал соответствующий стиль. Он такой, что бы не было пересечений, вроде как это так объясняется. Примеры пересечений выдумывать не стану )
Мы сейчас говорим про os dev
Вообще ни разу. Аллокаторы используются много где. В геймдеве, например.
нет такой проблемы с потенциальными конфликтами
собственно возвращаемся к исходному вопросу - а профит-то тогда какой.
Для реализации стандартной библиотеки соответствующий стиль кода. Вообще Главный плюс в том, что научитесь понимать алгоритмы в STL со временем. Сначала будет бить по глазам, а потом ревью пойдет как по маслу :-D
Что бы привыкнуть, лучше всего таким стилем писать имо
Аллокаторы везде используются где есть распределение памяти. std::cout то же в себе что то распределяет, так что даше Hello world на С++ содержит их. Я лишь говорю что я пишу конкретно про осдев, но принцип да, можно везде применять. Безусловно. Как сортировку например. Можно в игре массив сортировать, можно и ОС. Алгоритм это алгоритм
спасибо за статью, у Вас на каждом указателе uint8_t висит такой блок который в начале статьи суть в этом да?
Если вы про заголовок, то да. Это свойство блока памяти только. См тут: https://www.clear.rice.edu/comp321/html/laboratories/lab08/ или в этой книге на русском:
https://vk.com/wall-54530371_498 10.9.12
спасибо, а функция '__try_merge_free_blocks();'. не будет вызывать фрагментацию ?
Каким образом? Она пытается слить последовательно идущие блоки друг с другом.
Один вызов пытается сделать что то такое:
[free block] [free block] [free block] @[allocated block]@[free block] --
--> [free block * 3] @[allocated block]@[free block]
Другое дело что список односвязный и если свободен предыдущий блок, а не следующий, то она этого не поймет так как двигается по списку вперед. Из вывода теста аллокатора видно что это порождает фрагментацию в конце:
_MemoryBlock: service block address 0x55efd7b4beb8 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55efd7b4bec8 size 15832 size with overhead 15840 state free
_MemoryBlock: block address 0x55efd7b4fca8 size 504 size with overhead 512 state free
_MemoryBlock: service block address 0x55efd7b4fea8 size 8 size with overhead 16 state allocated
Это происходит именно поэтому. При освобождении блока (самый большой блок был свободен изначально) она вызывается для блока переданного в mem_free, но не для предыдущего. Таким образом вся память корректно освобождается в тесте в итоге, но она фрагментирована
Так она занимается дефграментацией
Делал примерно также, но список был двухсвязанный и хранился указатель на максимальный блок. Немного сложенее код был, но время alloc/free было меньше.
Отлично
Считаю, что использование каких-либо структур вокруг выделяемых аллокатором блоков, которые напрямую влияют на работу аллокации/деаллокации, не лучшей идеей. В случае коррапта кучи (случайного или намеренного) все может рухнуть совершенно непредсказуемым и трудно отлаживаемым образом (или лихо проломится).
это сложно назвать аллокатором, НОРМАЛЬНЫЙ аллокатор должен работать с битмапом, получать информацию от биоса/бутлоадеров про память (мемори ентри и т.д) и выделять страницы (4кб и т.д)
Разве что, совсем учебный аллокатор. Потому что, линейная сложность от числа выделенных блоков неприемлема. В реальных сценариях аллоцируют по 100500 миллионов нод какого-нибудь дерева/списка, и этот аллокатор встанет.
Мы же реализуем немного более сложную схему, но за то с вдвое меньшим оверхедом, т.е. односвязный список
В реальном коде экономии не случится. Для совместимости с ABI x64, аллокатор должен возвращать адреса, выровненные на 0x10, а это значит, между блоками у нас есть место на 2 указателя.
Вам во вторую часть :-)
Пожалуй не помешало бы оглавление в начале )
Статья интересная. Вопрос по коду. В функции __put_to_header есть строка:
*reinterpret_cast<size_t*>(__header()) = __size | static_cast<int>(__state);тут __state кастуется в int, хотя __size тип size_t. Почему бы сразу не кастовать его в size_t?
OSDEV: Разработка аллокатора на С++ часть 1. Неявный список свободных блоков с граничными тегами