OSDev.org https://forum.osdev.org/ |
|
BitmapHeapImplementation https://forum.osdev.org/viewtopic.php?f=8&t=32297 |
Page 1 of 1 |
Author: | lolxdfly [ Fri Aug 11, 2017 10:03 am ] |
Post subject: | BitmapHeapImplementation |
I was looking for some information about Memory Management of Operating Systems and found the BitmapHeapImplementation here: http://wiki.osdev.org/User:Pancakes/BitmapHeapImplementation. I'm not sure if I understand the impementation right but this line of k_heapBMAlloc looks suspicious: Code: 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? |
Author: | simeonz [ Fri Aug 11, 2017 11:30 am ] |
Post subject: | Re: BitmapHeapImplementation |
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: y = 0; 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.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]); Also, there are other slight improvements that would benefit the source on that page. For example, lines such as: Code: bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize; can be rewritten as:Code: 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. |
Author: | lolxdfly [ Fri Aug 11, 2017 12:39 pm ] |
Post subject: | Re: BitmapHeapImplementation |
I just changed the condition of the loop to Code: x != b->lfb like it is in the enhanced version:http://wiki.osdev.org/User:Pancakes/BitmapHeapImplementationEnhanced I'm not sure if it works completly but I can allocate and free memory now. |
Author: | simeonz [ Fri Aug 11, 2017 1:01 pm ] |
Post subject: | Re: BitmapHeapImplementation |
lolxdfly wrote: I just changed the condition of the loop... Why didn't I think of that...
|
Author: | FallenAvatar [ Sat Aug 12, 2017 7:51 pm ] |
Post subject: | Re: BitmapHeapImplementation |
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 |
Page 1 of 1 | All times are UTC - 6 hours |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |