Page 1 of 1
Linked Lists in Memory Manager?
Posted: Thu Apr 05, 2007 8:59 pm
by pcmattman
As I posted earlier I ran into a smallish problem that wouldn't let my OS boot - the fact that my memory manager ran off an array with 20,000,000 elements in it (ie. 20MB of allocateable memory). Problem with that was, it was slow and used up a LOT of memory.
The question I have is, how do you use linked lists in a memory manager if you have no 'malloc' available becuase that's what you're writing?
Posted: Thu Apr 05, 2007 9:39 pm
by mystran
Typically, you have a "heap" which starts at some known address, and which can be grown by calling a function like morecore(), sbrk()/brk() something else like that. The purpose of malloc then is to manage this area.
When your malloc doesn't have any free space, it'll want to call morecore() to move the endpoint of the heap futher, usually in relatively large steps, effectively allocating memory, so your lower-level memory manager can map more pages for you. This way you don't need to know in advance how much space you need.
Typically, when malloc gets a block (if it doesn't merge it with another free block at the end of the old area), it splits the block into a smaller piece to satisfy the requested allocation, and keeps the other piece as a free block. Since it will later in free() have to figure out what size of block it was, the easiest thing to do is to store the size of the block in the beginning of the block, and return a pointer just after the size-field. That way free will only have to move backwards from the pointer it got, and see how big a block it is.
Often you'd actually store a bit more info between the "user-visible" blocks. If you store not only the size of the following block, but also the preceding block, you can move both forward and backwards between the blocks, by reading the size fields, which makes it pretty easy to merge free blocks, for which you then store one bit worth information to indicate whether a given block is free or used (I used negative size for used blocks, but you could also rely on aligning the blocks and store the used/free-bit in the lowest bits of the size). Extra advantage of storing both next and previous block's size, is that you can detect some heap corruptions (from buffer overflows) in free() by checking that the size that's stored before and the one stored after the block to be free'd actually match. If they don't, you probably want to panic.
This is actually how my current malloc works. It's inefficient though, because I have to follow the chain of all blocks in order to find free blocks. But if you make sure that any block is at least 8 bytes long (on 32-bit architecture, and you probably want 8 byte alignment as well), you can take advantage of the fact that if a block is free, you have at least 8-bytes extra space in the block for stuff like two-pointers to build a doubly-linked. This is what I plan to do as soon as I feel like it's worth the trouble.
Other potential optimization then, for the above scheme, is to keep different free-lists for different block sizes, so that if you are searching for certain size of block, you can skip all the blocks that are too small anyway, and avoid splitting large blocks if there's a more suitably sized block free. The description of dlmalloc discusses some possibilities.
The theoretical size overhead for the scheme described above is 8-bytes per block-allocated, plus whatever you waste with fragmentation (which depends on allocation patterns). Note that it is very hard to beat this overhead with a general purpose malloc, so if you are worried about it, you probably want a separate, special purpose allocator for the really small blocks (for which the relative overhead would be large).
There are other variations for the same idea, but in most cases, you need the size of the block somewhere, so you store it just before the address you return, and if a block has a minimum size, you have at least that much extra space to use when the block is free. Since you don't need free-list for used-blocks, you avoid making the header (that's before the block) unnecessarily large.
Posted: Thu Apr 05, 2007 9:51 pm
by Kevin McGuire
As I posted earlier I ran into a smallish problem that wouldn't let my OS boot - the fact that my memory manager ran off an array with 20,000,000 elements in it (ie. 20MB of allocateable memory). Problem with that was, it was slow and used up a LOT of memory.
20MB seems like a lot.. You know there should be 0xFFFFF (4096 byte) pages in the system. So
(0xFFFFF * 4 = 4194300 bytes). If you stored each page address with four bytes. How did you get 20MB?
The question I have is, how do you use linked lists in a memory manager if you have no 'malloc' available becuase that's what you're writing?
You can store the linked list as pages.
Code: Select all
unsigned int global_variable_the_current_linked_list_page;
unsigned int global_variable_the_index_in_the_current_page;
struct tFreePageStack{
unsigned int previous;
unsigned int stack[1022];
unsigned int next;
};
Just use a whole page as one linked list item able to store one-thousand-and-twenty-two free pages or what not.
Posted: Thu Apr 05, 2007 9:59 pm
by pcmattman
Well, for a start I don't use paging.
Secondly, 20MB came from nowhere, I just randomly picked it.
The memory block array:
Code: Select all
// heap storage - approx. 20MB in 1B blocks
struct mBlock heap[20971520];
Memory block structure:
Code: Select all
// memory block structure
typedef struct mBlock {
unsigned int stat; // status - FREE or USED
unsigned int bottom; // bottom of the block
unsigned int top; // top of the block
unsigned int id; // id of the block
unsigned int count; // the number of blocks this one takes up
} mBlock;
IIRC an unsigned int is 4 bytes... 4 * 5 = 20... 20 * 20971520 = an insanely large number - my problem lies here...
Posted: Thu Apr 05, 2007 10:32 pm
by Kevin McGuire
Oh. I see what you are trying to do.
As you boot the system just tell it
m4096(aPage, theCount). Then it will automatically allocate space for it's self while pushing free memory into the stack. You could generally get away with using this for a little while?
Code: Select all
struct tPageHelper4096{
unsigned int next;
unsigned int stack[1022];
unsigned int prev;
};
unsigned int g_ph4096i = 0;
struct tPageHelper4096 *g_ph4096 = (struct tPageHelper4096*)0xFFFFFFFF;
void m4096push(unsigned int page, unsigned int count){
if(g_ph4096 == (struct tPageHelper4096*)0xFFFFFFFF){
g_ph4096 = (struct tPageHelper4096*)page;
for(x = 0; x < 1022; ++x){
g_ph4096->stack[x] = 0;
}
g_ph4096->next = 0;
g_ph4096->prev = 0;
g_ph4096i = 0;
}
for(y = 0; y < count; ++x){
if(g_ph4096i > 1021){
g_ph4096->next = (struct tPageHelper4096*)( page + ( y * 4096 ) );
((struct tPageHelper4096*)(page + ( y * 4096 ))->prev = g_ph4096;
g_ph4096 = (struct tPageHelper4096*)(page + ( y * 4096 ));
for(x = 0; x < 1022; ++x){
g_ph4096->stack[x] = 0;
}
g_ph4096->next = 0;
g_ph4096i = 0;
}else{
g_ph4096->stack[g_ph4096i] = page + ( y * 4096 );
}
}
return;
}
Or you could do a bitmap?
I use a bitmap, and I like it. Even if you do not use paging you still should find a performance gain in breaking memory into chunks and then going even smaller for the heap.
http://www.osdev.org/wiki/Quick_And_Dir ... ace_Scheme
The first part will show how to make a simple physical page manager. You could just ignore the second part and stuff relating to the second part.
http://www.osdev.org/wiki/Quick_And_Dir ... _Algorithm
This is a heap tutorial, but beware the functions have a bug where it does not advance enough.
Here is some heap code. It has no free function written. It has been tested.
Code: Select all
typedef unsigned int u32;
typedef unsigned char u8;
typedef unsigned short u16;
typedef signed int i32;
typedef signed short i16;
typedef signed char i8;
struct tkheap{
u8 flags;
u16 size;
};
struct tkheap *g_kheap = 0;
u32 g_kheap_size = 0;
void kheap_init(unsigned int address, unsigned int size){
g_kheap = (struct tkheap*)address;
g_kheap->flags = 0;
g_kheap->size = size - sizeof(struct tkheap);
g_kheap_size = size;
return;
}
void* kheap_alloc(unsigned int size){
struct tkheap *ch, *nh;
for(ch = g_kheap; (unsigned int)ch < ((unsigned int)g_kheap + g_kheap_size); ch = (struct tkheap*)((unsigned int)ch + ch->size + sizeof(struct tkheap))){
if(ch->flags == 0){
if(ch->size == size){
ch->flags = 1;
return (void*)((unsigned int)ch + sizeof(struct tkheap));
}
if(ch->size > size){
if((ch->size - sizeof(struct tkheap)) > (size+10)){
nh = (struct tkheap*)((unsigned int)ch + size + sizeof(struct tkheap));
nh->size = ch->size - size - sizeof(struct tkheap);
nh->flags = 0;
ch->size = size;
}else{
ch->size = ch->size;
}
ch->flags = 1;
return (void*)((unsigned int)ch + sizeof(struct tkheap));
}
}
}
/// FIXME: Lock thread here, and print warning message to console to get attention.
u32 x;
for(x = 0; x < 10; ++x){
console_write("WARNING: HEAP ALLOCATION FAILED!!\x10");
}
/// FIXME: Thread locked here.
for(;;);
return 0;
}
/// FIXME: implement these functions..
void kheap_reclaim(void);
void kheap__free(void *ptr);
void kheap_free(void *ptr);
You could most likely expand it cover a larger data area. It is the same implementation as in the heap tutorial but has the oops fixed.
Posted: Thu Apr 05, 2007 10:33 pm
by mystran
Well, if you don't use paging, you then want to take the memory map, and instead of using it as a map of physical frames to using for paging, you use it to give your malloc morecore().
With or without paging, try to understand my first post.
Dlmalloc page has some graphics about the basic idea, and describes the idea pretty well, though it includes all the complications that dlmalloc adds in order to give better performance.
Theoretically you could also look for some classic malloc descriptions, but the basic structure of dlmalloc is pretty simple, and can be made to perform very well.