My memory manager

[Memmaker]

I?ve written a memory manager, but I dont know if it?s good enought (havent been reading a lot about the subject).

So this is the way I?m doing it:
I use a struct before every new allocated memory block:

Code: Select all

struct mem_block {
    byte available;   // free or not? 
    dword size;
    struct mem_block *next, *prev;
}

I got a pointer (when the kernel is launched it?s set to the beginning of the kernel memory), which I increase after allocating something.

When freeing a block, I set the *next, *prev pointers to the next/previous freed block(can be anywhere, it?s like a linked list). When I want to allocate something, I look through the linked list of freed blocks and try to find the "best fitting" block. If there?s no free fitting blocks available, I create a new block (at the address where the pointer I mentioned earlier points).
After the mem_block-information and the allocated data, I put the size again, so every block looks like:

available
size
next/prev
..DATA...
size

this makes it simple for me to reach the previous block from a block. Because I can reach the next/prev block (Not the next/prev Available block that are stored in the struct), it?s easy to merge freed blocks bordering on eachother.

Just wondered if it?s completly crazy done or what? This way I wont waste memory, and the allocation is fast (the only thing that takes time is to look through the linked list to find the best freed block).

[Dreamsmith]

Yes, that's not a bad implementation, if you want to keep it simple and aren't too concerned about speed. You could save four bytes by eliminating the size field (if you have a pointer to the next block, you don't need size, since you can calculate it by subtracting next from this -- if you have size, you don't need a next pointer, since you can find next by adding size to this, so, pick one or the other to eliminate -- I'd keep the pointer and loose the size field).

You can also eliminate the used/free flag by encoding pointers in a way that makes it possible to distinguish used from free blocks. Otherwise, that "byte" takes four more bytes per block (due to padding). In short, other than the fact that you're using 16 bytes of overhead per block when 8 will do the job, this isn't a bad plan for a malloc.

[Memmaker]

But the thing is, the *next,*prev are not pointers to the next/prev linear block in the memory, it?s a pointer to the next/prev FREE block of memory. So if the memory looks like this:

Block0 Block1 Block2 Block3
and Block1 is free, the next/prev pointers at Block1 does Not point to Block0/Block1, they point the the next FREE block (that could be anywhere in memory). So to get the next/prev linear block of memory, I need the size variables..or?

[Memmaker]

Cause I need to know the next/prev free block so I dont have to search through the entire memory to find a free block (with this linked list I only need to look through the available blocks).

I also need the size attributes to be able to find the next/prev block (so if I free a block, I can see if the one in front of it also is freed and then merge them). like

Block0 Block1 Block2 Block3 Block4

suppose block1 and block4 is free.. then the next-pointer at Block1 will point to block4. the prev pointer at block4 will point at block1. But when I did free Block1, I need to reach Block2 and Block0 to see if I can merge them (that?s why I need size)

[proxy]

memaker i agree that you need the next and size in order to properly create your linked list for free blocks. I dont think you need the available byte as you can just remove it from the list on allocation and reinsert on free. Also you dont need prev as a single linked list would work just fine. This is similar to my scheme and i use only singly linked.

proxy

[Memmaker]

Ah that?s right thank you.. but in general the method is good?

I thought of using about 100 different linked lists for the free blocks instead of only one, and chose list depending on the size of the freed block. Cause if I need to allocate e.g. 24 bytes, it?s unnecessary to look through the entire list. Instead one of the list only contains blocks whichi size is between 0 and 32. This will make the algorithm very fast if I make lots of allocating with different sizes.

[Memmaker]

and yes I need the available block. So I can check if bordering blocks are free and merge two blocks into one (OR I can sort the linked list and check if two blocks borders.

[Pype.Clicker]

i'm not sure "100" lists would be required... What i've used somewhere to speed up fitting is to have a separated list for each 'power-of-two' size (that is, one list with 16-31 free zones, one with 32-63, ... one with blocks between 8K and 16K, etc).

The difficulty of doing so is that when you'll need a 5K zone and find a 7K zone, the remaining 2K free zone must be moved out of the [4K..8K[ list and inserted in [2K..4K[ list.

This is not impossible, just a bit more complex to handle...

Once such a 'slicing' is performed, the necessity for a 'best fit' becomes less important as any zone within the list will have a similar 'reminder' portion ...

[Memmaker]

Thank you
One thing I thought of. In my linked list, suppose I dont have a prev-pointer. That means that when I want to remove (allocate) a block from the available list, I need to go through the entire list to find the item behind then one I?d like to remove. If I have a previous-pointer, it?s not neccesary. But a prev-pointer is 4 bytes large. Is it worth to "waste" 4 bytes for each block to gain the time iterating through the list?

[Pype.Clicker]

just a thought: as you're listing *free* blocks only, how many space you 'waste' is simply irrelevant: that's *free* space, not wasted one, even the space for the header!

The only thing it will affect is the smallest free zone you can keep track of: if your header is N bytes, no free zones smaller than N bytes can exist in the system (thus those bytes are 'unused' in an allocated region)

[Dreamsmith]

Indeed. I assumed the next and prev pointed to the next and prev blocks, whether they're free or not. I also maintain a linked list of free blocks for fast allocation (in fact my free is always O(1) and my malloc is optionally O(1)), but I store that list's pointers inside the free blocks themselves, not in the standard block header.

There are a number of different ways to do it, but you shouldn't need more than 8 bytes of overhead per block. Since my free blocks require an extra 8 bytes on top of that, my blocks take a minimum of 16 bytes (8 bytes header + a minimum of 8 bytes of userdata or 8 bytes of freelist data). If the app requests just a single byte of storage, it gets a pointer to 8 free bytes. Since it would have to get at least 4 in any case (due to alignment issues), it's really not a big deal, and only impacts extremely small allocations.

[Dreamsmith]

Perhaps it would be easier to illustrate than explain. Here's the first few lines of my malloc.c (after the #includes):

Code: Select all

typedef union MemoryBlock *BlockPtr;

typedef struct UsedBlock
{
   BlockPtr prev;
   BlockPtr next;
}
UsedBlock;

typedef struct FreeBlock
{
   BlockPtr next;
   BlockPtr prev;
   BlockPtr nextFree;
   BlockPtr prevFree;
}
FreeBlock;

typedef union MemoryBlock
{
   BlockPtr first;
   UsedBlock used;
   FreeBlock free;
}
MemoryBlock;

// Note: UsedBlock has prev first, FreeBlock has next first, thus we can
// guarentee that in the case of MemoryBlock x, if x.first > &x, it is a
// free block, otherwise it is a used block (if x.first == &x, it is a
// marker block, which should be considered used).

#define BSR(val) \
   ({ int result; asm("bsr %1,%0" : "=r"(result) : "r"(val)); result; })

...

next and prev refer to the next and previous block in memory in all cases. The free list is maintained using the extra space in free blocks. A simple comparison tells us if a block is used or free without requiring a seperate flag or any bit manipulation in the pointers. Using the structures above, free can be written O(1), and an additional structure can be used to track information allowing malloc to also be O(1), which I'll leave as an exercise to the reader (hint, it involves that BSR macro).

[proxy]

Thank you
One thing I thought of. In my linked list, suppose I dont have a prev-pointer. That means that when I want to remove (allocate) a block from the available list, I need to go through the entire list to find the item behind then one I?d like to remove. If I have a previous-pointer, it?s not neccesary. But a prev-pointer is 4 bytes large. Is it worth to "waste" 4 bytes for each block to gain the time iterating through the list?

you can update a singly linked list without a previous pointer in the same efficiency as a doubly linked list ya know. The trick it to use a pointer to a pointer when traversing (this also helps insertion at end too).

ex:

Code: Select all

node **ptr = &first;
while(*ptr != NULL) {
    // do somthing
    ptr = &ptr->next
}

when that terminate, suppose you wanted to insert at the end..well just do *ptr = new_node(....);

follow? same kinda thing can be done with general updating

[Memmaker]

Dreamsmith: Of course, it?s better to save the next/prev pointer inside the block and not in the header stupid of me that I didnt think of that


proxy:
Yes but suppose my linked list looks like this
Item1 -> Item2 -> Item3 -> Item4

and I want to remove Item3.. then I?ll have to set the next-pointer at Item2 = Item4. And I dont see how I can do this Without traversing the list(or having a previous pointer)? Cause I need to change Item2...

[Legend]

Different lists for different sizes, perhaps a tree would help here instead of some lists?