| Message ID | 1478067447-24654-8-git-send-email-liang.z.li@intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
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.
> Please squish this and patch 5 together. It makes no sense to separate them. > OK. > > +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. > 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. > 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? In the QEMU, no matter how we encode the bitmap, the raw format bitmap will be used in the end. But what I did in this version is: kernel: get the raw bitmap --> encode the bitmap QEMU: decode the bitmap --> get the raw bitmap Is it worth to do this kind of job here? we can save the virtio data transmission, but at the same time, we did extra work. 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? Thanks! Liang
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. > 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.
> 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? > Yes. > So, what's the _worst_ case? It sounds like it is even worse than I was > positing. > Only a 32KB bitmap can be allocated, and there are a huge amount of low order (<3) free pages is the worst case. > >> 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. > Sounds good. Should we ignore some of the order-0 pages in step 4 if the bitmap is full? Or should retry to get a complete list of order-0 pages? > > > 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. The ' get_max_pfn()' can be avoid in this patch, but I think we can't avoid it completely. We need it as a hint for allocating a proper size bitmap. No? Thanks! Liang
On 11/07/2016 09:50 PM, Li, Liang Z wrote: > Sounds good. Should we ignore some of the order-0 pages in step 4 if the bitmap is full? > Or should retry to get a complete list of order-0 pages? I think that's a pretty reasonable thing to do. >>> 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. > > The ' get_max_pfn()' can be avoid in this patch, but I think we can't > avoid it completely. We need it as a hint for allocating a proper > size bitmap. No? If you start with higher-order pages, you'll be unlikely to get anywhere close to filling up a bitmap that was sized to hold all possible order-0 pages on the system. Any use of max_pfn also means that you'll completely mis-size bitmaps on sparse systems with large holes. I think you should size it based on the size of the free lists, if anything.
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.
diff --git a/drivers/virtio/virtio_balloon.c b/drivers/virtio/virtio_balloon.c index c6c94b6..ba2d37b 100644 --- a/drivers/virtio/virtio_balloon.c +++ b/drivers/virtio/virtio_balloon.c @@ -56,7 +56,7 @@ struct virtio_balloon { struct virtio_device *vdev; - struct virtqueue *inflate_vq, *deflate_vq, *stats_vq; + struct virtqueue *inflate_vq, *deflate_vq, *stats_vq, *req_vq; /* The balloon servicing is delegated to a freezable workqueue. */ struct work_struct update_balloon_stats_work; @@ -83,6 +83,8 @@ struct virtio_balloon { unsigned int nr_page_bmap; /* Used to record the processed pfn range */ unsigned long min_pfn, max_pfn, start_pfn, end_pfn; + /* Request header */ + struct virtio_balloon_req_hdr req_hdr; /* * The pages we've told the Host we're not using are enqueued * at vb_dev_info->pages list. @@ -552,6 +554,63 @@ static void update_balloon_stats(struct virtio_balloon *vb) pages_to_bytes(available)); } +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); + if (ret < 0) + break; + hdr->cmd = BALLOON_GET_UNUSED_PAGES; + hdr->id = req_id; + bmap_len = BALLOON_BMAP_SIZE * vb->nr_page_bmap; + + if (!ret) { + hdr->flag = BALLOON_FLAG_DONE; + nr_pfn = last_pfn - pfn; + used_nr_bmap = nr_pfn / PFNS_PER_BMAP; + if (nr_pfn % PFNS_PER_BMAP) + used_nr_bmap++; + bmap_len = nr_pfn / BITS_PER_BYTE; + } else { + hdr->flag = BALLOON_FLAG_CONT; + used_nr_bmap = vb->nr_page_bmap; + } + for (i = 0; i < used_nr_bmap; i++) { + unsigned int bmap_size = BALLOON_BMAP_SIZE; + + if (i + 1 == used_nr_bmap) + bmap_size = bmap_len - BALLOON_BMAP_SIZE * i; + set_bulk_pages(vb, vq, pfn + i * PFNS_PER_BMAP, + vb->page_bitmap[i], bmap_size, true); + } + if (vb->resp_pos > 0) + send_resp_data(vb, vq, true); + pfn += pfn_limit; + } + + mutex_unlock(&vb->balloon_lock); + sg_init_one(&sg_in, &vb->req_hdr, sizeof(vb->req_hdr)); + virtqueue_add_inbuf(vq, &sg_in, 1, &vb->req_hdr, GFP_KERNEL); + virtqueue_kick(vq); +} + /* * While most virtqueues communicate guest-initiated requests to the hypervisor, * the stats queue operates in reverse. The driver initializes the virtqueue @@ -686,18 +745,56 @@ static void update_balloon_size_func(struct work_struct *work) queue_work(system_freezable_wq, work); } +static void misc_handle_rq(struct virtio_balloon *vb) +{ + struct virtio_balloon_req_hdr *ptr_hdr; + unsigned int len; + + ptr_hdr = virtqueue_get_buf(vb->req_vq, &len); + if (!ptr_hdr || len != sizeof(vb->req_hdr)) + return; + + switch (ptr_hdr->cmd) { + case BALLOON_GET_UNUSED_PAGES: + send_unused_pages_info(vb, ptr_hdr->param); + break; + default: + break; + } +} + +static void misc_request(struct virtqueue *vq) +{ + struct virtio_balloon *vb = vq->vdev->priv; + + misc_handle_rq(vb); +} + static int init_vqs(struct virtio_balloon *vb) { - struct virtqueue *vqs[3]; - vq_callback_t *callbacks[] = { balloon_ack, balloon_ack, stats_request }; - static const char * const names[] = { "inflate", "deflate", "stats" }; + struct virtqueue *vqs[4]; + vq_callback_t *callbacks[] = { balloon_ack, balloon_ack, + stats_request, misc_request }; + static const char * const names[] = { "inflate", "deflate", "stats", + "misc" }; int err, nvqs; /* * We expect two virtqueues: inflate and deflate, and * optionally stat. */ - nvqs = virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_STATS_VQ) ? 3 : 2; + if (virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_HOST_REQ_VQ)) + nvqs = 4; + else if (virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_STATS_VQ)) + nvqs = 3; + else + nvqs = 2; + + if (!virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_STATS_VQ)) { + __virtio_clear_bit(vb->vdev, VIRTIO_BALLOON_F_PAGE_BITMAP); + __virtio_clear_bit(vb->vdev, VIRTIO_BALLOON_F_HOST_REQ_VQ); + } + err = vb->vdev->config->find_vqs(vb->vdev, nvqs, vqs, callbacks, names); if (err) return err; @@ -718,6 +815,18 @@ static int init_vqs(struct virtio_balloon *vb) BUG(); virtqueue_kick(vb->stats_vq); } + if (virtio_has_feature(vb->vdev, VIRTIO_BALLOON_F_HOST_REQ_VQ)) { + struct scatterlist sg_in; + + vb->req_vq = vqs[3]; + sg_init_one(&sg_in, &vb->req_hdr, sizeof(vb->req_hdr)); + if (virtqueue_add_inbuf(vb->req_vq, &sg_in, 1, + &vb->req_hdr, GFP_KERNEL) < 0) + __virtio_clear_bit(vb->vdev, + VIRTIO_BALLOON_F_HOST_REQ_VQ); + else + virtqueue_kick(vb->req_vq); + } return 0; } @@ -851,11 +960,13 @@ static int virtballoon_probe(struct virtio_device *vdev) vb->resp_hdr = kzalloc(sizeof(struct virtio_balloon_resp_hdr), GFP_KERNEL); /* Clear the feature bit if memory allocation fails */ - if (!vb->resp_hdr) + if (!vb->resp_hdr) { __virtio_clear_bit(vdev, VIRTIO_BALLOON_F_PAGE_BITMAP); - else { + __virtio_clear_bit(vdev, VIRTIO_BALLOON_F_HOST_REQ_VQ); + } else { vb->page_bitmap[0] = kmalloc(BALLOON_BMAP_SIZE, GFP_KERNEL); if (!vb->page_bitmap[0]) { + __virtio_clear_bit(vdev, VIRTIO_BALLOON_F_HOST_REQ_VQ); __virtio_clear_bit(vdev, VIRTIO_BALLOON_F_PAGE_BITMAP); kfree(vb->resp_hdr); } else { @@ -864,6 +975,8 @@ static int virtballoon_probe(struct virtio_device *vdev) if (!vb->resp_data) { __virtio_clear_bit(vdev, VIRTIO_BALLOON_F_PAGE_BITMAP); + __virtio_clear_bit(vdev, + VIRTIO_BALLOON_F_HOST_REQ_VQ); kfree(vb->page_bitmap[0]); kfree(vb->resp_hdr); } @@ -987,6 +1100,7 @@ static int virtballoon_restore(struct virtio_device *vdev) VIRTIO_BALLOON_F_STATS_VQ, VIRTIO_BALLOON_F_DEFLATE_ON_OOM, VIRTIO_BALLOON_F_PAGE_BITMAP, + VIRTIO_BALLOON_F_HOST_REQ_VQ, }; static struct virtio_driver virtio_balloon_driver = {
Support the request for vm's unused page information, response with a page bitmap. QEMU can make use of this bitmap and the dirty page logging mechanism to skip the transportation of some of these unused pages, this is very helpful to reduce the network traffic and speed up the live migration process. Signed-off-by: Liang Li <liang.z.li@intel.com> Cc: Michael S. Tsirkin <mst@redhat.com> Cc: Paolo Bonzini <pbonzini@redhat.com> Cc: Cornelia Huck <cornelia.huck@de.ibm.com> Cc: Amit Shah <amit.shah@redhat.com> Cc: Dave Hansen <dave.hansen@intel.com> --- drivers/virtio/virtio_balloon.c | 128 +++++++++++++++++++++++++++++++++++++--- 1 file changed, 121 insertions(+), 7 deletions(-)