From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933776AbcKHVHM (ORCPT ); Tue, 8 Nov 2016 16:07:12 -0500 Received: from mx1.redhat.com ([209.132.183.28]:42382 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933749AbcKHVHI (ORCPT ); Tue, 8 Nov 2016 16:07:08 -0500 Date: Tue, 8 Nov 2016 23:07:04 +0200 From: "Michael S. Tsirkin" To: Dave Hansen Cc: "Li, Liang Z" , "pbonzini@redhat.com" , "amit.shah@redhat.com" , "quintela@redhat.com" , "dgilbert@redhat.com" , "qemu-devel@nongnu.org" , "kvm@vger.kernel.org" , "virtio-dev@lists.oasis-open.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , "virtualization@lists.linux-foundation.org" , "mgorman@techsingularity.net" , "cornelia.huck@de.ibm.com" Subject: Re: [PATCH kernel v4 7/7] virtio-balloon: tell host vm's unused page info Message-ID: <20161108230220-mutt-send-email-mst@kernel.org> References: <1478067447-24654-1-git-send-email-liang.z.li@intel.com> <1478067447-24654-8-git-send-email-liang.z.li@intel.com> <281acd8d-fd94-6318-35e5-9eb130303dc6@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <281acd8d-fd94-6318-35e5-9eb130303dc6@intel.com> X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.28]); Tue, 08 Nov 2016 21:07:07 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Nov 07, 2016 at 09:23:38AM -0800, Dave Hansen wrote: > On 11/06/2016 07:37 PM, Li, Liang Z wrote: > >> Let's say we do a 32k bitmap that can hold ~1M pages. That's 4GB of RAM. > >> On a 1TB system, that's 256 passes through the top-level loop. > >> The bottom-level lists have tens of thousands of pages in them, even on my > >> laptop. Only 1/256 of these pages will get consumed in a given pass. > >> > > Your description is not exactly. > > A 32k bitmap is used only when there is few free memory left in the system and when > > the extend_page_bitmap() failed to allocate more memory for the bitmap. Or dozens of > > 32k split bitmap will be used, this version limit the bitmap count to 32, it means we can use > > at most 32*32 kB for the bitmap, which can cover 128GB for RAM. We can increase the bitmap > > count limit to a larger value if 32 is not big enough. > > OK, so it tries to allocate a large bitmap. But, if it fails, it will > try to work with a smaller bitmap. Correct? > > So, what's the _worst_ case? It sounds like it is even worse than I was > positing. > > >> That's an awfully inefficient way of doing it. This patch essentially changed > >> the data structure without changing the algorithm to populate it. > >> > >> Please change the *algorithm* to use the new data structure efficiently. > >> Such a change would only do a single pass through each freelist, and would > >> choose whether to use the extent-based (pfn -> range) or bitmap-based > >> approach based on the contents of the free lists. > > > > Save the free page info to a raw bitmap first and then process the raw bitmap to > > get the proper ' extent-based ' and 'bitmap-based' is the most efficient way I can > > come up with to save the virtio data transmission. Do you have some better idea? > > That's kinda my point. This patch *does* processing to try to pack the > bitmaps full of pages from the various pfn ranges. It's a form of > processing that gets *REALLY*, *REALLY* bad in some (admittedly obscure) > cases. > > Let's not pretend that making an essentially unlimited number of passes > over the free lists is not processing. > > 1. Allocate as large of a bitmap as you can. (what you already do) > 2. Iterate from the largest freelist order. Store those pages in the > bitmap. > 3. If you can no longer fit pages in the bitmap, return the list that > you have. > 4. Make an approximation about where the bitmap does not make any more, > and fall back to listing individual PFNs. This would make sens, for > instance in a large zone with very few free order-0 pages left. In practice, a single PFN using the bitmap format only takes up twice the size: I think it's 128 instead of 64 bit per entry. So it's not a a given that point 4 is worth it at any point, just packing multiple bitmaps might be good enough. > > > It seems the benefit we get for this feature is not as big as that in fast balloon inflating/deflating. > >> > >> You should not be using get_max_pfn(). Any patch set that continues to use > >> it is not likely to be using a proper algorithm. > > > > Do you have any suggestion about how to avoid it? > > Yes: get the pfns from the page free lists alone. Don't derive them > from the pfn limits of the system or zones.