Re: [PATCH v2 12/13] xen/device_tree: Introduce function to merge overlapping intervals

[Luca Fancellu <Luca.Fancellu@xxxxxxx>]

> On 9 Apr 2024, at 12:45, Luca Fancellu <Luca.Fancellu@xxxxxxx> 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.fancellu@xxxxxxx>
> ---

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