On 27/09/2022 17:20, Jan Beulich wrote: > --- a/xen/arch/x86/srat.c > +++ b/xen/arch/x86/srat.c > @@ -413,14 +414,37 @@ acpi_numa_memory_affinity_init(const str > node, pxm, start, end - 1, > ma->flags & ACPI_SRAT_MEM_HOT_PLUGGABLE ? " (hotplug)" : ""); > > - node_memblk_range[num_node_memblks].start = start; > - node_memblk_range[num_node_memblks].end = end; > - memblk_nodeid[num_node_memblks] = node; > + /* Keep node_memblk_range[] sorted by address. */ > + for (i = 0; i < num_node_memblks; ++i) > + if (node_memblk_range[i].start > start || > + (node_memblk_range[i].start == start && > + node_memblk_range[i].end > end)) > + break; > + > + memmove(&node_memblk_range[i + 1], &node_memblk_range[i], > + (num_node_memblks - i) * sizeof(*node_memblk_range)); > + node_memblk_range[i].start = start; > + node_memblk_range[i].end = end; > + > + memmove(&memblk_nodeid[i + 1], &memblk_nodeid[i], > + (num_node_memblks - i) * sizeof(*memblk_nodeid)); > + memblk_nodeid[i] = node;
This is now the 4th example we have of logic wanting a sorted array. (two examples in ARM code which want to switch away from using sort(), and the VMX MSR lists). I was already contemplating doing a small library (static inline, or perhaps extern inline now we've started using that) to abstract away the insert/find/delete operations and their decidedly non-trivial pointer operations. The secondary purpose was to be able to do some actual unit tests of the library, so we can be rather better assured of correctness. For this case, and the two ARM cases, the firmware data is supposed to be sorted to begin with, so the search-for-insertion loop should look at the num_node_memblks entry first because the overwhelming common case is that the end is the correct place to put it. If not, it should binary search backwards rather than doing a linear search. Obviously not work for 4.17, but there's a lot of value in such a library. ~Andrew
