Re: [PATCH for 4.6 5/5] libxc: de-duplicate gpfns in populate_pfns

[Andrew Cooper <andrew.cooper3@citrix.com>]

     On 04/09/15 19:32, Wei Liu wrote:
> The original implementation didn't consider there can be same gpfns
> present multiple times in the passed in array. The mechanism to prevent
> populating same gpfn multiple times only works if the same gpfn appear
> in different batch.
>
> This bug is discovered by save / restore Linux 4.1 32 bit kernel, which
> has several PTEs pointing to same gpfn. And gpfn pointed to by those
> PTEs are populated in one batch by libxc.  When libxc calls
> x86_pv_localise_page, the original implementation failed to detect
> duplications in one batch.
>
> The fix is to de-duplicate gpfns in populate_pfns.
>
> Signed-off-by: Wei Liu <wei.liu2@citrix.com>

The original version of populate_pfns() synchronously populated pfns 
when they were found referenced in PTEs ahead of the appropriate 
PAGE_DATA record arriving, but this proved to be very inefficient 
depends on the pagetable layout of the guest.

I agree that this is a bug.

> ---
>   tools/libxc/xc_sr_restore.c | 19 ++++++++++++++++---
>   1 file changed, 16 insertions(+), 3 deletions(-)
>
> diff --git a/tools/libxc/xc_sr_restore.c b/tools/libxc/xc_sr_restore.c
> index adb48da..09fe4c0 100644
> --- a/tools/libxc/xc_sr_restore.c
> +++ b/tools/libxc/xc_sr_restore.c
> @@ -198,7 +198,7 @@ int populate_pfns(struct xc_sr_context *ctx, unsigned count,
>       xc_interface *xch = ctx->xch;
>       xen_pfn_t *mfns = malloc(count * sizeof(*mfns)),
>           *pfns = malloc(count * sizeof(*pfns));
> -    unsigned i, nr_pfns = 0;
> +    unsigned i, j, nr_pfns = 0;
>       int rc = -1;
>   
>       if ( !mfns || !pfns )
> @@ -209,14 +209,27 @@ int populate_pfns(struct xc_sr_context *ctx, unsigned count,
>       }
>   
>       for ( i = 0; i < count; ++i )
> +        pfns[i] = mfns[i] = INVALID_MFN;
> +
> +    for ( i = 0; i < count; ++i )
>       {
>           if ( (!types || (types &&
>                            (types[i] != XEN_DOMCTL_PFINFO_XTAB &&
>                             types[i] != XEN_DOMCTL_PFINFO_BROKEN))) &&
>                !pfn_is_populated(ctx, original_pfns[i]) )
>           {
> -            pfns[nr_pfns] = mfns[nr_pfns] = original_pfns[i];
> -            ++nr_pfns;
> +            bool present = false;
> +
> +            /* De-duplicate gpfns to avoid populating the same one twice */

Just pfns to match the rest of the code.  (I notice some other memory 
terminology needing cleaning up - I will formulate some patches when I 
am next in a position to do so.)

> +            for ( j = 0; j < nr_pfns; ++j )
> +                if ( pfns[j] == original_pfns[i] )
> +                    present = true;

Adding this nested loop introduces O(N^2) behavior on what is typically 
1024-length inputs.

I recommend moving the pfn_set_populated() call from the subsequent loop 
into this loop, which will cause the pfn_is_populated() call in this 
loop condition to catch repeat populations even in the same batch.

The only way pfn_set_populated() can fail is out of memory, and any 
error anywhere in this function is fatal to migration, so there is no 
chance of proceeding with migration with a pfn marked as populated, but 
set to INVALID_MFN in the p2m.

~Andrew

> +
> +            if ( !present )
> +            {
> +                pfns[nr_pfns] = mfns[nr_pfns] = original_pfns[i];
> +                ++nr_pfns;
> +            }
>           }
>       }
>