---

kmalloc.c

Go to the documentation of this file.

/*!     \file kernel/kmalloc.c
 *      \brief Memory Allocator.
 *      \author Andrea Righi <drizzt@inwind.it>
 *      \date Last update: 2004-01-01
 *      \note Copyright (&copy;) 2003 Andrea Righi
 */

#include <const.h>

#include <arch/i386.h>
#include <arch/mem.h>
#include <arch/paging.h>

#include <kernel/console.h>
#include <kernel/kernel_map.h>
#include <kernel/keyboard.h>
#include <kernel/task.h>

#include <kernel/kmalloc.h>

//! \brief Initialize the kernel virtual memory area.
void kmalloc_init()
{
        mem_block_t *p;

        // Create only one hudge block                                  //
        p = (mem_block_t *)K_HEAP_START;
        p->magic = M_MAGIC;
        p->flags = M_FREE;
        p->size = K_HEAP_END - K_HEAP_START - sizeof(mem_block_t);
        p->owner = NULL;
}

//! \brief
//!     Allocate a memory block from the kernel memory area.
//!     This is a best-fit like allocator.
//! \param size The size of the block you want to allocate.
//! \exception NULL Out-of-memory.
//! \return A pointer to a memory area.
//! \note The memory area is not initialized when it's just allocated.

// NOTE!!! IF YOU WANT TO USE A FIRST-FIT LIKE ALLOCATOR FOR THE KERNEL //
// MEMORY AREA, YOU MUST CHANGE THE kmalloc(size_t size) FUNCTION WITH  //
// THIS ONE AND RECOMPILE THE KERNEL.
void *kmalloc(size_t size)
{
        mem_block_t *p, *p_best=NULL;
        dword IF = GET_IF();

        if (!size) return NULL; // Is the process crazy?! :-) //

        disable();

        // Round the size up to sizeof(mem_block_t); the        //
        // sizeof(mem_block_t) is the unit of allocation.       //
        size = ( size & -((uint32_t)sizeof(mem_block_t)) ) + sizeof(mem_block_t);

        // Explore the heap for the best-fit hole //
        p=(mem_block_t *)K_HEAP_START;
        while(p < (mem_block_t *)K_HEAP_END)
        {
                // Find a free block //
                if (p->flags == M_FREE)
                {
                        // This block is free... let's proceed //
                        if (p->size == size)
                        {
                                // Best fit block found! You're lucky! //
                                p_best = p;
                                break;
                        }
                        if (p->size > size)
                        {
                                // The hole is bigger than size...      //
                                // ...check if it's the best-fit hole!  //
                                if (p_best==NULL)
                                        p_best = p;
                                else
                                        if (p_best->size > p->size)
                                                p_best = p;
                        }
                }
                // Examine the next memory block //
                p = (void *)p+p->size+sizeof(mem_block_t);
        }

        // Have you found a free block?! //
        if (p_best == NULL)
        {
                // No free memory :( //
                SET_IF(IF);
                return NULL;
        }

        // Found, now allocate it! //
        p_best->magic = M_MAGIC;
        p_best->flags = M_ALLOC;
        p_best->owner = get_pid();

        if (p_best->size == size)
        {
                p_best = (void *)p_best + sizeof(mem_block_t);
                SET_IF(IF);
                // The block cover the size perfectly //
                return ((void *)p_best);
        }

        // Otherwise split the hole in two blocks //
        p = (void *)p_best + sizeof(mem_block_t) + size;
        p->magic = M_MAGIC;
        p->flags = M_FREE;
        p->size = p_best->size - size - sizeof(mem_block_t);
        p->owner = NULL;

        p_best->size = size;
        p_best = (void *)p_best + sizeof(mem_block_t);

        SET_IF(IF);
        // Return the best-fit pointer //
        return ((void *)p_best);
}

/*
//! \brief
//!     Allocate a memory block from the kernel memory area.
//!     This is a first-fit like allocator.
//! \param size The size of the block you want to allocate.
//! \exception NULL Out-of-memory.
//! \return A pointer to a memory area.
//! \note The memory area is not initialized when it's just allocated.

// NOTE!!! IF YOU WANT TO USE A FIRST-FIT LIKE ALLOCATOR FOR THE KERNEL //
// MEMORY AREA, YOU MUST CHANGE THE kmalloc(size_t size) FUNCTION WITH  //
// THIS ONE AND RECOMPILE THE KERNEL.
void *kmalloc(size_t size)
{
// This is a first-fit allocator for the kernel memory area.            //
// This function allocates size bytes and returns a pointer to the      //
// allocated memory. The memory is not cleaned.                         //

        mem_block_t *p, *p2;
        dword IF = GET_IF();

        if (!size) return NULL; // Is the process crazy?! :-)           //

        // Round the size up to sizeof(mem_block_t); the                //
        // sizeof(mem_block_t) is the unit of allocation.               //
        size = ( size & -((uint32_t)sizeof(mem_block_t)) ) + sizeof(mem_block_t);

        disable();

        // Let's start!                                                 //
        p = (mem_block_t *)K_HEAP_START;
        while(p < (mem_block_t *)K_HEAP_END)
        {
                if (p->flags == M_FREE)
                {
                        // We found a free block, now allocate it!      //
                        p->magic = M_MAGIC;
                        p->flags = M_ALLOC;
                        p->owner = get_pid();

                        if (p->size == size)
                        {
                                // The block cover the size perfectly,  //
                                // splitting is not required            //
                                p = (void *)p + sizeof(mem_block_t);

                                SET_IF(IF);

                                // Return the pointer                   //
                                return ((void *)p);
                        }

                        // Otherwise split the hole in two blocks       //
                        p2 = (void *)p + sizeof(mem_block_t) + size;
                        p2->magic = M_MAGIC;
                        p2->flags = M_FREE;
                        p2->size = p->size - size - sizeof(mem_block_t);
                        p2->owner = NULL;

                        p->size = size;
                        p = (void *)p + sizeof(mem_block_t);

                        SET_IF(IF);

                        // Return the pointer                           //
                        return ((void *)p);
                }

                // Examine the next memory block                        //
                p = (void *)p + p->size + sizeof(mem_block_t);
        }

        // Out of memory! Return 0...                                   //
        return(0);
}
*/

//! \brief Try to release physical frames occupied by the freed block.
//! \param ptr The pointer to deallocate.
static void deallocate(mem_block_t *ptr)
{
        dword start = PAGE_ALIGN_UP((dword)((void *)ptr + sizeof(mem_block_t)));
        dword end = PAGE_ALIGN((dword)((void *)ptr + sizeof(mem_block_t) + ptr->size));

        while(start < end)
        {
                if (*ADDR_TO_PDE(start) != NULL)
                {
                        delete_page(start);
                        start += PAGE_SIZE;
                }
                else
                        start = PAGE_DIR_ALIGN_UP(start);
        }
}

//! \brief
//!     Frees the memory space pointed by ptr, which must have
//!     been returned by a previous call to kmalloc(size_t size).
//! \param ptr The pointer you want to free.
void kfree(void *ptr)
{
        mem_block_t *p, *p2;
        dword IF = GET_IF();

        if (ptr == NULL) return;

        disable();

        // Point to the header                                          //
        p = (void *)ptr - sizeof(mem_block_t);

        if (p->magic != M_MAGIC) return; // Is the process crazy?! :)   //
        if (p->flags != M_ALLOC) return; // Crazy again?! :)            //

        // Free the block                                               //
        p->flags = M_FREE;
        p->owner = NULL;

        // Try to combine the block wih the next one...                 //
        p2 = (void *)p + p->size + sizeof(mem_block_t);

        if (p2 < (mem_block_t *)K_HEAP_END)
                if (p2->flags == M_FREE)
                {
                        // Let's merge the two blocks!                  //
                        p->size += p2->size + sizeof(mem_block_t);
                        p2->magic = NULL;
                }

        // Try to combine the block with the previous one...            //
        if (p != (mem_block_t *)K_HEAP_START)
        {
                // Find the previous block                              //
                p2 = (void *)K_HEAP_START;
                for(;;)
                {
                        if (((void *)p2 + p2->size + sizeof(mem_block_t)) == p)
                        {
                                // Block found!                         //
                                // Check if it's a free block           //
                                if (p2->flags == M_FREE)
                                {
                                        // Let's merge the two blocks!  //
                                        p2->size += (p->size + sizeof(mem_block_t));
                                        p->magic = NULL;
                                        p = p2;
                                }
                                break;
                        }
                        p2 = (void *)p2 + p2->size + sizeof(mem_block_t);
                }
        }
        // Release the physical space occupied by the block             //
        deallocate(p);

        SET_IF(IF);
}

//! \brief
//!     Return the size of the pointer \a ptr passed as argument.
//! \param ptr The pointer you want to know the size.
//! \exception NULL Invalid pointer \a ptr.
//! \return The size of the pointer \a ptr passed as argument.
int mem_sizeof(void *ptr)
{
// Return the size of the pointer "ptr", or NULL if an error occurs     //
        mem_block_t *p = ((mem_block_t *)ptr-1);

        if ( (p->magic == M_MAGIC) && (p->flags == M_ALLOC) )
                return( p->size );
        else
                return(NULL);
}

//! \brief Allocate some memory aligned to a boundary.
//! \param alignment The boundary.
//! \param size The size you want to allocate.
//! \exception NULL Out-of-memory.
//! \return
//!     A pointer to a memory area aligned to the boundary.
//!     The pointer is a \c aligned_mem_block_t pointer, so if you
//!     want to access to the data area of this pointer you must
//!     specify the \c p->start filed.
//! \note Use kfree(void *ptr) to free the allocated block.
void *kmemalign(size_t alignment, size_t size)
{
        mem_block_t *p, *p2;
        dword IF = GET_IF();

        // Cannot allocate memory with a size of zero                   //
        if ( !size )
                return(NULL);

        // Allocate the pointer                                         //
        p = kmalloc(size + alignment + 2*sizeof(mem_block_t));
        if ( p == NULL )
                return(NULL);

        // An alignment of zero is intended as a simple kmalloc(size)   //
        if ( alignment == 0 )
        {
                return(p);
        }

        // Check if the pointer is correcly aligned                     //
        if ( (size_t)(p) % alignment )
        {
                // Align the pointer p to the boundary.                 //
                disable();

                // Allocate the new block                               //
                p2 = p + 2;
                p2 = (mem_block_t *)ALIGN_UP((size_t)p2, alignment)  - 1;
                p2->magic = M_MAGIC;
                p2->flags = (p-1)->flags;
                p2->owner = (p-1)->owner;
                p2->size = mem_sizeof(p) - ((size_t)(p2+1) - (size_t)p);

                // Free the unused space                                //
                (p-1)->size = (size_t)p2 - (size_t)p;
                kfree(p);

                SET_IF(IF);

                return(p2+1);
        }
        else
                // The pointer p is already aligned to the boudary      //
                return(p);
}

//! \brief This is a routine for debug only.
//! It prints all the memory block headers.
//! \note Prints the result to the current console.
void dump_memory_map()
{
        mem_block_t *p = (mem_block_t *)K_HEAP_START;

        for(;;)
        {
                kprintf(
                        "\n\rp        = %#010x"
                        "\n\rp->magic = %s"
                        "\n\rp->flags = %#010x"
                        "\n\rp->size  = %u"
                        "\n\rp->owner = %i\n\r",
                        (dword)p + sizeof(mem_block_t),
                        (byte *)p->magic,
                        p->flags,
                        p->size,
                        p->owner);

                p = (void *)p + p->size + sizeof(mem_block_t);

                if (p >= (mem_block_t *)K_HEAP_END) break;

                // Wait for a key... //
                if (kgetchar() == CTRL_C) break;
        }
}

---