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