Memory Management Methods

[TylerH]

I'm really having trouble getting an idea I like for this one.

I've come up with a few ideas, but none are as intuitive as I'd like. So far, my head has been wrapped around the bitmap method of allocating. I'll have one for pages(in other words, page aligned/page sized blocks of physical memory), but how do I manage memory allocation within the individual pages when I get a malloc() call? I can't create a whole new page for every allocation of only a few bytes.

My only solution so far, to per process byte size allocation, is to dedicate X(how ever many is needed on a process by process basis) amount of pages per process to manage the memory of the pages within that processes domain on a byte by byte level. On both levels(page and byte sized) there would be a pool of pointers to the specific location allocated and it's size(in either pages or bytes), this would allow for free() to work since this method provides a way to keep track of the entire block of allocated memory.

My main problem is that this method, other than being exceptionally crude, would use roughly a ninth of memory(all bytes allocated by bits, that's one byte for every 8 bytes, plus the page allocation structure) just for memory allocation, which is unacceptable in my opinion.

I'm by no means asking anyone to write my memory manager for me, I'm only asking for ideas. I don't like mine, and would greatly appreciate any input from the forum. To give you an idea of the direction I'd like to head, I'd like to have an allocator that operates off of a more pointer based allocation structure, rather than using bitmaps and other simple data structures. I'd also like to hear what you have to say about my above aforementioned theory, should I just use it?

[montrom]

This may be a bit crude, but I would suggest this. You need five things for this:

1. pmem allocator (i.e. page * 0x1000)
2. pmem freer using your bitmap
3. malloc uses pmem allocator
4. free goes with malloc is basically pmem freer
5. struct to hold information. (e.g. current address, length, offset)

Then in your malloc function have it check the struct for its length and compare it to the length of your page (4KB), then allocate to that page until its full, update the struct and request more pages as needed. Free what is not needed when you're done with it. More could be added to this but this is my most basic idea.

[gerryg400]

I wonder whether you have read the Gorman book. It is a very practical description of the Linux memory manager. It is a little out of date wrt the current kernel but I wholly recommend it. It will teach you about slab and buddy allocators as well as how you can handle physical memory. The Linux implementations of these things are, I feel, a little overcomplicated, but the ideas are sound. For me the biggest thing was to understand how to get started.

http://ptgmedia.pearsoncmg.com/images/0 ... n_book.pdf

- gerryg400

[gerryg400]

. So far, my head has been wrapped around the bitmap method of allocating. I'll have one for pages....

I started with a bit to represent each physical page but soon found that more information about a page is required. Currently I have 32 bytes (0.78% of memory) to represent each page. That enough to keep a double linked list, a reverse lookup address and some status info (how the pages is currently used). I just put the little structure of each free page in a freelist.

My only solution so far, to per process byte size allocation, is to dedicate X(how ever many is needed on a process by process basis) amount of pages per process to manage the memory of the pages within that processes domain on a byte by byte level.

To some degree, processes manage their own memory. Many unixy type programs allocate system memory with a variation of brk. This requires only a small amount of work in the kernel. mmap is a little more difficult but the cool thing is that the app is making the decisions. The kernel just needs to make sure the requests are sound, implement them and track the results.

For the core of the kernel, I really recommend you study the slab and buddy allocators. They are very lightweight, easy to implement and debug and more-or-less invented for kernel use. You'll probably want both.

- gerryg400

[TylerH]

To some degree, processes manage their own memory. Many unixy type programs allocate system memory with a variation of brk. This requires only a small amount of work in the kernel. mmap is a little more difficult but the cool thing is that the app is making the decisions. The kernel just needs to make sure the requests are sound, implement them and track the results.

To what extent do I need to manage app memory resources? Ideally, I'd like to be able to completely separate the kernel memory allocator from individual processes, making a memory management lib instead. Having the kernel manage whole pages only, and having the lib manage on a process scale.

A prerequisite to being able to allocate on a per-process basis without having direct access to process managment is being able to tell who you're being called by. Is it possible to tell what process is calling(w/ or w/o a call to the kernel, I just want to know if it's possible)?

[gerryg400]

To what extent do I need to manage app memory resources? Ideally, I'd like to be able to completely separate the kernel memory allocator from individual processes, making a memory management lib instead. Having the kernel manage whole pages only, and having the lib manage on a process scale.

That's quite achievable. Think about it from the process point of view. Most processes call malloc when they allocate memory. This is done entirely within the process on the process heap and is part of the c library.

When the heap runs out the c library asks the kernel for more memory with brk. All the kernel has to do is add some more pages onto the process address space (thus extending the heap so malloc has more mem to play with) and remember the new brk value. It's actually very simple.

Complications arise when you want your kernel to support all the posix mmap semantics, but this may not be necessary in a simple kernel. That's up to you.

[TylerH]

At what level should I keep track of all the impotant info, virtual or physical level? For example, do I find out who the requesting process is when allocating the physical memory for the page, or when adding a page to the page dir?

[gerryg400]

In a simple OS you only need to keep track of the virtual memory of each process.

For this reason in a simple OS the only information you need to store about a physical page is whether it is used or not. You only need a bitmap for this. At some point if you want to implement swapping, reverse lookup, shared mem, mmap, etc. you will need a structure for each physical page to keep track of it's owner(s), permisions, last time used, mappings etc.

[gravaera]

Hi:

It may be useful to note that a simple BMP can in fact be maintained while implementing swap, etc.

The extension of the metadata on frames comes when you delegate the responsibility of swapping frames in and out of external storage to the physical memory manager. If you have a design which causes the PMM to negotiate the swap access on physical memory allocation fail, and thus cause the calling process to block until the PMM returns a frame, or a definitive 'NO_PHYSICAL_MEM' status after trying its best (including trying to swap out candidate frames and failing), then it would be important for the PMM to know of course, how the frames in RAM are used, and to maintain information on which frames are the best candidates for swapping out.

Thus you end up with something like the Linux struct mem_map_t/page, where the PMM is given, and maintains, info on frames.

If however, you do swapping within processes, where the process can only swap out its own frames, (and therefore not frames from any other process), then you can implement swapping simply by keeping that page usage information on a per process basis. Note that now you keep usage information on a page (virtual) level, and not a frame (physical) level. Thus, the responsibility of getting frames for a process falls on the calling process.

Process A makes an allocation call, and there is enough virtual memory in its address space to satisfy the allocation. The kernel moves on to try to back the virtual range with as much physical memory as it can, and then map the rest of the range as 'fake-mapped' pages, which have no physical memory backing. These fake mapped pages will generate a fault, and the kernel can read the faulting address to know what needs to be done with the page.

Enter the aforementioned fault. The kernel has used the not-present page's free bits to store a flag field, and reads the faulting address, and sees that this is indeed a valid memory address for the process to access; it's just that the kernel didn't back it with physical memory. From here, you make a call to the PMM. If the PMM fails to return memory (even after flushing the kernel heap for free pages, and the page table caches used for fast page table allocations, etc), it returns a 'NO_PHYSICAL_MEM' status.

The VMM now, running on the current CPU, and running re-entrant-ly (?) on that CPU, will seek to scan the information on the process's address space, and see which page ranges are viable for swapping out. You then swap out each fit page, and return its physical address to the faulting address or address range. The swap has been done entirely within the current address space.

There are several advantages here: The PMM is not locked off while it runs through an algorithm to (inaccurately, most likely) determine which physical frame seems best to swap out, then blocked some more while it calls on the file system code to swap out the frame, which will also take a demand map of the frame, a read of each frame to be swapped out, and then a write to disk. Using the non-PMM oriented approach, the PMM is completely free to take other allocation requests, and more importantly, to take free() requests, so that later allocations would have a higher chance of getting physical memory. The duty to get physical memory (or more accurately, to determine which pages to swap out via whatever algorithm), and the blocking on the disk access to swap it out is also delegated to the calling process, and if designed well, can also be pre-emptible.

Shared pages only require a count of the its users, really. All in all, it's just design. But your simple bitmap can remain, though.

--Hope that was helpful,
gravaera

[gerryg400]

Gravaera,
But what about if there is a long-lived process that is consuming lots of physical memory with mmaped files etc. Like a database server. How does the system force that process to release some of its physical memory ? Don't you need some sort of global accounting to check whether the pages it is using should be considered for eviction ? During periods when the database is heavily used, the entire database may be mmaped in. Later on, how would the database server know that it should evict pages and start freeing physical memory ?

[gravaera]

Hi:

Sorry for the latency; Well, technically a database server running up on memory usage is going to need most of the memory that it allocates. And most of the time, a database server is set aside as a single purpose functional unit: at least for serious use, that is. Expunging memory from a DB server is pretty much a gamble and an invitation to proliferate thrashing.

I suppose in the end each method has its merits. The PMM based page swapper can more easily gain physical memory, and the VMM based page swapper is easier to implement in a scalable manner.

--All the best,
gravaera