OSDev.org

The Place to Start for Operating System Developers
It is currently Sat Mar 25, 2017 3:47 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 15 posts ] 
Author Message
 Post subject: memory management the x'th.
PostPosted: Tue Jun 03, 2003 2:27 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
Yeah, I am about to implement a sort of demand paging.

I have some questions about it - just for going sure if I have understood Tim Robinsons's memory management paper (gg) and other ressources right.

1.
In the virtual memory manager, I have a collection of lists which are responsible for the book keeping of memory:

one for the kernel memory space (which will be hooked to each process)

one for each process: which virtual memory areas the process has allocated - f. ex. if it allocates a postbox at 0xa0000000 - 0xa000ffff, this will be recorded in it's list.

Is it wise to have these lists organized as a kind of tree structure?

2.
the pagefault handler wakes the virtual memory manager task with a message (process, adress causing the fault - cr2 register). the manager task crawls the list of the faulting process. If the missing adress is in valid adress space, the memory manager task fetches a physical pagetable for it and puts it into the apropriate page table of the process - if not, it kills the process.

3. for spawning processes ... is it good to have some space in kernel memory area spare for duplicating/building the page directory/pge tables prior to passing 'em to the process? the page directory I'd enter also in the process structure for the task switcher has to access it too.

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 03, 2003 10:16 am 
beyond infinity wrote:
Is it wise to have these lists organized as a kind of tree structure?

Yes, I like to do this in some form of binary tree, to make lookups faster. Lookups (in the form of page faults) should be much more frequent than insertions and deletions (in the form of allocating and deallocating memory) so it makes sense to have an efficient data structure there. NT does this; Linux did at one time, then it didn't, and now maybe it does again.
Quote:
3. for spawning processes ... is it good to have some space in kernel memory area spare for duplicating/building the page directory/pge tables prior to passing 'em to the process?

I avoided this issue by giving new processes a page directory with the bottom half full of zeroes and the top half full of the kernel address space (as normal). The first thread starts at a well-known address (0xdeadbeef).

The new thread will fault straight away and trap into the kernel, which can then allocate some memory in the address space of the new process, load some code and reassign the EIP of the thread to the entry point of the program. It seemed easier to do this than to have all memory management functions work for other processes as well as the current one.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 03, 2003 12:38 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
Tim Robinson wrote:

I avoided this issue by giving new processes a page directory with the bottom half full of zeroes and the top half full of the kernel address space (as normal). The first thread starts at a well-known address (0xdeadbeef).

The new thread will fault straight away and trap into the kernel, which can then allocate some memory in the address space of the new process, load some code and reassign the EIP of the thread to the entry point of the program.


Hehe ... interresting trick. I noticed there are some 0xdeadbeef in Linux Kernel aswell, but i can't remember why and where ... do you think they use the same trick as you do or is it an original idea from you ?

Btw, in Clicker, there is a special thread (the ProcessManager) that has the ability of moving from one address space to another, so when you create a new process, you first build a address space which is a complete copy of the current one and then ask the process manager to go tidy up that place. It will then remove pages that shouldn't be kept and make other pages copy-on-write if needed, etc. Once this is completed, it can also spawn new threads that will live in that address space before it returns to the Kernel Initial address space.

Maybe i should give a deeper look at your technique, as it seems way easier to deal with (though i'm not sure it is portable to Clicker :-/)

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 03, 2003 5:55 pm 
0xdeadbeef is a common hex constant which should be rarely used as a normal number yet is obvious to the human eye.

I don't know how original my process creation trick is, but it's just a bit of lateral thinking which gets me out of writing a lot more code.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 10, 2003 6:14 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
Now, it is about adress space management and binary trees:

I am now to some extent finished with the physical/virtual memory allocator/deallocator. It has still to be tested, but it works relatively stable. And due to the PD-selfmapping trick, it is nice to work with the paging stuff.

My problem is the following: I wanna do book keeping of adress space for processes in form of a linked list which forms a binary tree. I want to have this tree be organized by process-id, so each process gets its own list of allocated memory-areas. Would a binary-tree be effective enough? How should I do the condition whether to descend left or right leaf? And over all, what about the root node? Shall I install it at initialization of memory management?

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 10, 2003 8:58 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
hm. here's my suggestion:
- each node of your tree describes a virtual area (i.e. it has a base address, a size and properties)

- each node splits its children between areas that are *smaller* (i.e. children.base+children+size<this.base) on the left and areas that are *larger* (i.e. this.base+this.size<children.base) on the right.

- you don't need a root node until you assigned the first area.

- AVL trees may help you keeping good performances by keeping the tree depth under an optimal value (i.e. at every node, abs(this.left.depth() - this.right.depth())<=1 ). there should be tons of tutorials about AVL trees on the web.

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Tue Jun 10, 2003 5:24 pm 
Since most of the time you'll be searching on virtual address (i.e. on page faults), I recommend you sort your binary tree on base address. That is, a node's left children all start before it, and a node's right children all start after it.

First fit or last fit algorithms should also work well this way. Follow the left branch if the total size beneath the branch is less than or equal to the size requested. Otherwise, check the right branch; if it doesn't have enough space, then reject this node. If this node doesn't have any children, and it has enough space itself, then split this branch in two, and mark the appropriate half as allocated; put the other half as one of its children.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Wed Jun 11, 2003 1:18 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
Thx for advice guys :-))

Ok, so I would have a tree of memory allocations PER process.

Since the low level pagefault handler, which talks eventually to memory management task, knows the identity of the process causing the fault, it can make the memory manager do this searching and eventual committing of memory with the appropriate process data - the current process.

There won't be necessity to search for the process for it's vmm-allocation-tree is located in the process structure. Hm... would this fit into a micro kernel approach, where memory management has its own data and prcess management has also it's own data?

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Wed Jun 11, 2003 1:51 am 
Should be OK as long as the MM process doesn't try to allocate memory inside its own allocator, although this is a problem with any memory allocation scheme.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Wed Jun 11, 2003 2:03 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
Hmm ... to avoid this, there will be some semaphore or spinlock, because I want only One at a time requesting memory. Memory allocation is something *nonreentrant*. Therefore, Memory Manager will have to handle one request after another one.

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Wed Jun 11, 2003 10:26 am 
I don't see why memory allocation shouldn't be re-entrant. Certainly it should be possible for two different processes to try to allocate memory at the same time, and, with proper synchronisation, it should be possible for two threads in the same process to do the same.

What I was thinking was the possibility that the memory manager process recurses infinitely after trying to call itself from within itself.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Thu Jun 12, 2003 12:41 am 
Offline
Member
Member

Joined: Wed Oct 18, 2006 11:59 am
Posts: 1600
Location: Vienna/Austria
at least in a single processor environment, only one process at a time can have the memory manager allocate memory for him.

As you say, Tim, there HAS to be synchronisation - one process after the other one. That's why I consider at least the crucial parts of memory management - allocating more memory via morecore f. ex. - non reentrant. Maybe I am wrong with this, maybe I lack the proper words to argue exactly. But simply expressed: I think it is good to have requests to the memory manager queued up so that they are treated one by one and not ... at sixes and sevens (good to have some dictionary at hands - should mean jumbled,mixed-up).

As for two processes trying to allocate memory at the "same" time: Of course, they can try. It is up to the internals of the mm-task/routines to handle those requests by some policy: first come first served, highest priority first or so... I think it has to do with concurrency.

As for recursive calls of mm to itself: Hmmm... yes, it needs itself more memory the recursive call itself needs more memory. Maybe one can avoid this issue by providing the memory manager some calls it can use to allocate more memory for itself in a quick way?

stay safe

_________________
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Thu Jun 12, 2003 3:06 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
my personnal policy was to build the memory system as a upside-down pyramid. The above components (closer to useable service) may use the lower level, but not upper-level calls.

At the very bottom of the system was the system heap that can allocate and free chunks from the 4MB microkernel heap (mapped with static physical addresses). Atop of this is implemented stuffs like demand-paging, memory objects and address spaces (with control structure in the microkernel heap).

About the multiprocessor (or just multithreaded) system, one could decide to split resources (for instance physical pages) into several "free" structures, and apply different locking policies on it, so that even when the generic memory allocator is locked by some out-of-timequota thread, you still can allocate buffer-class memory to receive network packet.

As memory allocation algorithm usually have unpredictable execution time, i think it wouldn't be wise to lock interrupts while they're running ...

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:memory management the x'th.
PostPosted: Fri Jun 13, 2003 7:16 am 
Yeah, this is why I am now implementing the adress space management routines on a *per process*-base, so that the memory manager just needs to care about the actual process which has caused a fault or which is on the way of being born (via fork/exec). May be it is good to walk in the ruts of tim robinson: do lazy demand paging. Just install the structures and the adress space and have the page fault handler fill in the pages/load the program into memory.

I implement those functions on top of the paging engine I have coded so far: a collection of functions responsible for filling in or deleting page table entries and page tables. These calls pick free physical pageframes from the physical mm, which just keeps a stack of avilable pages. This has to be fine-grained too. The calls go from upper layer to lower layer, but not in the other direction, thus providing a useable abstraction.

stay safe.


Top
  
 
 Post subject: Re:memory management the x'th.
PostPosted: Sun Jul 13, 2003 8:05 pm 
BSD, etc, do something similar, but not quite. Instead of making the incoming process cause a massive amount of page faults when starting up, in order to page in its first x amount of pages from the filesystem, BSD uses a pre-fault scheme, where it loads in x amount of pages before the process executes, cutting down on the initial splurge of page faults.

You could always pre-load some of your pages before the process executes, and allow the other pages to be faulted in on demand.


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

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], Gigasoft, Google [Bot], MSNbot Media and 3 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