memory manager design

[hanumant]

Hi
I have reached the part where i have to design a mmemory manager, but I need a few basic ideas cleared first. Now I have gone through Tim's memory designe tutorial (PART -1), where he's put down the framework, but there are a few things I dont understand.for eg dont we have to allocate memory , to keep track of all the available (physical) pages in memory?? . I understand you can get the size of the RAM. and from tehre determine number of pages, and then use something like a bitmap if you want , to track them. But that bitmap itself would need memory, even before we determine the RAM size, chicken and egg sort of.Anyways can somebody direct me to some alternative designs, I just want to study first before I go for one design.
Thank you

[AndrewAPrice]

Place it somewhere. A bitmap which covers 4Gb of memory (32-bit addressing) will take 1MB of memory. My kernel loads at the 2MB mark, and my memory allocator is hard coded to point to 3MB for the bitmap. Then I call reserve page (which marks a page as being used) and loop through all the pages from 2MB to 4MB. Then I allocate (i.e. scan and search for an unset bit) a page for the kernel memory allocator to start at.

[JamesM]

That is the major issue in bootstrapping a memory manager, and it really is implementation specific. My kernel, for example, uses C++ and uses placement new until the heap is up and running. For example:

Code: Select all

// assume that placement_addr is a variable set to the first available location in memory.

u32int operator new[](u32int size, u32int &location)
{
  u32int tmp = location;
  location += size;
  return tmp;
}

// in memory manager bootstrap code
// initialise page bitmaps etc
myPageBitmap = new(placement_addr) Bitmap[mem_size];

Then, when I've set my heap up, I can just revert to using standard new, which is defined as:

Code: Select all

u32int operator new(u32int size)
{
  return memoryManager.malloc(size);
}

Hope this gives you some ideas. I wrote a C kernel before this one, but like you I came across this problem and adopted a temporary (which became permanent) solution - statically allocate bitmap room in the program .data segment. Obviously this relied on knowing the memory size beforehand, so I put that in at compile time. I DO NOT recommend following this, it is *crap* and was meant to be fixed but since I had built an entire kernel on top of it by the time I got round to it, I couldn't

JamesM

[SpooK]

Place it somewhere. A bitmap which covers 4Gb of memory (32-bit addressing) will take 1MB of memory.

Why so much

2^32 (4GB) / 4096 (Page Size) does indeed equal 1MB, but that would be considered a bytemap.

Bring it down to an actual bitmap level and you will have a nice and lean 128KB physical bitmap for every 4GB of RAM

A bytemap is indeed easier to implement but is less efficient, so I guess it is upto you

[os64dev]

a main advantage of a byte map is that you have an aditional 7 bits for information regarding that page and that it is fater to access bytes then bits. The downside is indeed the memory usage but the 1 MB is only if you have 4GiB installed but if you would make a bitmap for 2 Gib its only 512 KB and that is 1/4096 = 0,02 % percent of the total memory. Its all a trade-off between memory usage and performance.

[SpooK]

a main advantage of a byte map is that you have an aditional 7 bits for information regarding that page and that it is fater to access bytes then bits. The downside is indeed the memory usage but the 1 MB is only if you have 4GiB installed but if you would make a bitmap for 2 Gib its only 512 KB and that is 1/4096 = 0,02 % percent of the total memory. Its all a trade-off between memory usage and performance.

The only advantage I see is the extra information bits, but using that to keep track of physical memory seems like overkill. Good plan for virtual memory management, however.

Scanning bytes only seems faster if you are using poor bitmap scanning methods. Remember that scanning 1MB involves more iterations, cache misses and what-not.

Instead you can setup a 256 byte map representing return values and use it with XLATB (5 clocks). You can also add a couple more byte maps representing return values of a different size (4, 8, 16 KB) while an entire byte would be 32KB and a DWORD would represent 128KB.

[Candy]

a main advantage of a byte map is that you have an aditional 7 bits for information regarding that page and that it is fater to access bytes then bits. The downside is indeed the memory usage but the 1 MB is only if you have 4GiB installed but if you would make a bitmap for 2 Gib its only 512 KB and that is 1/4096 = 0,02 % percent of the total memory. Its all a trade-off between memory usage and performance.

For comparison, my OS uses 128 bits per page frame of memory. This contains a pointer to the previous page of the same type (40 bits), a pointer to the next page of the same type (another 40 bits), the virtual address it is mapped to (20 bits), the PID it belongs to (16 bits) and the state of the page (4 bits). I'm trying to get the virtual address stretched up for AMD64...

Bitmaps are ok for allocation and freeing.

[hanumant]

How does teh stack based allocation actually work, I mean u declare an array of 32 bit values to hold addresses??? and considerng , there are 1 MB pages , thats a huge stack. I know this seems a very dumb implementation , but how else would u create a stack, other then reserving the gigantic space?

[SpooK]

How does teh stack based allocation actually work, I mean u declare an array of 32 bit values to hold addresses??? and considerng , there are 1 MB pages , thats a huge stack. I know this seems a very dumb implementation , but how else would u create a stack, other then reserving the gigantic space?

Mix bitmaps and stacks. Either on demand, or in a background process, keep a sensibly-sized stack filled by scanning the bitmap for free pages... which will keep allocations reasonable quick without sacrificing too much.

You could easily use less than 1MB for 4GB of RAM with this method