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) */
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) */
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 
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 
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 
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 
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 
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 
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