@samitouri / QOSamiQemu
Code Commits Issues Pulls Sessions CI/CD
master
master
c 229 lines 6.18 KB
Raw
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 }