memory management in linux: implementing first fit

Question

I have assignment and I have tried to to the best I can but no matter what I try I am unable to get the best fit scheme. The following is the code. To implement best fit, I made changes to slob_page_alloc function. The code is given below:

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;
}

When I configure the kernel with this scheme, it just hangs at some place.

Debugging:

I have done printing at some place in this function and also in slob_alloc function. Though it does not make any sense to me, but my function is called many times and successfully returns and then is again called and it returns and so on. but at one point it gets called prints the statements inside this function but does not print the statements from its callee and just hangs there indefinitely.

Any help is appreciated!! Thanks.

Answer 1

The problem is that the prev pointer is wrong since you do not break when you find the best_fit but break on the slob_last(cur). best_fit pointer is last best_fit, but the prev is prev for last.

Later in the code list-s are modified with the assumption that prev is best_fit's prev entry. When lists get messed you get an endless loop.

Answer 2

I think there's not enough code here to figure out what's wrong (maybe there is at lxr.oss.org.cn/source/mm/slob.c, but I didn't check). But here's what I'm guessing is your problem:

Somehow you're getting a loop (or 'cycle') in your linked list, so your call to slob_last(cur) will never return true. (Your code does get to that line; there's nothing earlier, short of a segfault, that would be preventing it.) I've added a debugging function that will scan the list to see if it terminates or has a loop, and prints out a message if there's a loop. Then I added a call to that function in your function. If you've not heard about Bob Floyd's pet tortoise & hare before, Google for Bob Floyd and linked list loop detection (or linked list cycle detection). I haven't tested my code below, but I think I coded it right. If it detects a loop, then look into the logic that adds slob_t's to the list, and look at the code that takes them off of the list. There's gotta be some condition where it either adds something to the list improperly or takes something off the list improperly. If you DO find a loop here, add additional calls to other locations... immediately before & immediately after every point in your code where you modify the list... That way you can narrow down what part of your code is causing the loop.

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;
    }
.
.
.