Merge tag 'pull-hv-balloon-20231106' of https://github.com/maciejsszmigiero/qemu into staging

Hyper-V Dynamic Memory protocol driver.

This driver is like virtio-balloon on steroids for Windows guests:
it allows both changing the guest memory allocation via ballooning and
inserting pieces of extra RAM into it on demand from a provided memory
backend via Windows-native Hyper-V Dynamic Memory protocol.

* Preparatory patches to support empty memory devices and ones with
large alignment requirements.

* Revert of recently added "hw/virtio/virtio-pmem: Replace impossible
check by assertion" commit 5960f254dbb4 since this series makes this
situation possible again.

* Protocol definitions.

* Hyper-V DM protocol driver (hv-balloon) base (ballooning only).

* Hyper-V DM protocol driver (hv-balloon) hot-add support.

* qapi query-memory-devices support for the driver.

* qapi HV_BALLOON_STATUS_REPORT event.

* The relevant PC machine plumbing.

* New MAINTAINERS entry for the above.

# -----BEGIN PGP SIGNATURE-----
#
# iQGzBAABCAAdFiEE4ndqq6COJv9aG0oJUrHW6VHQzgcFAmVI81IACgkQUrHW6VHQ
# zgdzTgv+I5eV2R01YLOBBJhBjzxZ4/BUqkuUHNxHpfjuCqEIzPb7FIfoZ4ZyXZFT
# YJdSE4lPeTZLrmmi/Nt6G0rUKDvdCeIgkS2VLHFSsTV8IzcT71BTRGzV0zAjUF5v
# yDH6uzo6e9gmaziIalRjibUxSDjCQmoCifms2rS2DwazADudUp+naGfm+3uyA0gM
# raOfBfRkNZsDqhXg2ayuqPIES75xQONoON9xYPKDAthS48POEbqtWBKuFopr3kXY
# y0eph+NAw+RajCyLYKM3poIgaSu3l4WegInuKQffzqKR8dxrbwPdCmtgo6NSHx0W
# uDfl7FUBnGzrR18VU4ZfTSrF5SVscGwF9EL7uocJen15inJjl1q3G53uZgyGzHLC
# cw8fKMjucmE8njQR2qiMyX0b+T4+9nKO1rykBgTG/+c9prRUVoxYpFCF117Ei0U8
# QzLGACW1oK+LV41bekWAye7w9pShUtFaxffhPbJeZDDGh7q0x61R3Z3yKkA07p46
# /YWWFWUD
# =RAb0
# -----END PGP SIGNATURE-----
# gpg: Signature made Mon 06 Nov 2023 22:08:18 HKT
# gpg:                using RSA key E2776AABA08E26FF5A1B4A0952B1D6E951D0CE07
# gpg: Good signature from "Maciej S. Szmigiero <mail@maciej.szmigiero.name>" [unknown]
# gpg: WARNING: This key is not certified with a trusted signature!
# gpg:          There is no indication that the signature belongs to the owner.
# Primary key fingerprint: 727A 0D4D DB9E D9F6 039B  ECEF 847F 5E37 90CE 0977
#      Subkey fingerprint: E277 6AAB A08E 26FF 5A1B  4A09 52B1 D6E9 51D0 CE07

* tag 'pull-hv-balloon-20231106' of https://github.com/maciejsszmigiero/qemu:
  MAINTAINERS: Add an entry for Hyper-V Dynamic Memory Protocol
  hw/i386/pc: Support hv-balloon
  qapi: Add HV_BALLOON_STATUS_REPORT event and its QMP query command
  qapi: Add query-memory-devices support to hv-balloon
  Add Hyper-V Dynamic Memory Protocol driver (hv-balloon) hot-add support
  Add Hyper-V Dynamic Memory Protocol driver (hv-balloon) base
  Add Hyper-V Dynamic Memory Protocol definitions
  memory-device: Drop size alignment check
  Revert "hw/virtio/virtio-pmem: Replace impossible check by assertion"
  memory-device: Support empty memory devices

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>

1 files changed, 228 insertions, 0 deletions

diff --git a/hw/hyperv/hv-balloon-page_range_tree.c b/hw/hyperv/hv-balloon-page_range_tree.c
new file mode 100644
index 0000000000..e178d8b413
--- /dev/null
+++ b/hw/hyperv/hv-balloon-page_range_tree.c
@@ -0,0 +1,228 @@
+/*
+ * QEMU Hyper-V Dynamic Memory Protocol driver
+ *
+ * Copyright (C) 2020-2023 Oracle and/or its affiliates.
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ */
+
+#include "hv-balloon-internal.h"
+#include "hv-balloon-page_range_tree.h"
+
+/*
+ * temporarily avoid warnings about enhanced GTree API usage requiring a
+ * too recent Glib version until GLIB_VERSION_MAX_ALLOWED finally reaches
+ * the Glib version with this API
+ */
+#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
+
+/* PageRangeTree */
+static gint page_range_tree_key_compare(gconstpointer leftp,
+                                        gconstpointer rightp,
+                                        gpointer user_data)
+{
+    const uint64_t *left = leftp, *right = rightp;
+
+    if (*left < *right) {
+        return -1;
+    } else if (*left > *right) {
+        return 1;
+    } else { /* *left == *right */
+        return 0;
+    }
+}
+
+static GTreeNode *page_range_tree_insert_new(PageRangeTree tree,
+                                             uint64_t start, uint64_t count)
+{
+    uint64_t *key = g_malloc(sizeof(*key));
+    PageRange *range = g_malloc(sizeof(*range));
+
+    assert(count > 0);
+
+    *key = range->start = start;
+    range->count = count;
+
+    return g_tree_insert_node(tree.t, key, range);
+}
+
+void hvb_page_range_tree_insert(PageRangeTree tree,
+                                uint64_t start, uint64_t count,
+                                uint64_t *dupcount)
+{
+    GTreeNode *node;
+    bool joinable;
+    uint64_t intersection;
+    PageRange *range;
+
+    assert(!SUM_OVERFLOW_U64(start, count));
+    if (count == 0) {
+        return;
+    }
+
+    node = g_tree_upper_bound(tree.t, &start);
+    if (node) {
+        node = g_tree_node_previous(node);
+    } else {
+        node = g_tree_node_last(tree.t);
+    }
+
+    if (node) {
+        range = g_tree_node_value(node);
+        assert(range);
+        intersection = page_range_intersection_size(range, start, count);
+        joinable = page_range_joinable_right(range, start, count);
+    }
+
+    if (!node ||
+        (!intersection && !joinable)) {
+        /*
+         * !node case: the tree is empty or the very first node in the tree
+         * already has a higher key (the start of its range).
+         * the other case: there is a gap in the tree between the new range
+         * and the previous one.
+         * anyway, let's just insert the new range into the tree.
+         */
+        node = page_range_tree_insert_new(tree, start, count);
+        assert(node);
+        range = g_tree_node_value(node);
+        assert(range);
+    } else {
+        /*
+         * the previous range in the tree either partially covers the new
+         * range or ends just at its beginning - extend it
+         */
+        if (dupcount) {
+            *dupcount += intersection;
+        }
+
+        count += start - range->start;
+        range->count = MAX(range->count, count);
+    }
+
+    /* check next nodes for possible merging */
+    for (node = g_tree_node_next(node); node; ) {
+        PageRange *rangecur;
+
+        rangecur = g_tree_node_value(node);
+        assert(rangecur);
+
+        intersection = page_range_intersection_size(rangecur,
+                                                    range->start, range->count);
+        joinable = page_range_joinable_left(rangecur,
+                                            range->start, range->count);
+        if (!intersection && !joinable) {
+            /* the current node is disjoint */
+            break;
+        }
+
+        if (dupcount) {
+            *dupcount += intersection;
+        }
+
+        count = rangecur->count + (rangecur->start - range->start);
+        range->count = MAX(range->count, count);
+
+        /* the current node was merged in, remove it */
+        start = rangecur->start;
+        node = g_tree_node_next(node);
+        /* no hinted removal in GTree... */
+        g_tree_remove(tree.t, &start);
+    }
+}
+
+bool hvb_page_range_tree_pop(PageRangeTree tree, PageRange *out,
+                             uint64_t maxcount)
+{
+    GTreeNode *node;
+    PageRange *range;
+
+    node = g_tree_node_last(tree.t);
+    if (!node) {
+        return false;
+    }
+
+    range = g_tree_node_value(node);
+    assert(range);
+
+    out->start = range->start;
+
+    /* can't modify range->start as it is the node key */
+    if (range->count > maxcount) {
+        out->start += range->count - maxcount;
+        out->count = maxcount;
+        range->count -= maxcount;
+    } else {
+        out->count = range->count;
+        /* no hinted removal in GTree... */
+        g_tree_remove(tree.t, &out->start);
+    }
+
+    return true;
+}
+
+bool hvb_page_range_tree_intree_any(PageRangeTree tree,
+                                    uint64_t start, uint64_t count)
+{
+    GTreeNode *node;
+
+    if (count == 0) {
+        return false;
+    }
+
+    /* find the first node that can possibly intersect our range */
+    node = g_tree_upper_bound(tree.t, &start);
+    if (node) {
+        /*
+         * a NULL node below means that the very first node in the tree
+         * already has a higher key (the start of its range).
+         */
+        node = g_tree_node_previous(node);
+    } else {
+        /* a NULL node below means that the tree is empty */
+        node = g_tree_node_last(tree.t);
+    }
+    /* node range start <= range start */
+
+    if (!node) {
+        /* node range start > range start */
+        node = g_tree_node_first(tree.t);
+    }
+
+    for ( ; node; node = g_tree_node_next(node)) {
+        PageRange *range = g_tree_node_value(node);
+
+        assert(range);
+        /*
+         * if this node starts beyond or at the end of our range so does
+         * every next one
+         */
+        if (range->start >= start + count) {
+            break;
+        }
+
+        if (page_range_intersection_size(range, start, count) > 0) {
+            return true;
+        }
+    }
+
+    return false;
+}
+
+void hvb_page_range_tree_init(PageRangeTree *tree)
+{
+    tree->t = g_tree_new_full(page_range_tree_key_compare, NULL,
+                              g_free, g_free);
+}
+
+void hvb_page_range_tree_destroy(PageRangeTree *tree)
+{
+    /* g_tree_destroy() is not NULL-safe */
+    if (!tree->t) {
+        return;
+    }
+
+    g_tree_destroy(tree->t);
+    tree->t = NULL;
+}