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 = ®->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 92