OSDev.org

I already implement a first fit algorithm, it looks for an entry in the heap that has enough room for the asked allocation size. The entry is a record with size and pointer to the first byte. The question is, what's the initial condition of this heap? If it's all 0, then all allocation will of course fail.

Hi,

The heap can be as big or small as you like with whatever initial condition you like. You need a heap setup function which creates a heap entry labelling the entire heap as "free". The first allocation will split this memory, marking some as free and some as allocated.

I would recommend James Molloy's excellent heap tutorial at http://www.jamesmolloy.co.uk , which explains everything in fine detail.

Cheers,
Adam

AJ wrote:Hi,

The heap can be as big or small as you like with whatever initial condition you like. You need a heap setup function which creates a heap entry labelling the entire heap as "free". The first allocation will split this memory, marking some as free and some as allocated.

I would recommend James Molloy's excellent heap tutorial at http://www.jamesmolloy.co.uk , which explains everything in fine detail.

Cheers,
Adam

Hi,

Thanks AJ for the namedrop, however the heap on that site is rather poor in my opinion - I'm rewriting the tutorials and have majorly redone the heap one. I haven't written the accompanying text yet, but you can find code for it here. Look at heap.h and heap.c for a fully functional first-fit heap implementation in 132 lines of C.

As to the OP's question - I generally special-case the first allocation. Just makes things easier!

Cheers,

James

OT: I like the brevity of the new code, but did like the "safety" that the footer brought on your previous implementation. Nice idea using a bitfield to mark the region as allocated. I guess that seeing as you want to keep heap allocations aligned, you actually have one other spare bit should the need arise for a second flag. You said it's only partially completed, but out of interest, are you planning on putting magic numbers back in?

Cheers,
Adam

AJ wrote:OT: I like the brevity of the new code, but did like the "safety" that the footer brought on your previous implementation. Nice idea using a bitfield to mark the region as allocated. I guess that seeing as you want to keep heap allocations aligned, you actually have one other spare bit should the need arise for a second flag. You said it's only partially completed, but out of interest, are you planning on putting magic numbers back in?

Cheers,
Adam

Hmm, I'm considering it. I think maybe I can put magic numbers back into the header without adding too much code overhead. I'm loath to put footers back in as they added to code without really giving much back - if you overwrite the end of a memory chunk you actually corrupt the next header as well, so I think magic numbers in the headers should give around the same amount of safety.

Thanks for the feedback - all is welcome!

James

@JamesM:
I've seen your new code, is it complete? It seems more appropriate for newbies, the previous heap implementation was very long and quite hard to understand. Also, the pmm changes from bitmap to stack, eh? I personally prefer that since it doesn't differ much in size and much faster. I think I'll provide two pmm implementations in my OS so that I can switch easily whenever I want.

leledumbo wrote:@JamesM:
I've seen your new code, is it complete? It seems more appropriate for newbies, the previous heap implementation was very long and quite hard to understand. Also, the pmm changes from bitmap to stack, eh? I personally prefer that since it doesn't differ much in size and much faster. I think I'll provide two pmm implementations in my OS so that I can switch easily whenever I want.

Hi,

It's complete in that it works 100%, it's incomplete in that it may change before I release it

James