linux-kernel - Re: [PATCH kernel v4 7/7] virtio-balloon: tell host vm's unused page info

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20161108230220-mutt-send-email-mst@kernel.org>
Date:   Tue, 8 Nov 2016 23:07:04 +0200
From:   "Michael S. Tsirkin" <mst@...hat.com>
To:     Dave Hansen <dave.hansen@...el.com>
Cc:     "Li, Liang Z" <liang.z.li@...el.com>,
        "pbonzini@...hat.com" <pbonzini@...hat.com>,
        "amit.shah@...hat.com" <amit.shah@...hat.com>,
        "quintela@...hat.com" <quintela@...hat.com>,
        "dgilbert@...hat.com" <dgilbert@...hat.com>,
        "qemu-devel@...gnu.org" <qemu-devel@...gnu.org>,
        "kvm@...r.kernel.org" <kvm@...r.kernel.org>,
        "virtio-dev@...ts.oasis-open.org" <virtio-dev@...ts.oasis-open.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "virtualization@...ts.linux-foundation.org" 
        <virtualization@...ts.linux-foundation.org>,
        "mgorman@...hsingularity.net" <mgorman@...hsingularity.net>,
        "cornelia.huck@...ibm.com" <cornelia.huck@...ibm.com>
Subject: Re: [PATCH kernel v4 7/7] virtio-balloon: tell host vm's unused page
 info

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.