My memory manager
My memory manager
Ive started writin a memory manager for my little OS(using paging). I?ve made a stack with free pages. In another topic I read something like "When a program want more memory, deal out a free page. Use that page till it?s filled with data and then ask for a new page". But whats the best way for my malloc function to determine when a page is filled? I have to store the current page and all that somewhere, but where? in a static variabel in the malloc function? Should I just have a malloc function Something like this:
void *malloc(int size) {
static int usedMemory = 0;
static void *currentAdress = something;
if(usedMemory + size > SIZE_OF_A PAGE) {
// ask for more memory and move currentAdress
// set usedMemory = 0;
}
usedMemory += size;
currentAdress += size;
return (void *)(currentAdress - size);
}
void *malloc(int size) {
static int usedMemory = 0;
static void *currentAdress = something;
if(usedMemory + size > SIZE_OF_A PAGE) {
// ask for more memory and move currentAdress
// set usedMemory = 0;
}
usedMemory += size;
currentAdress += size;
return (void *)(currentAdress - size);
}
Re:My memory manager
Um, that's going to fail the first time I call malloc(5000). It's also a rather bizarre way of implementing malloc. But with regards to your question, yes, you do need to maintain some state information using a global or static variable. For an extremely simple malloc (with no way to free memory), you just need a free pointer and a "top of my address space" pointer. The free pointer is what will be returned by the next call to malloc. That call will increment the free pointer by the requested size (make sure you return the value before incrementing, not after). If the free pointer plus the requested size exceeds the "top of my address space" pointer, you need to request more memory (as many pages as necessary to fullfill the request). These pages must be added at the location the top pointer points to, and that pointer must be incremented past those pages.
char *freePointer; /* these must be initialized to sensible */
char *topPointer; /* values before the first malloc call */
void *simple_malloc(unsigned size)
{
void *result = (void *)freePointer;
while ( freePointer + size > topPointer )
{
addPage(topPointer);
topPointer += PAGESIZE;
}
freePointer += size;
return result;
}
If your OS implements a syscall to add more than one page at a time, you can replace the while loop with a single syscall and increment topPointer by the appropriate amount. If your OS doesn't let you map pages wherever you want them, you won't need to pass topPointer is a parameter.
And, obviously, this is not a real malloc. A real malloc keeps track of blocks allocated and can reuse freed memory...
char *freePointer; /* these must be initialized to sensible */
char *topPointer; /* values before the first malloc call */
void *simple_malloc(unsigned size)
{
void *result = (void *)freePointer;
while ( freePointer + size > topPointer )
{
addPage(topPointer);
topPointer += PAGESIZE;
}
freePointer += size;
return result;
}
If your OS implements a syscall to add more than one page at a time, you can replace the while loop with a single syscall and increment topPointer by the appropriate amount. If your OS doesn't let you map pages wherever you want them, you won't need to pass topPointer is a parameter.
And, obviously, this is not a real malloc. A real malloc keeps track of blocks allocated and can reuse freed memory...
Re:My memory manager
I see thenk you:)
Got another question. When handling memory in the kernel, I guess it?s good to have a page directory that does Not remap the memory(so that the logical address =
the physical). But I also need another modell for the kernel, with virtual memory? Cause suppose I want to allocate a big array, 10 000 bytes. I need to trick the kernel to believe that this 10 000 bytes are linear (of course), using a page dir. But should I only use this or should I also have another page dir where the logical address = the physicall (so I dont get confused when handling processes memory and so on)
Got another question. When handling memory in the kernel, I guess it?s good to have a page directory that does Not remap the memory(so that the logical address =
the physical). But I also need another modell for the kernel, with virtual memory? Cause suppose I want to allocate a big array, 10 000 bytes. I need to trick the kernel to believe that this 10 000 bytes are linear (of course), using a page dir. But should I only use this or should I also have another page dir where the logical address = the physicall (so I dont get confused when handling processes memory and so on)
Re:My memory manager
hmm realized that my explanation above wasnt that good.. what I meant was that you use virtual adresses for the kernel and processes, but linear unmapped memory when using the memory manager
Re:My memory manager
Actually, no, the memory manager doesn't need identity mapped memory. When you add a page of memory to someone's page table, you're just setting a pointer to the physical memory location. You don't need to actually access the page to allocate it, so it doesn't even have to be mapped into your page table at all, much less mapped at its physical location. The memory manager can use the same page table as the rest of the kernel, and it can be entirely virtual...
Re:My memory manager
But when I set a pointer to a physical location, this pointer Will be affected by the kernel page dir? Suppose I got a free page for a process, physical address 0xC000. Then I wanna add 0xC000 in the process?s page table. But in the Kernel, the adress 0xC000 may be remapped? or mabye that?s impossible(since the kernel will only remapp it if it has got it by allocating memory and then the page wouldnt be free however)..
Re:My memory manager
Brandon, you still seem to be severely confused by this memory thing, and stretching the issue across multiple threads doesn't really help, either...
I suggest you find the page that describes the inner workings of "dlmalloc()", aka Doug Lea's malloc(). To find that I'll leave as an exercise to you. That should shed some light on the situation.
I suggest you find the page that describes the inner workings of "dlmalloc()", aka Doug Lea's malloc(). To find that I'll leave as an exercise to you. That should shed some light on the situation.
Every good solution is obvious once you've found it.
Re:My memory manager
It could so. So? It doesn't matter one way or the other. You set the appropriate entry in the process's page table to point to 0xC000. Why do you CARE if it's even in the kernel's page table or not, and if it is, why would you care where the kernel has it mapped? All of these questions are irrelevant. The only thing you need to know the physical address of the page, and the logical address you want to map it to for the process. IT DOES NOT MATTER if it's mapped into kernel space at all, or at what address in kernel space it is.BrandonChris wrote:But in the Kernel, the adress 0xC000 may be remapped?
Re:My memory manager
One thing I thougt about.. right now I have a stack of free pages that I can allocate (Im talking about the kernel, not applications), like you (Dreamsmith) told me in the first answer. Then problem is, how should I be able to use free( )? Then there?ll be "holes" in the virtual memory (if I free a whole page and push it back on the stack). And mabye I just want to free a couple of bytes. What?s the best way of controlling this? (now all I got is a pointer to a virtual memorylocation which I increase when allocating memory). Thought I needed a more structed way of doing all this so I really can re-use freed mem
Re:My memory manager
free(p) can't free a page, it can only free the block of memory p points to, which is unlikely to be an exact page or pages. When you call free(p), that memory should be available for future calls to malloc(s). But the pages you receive from the OS belong to that process until it terminates. malloc needs to keep track of these freed blocks so it can use them to satisfy future malloc calls, but it never tries to return any memory to the OS.
It sounds like you're confusing the allocation and freeing of physical ram pages (which the OS handles) with the allocation and freeing of memory blocks (which the application handles, usually though malloc in the C library). These two issues are largely unrelated.
It sounds like you're confusing the allocation and freeing of physical ram pages (which the OS handles) with the allocation and freeing of memory blocks (which the application handles, usually though malloc in the C library). These two issues are largely unrelated.
Re:My memory manager
As Solar said as well, paging is entirely different from any free() or malloc() calls. Paging makes some memory be present, free() and malloc() make it marked for your use. You do not malloc() with paging, you only sbrk() (or morecore()) with paging. Malloc assumes an amount of memory X and allocates from that. At the end of that more can be added using sbrk(). You can add more memory anywhere using morecore() (but not in a place you specify, just any place). Then malloc is told about this memory, and it can then allocate more memory for you, from that space.BrandonChris wrote: One thing I thougt about.. right now I have a stack of free pages that I can allocate (Im talking about the kernel, not applications), like you (Dreamsmith) told me in the first answer. Then problem is, how should I be able to use free( )? Then there?ll be "holes" in the virtual memory (if I free a whole page and push it back on the stack). And mabye I just want to free a couple of bytes. What?s the best way of controlling this? (now all I got is a pointer to a virtual memorylocation which I increase when allocating memory). Thought I needed a more structed way of doing all this so I really can re-use freed mem
The short version, identical to Solar, "I suggest you find the page that describes the inner workings of "dlmalloc()", aka Doug Lea's malloc()."
Re:My memory manager
Again, check out dlmalloc()...
The general idea is:
You call malloc() to give you some RAM. malloc() keeps a limited-size internal pool of memory, which is already "paged" (i.e., allocated by the OS). If there's a chunk of memory in that pool large enough to satisfy your request, malloc() marks that chunk as "allocated", and returns a pointer to it.
If there isn't any large-enough chunk in malloc()'s memory pool, malloc() tells the OS it needs another page of memory. The OS does the page directory stuff, and passes the page to malloc()'s memory pool.
Now, what happens if you call free()? A common trick is for malloc() to add a "memory header" to the chunk of memory it passes you, at a negative offset. This "memory header" tells free() how large the chunk of memory actually is, so it can correctly return it to the memory pool.
And if the malloc()-memory-pool becomes too large, free() tells the OS that it can drop a certain page again.
----
One note: The Unixoid method of not actually assigning the memory upon request, but relying on the page-fault handler to page-in upon demand, has a serious drawback:
The C API assumes that malloc() either is successful, or returns NULL. In a Unix system, malloc() is virtually always successful (the page dir entry is created) - but when the page fault handler finds itself out of memory to page in, you have an "out of memory" situation that simply cannot be handled effectively. The page fault handler knows it happened but doesn't know how to handle it, and your application is clueless. The outcome is usually to unconditionally terminate your application...
Now, because developers are a lazy bunch and know how Unix handles memory allocation, it has become common practice to malloc() huge amounts of data that might never be actually used - so Unix OS developers can't even remedy the situation without making all such applications hopefully inefficient.
It's a mess I wouldn't want to allow in a newly designed OS...
The general idea is:
You call malloc() to give you some RAM. malloc() keeps a limited-size internal pool of memory, which is already "paged" (i.e., allocated by the OS). If there's a chunk of memory in that pool large enough to satisfy your request, malloc() marks that chunk as "allocated", and returns a pointer to it.
If there isn't any large-enough chunk in malloc()'s memory pool, malloc() tells the OS it needs another page of memory. The OS does the page directory stuff, and passes the page to malloc()'s memory pool.
Now, what happens if you call free()? A common trick is for malloc() to add a "memory header" to the chunk of memory it passes you, at a negative offset. This "memory header" tells free() how large the chunk of memory actually is, so it can correctly return it to the memory pool.
And if the malloc()-memory-pool becomes too large, free() tells the OS that it can drop a certain page again.
----
One note: The Unixoid method of not actually assigning the memory upon request, but relying on the page-fault handler to page-in upon demand, has a serious drawback:
The C API assumes that malloc() either is successful, or returns NULL. In a Unix system, malloc() is virtually always successful (the page dir entry is created) - but when the page fault handler finds itself out of memory to page in, you have an "out of memory" situation that simply cannot be handled effectively. The page fault handler knows it happened but doesn't know how to handle it, and your application is clueless. The outcome is usually to unconditionally terminate your application...
Now, because developers are a lazy bunch and know how Unix handles memory allocation, it has become common practice to malloc() huge amounts of data that might never be actually used - so Unix OS developers can't even remedy the situation without making all such applications hopefully inefficient.
It's a mess I wouldn't want to allow in a newly designed OS...
Every good solution is obvious once you've found it.
-
- Member
- Posts: 1600
- Joined: Wed Oct 18, 2006 11:59 am
- Location: Vienna/Austria
- Contact:
Re:My memory manager
Well, Solar is right here.
So, a way to handle the issue of growing out of memory is to check whether there are enough pages left to satisfy the actual request and then add the area to the tree of allocated virtual memory.
If there aren't enough pages left, just return the apropriate error code and have malloc sort it out - maybe return NULL and if the app is well coded, it recognizes this and bails out.
Of course this has several draw backs: what, if another process calls morecore immediately after the first one (because of preemption in a roundrobin queue): it would take the memory, the pager maps it in and there probably ain't enough memory pages left for the other process - concurrency issues everywhere. I've not yet done tests to sort it out correctly, but maybe keeping track of available vs. assigned phys pages might help: a kind of requested pages counter, hm? then the second process would get an appropriate notification about out of memory: either wait til memory is available(if using swapping) or quit.
And by the way: I wouldn't even go so far to create pagedir entries: that 's left for the pager to sort out. Just assign a virtual region in adress space as valid - enter it in the virtual adress space book keeping structure.
stay safe
So, a way to handle the issue of growing out of memory is to check whether there are enough pages left to satisfy the actual request and then add the area to the tree of allocated virtual memory.
If there aren't enough pages left, just return the apropriate error code and have malloc sort it out - maybe return NULL and if the app is well coded, it recognizes this and bails out.
Of course this has several draw backs: what, if another process calls morecore immediately after the first one (because of preemption in a roundrobin queue): it would take the memory, the pager maps it in and there probably ain't enough memory pages left for the other process - concurrency issues everywhere. I've not yet done tests to sort it out correctly, but maybe keeping track of available vs. assigned phys pages might help: a kind of requested pages counter, hm? then the second process would get an appropriate notification about out of memory: either wait til memory is available(if using swapping) or quit.
And by the way: I wouldn't even go so far to create pagedir entries: that 's left for the pager to sort out. Just assign a virtual region in adress space as valid - enter it in the virtual adress space book keeping structure.
stay safe
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image
BlueillusionOS iso image
Re:My memory manager
Guess I sounded a bit confused, sorry about that. I?ve thougt about storing some information before the allocated memory (e.g. the amount). The problem is. Suppose I use free()... then I can point to the adress, look behind it and see how much I should free.. that aint a problem. My real question was; whats the best way for malloc() to store what?s availabe? Cause I might have allocated lots and lots of memory and I free a little part of it in the middle. Next time using malloc, I want it to fill that gap. But How (datastructure) should malloc keep all this information? Thought of a linked list, but hey to create a linked list I need some memory aswell.. should I have special reserved memory for the malloc?s "I know where I can put data"-information?