first fit内存分配算法的测试.

#include
#include
#include

#define PAGE_SIZE 4096UL
#define PAGE_OFFSET 0UL
#define PAGE_SHIFT 12UL
#define PAGE_MASK ((1 << PAGE_SHIFT) - 1)

#define PAGE_ALIGN(addr) \
        ((addr) & (~PAGE_MASK))

#define phys_to_pfn(phys_addr) \
        ((phys_addr) >> PAGE_SHIFT)

#define virt_to_pfn(virt_addr) \
        phys_to_pfn(__pa(virt_addr))
#define ALIGN(a, align) \
        (((a) + (align) - 1UL) & (~((align) - 1UL)))
/* NOTE!!! */
#define PFN_UP(addr) \
        phys_to_pfn((((addr) + PAGE_SIZE - 1) & (~PAGE_MASK)))
#define PFN_DOWN(addr) \
        phys_to_pfn(((addr) & (~PAGE_MASK)))


struct bootmem_data {
    unsigned long boot_start_pfn;
    unsigned long boot_end_pfn;
    char *boot_map;
    unsigned long boot_map_size;
    unsigned long last_offset;
    unsigned long last_pfn;
    char *last_scan;
};

/* stolen from linux */
#define LOCK_PREFIX ""
#if __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 1)
/* Technically wrong, but this avoids compilation errors on some gcc
   versions. */
#define BITOP_ADDR(x) "=m" (*(volatile long *) (x))
#else
#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))
#endif



static inline int test_bit(int nr, volatile const unsigned long *addr)
{
    int oldbit;
    asm volatile("bt %2,%1\n\t"
             "sbb %0,%0"
             : "=r" (oldbit)
             : "m" (*(unsigned long *)addr), "Ir" (nr));
    return oldbit;
}
static inline void set_bit(unsigned int nr, volatile unsigned long *addr)
{
    asm volatile(LOCK_PREFIX "bts %1,%0"
        : BITOP_ADDR(addr) : "Ir" (nr) : "memory");    
}

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);
    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 allocator */
    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;
/* output this information should be enough, I hope so */
    printf("#######################first fit allocator#####################\n");
    printf("requested size: %ld, requested alignment %ld, requested starting addr %ld\n", size, align, goal);
    printf("start_bit %ld, addr %ld, size %ld, last_pfn %ld, last_offset %ld\n", start_bit, addr, size, bdata->last_pfn, bdata->last_offset);
    return addr;
}

int main()
{
    struct bootmem_data bdata;
    memset(&bdata, 0, sizeof(bdata));
    bdata.boot_map = (char *)malloc(sizeof(char) * 1024);
    bdata.boot_end_pfn = 1024 * 8;
    bdata.boot_map_size = 1024;
    bdata.last_scan = bdata.boot_map;
    bdata.last_offset = 0;
    bdata.last_pfn = 0;
    memset(bdata.boot_map, 0x00, 1024);
/* it's hard to decide the params to pass */
    alloc_bootmem_core(&bdata, 4, 1, 0);
    alloc_bootmem_core(&bdata, 10, 32, 0);
    alloc_bootmem_core(&bdata, 9600, 4096, 0);
    alloc_bootmem_core(&bdata, 12344, 32, 4096*5);
    alloc_bootmem_core(&bdata, 444444, 128, 4096*12);
    return 0;
}