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] [thread-next>] [day] [month] [year] [list]

Message-ID: <b25eac6e-3744-3874-93a8-02f814549adf@intel.com>
Date:   Fri, 4 Nov 2016 11:10:11 -0700
From:   Dave Hansen <dave.hansen@...el.com>
To:     Liang Li <liang.z.li@...el.com>, mst@...hat.com
Cc:     pbonzini@...hat.com, amit.shah@...hat.com, quintela@...hat.com,
        dgilbert@...hat.com, qemu-devel@...gnu.org, kvm@...r.kernel.org,
        virtio-dev@...ts.oasis-open.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org,
        virtualization@...ts.linux-foundation.org,
        mgorman@...hsingularity.net, cornelia.huck@...ibm.com
Subject: Re: [PATCH kernel v4 7/7] virtio-balloon: tell host vm's unused page
 info

Please squish this and patch 5 together.  It makes no sense to separate
them.

> +static void send_unused_pages_info(struct virtio_balloon *vb,
> +				unsigned long req_id)
> +{
> +	struct scatterlist sg_in;
> +	unsigned long pfn = 0, bmap_len, pfn_limit, last_pfn, nr_pfn;
> +	struct virtqueue *vq = vb->req_vq;
> +	struct virtio_balloon_resp_hdr *hdr = vb->resp_hdr;
> +	int ret = 1, used_nr_bmap = 0, i;
> +
> +	if (virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_PAGE_BITMAP) &&
> +		vb->nr_page_bmap == 1)
> +		extend_page_bitmap(vb);
> +
> +	pfn_limit = PFNS_PER_BMAP * vb->nr_page_bmap;
> +	mutex_lock(&vb->balloon_lock);
> +	last_pfn = get_max_pfn();
> +
> +	while (ret) {
> +		clear_page_bitmap(vb);
> +		ret = get_unused_pages(pfn, pfn + pfn_limit, vb->page_bitmap,
> +			 PFNS_PER_BMAP, vb->nr_page_bmap);

This changed the underlying data structure without changing the way that
the structure is populated.

This algorithm picks a "PFNS_PER_BMAP * vb->nr_page_bmap"-sized set of
pfns, allocates a bitmap for them, the loops through all zones looking
for pages in any free list that are in that range.

Unpacking all the indirection, it looks like this:

for (pfn = 0; pfn < get_max_pfn(); pfn += BITMAP_SIZE_IN_PFNS)
	for_each_populated_zone(zone)
		for_each_migratetype_order(order, t)
			list_for_each(..., &zone->free_area[order])...

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.

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.

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.