> On 9 Apr 2024, at 12:45, Luca Fancellu <luca.fance...@arm.com> 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 <luca.fance...@arm.com>
> ---
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(&tmp_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 0xFFFFFFFF
Int2: start 0xFFFFFFFF, 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: a[0])
print("IN (sorted) [(start,size)] -> [(start,end)]")
print_interval(banks)
banks = merge_intervals_inplace(banks, limit)
print("OUT [(start,size)] -> [(start,end)]")
print_interval(banks)
if __name__ == "__main__":
main(sys.argv[1:])
Cheers,
Luca
