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

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

Re: [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 <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

Re: [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@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
>

Re: [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 
> <sergio.gonzalez.monroy@intel.com 
> <mailto: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
>         <mailto: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
>
>

[dpdk-dev] [PATCH v2 0/1] change hugepage sorting to avoid overlapping memcpy

[Ralf Hoffmann]

Hi,

I want to catch up with the patch about the overlapping memory
areas/hugepage sorting. I have incorporated the qsort patch from Jay
and made the suggested changes. So this fixes both the valgrind
warning about the overlapping memcpy and possible performance problems
due to the bubblesort.

Best Regards,

Ralf

---
Ralf Hoffmann (1):
  change hugepage sorting to avoid overlapping memcpy

 lib/librte_eal/linuxapp/eal/eal_memory.c | 60 ++++++++------------------------
 1 file changed, 14 insertions(+), 46 deletions(-)

-- 
2.5.0

[dpdk-dev] [PATCH v2 1/1] 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 sort method to qsort to avoid this behavior, according to
original patch from Jay Rolette <rolette@infiniteio.com>. The separate
sort function is no longer necessary.

Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
---
v2:

* incorporate patch from http://dpdk.org/dev/patchwork/patch/2061/
  to use qsort instead of bubble sort,
  original patch by Jay Rolette <rolette@infiniteio.com>

 lib/librte_eal/linuxapp/eal/eal_memory.c | 60 ++++++++------------------------
 1 file changed, 14 insertions(+), 46 deletions(-)

diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c b/lib/librte_eal/linuxapp/eal/eal_memory.c
index 846fd31..a96d10a 100644
--- a/lib/librte_eal/linuxapp/eal/eal_memory.c
+++ b/lib/librte_eal/linuxapp/eal/eal_memory.c
@@ -701,54 +701,23 @@ error:
 	return -1;
 }
 
-/*
- * Sort the hugepg_tbl by physical address (lower addresses first on x86,
- * 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
-sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info *hpi)
+cmp_physaddr(const void *a, const void *b)
 {
-	unsigned i, j;
-	int 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;
-
-		/*
-		 * browse all entries starting at 'i', and find the
-		 * entry with the smallest addr
-		 */
-		for (j=i; j< hpi->num_pages[0]; j++) {
-
-			if (compare_addr == 0 ||
-#ifdef RTE_ARCH_PPC_64
-				hugepg_tbl[j].physaddr > compare_addr) {
+#ifndef RTE_ARCH_PPC_64
+	const struct hugepage_file *p1 = (const struct hugepage_file *)a;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)b;
 #else
-				hugepg_tbl[j].physaddr < compare_addr) {
+	/* PowerPC needs memory sorted in reverse order from x86 */
+	const struct hugepage_file *p1 = (const struct hugepage_file *)b;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)a;
 #endif
-				compare_addr = hugepg_tbl[j].physaddr;
-				compare_idx = j;
-			}
-		}
-
-		/* should not happen */
-		if (compare_idx == -1) {
-			RTE_LOG(ERR, EAL, "%s(): error in physaddr sorting\n", __func__);
-			return -1;
-		}
-
-		/* swap the 2 entries in the table */
-		memcpy(&tmp, &hugepg_tbl[compare_idx],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[compare_idx], &hugepg_tbl[i],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[i], &tmp, sizeof(struct hugepage_file));
-	}
-	return 0;
+	if (p1->physaddr < p2->physaddr)
+		return -1;
+	else if (p1->physaddr > p2->physaddr)
+		return 1;
+	else
+		return 0;
 }
 
 /*
@@ -1195,8 +1164,7 @@ rte_eal_hugepage_init(void)
 			goto fail;
 		}
 
-		if (sort_by_physaddr(&tmp_hp[hp_offset], hpi) < 0)
-			goto fail;
+		qsort(&tmp_hp[hp_offset], hpi->num_pages[0], sizeof(struct hugepage_file), cmp_physaddr);
 
 #ifdef RTE_EAL_SINGLE_FILE_SEGMENTS
 		/* remap all hugepages into single file segments */
-- 
2.5.0

[dpdk-dev] [PATCH v3 0/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Ralf Hoffmann]

Hi again,

I forgot to correctly set the commit title, so this is v3.

Best Regards,

Ralf

---
Ralf Hoffmann (1):
  change hugepage sorting to avoid overlapping memcpy

 lib/librte_eal/linuxapp/eal/eal_memory.c | 60 ++++++++------------------------
 1 file changed, 14 insertions(+), 46 deletions(-)

-- 
2.5.0

[dpdk-dev] [PATCH v3 1/1] eal/linux: 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 sort method to qsort to avoid this behavior, according to
original patch from Jay Rolette <rolette@infiniteio.com>. The separate
sort function is no longer necessary.

Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
---
v3:
* set commit title to eal/linux

v2:

* incorporate patch from http://dpdk.org/dev/patchwork/patch/2061/
  to use qsort instead of bubble sort,
  original patch by Jay Rolette <rolette@infiniteio.com>

 lib/librte_eal/linuxapp/eal/eal_memory.c | 60 ++++++++------------------------
 1 file changed, 14 insertions(+), 46 deletions(-)

diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c b/lib/librte_eal/linuxapp/eal/eal_memory.c
index 846fd31..a96d10a 100644
--- a/lib/librte_eal/linuxapp/eal/eal_memory.c
+++ b/lib/librte_eal/linuxapp/eal/eal_memory.c
@@ -701,54 +701,23 @@ error:
 	return -1;
 }
 
-/*
- * Sort the hugepg_tbl by physical address (lower addresses first on x86,
- * 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
-sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info *hpi)
+cmp_physaddr(const void *a, const void *b)
 {
-	unsigned i, j;
-	int 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;
-
-		/*
-		 * browse all entries starting at 'i', and find the
-		 * entry with the smallest addr
-		 */
-		for (j=i; j< hpi->num_pages[0]; j++) {
-
-			if (compare_addr == 0 ||
-#ifdef RTE_ARCH_PPC_64
-				hugepg_tbl[j].physaddr > compare_addr) {
+#ifndef RTE_ARCH_PPC_64
+	const struct hugepage_file *p1 = (const struct hugepage_file *)a;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)b;
 #else
-				hugepg_tbl[j].physaddr < compare_addr) {
+	/* PowerPC needs memory sorted in reverse order from x86 */
+	const struct hugepage_file *p1 = (const struct hugepage_file *)b;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)a;
 #endif
-				compare_addr = hugepg_tbl[j].physaddr;
-				compare_idx = j;
-			}
-		}
-
-		/* should not happen */
-		if (compare_idx == -1) {
-			RTE_LOG(ERR, EAL, "%s(): error in physaddr sorting\n", __func__);
-			return -1;
-		}
-
-		/* swap the 2 entries in the table */
-		memcpy(&tmp, &hugepg_tbl[compare_idx],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[compare_idx], &hugepg_tbl[i],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[i], &tmp, sizeof(struct hugepage_file));
-	}
-	return 0;
+	if (p1->physaddr < p2->physaddr)
+		return -1;
+	else if (p1->physaddr > p2->physaddr)
+		return 1;
+	else
+		return 0;
 }
 
 /*
@@ -1195,8 +1164,7 @@ rte_eal_hugepage_init(void)
 			goto fail;
 		}
 
-		if (sort_by_physaddr(&tmp_hp[hp_offset], hpi) < 0)
-			goto fail;
+		qsort(&tmp_hp[hp_offset], hpi->num_pages[0], sizeof(struct hugepage_file), cmp_physaddr);
 
 #ifdef RTE_EAL_SINGLE_FILE_SEGMENTS
 		/* remap all hugepages into single file segments */
-- 
2.5.0

Re: [dpdk-dev] [PATCH v3 1/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Sergio Gonzalez Monroy]

On 05/01/2016 09:37, 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 sort method to qsort to avoid this behavior, according to
> original patch from Jay Rolette <rolette@infiniteio.com>. The separate
> sort function is no longer necessary.
>
> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
> ---
>
Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>

Re: [dpdk-dev] [PATCH v3 1/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Sergio Gonzalez Monroy]

On 07/01/2016 09:33, Sergio Gonzalez Monroy wrote:
> On 05/01/2016 09:37, 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 sort method to qsort to avoid this behavior, according to
>> original patch from Jay Rolette <rolette@infiniteio.com>. The separate
>> sort function is no longer necessary.
>>
>> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
>> ---
>>
> Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>
Forgot to mention that there is a checkpatch warning:
WARNING:LONG_LINE: line over 90 characters
#113: FILE: lib/librte_eal/linuxapp/eal/eal_memory.c:1167:
+               qsort(&tmp_hp[hp_offset], hpi->num_pages[0], 
sizeof(struct hugepage_file), cmp_physaddr);

Could you fix that Ralf?

Thanks,
Sergio

Re: [dpdk-dev] [PATCH v3 1/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Sergio Gonzalez Monroy]

On 07/01/2016 09:51, Sergio Gonzalez Monroy wrote:
> On 07/01/2016 09:33, Sergio Gonzalez Monroy wrote:
>> On 05/01/2016 09:37, 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 sort method to qsort to avoid this behavior, according to
>>> original patch from Jay Rolette <rolette@infiniteio.com>. The separate
>>> sort function is no longer necessary.
>>>
>>> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
>>> ---
>>>
>> Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>
> Forgot to mention that there is a checkpatch warning:
> WARNING:LONG_LINE: line over 90 characters
> #113: FILE: lib/librte_eal/linuxapp/eal/eal_memory.c:1167:
> +               qsort(&tmp_hp[hp_offset], hpi->num_pages[0], 
> sizeof(struct hugepage_file), cmp_physaddr);
>
> Could you fix that Ralf?
>
> Thanks,
> Sergio

Just FYI, there is a new DPDK Contributors guide:
http://dpdk.org/doc/guides/contributing/patches.html

Regards,
Sergio

Re: [dpdk-dev] [PATCH v3 1/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Ralf Hoffmann]

Hi Sergio,

On 07.01.2016 11:38, Sergio Gonzalez Monroy wrote:
>> Forgot to mention that there is a checkpatch warning:
>> WARNING:LONG_LINE: line over 90 characters
>> #113: FILE: lib/librte_eal/linuxapp/eal/eal_memory.c:1167:
>> +               qsort(&tmp_hp[hp_offset], hpi->num_pages[0],
>> sizeof(struct hugepage_file), cmp_physaddr);
>>
>> Could you fix that Ralf?
>>
>> Thanks,
>> Sergio
> 
> Just FYI, there is a new DPDK Contributors guide:
> http://dpdk.org/doc/guides/contributing/patches.html

I will send an updated patch right away, fixing that warning.

I was aware of that guide, it's really good. Interestingly I have
already used the checkpatches.sh script as described on that page, but
it just said

"1/1 valid patch"

so I assumed it was ok. But indeed, running the checkpath.pl manually
showed that line size warning, thanks for the hint. The checkpatches.sh
only checks the return code, so it does not see the warning.

Best Regards,

Ralf

[dpdk-dev] [PATCH v4 1/1] 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 sort method to qsort to avoid this behavior. The separate sort
function is no longer necessary.

Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
---
v4:
* add linebreak to qsort statement

v3:
* set commit title to eal/linux

v2:

* incorporate patch from http://dpdk.org/dev/patchwork/patch/2061/
  to use qsort instead of bubble sort,
  original patch by Jay Rolette <rolette@infiniteio.com>

 lib/librte_eal/linuxapp/eal/eal_memory.c | 61 ++++++++------------------------
 1 file changed, 15 insertions(+), 46 deletions(-)

diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c b/lib/librte_eal/linuxapp/eal/eal_memory.c
index 846fd31..c0e510b 100644
--- a/lib/librte_eal/linuxapp/eal/eal_memory.c
+++ b/lib/librte_eal/linuxapp/eal/eal_memory.c
@@ -701,54 +701,23 @@ error:
 	return -1;
 }
 
-/*
- * Sort the hugepg_tbl by physical address (lower addresses first on x86,
- * 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
-sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info *hpi)
+cmp_physaddr(const void *a, const void *b)
 {
-	unsigned i, j;
-	int 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;
-
-		/*
-		 * browse all entries starting at 'i', and find the
-		 * entry with the smallest addr
-		 */
-		for (j=i; j< hpi->num_pages[0]; j++) {
-
-			if (compare_addr == 0 ||
-#ifdef RTE_ARCH_PPC_64
-				hugepg_tbl[j].physaddr > compare_addr) {
+#ifndef RTE_ARCH_PPC_64
+	const struct hugepage_file *p1 = (const struct hugepage_file *)a;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)b;
 #else
-				hugepg_tbl[j].physaddr < compare_addr) {
+	/* PowerPC needs memory sorted in reverse order from x86 */
+	const struct hugepage_file *p1 = (const struct hugepage_file *)b;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)a;
 #endif
-				compare_addr = hugepg_tbl[j].physaddr;
-				compare_idx = j;
-			}
-		}
-
-		/* should not happen */
-		if (compare_idx == -1) {
-			RTE_LOG(ERR, EAL, "%s(): error in physaddr sorting\n", __func__);
-			return -1;
-		}
-
-		/* swap the 2 entries in the table */
-		memcpy(&tmp, &hugepg_tbl[compare_idx],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[compare_idx], &hugepg_tbl[i],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[i], &tmp, sizeof(struct hugepage_file));
-	}
-	return 0;
+	if (p1->physaddr < p2->physaddr)
+		return -1;
+	else if (p1->physaddr > p2->physaddr)
+		return 1;
+	else
+		return 0;
 }
 
 /*
@@ -1195,8 +1164,8 @@ rte_eal_hugepage_init(void)
 			goto fail;
 		}
 
-		if (sort_by_physaddr(&tmp_hp[hp_offset], hpi) < 0)
-			goto fail;
+		qsort(&tmp_hp[hp_offset], hpi->num_pages[0],
+		      sizeof(struct hugepage_file), cmp_physaddr);
 
 #ifdef RTE_EAL_SINGLE_FILE_SEGMENTS
 		/* remap all hugepages into single file segments */
-- 
2.5.0

Re: [dpdk-dev] [PATCH v4 1/1] change hugepage sorting to avoid overlapping memcpy

[Sergio Gonzalez Monroy]

Hi Ralf,

It seems like the title update you did for v3 is missing in this patch.

On 07/01/2016 13:59, 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 sort method to qsort to avoid this behavior. The separate sort
> function is no longer necessary.
>
> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
> ---
>
Once you fix that you can add my Acked-by to your commit message.

Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>

By the way, just a reminder to update the status of previous patches in 
patchwork as 'superseded'.

Regards,
Sergio

[dpdk-dev] [PATCH v5 1/1] eal/linux: 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 sort method to qsort to avoid this behavior. The separate sort
function is no longer necessary.

Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>
---
v5:
* set commit title to eal/linux

v4:
* add linebreak to qsort statement

v3:
* set commit title to eal/linux

v2:

* incorporate patch from http://dpdk.org/dev/patchwork/patch/2061/
  to use qsort instead of bubble sort,
  original patch by Jay Rolette <rolette@infiniteio.com>

 lib/librte_eal/linuxapp/eal/eal_memory.c | 61 ++++++++------------------------
 1 file changed, 15 insertions(+), 46 deletions(-)

diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c b/lib/librte_eal/linuxapp/eal/eal_memory.c
index 846fd31..c0e510b 100644
--- a/lib/librte_eal/linuxapp/eal/eal_memory.c
+++ b/lib/librte_eal/linuxapp/eal/eal_memory.c
@@ -701,54 +701,23 @@ error:
 	return -1;
 }
 
-/*
- * Sort the hugepg_tbl by physical address (lower addresses first on x86,
- * 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
-sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info *hpi)
+cmp_physaddr(const void *a, const void *b)
 {
-	unsigned i, j;
-	int 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;
-
-		/*
-		 * browse all entries starting at 'i', and find the
-		 * entry with the smallest addr
-		 */
-		for (j=i; j< hpi->num_pages[0]; j++) {
-
-			if (compare_addr == 0 ||
-#ifdef RTE_ARCH_PPC_64
-				hugepg_tbl[j].physaddr > compare_addr) {
+#ifndef RTE_ARCH_PPC_64
+	const struct hugepage_file *p1 = (const struct hugepage_file *)a;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)b;
 #else
-				hugepg_tbl[j].physaddr < compare_addr) {
+	/* PowerPC needs memory sorted in reverse order from x86 */
+	const struct hugepage_file *p1 = (const struct hugepage_file *)b;
+	const struct hugepage_file *p2 = (const struct hugepage_file *)a;
 #endif
-				compare_addr = hugepg_tbl[j].physaddr;
-				compare_idx = j;
-			}
-		}
-
-		/* should not happen */
-		if (compare_idx == -1) {
-			RTE_LOG(ERR, EAL, "%s(): error in physaddr sorting\n", __func__);
-			return -1;
-		}
-
-		/* swap the 2 entries in the table */
-		memcpy(&tmp, &hugepg_tbl[compare_idx],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[compare_idx], &hugepg_tbl[i],
-			sizeof(struct hugepage_file));
-		memcpy(&hugepg_tbl[i], &tmp, sizeof(struct hugepage_file));
-	}
-	return 0;
+	if (p1->physaddr < p2->physaddr)
+		return -1;
+	else if (p1->physaddr > p2->physaddr)
+		return 1;
+	else
+		return 0;
 }
 
 /*
@@ -1195,8 +1164,8 @@ rte_eal_hugepage_init(void)
 			goto fail;
 		}
 
-		if (sort_by_physaddr(&tmp_hp[hp_offset], hpi) < 0)
-			goto fail;
+		qsort(&tmp_hp[hp_offset], hpi->num_pages[0],
+		      sizeof(struct hugepage_file), cmp_physaddr);
 
 #ifdef RTE_EAL_SINGLE_FILE_SEGMENTS
 		/* remap all hugepages into single file segments */
-- 
2.5.0

Re: [dpdk-dev] [PATCH v5 1/1] eal/linux: change hugepage sorting to avoid overlapping memcpy

[Thomas Monjalon]

2016-01-07 15:54, 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 sort method to qsort to avoid this behavior. The separate sort
> function is no longer necessary.
> 
> Signed-off-by: Ralf Hoffmann <ralf.hoffmann@allegro-packets.com>
> Acked-by: Sergio Gonzalez Monroy <sergio.gonzalez.monroy@intel.com>

Added ref to Jay Rolette and
Applied, thanks

Re: [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