malloc implementation

[alexyz]

I every one, i'm implementing a OS, my goal it's to create a very well commented kernel so it's easy for every one to read it, and hopefully help anyone whose trying to learn operating system development. meanwhile i've implemented a malloc from scratch.
For now it only have malloc() and free(), but because i'm new at this. I'm putting the file here so if anyone could look at it and give me some feed back
The code is full commented and it's working, i've test and it seems quick , but hey i'm not the best person to analize it.
I'll not explain here the algorithm because the comments in the code can easily explain that.

it have been compiled in gcc.

again, i would appreciate some feedback and some sugestions because it's my first malloc()

thx

[Crazed123]

Move this to the OS development board.

Somehow, I don't think code attachments really count as matters of OS design or theory.

[alexyz]

Move this to the OS development board.

Somehow, I don't think code attachments really count as matters of OS design or theory.

Ok, sorry i think you are right i moving it, thx

[alexyz]

moved into http://www.osdev.org/phpBB2/viewtopic.p ... 078#108078

[Candy]

moved into http://www.osdev.org/phpBB2/viewtopic.p ... 078#108078

Is it OK if we (the moderators) do the moving?

[JamesM]

Hi,

First of all, very well commented and laid out code. Makes it very easy to read. Thanks (I should point out that had it not been I wouldn't have read it)

Seems good, a few points though, in no particular order:

1)

Code: Select all

#define BLOCK_HEADER struct mm_blk_header
BLOCK_HEADER
{
	int          free;
	int          size;
	BLOCK_HEADER *next_blk;
	BLOCK_HEADER *prev_blk;
};

It's general practice to use typedef in this situation. It makes it a lot easier to understand than a preprocessor command, e.g.:

Code: Select all

typedef struct block_header
{
  int free
  int size;
  struct block_header *next_blk;
  struct block_header *prev_blk;
} block_header_t;

2) I assume this implementation is not written for your own OS? I'm confused by the #include <stdio.h>, <stdlib.h> stuff...

3)

Code: Select all

/* it's time to return address of this allocated block */
        goto return_address;

Spaghetti code alert! avoid goto like the PLAGUE wherever possible

4) Consider the following worst-case scenario:

Code: Select all

for(int i = 1; i < 0xFFFFFF; i++)
{
  kfree(kmalloc(i));
}

How would your heap manage this? As far as looking at the code can tell me, you would allocate a different linked-list structure for each allocation, because although they all get freed, the next allocation will always be bigger than the last. I.e. your algorithm doesn't reclaim and amalgamate space back into bigger holes. [EDIT] and thus would eventually run out of memory.

JamesM

[alexyz]

thx a lot, for the feedback, it really helps a lot when other ppl give us suggestions and recommendations.

2) I assume this implementation is not written for your own OS? I'm confused by the #include <stdio.h>, <stdlib.h> stuff...

you're right, a don't really need them, but at first i was only using this malloc inside my OS in bochs, so i really couldn't test the performance. ( my OS isn't ready for me to boot in a real hardware ).
i've google "malloc tester", and get some file called "mallocer.c" which was a simple code to test malloc speed, that's why those headers are included.

4) Consider the following worst-case scenario:

Code: Select all

for(int i = 1; i < 0xFFFFFF; i++)
{
  kfree(kmalloc(i));
}

How would your heap manage this? As far as looking at the code can tell me, you would allocate a different linked-list structure for each allocation, because although they all get freed, the next allocation will always be bigger than the last. I.e. your algorithm doesn't reclaim and amalgamate space back into bigger holes. [EDIT] and thus would eventually run out of memory.

JamesM

hmm..very good question, i've questioned myself about this too, and i'm having a few ideas how to handle it. so far this is what i've thought.

my allocator allways align size, for instance, if i need 11 bytes, it will allocate a block of 16 bytes, if 12, again 16, if i need 21 it will be 32, and so on (they are always powers of 2), so with your suggested test code it will create 24 linked lists and thats a lot :p

I was thinking of this structure:

Code: Select all

typedef struct block_header
{
  int free
  int size;
  struct block_header *next_blk;  /* this are used for linking in the free list */
  struct block_header *prev_blk;  /* same */
  struct block_header *next;      /* this will never change is the "real " physical neighbors */
  struct block_header *prev;     /* same */          
} block_header_t;

This could make possible for me to check if the neighbors were free, and join them.

But i'm thinking of a way to test this quick and not do this test every time we free or alloc other block, i think it will overhead the code.

again, thx for the suggestions, it really helps a lot.

[alexyz]

moved into http://www.osdev.org/phpBB2/viewtopic.p ... 078#108078

Is it OK if we (the moderators) do the moving?

oops, sorry it will not happen again

[JamesM]

thx a lot, for the feedback, it really helps a lot when other ppl give us suggestions and recommendations.

2) I assume this implementation is not written for your own OS? I'm confused by the #include <stdio.h>, <stdlib.h> stuff...

you're right, a don't really need them, but at first i was only using this malloc inside my OS in bochs, so i really couldn't test the performance. ( my OS isn't ready for me to boot in a real hardware ).
i've google "malloc tester", and get some file called "mallocer.c" which was a simple code to test malloc speed, that's why those headers are included.

4) Consider the following worst-case scenario:

Code: Select all

for(int i = 1; i < 0xFFFFFF; i++)
{
  kfree(kmalloc(i));
}

How would your heap manage this? As far as looking at the code can tell me, you would allocate a different linked-list structure for each allocation, because although they all get freed, the next allocation will always be bigger than the last. I.e. your algorithm doesn't reclaim and amalgamate space back into bigger holes. [EDIT] and thus would eventually run out of memory.

JamesM

hmm..very good question, i've questioned myself about this too, and i'm having a few ideas how to handle it. so far this is what i've thought.

my allocator allways align size, for instance, if i need 11 bytes, it will allocate a block of 16 bytes, if 12, again 16, if i need 21 it will be 32, and so on (they are always powers of 2), so with your suggested test code it will create 24 linked lists and thats a lot :p

I was thinking of this structure:

Code: Select all

typedef struct block_header
{
  int free
  int size;
  struct block_header *next_blk;  /* this are used for linking in the free list */
  struct block_header *prev_blk;  /* same */
  struct block_header *next;      /* this will never change is the "real " physical neighbors */
  struct block_header *prev;     /* same */          
} block_header_t;

This could make possible for me to check if the neighbors were free, and join them.

But i'm thinking of a way to test this quick and not do this test every time we free or alloc other block, i think it will overhead the code.

again, thx for the suggestions, it really helps a lot.

If your allocator always aligns sizes, won't that waste a lot of space?

For example, if I knew I had, say, 1500 bytes of memory to play with before segfaulting, (picking a random number out of the air), I could write this:

Code: Select all

void *ptra = kmalloc(514);
void *ptrb = kmalloc(514);

I (as a developer) would assume that 1500-(514*2)=476 bytes overhead for two allocations is more than enough, and those two allocations would succeed. However, your implementation would create two linked list structures each of size 1024 bytes (as that is the nearest power of 2, thus the second allocation would fail.

Again, a hypothetical scenario, but it could happen.

If you are going to force sizes to be powers of 2, i suggest you look at the [url="http://en.wikipedia.org/wiki/Buddy_memory_allocation"]Buddy allocation algorithm[/url] which is tried and tested.

An alternative is doug lea's malloc (which is implemented in glibc), a simplification of which I use in my own kernel.

JamesM