Malloc

[salil_bhagurkar]

Hi can anybody suggest me where i can find code for malloc/kmalloc? I need to write one in mm of my os. Till now i had a stupid one that never frees but now i need a better one... Kindly suggest resources...

[Solar]

dlmalloc is probably the best starting point you will find.

[Kevin McGuire]

Just make a block.. [block: size(x)]. Then split it when allocating, and create another block as the end of the allocated size. Set bit 31 in the allocated block to show it is used. Set the next block to contained the left over amount of heap from the first block. Continue doing this. When you free it just set the bit 31 to zero. The allocator might be able to use it again.. maybe not it will just search on.

You might make the allocator try to reclaim on a first failure.. Then try again and if it fails just exit with null.

All I am doing is searching blocks, each with their data size in the header. I increment to the next block by sizeof(struct tblock) for the header and adding the tblock->size to the header size. Then I check it.

When found I split the block into two parts..

Code: Select all

[free space block                                 ]=100 bytes
[used space block      ][free space block]=100 bytes
 ^^ 48 bytes                  ^^^  52 bytes =100 bytes

I placed the free space block at the end of the original free space block.

Code: Select all

It could like this after a little while...
[free][used][free][used][used][free][free][free]

In the beginning.
[free]

After one allocation.
[used][free]
After one free.
[free][free]
After a reclaim
[free]

Now the same idea continues. You just make two searches for a allocation now instead of one... the for loops handle that.

To reclaim you combine two blocks that are _both_ free and _both_ next to each others. Then you try again at the new block you created by taking two and making one, and check the one after that.

The code has not been tested, and will likely not work as is. It might run with no errors, but only minor fixes should be needed. *laughing*

It is nice that you do not need to specify a separate place for the heap management data, instead it gets built right into the heap. However - corruption could prove fatal.

Code: Select all

struct tblock{
	unsigned int size;
};
struct tblock *blocks = 0;
unsigned int heapsize = 0;
void init(unsigned int address, unsigned short size){
	blocks = (struct tblock*)address;
	blocks->size = size - sizeof(struct tblock);
	heapsize = size;
	return;
}

void *alloc(unsigned int size){
	struct tblock *cb, *nb;
	// keep going... removing used bit(31)..
	for(cb = blocks; (unsigned int)cb < heapsize; cb = (struct tblock*)((unsigned int)&cb[1] + (cb->size & (~0x80000000))){
		if(!(cb->size & 0x80000000)){
			if(cb->size <= size){
				// it is free..
				nb = (struct tblock*)((unsigned int)&cb[1] + size);
				nb->size = cb->size - (size + sizeof(struct tblock));
				cb->size = size & 0x80000000;
				return (void*)&cb[1];
			}
		}
	}
	return 0;
}

void free(void *ptr){
	struct tblock *cb = (struct tblock*)ptr;
	cb->size = cb->size & (~0x80000000);
	return;
}

void reclaim(void){
	struct tblock *cb, *nb;
	for(cb = blocks; (unsigned int)cb < heapsize; cb = (struct tblock*)((unsigned int)&cb[1] + (cb->size & (~0x80000000))){
		if(cb->size & 0x80000000){
			tryagain:;
			nb = (struct tblock*)((unsigned int)&cb[1] + (cb->size & (~0x80000000))
			if(nb->size & 0x80000000){
				// combine them..
				cb->size += sizeof(struct tblock) + nb->size;
				goto tryagain;
			}
		}
	}
	return;
}

[Solar]

@ kmcguire:

In a user process, you have to request additional heap space from the kernel; when your concept (and e.g. my PDCLib as of now) "frees" memory, it is "free" to be reused instead of requesting additional heap from the kernel, but it is not free to be reassigned to a different user process.

Which is what salil_bhagurkar was looking for, I think, and what I will do once I got that %&$§$& <stdio.h> running.

[pcmattman]

I just got my stdio.h working ... file and console i/o, I'm a very happy person...

My memory allocation system is really simple. Basically, it's just an array of 'mBlock' structures, which have important information such as the memory location of the block and its status. When you request a block (malloc, or malloc_count which lets you choose the number of blocks) it just finds free blocks on the list and gives them to the caller. Free just takes the structure as an argument and clears the blocks in the list (it also NULLifies all of the memory that was taken by it, just so that you can tell when you accidentally run into unallocated memory).

Just my 2 cents.

[Kevin McGuire]

I am starting to feel the PDClib, was a year or so ago - and, still is -- a good idea if it gets bigger. I was just thinking about it this second.. it felt interesting. But that happens a lot, and I am no millionaire.

[Solar]

It will get bigger. I just can't really tell how long it will take.

It gets really frustrating when you get to a point where you have to do something sweeping, complex (like ATM, getting read-write buffer handling / text-binary conversion / char-wchar orientation / read-write orientation right for all the various stdio functions), and find you just don't get around to doing it. I know that once that is done, I'll make lots of progress in very small time (locale / ctype is a piece of cake, in comparison).

You being a millionaire wouldn't change much, because I won't make my family's only income depend on PDCLib.

I can just promise I'll continue to work on it.

</sorryforofftopic>

[salil_bhagurkar]

Thanx all for your replies... I will try to implement the code...