util/reserved-region.c

   1 /*
   2  * QEMU ReservedRegion helpers
   3  *
   4  * Copyright (c) 2023 Red Hat, Inc.
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include "qemu/osdep.h"
  21 #include "qemu/range.h"
  22 #include "qemu/reserved-region.h"
  23
  24 GList *resv_region_list_insert(GList *list, ReservedRegion *reg)
  25 {
  26     ReservedRegion *resv_iter, *new_reg;
  27     Range *r = &reg->range;
  28     Range *range_iter;
  29     GList *l;
  30
  31     for (l = list; l ; ) {
  32         resv_iter = (ReservedRegion *)l->data;
  33         range_iter = &resv_iter->range;
  34
  35         /* Skip all list elements strictly less than range to add */
  36         if (range_compare(range_iter, r) < 0) {
  37             l = l->next;
  38         } else if (range_compare(range_iter, r) > 0) {
  39             return g_list_insert_before(list, l, reg);
  40         } else { /* there is an overlap */
  41             if (range_contains_range(r, range_iter)) {
  42                 /* new range contains current item, simply remove this latter */
  43                 GList *prev = l->prev;
  44                 g_free(l->data);
  45                 list = g_list_delete_link(list, l);
  46                 if (prev) {
  47                     l = prev->next;
  48                 } else {
  49                     l = list;
  50                 }
  51             } else if (range_contains_range(range_iter, r)) {
  52                 /* new region is included in the current region */
  53                 if (range_lob(range_iter) == range_lob(r)) {
  54                     /* adjacent on the left side, derives into 2 regions */
  55                     range_set_bounds(range_iter, range_upb(r) + 1,
  56                                      range_upb(range_iter));
  57                     return g_list_insert_before(list, l, reg);
  58                 } else if (range_upb(range_iter) == range_upb(r)) {
  59                     /* adjacent on the right side, derives into 2 regions */
  60                     range_set_bounds(range_iter, range_lob(range_iter),
  61                                      range_lob(r) - 1);
  62                     l = l->next;
  63                 } else {
  64                     uint64_t lob = range_lob(range_iter);
  65                     /*
  66                      * the new range is in the middle of an existing one,
  67                      * split this latter into 3 regs instead
  68                      */
  69                     range_set_bounds(range_iter, range_upb(r) + 1,
  70                                      range_upb(range_iter));
  71                     new_reg = g_new0(ReservedRegion, 1);
  72                     new_reg->type = resv_iter->type;
  73                     range_set_bounds(&new_reg->range,
  74                                      lob, range_lob(r) - 1);
  75                     list = g_list_insert_before(list, l, new_reg);
  76                     return g_list_insert_before(list, l, reg);
  77                 }
  78             } else if (range_lob(r) < range_lob(range_iter)) {
  79                 range_set_bounds(range_iter, range_upb(r) + 1,
  80                                  range_upb(range_iter));
  81                 return g_list_insert_before(list, l, reg);
  82             } else { /* intersection on the upper range */
  83                 range_set_bounds(range_iter, range_lob(range_iter),
  84                                  range_lob(r) - 1);
  85                 l = l->next;
  86             }
  87         } /* overlap */
  88     }
  89     return g_list_append(list, reg);
  90 }
  91