hw/hyperv/hv-balloon-page_range_tree.c

   1 /*
   2  * QEMU Hyper-V Dynamic Memory Protocol driver
   3  *
   4  * Copyright (C) 2020-2023 Oracle and/or its affiliates.
   5  *
   6  * This work is licensed under the terms of the GNU GPL, version 2 or later.
   7  * See the COPYING file in the top-level directory.
   8  */
   9
  10 #include "qemu/osdep.h"
  11 #include "hv-balloon-internal.h"
  12 #include "hv-balloon-page_range_tree.h"
  13
  14 /*
  15  * temporarily avoid warnings about enhanced GTree API usage requiring a
  16  * too recent Glib version until GLIB_VERSION_MAX_ALLOWED finally reaches
  17  * the Glib version with this API
  18  */
  19 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
  20
  21 /* PageRangeTree */
  22 static gint page_range_tree_key_compare(gconstpointer leftp,
  23                                         gconstpointer rightp,
  24                                         gpointer user_data)
  25 {
  26     const uint64_t *left = leftp, *right = rightp;
  27
  28     if (*left < *right) {
  29         return -1;
  30     } else if (*left > *right) {
  31         return 1;
  32     } else { /* *left == *right */
  33         return 0;
  34     }
  35 }
  36
  37 static GTreeNode *page_range_tree_insert_new(PageRangeTree tree,
  38                                              uint64_t start, uint64_t count)
  39 {
  40     uint64_t *key = g_malloc(sizeof(*key));
  41     PageRange *range = g_malloc(sizeof(*range));
  42
  43     assert(count > 0);
  44
  45     *key = range->start = start;
  46     range->count = count;
  47
  48     return g_tree_insert_node(tree.t, key, range);
  49 }
  50
  51 void hvb_page_range_tree_insert(PageRangeTree tree,
  52                                 uint64_t start, uint64_t count,
  53                                 uint64_t *dupcount)
  54 {
  55     GTreeNode *node;
  56     bool joinable;
  57     uint64_t intersection;
  58     PageRange *range;
  59
  60     assert(!SUM_OVERFLOW_U64(start, count));
  61     if (count == 0) {
  62         return;
  63     }
  64
  65     node = g_tree_upper_bound(tree.t, &start);
  66     if (node) {
  67         node = g_tree_node_previous(node);
  68     } else {
  69         node = g_tree_node_last(tree.t);
  70     }
  71
  72     if (node) {
  73         range = g_tree_node_value(node);
  74         assert(range);
  75         intersection = page_range_intersection_size(range, start, count);
  76         joinable = page_range_joinable_right(range, start, count);
  77     }
  78
  79     if (!node ||
  80         (!intersection && !joinable)) {
  81         /*
  82          * !node case: the tree is empty or the very first node in the tree
  83          * already has a higher key (the start of its range).
  84          * the other case: there is a gap in the tree between the new range
  85          * and the previous one.
  86          * anyway, let's just insert the new range into the tree.
  87          */
  88         node = page_range_tree_insert_new(tree, start, count);
  89         assert(node);
  90         range = g_tree_node_value(node);
  91         assert(range);
  92     } else {
  93         /*
  94          * the previous range in the tree either partially covers the new
  95          * range or ends just at its beginning - extend it
  96          */
  97         if (dupcount) {
  98             *dupcount += intersection;
  99         }
 100
 101         count += start - range->start;
 102         range->count = MAX(range->count, count);
 103     }
 104
 105     /* check next nodes for possible merging */
 106     for (node = g_tree_node_next(node); node; ) {
 107         PageRange *rangecur;
 108
 109         rangecur = g_tree_node_value(node);
 110         assert(rangecur);
 111
 112         intersection = page_range_intersection_size(rangecur,
 113                                                     range->start, range->count);
 114         joinable = page_range_joinable_left(rangecur,
 115                                             range->start, range->count);
 116         if (!intersection && !joinable) {
 117             /* the current node is disjoint */
 118             break;
 119         }
 120
 121         if (dupcount) {
 122             *dupcount += intersection;
 123         }
 124
 125         count = rangecur->count + (rangecur->start - range->start);
 126         range->count = MAX(range->count, count);
 127
 128         /* the current node was merged in, remove it */
 129         start = rangecur->start;
 130         node = g_tree_node_next(node);
 131         /* no hinted removal in GTree... */
 132         g_tree_remove(tree.t, &start);
 133     }
 134 }
 135
 136 bool hvb_page_range_tree_pop(PageRangeTree tree, PageRange *out,
 137                              uint64_t maxcount)
 138 {
 139     GTreeNode *node;
 140     PageRange *range;
 141
 142     node = g_tree_node_last(tree.t);
 143     if (!node) {
 144         return false;
 145     }
 146
 147     range = g_tree_node_value(node);
 148     assert(range);
 149
 150     out->start = range->start;
 151
 152     /* can't modify range->start as it is the node key */
 153     if (range->count > maxcount) {
 154         out->start += range->count - maxcount;
 155         out->count = maxcount;
 156         range->count -= maxcount;
 157     } else {
 158         out->count = range->count;
 159         /* no hinted removal in GTree... */
 160         g_tree_remove(tree.t, &out->start);
 161     }
 162
 163     return true;
 164 }
 165
 166 bool hvb_page_range_tree_intree_any(PageRangeTree tree,
 167                                     uint64_t start, uint64_t count)
 168 {
 169     GTreeNode *node;
 170
 171     if (count == 0) {
 172         return false;
 173     }
 174
 175     /* find the first node that can possibly intersect our range */
 176     node = g_tree_upper_bound(tree.t, &start);
 177     if (node) {
 178         /*
 179          * a NULL node below means that the very first node in the tree
 180          * already has a higher key (the start of its range).
 181          */
 182         node = g_tree_node_previous(node);
 183     } else {
 184         /* a NULL node below means that the tree is empty */
 185         node = g_tree_node_last(tree.t);
 186     }
 187     /* node range start <= range start */
 188
 189     if (!node) {
 190         /* node range start > range start */
 191         node = g_tree_node_first(tree.t);
 192     }
 193
 194     for ( ; node; node = g_tree_node_next(node)) {
 195         PageRange *range = g_tree_node_value(node);
 196
 197         assert(range);
 198         /*
 199          * if this node starts beyond or at the end of our range so does
 200          * every next one
 201          */
 202         if (range->start >= start + count) {
 203             break;
 204         }
 205
 206         if (page_range_intersection_size(range, start, count) > 0) {
 207             return true;
 208         }
 209     }
 210
 211     return false;
 212 }
 213
 214 void hvb_page_range_tree_init(PageRangeTree *tree)
 215 {
 216     tree->t = g_tree_new_full(page_range_tree_key_compare, NULL,
 217                               g_free, g_free);
 218 }
 219
 220 void hvb_page_range_tree_destroy(PageRangeTree *tree)
 221 {
 222     /* g_tree_destroy() is not NULL-safe */
 223     if (!tree->t) {
 224         return;
 225     }
 226
 227     g_tree_destroy(tree->t);
 228     tree->t = NULL;
 229 }