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

[Jan Beulich <jbeulich@xxxxxxxx>]

On 30.09.2022 13:54, Andrew Cooper wrote:
> 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.

For using such library routines the data structures here would need
re-organizing first: We're inserting into two arrays and a bitmap at
the same time.

> 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.

Well, yes, perhaps. Of course we don't expect there to be very many
entries, at which point I guess a linear search can be deemed acceptable.

Jan