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