Page 1 of 1
physical mem bitmap
Posted: Fri Apr 11, 2008 3:06 pm
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 );
Posted: Fri Apr 11, 2008 3:46 pm
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?
Posted: Fri Apr 11, 2008 4:03 pm
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.
Posted: Fri Apr 11, 2008 6:07 pm
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
Posted: Fri Apr 11, 2008 8:00 pm
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.
Posted: Fri Apr 11, 2008 8:07 pm
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.
Posted: Fri Apr 11, 2008 8:29 pm
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...
Posted: Fri Apr 11, 2008 8:41 pm
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
Posted: Sat Apr 12, 2008 5:51 am
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.
Posted: Sat Apr 12, 2008 6:46 am
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.
Posted: Mon Apr 14, 2008 2:00 pm
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