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

[Glauber de Oliveira Costa]

On 8/14/07, Jason Yeh <jasonyeh0908 at gmail.com> 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.
>
> This is a naive implementation of Least Recently Used list replacing
> pgdirs array of struct lg.  pgdirs are inserted into the list, and moved
> in the way that the least recently used pgdir is at the tail of the
> list. pgdir_cur replaces pgdidx pointing to the current pgdir. I have
> not done any measurements on the code yet other than verify that it
> boots the image. I would like to get some feedbacks and making more
> changes before doing any benchmarks. All comments, criticism, and
> suggestions are welcomed.
>
> The patch is made against Linus git tree. If there's a need to make the
> patch agains the lguest mercurial server, please let me know.
>
>
First of all, your mailer seems to be wrapping lines, and changing
tabs to spaces. Try to avoid it.

It would be really interesting to see measures on that. From my POV,
any complexity added to lguest must really pay off. Otherwise, we keep
it simple.

I'll put some comments below.

> @@ -474,7 +474,7 @@ static void run_guest_once(struct lguest *lg, struct
> lguest_pages *pages)
>               * 0-th argument above, ie "a").  %ebx contains the
>               * physical address of the Guest's top-level page
>               * directory. */
> -             : "0"(pages), "1"(__pa(lg->pgdirs[lg->pgdidx].pgdir))
> +            : "0"(pages), "1"(__pa(lg->pgdir_cur->pgdir))
>              /* We tell gcc that all these registers could change,
>               * which means we don't have to save and restore them in
>               * the Switcher. */
> diff --git a/drivers/lguest/lg.h b/drivers/lguest/lg.h
> index 64f0abe..75ac222 100644
> --- a/drivers/lguest/lg.h
> +++ b/drivers/lguest/lg.h
> @@ -7,6 +7,8 @@
> #define GDT_ENTRY_LGUEST_DS    11
> #define LGUEST_CS        (GDT_ENTRY_LGUEST_CS * 8)
> #define LGUEST_DS        (GDT_ENTRY_LGUEST_DS * 8)
> +/* Number of PGDIR we keep for each guest */
> +#define PGDIR_MAX 4
This change is good regardless of the rest. Best to keep in constants
what can be kept this way. You may want to mail a separate patch
regardless of the result of this one.

> #ifndef __ASSEMBLY__
> #include <linux/types.h>
> @@ -97,6 +99,7 @@ struct pgdir
> {
>     unsigned long cr3;
>     spgd_t *pgdir;
> +    struct list_head list;       };
>
> /* This is a guest-specific page (mapped ro) into the guest. */
> @@ -159,9 +162,11 @@ struct lguest
>     int changed;
>     struct lguest_pages *last_pages;
>
> -    /* We keep a small number of these. */
> -    u32 pgdidx;
> -    struct pgdir pgdirs[4];
> +    /* pgdir LRU
> +     * Newest pgdir is added to the head of the list.
> +     * pgdir_list is the tail of the list */
> +    struct list_head pgdir_list;
> +    struct pgdir *pgdir_cur;

Maybe we could avoid using pgdir_cur. It seems it will always be the
first one on the list anyway. We can just use list_entry (probably
wrapped by a macro) to retrieve its contents.

> --- a/drivers/lguest/page_tables.c
> +++ b/drivers/lguest/page_tables.c
> @@ -15,6 +15,7 @@
> #include <asm/tlbflush.h>
> #include "lg.h"
>
> +
No reason for this newline.

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

It does not seem right. flush_user_mappings() not always release the
mappings for the current pgdir.

> /* 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)
> {
> -    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);
I am not sure about lguest32, but as for lguest64, there are
situations in which finding a pgdir does not mean we're going to use
it. So it would maybe be better to have a separate function to move
things, once it is found. Brian Boitano (aka rusty) is the
authoritative person for this.

> +    /* 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);
> +    } else {
> +        /* If it's never been allocated at all before, try now. */
> +        newpgdir = kmalloc(sizeof(struct pgdir), GFP_KERNEL);
kzalloc is probably better.

> +    newpgdir = kmalloc(sizeof(struct pgdir), GFP_KERNEL);
again, kzalloc is probably better here.

> +    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;
And what about your earlier allocation of newpgdir? Will it be here
forever? free it before returning.


-- 
Glauber de Oliveira Costa.
"Free as in Freedom"
http://glommer.net

"The less confident you are, the more serious you have to act."