2 * QEMU Hyper-V Dynamic Memory Protocol driver
4 * Copyright (C) 2020-2023 Oracle and/or its affiliates.
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.
10 #include "hv-balloon-internal.h"
11 #include "hv-balloon-page_range_tree.h"
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
18 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
21 static gint
page_range_tree_key_compare(gconstpointer leftp
,
25 const uint64_t *left
= leftp
, *right
= rightp
;
29 } else if (*left
> *right
) {
31 } else { /* *left == *right */
36 static GTreeNode
*page_range_tree_insert_new(PageRangeTree tree
,
37 uint64_t start
, uint64_t count
)
39 uint64_t *key
= g_malloc(sizeof(*key
));
40 PageRange
*range
= g_malloc(sizeof(*range
));
44 *key
= range
->start
= start
;
47 return g_tree_insert_node(tree
.t
, key
, range
);
50 void hvb_page_range_tree_insert(PageRangeTree tree
,
51 uint64_t start
, uint64_t count
,
56 uint64_t intersection
;
59 assert(!SUM_OVERFLOW_U64(start
, count
));
64 node
= g_tree_upper_bound(tree
.t
, &start
);
66 node
= g_tree_node_previous(node
);
68 node
= g_tree_node_last(tree
.t
);
72 range
= g_tree_node_value(node
);
74 intersection
= page_range_intersection_size(range
, start
, count
);
75 joinable
= page_range_joinable_right(range
, start
, count
);
79 (!intersection
&& !joinable
)) {
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.
87 node
= page_range_tree_insert_new(tree
, start
, count
);
89 range
= g_tree_node_value(node
);
93 * the previous range in the tree either partially covers the new
94 * range or ends just at its beginning - extend it
97 *dupcount
+= intersection
;
100 count
+= start
- range
->start
;
101 range
->count
= MAX(range
->count
, count
);
104 /* check next nodes for possible merging */
105 for (node
= g_tree_node_next(node
); node
; ) {
108 rangecur
= g_tree_node_value(node
);
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 */
121 *dupcount
+= intersection
;
124 count
= rangecur
->count
+ (rangecur
->start
- range
->start
);
125 range
->count
= MAX(range
->count
, count
);
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
);
135 bool hvb_page_range_tree_pop(PageRangeTree tree
, PageRange
*out
,
141 node
= g_tree_node_last(tree
.t
);
146 range
= g_tree_node_value(node
);
149 out
->start
= range
->start
;
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
;
157 out
->count
= range
->count
;
158 /* no hinted removal in GTree... */
159 g_tree_remove(tree
.t
, &out
->start
);
165 bool hvb_page_range_tree_intree_any(PageRangeTree tree
,
166 uint64_t start
, uint64_t count
)
174 /* find the first node that can possibly intersect our range */
175 node
= g_tree_upper_bound(tree
.t
, &start
);
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).
181 node
= g_tree_node_previous(node
);
183 /* a NULL node below means that the tree is empty */
184 node
= g_tree_node_last(tree
.t
);
186 /* node range start <= range start */
189 /* node range start > range start */
190 node
= g_tree_node_first(tree
.t
);
193 for ( ; node
; node
= g_tree_node_next(node
)) {
194 PageRange
*range
= g_tree_node_value(node
);
198 * if this node starts beyond or at the end of our range so does
201 if (range
->start
>= start
+ count
) {
205 if (page_range_intersection_size(range
, start
, count
) > 0) {
213 void hvb_page_range_tree_init(PageRangeTree
*tree
)
215 tree
->t
= g_tree_new_full(page_range_tree_key_compare
, NULL
,
219 void hvb_page_range_tree_destroy(PageRangeTree
*tree
)
221 /* g_tree_destroy() is not NULL-safe */
226 g_tree_destroy(tree
->t
);