diff options
Diffstat (limited to 'util')
| -rw-r--r-- | util/meson.build | 1 | ||||
| -rw-r--r-- | util/range.c | 61 | ||||
| -rw-r--r-- | util/reserved-region.c | 91 | ||||
| -rw-r--r-- | util/uuid.c | 2 |
4 files changed, 149 insertions, 6 deletions
diff --git a/util/meson.build b/util/meson.build index 769b24f2e0..c3a24af5c5 100644 --- a/util/meson.build +++ b/util/meson.build @@ -52,6 +52,7 @@ util_ss.add(files('qdist.c')) util_ss.add(files('qht.c')) util_ss.add(files('qsp.c')) util_ss.add(files('range.c')) +util_ss.add(files('reserved-region.c')) util_ss.add(files('stats64.c')) util_ss.add(files('systemd.c')) util_ss.add(files('transactions.c')) diff --git a/util/range.c b/util/range.c index 098d9d2dc0..9605ccfcbe 100644 --- a/util/range.c +++ b/util/range.c @@ -20,11 +20,7 @@ #include "qemu/osdep.h" #include "qemu/range.h" -/* - * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap. - * Both @a and @b must not be empty. - */ -static inline int range_compare(Range *a, Range *b) +int range_compare(Range *a, Range *b) { assert(!range_is_empty(a) && !range_is_empty(b)); @@ -70,3 +66,58 @@ GList *range_list_insert(GList *list, Range *data) return list; } + +static inline +GList *append_new_range(GList *list, uint64_t lob, uint64_t upb) +{ + Range *new = g_new0(Range, 1); + + range_set_bounds(new, lob, upb); + return g_list_append(list, new); +} + + +void range_inverse_array(GList *in, GList **rev, + uint64_t low, uint64_t high) +{ + Range *r, *rn; + GList *l = in, *out = *rev; + + for (l = in; l && range_upb(l->data) < low; l = l->next) { + continue; + } + + if (!l) { + out = append_new_range(out, low, high); + goto exit; + } + r = (Range *)l->data; + + /* first range lob is greater than min, insert a first range */ + if (range_lob(r) > low) { + out = append_new_range(out, low, MIN(range_lob(r) - 1, high)); + } + + /* insert a range inbetween each original range until we reach high */ + for (; l->next; l = l->next) { + r = (Range *)l->data; + rn = (Range *)l->next->data; + if (range_lob(r) >= high) { + goto exit; + } + if (range_compare(r, rn)) { + out = append_new_range(out, range_upb(r) + 1, + MIN(range_lob(rn) - 1, high)); + } + } + + /* last range */ + r = (Range *)l->data; + + /* last range upb is less than max, insert a last range */ + if (range_upb(r) < high) { + out = append_new_range(out, range_upb(r) + 1, high); + } +exit: + *rev = out; +} diff --git a/util/reserved-region.c b/util/reserved-region.c new file mode 100644 index 0000000000..18f83eb4c6 --- /dev/null +++ b/util/reserved-region.c @@ -0,0 +1,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); +} + diff --git a/util/uuid.c b/util/uuid.c index d71aa79e5e..234619dd5e 100644 --- a/util/uuid.c +++ b/util/uuid.c @@ -51,7 +51,7 @@ int qemu_uuid_is_equal(const QemuUUID *lhv, const QemuUUID *rhv) void qemu_uuid_unparse(const QemuUUID *uuid, char *out) { const unsigned char *uu = &uuid->data[0]; - snprintf(out, UUID_FMT_LEN + 1, UUID_FMT, + snprintf(out, UUID_STR_LEN, UUID_FMT, uu[0], uu[1], uu[2], uu[3], uu[4], uu[5], uu[6], uu[7], uu[8], uu[9], uu[10], uu[11], uu[12], uu[13], uu[14], uu[15]); } |