#+LANG: ru #+TITLE: Семинар 6: Аллокация памяти, арихитектура * Что такое куча В рамках этого семинара мы познакомимся с тем, как может быть устроена куча. С данными связана такая характеристика как /время жизни/. Это тот промежуток выполнения программы, когда обращаться к этим данным корректно и не ведёт к неопределённому поведению. Данные в C могут быть выделены следующими способами: - Автоматически: локальные переменные функций создаются в момент их запуска и живут до их завершения. Правильно сказать: гарантированное время жизни переменных от запуска функции до её завершения. Зная, что компиляторы оптимизируют локальные переменные, мы больше не будем говорить, что они выделяются в стеке. - Глобальные переменные и локальные переменные функций, если локальные переменные помечены =static=. И те, и другие создаются в глобальной области данных. Других гарантированно возможных способов выделить память в "голом" C нет. Чтобы выделить память в стеке или в глобальной области данных необходимо знать, сколько именно памяти понадобится, уже в момент компиляции. Однако иногда мы не знаем этого заранее; например, когда принимаем по сети размер строки и саму строку; её нужно где-то выделить, а сколько под это выделять байт --- неясно. В таком случае приходится использовать =аллокаторы= --- специальные программы, которые умеют резервировать области памяти и управляют тем, где будут находиться блоки памяти, которые программист запрашивает. Функции =malloc=, =calloc=, =realloc=, =free= --- это интерфейс к аллокатору из стандартной библиотеки C. С помощью вызова =malloc= можно выделить память, время жизни которой будет неопределённо долгим. Она может существовать до завершения работы программы, как глобальные переменные, или быть возвращена для переиспользования с помощью функции =free=. Некоторые советы по работе с памятью: - Если вам нужно выделить память, подумайте, нельзя ли её выделить в стеке. Это всегда проще, чем в куче. - Не стесняйтесь передавать не очень большие структуры по значению. * Аллокатор блоков Самый простой аллокатор возвращает блоки фиксированного размера. Их можно заполнять не полностью, остаток будет теряться. Помимо блоков нужно хранить карту их занятости; здесь она хранится в виде массива =bool='ов, но для компактности можно было бы упаковывать булевы значения по восемь в каждый байт. #+begin_src c #define HEAP_BLOCKS 80 #define BLOCK_CAPACITY 1024 struct heap { struct block { char contents[BLOCK_CAPACITY]; } blocks[HEAP_BLOCKS]; bool is_occupied[HEAP_BLOCKS]; } global_heap = {0}; #+end_src *Задание 1* Изучите файл [[./heap-0.c][heap-0.c]] и реализуйте в нём недостающие функции для резервирования блока и для возвращения блока в пул доступных. Почему =block_id= содержит ссылку на =struct heap=? ** Аллокатор множества блоков В предыдущем аллокаторе есть несколько существенных недостатков: - блоки и заголовки перемежаются, и размер блоков фиксирован, поэтому нельзя занять несколько блоков подряд. - размер блока фиксирован, и потому мы можем нести накланые расходы по памяти. *Задание 2* Модифицируйте аллокатор так, чтобы он умел выделять несколько блоков подряд. См. файл [[./heap-1.c][heap-1.c]]. У блоков теперь будет статус с большей гранулярностью, нежели "занят --- не занят". Придумайте тесты для вашего кода для проверки всех особых случаев. #+begin_src c enum block_status { BLK_FREE = 0, BLK_ONE, BLK_FIRST, BLK_CONT, BLK_LAST }; #+end_src Блоки будут связываться в одну из следующих конфигураций: #+begin_src c BLK_FREE // свободный блок BLK_ONE // единичный занятый блок. // после него или свободный или занятый другими данными. BLK_FIRST, BLK_CONT, BLK_CONT, BLK_LAST // последовательность блоков с началом, серединкой и концом. BLK_FIRST, BLK_LAST // то же, но без серединки. #+end_src Выделение памяти должно привести к выделению адекватного количества блоков; освобождение памяти должно привести к освобождению блоков начиная с указанного, если этот блок -- начало. ** Чего не хватает для эффективности? Чтобы аллокатор стал более эффективным, можно отказаться от фиксированного размера блока, снабдив каждый из них заголовком и организовав в связный список. Затем из единой непрерывной кучи можно сделать несколько фрагментов и добавить довыделение памяти (а именно страниц от операционной системы) в случае, когда куча закончилась. Это и будет темой четвертой лабораторной работы. * Задание 3 В качестве последнего задания на 2 балла вы можете выбрать одно из двух заданий. ** Первый вариант Первый вариант задания - это развитие принтера, который вы увидели на прошлом семинаре. Добавьте туда: - вычислитель, который умеет вычислять формулы. Сделайте его расширяемым, так же, как сделан принтер. Подсказка: в отличие от принтера, который не имеет состояния, для вычисления потребуется накапливать состояние, поэтому функции будут иметь больше аргументов, нежели принтеры для узлов. - парсер, который сможет распознавать верные формулы из сложения, умножения, деления и вычитания. Не забудьте про скобки! - принтер, который будет выводить выражение используя постфиксную запись (обратная польская запись, без использования скобок). В качестве стартовой точки для выполнения этого задания можете использовать расширенный вариант принтера ([[./ast.h][ast.h]], [[./ast.c][ast.c]], [[./main.c][main.c]], [[./makefile][makefile]]), в который уже включен базовый токенайзер ([[./tokenizer.h][tokenizer.h]], [[./tokenizer.c][tokenizer.c]]), а также реализация стека и очереди для абстракнтых типов ([[./ring.h][ring.h]]). ** Второй вариант Второй вариант задания - это реализация несложной структуры данных как абстрагированного модуля с непрозрачным типом. Ему посвящена эта заметка. *Изначальный код* У вас есть код внутри одной функции =main=, который реализует расширяемый массив (вектор). Изучите его. #+begin_src c /* bad.c */ #include #include #include int main() { int64_t *array = malloc(sizeof(int64_t) * 5); // вместимость -- сколько памяти выделено size_t capacity = 5; // количество -- сколько памяти по факту используется из выделенной. size_t count = 0; // заполните массив квадратами чисел от 0 до 100 // если не хватает места, расширяем в два раза for (size_t i = 0; i <= 100; i++) { if (count == capacity) { array = realloc(array, sizeof(int64_t) * capacity * 2); capacity = capacity * 2; } array[count++] = i * i; } for (size_t i = 0; i < 100; i++) { printf("%" PRId64 " ", array[i]); } return 0; } #+end_src Расширяемый массив в отличие от обычного имеет нефиксированный размер, в конец такого массива можно добавлять элементы. Как это работает: - Мы выделяем память с запасом. - Мы храним два дополнительных числа: количество выделенных слотов под элементы и количество заполненных слотов в массиве. - Пока у нас хватает выделенных слотов, мы просто дописываем элементы в массив, увеличивая количество занятых слотов. - Если слотов перестало хватать, то увеличиваем количество слотов в 2 раза (или линейно на некоторый фиксированный размер). Для этого используем =realloc= чтобы скопировать выделенную память в расширенный участок. *Вопрос* Прочитайте раздел =man malloc= про функцию =realloc=. *Задание (второй вариант)* Ваша задача --- выделить из этого кода как минимум модуль с реализацией вектора, снабжённый заголовочным файлом. - Вектор должен быть реализован как [[https://stepik.org/lesson/408352/step/6][непрозрачная структура данных]]. - Доступ к его элементам должен быть контролируем и осуществляться через getter и setter. - Постарайтесь максимально переиспользовать код и ничего не дублировать. - Вывод вектора реализуйте как отдельную функцию, которая принимает =FILE*=, в который нужно вывести его содержимое. Эту функцию можно также разбить на функцию =foreach= и принтер одного элемента. - Стремитесь сделать настолько маленькие функции, насколько возможно. Ваша реализацяия как минимум должна позволять: - Получить доступ к любому элементу. - Получить информацию о текущей длинне массива и количестве выделенной памяти. - Добавить элемент в конец массива. - Добавить другой массив в конец массива (скопировать данные). - Изменить размер массива на заданный (при необхоимости выделить память). - Изменить размер массива на меньший с освобождением неиспользуемой памяти. - Освободить память. - Вывести массив в указанный поток вывода. В результате должна получиться программа из нескольких файлов, которая делает то же самое, но в которой =main= содержит только заполнение вектора числами и вызов функции, печатающей его в =stdout=. Прочитайте заметку [[[https://gitlab.se.ifmo.ru/c-language/main/-/wikis/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%B0-%D1%81%D1%82%D0%B8%D0%BB%D1%8F-%D0%BD%D0%B0%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D1%8F-%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC-%D0%BD%D0%B0-C][Правила хорошего стиля]]] --- ваш код должен им соответствовать.