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