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 #ifndef HW_HYPERV_HV_BALLOON_PAGE_RANGE_TREE_H
11 #define HW_HYPERV_HV_BALLOON_PAGE_RANGE_TREE_H
12
13 #include "qemu/osdep.h"
14
15 /* PageRange */
16 typedef struct PageRange {
17 uint64_t start;
18 uint64_t count;
19 } PageRange;
20
21 /* return just the part of range before (start) */
page_range_part_before(const PageRange * range,uint64_t start,PageRange * out)22 static inline void page_range_part_before(const PageRange *range,
23 uint64_t start, PageRange *out)
24 {
25 uint64_t endr = range->start + range->count;
26 uint64_t end = MIN(endr, start);
27
28 out->start = range->start;
29 if (end > out->start) {
30 out->count = end - out->start;
31 } else {
32 out->count = 0;
33 }
34 }
35
36 /* return just the part of range after (start, count) */
page_range_part_after(const PageRange * range,uint64_t start,uint64_t count,PageRange * out)37 static inline void page_range_part_after(const PageRange *range,
38 uint64_t start, uint64_t count,
39 PageRange *out)
40 {
41 uint64_t end = range->start + range->count;
42 uint64_t ends = start + count;
43
44 out->start = MAX(range->start, ends);
45 if (end > out->start) {
46 out->count = end - out->start;
47 } else {
48 out->count = 0;
49 }
50 }
51
page_range_intersect(const PageRange * range,uint64_t start,uint64_t count,PageRange * out)52 static inline void page_range_intersect(const PageRange *range,
53 uint64_t start, uint64_t count,
54 PageRange *out)
55 {
56 uint64_t end1 = range->start + range->count;
57 uint64_t end2 = start + count;
58 uint64_t end = MIN(end1, end2);
59
60 out->start = MAX(range->start, start);
61 out->count = out->start < end ? end - out->start : 0;
62 }
63
page_range_intersection_size(const PageRange * range,uint64_t start,uint64_t count)64 static inline uint64_t page_range_intersection_size(const PageRange *range,
65 uint64_t start, uint64_t count)
66 {
67 PageRange trange;
68
69 page_range_intersect(range, start, count, &trange);
70 return trange.count;
71 }
72
page_range_joinable_left(const PageRange * range,uint64_t start,uint64_t count)73 static inline bool page_range_joinable_left(const PageRange *range,
74 uint64_t start, uint64_t count)
75 {
76 return start + count == range->start;
77 }
78
page_range_joinable_right(const PageRange * range,uint64_t start,uint64_t count)79 static inline bool page_range_joinable_right(const PageRange *range,
80 uint64_t start, uint64_t count)
81 {
82 return range->start + range->count == start;
83 }
84
page_range_joinable(const PageRange * range,uint64_t start,uint64_t count)85 static inline bool page_range_joinable(const PageRange *range,
86 uint64_t start, uint64_t count)
87 {
88 return page_range_joinable_left(range, start, count) ||
89 page_range_joinable_right(range, start, count);
90 }
91
92 /* PageRangeTree */
93 /* type safety */
94 typedef struct PageRangeTree {
95 GTree *t;
96 } PageRangeTree;
97
page_range_tree_is_empty(PageRangeTree tree)98 static inline bool page_range_tree_is_empty(PageRangeTree tree)
99 {
100 guint nnodes = g_tree_nnodes(tree.t);
101
102 return nnodes == 0;
103 }
104
105 void hvb_page_range_tree_init(PageRangeTree *tree);
106 void hvb_page_range_tree_destroy(PageRangeTree *tree);
107
108 bool hvb_page_range_tree_intree_any(PageRangeTree tree,
109 uint64_t start, uint64_t count);
110
111 bool hvb_page_range_tree_pop(PageRangeTree tree, PageRange *out,
112 uint64_t maxcount);
113
114 void hvb_page_range_tree_insert(PageRangeTree tree,
115 uint64_t start, uint64_t count,
116 uint64_t *dupcount);
117
118 #endif
119