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