Virtual page - Frame allocation algorithm

Question

Guys, can someone explain me this algorithm of Frame allocation?
I’ve broken my head trying to understand what each function does but I can’t make sense of it.

Code tutorial link below: http://www.jamesmolloy.co.uk/tutorial_html/6.-Paging.html

// A bitset of frames - used or free.
u32int *frames;

u32int nframes;


// Defined in kheap.c

extern u32int placement_address;

// Macros used in the bitset algorithms.
#define INDEX_FROM_BIT(a) (a/(8*4))

#define OFFSET_FROM_BIT(a) (a%(8*4))


// Static function to set a bit in the frames bitset
static void set_frame(u32int frame_addr)

{
   u32int frame = frame_addr/0x1000;

   u32int idx = INDEX_FROM_BIT(frame);

   u32int off = OFFSET_FROM_BIT(frame);

   frames[idx] |= (0x1 << off);
}


// Static function to clear a bit in the frames bitset
static void clear_frame(u32int frame_addr)

{
   u32int frame = frame_addr/0x1000;

   u32int idx = INDEX_FROM_BIT(frame);

   u32int off = OFFSET_FROM_BIT(frame);

   frames[idx] &= ~(0x1 << off);

}


// Static function to test if a bit is set.
static u32int test_frame(u32int frame_addr)

{
   u32int frame = frame_addr/0x1000;

   u32int idx = INDEX_FROM_BIT(frame);

   u32int off = OFFSET_FROM_BIT(frame);

   return (frames[idx] & (0x1 << off));

}

// Static function to find the first free frame.
static u32int first_frame()

{
   u32int i,    j;
   for (i = 0; i < INDEX_FROM_BIT(nframes); i++)
   {

       if (frames[i] != 0xFFFFFFFF) // nothing free, exit early.

       {
           // at least one bit is free here.
           for (j = 0; j < 32; j++)
           {

               u32int toTest = 0x1 << j;

               if ( !(frames[i]&toTest) )
               {
                   return i*4*8+j;
               }
           }
       }
   }
}

Answer 1

I commented the code to you.

The program looks for the first free bit of a table with 1 and 0.

// A bitset of frames - used or free.
u32int *frames; // Tabela de frames de 32 bits, tem que alocar

u32int nframes; // Numero de tabela (tamanho da tabela)


// Defined in kheap.c

extern u32int placement_address; // ?

// Macros used in the bitset algorithms.
#define INDEX_FROM_BIT(a) (a/(8*4)) 

#define OFFSET_FROM_BIT(a) (a%(8*4))

// Indexo do array: qual é o index do bit 35 por exemplo ?
// Index  = 35 / 32 = 1
// Offset = 35 % 32 = 3
// Para ter o bit 35, você tem que buscar ao indexo 1 da tabela e ler o bit 3
// Tabela: XXXXXXXX XXXX[X]XXX XXXXXXXX XXXXXXXX XXXXXXXX ...
// Index:  0        1          2        3        4
// Offset                3 210

// Static function to set a bit in the frames bitset
static void set_frame(u32int frame_addr)

{
   // dividir por 0x1000 = 4096 = 2^12
   // significa: frame/addr >> 12 (dado é situado depois dos 12 primeiros bits)
   u32int frame = frame_addr/0x1000; // frame tem o bit para procurar.

   u32int idx = INDEX_FROM_BIT(frame); // Obter o index do bit

   u32int off = OFFSET_FROM_BIT(frame); // Obter o offset do bit

   frames[idx] |= (0x1 << off); // Colocar 1 no bit na tabela
}


// Static function to clear a bit in the frames bitset
static void clear_frame(u32int frame_addr)

{
   // Igual, mas esta vez para colocar um 0 no bit da tabela
   u32int frame = frame_addr/0x1000;

   u32int idx = INDEX_FROM_BIT(frame);

   u32int off = OFFSET_FROM_BIT(frame);

   frames[idx] &= ~(0x1 << off); // Colocar 0 no bit da tabela

}


// Static function to test if a bit is set.
static u32int test_frame(u32int frame_addr)

{
   // Igual, mas esta vez para obter o valor do bit
   u32int frame = frame_addr/0x1000;

   u32int idx = INDEX_FROM_BIT(frame);

   u32int off = OFFSET_FROM_BIT(frame);

   return (frames[idx] & (0x1 << off)); // Obter o valor do bit

}

// Static function to find the first free frame.
static u32int first_frame()

{
   u32int i,    j;
   for (i = 0; i < INDEX_FROM_BIT(nframes); i++) // Ler a tabela enterra (até o ultimo indexo)
   {
       // Se cada bit esta utilizado (1), não é útil testar este indexo, passar por o próximo diretamente
       if (frames[i] != 0xFFFFFFFF) // nothing free, exit early.

       {
           // at least one bit is free here.
           // Eu espero que é verdade, senão, o programa nunca vá retornar alguma cosa...
           for (j = 0; j < 32; j++) // Por cada bit do indexo
           {

               u32int toTest = 0x1 << j; // Fazer um mascara para isolar o bit
               // Isolar o bit: se o valor é > 0 (bit = 1, então o bit esta livre)
               if ( !(frames[i]&toTest) )
               {
                   // Retornar um inteiro:
                   // - A partir do bit 6 (2^6 = 32 = 4*8), terá o indexo
                   // - Nos outros bits (0 até 5) terão o offset
                   // Exemplo com 35 (indexo = 1, offset = 3):
                   // Retornado:     00000000 00000000 00000000 01   000011
                   // Numero do bit:                             6        0
                   // Valor:                                     1        3
                   //                < --------- index --------- > | offset
                   return i*4*8+j;
               }
           }
       }
   }
}