page alloc

[GLneo]

I'm starting to work on a paging system, my first task is to get a physical page allocator ( pages are 4k ) working, i am having trouble just finding a blank page, i wrote this:

Code: Select all

/*
 *  los/mm/palloc2.c
 *
 *  Copyright (C) 2007
 */

unsigned long page_usage_bitmap[32768];

int page_alloc()
{
    int i = 0, ipos = 0;
    while(page_usage_bitmap[i] == 0xFFFFFFFF)
    {
        if(i >= 32768)
            return 0;
        i++;
    }
    while(ipos < 32)
    {
        if( page_usage_bitmap[i] && (!(2147483648 >> ipos)) )
            return ((i * 32) + ipos);
        ipos++;
    }
    return 0;
}    

it always returns zero ( even when i set the first few pages ) I'm also confused on how to make a working page allocator out of this?

thanks for you time!

[frank]

Maybe the && in the following code should just be a &.

Code: Select all

while(ipos < 32)
    {
        if( page_usage_bitmap[i] && (!(2147483648 >> ipos)) )
            return ((i * 32) + ipos);
        ipos++;
    } 

[GLneo]

thank you, that fixed the page finding loop ( i think, i cant determine that until a can set pages, then test if it wont give me that page ), which is what i'm having more problems, here is code:

Code: Select all

/*
 *  los/mm/palloc2.c
 *
 *  Copyright (C) 2007  Andrew Davis
 */
 
#include <los/setup.h>

unsigned long page_usage_bitmap[32768];

int page_alloc()
{
    int i = 0, ipos = 0;
    while(page_usage_bitmap[i] == 0xFFFFFFFF) // page group loop
    {
        if(i >= 32768)
            return 0;
        i++;
    }
    while(ipos < 32)// page loop
    {
        if( !(page_usage_bitmap[i] & (!(2147483648 >> ipos))) ) // 2147483648 = 1000...0b
            return ((i * 32) + ipos);
        ipos++;
    }
    return 0;
}

void page_set( int page )
{
    int group;
    group = page / 32;
    if( group != 0 )
        page_usage_bitmap[group] |= (2147483648 >> (page % group));
    else
        page_usage_bitmap[group] |= (2147483648 >> (page)); // this avoids zero division
    
}    

what i do is call page_set( 0 );, then call page_alloc() and it returns 0, but it should return 1 ( becouse page one is already set )?

[bluecode]

Code: Select all

if( !(page_usage_bitmap[i] & (!(2147483648 >> ipos))) ) // 2147483648 = 1000...0b

should perhaps be something like

Code: Select all

if ((page_usage_bitmap[i] & (1 << ipos)) == 0)

and

Code: Select all

void page_set( int page ) 
{ 
    int group; 
    group = page / 32; 
    if( group != 0 ) 
        page_usage_bitmap[group] |= (2147483648 >> (page % group)); 
    else 
        page_usage_bitmap[group] |= (2147483648 >> (page)); // this avoids zero division 
    
}

something like

Code: Select all

page_usage_bitmap[page / 32] = 1 << (page % 32);

[frank]

Okay well I guess I'll let you see mine, I have always found code better than long explanations sometimes. Of course there is something i should tell you. All of functions use physical addresses and not page numbers.

Code: Select all

#define BIT( bit )                       ( 1 << bit )
#define SET_BIT( data, bit )       ( data |= BIT( bit ) )
#define RESET_BIT( data, bit )    ( data &= ( ~( BIT( bit ) ) ) )

#define GET_PAGE_NUMBER( address )    ( address >> 12 )
#define GET_PAGE_ADDRESS( page )      ( page << 12 )

// m_memory_bitmap = DWORD *m_memory_bitmap;

DWORD CPhysical_Memory_Manager::Allocate_Free_Page( )
{
	DWORD i = 0, j = 0;
	
    // look for a free page
    for ( i = ( m_first_free / 32 ); i < ( m_page_count / 32 ); i++ )
    {
        // are all of those pages used
        if ( m_memory_bitmap[i] == 0xFFFFFFFF )
            continue;

        // find the correct bit
        for ( j = 0; j < 32; j++ )
        {
            // test this page
            if ( m_memory_bitmap[i] & BIT( j ) )
            {
                // this page is allocated
                continue;

            } // end if

            else
            {
            	// this page is now used
            	SET_BIT( m_memory_bitmap[i], j );
            	
                // set the new first free page
                m_first_free = ( 32 * i ) + j;
                
                // update the free pages count
                m_free_pages--;

                // return the page address
                return( GET_PAGE_ADDRESS( ( 32 * i ) + j ) );

            } // end else

        } // end for

    } // end for

    // no more free pages
    // TODO: Add swaping code

    // for now return an error
    return( 0xFFFFFFFF );
	
} // end Allocate_Free_Page

void CPhysical_Memory_Manager::Set_Page_Used( DWORD address )
{
	DWORD *bitmap = m_memory_bitmap;
	
	// make sure this page is in the bitmap
	if ( GET_PAGE_NUMBER( address ) > m_page_count )
		return;

    // find the offset into the page
    DWORD offset = GET_PAGE_NUMBER( address ) / 32;

    // find the bit
    DWORD bit = GET_PAGE_NUMBER( address ) % 32;

    // go to the correct DWORD
    bitmap += offset;

    // now set the correct bit
    SET_BIT( (*bitmap), bit );
    
    // update the free page count
    m_free_pages--;
	
} // end Set_Page_Used

void CPhysical_Memory_Manager::Set_Page_Free( DWORD address )
{
	DWORD *bitmap = m_memory_bitmap;
	
	// make sure this page is in the bitmap
	if ( GET_PAGE_NUMBER( address ) > m_page_count )
		return;

    // find the offset into the page
    DWORD offset = GET_PAGE_NUMBER( address ) / 32;

    // find the bit
    DWORD bit = GET_PAGE_NUMBER( address ) % 32;

    // go to the correct DWORD
    bitmap += offset;

    // now set the correct bit
    RESET_BIT( (*bitmap), bit );
    
    // update the first free page if neccessary
    if ( GET_PAGE_NUMBER( address ) < m_first_free )
    	m_first_free = GET_PAGE_NUMBER( address );
    	
    // update the free page count
    m_free_pages++;
	
} // end Set_Page_Free 

[GLneo]

I like talking with code too, heres what I've made as of now:

Code: Select all

/*
 *  los/mm/physical.c
 *
 *  Copyright (C) 2007  Andrew Davis
 */
 
#include <los/setup.h>

unsigned long page_usage_bitmap[32768];

int page_alloc()
{
    int i = 0, ipos = 0;
    while(page_usage_bitmap[i] == 0xFFFFFFFF) // page group loop
    {
        if(i >= 32768)
            return 0;
        i++;
    }
    while(ipos < 32)// page loop
    {
        if ((page_usage_bitmap[i] & (1 << ipos)) == 0)
        {
            page_set( (int) ((i * 32) + ipos) );
            return ((i * 32) + ipos);
        }
        ipos++;
    }
    return 0;
}

void page_set( int page )
{
    page_usage_bitmap[page / 32] |= 1 << (page % 32); 
}

void page_free( int page )
{
    page_usage_bitmap[page / 32] &= !(1 << (page % 32)); 
}

void page_protect_mem( unsigned int start, unsigned int end )
{
    int page_start, page_end;
    if( start >= end )
        return;
    page_start = ( start / 4096 );
    page_end = (end % 4096)==0?(end / 4096):((end / 4096) + 1);
    while( page_start <= page_end )
    {
        page_set( page_start );
        page_start++;
    }
}

it is not commented but i would expect anyone working with this code to be competent enough to understand it

I'm am now in the process of writing code to easily add pages to a processes page directory, so the user can say give me 100k and it will peace together all the fragmented pages, but i haven't the slightest idea where to begin?

[frank]

I have 2 functions for doing that.

void Map_Page( DWORD vm_loc, DWORD phy_loc, DWORD attr );

and

DWORD Allocate_Page( DWORD location, DWORD type );

Allocate_Page calls Allocate_Free_Page to get a free physical page and then calls Map_Page to map that page at the virtual location specified.

Map_Page first checks to see if a page table needs to be allocated for that address and if so calls Allocate_Free_Page to get a free page. It then maps the physical address sent to the virtual address.

[GLneo]

but what is inside

void Map_Page( DWORD vm_loc, DWORD phy_loc, DWORD attr );

?

thx!

[frank]

but what is inside

void Map_Page( DWORD vm_loc, DWORD phy_loc, DWORD attr );

?

thx!

Do you want code or an explanation?

[GLneo]

explanation would help, but i learn best by example, i think i understand the idea ( add the page to the users task's page directory ), but the exact workings I'm still clueless, so any explanation or code would be greatly appreciated

thx!

[frank]

Okay well what do you already know? Do you know how to map pages? Do you have paging enabled now or are you looking for help in that area too?

Here is the code for my Map_Page function. It makes several assumptions, that the page directory can be accessed at 0xFFFFF000, and the page tables can be accessed from 0xFFC00000 to 0xFFFFEFFF.

Code: Select all

void CVirtual_Memory_Manager::Map_Page( DWORD vm_loc, DWORD phy_loc, DWORD attr )
{
	PAGE_DIRECTORY *pd = (PAGE_DIRECTORY *)0xFFFFF000;
    PAGE_TABLE *pt = 0;

    DWORD page = 0;

    DWORD page_table = 0;

    // get the page number
    page = GET_PAGE_NUMBER( vm_loc );

    // move to the right page directory entry
    pd += PAGE_TABLE( page );

    // check the present flag
    if ( pd->present == false )
    {
        // we need to allocate a page table
        page_table = phys_mem_manager.Allocate_Free_Page( );

        if ( page_table == 0xFFFFFFFF )
        {
            kernel_panic( "OUT OF MEMORY" );

        } // end if
        
        // get the page number
        page_table = GET_PAGE_NUMBER( page_table );

        // set the page directory entry
        pd->page_table = page_table;

        // set the page to present and read write
        pd->present             = true;
        pd->read_write          = true;
        pd->user_supervisor     = true;

        // flush page table entries
        asm( "invlpg (%%eax)" : : "a" ( ( (DWORD)page_table) << 12  ) );
        //asm( "invlpg (%%eax)" : : "a" ( page_directory ) );
        asm( "invlpg (%%eax)" : : "a" ( ( 0xFFC00000 + ( page_table * 4096 ) ) ) );

        // get a pointer to the page table data
        void *data = (void *)( 0xFFC00000 + ( PAGE_TABLE( page ) * 4096 ) );

        // zero the new page table
        memsetd( data, 0, 0x1000 / 4 );

    } // end if

    // move to the proper page entry
    pt = (PAGE_TABLE *) ( 0xFFC00000 + ( PAGE_TABLE( page ) * 4096 ) );

    // move to the right entry
    pt += PAGE( page );
    
    // set the attributes
    pt->entry = attr & 0xFFF;

    // set the address
    pt->page = GET_PAGE_NUMBER( phy_loc );

    // flush the TLB entries
    asm( "invlpg (%%eax)" : : "a" ( phy_loc ) );
    asm( "invlpg (%%eax)" : : "a" ( vm_loc ) );
	
} // end Map_Page

EDIT: Oh I should tell you what the macros are

Code: Select all

#define GET_PAGE_NUMBER( address ) ( address >> 12 )
#define GET_PAGE_ADDRESS( page ) ( page << 12 )
#define PAGE_TABLE( data )      ( ( data & 0xFFC00 ) >> 10 )
#define PAGE( data )            ( data & 0x3FF )