hw/hyperv/hv-balloon-page_range_tree.h

   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