суббота, 17 августа 2013 г.

PhantomEx: Выделение и освобождение фреймов физической памяти

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

Для реализации данной задачи необходимо:
  1. Дать ядру представление о расположении и размерах блоков доступной физической памяти.
  2. Реализовать функции выделения и освобождения страниц физической памяти.
Существует несколько алгоритмов решения данных задач, в частности James Molloy предлагал алгоритм на основе заполнения битового поля. Мы реализуем  хранение информации о доступной физической памяти в виде двунаправленного кольцевого списка блоков свободной памяти.



1. Организация доступа к не отображенной физической памяти

 

В процессе реализации алгоритмов управления физической памятью нам будет необходимо писать информацию непосредственно в физическую память, причем не обязательно отображенную в каталоге таблиц страниц ядра. Так просто этого не сделать по следующим причинам:
  • физические адреса от нас сокрыты режимом страничной адресации, а нашем распоряжении только виртуальные адреса.
  • если мы попытаемся обратится к не отображенной области физической памяти нас ждет процессорное исключение  #PF.
Однако, для доступа к физической памяти мы можем воспользоваться уже отображенной страницей - ведь мы можем переотобразить её в любую интересующую нас область физической памяти, изменив старшие 20 бит её дескриптора.

В файле memory.h у нас уже мелькало макроопределение для этой страницы

/*-----------------------------------------------------
// Временная страница для доступа к физической памяти
//---------------------------------------------------*/
#define TEMP_PAGE         (KERNEL_BASE + KERNEL_SIZE - PAGE_SIZE)  

которая задает виртуальный адрес начала этой страницы. Видно, что она находится в уже отображенной нами области ВАП ядра. Реализуем некоторые функции для работы с этой страницей

Листинг 50. Переотображение временной страницы (memory.c)

/*--------------------------------------------------------------
// Отображение временной страницы по нужному физическому адресу
//------------------------------------------------------------*/

void temp_map_page(physaddr_t paddr)
{
    /* Выполняем трансляцию виртуального адреса страницы */    /* (можно не выполнять, заранее рассчитав индексы) */
    u32int table_idx = TEMP_PAGE >> 22;
    u32int page_idx = (TEMP_PAGE >> 12) & 0x3FF;
    u32int* pages = (u32int*) (KERNEL_PAGE_TABLE + PAGE_SIZE);
   /* Создаем страницу в новом месте физической памяти */
   *(pages + (table_idx << 10) + page_idx) = (u32int) paddr | 
                                               PAGE_PRESENT |
                                               PAGE_WRITEABLE;

   /* Удаляем страницу из TLB */
   asm volatile ("invlpg (,%0,)"::"a"(TEMP_PAGE));
}

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

Переотображение сводится к записи в дескриптор временной страницы нового физического адреса, а так же в аннулировании страницы - удалении её из кэша TLB. Это необходимо для обновления информации о данной странице в каталоге, так как если данная страница была в TLB, то изменение её физического адреса останется просто незамеченным для процессора.

Таким образом через данную временную страницу как через "окно" мы имеем доступ ко всей физической памяти.


2. Освобождение и выделение физической памяти


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

Но для начала нам необходима структура для работы с блоками свободной физической памяти

Листинг 51. Структура блока свободной физической памяти (memory.h)

/*------------------------------------------------------
//        Блок страниц физической памяти
//----------------------------------------------------*/
typedef    struct
{
    physaddr_t        prev;    /* Указатель на предыдущий блок */
    physaddr_t        next;    /* Указатель на следующий блок */
    size_t            size;    /* Размер блока (в страницах!) */

}__attribute__((packed)) physmemory_pages_block_t;

Новый тип size_t это переопределенный в common.h u32int для того чтобы мы могли сразу видеть, что речь идет о размере чего либо. Листинг этого переопределения приводить не буду в силу его элементарности.

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

Листинг 52. Получение указателя на описатель блока (memory.c)

/*---------------------------------------------------
//        Получить описатель свободного блока
//-------------------------------------------------*/

physmemory_pages_block_t* get_free_block(physaddr_t paddr)
{
    temp_map_page(paddr);

    return (physmemory_pages_block_t*) TEMP_PAGE;
}

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

Теперь реализуем алгоритм освобождения блока физической памяти

Листинг 53. Освобождение блока физической памяти (memory.h)

size_t      free_pages_count = 0; /* число свободных страниц */

/* Указатель на начало свободной памяти */
physaddr_t  free_phys_memory_pointer = -1;

u32int      kernel_stack = 0;
u32int      memory_size = 0;

/*--------------------------------------------------------
//        Освобождение физической памяти
//------------------------------------------------------*/
void free_phys_pages(physaddr_t base, size_t count)
{
    physmemory_pages_block_t* tmp_block;
   
    /* Если это инициализации или свободных блоков больше нет */
    if (free_phys_memory_pointer == -1)
    {
        /* Помечаем блок по заданному адресу как свободный */
        tmp_block = get_free_block(base);


        tmp_block->prev = base;
        tmp_block->next = base;
        tmp_block->size = count;

        free_phys_memory_pointer = base;
    }
    else /* Если у нас ещё есть свободные блоки  */
    {
        /* Берем первый из них как текущий */
        physaddr_t cur_block = free_phys_memory_pointer;

        do
        {
            tmp_block = get_free_block(cur_block);

            /* Если заданный адрес расположен после текущего блока */
            if (base == cur_block + 
                        (tmp_block->size << PAGE_OFFSET_BITS))
            {
                /* Увеличиваем размер текущего блока */
                tmp_block->size += count;


                /* если после освобождаемого блока есть другой 
                   свободный блок*/
                if (tmp_block->next == base + 
                                       (count << PAGE_OFFSET_BITS) )
                {
                    /* Запоминаем адрес следующего блока */
                    physaddr_t next_old = tmp_block->next;

                    /* Берем указатель на него */
                    tmp_block = get_free_block(next_old);

                    /* Получаем его размер и адрес блока который                                         идет после него */
                    physaddr_t next_new = tmp_block->next;
                    size_t new_count = tmp_block->size;

                    /* Вставляем новый свободный блок в список */
                    tmp_block = get_free_block(next_new);

                    tmp_block->prev = cur_block;

                    tmp_block = get_free_block(cur_block);

                    tmp_block->next = next_new;
                    tmp_block->size += new_count;
                }

                break;
            }

            /* Если освобождаемый блок перед остальными блоками */
            if (cur_block == base + (count << PAGE_OFFSET_BITS))
            {
                /* Запоминаем размер текущего блока */
                /* и его место в списке */
                size_t old_count = tmp_block->size;
                physaddr_t next = tmp_block->next;
                physaddr_t prev = tmp_block->prev;

                /* Берем блок следующий за текущим */
                tmp_block = get_free_block(next);

                /* Новый блок становится предыдущим для него */
                tmp_block->prev = base;

                /* Берем предыдущий блок */
                tmp_block = get_free_block(prev);

                /* Новый блок становится следующим для него */
                tmp_block->next = base;

                /* Берем новый блок и вставляем его в список */
                tmp_block = get_free_block(base);

                tmp_block->next = next;
                tmp_block->prev = prev;
                tmp_block->size += old_count;

                break;
            }

            /* Если освобождаемый блок между двумя
               свободными блоками */

            if ( cur_block > base  )
            {
                /* Просто вставляем его в список */
                physaddr_t prev = tmp_block->next;

                tmp_block->prev = base;

                tmp_block = get_free_block(prev);
                tmp_block->next = base;

                tmp_block = get_free_block(base);
                tmp_block->next = cur_block;
                tmp_block->prev = prev;
                tmp_block->size = count;

                break;
            }

            /* Или у нас имеется один свободный блок */
            if (tmp_block->next == free_phys_memory_pointer)
            {
                /* Вставляем новый свободный блок в список */
                tmp_block->prev = base;

                physaddr_t next = tmp_block->next;

                tmp_block->next = base;

                tmp_block = get_free_block(base);

                tmp_block->prev = cur_block;
                tmp_block->next = cur_block;
                tmp_block->size = count;

                break;
            }

            /* Делаем текущим следующий блок в списке */
            cur_block = tmp_block->next;


                      /* Ходим по циклу пока не поменяется адрес
               текущего свободного блока */

        } while ( cur_block != free_phys_memory_pointer );

        /* Модифицируем указатель на начало свободной памяти */
        if (base < free_phys_memory_pointer)

        {
            free_phys_memory_pointer = base;
        }
    }

        /* Увеличиваем число свободных страниц */
    free_pages_count += count;   
}

 
Надо сказать алгоритм достаточно запутанный на вид. Однако сводится всё написанное к простым действиям, вытекающим из трех возможных ситуаций:

  1. Освобождаемый блок памяти лежит после всех свободных блоков в списке - мы просто увеличиваем размер последнего блока в списке и модифицируем указатели на соседние блоки
  2. Освобождаемый блок лежит перед всеми свободными блоками в списке - увеличиваем размер первого блока с модификацией указателей на соседей
  3. Освобождаемый блок лежит между свободными блоками - просто встраиваем его в список.
Выделение памяти реализовано несколько проще

 Листинг 54. Выделение блока физической памяти (memory.c)

/*---------------------------------------------------------
//        Выделение блока страниц физической памяти
//-------------------------------------------------------*/

physaddr_t alloc_phys_pages(size_t count)
{
    physaddr_t result = -1;
    physmemory_pages_block_t* tmp_block;

    /* Число свободных страниц меньше чем запрашивается */
    /* Выходим из функции с кодом ошибки */

    if (free_pages_count < count)
        return -1;

    /* Если у нас есть свободная физическая память */
    if
(free_phys_memory_pointer != -1)
    {

        physaddr_t    cur_block = free_phys_memory_pointer;

        do
        {
            /* Берем текущий свободный блок */
            tmp_block = get_free_block(cur_block);

            /* Если размер блока равен запрашиваемому */
            if ( tmp_block->size == count )
            {
                /* Запоминаем где находятся соседние блоки */
                physaddr_t next = tmp_block->next;
                physaddr_t prev = tmp_block->prev;

                /* Берем следующий блок */
                tmp_block = get_free_block(next);

                /* Для следующего блока предыдущий - тот что
                   был предыдущим для выделяемого сейчас блока */

                tmp_block->prev = prev;

                /* Берем предыдущий блок */
                tmp_block = get_free_block(prev);

                /* Следующий для него - тот что был следующим для
                   выделяемого блока */

                tmp_block->next = next;

                /* Влруг этот блок последний? */
                if (cur_block == free_phys_memory_pointer)
                {
                    /* берем следующий за ним блок */
                    free_phys_memory_pointer = next;

                    /* если следующий блок - это текущий блок
                       то мы действительно выделили последний блок */

                    if (cur_block == free_phys_memory_pointer)
                    {
                        /* и свободной памяти у нас более нет */
                        free_phys_memory_pointer = -1;
                    }
                }

                /* Результат - адрес выделенного блока */
                result = cur_block;
                break;
            }

            /* Если блок больше чем запрашиваемое пространство */
            if ( tmp_block->size > count )
            {
                /* Уменьшаем размер свободного блока на
                   запрашиваемую величину */

                tmp_block->size -= count;

                /* Возвращаем адрес - адрес начала свободного блока
                   плюс оставшееся свободное место */

                result = cur_block + 
                         (tmp_block->size << PAGE_OFFSET_BITS);
                break;
            }

            /* Берем следующий свободный блок */
            cur_block = tmp_block->next;
          /* Прекращаем цикл при изменении адреса свободной памяти */
        } while (cur_block != free_phys_memory_pointer);

        /* Если возвращаемый адрес корректен */
        if (result != -1)
        {
            /* Уменьшаем число свободных страниц */
            free_pages_count -= count;
        }
    }
    /* Возвращаем адрес выделенной физической памяти */
    return result;
}

Здесь мы просто перебираем свободные блоки памяти. Если размер найденного блока в точности равен запрашиваемому - просто удаляем свободный блок из списка и возвращаем его адрес. Если свободный блок больше чем запрашиваемый размер памяти - уменьшаем размер блока на запрашиваемое число страниц.

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

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

Листинг 55. Инициализация менеджера памяти (memory.c)

/*-------------------------------------------------------
//        Инициализация менеджера памяти
//-----------------------------------------------------*/
void init_memory_manager(u32int stack)
{
    /* Запоминаем расположение стека ядра */
    kernel_stack = stack;
    /* Переключаемся в режим страничной адресации */
    switch_page_mode();

    /* Просматриваем карту памяти на предмет доступных блоков */
    memory_map_entry_t* entry;

    /* Перебираем все записи в цикле пока не наткнемся на пустую */
    for (entry = mentry; entry->type; entry++)
    {
        /* Если блок доступен для использования и он выше 1 Мб */
        if ( (entry->type == 1) && (entry->addr >= 0x100000) )
        {
            /* Помечаем его как свободный */
            free_phys_pages(entry->addr,
                            entry->len >> PAGE_OFFSET_BITS);

            /* Увеличиваем объем доступно памяти */
            memory_size += entry->len;
        }
    }

    /* Выводим на экран число доступных физических фреймов */
    print_text("Free pages: ");
    print_dec_value(free_pages_count);
    print_text(" pages\n");
}

В качестве параметра передадим функции инициализации указатель на сформированный загрузчиком стек ядра, с высокой долей вероятности имеющий значение 0x7FFFF. Знание о того где находится стек ядра пригодится нам позже, пока мы не задействуем это значение, а просто запомним его.

Далее включаем режим страничной адресации, а потом анализируем карту памяти, для определения доступных блоков ОЗУ и пометки всех их как свободных. В конце выводим количество доступной памяти в 4 Кб страницах.

Теперь мы можем выделять физическую память в виде блоков страниц с помощью функции alloc_phys_pages(...). Воспользуемся этой возможностью и реализуем


3. Отображение виртуальной памяти на физическую


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

Листинг 56. Функция отображения памяти (memory.c)

/*-------------------------------------------------------
// Отображение виртуальной памяти на физическую
//-----------------------------------------------------*/

u8int map_pages(physaddr_t page_dir, /* Адрес каталога страниц */
                void* vaddr,         /* Начальный виртуальный адрес */
                physaddr_t paddr,    /* Начальный физический адрес */
                size_t count,        /* Число отображаемых страниц */
                u32int flags)        /* Флаги страниц */
{
    /* Указатель для доступа к временной странице */
    physaddr_t* tmp_page = (physaddr_t*) TEMP_PAGE;

    physaddr_t table;

    u32int table_flags;

    /* Создаем необходимые страницы в цикле */
    for(; count; count--)
    {
        /* Транслируем виртуальный адрес */
        u32int table_idx = (u32int) vaddr >> 22;
        u32int page_idx = ((u32int) vaddr >> PAGE_OFFSET_BITS) &
                          PAGE_TABLE_INDEX_MASK;

        /* Получаем указатель на каталог таблиц страниц */
        temp_map_page(page_dir);

        /* Получаем указатель на таблицу */
        table = tmp_page[table_idx];

        /* Проверяем флаг присутствия таблицы */
        if ( !(table & PAGE_PRESENT) ) /* Если её нет */
        {
            /* Размещаем память под новую таблицу (одна страница) */
            physaddr_t addr = alloc_phys_pages(1);

            /* Получен корректный адрес? */
            if (addr != -1)
            {
                /* Получаем указатель на новую таблицу */
                temp_map_page(addr);

                /* Очищаем её */
                memset(tmp_page, 0, PAGE_SIZE);

                /* Получае указатель на каталог таблиц */
                temp_map_page(page_dir);

                /* Устанавливаем необходимые флаги для таблицы */
                table_flags = PAGE_PRESENT | 
                              PAGE_WRITEABLE |
                              PAGE_USER;

                /* Создаем дескриптор новой таблицы */
                tmp_page[table_idx] = (addr & ~PAGE_OFFSET_MASK) |
                                       table_flags;

                /* Запоминаем физический адрес таблицы */
                table = addr;
            }
            else
            {
                /* Если получен некорректный адрес
                   таблицы - выходим с кодом ошибки */

                return FALSE;
            }
        }

        /* Игнорируем флаги в дескрипторе таблицы, выделяем адрес
           (так же поступает и процессор) */

        table &= ~PAGE_OFFSET_MASK;

        /* Получаем указатель на таблицу */
        temp_map_page(table);

        /* Формируем дескриптор страницы */
        tmp_page[page_idx] = (paddr & ~PAGE_OFFSET_MASK) | flags;

        /* Обновляем буфер TLB */
        asm volatile ("invlpg (,%0,)"::"a"(vaddr));

        /* Переходим к новым адресам */
        vaddr += PAGE_SIZE;
        paddr += PAGE_SIZE;
    }

    /* Выходим с флагом успешности операции */
    return TRUE;
}

Вот теперь, используя данную функцию можно осуществить отображение любого участка виртуальной памяти, на любой участок физической. Протестируем эту функцию. Для этого пересоберем ядро, изменив предварительно функцию main(). Так как мы уже много изменений туда внесли, приведу листинг чтобы не было путаницы

Листинг 57. Главная функция ядра (main.c)

#include    "main.h"

/*-----------------------------------------------------
//    Точка входа в ядро
//---------------------------------------------------*/
int main(multiboot_header_t* mboot, u32int init_esp)
{
  u32int vir_addr = 0;
  u32int phys_addr = 0;
  int i = 0; 
 
  /* Выводим приветствие */
  print_text("Hello from myOSkernel!!!\n\n");
 
  /* Тест функций вывода на экран */
  print_text("hex value: ");
  print_hex_value(1000);
  print_text("\n");
 
  print_text("dec value: ");
  print_dec_value(589);
  print_text("\n\n");
  
  /* Тест видеопамяти */
  print_text("0 1 2 3 4 5 6 7 8 9 A B C D E F\n");
 
  for (i = 0; i < 16; i++)
  {
    set_bkground_color(i);
    print_text("  ");
  }
 
  print_text("\n");
 
  /* Инициализация сегментной памяти и прерываний */
  init_descriptor_tables();
 
  print_text("\n\n"); 
 
  set_bkground_color(BLACK);      
 
  /* Читаем и анализируем карту памяти */ 
  check_memory_map((memory_map_entry_t*) mboot->mmap_addr, 
                    mboot->mmap_length);
 
  print_text("\n");
 
  /* Инициализируем менеджер памяти */
  init_memory_manager(init_esp);
 
  /* Включаем таймер и разрешаем прерывания */
  init_timer(BASE_FREQ);
  asm volatile ("sti");
     
  return 0;
}

В итоге получаем такую картину


Память инициализирована, число доступных страниц - 16126, что соответствует 63 Мб памяти. Всё верно, мы не стали учитывать память ниже первого мегабайта. Она размечена для ядра, её мы не будем задействовать.

Проведем ещё один эксперимент - отобразим видеопамять в произвольную область виртуальной памяти, скажем по адресу 0x1500000. Для этого добавим в модуль управления текстовым видео буфером возможность установки произвольного адреса начала видеопамяти.

Листинг 58. Установка начального адреса видеопамяти 
(text_framebuffer.c)

/*--------------------------------------------------
 *
 * -----------------------------------------------*/

void set_video_vaddr(void* vaddr)
{
    video_memory = (u16int*) vaddr;
}

Думаю комментарии тут излишни.  Теперь добавим в main(), сразу после инициализации менеджера памяти такой код 

Листинг 59. Отображение видеопамяти по произвольному адресу (main.c)

init_memory_manager(init_esp);
/* Инициализируем указатель на видеопамять в ВАП ядра */
void
* new_video_mem = (void*) 0x15000000;

/* Отобразим видеопамять в ВАП начиная с нового адреса */
map_pages(KERNEL_PAGE_TABLE,
          new_video_mem,
          0xB8000,
          1,
          PAGE_PRESENT | PAGE_WRITEABLE);

/* Перенастраиваем видеобуфер на новое начало видеопамяти */
set_video_vaddr(new_video_mem);
 
/* Выводим тестовое сообщение */
print_text("\nVirtual video memory at ");
print_hex_value((u64int) new_video_mem);
print_text("\n\n");

Для видеопамяти в текстовом режиме достаточно одной страницы, ибо она занимает 4000 байт, а это немногим менее одной страницы. Собираем ядро и запускаем ОС


Сообщение об изменении адреса начала видеопамяти и время работы системы вывелось уже в видеопамять, отображенную в виртуальную память. Теперь ядро считает что начало видеопамяти расположено именно по адресу 0x15000000 и никак иначе. При этом реальное расположение видеопамяти сокрыто от него. В этом заключается мощь системы страничной адресации.

Заключение


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