Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org
Memory Management 1
by Tim Robinson

Introduction

Управление физической памятью - низкоуровневый компонент любой ОС. В ядре может быть несколько менеджеров памяти , и каждый может работать на своем уровне .
Предполагается , что ядро работает с админскими правами и в защищенном режиме . Для x86 это означает , что это уровень 0 (PL0) .

Specifications
Когда управление передается из загрузчика в ядро , вы получаете полный контроль над системой. Код , данные и стек разнесены при этом на разные сектора . Вы напечатали на экране “Hello world” - и что же дальше ?
Задача менеджера памяти проста - разложить всю доступную память по полочкам . Память мы разбиваем на страницы - “pages”, одна страница - 4KB .
Процессор x86 уникален в том смысле , что он оперирует с сегментами и страницами : сначала идет ссылка на сегмент , а потом на страницу внутри него .
* Большинство других архитектур разбивает адресное пространство на страницы . А в x86-архитектуре существует принцип сегментации по признаку кода,данных и стека . И нет никакой возможности перенести это на другие архитектуры , не поддерживающие сегментацию.

* Не используя paging, на x86 можно получить доступ лишь к 16MB физической памяти. В 16-битном пространстве имеется 24-битная шина, дающая доступ лишь к 16MB. Не имея сегментации , мы ограничены 64KB. С приходом 386 появилась возможность разбить память на 4KB pages. У этого метода есть свои недостатки - например , невозможность выделить память менее 4 КБ.


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

Organization

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

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

Если мы имеем 256MB памяти , нам нужно 8192 байт для управления 65,536 страницами . При выделении памяти под процесс , нам нужно знать ее размер , идентификатор процесса и пользователя .

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

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


Initialization
Для того чтобы определить количество доступной физической памяти , при загрузке надо вызвать прерывание BIOS 15h .

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

Мы знаем стартовый и конечный адрес ядра - его можно взять из GNU ld script. Кусок памяти мы назовем bitmap и положим сразу после ядра .


Allocation
Первой функцией менеджера памяти будет выделение физической страницы . Страница будет промаркирована как выделенная и будет возвращен ее адрес .
Если свободные страницы заканчиваются , нужно свопировать на диск .

Mapping
This is where the paging architecture starts to get useful. In short (and the processor manual explains this better), paging allows you to control the address space from software. You can map pages anywhere you like; you can apply protection to pages; and you can allocate and map pages on demand via page faults (or even emulate memory access completely).

I’ll leave the MMU description to the hardware manuals, and for this, I’ll stick to the x86 (although other architectures are fairly similar). The 386 and above use a three-level translation scheme: the PDBR (Page Directory Base Register, called CR3) contains the physical address of a page directory. The page directory is a page in memory split into 1,024 32-bit words, or Page Directory Entries, each of which is the physical address of a page table. Each page table is, too, split into 1,024 Page Table Entries; each of these words is the physical address of a page in memory.

Note that, to span 4GB of 4096-byte pages, you don’t need 32 bits for each physical address. The PDBR, PDEs and PTEs only need 20 bits each, so the bottom 12 bits are used as flags. These flags can apply protection (read/write and user vs. supervisor) to pages and page tables, and they can mark individual pages and page tables as present or not present. There is also an ‘accessed’ flag, which the processor sets when a page or page table is accessed. By switching the PDBR you can use different page directories and page tables in different contexts, thereby causing separate applications to use different address spaces.

Paging is immensely powerful, and its true benefits aren’t fully realized until you start writing user applications to make use of the address space. Now we need to write functions in our memory manager to maintain the various page directories and page tables.

Remember that page directories and page tables are just normal pages in memory; the processor needs to know their physical addresses. There’s only one page directory per process (or per address space) and there can be up to 1,024 page tables per page directory. We can allocate these as normal from our physical allocator we wrote before. Remember that page directory and page table addresses need to be page-aligned: that is, the bottom 12 bits need to be zero (otherwise they would interfere with the read/write/protection/accessed bits).

Before we enable paging we need valid a PDBR and page directory, and a valid page table for wherever we’re executing. The current page table needs to identity map the current EIP: when we set the paging bit in CR0, the CPU will still be executing from the same address, so it had better have some valid instructions at wherever it’s executing. This is why it’s good to locate the kernel at whatever address it’s going to end up once paging is enabled.

So before we enable paging, we need to allocate a page directory and one page table. You could use the page allocator or you could reserve giant (4096-byte) global variables: either way it’s the same. If you’re using global variables for your page directory/page table, be sure that they’re page-aligned.

Zero all the entries you’re not using. This will clear the present bit so that accessing the addresses they cover will cause a page fault. You could set the other bits to some distinctive pattern if you want your page faults to look good. Remember that each PDE (and page table) covers 4MB of your address space, which should be enough for your kernel – if not, I’d like to see it. Each PTE covers only 4KB, so you’ll probably need several PTEs to cover your kernel (again, if not, I’d like to see it…). Assuming you’re not relocating your kernel dynamically (and why? Since it’s the first user of the address space, it’s not likely to clash), you can just poke numbers into the page directory and page table you’ve allocated as appropriate. You’ll be making your memory-mapping function more sophisticated later.

All of this needs to go into your memory manager initialization routine, which I covered before. Since your memory manager should separate all the machine-specific memory stuff from the rest of the kernel, it’s polite to enable paging before your return, and it’s polite to keep the address format the same (if not, then the return address on the stack from the last function call will be wrong). So set up your page directory and page tables, enable paging, do a far jump (to reload CS) and reload the other selectors (SS, DS, ES, FS and GS) as appropriate. Now that you’ve enabled paging it makes sense to use segments whose base addresses are zero, although there’s no reason why this should be mandatory.

With luck, we’re now running with paging enabled. All addresses now are going through the page directory and page tables we established before. Note that the rest of physical memory is not necessarily mapped into our new address space – all that is necessary is the part of code that the CPU is currently executing (in practice, you’d map the whole kernel: data, stack and all). We’d like to map in video memory so we can print some more messages, and the full memory-mapping routine comes in useful.


Memory mapping
At first glance this appears pretty easy. Just poke words into the right pages in the current page directory and page table; allocate a new page table if required. However, the CPU uses physical addresses for page directories and page tables; we’re using virtual addresses for everything. There’s a number of ways around this:
1) Map all physical memory into the address space. This can either be done 1:1 (that is, physical memory is addressed by the bottom of the address space) or at some offset (that is, physical memory is accessible starting at, say, 0xD0000000). This approach’s advantage is its simplicity (Win9x uses this); however, its disadvantage is the fact that the user may have any amount of memory installed in their system, all of which must be addressable. Imagine if the user had 4GB installed: there would be no address space left…
2) Map each page into the address space and keep track of their virtual addresses in a virtual page directory parallel to the real one. The virtual page directory can store the virtual addresses of each of the page tables while the real page directory stores their physical addresses. This is good if the only pieces of physical memory which must be addressed directly are the page directories/page tables; however, it increases the amount of space taken up just by mapping – not good in a small system.
3) Map the page directory into itself. This might seem like a kind of weird fractal memory mapper, but it works well in practice. By setting one of the fixed PDEs to the physical address of the associated page directory, you can address PDEs and PTEs as separate addresses. If you set element 1023 of each page directory to the physical address of the page directory itself, the processor will see the page directory as the last page table. It will see the PDEs as PTEs, and it will see the PTEs as individual 32-bit words in the top 4MB of the address space. You can use the top 4KB of the address space as the entries in the original page directory. This has the advantage of being beautiful yet simple; it has the disadvantage that you can only access page mappings inside the current address space.
By way of an example, Windows NT maps up to 512MB of physical memory into the kernel’s address space (as in option 1) while mapping the page tables directly into the address space (as in option 3). Personally, I’d go for the third option, even though it takes some thinking about to get your head round it. The first option also has its advantages for a simple kernel. Either way, the page mapper’s job is simple. Remember to apply the correct protection at each stage: on the PTE, apply the desired protection for that page; on the PDE, apply the desired protection for that 4MB region. Each PDE should normally be made read/write and user-visible unless you have a good reason for making the whole 4MB region inaccessible from user mode.


Overview
That’s about it for our simple physical memory manager. If you want HAL-style machine abstraction you’ll probably need an address space switching function callable from the scheduler (on the x86, this is just MOV CR3, addr). If you’re going for a full VMS- or NT-style asynchronous device architecture you’ll need a routine which can lock a buffer in the virtual address space and record the physical pages associated with it; however, that comes under ‘advanced’ design and you probably won’t need it for a simple Minix or Linux model.

Before we can use our address fully, we’ll need a more sophisticated memory manager, so here’s a look forward to part 2 of the memory management tutorial.


Memory Management 2
by Tim Robinson

Introduction
You might have already read my “Memory Management 1” tutorial; if not, then you should go and read it now, because this tutorial relies on it. Here I’ll be describing the next level of memory management: turning the memory manager I wrote about in the first tutorial into something useful and general-purpose.

Remember that the low-level memory manager deals with the computer’s physical memory: that is, the raw address space of your PC before things like paging come into effect. The low-level manager has three main components: an allocator (for allocating one physical page at a time), a deallocator (for deallocating those pages) and a memory mapper (for modifying mappings between the virtual address space and physical memory). Now it’s time to make something useful out of these.

There are a few problems with the physical memory functions which make them unsuitable for everyday memory allocation like, say, malloc():
*They only allocate whole pages at a time. This is fine if you only ever want to allocate memory in multiples of 4KB (on the x86), but not much use if you’re using things like linked lists (which you will be).

*They deal with physical addresses, not virtual. This means that they don’t naturally take advantage of a paged architecture, which would allow your kernel to arrange applications’ address spaces independently of the layout of the computers RAM chips.

*They don’t do much with the memory they allocate: they don't allow things like sharing, swapping to disk, memory-mapped files, integration with the disk cache, etc.


What we need to do is write a layer of functions on top of the physical memory manager which deal with these problems. Note that this memory manager, like most of the kernel, can be made portable: the things it deals with are generally the same across different architectures (that is, until you start dealing with things like the Z80 and the 80286).


Specifications
What we’re going to do is, effectively, write two memory managers: one which can manage the virtual address space for user applications, and one which implements malloc() and free() (or the equivalents in your language of choice) for your kernel. A virtual memory manager is useful for providing a large-block memory interface to your user applications: sure, it would be OK to expose the physical memory manager directly to user mode, but that would mean that user apps needed to know about the physical architecture of the target machine, and surely we’re writing a kernel to avoid that kind of thing?

It’s good to write versions of malloc() and free() for the kernel because it makes writing kernel (and driver) code easier and more enjoyable. I’m a great believer in providing a good run-time library interface in kernel mode, even if it means that the kernel grows in size. Different kernels provide these RTL facilities to different extents; the Linux kernel provides a small subset of the C RTL, and Windows NT provides its own set of functions which mirror those provided by the C standard. Linux calls its malloc() kmalloc(); Windows NT has ExAllocatePool() and friends; I’ll be sticking with the familiar malloc().


malloc() and free()
I’ll start with these two because they are probably the simplest to implement. The goal of any malloc() is to take a large slab of memory and divide it up into pieces as requested, and that is what we’ll be doing in the kernel. Here, we need to set aside a portion of the kernel’s address space (remember, the kernel’s address space ought to be separate from the user address space, in the interests of memory protection) from where malloc()’s memory will come.

I like to split my kernel’s address space into several regions. The MпїЅius kernel, for example, starts at address 0xC0000000; that is, it occupies the top gigabyte. Kernel memory is split up into 256MB-regions as follows:

0xC0000000
Kernel code, data, bss, etc.
Probably too much but, hey, we might see a 256MB kernel one day.
0xD0000000
Kernel heap
0xE0000000
Space reserved for device drivers
0xF0000000
Some physical memory (useful for video memory access)
Page directory and page tables of the current process

Note that 256MB of address space, from 0xD0000000 to 0xE0000000 is devoted to the kernel’s heap. This doesn’t mean that 256MB of physical memory will be given over to the kernel heap at all times; it just means that there is a 256MB window through which heap memory is accessed.

I’m not going to go into telling you how to write the malloc() and free() functions themselves; other people can do that better than me. There is a sample implementation in the book The C Programming Language by Kernighan and Ritchie, and there are several slot-in implementations on the Internet. However, one thing all malloc() implementations should have in common is a hook into the OS kernel to request more memory. In the more conventional user-mode environment, this function (often called morecore() or sbrk()) will ask the kernel for a large block of memory in order to enlarge the process’s address space. Here, we are the kernel, so we need to write our own morecore().

Incidentally, there is a slight difference between morecore() (as featured in K&R) and sbrk() (as used by most Unix implementations):

void *morecore(size_t n)
Requests a block of size n bytes (K&R uses multiples of the allocation header size) which might come from anywhere in the application’s address space
char *sbrk(size_t d)
Adjusts the size of the application’s address space by d bytes and returns a pointer to the start of the new region. Returns char* because the earliest versions of C compilers had no void* type.

The difference is subtle but it makes sense to be clear about these definitions. I’ll be using the morecore() interface here, but it should be trivial to adapt it for sbrk(); in fact, there’s no reason why morecore() can’t work the same way as sbrk() internally.

Remember: malloc() calls morecore() when it runs out of memory. If it succeeds, the new block is added to the free block list (if it fails, malloc() returns NULL). In the kernel we need to increase the amount of space set aside for the kernel’s heap by n bytes and return a pointer to the start of the block. But morecore() wants to return an address inside the virtual address space, and so far we only know how to allocate physical pages. Well, the obvious thing to do would be to:

1) Allocate a page using the physical memory allocator
2) Map it at the end of the kernel’s heap using the physical memory mapper
3) Adjust the kernel’s end-of-heap pointer
4) Repeat from (1) until enough memory has been allocated to satisfy the request

Note that there is no provision made to free the physical memory associated with the heap. I don’t know of any malloc() implementation which will ask the OS to free the memory is has been given (the RTL usually assumes that the program’s memory will be freed when it exits) but it should be possible to walk the free block heap periodically and release any memory used. As is is, this algorithm will only allocate memory as it is used: if a lot of memory is suddenly allocated and then freed, it will remain allocated (as far as the kernel is concerned) but it will be re-used next time malloc() is called.

That’s all there is to the kernel side of malloc(). Remember that this malloc() is only for use by the kernel and by kernel-mode device drivers. User applications can have their own funky implementation of malloc(), or new, or GetMem() as required. These user-mode allocators can call the kernel’s virtual memory manager, which I’ll conveniently cover next.


The Virtual Memory Manager
The kernel’s malloc() is all well and good; we can go off and write strdup() and new and make linked list functions now. But it’s not very sophisticated. We can make a much more powerful allocator which can do more than allocate and free arbitrary small blocks of memory: it can do all the things I talked about in the Introduction. This is where we write the virtual memory manager.

As with the physical memory manager from part 1, the virtual memory manager will be managing the address space. However, this address space is the virtual one: it is a constant 4GB long (on a 32-bit machine) and it needn’t correspond directly with the underlying memory installed the machine. Parts of it can be mapped to the same physical memory (to share memory); parts of it can be mapped nowhere at all (to provide guard pages, for example, at the end of stacks); parts of it can be unmapped but can emulate real memory (like in Windows NT’s ntvdm.exe, which emulates the PC’s BIOS Data Area for real-mode apps).

The key to all of this is the page fault. If you’ve done much Windows programming you’ll probably be familiar with the page fault (along with the access violation) as one of the symptoms of a spurious pointer; Linux programmers (and users) will know it as a segmentation violation or bus fault. However, as applications programmers, we only see the page fault when things go wrong. In reality, the page fault is the processor’s way of telling the kernel that it doesn’t know how to handle an access to a particular region of memory, and that some software handler needs to be invoked to sort it out. Under the correct circumstances, the kernel will be able to do so and continue the execution of the application.

The most benign kind of page fault occurs when the processor tries to read from or write to a page which has been marked as ‘not present’. Remember that each entry in the page directory and each entry in each page table has a ‘Present’ bit. The processor checks this bit on every memory access (actually it will cache the PDEs and PTEs to speed up memory access). If it is set then the access can continue; if not, it writes the address in question to the register CR2 and invokes the page fault handler. This is installed the same way as a normal interrupt handler; see the interrupts tutorial for more details. I’ll assume that you have got your interrupt handler sufficiently advanced that control will be passed to a routine when an interrupt occurs.

So the page fault handler is executed when a page is accessed which is, as far as the MMU is concerned, not present. The page fault handler needs to:
1) Check what should be located at the faulting address and,
2) Make sure the address is accessible if it should be, or,
3) Take the appropriate action if the address is incorrect

The "appropriate action" in this case will probably involve terminating the application in question. Different operating systems take different approaches over this; Windows NT invokes the current set of Structured Exception Handlers, the default action of which is to terminate the application; Linux invokes the appropriate signal handler.


Allocator
In order to check what should be located at the faulting address we need to keep records of how the address space is organized. To start with, we can write a simple virtual memory allocator. Forget about page faults for a moment while I describe what our virtual memory allocator will do.

In short, we need to be able to make good use of the 4GB given to us by the hardware designers. This comes down to writing a routine which can allocate an arbitrary amount of virtual memory. Note that the physical memory behind it doesn’t need to be allocated all at once, and it doesn’t need to be contiguous. Of course the physical memory does eventually need to be there – the processor needs something to send over the address bus to the main memory – but it’s not essential to allocate it all at once. For now it’s enough to record all allocations that take place in a list. Our malloc() can come in useful here because you can allocate one record per allocation and store things like the virtual address of the allocation and how many pages were allocated. In fact, we need to record at least the allocation base address and the size so that we can allocate (“commit”) physical memory later. It’s usually more worthwhile dealing in pages here, rather than bytes, because it makes the kernel’s accounting easier. Remember that the user-mode RTL can implement a malloc()-style allocator itself which can divide large blocks of memory into smaller ones. As a reasonable minimum you ought to record for each allocation:
*Virtual base address (i.e. the start of the block in the current application’s address space)

*Size

*Protection (e.g. read/write, user vs. kernel)


At this point we have a function which can ‘mentally’ allocate blocks of memory and record them somewhere in a list. If you’re implementing process-based protection in your kernel you ought to keep one list per process, to avoid confusion.

Once some application has a block allocated it can try to access it. However, there’s no physical memory associated with the block yet – the page table entries (and, in fact, the page directory entry) for that region are marked as ‘not present’. So the processor invokes a page fault, and calls our page fault handler.

The first thing the handler needs to do is check the allocation list to find the faulting address. The x86 processor records the actual address accessed, not the address of the start of the page, but this shouldn’t make any difference here. We need to walk the list to find a block which spans the faulting address.

Once the block is found, we need to commit it. This will involve allocating the relevant physical pages and mapping them into the address space, using the physical memory allocator from part 1. It’s up to you whether you commit an entire block at once or commit it page-by-page. Imagine an allocation of 4MB: that’s 1,024 pages. On the one hand, the application might write one byte at the start and then forget about it. If we committed the whole block on the first access, we’d waste 3.99MB (that is, until the application freed the block). Alternatively we could commit one page at once, and invoke the page fault handler when each page was accessed. If the application allocated the 4MB block and wrote to every byte we’d end up faulting 1,024 times: each fault has its overhead which would be unnecessary if the whole block was committed on the first fault. As with so many design decisions, it’s up to you.

I mentioned the processor’s page table cache before. This is called the Translation Lookaside Buffer and it is an internal copy of the PDEs and PTEs as they were when the cache was last invalidated. The cache is invalidated when CR3 is written to and when the INVLPG instruction is executed (on the 486 and above). Invalidating the whole TLB takes a while so it should only be done when necessary (e.g. when switching between two processes). The INVLPG instruction is useful because it instructs the processor to invalidate only the region of the TLB associated with one page. The TLB must be updated when any changes are made to the page directory or page tables (the processor doesn’t do it automatically) so it is necessary after allocating and mapping the physical memory here.

Assuming that the faulting address was correctly identified as part of an allocated block, and the relevant physical memory was allocated and mapped successfully, the kernel is free to return from the page fault handler and continue execution of the current application. The processor will retry the faulting instruction and, if the kernel has done its job, all will be well.


Executables
If we load an executable program into memory, we’ll have a record of the makeup of that executable – that is, what sections it contains, where they are located, and how big they are. They will be laid out in the application’s address space in some order, and they needn’t all be loaded at startup. This is similar to the virtual memory allocator I just described, except that we already have a record of the executable’s sections in the header. Why not map the file into memory as it appears on disk, headers and all. Then it becomes unnecessary to allocate the executable’s memory with the virtual allocator.

To do this we need to walk the list of executable image sections at the same time as we check the list of allocated blocks. This is a matter of starting at the base address of the executable (that is, the address of the start of the headers), parsing the headers and locating the section which spans the faulting address. It may be more efficient to cache the sections’ details in some other format, but most executable formats (including COFF, ELF and PE) keep it reasonable. Then we can write a “separate executable section committer” which will load an executable section from disk, allocate physical storage and map it. We can make some more optimizations here – for example, if code pages are read-only, it will be unnecessary to swap them to disk if they are already present in the on-disk image. Read-only code pages can also be shared among multiple instances, and data pages can be shared until they are written to; once they are written to, a copy is made. The principle of copying pages only when they are written to ("dirtied") is known as Copy-On-Write, and is commonly used.

The principle behind COW is that the originals of such pages are made read-only. The processor will fault when the application attempts to write to it – because they are data pages there’s no reason why the application should avoid writing to them – and the error code on the stack will reflect this. The page fault handler detects that the faulting address is contained within a COW page, so it can make a copy of the underlying physical memory, re-map it in the address space, and allow the application to continue. Because the mapping has changed, the application will continue with the copy, which the page fault handler has now made read-write.

Copy-on-write is also used in the common Unix fork() paradigm. The fork() system call, which has no parallel in standard Win32, creates a copy of the current process which is identical – it uses the same code pages, data pages and stack pages are shared, and execution continues at the same location. To save memory, as many pages are shared as possible. However, the new process and the old one are completely separate, so each is free to write to its shared copy of the data. Here COW is used to spawn new copies of the shared data when either process (parent or child) modifies them.


Swapping
Now that we’re able to allocate memory on demand, we can do some more advanced things with our virtual memory manager. Granted, we can only implement the more advanced features when we’ve got things like a disk driver and a process manager going, but the theory’s here. One useful feature is the ability of the virtual memory manager to swap pages to and from disk. This is present in most modern operating systems and it is responsible for the thrashing noise when the hard disk is accessed in a low-memory situation. The theory is simple: sooner or later, a block will need to be committed, and the physical memory allocator will run out of pages. We need to clear out some space for the new block: after all, the new block is being accessed right now, and there’s probably blocks in the system which haven’t been accessed for a while.

The swapper function needs to:
1) Find a block suitable for swapping out to disk. This will usually be the least recently used one, although Win9x will swap arbitrary blocks out randomly.
2) Make room for it in the swap file: talk to the file system and disk drivers for this. A fixed contiguous swap file is simplest (пїЅla Windows 3.1): at startup, record the disk sector numbers associated with the swap file and talk directly to the disk driver when necessary. Alternatively you could access the swap file as a normal file, via the file system driver.
3) Write the old block to disk, and record that is has been swapped out
4) Repeat from (1) until the physical allocation request succeeds

Note that if any of this goes wrong, the commit will fail. Remember that if a page fault occurs in a block which has been swapped out, it must be swapped back in again.


Overview
A typical sequence of events after an illegal address is accessed might go as follows:
1.Processor triggers page fault.
2.Control is passed to the kernel, which calls the page fault handler.
3.The page fault handler looks through the list of allocated blocks for the current process.
3.1.A block has been found which spans the faulting address; the “commit” function is called.
3.2.The commit function allocates a physical page for each page in the block’s range.
3.3.If the block was in the swap file, each page of the block is read in from the swap file.
3.4.The relevant mappings are made in the current process’s address space, according to the protection flags given when the block was first allocated.
3.5.Control is passed back to the application.
4.The page fault handler looks through the list of executable modules for the current process.
4.1.An module has been found which spans the faulting address; the “dynamic load” function is called.
4.2.The dynamic load function looks for a section in the module which spans the faulting address.
4.2.It looks for a copy of that section already loaded into another process’s address space.
4.2a.1. Another copy of the section has been found. Its reference count is incremented.
4.2a.2. The physical memory for that section is mapped into the current address space read-only. A later write to the section will incur another page fault; then, the physical memory for the section is copied and unshared.
4.2b.1. The section has not been loaded anywhere else.
4.2b.2. Physical memory for the section is allocated and mapped into the current address space.
4.2b.3. The section is loaded from disk into memory.
4.3.Control is passed back to the application.
5.No valid block has been found; the current process is either terminated or control is passed to its exception/signal handlers.

I’ve gone through the major functionality of a reasonably-sophisticated virtual memory manager. The VMM is able to split up applications’ address spaces into reasonable chunks, and the kernel malloc() makes writing the rest of the kernel a lot easier. But so far all we’ve got is still a bloated “Hello, world” program, albeit one which uses protected mode and which can allocate a full 4GB of address space. No operating systems ever sold themselves on the ability to switch from one archaic processor mode to another which became public in 1986, so it’s time to give the kernel some work to do and start scheduling some code.


Page Tables
by Mike Rieker

Page Tables
This discussion makes reference to Intel hardware, but is generally applicable to other processors that implement pagetables.

When an usermode application runs, it addesses memory using virtual addresses. So the value in a typical C pointer is a virtual address. The application has no idea where in physical memory it actually is, and for the vast majority of cases, it really doesn't need to.

This has been necessary so that you can, for example, have two users doing a 'copy' command at the same time. Each 'copy' command has its own set of physical memory pages that it is running in, but each 'copy' command is running at the same virtual address as the others. This gives us these advantages:
1) It can be linked to run at the one virtual address and not have to be adjusted for a different address depending on where in physical memory it happens to load.
2) It only has access to it's virtual address space and can't interfere with other 'copy' commands, or any other command for that matter.

So now the CPU is running that 'copy' command. And let's say the copy command is written in C, and a routine in there has a pointer variable. I mentioned that all addresses, such as those in a pointer are virtual addresses. Somehow the CPU has to translate all virtual addresses to an actual physical memory addresses so it can read or write the memory. It performs a translation of a virtual address to the corresponding physical address by way of the page table.

A pagetable is basically an array of pagetable entries that is indexed by a virtual address. Each entry of the pagetable contains items such as:
1) Whether or not the page is accessible at all
2) If so, the corresponding physical address
3) Allowable access modes (user, kernel, read, write)

Now I said the pagetable is an array that is indexed by a virtual address. Let's say our virtual addresses are 32 bits (as in an Intel pentium type chip). It would be impractical to have a pagetable that had 2^32 entries. So instead of using all 32 bits of the virtual address as an index, only the most significat 20 bits are used, the lower 12 bits are ignored. So that means there is one pagetable entry for 4K worth of virtual addresses. For example, virtual addresses 00003012 and 000039EC both reference the same pagetable entry, specifically index 3. It is said then that Pentiums have a page size of 4K, that is, one pagetable entry (PTE) maps 4K of virtual addresses onto 4K physical addresses. The low 12 bits of the virtual address that were discarded earlier are now used to index the specific byte in the 4K physical memory page.

Most programs do not need all 2^32 bits of possible virtual address space to execute. They would have to be 4 gigabytes in size to do that! Usually they are at most a few megabytes. This implies then that most of the pagetable contains entries indicate nothing is supposed to be at a given virtual address. If we needed to supply a pagetable entry (PTE) for each 4K page in that 4G address space, that is 1Meg entries. Each PTE takes a long, so you need 4Meg just for the pagetable. Well, the designers of the Pentium realized that would be silly, as back then, that's all the memory there was in the whole computer. So there is a pagetable page for the pagetable pages themselves, called a pagetable directory page. This means you only have to have a page of pagetable entries for addresses you are actually using. So if a page of pagetable entries is all unused, you don't have to supply a pagetable page. Each entry of the pagetable directory page has a flag saying whether or not there is a corresponding pageta le page, and if so, the physical address of the corresponding pagetable page.

The virtual address now breaks down into:
Bits 31..22: index into the pagetable directory page
Bits 21..12: index into the pagetable page pointed to by the directory entry selected by bits 31..22
Bits 11..00: offset in the physical page pointed to by the pagetable entry selected by bits 21..12

The above is Intel specific, but other processors have similar stuff. Like Alphas have 8K pages, and IIRC, they have 3 levels of pagetable pages, instead of just 2 (because they have 64-bit virtual addresses). VAX's do it a completely different way, but the result is the same.

When we say that a particular process is active on a CPU, we are saying that that process' pagetables are being accessed by that CPU. In the Pentiums, this is done by loading the physical address of the pagetable directory in %CR3. So to switch processes on a Pentium, all one has to do is change the contents of %CR3 and you are now executing with different pagetables.

One more thing. The Intel hardware requires only that the pagetable directory and the pagetable pages exist in physical memory. It does not require that the pagetable stuff actually be mapped to virtual memory, it will run fine without that. However, it will make your coding miserable (and inefficient). So you *should* map the pagetables themselves to virtual addresses. In my OS, I put them at the high end. So the pagetable directory page for a given process is at that process' virtual address FFFFExxx. (I map FFFFFxxx to no-access to catch bad pointers at the high end). The pagetable pages are just below that and occupy virtual addresses FFCFE000 to FFFFDFFF (4 Meg). Just work out how to do it with pencil and paper, and in a few short hours of pure joy you'll have it.


Pagefaults
Now we have to fill in our pagetable with something useful. Let's say someone types in a 'copy' command or something like that. What happens (in regards to pagetables)?
1) The OS creates a pagetable directory page for the new process
2) The OS creates pagetable pages sufficient to point to the memory pages for the copy executable
3) The OS allocates memory pages for the copy executable
4) The OS reads the copy executable into those pages
5) Additional pagetable entries and memory pages are added for stack and heap memory

Now OS's usually don't do this for the whole image at once, they typically just set up structures to facilitate this. The reason for this is you may have a large image (such as MS Word), but you are only going to use a small part of it this time. So why load in all 10Meg when you are only going to be using say 1.5Meg? And if we only had 8Meg of ram available, it wouldn't even fit in there all at the same time!

So what an OS does is:
1) Create the pagetable directory page, with all entries marked as 'not-present', ie, there are no associated pagetable pages yet
2) Create a kernel struct that says where on disk and how big the executable is, and what virtual address it is to be loaded at
3) Create a kernel struct that says how big the stack is and what virtual address it starts at. Same for heap memory.

Now when a CPU tries to execute instructions or data in that image, the CPU will not be able to access it, because the pagetable directory contains a null entry indicating the instructions or data are not in memory. So what the CPU does is generate a Page Fault exception. This passes the virtual address of the attempted access, and whether it was a read or a write, and whether it was by kernel mode or user mode, to a Page Fault Exception handler, which (usually) is a kernel mode routine that you are going to supply. A prototype for the handler might look something like:


int pagefault_exception_handler (void *virtual_address,
int writing,
int usermode)

Input:
virtual_address = address that the program was trying to access but couldn't because either:
1) the directory indicates there is no pagetable page present
2) the pagetable entry indicates no physical page is allocated
3) the pagetable entry indicates that the access attempt is illegal (eg, writing to a page that is marked read-only)

writing = 0: the program is attempting to read the memory location
1: the program is attempting to write to the memory location

usermode = 0: the routine was executing in kernel mode
1: the routine was executing in user mode

Output:
pagefault_exception_handler = SUCCESS : the page was faulted in and the instruction should be retried
else : unable to fix it, signal a pagefault exception

So the pagefault handler routine looks at the kernel structs that were created to determine whether the access was legitimate, ie, is there supposed to be something there or not. If not, typically, it signals the exception (like a 'segment violation' in Linux). If there is supposed to be something there, that's when it allocates a pagetable page (if there isn't one there already), and allocates the page for the instructions or data.

Now it needs to look at the struct to see what goes into the page. If the struct says it is part of the executable, then the page is read in from disk. If it is a stack or heap page, it is filled with zeroes (or some other fill pattern).

Once the page is all set up, the pagefault handler returns back to the instruction that caused the fault. The CPU re-executes the instruction, and this time, it succeeds, because the pagetable entry is all filled in.


Some details
So the things the hardware requires us to tell it in a pagetable entry are:
*whether or not the page is in memory

*if so, what physical page it is in

*what kind of access is currently allowed (read, write, user, kernel)


Now, it turns out that your OS may find it handy to save some other info in there, too. Fortunately, the hardware usually leaves unused bits in the pagetable entries just for this very purpose. If it doesn't, you'll have to make an array that parallels the pagetable array to store these extra bits.

So here are additional things I store in the pagetable entries:

*software page state (valid and readable, valid and readable but dirty, valid and writable and dirty, page being read in from disk, page being written out to disk, page read/write from/to disk failed, page faulted out)


*what the requested protection is (read, write, user, kernel)

Differs from current protection. Current protection should be 'no-access' when the page is faulted out, read-only when the page is being written out to disk, etc. Requested protection is what the page should be when it is fully realized.

Here are some low-level routines you will probably need for accessing pagetable entries:

read_pte : given a virtual address, determine if the corresponding pagetable entry exists in memory for the current process.
If not, return the virtual address of the missing pagetable entry (this will allow the caller to fault in the pagetable page then retry)
If it is in memory, return:
whether or not there is a memory page associated with it
if so, what physical page is there
current access modes
software page state
requested access modes

Now in my OS, my kernel's pagetable pages are always in memory, so I provide another routine, read_ptesys, that panics if the entry is not in memory, so I don't have to check the return value.

write_pte: given a virtual address, write the corresponding pagetable entry
For my OS, this routine could assume the pagetable page was in memory, as I always attempted to read the pagetable entry before writing it.


Translation Buffers
You may wonder if the CPU actually goes out and reads the pagetable entry for every memory access so it can translate the virtual address to the physical address. Well, they don't. CPU's typically have a special cache where they save the most recently used pagetable entries so they don't have to constantly go out and read pagetable entries.

These caches, typically, are somewhat 'manually operated'. The CPU will automatically load entries into the cache, but if you change a pagetable entry, it won't unload or update the corresponding cache entry. They do provide an instruction to unload it, though. So this just means your 'write_pte' subroutine has to also invoke this instruction after it sets up the new pagetable entry. For Intel chips, the magic instruction is INVLPG. The cache also gets completely flushed when you change which pagetable you are using, ie, you write %CR3.


Multiprocessor stuff
Now if you are running on an multiprocessor system, things can get a little messy. Let's say two (or more) CPU's are executing different threads in the same process. Suppose one of the CPU's does something like an 'munmap' call that removes pages from the virtual address space and frees the physical pages for use by other users. So it executes INVLPG instructions for itself to remove those bad cache entries. It also has to tell any of the other CPU's that are mapped to this pagetable to remove their bad cache entries, too! Typically, this is done (in Intel processors), by setting a value in memory indicating which virtual address to invalidate, then issuing an NMI to the other processors, and then waiting for them to acknowledge that they have done the invalidate.

Now there is a little trick you can use to minimize NMI-ing everytime you write an pte. Suppose, again, we have two CPU's executing different threads in the same process. And one of them gets a pagefault because part of the executable needs reading in. That pagetable entry will be 'no-access' because there is nothing there in memory. So the faulting CPU will read the page in from disk and set up the new pagetable entry, and issue an INVLPG to itself. Now it doesn't have to NMI the other CPU's. If the other CPU attempts to access that same page, the worst that will happen is it will get a pagefault too. Then your pagefault handler will see that some other CPU faulted the page in and it's ok, so it just does an INVLPG on itself and returns. So it turns out the only time you need to do the NMI thing is when you are 'downgrading' the protection on a page, ie, you are disallowing some type of access that was previously allowed. Examples are changing a page from read/write to read-only, or marking an entry as non-existant.

So my OS actually has two pte write routines, pte_writecur which invalidates only the calling CPU's cache entry, and pte_writeall which invalidates all CPU's cache entries. I must call pte_writeall for downgrades in protection, pte_writecur can be called for upgrades only.



Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье