Теперь мы вплотную подошли к ещё одному важному аспекту работы с памятью в ядре ОС - динамическое выделение участков памяти произвольного размера.
Область памяти используемая для размещения динамических объектов созданных программой в момент выполнения называется "куча" (англ. heap - куча, ворохб масса, множество). Кроме того кучей принято называть и систему управления динамической памятью, в частности и реализованную в ядре ОС.
Мы уже выделяли память под информационные структуры ядра, однако делали это непосредственным указанием адреса, на который ссылается указатель (например так мы создали каталог таблиц страниц). Однако такой подход неверен - рано или поздно мы запутаемся в свободных и занятых адресах, выделим перекрывающиеся блоки памяти и сотворим ещё что-то приводящее нас к краху. Реализуем нормальный механизм выделения памяти в ядре - кучу ядра.
1. Организуем кучу в ВАП ядра
Для начал надо отобразить память, в которой будет размещаться куча. А для этого сначала распределим виртуальное адресное пространство между ядром и пользовательскими процессами, которые рано или поздно будут работать в нашей системе.
У нас 4 Гб виртуального адресного пространства. Чтобы долго не ломать голову, поделим это ВАП пополам: адреса 0x00000000 - 0x7FFFFFFF для ядра и сервисов операционной системы, а адреса 0x80000000 - 0xFFFFFFFF для процессов пользовательского режима. Зафиксируем эти значения в виде констант в менеджере памяти
Листинг 60. Определение некоторых констант (memory.h)
Константами же определяем и параметры кучи: пусть её размер будет 16 Мб, пусть она будет расположена в конце ВАП ядра. Кроме того, определим размер памяти для хранения информации об объектах кучи, для начала пусть это будет 4 Мб.
Для описания кучи необходимо создать соответствующую структуру
Листинг 61. Структуры для описания кучи (memory.h)
Каждый блок выделенной памяти описывается адресом своего начала и размером. Смешно, но блок в один байт требует для своего описание целых 8 байт служебной информации ), именно таков размер структуры memory_block_t. Информация о вей куче будет хранится в heap_t структуре содержащей информацию о расположении кучи в ВАП и массив данных о распределенных блоков, их числе и общем размере кучи.
Теперь можно отобразить память под кучу.
Листинг 62. Отображение памяти под кучу (memory.c)
Код добавляем в конец функции инициализации менеджера памяти. Чтобы было ясно, как мы выполняем отображение памяти, приведу схему распределения физической памяти под кучу.
/* Если мы перебрали все блоки и не нашли ничего - выходим */
if (i == kheap.count)
{
return;
}
/* Сдвигаем список блоков вниз, затирая данные найденного блока */
for (i = block_idx; i < kheap.count - 1; i++)
{
kheap.blocks[i].base = kheap.blocks[i+1].base;
kheap.blocks[i].size = kheap.blocks[i+1].size;
}
/* Уменьшаем число выделенных блоков памяти */
kheap.count--;
}
Надо сказать это достаточно простая реализация функции освобождения памяти - мы просто находим блок по его адресу и удаляем из списка блоков информацию о нем, модифицируя структуры кучи.
У нас 4 Гб виртуального адресного пространства. Чтобы долго не ломать голову, поделим это ВАП пополам: адреса 0x00000000 - 0x7FFFFFFF для ядра и сервисов операционной системы, а адреса 0x80000000 - 0xFFFFFFFF для процессов пользовательского режима. Зафиксируем эти значения в виде констант в менеджере памяти
Листинг 60. Определение некоторых констант (memory.h)
/*--------------------------------------------------------
// ВАП пользователя
//------------------------------------------------------*/
#define USER_MEMORY_START ((void*) 0x80000000)
#define USER_MEMORY_END ((void*) 0xFFFFFFFF)
/*--------------------------------------------------------
// ВАП ядра
//------------------------------------------------------*/
#define KERNEL_MEMORY_START ((void*) 0x00000000)
#define KERNEL_MEMORY_END ((void*) 0x7FFFFFFF)
/*--------------------------------------------------------
// Параметры кучи ядра
//------------------------------------------------------*/
/* Размер кучи */#define KERNEL_HEAP_SIZE 0x1000000
/* Адрес начала кучи в памяти */
#define KERNEL_HEAP_BASE ((void*)(KERNEL_MEMORY_END-KERNEL_HEAP_SIZE))
/* Размер области под служебную информации кучи */
#define KERNEL_HEAP_BLOCK_INFO_SIZE 0x400000
// ВАП пользователя
//------------------------------------------------------*/
#define USER_MEMORY_START ((void*) 0x80000000)
#define USER_MEMORY_END ((void*) 0xFFFFFFFF)
/*--------------------------------------------------------
// ВАП ядра
//------------------------------------------------------*/
#define KERNEL_MEMORY_START ((void*) 0x00000000)
#define KERNEL_MEMORY_END ((void*) 0x7FFFFFFF)
/*--------------------------------------------------------
// Параметры кучи ядра
//------------------------------------------------------*/
/* Размер кучи */#define KERNEL_HEAP_SIZE 0x1000000
/* Адрес начала кучи в памяти */
#define KERNEL_HEAP_BASE ((void*)(KERNEL_MEMORY_END-KERNEL_HEAP_SIZE))
/* Размер области под служебную информации кучи */
#define KERNEL_HEAP_BLOCK_INFO_SIZE 0x400000
Константами же определяем и параметры кучи: пусть её размер будет 16 Мб, пусть она будет расположена в конце ВАП ядра. Кроме того, определим размер памяти для хранения информации об объектах кучи, для начала пусть это будет 4 Мб.
Для описания кучи необходимо создать соответствующую структуру
Листинг 61. Структуры для описания кучи (memory.h)
/*----------------------------------------------------
// Структура описывающая блок выделенной памяти
//--------------------------------------------------*/
typedef struct
{
void* base; /* Адрес начала */
size_t size; /* Размер в байтах */
}__attribute__((packed)) memory_block_t;
/*----------------------------------------------------
// Структура кучи
//--------------------------------------------------*/
typedef struct
{
memory_block_t* blocks; /* Массив данных о выделенных блоках */
void* start; /* Виртуальный адрес начала кучи */
void* end; /* Виртуальный адрес конца кучи */
size_t size; /* Размер кучи */
size_t count; /* Число выделенных блоков памяти */
}__attribute__((packed)) heap_t;
// Структура описывающая блок выделенной памяти
//--------------------------------------------------*/
typedef struct
{
void* base; /* Адрес начала */
size_t size; /* Размер в байтах */
}__attribute__((packed)) memory_block_t;
/*----------------------------------------------------
// Структура кучи
//--------------------------------------------------*/
typedef struct
{
memory_block_t* blocks; /* Массив данных о выделенных блоках */
void* start; /* Виртуальный адрес начала кучи */
void* end; /* Виртуальный адрес конца кучи */
size_t size; /* Размер кучи */
size_t count; /* Число выделенных блоков памяти */
}__attribute__((packed)) heap_t;
Каждый блок выделенной памяти описывается адресом своего начала и размером. Смешно, но блок в один байт требует для своего описание целых 8 байт служебной информации ), именно таков размер структуры memory_block_t. Информация о вей куче будет хранится в heap_t структуре содержащей информацию о расположении кучи в ВАП и массив данных о распределенных блоков, их числе и общем размере кучи.
Теперь можно отобразить память под кучу.
Листинг 62. Отображение памяти под кучу (memory.c)
heap_t kheap; /* Куча ядра */
/*-----------------------------------------------------
// Инициализация менеджера памяти
//---------------------------------------------------*/
void init_memory_manager(u32int stack)
{
.
// Инициализация менеджера памяти
//---------------------------------------------------*/
void init_memory_manager(u32int stack)
{
.
.
.
.
/* Создаем кучу ядра */
/* Отображаем страницы под кучу */
map_pages(KERNEL_PAGE_TABLE,
KERNEL_HEAP_BASE,
(physaddr_t) (KERNEL_MEMORY_START +
KERNEL_SIZE +
KERNEL_HEAP_BLOCK_INFO_SIZE),
KERNEL_HEAP_SIZE >> PAGE_OFFSET_BITS,
PAGE_PRESENT | PAGE_WRITEABLE);
/* Отображаем страницы для служебной информации */
map_pages(KERNEL_PAGE_TABLE,
(void*) (KERNEL_MEMORY_START + KERNEL_SIZE),
(physaddr_t) (KERNEL_MEMORY_START + KERNEL_SIZE),
KERNEL_HEAP_BLOCK_INFO_SIZE >> PAGE_OFFSET_BITS,
PAGE_PRESENT | PAGE_WRITEABLE);
/* Передаем структуре кучи указатель на
массив служебных данных кучи */
kheap.blocks = (memory_block_t*) (KERNEL_MEMORY_START +
KERNEL_SIZE);
/* Чистим этот массив */
memset(kheap.blocks, 0, KERNEL_HEAP_BLOCK_INFO_SIZE);
kheap.count = 0; /* Число выделенных */
/* блоков памяти */
kheap.start = KERNEL_HEAP_BASE; /* Начало кучи */
kheap.size = KERNEL_HEAP_SIZE; /* Размер кучи */
kheap.end = kheap.start + kheap.size; /* Конец кучи */
}
.
.
/* Создаем кучу ядра */
/* Отображаем страницы под кучу */
map_pages(KERNEL_PAGE_TABLE,
KERNEL_HEAP_BASE,
(physaddr_t) (KERNEL_MEMORY_START +
KERNEL_SIZE +
KERNEL_HEAP_BLOCK_INFO_SIZE),
KERNEL_HEAP_SIZE >> PAGE_OFFSET_BITS,
PAGE_PRESENT | PAGE_WRITEABLE);
/* Отображаем страницы для служебной информации */
map_pages(KERNEL_PAGE_TABLE,
(void*) (KERNEL_MEMORY_START + KERNEL_SIZE),
(physaddr_t) (KERNEL_MEMORY_START + KERNEL_SIZE),
KERNEL_HEAP_BLOCK_INFO_SIZE >> PAGE_OFFSET_BITS,
PAGE_PRESENT | PAGE_WRITEABLE);
/* Передаем структуре кучи указатель на
массив служебных данных кучи */
kheap.blocks = (memory_block_t*) (KERNEL_MEMORY_START +
KERNEL_SIZE);
/* Чистим этот массив */
memset(kheap.blocks, 0, KERNEL_HEAP_BLOCK_INFO_SIZE);
kheap.count = 0; /* Число выделенных */
/* блоков памяти */
kheap.start = KERNEL_HEAP_BASE; /* Начало кучи */
kheap.size = KERNEL_HEAP_SIZE; /* Размер кучи */
kheap.end = kheap.start + kheap.size; /* Конец кучи */
}
Код добавляем в конец функции инициализации менеджера памяти. Чтобы было ясно, как мы выполняем отображение памяти, приведу схему распределения физической памяти под кучу.
Виртуальную память под саму кучу отображаем принятому нами диапазону 0x7EFFFFFF - 0x7FFFFFFF на физические адреса 0x1600000 - 0x25FFFFF, а память под служебную информацию отображаем "адрес в адрес".
Инициализируем структуру кучи: передаем в нее указатель на массив данных о блоках, заполняем прочую информацию.
Куча готова, теперь можно написать функции для выделения и освобождения памяти. Для начала создадим универсальную функцию выделения памяти
Листинг 63. Общая функция выделения памяти в куче (memory.c)
/*---------------------------------------------------
// Проверка перекрытия двух блоков памяти
//-------------------------------------------------*/
static inline u8int is_blocks_overlapped(void* base1,
size_t size1,
void* base2,
size_t size2)
{
return (( base1 >= base2 ) && (base1 < base2 + size2)) ||
(( base2 >= base1 ) && (base2 < base1 + size1));
}
// Проверка перекрытия двух блоков памяти
//-------------------------------------------------*/
static inline u8int is_blocks_overlapped(void* base1,
size_t size1,
void* base2,
size_t size2)
{
return (( base1 >= base2 ) && (base1 < base2 + size2)) ||
(( base2 >= base1 ) && (base2 < base1 + size1));
}
/*---------------------------------------------------
* Выделение памяти
*-------------------------------------------------*/
void* kmalloc_common(size_t size, bool align)
{
void* vaddr = kheap.start; /* Полагаем что свободен адрес */
/* в начале кучи */
int i = 0;
/* Проверяем не перекрывает ли новый блок уже выделенные */
for (i = kheap.count - 1; i >= 0 ; i--)
{
if (is_blocks_overlapped(kheap.blocks[i].base,
kheap.blocks[i].size,
vaddr,
size))
{
/* В случае перекрытия располагаем новый блок
сразу за перекрываемым блоком */
vaddr = kheap.blocks[i].base + kheap.blocks[i].size;
}
}
/* Если необходимо выравнивание блока по границе страницы */
* Выделение памяти
*-------------------------------------------------*/
void* kmalloc_common(size_t size, bool align)
{
void* vaddr = kheap.start; /* Полагаем что свободен адрес */
/* в начале кучи */
int i = 0;
/* Проверяем не перекрывает ли новый блок уже выделенные */
for (i = kheap.count - 1; i >= 0 ; i--)
{
if (is_blocks_overlapped(kheap.blocks[i].base,
kheap.blocks[i].size,
vaddr,
size))
{
/* В случае перекрытия располагаем новый блок
сразу за перекрываемым блоком */
vaddr = kheap.blocks[i].base + kheap.blocks[i].size;
}
}
/* Если необходимо выравнивание блока по границе страницы */
if (align)
{
/* производим выравнивание */
u32int tmp_addr = (u32int) vaddr;
/* Если младшие 12 бит виртуального адреса не нулевые */
if (tmp_addr & 0xFFF)
{
/* Обнуляем их */
tmp_addr &= 0xFFFFF000;
/* Увеличиваем результат на размер страницы */
tmp_addr += PAGE_SIZE;
vaddr = (void*) tmp_addr;
}
}
/* Сдвигаем вверх по массиву информацию о
ранее выделенной памяти */
for (i = kheap.count - 1; i >= 0; i--)
{
kheap.blocks[i+1].base = kheap.blocks[i].base;
kheap.blocks[i+1].size = kheap.blocks[i].size;
}
/* Увеличиваем счетчик выделенных блоков */
kheap.count++;
/* Помещаем в начала массива данные о новом блоке */
kheap.blocks[0].base = vaddr;
kheap.blocks[0].size = size;
return vaddr;
}
{
/* производим выравнивание */
u32int tmp_addr = (u32int) vaddr;
/* Если младшие 12 бит виртуального адреса не нулевые */
if (tmp_addr & 0xFFF)
{
/* Обнуляем их */
tmp_addr &= 0xFFFFF000;
/* Увеличиваем результат на размер страницы */
tmp_addr += PAGE_SIZE;
vaddr = (void*) tmp_addr;
}
}
/* Сдвигаем вверх по массиву информацию о
ранее выделенной памяти */
for (i = kheap.count - 1; i >= 0; i--)
{
kheap.blocks[i+1].base = kheap.blocks[i].base;
kheap.blocks[i+1].size = kheap.blocks[i].size;
}
/* Увеличиваем счетчик выделенных блоков */
kheap.count++;
/* Помещаем в начала массива данные о новом блоке */
kheap.blocks[0].base = vaddr;
kheap.blocks[0].size = size;
return vaddr;
}
Нельзя назвать приведенный алгоритм супер-оптимальным, его единственное преимущество - достаточная для понимания простота. блоки памяти просто выделяются от начала кучи по порядку, так чтобы они не перекрывались. Для проверки перекрытия двух блоков используется функция is_blocks_overlapped(...), принцип действия которой можно проиллюстрировать схемой
Схема отражает два возможных случая перекрытия блоков памяти, функция же реализует проверку этих случаев. Новый блок ставится в начало кучи, а затем происходит проверка на перекрытие им уже имеющихся блоков, и при перекрытии какого-то блока выполняется сдвиг виртуального адреса нового сразу за перекрываемый блок. Это позволит занимать место в куче, выделенное ранее, а потом освобожденное.
Кроме того, часто, например при создании каталога страниц для процесса, выделять память с выравниванием по границе страниц - мы уже сталкивались с этим при инициализации страничного режима. Поэтому в функцию выделения памяти добавлена возможность произвести выравнивание, если оно запрошено.
На практике мы не будем непосредственно вызывать рассмотренную функцию, а создадим две функции-обертки
Листинг 64. Функции выделения памяти (memory.c)
/*------------------------------------------------
* Обычное выделение памяти
*----------------------------------------------*/
void* kmalloc(size_t size)
{
return kmalloc_common(size, false);
}
/*------------------------------------------------
* Выделение с выравниванием по границе страницы
*----------------------------------------------*/
void* kmalloc_a(size_t size)
{
return kmalloc_common(size, true);
}
* Обычное выделение памяти
*----------------------------------------------*/
void* kmalloc(size_t size)
{
return kmalloc_common(size, false);
}
/*------------------------------------------------
* Выделение с выравниванием по границе страницы
*----------------------------------------------*/
void* kmalloc_a(size_t size)
{
return kmalloc_common(size, true);
}
Созданы они для того чтобы не озадачиваться каждый раз заданием двух параметров. Что касается флага выравнивания, то при его введении возникла мысль создать полноценный логический тип данных и указатель NULL
Листинг 65. Тип bool и указатель NULL (common.h)
/* Логический тип bool */
typedef enum
{
false = 0,
true = 1
} bool;
typedef enum
{
false = 0,
true = 1
} bool;
#define NULL ((void*) 0)
Теперь необходимо реализовать освобождение памяти
Листинг 66. Функция освобождения памяти (memory.c)
/*-------------------------------------------------
* Освобождение памяти
*-----------------------------------------------*/
void kfree(void* vaddr)
{
int i = 0;
int block_idx = 0;
/* Выходим, если указатель некорректный */
if (vaddr == NULL)
{
return;
}
/* Ищем блок по его адресу в списке блоков */
for (i = 0; i < kheap.count; i++)
{
if (vaddr == kheap.blocks[i].base)
{
block_idx = i;
break;
}
}
* Освобождение памяти
*-----------------------------------------------*/
void kfree(void* vaddr)
{
int i = 0;
int block_idx = 0;
/* Выходим, если указатель некорректный */
if (vaddr == NULL)
{
return;
}
/* Ищем блок по его адресу в списке блоков */
for (i = 0; i < kheap.count; i++)
{
if (vaddr == kheap.blocks[i].base)
{
block_idx = i;
break;
}
}
/* Если мы перебрали все блоки и не нашли ничего - выходим */
if (i == kheap.count)
{
return;
}
/* Сдвигаем список блоков вниз, затирая данные найденного блока */
for (i = block_idx; i < kheap.count - 1; i++)
{
kheap.blocks[i].base = kheap.blocks[i+1].base;
kheap.blocks[i].size = kheap.blocks[i+1].size;
}
/* Уменьшаем число выделенных блоков памяти */
kheap.count--;
}
В общем то на этом все, можно пересобирать ядро и тестировать менеджер памяти. Добавим в main() такой код
Листинг 67. Тестирование кучи ядра (main.c)
u32int* ptr1 = (u32int*) kmalloc(8);
u8int* ptr2 = (u8int*) kmalloc(4);
u8int* ptr3 = (u8int*) kmalloc(10);
print_text("ptr1 = ");
print_hex_value((u64int) ptr1);
print_text("\n");
print_text("ptr2 = ");
print_hex_value((u64int) ptr2);
print_text("\n");
print_text("ptr3 = ");
print_hex_value((u64int) ptr3);
print_text("\n");
kfree(ptr2);
u32int* ptr4 = (u32int*) kmalloc(4);
print_text("ptr4 = ");
print_hex_value((u64int) ptr4);
print_text("\n\n");
*ptr1 = 0x78563412;
*ptr4 = 0xDA;
*ptr3 = 0x11;
print_dump(ptr1, 32);
u8int* ptr3 = (u8int*) kmalloc(10);
print_text("ptr1 = ");
print_hex_value((u64int) ptr1);
print_text("\n");
print_text("ptr2 = ");
print_hex_value((u64int) ptr2);
print_text("\n");
print_text("ptr3 = ");
print_hex_value((u64int) ptr3);
print_text("\n");
kfree(ptr2);
u32int* ptr4 = (u32int*) kmalloc(4);
print_text("ptr4 = ");
print_hex_value((u64int) ptr4);
print_text("\n\n");
*ptr1 = 0x78563412;
*ptr4 = 0xDA;
*ptr3 = 0x11;
print_dump(ptr1, 32);
Выделяем память под три объекта, выводим значения полученных указателей. Затем удаляем объект с указателем ptr2, и выделяем память такого же объема уже по указателю ptr4.
Видно, что последнее выделение памяти использует освобожденное ранее пространство. Далее инициализируем выделенную нами память и выведем дамп участка кучи. Ок, всё вроде работает )
Заключение
В первом приближении можно считать что у нас есть менеджер памяти для нашего ядра. Теперь мы способны решать более сложные задачи.
Комментариев нет:
Отправить комментарий