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

[Ralf Hoffmann]

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 
---
 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++) {

-   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;
 }

 /*
@@ -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 */
-- 
2.1.4

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

[Gonzalez Monroy, Sergio]

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

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

[Jay Rolette]

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

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

[Gonzalez Monroy, Sergio]

On 08/09/2015 14:29, Jay Rolette wrote:
> 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.
>
Fair enough.
Actually, we already use qsort in 
lib/librte_eal/linuxapp/eal/eal_hugeapge_info.c

> I submitted a patch for this close to a year ago: 
> http://dpdk.org/dev/patchwork/patch/2061/
>
I just had a quick look at it and seems to be archived with 'Changes 
Requested' status.

I will comment on it.

Sergio
> Jay
>
> On Tue, Sep 8, 2015 at 7:45 AM, Gonzalez Monroy, Sergio 
>  > 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
>  >
> ---
>   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)
>   

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

[Ralf Hoffmann]

Hi Sergio,

On 08.09.2015 14:45, Gonzalez Monroy, Sergio wrote:
> Just a few comments/suggestions:
> 
> Add 'eal/linux:'  to the commit title, ie:
>   "eal/linux: change hugepage sorting to avoid overlapping memcpy"
> 

I would modify the patch according to your notes if needed, but if you
consider the other patch from Jay, then I would vote for that instead.
Actually, I thought about using qsort too, but decided against it to
keep the number of changes low and the sorting speed is not a problem
for me. Changing the return value of that function to void might still
be a good idea.

Best Regards,

Ralf

-- 
Ralf Hoffmann
Allegro Packets GmbH
K?the-Kollwitz-Str. 54
04109 Leipzig
HRB 30535, Amtsgericht Leipzig