From mboxrd@z Thu Jan 1 00:00:00 1970 From: Andrew Cooper Subject: Re: [PATCH for 4.6 5/5] libxc: de-duplicate gpfns in populate_pfns Date: Fri, 4 Sep 2015 22:56:42 +0100 Message-ID: <55EA139A.7080808@citrix.com> References: <1441391531-30004-1-git-send-email-wei.liu2@citrix.com> <1441391531-30004-6-git-send-email-wei.liu2@citrix.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; Format="flowed" Content-Transfer-Encoding: 7bit Return-path: Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1ZXyyc-0005C8-04 for xen-devel@lists.xenproject.org; Fri, 04 Sep 2015 21:56:54 +0000 In-Reply-To: <1441391531-30004-6-git-send-email-wei.liu2@citrix.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Wei Liu , Xen-devel Cc: Ian Jackson , Ian Campbell List-Id: xen-devel@lists.xenproject.org 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 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; > + } > } > } >