OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Apr 26, 2017 4:04 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Memory Management...
PostPosted: Sun Jan 29, 2006 4:54 pm 
I've been trying to make the memory management for my kernel, but there's one thing I don't understand. How am to supposed to allocate pages to hold the page tables without having a page allocator in the first place?


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Sun Jan 29, 2006 5:20 pm 
What I do is I reserve a space in memory to hold the kernel's page directory and first page table (i.e just below where I load the kernel). This is enough to get the kernel fully initialized.

Cheers,
The Senaus


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 3:18 am 
Thanks.

I have another question now though. If all the pages that a page table refers to are freed, should I free that page table as well? If so, I'm not sure where I should keep the information. I was thinking about using the "available" bits in the first few page entries to store the information I need. That seems very ugly though.


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 4:27 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
that's not mandatory. You might very well have a page table present without any page present in it. The "available" bits are indeed there for swapping/maintenance purpose, but you probably won't be able to use it to count how many present entries a page table has.

Personnally, i'd be tempted to handle that in the "pages collector" mechanism (e.g. the one which will read dirty/accessed flags of each page, and decide whether the page should be kept or swapped out). Since you'll have to sweep all page tables to do that, that will be the best time to tell whether the content of a page table can be dumped.

Note, however, that a non-present page entry could still contain valuable information (such as where on the swap device the page is kept), so you might want to keep a page table present (or swap it) even if it has no present pages.

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 3:06 pm 
Oh. I was thinking of shifting and ORing the avail bits of the first three entries together (and of course storing it there)... Anyway, I think that's a really bad idea now, though, since storing the counts in a separate place wouldn't take much memory, not to mention that I might want those bits for something else.

Anyway, thanks for the help. I started the kernel I'm working on a long time ago, and just came back to it. The reason I quit was because I couldn't understand how the memory management was supposed to work. I think I understand it better now. What I don't get is how you're supposed to implement a dynamically sized free page stack when your memory manager won't work until you've done that... So I'm just going to use a bitmap for now, even if it's slow.


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 4:34 pm 
From what I've seen you simply set aside memory that the kernel uses (even if it is just during boot and system init). Remember, you have control over everything.

Let's say a system has 16 MB of memory and you decide to load all of your (kernel) modules (including the memory manager) starting at the 1 MB mark. You could decide that the stack is some area below 1 MB (if you do, put it below the BIOS areas and above the "old" BIOS interrupt table and BIOS data area, so in other words above 4 KB and beneath 640 KB) or if you want at the end of memory (the 16 MB mark in this example).

You can then mark these pages (including the ones you loaded all your kernel modules into and the memory table itself) as not available in your [physical] memory map you are building at that point. If you want to keep it simple you never give those pages "back" to your memory manager (after you start that module).

Let's say you put the stack in the 4 KB - 640 KB range. If so, you could simply set all pages below 1 MB to not available (or have your memory manager start at the 1 MB mark).

Let's say our kernel with all the modules and data structures takes 131 KB of memory (which we loaded starting at 1 MB). Assuming we have 4 KB pages we make the first 131 / 4 = 33 bits [which represent pages], assuming the memory manager starts at 1 MB, zero to indicate memory that is in-use or unavailable. The rest of the 16 MB - 1 MB - 132 KB (33 pages) is available for the memory manager and when it starts we give it this bitmap to work with.

This way you can use all the memory you want during boot / load and you simply inform the memory manager which memory pages are already in use or not available.

This is probably one of the easiest ways to do all this, but you can make it as complex as you want. You could load the memory manager as the very first module and just have it mark its own memory as in use, for example.


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 5:12 pm 
Maybe I'm just misinterpreting your post, but I don't see how I could put the stack below the kernel because it could be too large to fit there. If you have 4GB of physical memory, that's 1,048,576 pages. Each page address takes 4 bytes, so that's 4,194,304 bytes or 4MB. So I would need 4MB to hold the stack at it's maximum possible size for 4GB. The problem is that most computers don't have nearly 4GB, so I would be wasting lots of memory if I just reserved 4MB no matter what instead of making it dynamic. Maybe I missed something, though...


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Mon Jan 30, 2006 9:47 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 7824
Location: At his keyboard!
Hi,

shadow wrote:
Maybe I'm just misinterpreting your post, but I don't see how I could put the stack below the kernel because it could be too large to fit there.


I think Rob meant the CPU's stack (SS:ESP) rather than a free page stack.

shadow wrote:
If you have 4GB of physical memory, that's 1,048,576 pages. Each page address takes 4 bytes, so that's 4,194,304 bytes or 4MB. So I would need 4MB to hold the stack at it's maximum possible size for 4GB. The problem is that most computers don't have nearly 4GB, so I would be wasting lots of memory if I just reserved 4MB no matter what instead of making it dynamic. Maybe I missed something, though...


That isn't how free page stacks are normally implemented.

Normally you'd have a pointer to the top of the stack somewhere, which points to the address of the first free page. The address of the second free page is stored in the first free page, the address of the third free page is stored in the second free page, etc. This consumes 4 bytes regardless of how much memory is present. For e.g.:

Code:
void *alloc_page(void) {
    void *freePage;

    freePage = currentPageStackTop;
    currentPageStackTop = currentPageStackTop->nextFreePage;
    return freePage;
}



There are some variations on this though, like using a stack of "free page index tables". In this case each index page contains the address of the next index page, a count and the addresses for up to 1022 free pages. When you allocate a page you get the last entry in the index page and reduce the count. If the count reaches zero then you'd take the index page itself and find the address of the next index page from it. For e.g.:

Code:
struct INDEX_PAGE {
    void *next_index;
    unsigned int count;
    void *free_pages[1022];
}

void *alloc_page(void) {
    void *freePage;
    int entry;

    entry = currentIndex->count;
    currentIndex->count--;
    if( entry == 0) {
        freePage = currentIndex;
        currentIndex = currentIndex->next;
    } else {
         freePage = currentIndex->free_pages[entry];
    }
    return freePage;
}



The first method (plain free page stack) looks simple but it isn't because "currentPageStackTop" is a physical address and "currentPageStackTop->nextFreePage;" doesn't work. You have to map "currentPageStackTop" into linear memory before you can get the next free page. This usually means combining it with the linear memory manager - when you're allocating a linear page you'd store "currentPageStackTop" into the page table, then use INVLPG to flush the TLB entry, then get the address of the next free page from whereever you mapped "currentPageStackTop".

The second method (stack of index pages) has the same problem - you have to map the current index page into linear memory before you can access it. Because of the way it works you can get 1022 free pages easily, but when an index page becomes a free page you need map the next index page into linear memory.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re:Memory Management...
PostPosted: Tue Jan 31, 2006 12:29 am 
Thanks for that explanation. I'm going to try the second one. I find that a lot of the information on the Internet doesn't really explain in enough detail. When I read "stack", I thought it meant just a long contiguous block of memory holding only addresses.


Top
  
 
 Post subject: Re:Memory Management...
PostPosted: Tue Jan 31, 2006 2:39 am 
I meant the CPU stack indeed.


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: StudlyCaps and 13 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group