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