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