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