Paging (Help!)

[Lprogster]

...

Thanks,
Lster

[mystran]

A page (without qualification) is supposed to refers to a virtual page. A page frame, then is something you can put a page into. In other words, a page frame (or just a frame) is a page-sized unit of physical memory. The idea is that you can put one page in each frame, and if all the frames are full, then you must put rest of the pages into secondary storage instead.

Seriously, you hear frames called "physical pages" more often than "frames" these days, but that's anyway what a frame means, and originally a "page" only referred to the virtual page.

As for malloc/free, that's a separate thing. Those just take a big area of memory (a heap, usually can be grown as needed) and split it into small chunks and keep track of what parts are free and what are in use. Malloc/free don't usually work on pages, because then the smallest block you could allocate was 4k. Doing a good malloc/free is pretty hard problem, so I'm not going to go into details here, 'cos I'm hungry.

As with a lot of thing with OS dev, you can usually decide where you want to put something. The tutorial doesn't seem to want to load right now, so I can't look into it to see what it does, so ....

[Lprogster]

...

Thankyou very much for your help,
Lster

[mystran]

With malloc (for the moment) any sized allocation is fine...

Actually, now that I've eaten, I could explain the basic idea of malloc/free.

These two functions (and typically calloc/realloc as well) manage the so-called heap. When a program written in a typical language like C runs, it uses three types of memory: there statically allocate memory, stack, and heap. The situation is typically more or less the same, whether you're in a normal program, or a kernel, though a kernel will have to deal with some more issues, ofcourse.

Statically allocate memory includes the program text, as well as any "global" variables and other data (like anything with "static" qualifier in C) that will exist from the start of the program all the way to the end of it. Normally there are three program segments (not to be confused with hardware segments, which are best ignored) defined: .text which is the program code and often read-only, .data which is any static data with it's initial content defined in the program, and then .bss, which isn't really in the binary, rather only it's size is kept, and at load time the .bss is simply allocated and cleared with zeroes. Then there's often also .rodata (for constant strings) but you can tell your linker to put any .rodata segments into the .text segment of the program.

If you use something like GRUB to boot your kernel, it'll take care of these segments, load .text and .data where they are specified to be loaded (usually 1MB) and clear .bss for you. When your kernel loads a program, it'll do the same for the program in question.

Now, if we always knew how much memory we need, all would be easy. But we typically don't, so there's the stack and the heap. For normal programs stack is normally kept at the end of their address space, though multi-threading complicates matters (you have to place somewhere a stack for each thread). In a kernel, you typically keep an initial stack in .bss, and if we need more stacks (for each thread we have in kernel) we just allocate them from the heap or something. Or maybe allocate pages for them directly. Depends on what you want. But the point about stack, is that once you have a stack, you can allocate/deallocate by moving a stack pointer up and down. A compiler does this for you automatically when you use local variables.

Now, heap is different. Heap is for data which we don't know how much we need, and how long we need it. That's what malloc()/free() are for. Heap normally begins at some fixed adress (after .bss is one option, but for kernel you might want something else) and it's size can usually be grown (map more pages at the end of it). When you malloc() something, it looks around the heap for a free block. If there's none, it asks the operating system (or in case of kernel, your virtual memory manager) to grow the heap, until there's enough space. When you free() something, it marks that area of the heap free, so next time you malloc() something, it can be used.

So how do you do that? Well, as long as we don't need to free() anything, we can simply look at the last allocation we did, and if you asked for 16 bytes of memory, give you the address of the free area, and mark down that 16 more bytes where allocated (advance the free-area pointer by 16 bytes). But in reality you want to free() as well, right?

There's a few options, but easiest is for malloc() to take a block that's a bit larger than what you asked for, write down in the beginning of it how much you allocated, and then give you a pointer to the memory after the "header" that it just wrote. free() can then look what's just before the pointer you gave it, to find the size of the block, and add it to some sort of free-list. Now malloc() first scans the freelist to see if there's already a free block large enough (and possibly splits a too large block, or something) and only if there's no suitable block, it goes and actually allocates new memory.

That's the basic idea at least. In reality, there's a few complications. You typically want to align the blocks at least to pointer size or more (so, say, you want to align to 8 bytes, you round any allocation up until it's a multiple of . You also might want to keep more than the size. I keep the size of previous block as well, and whether it's allocated, so that I can join two free blocks together. When a block is free, you can use the block itself to keep a linked freelist, but this means you need to have the smallest allocation size fit at least two pointers (so 8 bytes on 32-bit architectures) plus whatever headers you have (say, I have 8 bytes for headers, giving me a minimum blocksize of 16-bytes, of which the client can use .

You could also keep different free-lists for different sizes, so that if you are looking for a large block, you don't need to scan a free-list full of small blocks that are way too small... and such.

You could search for dlmalloc which is a known-to-be-good malloc. It's page also has a description of how (an older version of it) works, which can be helpful. Then there's also some descriptions of mallocs in books like K&R's C programming language, and various lecture slides and what not, but most of those are not very good. You could also have your malloc()/free() return memory areas back to the kernel when larger areas are freed, but I don't think there's much point doing this before your kernel is advanced enough that this actually becomes an issue.

You could also search the forum for "malloc" as this is not the first (and probably not the best) description I've written about mallocs. I even posted an old version of my own malloc here at some point (was in announcements forum though, I think). I could probably post my improved version some time real-soon-now.

Hope that helps.

[Crazed123]

A page (without qualification) is supposed to refers to a virtual page. A page frame, then is something you can put a page into. In other words, a page frame (or just a frame) is a page-sized unit of physical memory. The idea is that you can put one page in each frame, and if all the frames are full, then you must put rest of the pages into secondary storage instead.

Actually, if you want the contents of the two pages to be the same (exactly the same, with writes to one affecting the other), then you can put two pages in one page frame. This forms the basis of shared memory, which can be used to perform IPC, to avoid copying common read-only pages, and some stuff I can't think of at 1 in the morning.

[mystran]

Actually, if you want the contents of the two pages to be the same (exactly the same, with writes to one affecting the other), then you can put two pages in one page frame. This forms the basis of shared memory, which can be used to perform IPC, to avoid copying common read-only pages, and some stuff I can't think of at 1 in the morning.

That's a VERY confusing way to talk about shared memory. A page is a unit of information, which may be in a frame, or in secondary store, or both.

You just map the same page in (and hence the same frame) in two processes, when you are doing shared memory. The whole point of shared memory is that the page is shared... But then again, once we start doing copy-on-write, we indeed have two logically separate pages in the same frame.

I like observational equivalence here: two pages are the same, if they are observationally equivalent. If writes into one affect the other, then they are the same page. If writes to one will make it different, they are two different pages, even if they shared the frame.

[Lprogster]

...

Thankyou lots again,
Lster

[pcmattman]

I couldn't actually get that tutorial to compile/work ...

AFAIK paging allows you to allocate the physical memory itself to 'pages' which can be any address. For instance, in your process creation function you might allocate a new page for the new process, and then the process can refer to the memory relative to 0, instead of the actual location at which the physical memory is.

It also means that you don't have to do dynamic relocation of symbols in executable files.

If I could figure out how to implement it, I'd be very happy.

[mystran]

There's nothing really hard about paging, except a few chicken-egg problems, and a lot of things you just have to decide..

Anyway, you should probably divide and conquer:

- figure out some way to keep track of free frames first. I suggest a stack, at least for most of your pages, because it's simple and efficient. For a stack you need push (free a frame), pop (allocate a frame) and a method to fill the stack initially from a BIOS or multiboot memory map..

- next decide about your virtual memory layout, at least partially, write some functions to manipulate page directory/table entries, and get the basic paging up and running. I suggest mapping the page directory as a page table at some point in memory, giving you a sort of recursive mapping, which let's you easily access the page directory at a known address.. YMMV..

- next decide where your kernel heap goes, and write a function (for malloc to call) to extend this area by mapping more pages. Then you can write malloc/free, or if you had those already, make them use the dynamically allocated kernel heap. Rest of the stuff you can worry about later..

- finally, once you get into the point that you want to go to userspace, you write a separate manager for the userspace part of the virtual memory, which knows how to deal with all the fancy stuff they expect in normal processes... and this can then use the page-directory-manipulation functions you wrote earlier to do the actual manipulation, and not care (much) about the hardware details..

Trying to do all of the above at once is likely to fail. Start simple, and don't try to mix separate issues too much. If you try to make clean simple functions, you can always add more functionality later.

[Lprogster]

...

Thankyou both
Lster

[pcmattman]

Post your Bochs log. We can then find out why it restarted.

[Lprogster]

Sorry, here is 'bochsout.txt':

...

Pretty short ...
Lster

[Lprogster]

Looking at it, it seems to repeat its self...

[pcmattman]

Obviously, the paging causes the system to crash on an interrupt...

I'm not 100% sure as to what CR0-4 hold after such a crash (maybe the page pointer?)...

Edit: the Intel manuals tell all:

The cr3 register contains the address of the currently-executing process's page directory.

Always look at the first crash. After that, the system is compromised:

Code: Select all

00007034488i[CPU0 ] | CR0=0x80000011 CR1=0 CR2=0x80000011 
00007034488i[CPU0 ] | CR3=0x0009c000 CR4=0x00000000 

The page directory apparently is at 0x9c000... is this right?

The CR2 register always holds the exact location of the last page fault
[/code]

CR2 holds the location of the last page fault. Reading the error code when exception 14 fires may help (if you have an IDT set up):

Code: Select all

Bit 2: 0=supervisor, 1=user
Bit 1: 0=read, 1=write
Bit 0: 0='Page not present'

[Lprogster]

Im not sure if I understand you?