Linux中的内存管理：实现首次适配算法。

Question

我有一个任务需要完成，尽管我已经尽力了，但无论我怎么努力，都无法得到最佳适配方案。下面是代码。为了实现最佳适配，我对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 函数中进行了打印。虽然对我来说没有任何意义，但我的函数被成功调用并返回，然后再次被调用并返回等等。但在某一点上，它被调用，打印了这个函数内部的语句，但没有打印其被调用者的语句，然后无限期地挂起。

任何帮助将不胜感激！ 谢谢。

- Aman Deep Gautam

---

如果在for循环中放置一个printk，它会持续打印吗？ - user7116

@sixlettervariables，您能否详细说明一下最后一句话。我不明白为什么它不会触发 if(slob_last(cur))。 - Aman Deep Gautam

@sixlettervariables：你不觉得循环由于cur=slob_next(cur)语句而必定会命中if(slob_last(cur))吗？如果此时我们找到了所需的空间，那就好，否则返回NULL。 - Aman Deep Gautam

我希望for循环是for(prev=NULL, cur=sp->freelist; cur ; prev=cur, cur=slob_next(cur)) { :: 在每次迭代中测试cur。如果slob_units()和slob_last()在NULL参数上（比如freelist为NULL）表现良好，那么这将不再需要。 - wildplasser

@AmanDeepGautam - 你有机会看这个了吗？ - phonetagger

Answer 1

我认为这里的代码不足以找出问题（也许可以在lxr.oss.org.cn/source/mm/slob.c中找到，但我没有检查）。但是我猜测您的问题可能是这样的：

某种情况下，您的链表中存在循环，因此调用slob_last(cur)永远不会返回true。（您的代码能够到达那行；除了段错误之外，没有什么早期的障碍。）我添加了一个调试函数来扫描列表，以查看它是否终止或具有循环，并在存在循环时打印出一条消息。然后我在您的函数中添加了对该函数的调用。如果您之前没有听说过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;
    }
.
.
.

- phonetagger

---

我使用了你的代码进行测试，但是没有发现任何循环，因为没有输出任何内容。非常抱歉让你等待，但你可能已经注意到我被其他任务占据了，所以无法抽出时间来完成这个任务（这个任务有一个较晚的截止日期）。感谢你所做的一切努力。 - Aman Deep Gautam

@AmanDeepGautam - 你是在告诉我我的代码没有找到循环，但是Alexander Atanasov的回答解决了你的问题吗？如果他的回答解决了你的问题，那么你一定有一个循环。 - phonetagger

@AmanDeepGautam - 你是否真的在slob_page_alloc()中添加了对slob_debug_detect_loop()的调用，还是只添加了调试函数但忘记调用它了？ - phonetagger

没有我添加调用它。我的感觉是由于prev->next = best_fit->next，空闲列表之间的空间就丢失了。基本上，我认为挂起是由于代码中发生的内存泄漏引起的。我真的不认为会有循环形成。我希望听到您的意见。 - Aman Deep Gautam

@AmanDeepGautam - 好的，我能想到的唯一一件事就是你的freelist由于你的bug而被减少到了零...并且sp->freelist为空，而slob_last(cur)如果cur==NULL则不会返回true。但是如果是这种情况，我认为循环检测器仍然会检测到一个循环。奇怪。 - phonetagger

@AmanDeepGautam - 如果你的bug已经修复，太好了。我就不会再烦你了。 - phonetagger

Answer 2

问题在于，由于您没有在找到best_fit时中断，而是在slob_last(cur)处中断，因此prev指针是错误的。best_fit指针是最后一个best_fit，但prev是上一个best_fit的prev。

稍后在代码中，假定prev是best_fit的前一个条目，并对列表进行修改。当列表混乱时，会导致无限循环。

- Alexander Atanasov