buddy_alloc.c

Go to the documentation of this file.

/*
 * kernel_super/memory/buddy_alloc.c
 *
 * Copyright (c) 2003-2004 Lukasz Dembinski <dembol@nasa.com.pl>
 * All Rights Reserved
 * 
 * Date:        2004/09
 * Author:      Lukasz Dembinski
 * Info:        buddy_alloc.c core file
 * Contact:     mailto: <dembol@nasa.com.pl>
 *
 */
 
#include <agnix/agnix.h>
#include <asm/bitops.h>
#include <agnix/memory.h>
#include <agnix/panic.h>
#include <agnix/console.h>

#define MOD_NAME        "MEM: "
#define NO_PAGE         0

struct buddy_allocator_s buddy_alloc_normal = {
    .buddy_name                 = "Normal area buddy allocator",
    .buddy_alloc_req_areas      = BUDDY_ALLOC_NORMAL_AREAS 
};

struct buddy_allocator_s buddy_alloc_dma = {
    .buddy_name                 = "DMA area buddy allocator",
    .buddy_alloc_req_areas      = BUDDY_ALLOC_DMA_AREAS 
};

extern struct allocator_s main_alloc;
extern void (*put_free_pages_fn)(u32 addr, u8 order);
extern u32  (*get_free_pages_fn)(u8 order);
extern void (*put_free_dma_pages_fn)(u32 addr, u8 order);
extern u32  (*get_free_dma_pages_fn)(u8 order);
struct page_desc_s *system_pages;

void buddy_put_free_pages(struct buddy_allocator_s *buddy_alloc, u32 addr, u8 order)
{
    u8 start_order;
    u32 bitmap_idx;
    struct buddy_area_s *area = &buddy_alloc->buddy_area[order];
    struct page_desc_s *page_desc;
    struct page_desc_s *page_buddy_desc;
    u32 page_idx = virt_to_page(addr);
    u32 page_buddy_idx;
    u32 page_mask;
    u32 flags;

    spin_lock_irqsave(&buddy_alloc->buddy_lock, flags);

    page_mask  = (~0UL) << order;
    for (start_order = order; start_order < buddy_alloc->buddy_alloc_req_areas; start_order++) {
        bitmap_idx = page_idx >> (start_order + 1);

        if (!test_and_change_bit(bitmap_idx, area->area_bitmap)) {
            break;
        }
        
        page_buddy_idx  = page_idx ^ (1 + ~page_mask);
        page_buddy_desc = &system_pages[page_buddy_idx];
        list_del(&page_buddy_desc->page_list);
        area->free_units--;
        
        area++;
        page_mask <<= 1;
        page_idx &= page_mask;
    }

    page_desc = &system_pages[page_idx];
    list_add(&page_desc->page_list, &area->area_list);
    area->free_units++;
    
    spin_unlock_irqrestore(&buddy_alloc->buddy_lock, flags);
}

struct page_desc_s *buddy_get_free_pages_back(struct buddy_allocator_s *buddy_alloc, u32 order, u32 cur_order)
{
    struct buddy_area_s *area = &buddy_alloc->buddy_area[cur_order];
    struct page_desc_s *page_desc = NULL;
    u32 page_idx;
    u32 page_half_idx;
    u32 back_order;
    u32 area_size;

    page_desc = list_entry(area->area_list.next, struct page_desc_s, page_list);
    page_idx  = virt_to_page(page_desc->address_virt);
    list_del(area->area_list.next);
    change_bit(page_idx >> (cur_order + 1), area->area_bitmap);
    area->free_units--;

    for (back_order = cur_order - 1; back_order >= order; back_order--) {
        area = &buddy_alloc->buddy_area[back_order];
        area_size = 1 << back_order;
        page_idx  = virt_to_page(page_desc->address_virt);
        page_half_idx = page_idx + area_size;
        list_add(&page_desc->page_list, &area->area_list);
        area->free_units++;

        change_bit(page_idx >> (back_order + 1), area->area_bitmap);
        page_desc = &system_pages[page_half_idx];
        
        if (back_order == order)
            break;
    }   
        
    return page_desc;
}

u32 buddy_get_free_pages(struct buddy_allocator_s *buddy_alloc, u8 order)
{
    struct buddy_area_s *area = &buddy_alloc->buddy_area[order];
    struct page_desc_s *page_desc = NULL;
    u32 cur_order;
    u32 flags;
    u8  *ptr;
    int i;
        
    spin_lock_irqsave(&buddy_alloc->buddy_lock, flags);

    for (cur_order = order; cur_order < buddy_alloc->buddy_alloc_req_areas; cur_order++) {

        if (!list_empty(&area->area_list)) {
            if (cur_order == order) {
                page_desc = list_entry(area->area_list.next, struct page_desc_s, page_list);
                change_bit(virt_to_page(page_desc->address_virt) >> (order + 1), area->area_bitmap);
                list_del(area->area_list.next);
                area->free_units--;
            } else {
                page_desc = buddy_get_free_pages_back(buddy_alloc, order, cur_order);
            }    
            
            break;
        }
        area++;
    }
    
    spin_unlock_irqrestore(&buddy_alloc->buddy_lock, flags);

    if (cur_order == buddy_alloc->buddy_alloc_req_areas)
        return 0;

    if (page_desc->address_virt < 0xc0000000) {
        printk("address < 0xc0000000\n");
        for (i = 0; i < 1000000000; i++);
    }

    ptr = (u8 *)page_desc->address_virt;
    
    for (i = 0; i < PAGE_SIZE; i++) {
        ptr[i] = 0;
    }
        
    return page_desc->address_virt;
}

u32 buddy_get_free_pages_wrapper(u8 order)
{
    return buddy_get_free_pages(&buddy_alloc_normal, order);
}

void buddy_put_free_pages_wrapper(u32 address, u8 order)
{
    return buddy_put_free_pages(&buddy_alloc_normal, address, order);
}

u32 buddy_get_free_dma_pages_wrapper(u8 order)
{
    return buddy_get_free_pages(&buddy_alloc_dma, order);
}

void buddy_put_free_dma_pages_wrapper(u32 address, u8 order)
{
    return buddy_put_free_pages(&buddy_alloc_dma, address, order);
}

void buddy_alloc_fn_init(void)
{
    get_free_pages_fn     = buddy_get_free_pages_wrapper;    
    put_free_pages_fn     = buddy_put_free_pages_wrapper;    
    get_free_dma_pages_fn = buddy_get_free_dma_pages_wrapper;    
    put_free_dma_pages_fn = buddy_put_free_dma_pages_wrapper;    
}

int buddy_alloc_areas_init(struct allocator_s *main_alloc, struct buddy_allocator_s *buddy_alloc)
{
    int i;
    int area_size_pages = 0;
    
    for (i = 0; i < buddy_alloc->buddy_alloc_req_areas; i++) {

        area_size_pages = (((main_alloc->mem_size_pages + (1 << 3) - 1) >> 4) + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
        if ((buddy_alloc->buddy_area[i].area_bitmap = (u32 *)bin_get_free_pages(area_size_pages)) == NULL) {
            kernel_panic(MOD_NAME "buddy_alloc_init() failed\n");
        }

        INIT_LIST_HEAD(&buddy_alloc->buddy_area[i].area_list);
        buddy_alloc->buddy_area[i].free_units = 0;      
    }    
    
    return 0;
}

void buddy_alloc_pages_init(struct allocator_s *main_alloc)
{
    int system_pages_size;
    int i;
    
    system_pages_size = ((main_alloc->mem_size_pages * sizeof(struct page_desc_s)) + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
    
    if ((system_pages = (struct page_desc_s *)bin_get_free_pages(system_pages_size)) == NULL) {
        kernel_panic(MOD_NAME "buddy_alloc_pages_init() failed\n");
    }    
    
    for (i = 0; i < main_alloc->mem_size_pages; i++) {
        system_pages[i].address_phys = (u32)(i << PAGE_SHIFT);
        system_pages[i].address_virt = phys_to_virt(system_pages[i].address_phys);

        INIT_LIST_HEAD(&system_pages[i].page_list);
    }
}

void buddy_alloc_print_units(struct buddy_allocator_s *buddy_alloc, int broadcast)
{
    struct buddy_area_s *area;
    int i;
    u32 flags;
    
    if (broadcast)
        printk("\n" MOD_NAME "%s free units\n", buddy_alloc->buddy_name);
    else
        printf("\n" MOD_NAME "%s free units\n", buddy_alloc->buddy_name);

    spin_lock_irqsave(&buddy_alloc->buddy_lock, flags);

    for (i = 0; i < buddy_alloc->buddy_alloc_req_areas; i++) {
        area = &buddy_alloc->buddy_area[i];
        if (broadcast)
            printk(MOD_NAME "\torder %02d -> %d free units\n", i, area->free_units);
        else
            printf(MOD_NAME "\torder %02d -> %d free units\n", i, area->free_units);
    }
    
    if (broadcast)
        printk("\n");
    else
        printf("\n");
    
    spin_unlock_irqrestore(&buddy_alloc->buddy_lock, flags);
}

u32 buddy_alloc_free(struct buddy_allocator_s *buddy_alloc)
{
    struct buddy_area_s *area;
    u32 page_order;
    u32 free;
    u32 flags;
    int i;
    
    spin_lock_irqsave(&buddy_alloc->buddy_lock, flags);

    free = 0;
    page_order = 1;
    for (i = 0; i < buddy_alloc->buddy_alloc_req_areas; i++) {
        area = &buddy_alloc->buddy_area[i];
        free += area->free_units * page_order;
        page_order <<= 1;
    }
    
    spin_unlock_irqrestore(&buddy_alloc->buddy_lock, flags);
    
    return free;
}

void __init buddy_alloc_init(void)
{
    spin_lock_init(&buddy_alloc->buddy_lock);

    buddy_alloc_areas_init(&main_alloc, &buddy_alloc_dma);
    buddy_alloc_areas_init(&main_alloc, &buddy_alloc_normal);
    buddy_alloc_pages_init(&main_alloc);
    buddy_alloc_fn_init();
    bin_put_all_free_pages();
    buddy_alloc_print_units(&buddy_alloc_dma, 1);
    buddy_alloc_print_units(&buddy_alloc_normal, 1);
}

void buddy_alloc_print_stats(void)
{
    buddy_alloc_print_units(&buddy_alloc_dma, 0);
    buddy_alloc_print_units(&buddy_alloc_normal, 0);
}

void buddy_alloc_print_free(void)
{
    u32 free_dma, free_normal;

    free_dma    = buddy_alloc_free(&buddy_alloc_dma);
    printf("DMA free:     %d KB\n", free_dma << (PAGE_SHIFT - 10));

    free_normal = buddy_alloc_free(&buddy_alloc_normal);
    printf("Normal free:  %d KB\n", free_normal << (PAGE_SHIFT - 10));
    
    printf("Total free:   %d KB\n", (free_normal + free_dma) << (PAGE_SHIFT - 10));
}