linux操作系统学习实践 －－－first fit分配算法的实现.

/* 还没有加入到现有的代码中进行测试.不过把first fit的核心代码提出来编写了模拟的内存分配.貌似没有什么问题 */
#include
#include
#include
#include
unsigned long max_low_pfn;
unsigned long min_low_pfn;
unsigned long highstart_pfn;
unsigned long highend_pfn;
unsigned long max_pfn;

static unsigned long bootmem_init_core(struct bootmem_data *bdata, unsigned long bootmap_start, \
                                    unsigned long startpfn, unsigned long endpfn)
{
    unsigned long bootmap_size;
    bootmap_size = ((endpfn - startpfn) + 7) / 8;
    bdata->boot_start_pfn = startpfn;
    bdata->boot_end_pfn = endpfn;
    bdata->boot_map = bootmap_start;
    bdata->boot_map_size = bootmap_size;
#if 1
    bdata->boot->last_offset = 0;
    bdata->boot->last_pfn = 0;
    bdata->boot->last_bit = 0;
#endif
    /* mark all the already-known page frames reserved */
    memset(bdata->boot_map, 0xff, bootmap_size);
    return bootmap_size;
}

    


void bootmap_init(void)
{
    struct bootmem_data *bdata = &contig_pg_data.bdata;
    struct e820_map *e_map = e820_map_table + 0;
    int i;
    int j;
/* high32?! */
    for(i = 0; i < e820_map_nr; i++, e_map++) {
        unsigned long start;
        int size;
        if(e_map->type != E820_TYPE_AVAIL)
            continue;
        start = PFN_UP(e_map->base_addr_low32);
        size = PFN_DOWN(e_map->len_low32);
        if(start < max_low_pfn && (start + size) > max_low_pfn)
            size = PFN_DOWN(max_low_pfn - start);
        if(start >= max_low_pfn)
            break;
        for(j = 0; j < size; j++)
            clear_bit(start + j, bdata);
        reserve_bootmem(__start, PFN_UP(__end - __start));
        reserve_bootmem(bdata->boot_map, PFN_UP(bdata->boot_map_size));
}

void reserve_bootmem(unsigned long phys_addr, unsigned long _size)
{
    struct bootmem_data *bdata = &contig_pg_data.bdata;
    unsigned long start = PFN_UP(phys_addr);
    int size = PFN_DOWN(_size);
    int i;
    for(i = 0; i < size; i++)
        set_bit(start + i; bdata->boot_mem);
}

unsigned long bootmem_init(unsigned long bootmap_start, unsigned long endpfn)
{
    return bootmem_init_core(&contig_pg_data.bdata, bootmap_start, 0, endpfn);
}


static void free_bootmem_core(struct bootmem_data *bdata, unsigned long pfn, \
                                                                                unsigned long nr_pfns)
{
    int i;
    for(i = 0;  i < nr_pfns; i++)
        if(test_and_set_bit(pfn + i, bdata->boot_map))
            BUG("try to free a page frame twice!\n");
}


void free_bootmem(unsigned long addr, unsigned long size)
{
    unsigned long pfn = virt_to_pfn(PFN_UP(addr));
    unsigned long nr_pfns = PFN_DOWN(size);
    nr_pfns >>= PAGE_SHIFT;
    free_bootmem_core(&contig_pg_dat.bdata, pfn, nr_pfns);
}




static void *alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size, \
                                                unsigned long align, unsigned long goal)
{
#if 0
    BUG_ON(!size);
    BUG_ON(align & (align - 1));
#endif
    int merged = 0;
    int start_over = 0;
    int i = 0;
    unsigned long start_bit, nr_bit, step;
    char *last_scan;
    void *addr;
    step = (align >> PAGE_SHIFT) ? : 1;
    if(!goal) {
        start_bit = bdata->last_pfn;
        last_scan = bdata->last_scan;
    } else {
        start_bit = ALIGN(goal, align);
        start_bit >>= PAGE_SHIFT;
        last_scan = bdata->boot_map;
    }
    nr_bit = PFN_UP(size);
    nr_bit >>= PAGE_SHIFT;
    while(1) {
        unsigned long map_size = bdata->boot_map_size;
try_again:
        if(step != 1)
            start_bit += ((i + step - 1) / step) * step;
        else
            start_bit += i;
        if(start_bit + nr_bit >= map_size / 8) {
            if(goal) {
                if(!start_over) {
                    start_over = 1;
                } else {
                    return NULL;
                }
                start_bit = ALIGN(goal, align);
                start_bit >>= PAGE_SHIFT;
                last_scan = bdata->boot_map;
            } else
                return NULL;
        }
        for(i = start_bit; i < start_bit + nr_bit; i++) {
            if(test_bit(i, last_scan)) {
                i = i - start_bit + 1;
                goto try_again;
            }
        }
        break;
    }
    /* check if we could merge */
    if(!PAGE_ALIGN(bdata->last_offset) && PFN_DOWN(bdata->last_offset) + 1 == start_bit \
            &&    (PAGE_SIZE - bdata->last_offset) > align) {
            merged = 1;
            start_bit--;
        if((size & PAGE_MASK) < (PAGE_SIZE - ALIGN(bdata->last_offset, align)))
            nr_bit--;
    }
    /* reserve the memory being allocated */
    for(i = 0;  i < nr_bit; i++)
        set_bit(start_bit + i, last_scan);
    if(merged)
        addr = (void *)((start_bit << PAGE_SHIFT) + ALIGN(bdata->last_offset, align));
    else
        addr = (void *)(start_bit << PAGE_SHIFT);
        /* update bootmem_data */
    bdata->last_offset = ((unsigned long)addr + size) & PAGE_MASK;
    bdata->last_pfn = start_bit;
    if(!goal)
        bdata->last_scan = bdata->boot_map + start_bit / 8;
    return addr;
}