4

我有任务，我已尽我所能，但无论我尝试什么，我都无法获得最合适的方案。以下是代码。为了实现最佳拟合，我对功能进行了更改slob_page_alloc。代码如下：

static void *slob_page_alloc(struct page *sp, size_t size, int align)
{
    slob_t *prev, *cur, *aligned = NULL, *best_fit=NULL;
    /* See SLOB_UNITS defination for meaning of macro. units is required 
     * number OF units.*/
    int delta = 0, units = SLOB_UNITS(size);
    unsigned long frag_size = -1UL;
    /*Iterate throught the whole page to find best fit*/
    //printk("Before the for loop\n");
    printk("Starting slob_page_alloc execution\t"); 
    for(prev=NULL, cur=sp->freelist; ; prev=cur, cur=slob_next(cur)) {
        slobidx_t avail = slob_units(cur);
        if(align) {
            aligned = (slob_t *)ALIGN((unsigned long)cur, align);
            delta = aligned - cur;
        }
        if(avail >= delta+units) {
            if( frag_size > avail-units ) {
                frag_size = avail-units;
                best_fit = cur;
            }
        }
        if(slob_last(cur))
            break;
    }

    //printk("after the for loop.\n");
    if(best_fit) {
        slobidx_t avail = slob_units(best_fit);
        //printk("best fit found\n");

        if (align) {
            aligned = (slob_t *)ALIGN((unsigned long)best_fit, align);
            delta = aligned - best_fit;
        }
        if (avail >= units + delta) { /* room enough? */
            slob_t *next;

            if (delta) { /* need to fragment head to align? */
                next = slob_next(best_fit);
                /*Update the newly fragmented slob*/
                set_slob(aligned, avail - delta, next);
                /* Update the lod slob about reduced size 
                 * and new next slob*/
                set_slob(best_fit, delta, aligned);
                prev = best_fit;
                best_fit = aligned;
                avail = slob_units(best_fit);
            }

            next = slob_next(best_fit);
            if (avail == units) { /* exact fit? unlink. */
                if (prev)
                    set_slob(prev, slob_units(prev), next);
                else
                    sp->freelist = next;
            } else { /* fragment */
                if (prev)
                    set_slob(prev, slob_units(prev), best_fit + units);
                else
                    sp->freelist = best_fit + units;
                set_slob(best_fit + units, avail - units, next);
            }

            sp->units -= units;
            if (!sp->units)
                clear_slob_page_free(sp);
            printk("Returned from slob_page_alloc\t");
            return best_fit;
        }
    }
    printk("Returned from slob_page_alloc\t");
    return NULL;
}

当我用这个方案配置内核时，它只是挂在某个地方。

调试：

我已经在此功能的某个地方以及功能中完成了打印slob_alloc。虽然这对我没有任何意义，但我的函数被多次调用并成功返回，然后再次被调用并返回等等。但在某一时刻，它被调用会打印此函数内的语句，但不会打印其被调用者的语句，而是无限期地挂在那里。

任何帮助表示赞赏！谢谢。

4

2 回答 2

4

我认为这里没有足够的代码来找出问题所在（可能在 lxr.oss.org.cn/source/mm/slob.c，但我没有检查）。但我猜这是你的问题：

不知何故，您在链接列表中获得了一个循环（或“循环”），因此您对 slob_last(cur) 的调用将永远不会返回 true。（您的代码确实到达了该行；没有什么更早的，除了段错误，可以阻止它。）我添加了一个调试函数，它将扫描列表以查看它是否终止或有一个循环，并打印出来如果有循环，则发出消息。然后我在你的函数中添加了对该函数的调用。如果您之前没有听说过 Bob Floyd 的宠物龟兔赛跑，请使用 Google for Bob Floyd 和链表循环检测（或链表循环检测）。我没有在下面测试我的代码，但我认为我编码它是正确的。如果它检测到循环，则查看将 slob_t 添加到列表的逻辑，并查看将它们从列表中删除的代码。那里' 必须是某种情况，它要么不正确地将某些内容添加到列表中，要么不正确地从列表中删除某些内容。如果您确实在这里找到了一个循环，请添加对其他位置的额外调用...在您修改列表的代码中的每个点之前和之后...这样您可以缩小代码的哪一部分导致循环.

static void slob_debug_detect_loop(slob_t *list_head, const char* debug_location)
{
    // Bob Floyd's pet tortoise & hare, both born in 1967...
    slot_t *hare = list_head;
    slob_t *tortoise = list_head;
    int tortoise_pacer=0;
    while (!slob_last(hare))
    {
        hare = slob_next(hare);
        if (++tortoise_pacer&1)
            tortoise = slob_next(tortoise);
        if (tortoise_pacer>2 && hare==tortoise)
        {
            printk("LINKED LIST LOOP DETECTED at %s!\n", debug_location);
            return;
        }
    }
}



static void *slob_page_alloc(struct page *sp, size_t size, int align)
{
    slob_t *prev, *cur, *aligned = NULL, *best_fit=NULL;
    /* See SLOB_UNITS defination for meaning of macro. units is required
    * number OF units.*/
    int delta = 0, units = SLOB_UNITS(size);
    unsigned long frag_size = -1UL;
    /*Iterate throught the whole page to find best fit*/
    //printk("Before the for loop\n");
    printk("Starting slob_page_alloc execution\t");
    slob_debug_detect_loop(sp->freelist, "before best-fit detection loop"); // ++++++++++
    for(prev=NULL, cur=sp->freelist; ; prev=cur, cur=slob_next(cur)) {
        slobidx_t avail = slob_units(cur);
        if(align) {
            aligned = (slob_t *)ALIGN((unsigned long)cur, align);
            delta = aligned - cur;
        }
        if(avail >= delta+units) {
            if( frag_size > avail-units ) {
                frag_size = avail-units;
                best_fit = cur;
            }
        }
        if(slob_last(cur))
            break;
    }
.
.
.
于 2012-12-08T08:10:26.090 回答
2

问题是 prev 指针是错误的，因为当你找到 best_fit 时你没有中断，而是在 slob_last(cur) 上中断。best_fit 指针是 last best_fit，但 prev 是 last 的 prev。

稍后在代码列表中修改为 prev 是 best_fit 的 prev 条目的假设。当列表变得混乱时，您会陷入无限循环。

于 2012-12-12T16:40:24.177 回答