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:
