Re: [PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals
> On 18 Apr 2024, at 07:28, Jan Beulich wrote:
>
> On 09.04.2024 13:45, Luca Fancellu wrote:
>> --- a/xen/arch/x86/extable.c
>> +++ b/xen/arch/x86/extable.c
>> @@ -23,7 +23,8 @@ static inline unsigned long ex_cont(const struct
>> exception_table_entry *x)
>> return EX_FIELD(x, cont);
>> }
>>
>> -static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b)
>> +static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b,
>> + const void *data)
>> {
>> const struct exception_table_entry *l = a, *r = b;
>> unsigned long lip = ex_addr(l);
>> @@ -53,7 +54,7 @@ void init_or_livepatch sort_exception_table(struct
>> exception_table_entry *start,
>> const struct exception_table_entry *stop)
>> {
>> sort(start, stop - start,
>> - sizeof(struct exception_table_entry), cmp_ex, swap_ex);
>> + sizeof(struct exception_table_entry), cmp_ex, swap_ex, NULL);
>> }
>
> Not the least because of this addition of an entirely useless parameter /
> argument
Well it’s not useless in this patch, given that without it I couldn’t know the
size of the address
element, however ...
> I'm not in favor of ...
>
>> --- a/xen/include/xen/sort.h
>> +++ b/xen/include/xen/sort.h
>> @@ -23,8 +23,8 @@
>> extern gnu_inline
>> #endif
>> void sort(void *base, size_t num, size_t size,
>> - int (*cmp)(const void *a, const void *b),
>> - void (*swap)(void *a, void *b, size_t size))
>> + int (*cmp)(const void *a, const void *b, const void *data),
>> + void (*swap)(void *a, void *b, size_t size), const void *cmp_data)
>> {
>
> ... this change. Consider you were doing this on a C library you cannot
> change.
> You'd have to find a different solution anyway.
I get your point here, we should not change standard functions.
> And the way we have sort()
> right now is matching the C spec. The change to do renders things unexpected
> to
> anyone wanting to use this function in a spec-compliant way. One approach may
> be to make an adjustment to data representation, such that the extra reference
> data is accessible through the pointers already being passed.
>
> Jan
>
Anyway in the end this patch was dropped for other reasons.
Cheers,
Luca
Re: [PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals
On 09.04.2024 13:45, Luca Fancellu wrote:
> --- a/xen/arch/x86/extable.c
> +++ b/xen/arch/x86/extable.c
> @@ -23,7 +23,8 @@ static inline unsigned long ex_cont(const struct
> exception_table_entry *x)
> return EX_FIELD(x, cont);
> }
>
> -static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b)
> +static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b,
> + const void *data)
> {
> const struct exception_table_entry *l = a, *r = b;
> unsigned long lip = ex_addr(l);
> @@ -53,7 +54,7 @@ void init_or_livepatch sort_exception_table(struct
> exception_table_entry *start,
> const struct exception_table_entry *stop)
> {
> sort(start, stop - start,
> - sizeof(struct exception_table_entry), cmp_ex, swap_ex);
> + sizeof(struct exception_table_entry), cmp_ex, swap_ex, NULL);
> }
Not the least because of this addition of an entirely useless parameter /
argument
I'm not in favor of ...
> --- a/xen/include/xen/sort.h
> +++ b/xen/include/xen/sort.h
> @@ -23,8 +23,8 @@
> extern gnu_inline
> #endif
> void sort(void *base, size_t num, size_t size,
> - int (*cmp)(const void *a, const void *b),
> - void (*swap)(void *a, void *b, size_t size))
> + int (*cmp)(const void *a, const void *b, const void *data),
> + void (*swap)(void *a, void *b, size_t size), const void *cmp_data)
> {
... this change. Consider you were doing this on a C library you cannot change.
You'd have to find a different solution anyway. And the way we have sort()
right now is matching the C spec. The change to do renders things unexpected to
anyone wanting to use this function in a spec-compliant way. One approach may
be to make an adjustment to data representation, such that the extra reference
data is accessible through the pointers already being passed.
Jan
Re: [PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals
> > I’ve just spotted an issue with the algorithm, the fix is this one: > > diff --git a/xen/common/device_tree.c b/xen/common/device_tree.c > index 24914a80d03b..262385a041a8 100644 > --- a/xen/common/device_tree.c > +++ b/xen/common/device_tree.c > @@ -2360,6 +2360,10 @@ int __init > dt_merge_overlapping_addr_size_intervals(__be32 *reg, int *nr_cells, > __be32 *tmp_last_cell_size = last_cell + addrcells; > > dt_set_cell(_last_cell_size, sizecells, new_size); > + > +/* Last interval updated, so the end is changed */ > +end_last = start_last + size_last; > + > /* > * This current interval is merged with the last one, so remove > this > * interval and shift left all the remaining elements > Apologies, this is the fix: diff --git a/xen/common/device_tree.c b/xen/common/device_tree.c index 24914a80d03b..9a2f5b27aa9b 100644 --- a/xen/common/device_tree.c +++ b/xen/common/device_tree.c @@ -2360,6 +2360,10 @@ int __init dt_merge_overlapping_addr_size_intervals(__be32 *reg, int *nr_cells, __be32 *tmp_last_cell_size = last_cell + addrcells; dt_set_cell(_last_cell_size, sizecells, new_size); + +/* Last interval updated, so the end is changed */ +end_last = start_last + new_size; + /* * This current interval is merged with the last one, so remove this * interval and shift left all the remaining elements So instead of “size_last” -> “new_size”. Sorry for the noise. Cheers, Luca
Re: [PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals
> On 9 Apr 2024, at 12:45, Luca Fancellu wrote:
>
> Introduce a function that given an array of cells containing
> (address,size) intervals, merges the overlapping ones, returning
> an array with no overlapping intervals.
>
> The algorithm needs to sort the intervals by ascending order
> address, so the sort() function already included in the codebase
> is used, however in this case additional data is needed for the
> compare function, to be able to extract the address from the
> interval.
> So add one argument to the sort() function and its compare
> callback to have additional data and be able to pass, in this
> case, the address length. In case the argument is not needed,
> NULL can be provided.
>
> Signed-off-by: Luca Fancellu
> ---
Hi all,
I’ve just spotted an issue with the algorithm, the fix is this one:
diff --git a/xen/common/device_tree.c b/xen/common/device_tree.c
index 24914a80d03b..262385a041a8 100644
--- a/xen/common/device_tree.c
+++ b/xen/common/device_tree.c
@@ -2360,6 +2360,10 @@ int __init
dt_merge_overlapping_addr_size_intervals(__be32 *reg, int *nr_cells,
__be32 *tmp_last_cell_size = last_cell + addrcells;
dt_set_cell(_last_cell_size, sizecells, new_size);
+
+/* Last interval updated, so the end is changed */
+end_last = start_last + size_last;
+
/*
* This current interval is merged with the last one, so remove
this
* interval and shift left all the remaining elements
Now, I would like to write something about the algorithm to ease the reviewers,
the problem is that we have some intervals and we would like to merge the
overlapping
ones, a simple algorithm can be found here:
https://www.interviewbit.com/blog/merge-intervals/
Limitation now is that when merging the intervals, we don’t want to exceed the
space needed
to store the information, for example:
sizecells: 1 (meaning one __be32, 4 byte)
Int1: start 0x0, size 0x
Int2: start 0x, size 0x1000
We can’t merge them because the new size would be over 4 byte.
During the development of this algorithm I’ve prototyped it in Python, I’ll
attach my script here
so that it’s easier to understand:
#!/usr/bin/env python3
def merge_intervals_inplace(intervals, size_limit):
merged = intervals[:]
last_idx = 0
i = 1
count = len(merged)
if count == 1:
return merged
last_cell = merged[last_idx]
start_last = last_cell[0]
size_last = last_cell[1]
end_last = start_last + size_last
while i < count:
start_current = merged[i][0]
size_current = merged[i][1]
end_current = start_current + size_current
overlap = end_last >= start_current
new_size = max(end_last, end_current) - start_last
#print((f"last ({start_last},{end_last}),"
# f" curr ({start_current},{end_current}),"
# f" newsize: {new_size}"
#))
# If the current interval doesn't overlap with the last one, or even if
# they overlap but the computed new size would be over the imposed
# limit, then advance the last element by one position
if (not overlap) or (overlap and new_size > size_limit):
#print("advance last")
last_idx += 1
last_cell = merged[last_idx]
start_last = last_cell[0]
size_last = last_cell[1]
end_last = start_last + size_last
else:
#print("merge")
# Set new size for the last element, merging the last interval with
# the current one
merged[last_idx] = (start_last, new_size)
# Update last elem interval end
end_last = start_last + new_size
# The current interval (i) is merged with the last, so remove it and
# shift left all the remaining intervals
merged = merged[:i] + merged[i+1:]
# Now the array has less element since we merged two intervals
count -= 1
# Next iteration needs to start from the current index, skip
# increment
continue
i += 1
return merged
def print_interval(intervals):
print("[", end='')
for interval in intervals:
s = interval[0]
sz = interval[1]
print(f" ({s},{sz}) ", end='')
print("] -> ", end='')
print("[", end='')
for interval in intervals:
s = interval[0]
e = interval[0] + interval[1]
print(f" ({s},{e}) ", end='')
print("]")
def main(argv):
limit=20
# Array of intervals (start address, size)
#banks = [(0,2), (5,1), (0,10), (10,7), (2,6)]
banks = [(0,20), (20,5), (10,15), (5,15)]
for interval in banks:
if interval[1] > limit:
raise Exception(f"{interval} size > limit ({limit})")
# Sort by start address ascending order
banks.sort(key=lambda a:
[PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals
Introduce a function that given an array of cells containing
(address,size) intervals, merges the overlapping ones, returning
an array with no overlapping intervals.
The algorithm needs to sort the intervals by ascending order
address, so the sort() function already included in the codebase
is used, however in this case additional data is needed for the
compare function, to be able to extract the address from the
interval.
So add one argument to the sort() function and its compare
callback to have additional data and be able to pass, in this
case, the address length. In case the argument is not needed,
NULL can be provided.
Signed-off-by: Luca Fancellu
---
v2:
- new patch
---
---
xen/arch/arm/bootfdt.c| 5 +-
xen/arch/arm/io.c | 11 ++-
xen/arch/x86/extable.c| 5 +-
xen/common/device_tree.c | 140 ++
xen/include/xen/device_tree.h | 19 +
xen/include/xen/sort.h| 14 ++--
6 files changed, 181 insertions(+), 13 deletions(-)
diff --git a/xen/arch/arm/bootfdt.c b/xen/arch/arm/bootfdt.c
index 4d708442a19e..a2aba67b45e7 100644
--- a/xen/arch/arm/bootfdt.c
+++ b/xen/arch/arm/bootfdt.c
@@ -521,7 +521,8 @@ static void __init early_print_info(void)
}
/* This function assumes that memory regions are not overlapped */
-static int __init cmp_memory_node(const void *key, const void *elem)
+static int __init cmp_memory_node(const void *key, const void *elem,
+ const void *data)
{
const struct membank *handler0 = key;
const struct membank *handler1 = elem;
@@ -569,7 +570,7 @@ size_t __init boot_fdt_info(const void *fdt, paddr_t paddr)
* the banks sorted in ascending order. So sort them through.
*/
sort(mem->bank, mem->nr_banks, sizeof(struct membank),
- cmp_memory_node, swap_memory_node);
+ cmp_memory_node, swap_memory_node, NULL);
early_print_info();
diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 96c740d5636c..c1814491fec4 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -57,7 +57,7 @@ static enum io_state handle_write(const struct mmio_handler
*handler,
}
/* This function assumes that mmio regions are not overlapped */
-static int cmp_mmio_handler(const void *key, const void *elem)
+static int cmp_mmio_handler(const void *key, const void *elem, const void
*data)
{
const struct mmio_handler *handler0 = key;
const struct mmio_handler *handler1 = elem;
@@ -71,6 +71,11 @@ static int cmp_mmio_handler(const void *key, const void
*elem)
return 0;
}
+static int bsearch_cmp_mmio_handler(const void *key, const void *elem)
+{
+return cmp_mmio_handler(key, elem, NULL);
+}
+
static void swap_mmio_handler(void *_a, void *_b, size_t size)
{
struct mmio_handler *a = _a, *b = _b;
@@ -87,7 +92,7 @@ static const struct mmio_handler *find_mmio_handler(struct
domain *d,
read_lock(>lock);
handler = bsearch(, vmmio->handlers, vmmio->num_entries,
- sizeof(*handler), cmp_mmio_handler);
+ sizeof(*handler), bsearch_cmp_mmio_handler);
read_unlock(>lock);
return handler;
@@ -219,7 +224,7 @@ void register_mmio_handler(struct domain *d,
/* Sort mmio handlers in ascending order based on base address */
sort(vmmio->handlers, vmmio->num_entries, sizeof(struct mmio_handler),
- cmp_mmio_handler, swap_mmio_handler);
+ cmp_mmio_handler, swap_mmio_handler, NULL);
write_unlock(>lock);
}
diff --git a/xen/arch/x86/extable.c b/xen/arch/x86/extable.c
index 8415cd1fa249..589e251b29b9 100644
--- a/xen/arch/x86/extable.c
+++ b/xen/arch/x86/extable.c
@@ -23,7 +23,8 @@ static inline unsigned long ex_cont(const struct
exception_table_entry *x)
return EX_FIELD(x, cont);
}
-static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b)
+static int init_or_livepatch cf_check cmp_ex(const void *a, const void *b,
+ const void *data)
{
const struct exception_table_entry *l = a, *r = b;
unsigned long lip = ex_addr(l);
@@ -53,7 +54,7 @@ void init_or_livepatch sort_exception_table(struct
exception_table_entry *start,
const struct exception_table_entry *stop)
{
sort(start, stop - start,
- sizeof(struct exception_table_entry), cmp_ex, swap_ex);
+ sizeof(struct exception_table_entry), cmp_ex, swap_ex, NULL);
}
void __init sort_exception_tables(void)
diff --git a/xen/common/device_tree.c b/xen/common/device_tree.c
index 8d1017a49d80..24914a80d03b 100644
--- a/xen/common/device_tree.c
+++ b/xen/common/device_tree.c
@@ -18,6 +18,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -2243,6 +2244,145 @@ int dt_get_pci_domain_nr(struct dt_device_node *node)
return (u16)domain;
}
+static int __init cmp_mem_reg_cell(const void *key, const void *elem,
+
