BitmapHeapImplementation

[lolxdfly]

I was looking for some information about Memory Management of Operating Systems and found the BitmapHeapImplementation
here: http://wiki.osdev.org/User:Pancakes/Bit ... ementation.

I'm not sure if I understand the impementation right but this line of k_heapBMAlloc looks suspicious:

Code: Select all

for (x = (b->lfb + 1 >= bcnt ? 0 : b->lfb + 1); x < b->lfb; ++x) {

x gets the value 0 if lfb+1 is bigger or equal to bcnt. If not x gets lfb+1. But the for loop conditions is x < lfb. In this case the complete loop is skipped and the function returns 0.

I tried the Implementation in my own kernel and got the same problem. All Memory Allocations result in a null pointer.

Did I undestand the implementation wrong or did I just messed up my kernel code or is this a mistake in the wiki?

[simeonz]

I think you are correct. It is kind-of strange, because the bug should short-circuit even the first allocation attempt.

I have not tested the following in any shape or form, but the correct method should be something like this I think:

Code: Select all

			y = 0;
			for (x = b->lfb + 1; x < bcnt; ++x) {
				if (bm[x] == 0)
				{
					/* count free blocks */
					++y;
					if (y == bneed)
						goto allocate;
					continue;
				}
				y = 0;
			}
			y = 0;
			for (x = 0; x <= b->lfb; ++x) {
				if (bm[x] == 0)
				{
					/* count free blocks */
					++y;
					if (y == bneed)
						goto allocate;
					continue;
				}
				y = 0;
			}
			return 0;
			/* we have enough, now allocate them */
			allocate:
			/* find ID that does not match left or right */
			nid = k_heapBMGetNID(bm[x - 1], bm[x + y]);

			/* allocate by setting id */
			for (z = 0; z < y; ++z) {
				bm[x + z] = nid;
			}

			/* optimization */
			b->lfb = (x + bneed) - 2;

			/* count used blocks NOT bytes */
			b->used += y;

			return (void*)(x * b->bsize + (uintptr)&b[1]);

It could use refactoring (the labeled branch into a separate function), but I left it like this to minimize the difference with the original code.

Also, there are other slight improvements that would benefit the source on that page. For example, lines such as:

Code: Select all

bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize;

can be rewritten as:

Code: Select all

bneed = (size + b->bsize - 1) / b->bsize;

That being said, such code requires testing. And even if we had a working version, this is a personal page, so the user has to be contacted for consent at least.

Edit: "(size + b->bsize) / b->bsize" -> "(size + b->bsize - 1) / b->bsize" That shows you what a good programmer I am.

[lolxdfly]

I just changed the condition of the loop to

Code: Select all

x != b->lfb

like it is in the enhanced version:
http://wiki.osdev.org/User:Pancakes/Bit ... onEnhanced

I'm not sure if it works completly but I can allocate and free memory now.

[simeonz]

I just changed the condition of the loop...

Why didn't I think of that...

[FallenAvatar]

lolxdfly: Just an FYI, this subforum is for dicussing ideas/edits/problems with the Wiki. This topic belongs more in OS Development.

Not an issue, just an FYI.

- Amy