OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Oct 23, 2017 7:08 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: BitmapHeapImplementation
PostPosted: Fri Aug 11, 2017 10:03 am 
Offline

Joined: Wed Dec 03, 2014 1:46 pm
Posts: 15
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?

_________________
My Code


Top
 Profile  
 
 Post subject: Re: BitmapHeapImplementation
PostPosted: Fri Aug 11, 2017 11:30 am 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 199
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.


Top
 Profile  
 
 Post subject: Re: BitmapHeapImplementation
PostPosted: Fri Aug 11, 2017 12:39 pm 
Offline

Joined: Wed Dec 03, 2014 1:46 pm
Posts: 15
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.

_________________
My Code


Top
 Profile  
 
 Post subject: Re: BitmapHeapImplementation
PostPosted: Fri Aug 11, 2017 1:01 pm 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 199
lolxdfly wrote:
I just changed the condition of the loop...
Why didn't I think of that...


Top
 Profile  
 
 Post subject: Re: BitmapHeapImplementation
PostPosted: Sat Aug 12, 2017 7:51 pm 
Offline
Member
Member

Joined: Mon Jan 03, 2011 6:58 pm
Posts: 273
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group