[Lguest] [PATCH 1/1] Least Recently Used pgdirs

[Rusty Russell]

On Tue, 2007-08-14 at 00:06 -0500, Jason Yeh wrote:
> Hi all,
> 
> After seeing the code comment "Choosing the Least Recently Used might be 
> better, but this is easy" in function new_pgdir, I decided to give it a 
> try.

Hi Jason!

	Thanks for the patch.  It was mangled by your mailer a little, but I'll
comment based on what I can see.  Note that I always like to nitpick
patches: most of my comments are "how I would have done it" rather than
"this is how it *must* be done".

	I think the benchmark which might gain most from this is a kernel
compile, so that might be worth timing.

> @@ -357,7 +361,7 @@ static void flush_user_mappings(struct lguest *lg, 
> int idx)
>     unsigned int i;
>     /* Release every pgd entry up to the kernel's address. */
>     for (i = 0; i < vaddr_to_pgd_index(lg->page_offset); i++)
> -        release_pgd(lg, lg->pgdirs[idx].pgdir + i);
> +        release_pgd(lg, lg->pgdir_cur->pgdir + i);   }
> 
> /* The Guest also has a hypercall to do this manually: it's used when a 
> large
> @@ -365,51 +369,68 @@ static void flush_user_mappings(struct lguest *lg, 
> int idx)
> void guest_pagetable_flush_user(struct lguest *lg)
> {
>     /* Drop the userspace part of the current page table. */
> -    flush_user_mappings(lg, lg->pgdidx);
> +    flush_user_mappings(lg, 0);

Seems like the "idx" argument to flush_user_mappings isn't used any
more, but I think it should become a pgdir ptr.

> /* We keep several page tables.  This is a simple routine to find the page
>  * table (if any) corresponding to this top-level address the Guest has 
> given
>  * us. */
> -static unsigned int find_pgdir(struct lguest *lg, unsigned long pgtable)
> +static struct pgdir * find_pgdir_from_list(struct lguest *lg, unsigned 
> long pgtable)

Comment should be enhanced to point out that if we find one we shuffle
it to the front.

> {
> -    unsigned int i;
> -    for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
> -        if (lg->pgdirs[i].cr3 == pgtable)
> +    struct pgdir *p, *rpgdir = NULL;
> +   +    list_for_each_entry(p, &lg->pgdir_list, list) {
> +        if (p->cr3 == pgtable) {
> +            rpgdir  = p;
> +            list_move(&rpgdir->list, &lg->pgdir_list);
>             break;
> -    return i;
> +        }
> +    }
> +    return rpgdir;
> }

This is probably neater without the variable rpgdir: just return p
inside the loop, and NULL outside.

> +
> /*H:435 And this is us, creating the new page directory.  If we really do
>  * allocate a new one (and so the kernel parts are not there), we set
>  * blank_pgdir. */
> -static unsigned int new_pgdir(struct lguest *lg,
> +static struct pgdir * new_pgdir(struct lguest *lg,
>                   unsigned long cr3,
>                   int *blank_pgdir)
> {
>     unsigned int next;
> +    struct pgdir *newpgdir, *tmp;
> 
> -    /* We pick one entry at random to throw out.  Choosing the Least
> -     * Recently Used might be better, but this is easy. */
> -    next = random32() % ARRAY_SIZE(lg->pgdirs);
> -    /* If it's never been allocated at all before, try now. */
> -    if (!lg->pgdirs[next].pgdir) {
> -        lg->pgdirs[next].pgdir = (spgd_t *)get_zeroed_page(GFP_KERNEL);
> -        /* If the allocation fails, just keep using the one we have */
> -        if (!lg->pgdirs[next].pgdir)
> -            next = lg->pgdidx;
> -        else
> -            /* This is a blank page, so there are no kernel
> -             * mappings: caller must map the stack! */
> -            *blank_pgdir = 1;
> +    /* Check if we reach the maximum number of pgdirs we can hold.
> +     * Reuse the Least Recently Used one if we have. */
> +    if (lg->pgdir_list_size > PGDIR_MAX)  {
> +        newpgdir= list_entry(lg->pgdir_list.prev, struct pgdir, list);
> +        list_move(&newpgdir->list, &lg->pgdir_list);

I prefer the name "num_pgdirs" to "pgdir_list_size".  I also wonder if
it might be worth experimenting with *not* moving the LRU to the head at
this point, only when it's re-used (imagine lots of thrashing).
Benchmarking will show, I guess.

> +    } else {
> +        /* If it's never been allocated at all before, try now. */
> +        newpgdir = kmalloc(sizeof(struct pgdir), GFP_KERNEL);
> +        if (!newpgdir)
> +            goto out;
> +
> +        newpgdir->pgdir = (spgd_t *)get_zeroed_page(GFP_KERNEL);
> +        if (!newpgdir)
> +            kill_guest(lg, "failed to get zeroed page");
> +   +        list_add(&newpgdir->list, &lg->pgdir_list);
> +        lg->pgdir_list_size++;
> +        /* This is a blank page, so there are no kernel
> +         * mappings: caller must map the stack! */
> +        *blank_pgdir = 1;
>     }
> +
> +    /* Change the current pgd pointer to the new one. */
> +    lg->pgdir_cur = newpgdir;
>     /* Record which Guest toplevel this shadows. */
> -    lg->pgdirs[next].cr3 = cr3;
> +    lg->pgdir_cur->cr3 = cr3;
>     /* Release all the non-kernel mappings. */
> -    flush_user_mappings(lg, next);
> -
> -    return next;
> +    flush_user_mappings(lg, 0);

OK, this flush_user_mappings() only works because you set lg->pgdir_cur
here, as well as:


> +out:
> +    return newpgdir;
> }
> 
> /*H:430 (iv) Switching page tables
> @@ -418,19 +439,23 @@ static unsigned int new_pgdir(struct lguest *lg,
>  * top-level pgdir).  This happens on almost every context switch. */
> void guest_new_pagetable(struct lguest *lg, unsigned long pgtable)
> {
> -    int newpgdir, repin = 0;
> +    int repin = 0;
> +    struct pgdir * newpgdir;   
>     /* Look to see if we have this one already. */
> -    newpgdir = find_pgdir(lg, pgtable);
> -    /* If not, we allocate or mug an existing one: if it's a fresh one,
> -     * repin gets set to 1. */
> -    if (newpgdir == ARRAY_SIZE(lg->pgdirs))
> +    newpgdir = find_pgdir_from_list(lg, pgtable);
> +    if (!newpgdir) {
> +        /* If not, we allocate or mug an existing one: if it's a fresh 
> one,
> +         * repin gets set to 1. */
>         newpgdir = new_pgdir(lg, pgtable, &repin);
> -    /* Change the current pgd index to the new one. */
> -    lg->pgdidx = newpgdir;
> -    /* If it was completely blank, we map in the Guest kernel stack */
> -    if (repin)
> -        pin_stack_pages(lg);
> +       +        /* If it was completely blank, we map in the Guest 
> kernel stack */
> +        if (repin)
> +            pin_stack_pages(lg);
> +    }
> +
> +    /* Change the current pgd pointer to the new one. */
> +    lg->pgdir_cur = newpgdir;
> }

Down here.  The original code only set it in one place, which is neater.

> /*H:470 Finally, a routine which throws away everything: all PGD entries 
> in all
> @@ -438,13 +463,17 @@ void guest_new_pagetable(struct lguest *lg, 
> unsigned long pgtable)
> static void release_all_pagetables(struct lguest *lg)
> {
>     unsigned int i, j;
> +    struct pgdir *tmp;
> +    struct list_head *pos, *q;  
>     /* Every shadow pagetable this Guest has */
> -    for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
> -        if (lg->pgdirs[i].pgdir)
> +    list_for_each_safe (pos, q, &lg->pgdir_list) {
> +        tmp = list_entry (pos, struct pgdir, list);       +        if 
> (tmp->pgdir)
>             /* Every PGD entry except the Switcher at the top */
>             for (j = 0; j < SWITCHER_PGD_INDEX; j++)
> -                release_pgd(lg, lg->pgdirs[i].pgdir + j);
> +                release_pgd(lg, tmp->pgdir + j);
> +    }
> }

I prefer "while (!list_empty(&lg->pgdir_list)) { pgdir =
list_first_entry(&lg->pgdir_list); ..." for emptying lists (basically I
hate raw struct list_heads).

>     } else {
>         /* Is this page table one we have a shadow for? */
> -        int pgdir = find_pgdir(lg, cr3);
> -        if (pgdir != ARRAY_SIZE(lg->pgdirs))
> -            /* If so, do the update. */
> -            do_set_pte(lg, pgdir, vaddr, gpte);
> +        p = find_pgdir_from_list(lg, cr3);
> +        /* If so, do the update. */
> +        do_set_pte_my(lg, p, vaddr, gpte);
> +
>     }
> +
> +
> }

Extra whitespace here, and elsewhere: distorts your line count
unfavourably 8)

> /*H:400
> @@ -540,7 +573,7 @@ void guest_set_pte(struct lguest *lg,
>  */
> void guest_set_pmd(struct lguest *lg, unsigned long cr3, u32 idx)
> {
> -    int pgdir;
> +    struct pgdir * pgdir;

Usually no space between * and pgdir.

> +    newpgdir = kmalloc(sizeof(struct pgdir), GFP_KERNEL);
> +    if (!newpgdir) {
>         return -ENOMEM;
> +    }
> +
> +    lg->pgdir_cur = newpgdir;
> +    newpgdir->cr3 = pgtable;
> +    newpgdir->pgdir = (spgd_t*)get_zeroed_page(GFP_KERNEL);
> +    if (!newpgdir->pgdir)
> +        return -ENOMEM;

Don't need the newpgdir variable here, I think.  Perhaps create a helper
to allocate the struct and its zeroed page, since we do this in two
places?

>     /* Throw away all page table pages. */
>     release_all_pagetables(lg);
>     /* Now free the top levels: free_page() can handle 0 just fine. */
> -    for (i = 0; i < ARRAY_SIZE(lg->pgdirs); i++)
> -        free_page((long)lg->pgdirs[i].pgdir);
> +    list_for_each_safe (pos, q, &lg->pgdir_list) {
> +        tmp = list_entry (pos, struct pgdir, list);       +        
> free_page((long)tmp->pgdir);
> +        list_del(&tmp->list);
> +        kfree(tmp);
> +        lg->pgdir_list_size--;
> +    }
> }

Hmm, maybe a helper to release them, too since we do it in two places?

But basically, it looks good!  Not sure if it will be better than random
in practice, but you're about to find out.

Cheers,
Rusty.