physical mem bitmap

Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
Post Reply
itisiuk
Member
Member
Posts: 98
Joined: Mon Mar 24, 2008 1:46 pm

physical mem bitmap

Post by itisiuk »

hi, im busy changing my physical mem manager from a stack based allocator to a bitmap map.
ive been reading the info in
http://www.osdev.org/wiki/Page_Frame_Allocation
anyway, this is what i have come up with so far, ive checked it and it seems to work but i would like another persons opinion.

char *physical_bitmap;
int physical_bitmapSize;
void *physical_max Address;

#define BITMAP_BYTE_INDEX( address )( ((DWORD)address / 4096) / 8 )

#define BITMAP_BIT_INDEX( address )( 8 - (((DWORD)address / 4096) % 8 ) - 1 )

#define physical_pageAllocAddress(address)( physical_bitmap[ BITMAP_BYTE_INDEX(address) ] |= ( 1 << BITMAP_BIT_INDEX(address) ) )

int physical_isPageFree( void * physicalAddress )
{
if( physical_bitmap[ BITMAP_BYTE_INDEX( physicalAddress ) ] & ( 1 << BITMAP_BIT_INDEX( physicalAddress ) ) )
return FAIL;
return SUCCESS;
}

m_upper is = to grub upper mem size in Kb

physical_max Address = (1024*1024)*((m_upper-1)/1024);

physical_bitmapSize = (((m_upper*1024)/4096)/8 );
Hangin10
Member
Member
Posts: 162
Joined: Wed Feb 27, 2008 12:40 am

Post by Hangin10 »

It looks right to me so far. It doesn't actually change anything, but for the smaller code you could change the 8 to a 7 in BITMAP_BIT_INDEX and get rid of the -1 at the end.

Also, it might be more efficient to use the full size of int on whatever platform you're on, so that when doing the allocation, you can test for 0xffff... (16/32/64, etc) or zero quicker. <- can anyone confirm that?
itisiuk
Member
Member
Posts: 98
Joined: Mon Mar 24, 2008 1:46 pm

Post by itisiuk »

Thanks for the reply.

im not sure about the full size int making testing quicker, but ill look into it, thanks.

ill be posting some more code to this later once ive finished, 1st time trying this so any advice or comments on the code ill be posting are much appreciated.
zerosum
Member
Member
Posts: 63
Joined: Wed Apr 09, 2008 6:57 pm

Post by zerosum »

One thing I would do is get rid of the divisions/multiplications and use bit-shifts instead. I once wrote some code for image processing stuff I was working on and I soon learned just how slow division/multiplication is and I now avoid it whenever I can.

It might not make a huge difference, but something that easy to do that will make something even a tiny bit faster surely has to be a good thing :-)

<edit>
Then again, a decent compiler would do that for you, I suppose. And this leads me to an O/T question. How would a compiler output the code <value> % 8? Would it do the sensible thing and AND it with 0x07, or would it do something else? I'm assuming any decent one would do that...

Sorry for thread hijacking :-)
</edit>

Cheers,
Lee
pcmattman
Member
Member
Posts: 2566
Joined: Sun Jan 14, 2007 9:15 pm
Libera.chat IRC: miselin
Location: Sydney, Australia (I come from a land down under!)
Contact:

Post by pcmattman »

Hi,
How would a compiler output the code <value> % 8?
Make a testcase, compile, and then objdump (-S iirc) to get the assembly.
User avatar
bewing
Member
Member
Posts: 1401
Joined: Wed Feb 07, 2007 1:45 pm
Location: Eugene, OR, US

Post by bewing »

You never can tell with compilers. Most people just blindly assume that they are smarter than they really are. It is best to force the calculation to work properly, using & 7, rather than % 8. Or to use bitfields, to hide the fact from yourself that you are doing bitwise operations.
Hangin10
Member
Member
Posts: 162
Joined: Wed Feb 27, 2008 12:40 am

Post by Hangin10 »

bewing wrote:You never can tell with compilers. Most people just blindly assume that they are smarter than they really are. It is best to force the calculation to work properly, using & 7, rather than % 8. Or to use bitfields, to hide the fact from yourself that you are doing bitwise operations.
This made me kinda curious... So I did a small test on cygwin gcc (my ubuntu laptop doesn't have internet access):

Code: Select all

 40107a:       c7 45 fc ad 0b 00 00    movl   $0xbad,0xfffffffc(%ebp)
 401081:       c7 45 f8 23 01 00 00    movl   $0x123,0xfffffff8(%ebp)
 401088:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
 40108b:       83 e0 07                and    $0x7,%eax
 40108e:       89 45 fc                mov    %eax,0xfffffffc(%ebp)
 401091:       8d 45 f8                lea    0xfffffff8(%ebp),%eax
 401094:       83 20 07                andl   $0x7,(%eax)
 401097:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
 40109a:       89 44 24 04             mov    %eax,0x4(%esp)
 40109e:       c7 04 24 00 20 40 00    movl   $0x402000,(%esp)
 4010a5:       e8 c6 00 00 00          call   401170 <_printf>
 4010aa:       8b 45 f8                mov    0xfffffff8(%ebp),%eax
 4010ad:       89 44 24 04             mov    %eax,0x4(%esp)
 4010b1:       c7 04 24 07 20 40 00    movl   $0x402007,(%esp)
 4010b8:       e8 b3 00 00 00          call   401170 <_printf>
 4010bd:       b8 00 00 00 00          mov    $0x0,%eax
the C:

Code: Select all

	unsigned long a, b;

	a = 0xBAD;
	b = 0x123;

	a = a % 8;
	b = b & 7;

	printf("a = %d", a);
	printf("b = %d", b);
It looks like it's doing & 7 the first time on the contents of EAX, then
loading an address and using the AND instruction on memory the second
time instead. I don't know what that's about unless it's some kinda pipeline optimization ordering the load/stores...
zerosum
Member
Member
Posts: 63
Joined: Wed Apr 09, 2008 6:57 pm

Post by zerosum »

pcmattman wrote:Hi,
How would a compiler output the code <value> % 8?
Make a testcase, compile, and then objdump (-S iirc) to get the assembly.
Done. GCC at least does it the smart way :-)

Again, sorry for hijacking the thread.

Cheers,
Lee
User avatar
JamesM
Member
Member
Posts: 2935
Joined: Tue Jul 10, 2007 5:27 am
Location: York, United Kingdom
Contact:

Post by JamesM »

bewing wrote:You never can tell with compilers. Most people just blindly assume that they are smarter than they really are. It is best to force the calculation to work properly, using & 7, rather than % 8. Or to use bitfields, to hide the fact from yourself that you are doing bitwise operations.
Constant folding has been around in compilers since the dawn of time. You can be pretty sure the compiler will fold these kind of things - similarly with "x = x/1024", it will change that into a right shift.
itisiuk
Member
Member
Posts: 98
Joined: Mon Mar 24, 2008 1:46 pm

Post by itisiuk »

Thanks for all the replays.

i havent changed anything on your suggestions yet as ive only just finished and gone through your comments.
itisiuk
Member
Member
Posts: 98
Joined: Mon Mar 24, 2008 1:46 pm

Post by itisiuk »

ok so ive been working on all your comments, reading up on the net and testing what works better and this is what ive found works for the bit modification.

x = the index in bytes

a = the byte to test
b = the bit to select for testing

#define BIT_TEST(a,b) ((a) & (1 << b))

#define BIT_BYTE_INDEX(x) (x / 8 )

#define BIT_BIT_INDEX(x) (x & 7)


thanks
Post Reply