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

[Rusty Russell]

On Sun, 2007-08-19 at 13:08 -0500, Jason Yeh wrote:
> hi all,
> 
> This is the update to the previous patch I send under the same title.
> The main difference between the two versions are:
> 	1. flush_user_mapping() no longer always flush the current
> 	pgdir. It takes an a struct pgdir * parameter and flush the
> 	pgdir.
> 
> 	2. The Least Recently Used list is updated only when the pgdir
> 	is about to be used.
> 
> 	3. Formatting changes.
> 
> I also measured the time it takes to compile a kernel with "-j 4" flag
> under the Guest. I am not sure if it is the best way to measure
> the impact of the patch. If you have better idea, please let me know.
> The average of five runs with the patch is:
> 	real    9m26.849s
> 	user    7m13.130s
> 	sys     2m11.330s
> 
> without the patch, the number looks like:
> 	real    9m46.572s
> 	user    7m33.140s
> 	sys     2m11.260s
> 
> Suggestions/comments are welcomed.

+51 lines (+1% lines) for 3% improvement?  Sold!

Except you seem to have increased the number of pgdirs to 5, so
benchmark results don't really count:

+	if (lg->num_pgdirs > PGDIR_MAX)  {

This should be ==.

Also, I think you mis-understood my recommendation.  I was saying that
find_pgdir_from_list should probably move the pgdir to the front, not
alloc_newpgdir().

Also build doesn't need to be -j4, that's overkill for a UP box.

Your patch was still line-wrapped.  Perhaps you need to use an
attachment?

Other minor things:
1) I prefer "MAX_PGDIRS" to PGDIR_MAX (the latter suggests pgdir is a
counter or something).

> +	/* 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;
> +	unsigned int num_pgdirs;

Comment needs more meat, I think.  How about:

	/* We keep up to MAX_PGDIRS page tables for each guest: latest-used is
	 * moved to the head and we discard from the tail (ie. LRU). */

> -static unsigned int find_pgdir(struct lguest *lg, unsigned long pgtable)
> +static struct pgdir * find_pgdir_from_list(struct lguest *lg, unsigned 
> long pgtable)

No space between the "struct pgdir *" and the "find_pgdir". Not sure it
needs to be renamed, either?

> +/* Helper to allocate new pgdir */
> +struct pgdir * alloc_newpgdir(void)

static?  Also, alloc_newpgdir is redundant: alloc_pgdir?

> -static unsigned int new_pgdir(struct lguest *lg,
> +static struct pgdir * new_pgdir(struct lguest *lg,

"static struct pgdir *new_pgdir()".

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

No space after the '*'.

>    * its first page table is.  We set some things up here: */
>   int init_guest_pagetable(struct lguest *lg, unsigned long pgtable)
>   {
> +	struct pgdir * newpgdir;
> +
>   	/* In flush_user_mappings() we loop from 0 to
>   	 * "vaddr_to_pgd_index(lg->page_offset)".  This assumes it won't hit
>   	 * the Switcher mappings, so check that now. */
>   	if (vaddr_to_pgd_index(lg->page_offset) >= SWITCHER_PGD_INDEX)
>   		return -EINVAL;
> -	/* We start on the first shadow page table, and give it a blank PGD
> -	 * page. */
> -	lg->pgdidx = 0;
> -	lg->pgdirs[lg->pgdidx].cr3 = pgtable;
> -	lg->pgdirs[lg->pgdidx].pgdir = (spgd_t*)get_zeroed_page(GFP_KERNEL);
> -	if (!lg->pgdirs[lg->pgdidx].pgdir)
> +
> +	INIT_LIST_HEAD(&lg->pgdir_list);
> +
> +	newpgdir = alloc_newpgdir();
> +	if (!newpgdir)
>   		return -ENOMEM;
> +
> +	lg->pgdir_cur = newpgdir;
> +	newpgdir->cr3 = pgtable;
> +	list_add(&newpgdir->list, &lg->pgdir_list);
> +	lg->num_pgdirs = 1;
> +

Hmm, perhaps rename alloc_newpgdir() to "add_pgdir()" and have it do the
"list_add(&newpgdir->list, &lg->pgdir_list);", "lg->num_pgdirs++" and
cr3 assignments?  Then this code becomes:

	lg->pgdir_cur = add_pgdir(lg, pgtable);
	if (!lg->pgdir_cur)
		return -ENOMEM;

And new_pgdir becomes:

	/* Have we reached the maximum number of pgdirs we can hold? */
	if (lg->num_pgdirs == PGDIR_MAX)  {
		/* Grab the tail for recycling and move it to the front. */
		newpgdir = list_entry(lg->pgdir_list.prev, struct pgdir, list);
		list_move(&newpgdir->list, &lg->pgdir_list);
		/* Release all the non-kernel mappings. */
		flush_user_mappings(lg, newpgdir);
		/* Record which Guest toplevel this shadows. */
		lg->cr3 = cr3;
	} else {
		/* Now we try to allocate a fresh one. */
		newpgdir = alloc_newpgdir(lg, cr3);
		if (!newpgdir)
			kill_guest(lg, "failed to get fresh pgdir");
		/* This is a blank page, so there are no kernel
		 * mappings: caller must map the stack! */
		*blank_pgdir = 1;
	}
	return newpgdir;
}

Cheers!
Rusty.