Re: [dpdk-dev] [PATCH v1] change hugepage sorting to avoid overlapping memcpy

[Jay Rolette <rolette@infiniteio.com>]

Most of the code in sort_by_physaddr() should be replaced by a call to
qsort() instead. Less code and gets rid of an O(n^2) sort. It's only init
code, but given how long EAL init takes, every bit helps.

I submitted a patch for this close to a year ago:
http://dpdk.org/dev/patchwork/patch/2061/

Jay

On Tue, Sep 8, 2015 at 7:45 AM, Gonzalez Monroy, Sergio <
sergio.gonzalez.monroy@intel.com> wrote:

> Hi Ralf,
>
> Just a few comments/suggestions:
>
> Add 'eal/linux:'  to the commit title, ie:
>   "eal/linux: change hugepage sorting to avoid overlapping memcpy"
>
> On 04/09/2015 11:14, Ralf Hoffmann wrote:
>
>> with only one hugepage or already sorted hugepage addresses, the sort
>> function called memcpy with same src and dst pointer. Debugging with
>> valgrind will issue a warning about overlapping area. This patch changes
>> the bubble sort to avoid this behavior. Also, the function cannot fail
>> any longer.
>>
>> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
>> ---
>>   lib/librte_eal/linuxapp/eal/eal_memory.c | 27
>> +++++++++++++--------------
>>   1 file changed, 13 insertions(+), 14 deletions(-)
>>
>> diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c
>> b/lib/librte_eal/linuxapp/eal/eal_memory.c
>> index ac2745e..6d01f61 100644
>> --- a/lib/librte_eal/linuxapp/eal/eal_memory.c
>> +++ b/lib/librte_eal/linuxapp/eal/eal_memory.c
>> @@ -699,25 +699,25 @@ error:
>>    * higher address first on powerpc). We use a slow algorithm, but we
>> won't
>>    * have millions of pages, and this is only done at init time.
>>    */
>> -static int
>> +static void
>>   sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info
>> *hpi)
>>   {
>>         unsigned i, j;
>> -       int compare_idx;
>> +       unsigned compare_idx;
>>         uint64_t compare_addr;
>>         struct hugepage_file tmp;
>>         for (i = 0; i < hpi->num_pages[0]; i++) {
>> -               compare_addr = 0;
>> -               compare_idx = -1;
>> +               compare_addr = hugepg_tbl[i].physaddr;
>> +               compare_idx = i;
>>                 /*
>> -                * browse all entries starting at 'i', and find the
>> +                * browse all entries starting at 'i+1', and find the
>>                  * entry with the smallest addr
>>                  */
>> -               for (j=i; j< hpi->num_pages[0]; j++) {
>> +               for (j=i + 1; j < hpi->num_pages[0]; j++) {
>>
> Although there are many style/checkpatch issues in current code, we try to
> fix them
> in new patches.
> In that regard, checkpatch complains about above line with:
> ERROR:SPACING: spaces required around that '='
>
>   -                     if (compare_addr == 0 ||
>> +                       if (
>>   #ifdef RTE_ARCH_PPC_64
>>                                 hugepg_tbl[j].physaddr > compare_addr) {
>>   #else
>> @@ -728,10 +728,9 @@ sort_by_physaddr(struct hugepage_file *hugepg_tbl,
>> struct hugepage_info *hpi)
>>                         }
>>                 }
>>   -             /* should not happen */
>> -               if (compare_idx == -1) {
>> -                       RTE_LOG(ERR, EAL, "%s(): error in physaddr
>> sorting\n", __func__);
>> -                       return -1;
>> +               if (compare_idx == i) {
>> +                       /* no smaller page found */
>> +                       continue;
>>                 }
>>                 /* swap the 2 entries in the table */
>> @@ -741,7 +740,8 @@ sort_by_physaddr(struct hugepage_file *hugepg_tbl,
>> struct hugepage_info *hpi)
>>                         sizeof(struct hugepage_file));
>>                 memcpy(&hugepg_tbl[i], &tmp, sizeof(struct
>> hugepage_file));
>>         }
>> -       return 0;
>> +
>> +       return;
>>   }
>>
> I reckon checkpatch is not picking this one because the end-of-function is
> not part of the patch,
> but it is a warning:
> WARNING:RETURN_VOID: void function return statements are not generally
> useful
>
>     /*
>> @@ -1164,8 +1164,7 @@ rte_eal_hugepage_init(void)
>>                         goto fail;
>>                 }
>>   -             if (sort_by_physaddr(&tmp_hp[hp_offset], hpi) < 0)
>> -                       goto fail;
>> +               sort_by_physaddr(&tmp_hp[hp_offset], hpi);
>>     #ifdef RTE_EAL_SINGLE_FILE_SEGMENTS
>>                 /* remap all hugepages into single file segments */
>>
>>
>>
> Thanks,
> Sergio
>