Page 1 of 1
mm bitmap
Posted: Mon Jul 16, 2007 6:48 pm
by xyjamepa
Hi,
I'm rewriting my memory manager and I started from the first layer
which the physical mm,in the past I used stack for allocating and
deallocating memory pages,now I want to use bitmap but I have a few questions:
*if I decleared the bitmap as a pointer to a dword,is this the right
formula to calculate number of available pages?
max_pages=memory_size/page_size/32
*If I want to set page as used I have to do:
.calculate the offset by page / 32
.determin the exact bit by bit=page % 32
Am I right?
*would you please give me a simple example of how to "set_bit"
I'm having problems here.
Thanx.
Posted: Mon Jul 16, 2007 7:01 pm
by Kevin McGuire
Posted: Mon Jul 16, 2007 8:37 pm
by AndrewAPrice
To set a bit, I do an binary AND operation to check if it's not what we want it to be, and then I use a binary XOR to switch it around.
Posted: Mon Jul 16, 2007 9:53 pm
by Brendan
Hi,
MessiahAndrw wrote:To set a bit, I do an binary AND operation to check if it's not what we want it to be, and then I use a binary XOR to switch it around.
Or you you want it to be faster, use BTS, BTR, BTC and BT instructions. For e.g. (to set a bit):
Code: Select all
mov eax, pageNumber
bts [myArrayOfBits], eax
jc .itWasAlreadySet!
It prevents the need to calculate the address of the dword in the array.
Unfortunately, the optimizers in most (all?) compilers won't do this for you. For example, with "GCC -O3" this code:
Code: Select all
int AllocPageFromBitmap(unsigned char *my_bitmap, unsigned int pageAddr)
{
if(my_bitmap[(pageAddr>>12)/8] & (1<<((pageAddr>>12)%8 ) ) )
{
return 1; // Return ERROR
}
my_bitmap[(pageAddr>>12)/8] &= ~(1<<((pageAddr>>12)%8 ));
return 0; // Return OK
}
Becomes:
Code: Select all
AllocPageFromBitmap:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 12(%ebp), %eax
movl %esi, 4(%esp)
movl $1, %esi
movl %ebx, (%esp)
movl %eax, %ecx
movl %eax, %edx
movl 8(%ebp), %eax
shrl $15, %edx
shrl $12, %ecx
andl $7, %ecx
addl %eax, %edx
movzbl (%edx), %ebx
movzbl %bl, %eax
sarl %cl, %eax
testb $1, %al
jne .L4
movl $1, %eax
xorl %esi, %esi
sall %cl, %eax
notb %al
andb %al, %bl
movb %bl, (%edx)
.L4:
movl %esi, %eax
movl (%esp), %ebx
movl 4(%esp), %esi
movl %ebp, %esp
popl %ebp
ret
Instead you could use:
Code: Select all
AllocPageFromBitmap:
mov ecx,[esp+8] ;ecx = address of page
mov eax,[esp+4] ;eax = address of bitmap
shr ecx,12 ;ecx = page number
bts [eax],ecx ;Set the bit
mov eax,0 ;Return value = 0
adc eax,0 ;Return value = 1 if bit was already set
ret
The other nice thing about this is that it can be easy to make this code re-entrant (SMP safe):
Code: Select all
AllocPageFromBitmap:
mov ecx,[esp+8] ;ecx = address of page
mov eax,[esp+4] ;eax = address of bitmap
shr ecx,12 ;ecx = page number
lock bts [eax],ecx ;Set the bit
mov eax,0 ;Return value = 0
adc eax,0 ;Return value = 1 if bit was already set
ret
Cheers,
Brendan
Posted: Tue Jul 17, 2007 12:52 am
by xyjamepa
Hi...
Okay here's what I got now,I tested this code in my kernel
and it gave me valid addresses but would you please guys
check it for me.
Also I want to know how can I make any address 4k aligned?
Code: Select all
//let's assume memory size is 4MB
//and till now there's no free pages
dword first_free_page=0x400;
dword max_pages=(0x400000/0x1000/0x20);
//return the address from a given number
dword page_addr(dword page)
{
return (page << 12);
}
//return page number from given address
dword page_num(dword addr)
{
return (addr >> 12);
}
Code: Select all
used_page(dword *my_bitmap, dword pageAddr)
{
if(my_bitmap[(pageAddr>>12)/32] & (1<<((pageAddr>>12)%32 ) ) )
{
/// already allocated!
}
// allocate
my_bitmap[(pageAddr>>12)/32] &= ~(1<<((pageAddr>>12)%32 ));
first_free_page=page_addr(++first_free_page);
}
free_page(dword *my_bitmap,dword pageaddr)
{
my_bitmap[bitnum/32] |= (1<<(bitnum%32 ));
first_free_page=page_addr(--first_free_page);
}
dword get_first_free()
{
return page_addr(first_free_page);
}
dword alloc_phs_page()
{
dword page=get_first_free();
used_page(page);
return page;
}
void free_phs_page(dword page)
{
free_page(page);
}
void init_mm()
{
dword i;
//set all memory free
for(i=0x1000;i<=0x400000;i+=0x1000)
free_phs_page(i);
//set kernel pages as used
for(i=0x100000;i<=kernelend;i+=0x1000)
alloc_phs_page();
}
Posted: Tue Jul 17, 2007 5:59 am
by AndrewAPrice
Your free_page was using a binary or, since 1 or 1 = 1 your bit is left set. You should try using xor (1 xor 1 = 0).
Code: Select all
free_page(dword *my_bitmap,dword pageaddr)
{
/* first check to see if the bit is set */
if(my_bitmap[(pageAddr>>12)/32] & (1<<((pageAddr>>12)%32 ) ) )
{
/* if it is, use xor to unset it */
my_bitmap[bitnum/32] ^= (1<<(bitnum%32));
first_free_page=page_addr(--first_free_page);
}
}
Posted: Tue Jul 17, 2007 1:45 pm
by xyjamepa
Hi...
That was the first problem,thank you for fixing it,
also how about max_pages ,am I doing it in the right way?
I mean is this right?
dword max_pages=(0x400000/0x1000/0x20)
Know that I assume the memory size is 4MB.
Also is there any other bugs or mistakes in my code?
Thanx.
Posted: Tue Jul 17, 2007 5:12 pm
by xyjamepa
Hi...
here's what I got so far,I think there's wrong with
my free_page.
would you please check it.
Code: Select all
void used_page(dword page)
{
if(mem_bitmap[(page>>12)/32] & (1<<((page>>12)%32 ) ) )
{
/// already allocated! printf("errrrror");return;
}
// allocate
mem_bitmap[(page>>12)/32] |= (1<<((page>>12)%32 ));
first_free_page++;
printf("page allocated at %x\n",page);
}
void free_page(dword page)
{
//check if it's allocated or not
if((mem_bitmap[(page>>12)/32] & (1<<((page>>12)%32 ) ) ) )
{
mem_bitmap[(page>>12)/32] &= ~(1<<((page>>12)%32 ));
first_free_page--;
printf("page freed at %x\n",page);
}
}
I have only one last question,how can I make the kernel end address
4KB aligned?
Thanx.
Posted: Wed Jul 18, 2007 9:11 am
by Combuster
I have only one last question,how can I make the kernel end address
4KB aligned?
Just add the necessary bytes. You should be able to use linker scripts for that