Re: [PATCH v2 09/12] util/reserved-region: Add new ReservedRegion helpers

[Eric Auger <eric.auger@redhat.com>]

Hi Jean,
On 9/29/23 18:16, Jean-Philippe Brucker wrote:
> On Wed, Sep 13, 2023 at 10:01:44AM +0200, Eric Auger wrote:
>> Introduce resv_region_list_insert() helper which inserts
>> a new ReservedRegion into a sorted list of reserved region.
>> In case of overlap, the new region has higher priority and
>> hides the existing overlapped segments. If the overlap is
>> partial, new regions are created for parts which are not
>> overlapped. The new region has higher priority independently
>> on the type of the regions.
>>
>> Signed-off-by: Eric Auger <eric.auger@redhat.com>
>> ---
>>  include/qemu/reserved-region.h | 32 ++++++++++++
>>  util/reserved-region.c         | 94 ++++++++++++++++++++++++++++++++++
>>  util/meson.build               |  1 +
>>  3 files changed, 127 insertions(+)
>>  create mode 100644 include/qemu/reserved-region.h
>>  create mode 100644 util/reserved-region.c
>>
>> diff --git a/include/qemu/reserved-region.h b/include/qemu/reserved-region.h
>> new file mode 100644
>> index 0000000000..8e6f0a97e2
>> --- /dev/null
>> +++ b/include/qemu/reserved-region.h
>> @@ -0,0 +1,32 @@
>> +/*
>> + * 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/>.
>> + */
>> +
>> +#ifndef QEMU_RESERVED_REGION_H
>> +#define QEMU_RESERVED_REGION_H
>> +
>> +#include "exec/memory.h"
>> +
>> +/*
>> + * Insert a new region into a sorted list of reserved regions. In case
>> + * there is overlap with existing regions, the new added region has
>> + * higher priority and replaces the overlapped segment.
>> + */
>> +GList *resv_region_list_insert(GList *list, ReservedRegion *reg);
>> +
>> +#endif
>> diff --git a/util/reserved-region.c b/util/reserved-region.c
>> new file mode 100644
>> index 0000000000..bb26a6bed3
>> --- /dev/null
>> +++ b/util/reserved-region.c
>> @@ -0,0 +1,94 @@
>> +/*
>> + * 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 = &reg->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 operlap */
> I guess this could just be 'else if', and the whole block below
> unindented. But I don't know if the function would look less or more scary :)
yeah if you don't mind I would be inclided to leave it as is. It
isolates the case where we have an overlap and you already reviewed it ;-).
>
>> +            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) {
> These four lines could just be 'l = prev->next'.
indeed!
>
>> +                    l = prev;
>> +                    if (l) {
>> +                        l = l->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);
> Looks correct overall
>
> Reviewed-by: Jean-Philippe Brucker <jean-philippe@linaro.org>

That must have been a pain, really appreciated!

Eric
>
>> +}
>> +
>> diff --git a/util/meson.build b/util/meson.build
>> index c4827fd70a..eb677b40c2 100644
>> --- a/util/meson.build
>> +++ b/util/meson.build
>> @@ -51,6 +51,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'))
>> -- 
>> 2.41.0
>>