Урок 6. Страничная адресация

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

6.1. Виртуальная память (теория)

Если Вы уже знаете что такое виртуальная память - Вы можете пропустить данный раздел.

В Linux, если Вы создаете простую программу:

int main(int argc, char* argv[])
{
    return 0;
}

скомпилируете ее и затем выполните:

objdump -f

вы можете обнаружить что-то похожее на это:

$ objdump -f a.out

a.out: file format elf32-i386
architecture: i386, flags 0x00000112
EXEC_P, HAS_SYMS, D_PAGED
start address 0x080482e0

Удивительно. Адрес начала программы 0x080482e0, что примерно равно 128 МБ в адресном пространстве. А ведь на компьютерах с размером оперативной памяти менее 128 МБ эта программа также прекрасно работает.

Программа оперирует вдресами виртуальной памяти. Части этой памяти отображаются на физическую память, а часть - нет. Если Вы попытаетесь получить доступ к неотображенным участкам виртуальной памяти, то ЦП инициирует прерывание Page Fault. Обычно ОС обрабатывает это прерывание и посылает процессу сигнал SIGSEGV, за которым как правило следует SIGKILL.

Эта абстракция очень удобна. Компиляторы могут создавать программы, которые располагаются по одному и тому же адресу в памяти. Обеспечивая механизм виртуальной памяти, ОС позволяет процессу думать, что он, например, находится по адресу 0x080482e0, но на самом деле он может находиться по адресу 0x1000000 в физической памяти. Кроме того, благодаря этому механизму процессы не могут случайно (или умышленно) испортить данные или код другого процесса.

Виртуальная память такого типа должна поддерживаться оборудованием. Ее невозможно эмулировать программно. К счастью, такая поддержка в архитектуре x86 предусмотрена. Она называется MMU (memory management unit, Блок управления памятью). MMU берет на себя все заботы по отображению виртуальной памяти на физическую, выступая посредником между ЦП и физической памятью.

6.2. Виртуальная память и страничная адресация

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

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

6.2.1. Страничные записи

Каждый процесс обладает своим собственным набором страничных отображений. Таким образом, пространства виртуальной памяти каждого процесса независимы. В архитектуре x86 размер страниц фиксирован. Каждая страница имеет дескриптор, который содержит информацию о кадре, на который она отображается (размер дескриптора - 32 бита). Так как страницы и кадры должны быть выровнены по границе страницы (4 кБ = 4 * 0х1000 Б), последние 12 бит дескриптора всегда равны нулю. В эти биты помещается служебная информация. Дескриптор выглядит так:

 31         12 11  9 8  7 6 5 4  3  2   1  0
|Frame address|AVAIL|RSVD|D|A|RSVD|U/S|R/W|P|

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

P
    установлен, если страница представлена в памяти

R/W
    Если установлен, то страница доступна для записи. Игнорируется, если код исполняется в режиме ядра.

U/S
    Если установлен, то это страница уровня пользователя. В противном случае - уровня ядра. В режиме пользователя нельзя читать или записывать в страницы уровня ядра.

Reserved
    Зарезервировано.

A
    Установлен, если к странице уже обращались.

D
    Установлен, если к странице обращались для записи.

AVAIL
    Эти три бита не используются и доступны для использования ядром ОС.

Page frame address
    Старшие 20 бит адреса кадра в физической памяти.

6.2.2. Каталоги и таблицы страниц

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

4 МБ может казаться не очень большой ценой, если у вас есть 4 ГБ физической памяти. А если у вас 16 МБ? Эта таблица займет четверть доступного пространства. Нам необходимо, чтобы размер таблицы был пропорционален размеру физической памяти.

Intel предлагает воспользоваться двухуровневой системой: в ЦП сообщается адрес каталога страниц размером 4 кБ, каждая запись в котором содержит адрес таблицы страниц размером 4 кБ. Каждая запись таблицы страниц указывает на конкретную страницу.

Таким образом, все адресное пространство (4 ГБ) может быть представлено при помощи этой схемы. Если таблица страниц не имеет записей, то она может быть освобождена и ее флаг P (present) сброшен в каталоге страниц.

6.2.3. Включаем страничную адресацию

Нужно сделать два простых действия:

1. Записать в регистр CR3 адрес каталога страниц. Это должен быть адрес в физической памяти.
2. Установить флаг PG в регистре CR0.

6.3. Page faults

Если процесс сделает что-то, что не понравится нашему MMU, будет сгенерировано прерывание номер 14 (Page fault). Это прерывание может быть сгенерировано в следующих случаях:

• Чтение или запись в область памяти, которая не была отображена;
• Процесс пользовательского уровня пытается записать в область памяти, предназначенную только для чтения;
• Процесс пользовательского уровня пытается получить доступ к области памяти уровня ядра;
• Запись в таблице страниц испорчена (значение зарезервированных битов было изменено).

Если мы обратимся к 4 уроку, то можем убедиться, что прерывание номер 14 проталкивает в стек код ошибки. Этот код может сообщить нам причины возникновения прерывания.

Бит 0
    Если установлен, то прерывание произошло НЕ по причине отсутствия страницы. Если сброшен - страница не существует.

Бит 1
    Если установлен, то процесс пытался записать в память, когда было сгенерировано исключение. Если сброшен - то пытался прочитать.

Бит 2
    Если установлен, то процессор находился в пользовательском режиме. Если сброшен - в режиме ядра.

Бит 3
    Если установлен, то причиной послужила некорректное значение зарезервированной секции.

Бит 4
    Если установлен, то прерыавние вызвано программно.

Процессор также сообщает нам адрес в памяти, обращение к которому вызвало прерывание. Он помещается в регистр CR2. Будьте осторожны, т.к. если ваш обработчик 14 прерывания повторно вызовет Page fault, значение в этом регистре будет перезаписано.

6.4. От теории к практике

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

6.4.1. Простой менеджер памяти

Если вы знакомы с языком С++, то наверняка слышали об операторе 'placement new'. Эта версия оператора не выделяет память для объекта, а только создает его в уже выделенной области памяти. Наш менеджер памяти будет очень похож на этот оператор.

Когда ядро полностью загружено, мы имеем кучу(heap) для ядра. Когда мы начинаем работать с кучей, мы как правило работаем уже с виртуальной, а не физической памятью. Но нам необходим некоторый механизм, который позволит выделять память до того, как мы создадим кучу.

Если мы выделяем память на ранней стадии загрузки ядра, мы можем сделать предположение о том, что нет необходимости в освобождении этой памяти. То есть нам не нужна будет функция kfree(). Это значительно упрощает нам жизнь. Нам достаточно иметь указатель (placement address) на свободную память, который мы возвращаем запрашивающей память функции, а затем просто увеличиваем значение указателя. Пример:

u32int kmalloc(u32int sz)
{
    u32int tmp = placement_address;
    placement_address += sz;
    return tmp;
}

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

u32int kmalloc(u32int sz,int align)
{
    if (align && (placement_address & 0xFFFFF000))
    {
        // Если еще не выравнено
        placement_address &= 0xFFFFF000;
        placement_address += 0x1000;
    }
    u32int tmp = placement_address;
    placement_address += sz;
    return tmp;
}

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

u32int kmalloc(u32int sz,int align,u32int *phys)
{
    if (align && (placement_address & 0xFFFFF000))
    {
        // Если еще не выравнено
        placement_address &= 0xFFFFF000;
        placement_address += 0x1000;
    }
    if(phys)
    {
        *phys = placement_address;
    }
    u32int tmp = placement_address;
    placement_address += sz;
    return tmp;
}

Отлично. Этих функция для нашего простейшего менеджера памяти вполне достаточно. Добавим эти функции в файл kheap.c, а в kheap.h пойдет их объявление:

extern u32int kmalloc_a(u32int sz,int align); // Page aligned
extern u32int kmalloc_p(u32int sz,u32int *phys); // returns physical address
extern u32int kmalloc_ap(u32int sz, int align, u32int *phys); // both
extern u32int kmalloc(u32int sz); // vanilla (normal)

6.4.2. Необходимые объявления

Файл paging.h должен включать в себя несколько специальных объявлений:

#ifndef PAGING_H
#define PAGING_H

#include "common.h"
#include "isr.h"

typedef struct page
{
   u32int present    : 1;   // Page present in memory
   u32int rw         : 1;   // Read-only if clear, readwrite if set
   u32int user       : 1;   // Supervisor level only if clear
   u32int accessed   : 1;   // Has the page been accessed since last refresh?
   u32int dirty      : 1;   // Has the page been written to since last refresh?
   u32int unused     : 7;   // Amalgamation of unused and reserved bits
   u32int frame      : 20;  // Frame address (shifted right 12 bits)
} page_t;

typedef struct page_table
{
   page_t pages[1024];
} page_table_t;

typedef struct page_directory
{
   /**
      Array of pointers to pagetables.
   **/
   page_table_t *tables[1024];
   /**
      Array of pointers to the pagetables above, but gives their *physical*
      location, for loading into the CR3 register.
   **/
   u32int tablesPhysical[1024];
   /**
      The physical address of tablesPhysical. This comes into play
      when we get our kernel heap allocated and the directory
      may be in a different location in virtual memory.
   **/
   u32int physicalAddr;
} page_directory_t;

/**
  Sets up the environment, page directories etc and
  enables paging.
**/
void initialise_paging();

/**
  Causes the specified page directory to be loaded into the
  CR3 register.
**/
void switch_page_directory(page_directory_t *new);

/**
  Retrieves a pointer to the page required.
  If make == 1, if the page-table in which this page should
  reside isn't created, create it!
**/
page_t *get_page(u32int address, int make, page_directory_t *dir);

/**
  Handler for page faults.
**/
void page_fault(registers_t regs);

Обратите внимание на tablesPhysical и physicalAddr. physicalAddr используется только в случае клонирования каталога страниц. Учтите, что с этого момента новый каталог будет иметь адрес в виртуальной памяти, который не равен адресу в физической памяти. А для загрузки в регистр нам нужен именно физический адрес каталога страниц. Для этого мы его и храним, на случай если решим сменить каталог. Аналогичная роль отведена и массиву tablesPhysical.

Перед нами стоит проблема: Как нам получить доступ к таблицам страниц? На первый взгляд все просто, но помните, что в каталоге страниц содержаться физические адреса таблиц, не виртуальные. А единственный возможный способ записи/чтения - это использование виртуальных адресов.

Первое решение, которое приходит на ум - это отобразить первую страницу таблицы на кадр, содержащий саму таблицу. Таким образом вы получите доступ к записям таблицы как к обычным целочисленным значениям. Но этот метод немного нелогичен и требует некоторого количества памяти (256 МБ). Поэтому мы пойдем другим путем.

Второй метод заключается в хранении двух массивов для каждого каталога страниц. В первом хранятся физические адреса таблиц (для ЦП), в другом - виртуальные адреса (для ОС). Это решение требует всего 4 кБ памяти для каждой страницы под служебные данные. Это не очень много.

6.4.3. Выделение кадра

Если мы захотим отобразить страницу на кадр, нам необходим способ поиска свободного кадра. Конечно, мы можем просто определить массив целочисленных значений в который будем помещать 0 или 1 в зависимости от занятости кадра. Но это несколько нелепо использовать 32 бита для значения, которое может поместиться в одном. Так что самым разумным решением будет использовать bitmap.

Нам понадобятся четыре функции:

// A bitset of freames - used or free
u32int *frames;
u32int nframes;

// Defined in kheap.c
extern u32int placement_address;

// Macros used in the bitset algorithms
#define INDEX_FROM_BIT(a) (a/(8*4))
#define OFFSET_FROM_BIT(a) (a%(8*4))

// Static function to set a bit int the frames bitset
static void set_frame(u32int frame_addr)
{
    u32int frame = frame_addr/0x1000;
    u32int idx = INDEX_FROM_BIT(frame);
    u32int off = OFFSET_FROM_BIT(frame);
    frames[idx] |= (0x1 << off);
}

static void clear_frame(u32int frame_addr)
{
    u32int frame = frame_addr/0x1000;
    u32int idx = INDEX_FROM_BIT(frame);
    u32int off = OFFSET_FROM_BIT(frame);
    frames[idx] &= ~(0x1 << off);
}

static u32int test_frame(u32int frame_addr)
{
    u32int frame = frame_addr/0x1000;
    u32int idx = INDEX_FROM_BIT(frame);
    u32int off = OFFSET_FROM_BIT(frame);
    return (frames[idx] & (0x1 << off));
}

static u32int first_frame()
{
    u32int i, j;
    for (i = 0; i < INDEX_FROM_BIT(nframes); ++i)
    {
        if (frames[i] != 0xFFFFFFFF) // nothing free, exit early
            for (j = 0; j < 32; ++j)
            {
                u32int toTest = 0x1 << j;
                if(!(frames[i]&toTest))
                    return i*4*8+j;
            }
    }
}

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

// Function to allocate frame
void alloc_frame(page_t *page, int is_kernel, int is_writeable)
{
    if (page->frame != 0)
        return; // Кадр уже выделен для данной страницы
    else
    {
        u32int idx = first_frame(); // index of the first frame
        if(idx == (u32int)-1)
            PANIC("No free frames!");

        set_frame(idx*0x1000); // застолбили кадр
        page->present = 1;
        page->rw = (is_writeable)?1:0;
        page->user = (is_kernel)?0:1;
        page->frame = idx;
    }
}

void free_frame(page_t *page)
{
    u32int frame;
    if(!(frame = page->frame))
        return; // Кадр для данной страницы не выделен
    else
    {
        clear_frame(frame);
        page->frame = 0x0;
    }
}

Макрос PANIC просто вызывает глобальную функцию panic(), которая принимает в качестве аргументов сообщение, __FILE__ и __LINE__ где произошел вызов. Функция panic() выводит все это на экран и уходит в бесконечный цикл, останавливая выполнения кода ядра.

Определим пока что для него заглушку:

#define PANIC(a) while(1);

6.4.4. Последнее, но не в последнюю очередь

void initialise_paging()
{
    // Пусть размер нашей памяти - 16 МБ
    // пока что
    u32int mem_end_page = 0x1000000;

    nframes = mem_end_page / 0x1000;
    frames = (u32int*)kmalloc(INDEX_FROM_BIT(nframes));
    memset(frames, 0, INDEX_FROM_BIT(nframes));

    // Создаем каталог страниц
    kernel_directory = (page_directory_t*)kmalloc_a(sizeof(page_directory_t));
    memset(kernel_directory, 0, sizeof(page_directory_t));
    current_directory = kernel_directory;

    /**
     * Теперь нам необходимо тождественно отобразить
     * адреса виртуальной памяти на адреса физической памяти,
     * чтобы мы могли прозрачно обращаться к физической памяти,
     * как будто страничная адресация не включена.
     * Обратите внимание что мы специально используем здесь
     * цикл while, т.к. внутри тела цикла значение переменной
     * placement_address изменяется при вызове kmalloc().
     */
    int i = 0;
    while (i < placement_address)
    {
        // Код ядра доступен для чтения но не для записи
        // из пространства пользователя
        alloc_frame( get_page(i, 1, kernel_directory),0,0);
        i += 0x1000;
    }
    // Прежде чем мы включим страничную адресацию, мы должны
    // зарегистрировать обработчик page fault
    register_interrupt_handler(14, page_fault);

    // Теперь ВКЛ.
    switch_page_directory(kernel_directory);
}

void switch_page_directory(page_directory_t *dir)
{
    current_directory = dir;
    __asm__ volatile ("mov %0, %%cr3"::"r"(&dir->tablesPhysical));
    u32int cr0;
    __asm__ volatile ("mov %%cr0, %0": "=r"(cr0));
    cr0 |= 0x80000000; // ВКЛ
    __asm__ volatile ("mov %0, %%cr0":: "r"(cr0));
}

page_t *get_page(u32int address, int make, page_directory_t *dir)
{
    // Делаем из адреса индекс
    address /= 0x1000;
    // Находим таблицу, содержащую адрес
    u32int table_idx = address / 1024;
    if (dir->tables[table_idx]) // Если таблица уже создана
        return &dir->tables[table_idx]->pages[address%1024];
    else if(make)
    {
        u32int tmp;
        dir->tables[table_idx] = (page_table_t*)kmalloc_ap(sizeof(page_table_t), &tmp);
        memset(dir->tables[table_idx], 0, 0x1000);
        dir->tablesPhysical[table_idx] = tmp | 0x7; // PRESENT, RW, US
        return &dir->tables[table_idx]->pages[address%1024];
    }
    else
        return 0;
}

Проанализируем код.

switch_page_directory() делает именно то, что было заявлено. Она принимает указатель на каталог страниц, записывает его физический адрес в регистр CR3 и включает страничную адресацию.

get_page() возвращает указатель на запись в таблице страниц для заданного адреса. Если задан аргумент make, и таблица страниц, в которой должна располагаться запись, не существует - то такая таблица создается. Если же таблица существует, то функция просто возвращает запись из этой таблицы.

Функция get_page() использует kmalloc_ap() для выделения блока памяти, выравненного по границе страницы. Физический адрес таблицы помещается в tablesPhysical (после добавления нескольких служебных бит, сообщающих ЦП, что данный блок памяти существует, доступен для записи, и доступен для доступа из пользовательского режима); виртуальный адрес записывается в массив tables.

initialise_paging() создает bitmap и устанавливает значение всех битов в нем в 0. Затем она выделяет память для каталога страниц. После этого, она выделяет кадры таким образом, чтобы адрес в виртуальной памяти отображался на тот же адрес в физической памяти. Это делается для маленькой секции адресного пространства, так что код ядра может продолжать выполняться в штатном режиме. Затем функция регистрирует обработчик 14 прерывания и включает страничную адресацию.

6.4.5. Обработчик page fault

void page_fault(registers_t regs)
{
    // Произошло прерывание page fault
    // Адрес по которому произошло прерывание содержится в регистре CR2
    u32int faulting_address;
    __asm__ volatile ("mov %%cr2, %0" : "=r"(faulting_address));

    // Код ошибки сообщит нам подробности произошедшего
    int present = !(regs.err_code & 0x1);    // Page not present
    int rw = regs.err_code & 0x2;            // Write operation ?
    int us = regs.err_code & 0x4;            // Processor was in user-mode?
    int reserved = regs.err_code & 0x8;        // Overwritten CPU reserved bits
    int id = regs.err_code & 0x10;            // Caused by an instruction

    // Error message
    monitor_write("Page fault! (");
    if (present) monitor_write("present ");
    if (rw) monitor_write("read-only ");
    if (us) monitor_write("user-mode ");
    if (reserved) monitor_write("reserved ");
    monitor_write(") at 0x");
    monitor_write_hex(faulting_address);
    monitor_write("\n");
    PANIC("Page fault");
}

Этот обработчик выводит замечательное сообщение об ошибке на экран. Он берет адрес который вызвал ошибку из регистра CR2 и анализирует код ошибки, возвращаемый ЦП.

6.4.6. Тестируем
Добавим строки в файл main.c:

void kmain(int magic, struct multiboot *mboot_ptr)
{
    monitor_clear();
    // All our initialisation calls will go in here
    // Setting up GDT and IDT
    init_descriptor_tables();
    __asm__ volatile ("sti");

    initialise_paging();
    monitor_write("Hello, paging world!\n");

    u32int *ptr = (u32int*)0xA0000000;
    u32int do_page_fault = *ptr;
}

А теперь соберем и запустим нашу ОС. На экране должно отобразиться следующее:

Ура. Теперь наше ядро поддерживает страничную адресацию. А также может обрабатывать ошибки доступа к памяти. Это очень хорошо.

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

Код уже на github.
А также доступен по ссылке:http://dl.dropbox.com/u/40211944/Lesson%206.tar.gz