Heap/Tasking questions

[Creature]

I actually have 2 questions that aren't really related.

Firstly, when I set up paging, I need to set up my heap. The thing I was wondering about is where does this heap start and where does it end? The most logical thing to do seems to let the heap (as virtual address) start after the kernel (which was identity mapped) and let it run all the way to infinity (~ 4 GB on 32-bit). But when I do that, I might get problems mapping executables into my address space later (what if they want a virtual address that the heap is using). The other solution is to let the heap start high in virtual memory (for example, in JamesM's tutorials, he uses 0xC0000000 and as limit 0xCFFFF000). But with this last approach, wouldn't a part of memory be lost? Suppose the physical RAM is 2 gigabytes, then the area between the starting address and limit address only permit a certain range of virtual (and thus physical too) addresses. So what virtual address is one supposed to use for the physical addresses then? Have I got this all wrong or is there a simple solution behind this?

The second thing I was wondering about is how the heap relates to multitasking. I know that, when the heap has just been created (there is no multitasking whatsoever yet), there is basically only one address space (the kernel's). When a new process is created, it (preferably) makes a copy of the kernel's directory so it already has the important area's mapped in (the heap and the kernel), so it will stay consistent. The new directory basically links into the kernel directory so they remain the same. This is all great, but what happens when you're allocating memory across processes and one of them makes the heap want to expand? The heap will allocate additional physical frames and map the new physical addresses to those frames. But what if the new virtual addresses required a new page table to be created? It will be fine for the kernel's directory, but the other processes only have their address space linked up to where the heap didn't expand yet. So the new virtual addresses aren't mapped.

Sorry for the longwinded post. I'm feeling like I'm getting a better grasp of paging lately so that basically explains the questions. It is possible that I got this all wrong, but please do correct me if I'm mistaken somewhere.

Any advice is appreciated,
Creature

[Gigasoft]

It's best to reserve a range of virtual addresses for the heap in the kernel's address space. Optionally, you could add more virtual address ranges if the first becomes full. Memory isn't lost, only the range of virtual addresses available to each process.

Either, you can embed the kernel's address space in each process' address space. This requires you to go through each process every time the kernel's part of the page directory changes to update every process' page directory. Another, slower option, which Mac OS X uses, is to only reserve a small region in each address space, which contains the GDT, IDT and interrupt stubs which switch to the kernel's page directory. This is a more complicated solution since it means the kernel has to temporarily map parts of the application memory in its own address space when receiving data from, or returning data to an application.

[NickJohnson]

... This requires you to go through each process every time the kernel's part of the page directory changes to update every process' page directory.

No, it doesn't. You can have a set of page tables dedicated to the kernel that are simply pointed to by all of the page directories, as long as kernel space is 4MB aligned in virtual memory. You never have to copy anything or even do a task switch. I hope the way you described isn't how you do it...

[gravaera]

I've never asked anyone for critique on this, and it works fine, so I don't see any need to change it:

In my MM, There's the physical overview of all RAM, and then each process, upon initialization is given a per-process data structure which is like a mini-PMM for it and its threads. This per-process data structure (C++ class) is actually the syscall entry for MM, where before a process is given a new free frame, its per-process structure is consulted.

This per-process class has the routines (getVaddr(), getNVaddrs()) to find free pages (I use the word 'page' for a virtual block and 'frame' for a physical block; I've seen people mixing up the two, so I'm making it clear for readability) in the process's address space for the purpose of mapping the frames into the process's address space when the kernel returns the new frames.

On init, a process's executable image is mapped and recorded to the kernel as being 'non-volatile' addresses, and every other page in the address space other than the process's 'non-volatile' space, with the exception of page #0 and the kernel's own 1GB, is taken to be 'volatile', and can be mapped by the kernel to the process for any purpose, whether mapping files, or shared memory, or allocated memory, etc.

The implication is that the process is confined to its 3GB, and the kernel uses its 3GB ONLY for itself, and for managerial structures for userspace, thus allowing the kernel to grow as needed without having to worry about any userspace influences in its address space, and having to move them around if any sort of rennovations are needed. I assume this is not so innovative as it's the only logical way to do it.

In other words, all virtual pages which are not in a process's 'non-volatile' range, (the executable image itself) are like a huge heap in my design, and the kernel may allocate virtual addresses from anywhere, with the sole provision that it starts mapping at pages above the executable image first. This way, the allocated resources would grow toward the process's stack (and thus the guard page, so it can't grow into the kernel).

I've though of this from as many angles as I could, and I have, while writing it, not encountered any ideological concerns.

I've long wondered why anyone would limit the size of the heap, or try to confine it to one area: what if the user is running an emulator, and requests that the emulator emulate a machine with about 2GB of RAM? How would anyone with a constrained heap deal that kind of happenstance?

Note well that I've already considered fragmentation, etc, and have answered these privately; This is not an exhaustive overview of my MM. I wonder if that answers the heap question, Creature? As in, not having a fixed, or designated 'heap' area at all? and confining the userspace process's heap to its own area of the VAddress space? Certainly from what I've read, Windows and Linux do something at least slightly similar;

[Gigasoft]

... This requires you to go through each process every time the kernel's part of the page directory changes to update every process' page directory.

No, it doesn't. You can have a set of page tables dedicated to the kernel that are simply pointed to by all of the page directories, as long as kernel space is 4MB aligned in virtual memory. You never have to copy anything or even do a task switch. I hope the way you described isn't how you do it...

I know, but that would waste some space. I prefer my way because the kernel's page directory doesn't change too often, and every page directory is always present in the kernel's address space anyway, so updating them is very quick.

[pcmattman]

I know, but that would waste some space

I hope you realise shared page tables actually reduce the amount of memory used...

[Gigasoft]

Well, my page tables are shared. I'm not copying those. I'm just updating the page directories, not the page tables. So I'm changing only 1 dword per process when there's an update in the page directory.

[Creature]

... This requires you to go through each process every time the kernel's part of the page directory changes to update every process' page directory.

No, it doesn't. You can have a set of page tables dedicated to the kernel that are simply pointed to by all of the page directories, as long as kernel space is 4MB aligned in virtual memory. You never have to copy anything or even do a task switch. I hope the way you described isn't how you do it...

I think this is what I was planning to use. So basically, suppose I use a constrainted heap (the idea of which I don't really like, but it can possibly be solved later), then I will know what addresses the heap can use (the addresses between start and limit). So taken that I know that, I can (when paging is set up) create the page tables matching those virtual addresses (I don't necessarily have to set up the pages yet). When a new process is created later, the tables matching these heap virtual addresses are "linked" rather than copied, so if I change anything inside the heap or it expands within its boundaries, there is no problem whatsoever since all directories will be automatically updated.

If I however don't want to use a constrainted heap (I will have a starting address somewhere, though), then the heap can expand as far (in virtual memory) as it wants to (~ 4 GB on 32-bits, of course). I could do the same as I said earlier: I could create all the page tables matching the virtual addresses starting from the heap to the end of memory. If I don't do that, I will have to parse all the page directories to link in a new page-table when a new one is created in the kernel's directory (when I have to expand the heap, for example).

Note well that I've already considered fragmentation, etc, and have answered these privately; This is not an exhaustive overview of my MM. I wonder if that answers the heap question, Creature? As in, not having a fixed, or designated 'heap' area at all? and confining the userspace process's heap to its own area of the VAddress space? Certainly from what I've read, Windows and Linux do something at least slightly similar;

I understand your point about having lots of memory. If my heap was to start at a high address, it would be limited to the amount of virtual addresses available after that. So if there would be more memory than virtual addresses in the heap, a part of physical memory could be lost. Another solution would be to make the heap start straight after the (identity mapped) kernel region, and skip regions that should be protected in between (like where programs should be loaded in the process' VAS), which causes the problem that you can't always predict the size of the executable and the size must be fixed from compile time (because you basically have know way of knowing what the maximum size of an executable is that would maybe someday get loaded in your OS).

So you basically have a heap in every process (the PMM remains the same, but every process has a possibly different mapping for the same virtual address)? The only "possible" problem I could think of is that memory immediately allocated by the kernel (so it would not be linked in to the other process' page directories), can't be accessed by other processes, because the virtual addresses are different. This doesn't really seem to be a problem at first (I guess it's not a good idea to start new processes that are local to the kernel and access its variables anyway) and you seem to have a well thought design. I could then use threads if I needed to run multiple things at once inside the kernel.

Thanks for all your idea's, any other idea's are still welcome.

[Creature]

...

I have one question left about your design. Since you have small heaps for every process, I'm wondering about one thing: every process has its own address space. So if you want to create a new process, where do you allocate it? If you were to allocate it inside the current address space or heap, you would run into problems if some process gets deleted which created another process, because the other process will still exist, but there will be no way to access it in physical memory (unless you remap it). The most interesting thing to do is to allocate the process structures inside the kernel heap/address space, but that would require you to switch back to that address space every time you want to change processes or even threads. Stacks for these threads or processes would also have to be allocated in the kernel's heap, because if they would be inside the process' heap, the kernel wouldn't be able to find them without mapping them in its own address space or switching to that process' space.

This all seems very complicated, is it really this difficult to have decent multitasking? I was wrapping my head around to understanding the pushing/popping of the stack (which I think I understand now), but now problems are popping up in this regard, does anyone have any idea's/designs or examples they could show?

[Gigasoft]

He mentioned that his kernel has it's own part of virtual memory shared between all the processes' address spaces (like most OSes do it). This would be where process and thread structures are allocated. Therefore, no address space switches are needed to access these structures.

[Creature]

He mentioned that his kernel has it's own part of virtual memory shared between all the processes' address spaces (like most OSes do it). This would be where process and thread structures are allocated. Therefore, no address space switches are needed to access these structures.

I see. Then I guess I'm going to (for now) use a small area dedicated to only the processes and their threads. I think I might make some sort of mini-heap that takes care of that specific area. I might change that later I guess.

[gravaera]

Gigasoft answered it correctly: I, like many other kernels, have a whole 1GB of virtual address space in every process's address space. Windows uses 2GB, and nobody complains, so I figured 1GB couldn't be that bad

EDIT: On re-read, it seems like you're asking how to spawn new processes/new address spaces. The kernel itself, although limited to a 1GB address space, does have its own page directory, which is a full 4GB linear range. The only thing is that you adamantly keep it from extending down past the 3GB mark into the lower virtual addresses so that it can fit into any process's address space. But the kernel's page directory itself is still a page directory, even though 3GB of it are not being used.

You may comfortably switch to the kernel's actual address space and use the whole range of addresses in the lower 3GB to spawn a new process:

Switch to the kernel's actual address space, use a fixed offset and allocate a frame for at that offset. Start treating this frame which you are accessing through a virtual page in the kernel's address space as if it were a new page directory, and just copy the upper few Page directory entries from the kernel's page directory (768 - 1023) to the newly-being-spawned process's page directory which you are currently building.

You just finished mapping the kernel into the higher 3GB of the new process.

Now, assuming that before actually spawning the process's address space, you had already enumerated the number of bytes the process's executable image would need, and and parsed the ELF for the virtual load address, you just allocate frames for all those pages which would hold process image data.

However you do it, at this point, you need to switch into the actual process's address space (the one you just built) and load the executable file into the virtual address space. You had just mapped all the pages the process's executable image itself would need (plus any .BSS type section), so there should be no page faults while you copy the executable file into the virtual address space.

You now have a process which has an executable image loaded into its virtual address space, and a kernel mapped into its higher addresses. The process now needs its shared libs mapped in, and whatever form of StdIO you use, and a beginner ring 3 stack (I am told that processes in userspace are fully able to malloc a new stack and use that if they please), and a ring 0 stack for syscalls for the process, and you should be able to go from there.

Of course, you would have to account for concurrency, such as two different processes having to be spawned at the same time: this could be disastrous since two instances of the kernel mapping out pages in the same address space can lead to some very murky stuff.

Simplest solution: implement a lock at the very point where the kernel switches to its own address space to start creating a new process. That way only one process can actually be spawned at a time, and any other pending re-entrant attempts to spawn a process wait on the lock.

EDIT: I thought I should mention that in this reply, anything past the mapping in of the kernel into the new address space is pure theory for me, since I've never written or tested anything beyond that. I'm sure you'll receive some more hands-on advice from someone else.

--All the best
gravaera