My Memory Management

[Jeko]

I think I will implement this type of physical memory management:
Two stacks.
One covers 0 to 16MB and is used for DMA (but also for other tasks if the higher memory is occupied).
The other covers 16MB to all memory and is used for all tasks.

I don't know if is better to use a bitmap for DMA rather than a stack, because a bitmap can easily give contiguous pages.

Can you give me some advices about memory management? Is my idea good? What do you think about it?

Also another question, related to paging.
When I write a device driver such as a floppy driver and I use DMA, I must use physical memory for DMA or I can use directly virtual memory?

[AJ]

Hi,

Seems a reasonable approach - I have much the same idea with my frame allocator, except the split is not set at 16MB - it varies with the amount of total system RAM. For example, if you have a system with only 32MiB of RAM, my OS will only allow 2MiB for DMA. Also, if the upper memory stack is empty (in which case the paging mechanism has got something seriously wrong), it will then allocate the DMA RAM to the system.

And yes, DMA can only be used to access physical memory, not virtual.

Cheers,
Adam

[zaleschiemilgabriel]

IMO treating physical memory as a stack is not very useful, unless you plan to never deallocate memory.
Here's what I mean:
* You allocate 3 pages starting at a certain address (at the top of the stack)...
* You deallocate the middle page. What do you do in this case to mark the deallocated page as "not used"? With bitmaps you just set a bit in the corresponding page's position and you're done. With stacks you can only deallocate from the top of the stack, if I'm not mistaken...

[AJ]

To deallocate a page in the stack mechanism, you just push the page frame address on to the stack. You can deallocate in any order.

Cheers,
Adam

[Jeko]

IMO treating physical memory as a stack is not very useful, unless you plan to never deallocate memory.
Here's what I mean:
* You allocate 3 pages starting at a certain address (at the top of the stack)...
* You deallocate the middle page. What do you do in this case to mark the deallocated page as "not used"? With bitmaps you just set a bit in the corresponding page's position and you're done. With stacks you can only deallocate from the top of the stack, if I'm not mistaken...

no. my stack approach uses pop and push and they can be used with any page.
However this is my code to choose how many memory must I use for DMA (before I wrote that I use always 0 to 16MB, but it was for resume).

Code: Select all

//Note that phys_mem is of course a global variable.
unsigned int dma_memory_end = 16*1024*1024;

void dma_setup_memory_end()
{
	switch( phys_mem )
	{
		// From 15M to 23M of extended physical memory.
		case (15*1024*1024) ... (23*1024*1024):
			dma_memory_end = 8*1024*1024;
		break;

		// From 7M to 15M of extended physical memory.
		case (7*1024*1024) ... (15*1024*1024 - 1):
			dma_memory_end = 4*1024*1024;
		break;

		// From 3M to 7M of extended physical memory.
		case (3*1024*1024) ... (7*1024*1024 - 1):
			dma_memory_end = 2*1024*1024;
		break;

		// Less than 3M of extended memory is not enough...
		case 0 ... (3*1024*1024 - 1):
			dma_memory_end = 2*1024*1024;
		break;

		default:
			//Leave default value
		break;
	}
}

But, it's better a bitmap or a stack for DMA memory? I don't know, because sometimes DMA needs contiguous pages, so with a bitmap is faster and easier.

[zaleschiemilgabriel]

@AJ:
Sorry, but I don't really understand how that works...
Isn't it possible to just use the reserved bits in the Directory & Page table's entries to mark them as used/not used? If so, I don't see the point of implementing an extra bitmap or stack mechanism.

[AJ]

No - when all your pages are deallocated, where do you store them? Am right in thinking that you are using pure identity mapping? In this case, I can see why you are doing what you are doing. My approach to memory management is threefold:

1. A physical frame allocator. This is a stack which stores free page frame addresses. When you want a new physical page, call pmalloc() which will return the address of the next free page. To return a page to the stack, pfree(void*) does this.

2. A virtual heap manager - enough said!

3. The paging mechanism, which takes a virtual address and allocates a physical page to be paged in, making the virtual address valid. If a PFE happens and the faulting address is inside the valid heap, a page in function will be called. On paging out, the physical page frame is returned to the paging stack in 1.

Using your method, I would have to have a page directory and page tables created for the phole of physical memory to start with. Creating separate memory spaces for different processes would also be a headache. Using the stack / bitmap, you ensure that each page frame has been allocated only once.

@MarkOS:
Thats the sort of thing I do. Also, just because I do something like that does not necessarily mean it's a Good Idea (TM). It adds complexity, but if you want to execute your OS on a machine with low RAM, it just seemed to me to make sense. Whether or not you use this mechanism is entirely dependent on the design and goals of your OS.

In my OS, DMA is still in its early stages, but I have chosen to use a stack which has large pages (they allocate 64k at a time). If you want large contiguous ranges, stick with a bitmap. Again, it's really down to your OS design.

Cheers,
Adam

[zaleschiemilgabriel]

Using your method, I would have to have a page directory and page tables created for the phole of physical memory to start with.

Not really... If you want to check if a certain page is allocated, and it is not in the directory/page table, you already know it is not allocated (because it is not in there)... This is ptobably just another one of my non-conventional stupid ideas, but I bet it would work.

Creating separate memory spaces for different processes would also be a headache.

If you keep all your tables for all the processes in one place, assuming the kernel is the only one who handles them, which is true, it will always have everything it needs to determine the status of a physical page.

Using the stack / bitmap, you ensure that each page frame has been allocated only once.

IMO the bitmap / stack approach is more of a speed improvement. Using the tables directly, the way I describe, it would probably be pretty slow, but you'd be sure that there are no discrepancies between the bitmap/stack and the way the processor handles physical memory (hard to imagine any difference in handling physical memory if the bitmap/stack are kept in complete sync with the currently loaded tables, but still... if you're paranoid like me, you think about stuff going wrong... ).

[AJ]

I still don't quite understand. What if you want to run two processes in separate memory spaces and have both processes linked to run at 0x100000 (a fairly common requirement). How does your mechanism deal with that? Do you have separate PD's for each task space?

Cheers,
Adam

[zaleschiemilgabriel]

Do you have separate PD's for each task space?

Yes, the kernel would hold separate directory/page tables for each process and load them every time a context switch happens. As I said, it would be slow...
This is all theoretical, though. I haven't tried it myself, but I think it will be the way I will implement memory management. IMO it's the fastest (development-wise/most direct) way to implement a memory manager in asm.

[iammisc]

Yes, the kernel would hold separate directory/page tables for each process and load them every time a context switch happens. As I said, it would be slow...

most kernels switch page directories at every context switch. That's how you implement virtual memory.[/quote]

[zaleschiemilgabriel]

most kernels switch page directories at every context switch. That's how you implement virtual memory.

My point exactly! That means that the kernel already has everything it needs to manage memory inside those tables, and those tables will always be the most accurate way of figuring out the current state of the physical memory.
So an algorithm having the tables as the only input data instead of adding needless stack/bitmap structures as intermediaries would be much more convenient. At least that's how I see it. Anyway, I'm repeating myself so unless you have something useful to add please refrain from answering.

There I go being rude again, but pointing out the obvious or repeating the obvious I already pointed out (and removing the gist of it) does not count as a valid comment and reading it is a perfect waste of time for me.

Sorry for being rude...

[Brendan]

Hi,

most kernels switch page directories at every context switch. That's how you implement virtual memory.

My point exactly! That means that the kernel already has everything it needs to manage memory inside those tables, and those tables will always be the most accurate way of figuring out the current state of the physical memory.

You're right - those tables do contain enough information to manage physical RAM (but not other areas in the physical address space, like memory mapped PCI devices).

However...

Managing physical RAM by using the tables alone would be insanely slow - for something like finding a free phyiscal page of RAM you'd need to scan (potentially) thousands of page tables many many times (which is a severe problem for RAM chip bandwidth, cache thrashing and other reasons). The only way to speed it up would be to create some sort of temporary data structure.

However...

If you're going to construct a temporary data structure, why not keep the temporary data structure up-to-date and call it a permanent data structure (so you don't need to continually rebuild it)?

Now, what if this permanently up-to-date data structure was a bitmap, where each bit determines if a page is used or free?

Note: If you don't beleive me, post an algorithm that uses page directories and page tables to find a free physical page...


Cheers,

Brendan

[zaleschiemilgabriel]

I don't have an algorithm, and after you said, I don't think I ever will. It's mind boggling...