美文网首页
buddy algorithm

buddy algorithm

作者: 101dog | 来源:发表于2017-04-25 20:17 被阅读92次

there is a global array, it stores the head of link of several pages which has different numbers

// from 2^0 to 2^10
static free_area_t free_area[MAX_ORDER+1];
#define free_list(x) (free_area[x].free_list)
#define nr_free(x) (free_area[x].nr_free)

something bad is not as bad as you think, it may do some good in some ways you don't notice

1.buddy_init_memmap()

static void buddy_init_memmap(struct Page *base, size_t n)
{
    struct Page *p = base;
    for (; p != base + n; p++) {
        p->flags = p->order = 0;
    }
    p = base;
    size_t order = MAX_ORDER, order_size = (1<<order);
    while (n != 0) {
        while(n >= order_size) {
            p->order = order;
            list_add(&free_list(order), &(p->page_link));
            p += order_size;
            n -= order_size;
            nr_free(order)++;

            cprintf("list order=%d ++\n", order);
        }
        --order; 
        order_size >>= 1;
    }
}

2.alloc_pages()

static struct Page * buddy_alloc_pages(size_t n)
{
    if(n == 0)return NULL;
    size_t order = getorder(n), order_size = (1<<order);
    cprintf("allocorder:%d\n", order);
    struct Page *page = buddy_alloc_pages_sub(order);
    if(page != NULL && n!=order_size) {
        free_pages(page+n, order_size-n);
    }
    return page;
}
static inline struct Page* buddy_alloc_pages_sub(size_t order)
{
    cprintf("alloc_sub_order:%d\n", order);
    if(order>MAX_ORDER)
        cprintf("buddy_alloc_page_sub order ERROR\n");
    for(size_t i=order; i<=MAX_ORDER; i++) {
        if(!list_empty(&free_list(i))) {
            cprintf("i:%d\n", i);
            list_entry_t *le = list_next(&free_list(i));
            struct Page *page = tostruct(le, struct Page, page_link);
            nr_free(i) --;
            list_del(le);
            size_t size = 1 << i;
            while(i > order) {
                i--;
                size >>= 1;
                struct Page * buddy = page+size;
                buddy->order = i;
                nr_free(i) ++;
                cprintf("i2:%d, nr_free(i):%d ", i, nr_free(i));
                list_add(&free_list(i), &(buddy->page_link));
            }
            return page;
        }
    }
    return NULL;

}

3.free_pages()

static void buddy_free_pages_sub(struct Page *base, size_t order)
{
    struct Page * p=base;
    p->order = order;
    size_t i=order, flag=0;

    while(i<MAX_ORDER) {
        list_entry_t * le = list_next(&free_list(i));
        while(1) {
            if(le == &free_list(i)) {
                flag = 1;
                break;
            }
            struct Page * buddy = tostruct(le, struct Page, page_link);
            le = list_next(le);
            size_t p_size = 1<<p->order, buddy_size = 1<<buddy->order;
            if(p == buddy+buddy_size) {
                list_del(&(buddy->page_link));
                nr_free(i) --;
                p = buddy;
                p->order ++;
                cprintf("left match\n");
                break;
            }
            else if(p+p_size == buddy) {
                list_del(&(buddy->page_link));
                nr_free(i) --;
                p->order ++;
                cprintf("right match\n");
                break;
            }
            else {
                flag = 1;
                break;
            }
        }
        if(flag == 1) break;
        cprintf("i3:%d ", i);
        i++;
    }
    list_add(&free_list(i), &(p->page_link));
    nr_free(i)++;
    cprintf("i4:%d nr_free(i):%d\n", i, nr_free(i));
}
static void buddy_free_pages(struct Page *base, size_t n)
{
    cprintf("buddy_free_pages base:%x n:%d  ", base, n);
    if (n==1) {
        buddy_free_pages_sub(base, 0);
    }
    else {
        size_t i=0, size = 1;
        while(n>=size) {
            i++;
            size <<=1;
        }
        while(n!=0) {
            while(n<size) {
                i--;
                size>>=1;
            }
            base->order = i;
            buddy_free_pages_sub(base, i);
            base += size;
            n -= size;
        }
    }
}

相关文章

  • buddy algorithm

    there is a global array, it stores the head of link of se...

  • Buddy,Buddy,还是Buddy

    (本文可能不适合国内教育环境) 对于刚进入学校的低年级孩子,怎样才能让他每天开开心心的愿意上学,可能是一个让很多家...

  • Buddy懵圈记(77)

    (七十七) 羞羞Buddy Buddy喜欢车,怎么和男人一样喜欢这些东西,这是因为Buddy是Boy?...

  • 不可低估了狗狗的智商

    狗狗Buddy很喜欢猫罐头,聪明的Buddy每天猫在桌子上吃罐头的时候,Buddy都会蹲在椅子上等候,如果主人离开...

  • Buddy懵圈记(二二九)

    (二二九)热情过度的Buddy 每次主人下班回家,Buddy都会跳着脚的迎接。周四晚上主人下班回来,Buddy听见...

  • Buddy Training Lesson 1

    课程内容:Clarify buddy 程序的基本概念 Agenda: 1 buddy程序的目标 2 junior ...

  • Buddy

    这几天,经历了一个Week3。回想起过去的3年多将近4年,人生的道路上不乏你的身影。。。 回想...

  • Buddy Training Summary

    Buddy是什么 buddy vs buddeeThoughtWorks会为每一位新加入的同事(可以是senior...

  • Buddy懵圈记(24)

    (二十四) 猫食 Buddy主人家除了Buddy和狗弟帅哥Bubble以及儿子Baby外,还...

  • Buddy懵圈记(10)

    (十) 加锁 咚咚咚清晨Buddy被一阵敲门声惊醒,汪汪汪Buddy叫着跳起来向大门...

网友评论

      本文标题:buddy algorithm

      本文链接:https://www.haomeiwen.com/subject/ydkxzttx.html