[PATCH 1/1] Improve device tree directory sorting

[PATCH 1/1] Improve device tree directory sorting

[Curt Brune]

Previously when sorting the device tree directory entries, if both
device tree entries contained the '@' character then comparison was
made based on the length of the strings.

This did not work in all cases and could result in odd orderings.

This patch modifies the comparison function for the case when both
strings contain the '@' character.

First a lexical comparison is made between the prefix portions of the
strings *before* the '@' character.

Next, if the prefixes are equal, the lengths of the suffixes *after*
the '@' character are compared.  This preserves the intent of the
original code.

Next, if the suffix lengths are equal, a lexical comparison of the
suffixes is made.

This is still not strictly correct, as ideally the portion after the
'@' should be compared numerically.  However, determining what base to
use for all case is difficult.

Signed-off-by: Curt Brune <curt@cumulusnetworks.com>
---
 kexec/arch/ppc/fs2dt.c | 21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

diff --git a/kexec/arch/ppc/fs2dt.c b/kexec/arch/ppc/fs2dt.c
index 4121c7d..6e77379 100644
--- a/kexec/arch/ppc/fs2dt.c
+++ b/kexec/arch/ppc/fs2dt.c
@@ -30,6 +30,7 @@
 #include <stdio.h>
 #include "../../kexec.h"
 #include "kexec-ppc.h"
+#include "types.h"
 
 #define MAXPATH			1024	/* max path name length */
 #define NAMESPACE		16384	/* max bytes for property names */
@@ -296,6 +297,8 @@ static int comparefunc(const void *dentry1, const void *dentry2)
 {
 	char *str1 = (*(struct dirent **)dentry1)->d_name;
 	char *str2 = (*(struct dirent **)dentry2)->d_name;
+	char *p1, *p2;
+	int res = 0, max_len;
 
 	/*
 	 * strcmp scans from left to right and fails to idetify for some
@@ -303,11 +306,21 @@ static int comparefunc(const void *dentry1, const void *dentry2)
 	 * Therefore, we get the wrong sorted order like memory@10000000 and
 	 * memory@f000000.
 	 */
-	if (strchr(str1, '@') && strchr(str2, '@') &&
-		(strlen(str1) > strlen(str2)))
-		return 1;
+	if ((p1 = strchr(str1, '@')) && (p2 = strchr(str2, '@'))) {
+		max_len = max(p1 - str1, p2 - str2);
+		if ((res = strncmp(str1, str2, max_len)) == 0) {
+			/* prefix is equal - compare part after '@' by length */
+			p1++; p2++;
+			res = strlen(p1) - strlen(p2);
+			if (res == 0)
+				/* equal length, compare by strcmp() */
+				res = strcmp(p1,p2);
+		}
+        } else {
+		res = strcmp(str1, str2);
+        }
 
-	return strcmp(str1, str2);
+	return res;
 }
 
 /*
-- 
1.9.1


_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec

Re: [PATCH 1/1] Improve device tree directory sorting

[Simon Horman]

On Tue, Nov 24, 2015 at 06:17:10PM -0800, Curt Brune wrote:
> Previously when sorting the device tree directory entries, if both
> device tree entries contained the '@' character then comparison was
> made based on the length of the strings.
> 
> This did not work in all cases and could result in odd orderings.
> 
> This patch modifies the comparison function for the case when both
> strings contain the '@' character.
> 
> First a lexical comparison is made between the prefix portions of the
> strings *before* the '@' character.
> 
> Next, if the prefixes are equal, the lengths of the suffixes *after*
> the '@' character are compared.  This preserves the intent of the
> original code.
> 
> Next, if the suffix lengths are equal, a lexical comparison of the
> suffixes is made.
> 
> This is still not strictly correct, as ideally the portion after the
> '@' should be compared numerically.  However, determining what base to
> use for all case is difficult.
> 
> Signed-off-by: Curt Brune <curt@cumulusnetworks.com>

Thanks, applied.

_______________________________________________
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec