mm bitmap

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

[Kevin McGuire]

http://www.osdev.org/phpBB2/viewtopic.p ... ht=#100611

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

[Brendan]

Hi,

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

[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();
}

[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);
     }
}

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

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

[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