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 } 230