physical mem bitmap

[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]

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]

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]

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]

Hi,

How would a compiler output the code <value> % 8?

Make a testcase, compile, and then objdump (-S iirc) to get the assembly.

[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]

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]

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

[JamesM]

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]

Thanks for all the replays.

i havent changed anything on your suggestions yet as ive only just finished and gone through your comments.

[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