Re: [PATCH] x86/NUMA: improve memnode_shift calculation for multi node system

[Andrew Cooper <Andrew.Cooper3@citrix.com>]

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