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;
         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:
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/