Bug fix and test matching method for of_match_node()

Bug fix and test matching method for of_match_node()

[Grant Likely]

This series fixes the matching order in of_match_node() and adds some
test cases to make sure the ordering is working correctly. It mostly
works, but there is one test case that fails. I haven't debugged yet
whether the problem is of_match_node() or the testcase itself.

[PATCH 1/4] Revert "of: search the best compatible match first in __of_match_node()"

[Grant Likely]

From: Kevin Hao <haokexin@gmail.com>

This reverts commit 06b29e76a74b2373e6f8b5a7938b3630b9ae98b2.
As pointed out by Grant Likely, we should also take the type and name
into account when searching the best compatible match. That means the
match with compatible, type and name should be better than the match
just with the same compatible string. So revert this and we will
implement another method to find the best match entry.

Signed-off-by: Kevin Hao <haokexin@gmail.com>
Signed-off-by: Grant Likely <grant.likely@linaro.org>
---
 drivers/of/base.c | 43 +------------------------------------------
 1 file changed, 1 insertion(+), 42 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index 10b51106c854..ba195fbce4c6 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -730,49 +730,13 @@ out:
 }
 EXPORT_SYMBOL(of_find_node_with_property);
 
-static const struct of_device_id *
-of_match_compatible(const struct of_device_id *matches,
-			const struct device_node *node)
-{
-	const char *cp;
-	int cplen, l;
-	const struct of_device_id *m;
-
-	cp = __of_get_property(node, "compatible", &cplen);
-	while (cp && (cplen > 0)) {
-		m = matches;
-		while (m->name[0] || m->type[0] || m->compatible[0]) {
-			/* Only match for the entries without type and name */
-			if (m->name[0] || m->type[0] ||
-				of_compat_cmp(m->compatible, cp,
-					 strlen(m->compatible)))
-				m++;
-			else
-				return m;
-		}
-
-		/* Get node's next compatible string */
-		l = strlen(cp) + 1;
-		cp += l;
-		cplen -= l;
-	}
-
-	return NULL;
-}
-
 static
 const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 					   const struct device_node *node)
 {
-	const struct of_device_id *m;
-
 	if (!matches)
 		return NULL;
 
-	m = of_match_compatible(matches, node);
-	if (m)
-		return m;
-
 	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
 		int match = 1;
 		if (matches->name[0])
@@ -796,12 +760,7 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
  *	@matches:	array of of device match structures to search in
  *	@node:		the of device structure to match against
  *
- *	Low level utility function used by device matching. We have two ways
- *	of matching:
- *	- Try to find the best compatible match by comparing each compatible
- *	  string of device node with all the given matches respectively.
- *	- If the above method failed, then try to match the compatible by using
- *	  __of_device_is_compatible() besides the match in type and name.
+ *	Low level utility function used by device matching.
  */
 const struct of_device_id *of_match_node(const struct of_device_id *matches,
 					 const struct device_node *node)
-- 
1.8.3.2

[PATCH 2/4] of: reimplement the matching method for __of_match_node()

[Grant Likely]

From: Kevin Hao <haokexin@gmail.com>

In the current implementation of __of_match_node(), it will compare
each given match entry against all the node's compatible strings
with of_device_is_compatible().

To achieve multiple compatible strings per node with ordering from
specific to generic, this requires given matches to be ordered from
specific to generic. For most of the drivers this is not true and
also an alphabetical ordering is more sane there.

Therefore, we define a following priority order for the match, and
then scan all the entries to find the best match.
  1. specific compatible && type && name
  2. specific compatible && type
  3. specific compatible && name
  4. specific compatible
  5. general compatible && type && name
  6. general compatible && type
  7. general compatible && name
  8. general compatible
  9. type && name
  10. type
  11. name

This is based on some pseudo-codes provided by Grant Likely.

Signed-off-by: Kevin Hao <haokexin@gmail.com
[grant.likely: Changed multiplier to 4 which makes more sense]
Signed-off-by: Grant Likely <grant.likely@linaro.org>
---
 drivers/of/base.c | 87 +++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 68 insertions(+), 19 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index ba195fbce4c6..6e893f6f19a9 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -342,21 +342,28 @@ struct device_node *of_get_cpu_node(int cpu, unsigned int *thread)
 }
 EXPORT_SYMBOL(of_get_cpu_node);
 
-/** Checks if the given "compat" string matches one of the strings in
- * the device's "compatible" property
+/*
+ * Compare with the __of_device_is_compatible, this will return a score for the
+ * matching strings. The smaller value indicates the match for the more specific
+ * compatible string.
  */
-static int __of_device_is_compatible(const struct device_node *device,
-				     const char *compat)
+static int __of_device_is_compatible_score(const struct device_node *device,
+				     const char *compat, unsigned int *pscore)
 {
 	const char* cp;
 	int cplen, l;
+	unsigned int score = 0;
 
 	cp = __of_get_property(device, "compatible", &cplen);
 	if (cp == NULL)
 		return 0;
 	while (cplen > 0) {
-		if (of_compat_cmp(cp, compat, strlen(compat)) == 0)
+		score++;
+		if (of_compat_cmp(cp, compat, strlen(compat)) == 0) {
+			if (pscore)
+				*pscore = score;
 			return 1;
+		}
 		l = strlen(cp) + 1;
 		cp += l;
 		cplen -= l;
@@ -368,6 +375,15 @@ static int __of_device_is_compatible(const struct device_node *device,
 /** Checks if the given "compat" string matches one of the strings in
  * the device's "compatible" property
  */
+static int __of_device_is_compatible(const struct device_node *device,
+				     const char *compat)
+{
+	return __of_device_is_compatible_score(device, compat, NULL);
+}
+
+/** Checks if the given "compat" string matches one of the strings in
+ * the device's "compatible" property
+ */
 int of_device_is_compatible(const struct device_node *device,
 		const char *compat)
 {
@@ -734,25 +750,46 @@ static
 const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 					   const struct device_node *node)
 {
+	const struct of_device_id *best_match = NULL;
+	unsigned int best_score = ~0;
+
 	if (!matches)
 		return NULL;
 
 	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
-		int match = 1;
-		if (matches->name[0])
-			match &= node->name
-				&& !strcmp(matches->name, node->name);
-		if (matches->type[0])
-			match &= node->type
-				&& !strcmp(matches->type, node->type);
-		if (matches->compatible[0])
-			match &= __of_device_is_compatible(node,
-							   matches->compatible);
-		if (match)
-			return matches;
+		unsigned int score = ~0;
+
+		/*
+		 * Matching compatible is better than matching type and name,
+		 * and the specific compatible is better than the general.
+		 */
+		if (matches->compatible[0] &&
+			 __of_device_is_compatible_score(node,
+						matches->compatible, &score))
+			score *= 4;
+
+		/*
+		 * Matching type is better than matching name, but matching
+		 * both is even better than that.
+		 */
+		if (matches->type[0] && node->type &&
+			!strcmp(matches->type, node->type))
+			score -= 2;
+
+		/* Matching name is a bit better than not */
+		if (matches->name[0] && node->name &&
+			!strcmp(matches->name, node->name))
+			score--;
+
+		if (score < best_score) {
+			best_match = matches;
+			best_score = score;
+		}
+
 		matches++;
 	}
-	return NULL;
+
+	return best_match;
 }
 
 /**
@@ -760,7 +797,19 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
  *	@matches:	array of of device match structures to search in
  *	@node:		the of device structure to match against
  *
- *	Low level utility function used by device matching.
+ *	Low level utility function used by device matching. The priority order
+ *	for the matching is:
+ *	  1. specific compatible && type && name
+ *	  2. specific compatible && type
+ *	  3. specific compatible && name
+ *	  4. specific compatible
+ *	  5. general compatible && type && name
+ *	  6. general compatible && type
+ *	  7. general compatible && name
+ *	  8. general compatible
+ *	  9. type && name
+ *	  10. type
+ *	  11. name
  */
 const struct of_device_id *of_match_node(const struct of_device_id *matches,
 					 const struct device_node *node)
-- 
1.8.3.2

[PATCH v2 2/4] of: reimplement the matching method for __of_match_node()

[Kevin Hao]

In the current implementation of __of_match_node(), it will compare
each given match entry against all the node's compatible strings
with of_device_is_compatible().

To achieve multiple compatible strings per node with ordering from
specific to generic, this requires given matches to be ordered from
specific to generic. For most of the drivers this is not true and
also an alphabetical ordering is more sane there.

Therefore, we define a following priority order for the match, and
then scan all the entries to find the best match.
  1. specific compatible && type && name
  2. specific compatible && type
  3. specific compatible && name
  4. specific compatible
  5. general compatible && type && name
  6. general compatible && type
  7. general compatible && name
  8. general compatible
  9. type && name
  10. type
  11. name

This is based on some pseudo-codes provided by Grant Likely.

Signed-off-by: Kevin Hao <haokexin@gmail.com>
[grant.likely: Changed multiplier to 4 which makes more sense]
Signed-off-by: Grant Likely <grant.likely@linaro.org>
---
v2: Fix the bug such as we get the same score for the following two match
entries:
	name2 { }

	struct of_device_id matches[] = {
		{.name = "name2", },
		{.name = "name2", .type = "type1", },
		{}
	};
 
 drivers/of/base.c | 93 +++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 74 insertions(+), 19 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index ba195fbce4c6..4085e2af0b7f 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -342,21 +342,28 @@ struct device_node *of_get_cpu_node(int cpu, unsigned int *thread)
 }
 EXPORT_SYMBOL(of_get_cpu_node);
 
-/** Checks if the given "compat" string matches one of the strings in
- * the device's "compatible" property
+/*
+ * Compare with the __of_device_is_compatible, this will return a score for the
+ * matching strings. The smaller value indicates the match for the more specific
+ * compatible string.
  */
-static int __of_device_is_compatible(const struct device_node *device,
-				     const char *compat)
+static int __of_device_is_compatible_score(const struct device_node *device,
+				     const char *compat, int *pscore)
 {
 	const char* cp;
 	int cplen, l;
+	int score = 0;
 
 	cp = __of_get_property(device, "compatible", &cplen);
 	if (cp == NULL)
 		return 0;
 	while (cplen > 0) {
-		if (of_compat_cmp(cp, compat, strlen(compat)) == 0)
+		score++;
+		if (of_compat_cmp(cp, compat, strlen(compat)) == 0) {
+			if (pscore)
+				*pscore = score;
 			return 1;
+		}
 		l = strlen(cp) + 1;
 		cp += l;
 		cplen -= l;
@@ -368,6 +375,15 @@ static int __of_device_is_compatible(const struct device_node *device,
 /** Checks if the given "compat" string matches one of the strings in
  * the device's "compatible" property
  */
+static int __of_device_is_compatible(const struct device_node *device,
+				     const char *compat)
+{
+	return __of_device_is_compatible_score(device, compat, NULL);
+}
+
+/** Checks if the given "compat" string matches one of the strings in
+ * the device's "compatible" property
+ */
 int of_device_is_compatible(const struct device_node *device,
 		const char *compat)
 {
@@ -734,25 +750,52 @@ static
 const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 					   const struct device_node *node)
 {
+	const struct of_device_id *best_match = NULL;
+	int best_score = 0;
+
 	if (!matches)
 		return NULL;
 
 	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
-		int match = 1;
-		if (matches->name[0])
-			match &= node->name
-				&& !strcmp(matches->name, node->name);
-		if (matches->type[0])
-			match &= node->type
-				&& !strcmp(matches->type, node->type);
-		if (matches->compatible[0])
-			match &= __of_device_is_compatible(node,
-							   matches->compatible);
-		if (match)
-			return matches;
+		int score = 0;
+
+		/*
+		 * Matching compatible is better than matching type and name,
+		 * and the specific compatible is better than the general.
+		 */
+		if (matches->compatible[0] &&
+			 __of_device_is_compatible_score(node,
+						matches->compatible, &score))
+			score = INT_MAX - 4 * score;
+
+		/*
+		 * Matching type is better than matching name, but matching
+		 * both is even better than that.
+		 */
+		if (matches->type[0]) {
+			if (node->type && !strcmp(matches->type, node->type))
+				score += 2;
+			else
+				score = INT_MIN;
+		}
+
+		/* Matching name is a bit better than not */
+		if (matches->name[0]) {
+			if (node->name && !strcmp(matches->name, node->name))
+				score++;
+			else
+				score = INT_MIN;
+		}
+
+		if (score > best_score) {
+			best_match = matches;
+			best_score = score;
+		}
+
 		matches++;
 	}
-	return NULL;
+
+	return best_match;
 }
 
 /**
@@ -760,7 +803,19 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
  *	@matches:	array of of device match structures to search in
  *	@node:		the of device structure to match against
  *
- *	Low level utility function used by device matching.
+ *	Low level utility function used by device matching. The priority order
+ *	for the matching is:
+ *	  1. specific compatible && type && name
+ *	  2. specific compatible && type
+ *	  3. specific compatible && name
+ *	  4. specific compatible
+ *	  5. general compatible && type && name
+ *	  6. general compatible && type
+ *	  7. general compatible && name
+ *	  8. general compatible
+ *	  9. type && name
+ *	  10. type
+ *	  11. name
  */
 const struct of_device_id *of_match_node(const struct of_device_id *matches,
 					 const struct device_node *node)
-- 
1.8.5.3

Re: [PATCH v2 2/4] of: reimplement the matching method for __of_match_node()

[Kevin Hao]

[-- Attachment #1: Type: text/plain, Size: 479 bytes --]

On Wed, Feb 19, 2014 at 02:21:02PM +0800, Kevin Hao wrote:
> +		/*
> +		 * Matching compatible is better than matching type and name,
> +		 * and the specific compatible is better than the general.
> +		 */
> +		if (matches->compatible[0] &&
> +			 __of_device_is_compatible_score(node,
> +						matches->compatible, &score))
> +			score = INT_MAX - 4 * score;

It seems that we also need to adjust the above as what we do for the type
and name. The v3 is coming.

Thanks,
Kevin

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

[PATCH v3 2/4] of: reimplement the matching method for __of_match_node()

[Kevin Hao]

In the current implementation of __of_match_node(), it will compare
each given match entry against all the node's compatible strings
with of_device_is_compatible().

To achieve multiple compatible strings per node with ordering from
specific to generic, this requires given matches to be ordered from
specific to generic. For most of the drivers this is not true and
also an alphabetical ordering is more sane there.

Therefore, we define a following priority order for the match, and
then scan all the entries to find the best match.
  1. specific compatible && type && name
  2. specific compatible && type
  3. specific compatible && name
  4. specific compatible
  5. general compatible && type && name
  6. general compatible && type
  7. general compatible && name
  8. general compatible
  9. type && name
  10. type
  11. name

This is based on some pseudo-codes provided by Grant Likely.

Signed-off-by: Kevin Hao <haokexin@gmail.com>
[grant.likely: Changed multiplier to 4 which makes more sense]
Signed-off-by: Grant Likely <grant.likely@linaro.org>
---
v3: Also need to bail out when there does have a compatible member in match
    entry, but it doesn't match with the device node's compatible.
 
v2: Fix the bug such as we get the same score for the following two match
entries:
	name2 { }

	struct of_device_id matches[] = {
		{.name = "name2", },
		{.name = "name2", .type = "type1", },
		{}
	};

 drivers/of/base.c | 96 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 77 insertions(+), 19 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index ba195fbce4c6..8f79f006d86f 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -342,21 +342,28 @@ struct device_node *of_get_cpu_node(int cpu, unsigned int *thread)
 }
 EXPORT_SYMBOL(of_get_cpu_node);
 
-/** Checks if the given "compat" string matches one of the strings in
- * the device's "compatible" property
+/*
+ * Compare with the __of_device_is_compatible, this will return a score for the
+ * matching strings. The smaller value indicates the match for the more specific
+ * compatible string.
  */
-static int __of_device_is_compatible(const struct device_node *device,
-				     const char *compat)
+static int __of_device_is_compatible_score(const struct device_node *device,
+				     const char *compat, int *pscore)
 {
 	const char* cp;
 	int cplen, l;
+	int score = 0;
 
 	cp = __of_get_property(device, "compatible", &cplen);
 	if (cp == NULL)
 		return 0;
 	while (cplen > 0) {
-		if (of_compat_cmp(cp, compat, strlen(compat)) == 0)
+		score++;
+		if (of_compat_cmp(cp, compat, strlen(compat)) == 0) {
+			if (pscore)
+				*pscore = score;
 			return 1;
+		}
 		l = strlen(cp) + 1;
 		cp += l;
 		cplen -= l;
@@ -368,6 +375,15 @@ static int __of_device_is_compatible(const struct device_node *device,
 /** Checks if the given "compat" string matches one of the strings in
  * the device's "compatible" property
  */
+static int __of_device_is_compatible(const struct device_node *device,
+				     const char *compat)
+{
+	return __of_device_is_compatible_score(device, compat, NULL);
+}
+
+/** Checks if the given "compat" string matches one of the strings in
+ * the device's "compatible" property
+ */
 int of_device_is_compatible(const struct device_node *device,
 		const char *compat)
 {
@@ -734,25 +750,55 @@ static
 const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 					   const struct device_node *node)
 {
+	const struct of_device_id *best_match = NULL;
+	int best_score = 0;
+
 	if (!matches)
 		return NULL;
 
 	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
-		int match = 1;
-		if (matches->name[0])
-			match &= node->name
-				&& !strcmp(matches->name, node->name);
-		if (matches->type[0])
-			match &= node->type
-				&& !strcmp(matches->type, node->type);
-		if (matches->compatible[0])
-			match &= __of_device_is_compatible(node,
-							   matches->compatible);
-		if (match)
-			return matches;
+		int score = 0;
+
+		/*
+		 * Matching compatible is better than matching type and name,
+		 * and the specific compatible is better than the general.
+		 */
+		if (matches->compatible[0]) {
+			if (__of_device_is_compatible_score(node,
+						matches->compatible, &score))
+				score = INT_MAX - 4 * score;
+			else
+				score = INT_MIN;
+		}
+
+		/*
+		 * Matching type is better than matching name, but matching
+		 * both is even better than that.
+		 */
+		if (matches->type[0]) {
+			if (node->type && !strcmp(matches->type, node->type))
+				score += 2;
+			else
+				score = INT_MIN;
+		}
+
+		/* Matching name is a bit better than not */
+		if (matches->name[0]) {
+			if (node->name && !strcmp(matches->name, node->name))
+				score++;
+			else
+				score = INT_MIN;
+		}
+
+		if (score > best_score) {
+			best_match = matches;
+			best_score = score;
+		}
+
 		matches++;
 	}
-	return NULL;
+
+	return best_match;
 }
 
 /**
@@ -760,7 +806,19 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
  *	@matches:	array of of device match structures to search in
  *	@node:		the of device structure to match against
  *
- *	Low level utility function used by device matching.
+ *	Low level utility function used by device matching. The priority order
+ *	for the matching is:
+ *	  1. specific compatible && type && name
+ *	  2. specific compatible && type
+ *	  3. specific compatible && name
+ *	  4. specific compatible
+ *	  5. general compatible && type && name
+ *	  6. general compatible && type
+ *	  7. general compatible && name
+ *	  8. general compatible
+ *	  9. type && name
+ *	  10. type
+ *	  11. name
  */
 const struct of_device_id *of_match_node(const struct of_device_id *matches,
 					 const struct device_node *node)
-- 
1.8.5.3

Re: [PATCH v3 2/4] of: reimplement the matching method for __of_match_node()

[Grant Likely]

On Wed, 19 Feb 2014 16:15:45 +0800, Kevin Hao <haokexin@gmail.com> wrote:
> In the current implementation of __of_match_node(), it will compare
> each given match entry against all the node's compatible strings
> with of_device_is_compatible().
> 
> To achieve multiple compatible strings per node with ordering from
> specific to generic, this requires given matches to be ordered from
> specific to generic. For most of the drivers this is not true and
> also an alphabetical ordering is more sane there.
> 
> Therefore, we define a following priority order for the match, and
> then scan all the entries to find the best match.
>   1. specific compatible && type && name
>   2. specific compatible && type
>   3. specific compatible && name
>   4. specific compatible
>   5. general compatible && type && name
>   6. general compatible && type
>   7. general compatible && name
>   8. general compatible
>   9. type && name
>   10. type
>   11. name
> 
> This is based on some pseudo-codes provided by Grant Likely.
> 
> Signed-off-by: Kevin Hao <haokexin@gmail.com>
> [grant.likely: Changed multiplier to 4 which makes more sense]
> Signed-off-by: Grant Likely <grant.likely@linaro.org>
> ---
> v3: Also need to bail out when there does have a compatible member in match
>     entry, but it doesn't match with the device node's compatible.
>  
> v2: Fix the bug such as we get the same score for the following two match
> entries:
> 	name2 { }
> 
> 	struct of_device_id matches[] = {
> 		{.name = "name2", },
> 		{.name = "name2", .type = "type1", },
> 		{}
> 	};
> 
>  drivers/of/base.c | 96 ++++++++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 77 insertions(+), 19 deletions(-)
> 
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index ba195fbce4c6..8f79f006d86f 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -342,21 +342,28 @@ struct device_node *of_get_cpu_node(int cpu, unsigned int *thread)
>  }
>  EXPORT_SYMBOL(of_get_cpu_node);
>  
> -/** Checks if the given "compat" string matches one of the strings in
> - * the device's "compatible" property
> +/*
> + * Compare with the __of_device_is_compatible, this will return a score for the
> + * matching strings. The smaller value indicates the match for the more specific
> + * compatible string.
>   */
> -static int __of_device_is_compatible(const struct device_node *device,
> -				     const char *compat)
> +static int __of_device_is_compatible_score(const struct device_node *device,
> +				     const char *compat, int *pscore)
>  {
>  	const char* cp;
>  	int cplen, l;
> +	int score = 0;
>  
>  	cp = __of_get_property(device, "compatible", &cplen);
>  	if (cp == NULL)
>  		return 0;
>  	while (cplen > 0) {
> -		if (of_compat_cmp(cp, compat, strlen(compat)) == 0)
> +		score++;
> +		if (of_compat_cmp(cp, compat, strlen(compat)) == 0) {
> +			if (pscore)
> +				*pscore = score;
>  			return 1;
> +		}
>  		l = strlen(cp) + 1;
>  		cp += l;
>  		cplen -= l;
> @@ -368,6 +375,15 @@ static int __of_device_is_compatible(const struct device_node *device,
>  /** Checks if the given "compat" string matches one of the strings in
>   * the device's "compatible" property
>   */
> +static int __of_device_is_compatible(const struct device_node *device,
> +				     const char *compat)
> +{
> +	return __of_device_is_compatible_score(device, compat, NULL);
> +}
> +
> +/** Checks if the given "compat" string matches one of the strings in
> + * the device's "compatible" property
> + */
>  int of_device_is_compatible(const struct device_node *device,
>  		const char *compat)
>  {
> @@ -734,25 +750,55 @@ static
>  const struct of_device_id *__of_match_node(const struct of_device_id *matches,
>  					   const struct device_node *node)
>  {
> +	const struct of_device_id *best_match = NULL;
> +	int best_score = 0;
> +
>  	if (!matches)
>  		return NULL;
>  
>  	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
> -		int match = 1;
> -		if (matches->name[0])
> -			match &= node->name
> -				&& !strcmp(matches->name, node->name);
> -		if (matches->type[0])
> -			match &= node->type
> -				&& !strcmp(matches->type, node->type);
> -		if (matches->compatible[0])
> -			match &= __of_device_is_compatible(node,
> -							   matches->compatible);
> -		if (match)
> -			return matches;
> +		int score = 0;
> +
> +		/*
> +		 * Matching compatible is better than matching type and name,
> +		 * and the specific compatible is better than the general.
> +		 */
> +		if (matches->compatible[0]) {
> +			if (__of_device_is_compatible_score(node,
> +						matches->compatible, &score))
> +				score = INT_MAX - 4 * score;
> +			else
> +				score = INT_MIN;
> +		}
> +
> +		/*
> +		 * Matching type is better than matching name, but matching
> +		 * both is even better than that.
> +		 */
> +		if (matches->type[0]) {
> +			if (node->type && !strcmp(matches->type, node->type))
> +				score += 2;
> +			else
> +				score = INT_MIN;
> +		}
> +
> +		/* Matching name is a bit better than not */
> +		if (matches->name[0]) {
> +			if (node->name && !strcmp(matches->name, node->name))
> +				score++;
> +			else
> +				score = INT_MIN;
> +		}

All that mucking about with setting the score to INT_MIN is pretty ugly.
I've reworked the patch to 'continue;' whenever one of the above matches
fail. That completely eliminates any possibility of accepting an entry
that has a failed match. Here's my diff. I'll merge this change into the
patch before committing. All of the test cases still pass with my
rework.

---

diff --git a/drivers/of/base.c b/drivers/of/base.c
index 8f79f006d86f..fcb65d27d071 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -756,7 +756,7 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 	if (!matches)
 		return NULL;
 
-	while (matches->name[0] || matches->type[0] || matches->compatible[0]) {
+	for (; matches->name[0] || matches->type[0] || matches->compatible[0]; matches++) {
 		int score = 0;
 
 		/*
@@ -764,11 +764,10 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 		 * and the specific compatible is better than the general.
 		 */
 		if (matches->compatible[0]) {
-			if (__of_device_is_compatible_score(node,
+			if (!__of_device_is_compatible_score(node,
 						matches->compatible, &score))
-				score = INT_MAX - 4 * score;
-			else
-				score = INT_MIN;
+				continue;
+			score = INT_MAX - 4 * score;
 		}
 
 		/*
@@ -776,26 +775,22 @@ const struct of_device_id *__of_match_node(const struct of_device_id *matches,
 		 * both is even better than that.
 		 */
 		if (matches->type[0]) {
-			if (node->type && !strcmp(matches->type, node->type))
-				score += 2;
-			else
-				score = INT_MIN;
+			if (!node->type || strcmp(matches->type, node->type))
+				continue;
+			score += 2;
 		}
 
 		/* Matching name is a bit better than not */
 		if (matches->name[0]) {
-			if (node->name && !strcmp(matches->name, node->name))
-				score++;
-			else
-				score = INT_MIN;
+			if (!node->name || strcmp(matches->name, node->name))
+				continue;
+			score++;
 		}
 
 		if (score > best_score) {
 			best_match = matches;
 			best_score = score;
 		}
-
-		matches++;
 	}
 
 	return best_match;

Re: [PATCH v3 2/4] of: reimplement the matching method for __of_match_node()

[Grant Likely]

On Wed, 19 Feb 2014 16:15:45 +0800, Kevin Hao <haokexin@gmail.com> wrote:
> In the current implementation of __of_match_node(), it will compare
> each given match entry against all the node's compatible strings
> with of_device_is_compatible().
> 
> To achieve multiple compatible strings per node with ordering from
> specific to generic, this requires given matches to be ordered from
> specific to generic. For most of the drivers this is not true and
> also an alphabetical ordering is more sane there.
> 
> Therefore, we define a following priority order for the match, and
> then scan all the entries to find the best match.
>   1. specific compatible && type && name
>   2. specific compatible && type
>   3. specific compatible && name
>   4. specific compatible
>   5. general compatible && type && name
>   6. general compatible && type
>   7. general compatible && name
>   8. general compatible
>   9. type && name
>   10. type
>   11. name
> 
> This is based on some pseudo-codes provided by Grant Likely.
> 
> Signed-off-by: Kevin Hao <haokexin@gmail.com>
> [grant.likely: Changed multiplier to 4 which makes more sense]
> Signed-off-by: Grant Likely <grant.likely@linaro.org>
> ---
> v3: Also need to bail out when there does have a compatible member in match
>     entry, but it doesn't match with the device node's compatible.
>  
> v2: Fix the bug such as we get the same score for the following two match
> entries:
> 	name2 { }
> 
> 	struct of_device_id matches[] = {
> 		{.name = "name2", },
> 		{.name = "name2", .type = "type1", },
> 		{}
> 	};

BTW, I prefer patch version information like the above to appear before
the '---' line so that it shows up in the final commit log. It is often
useful to have the revision history in mainline.

> 
>  drivers/of/base.c | 96 ++++++++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 77 insertions(+), 19 deletions(-)
> 
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index ba195fbce4c6..8f79f006d86f 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -342,21 +342,28 @@ struct device_node *of_get_cpu_node(int cpu, unsigned int *thread)
>  }
>  EXPORT_SYMBOL(of_get_cpu_node);
>  
> -/** Checks if the given "compat" string matches one of the strings in
> - * the device's "compatible" property
> +/*
> + * Compare with the __of_device_is_compatible, this will return a score for the
> + * matching strings. The smaller value indicates the match for the more specific
> + * compatible string.
>   */
> -static int __of_device_is_compatible(const struct device_node *device,
> -				     const char *compat)
> +static int __of_device_is_compatible_score(const struct device_node *device,
> +				     const char *compat, int *pscore)
>  {

Another note: I've removed this new function. There are only three users
of __of_device_is_compatible, and they are all in this file. Adding a
field is just fine. I'm also considering rolling the name and
device_type checks into this function, but that goes beyond the bug fix
so it will wait until the next merge window.

g.

[PATCH 3/4] of: Move testcase FDT data into drivers/of

[Grant Likely]

The testcase data is usable by any platform. This patch moves it into
the drivers/of directory so it can be included by any architecture.

Using the test cases requires manually adding #include <testcases.dtsi>
to the end of the boards .dtsi file and enabling CONFIG_OF_SELFTEST. Not
pretty though. A useful project would be to make the testcase code
easier to execute.

Signed-off-by: Grant Likely <grant.likely@linaro.org>
---
 arch/arm/boot/dts/testcases/tests-interrupts.dtsi | 58 -----------------------
 arch/arm/boot/dts/testcases/tests-phandle.dtsi    | 39 ---------------
 arch/arm/boot/dts/testcases/tests.dtsi            |  2 -
 arch/arm/boot/dts/versatile-pb.dts                |  4 +-
 drivers/of/testcase-data/testcases.dtsi           |  2 +
 drivers/of/testcase-data/tests-interrupts.dtsi    | 58 +++++++++++++++++++++++
 drivers/of/testcase-data/tests-phandle.dtsi       | 39 +++++++++++++++
 scripts/Makefile.lib                              |  1 +
 8 files changed, 102 insertions(+), 101 deletions(-)
 delete mode 100644 arch/arm/boot/dts/testcases/tests-interrupts.dtsi
 delete mode 100644 arch/arm/boot/dts/testcases/tests-phandle.dtsi
 delete mode 100644 arch/arm/boot/dts/testcases/tests.dtsi
 create mode 100644 drivers/of/testcase-data/testcases.dtsi
 create mode 100644 drivers/of/testcase-data/tests-interrupts.dtsi
 create mode 100644 drivers/of/testcase-data/tests-phandle.dtsi

diff --git a/arch/arm/boot/dts/testcases/tests-interrupts.dtsi b/arch/arm/boot/dts/testcases/tests-interrupts.dtsi
deleted file mode 100644
index c843720bd3e5..000000000000
--- a/arch/arm/boot/dts/testcases/tests-interrupts.dtsi
+++ /dev/null
@@ -1,58 +0,0 @@
-
-/ {
-	testcase-data {
-		interrupts {
-			#address-cells = <1>;
-			#size-cells = <1>;
-			test_intc0: intc0 {
-				interrupt-controller;
-				#interrupt-cells = <1>;
-			};
-
-			test_intc1: intc1 {
-				interrupt-controller;
-				#interrupt-cells = <3>;
-			};
-
-			test_intc2: intc2 {
-				interrupt-controller;
-				#interrupt-cells = <2>;
-			};
-
-			test_intmap0: intmap0 {
-				#interrupt-cells = <1>;
-				#address-cells = <0>;
-				interrupt-map = <1 &test_intc0 9>,
-						<2 &test_intc1 10 11 12>,
-						<3 &test_intc2 13 14>,
-						<4 &test_intc2 15 16>;
-			};
-
-			test_intmap1: intmap1 {
-				#interrupt-cells = <2>;
-				interrupt-map = <0x5000 1 2 &test_intc0 15>;
-			};
-
-			interrupts0 {
-				interrupt-parent = <&test_intc0>;
-				interrupts = <1>, <2>, <3>, <4>;
-			};
-
-			interrupts1 {
-				interrupt-parent = <&test_intmap0>;
-				interrupts = <1>, <2>, <3>, <4>;
-			};
-
-			interrupts-extended0 {
-				reg = <0x5000 0x100>;
-				interrupts-extended = <&test_intc0 1>,
-						      <&test_intc1 2 3 4>,
-						      <&test_intc2 5 6>,
-						      <&test_intmap0 1>,
-						      <&test_intmap0 2>,
-						      <&test_intmap0 3>,
-						      <&test_intmap1 1 2>;
-			};
-		};
-	};
-};
diff --git a/arch/arm/boot/dts/testcases/tests-phandle.dtsi b/arch/arm/boot/dts/testcases/tests-phandle.dtsi
deleted file mode 100644
index 0007d3cd7dc2..000000000000
--- a/arch/arm/boot/dts/testcases/tests-phandle.dtsi
+++ /dev/null
@@ -1,39 +0,0 @@
-
-/ {
-	testcase-data {
-		phandle-tests {
-			provider0: provider0 {
-				#phandle-cells = <0>;
-			};
-
-			provider1: provider1 {
-				#phandle-cells = <1>;
-			};
-
-			provider2: provider2 {
-				#phandle-cells = <2>;
-			};
-
-			provider3: provider3 {
-				#phandle-cells = <3>;
-			};
-
-			consumer-a {
-				phandle-list =	<&provider1 1>,
-						<&provider2 2 0>,
-						<0>,
-						<&provider3 4 4 3>,
-						<&provider2 5 100>,
-						<&provider0>,
-						<&provider1 7>;
-				phandle-list-names = "first", "second", "third";
-
-				phandle-list-bad-phandle = <12345678 0 0>;
-				phandle-list-bad-args = <&provider2 1 0>,
-							<&provider3 0>;
-				empty-property;
-				unterminated-string = [40 41 42 43];
-			};
-		};
-	};
-};
diff --git a/arch/arm/boot/dts/testcases/tests.dtsi b/arch/arm/boot/dts/testcases/tests.dtsi
deleted file mode 100644
index 3f123ecc9dd7..000000000000
--- a/arch/arm/boot/dts/testcases/tests.dtsi
+++ /dev/null
@@ -1,2 +0,0 @@
-/include/ "tests-phandle.dtsi"
-/include/ "tests-interrupts.dtsi"
diff --git a/arch/arm/boot/dts/versatile-pb.dts b/arch/arm/boot/dts/versatile-pb.dts
index f43907c40c93..65f657711323 100644
--- a/arch/arm/boot/dts/versatile-pb.dts
+++ b/arch/arm/boot/dts/versatile-pb.dts
@@ -1,4 +1,4 @@
-/include/ "versatile-ab.dts"
+#include <versatile-ab.dts>
 
 / {
 	model = "ARM Versatile PB";
@@ -47,4 +47,4 @@
 	};
 };
 
-/include/ "testcases/tests.dtsi"
+#include <testcases.dtsi>
diff --git a/drivers/of/testcase-data/testcases.dtsi b/drivers/of/testcase-data/testcases.dtsi
new file mode 100644
index 000000000000..3cc2f55534ac
--- /dev/null
+++ b/drivers/of/testcase-data/testcases.dtsi
@@ -0,0 +1,2 @@
+#include "tests-phandle.dtsi"
+#include "tests-interrupts.dtsi"
diff --git a/drivers/of/testcase-data/tests-interrupts.dtsi b/drivers/of/testcase-data/tests-interrupts.dtsi
new file mode 100644
index 000000000000..c843720bd3e5
--- /dev/null
+++ b/drivers/of/testcase-data/tests-interrupts.dtsi
@@ -0,0 +1,58 @@
+
+/ {
+	testcase-data {
+		interrupts {
+			#address-cells = <1>;
+			#size-cells = <1>;
+			test_intc0: intc0 {
+				interrupt-controller;
+				#interrupt-cells = <1>;
+			};
+
+			test_intc1: intc1 {
+				interrupt-controller;
+				#interrupt-cells = <3>;
+			};
+
+			test_intc2: intc2 {
+				interrupt-controller;
+				#interrupt-cells = <2>;
+			};
+
+			test_intmap0: intmap0 {
+				#interrupt-cells = <1>;
+				#address-cells = <0>;
+				interrupt-map = <1 &test_intc0 9>,
+						<2 &test_intc1 10 11 12>,
+						<3 &test_intc2 13 14>,
+						<4 &test_intc2 15 16>;
+			};
+
+			test_intmap1: intmap1 {
+				#interrupt-cells = <2>;
+				interrupt-map = <0x5000 1 2 &test_intc0 15>;
+			};
+
+			interrupts0 {
+				interrupt-parent = <&test_intc0>;
+				interrupts = <1>, <2>, <3>, <4>;
+			};
+
+			interrupts1 {
+				interrupt-parent = <&test_intmap0>;
+				interrupts = <1>, <2>, <3>, <4>;
+			};
+
+			interrupts-extended0 {
+				reg = <0x5000 0x100>;
+				interrupts-extended = <&test_intc0 1>,
+						      <&test_intc1 2 3 4>,
+						      <&test_intc2 5 6>,
+						      <&test_intmap0 1>,
+						      <&test_intmap0 2>,
+						      <&test_intmap0 3>,
+						      <&test_intmap1 1 2>;
+			};
+		};
+	};
+};
diff --git a/drivers/of/testcase-data/tests-phandle.dtsi b/drivers/of/testcase-data/tests-phandle.dtsi
new file mode 100644
index 000000000000..0007d3cd7dc2
--- /dev/null
+++ b/drivers/of/testcase-data/tests-phandle.dtsi
@@ -0,0 +1,39 @@
+
+/ {
+	testcase-data {
+		phandle-tests {
+			provider0: provider0 {
+				#phandle-cells = <0>;
+			};
+
+			provider1: provider1 {
+				#phandle-cells = <1>;
+			};
+
+			provider2: provider2 {
+				#phandle-cells = <2>;
+			};
+
+			provider3: provider3 {
+				#phandle-cells = <3>;
+			};
+
+			consumer-a {
+				phandle-list =	<&provider1 1>,
+						<&provider2 2 0>,
+						<0>,
+						<&provider3 4 4 3>,
+						<&provider2 5 100>,
+						<&provider0>,
+						<&provider1 7>;
+				phandle-list-names = "first", "second", "third";
+
+				phandle-list-bad-phandle = <12345678 0 0>;
+				phandle-list-bad-args = <&provider2 1 0>,
+							<&provider3 0>;
+				empty-property;
+				unterminated-string = [40 41 42 43];
+			};
+		};
+	};
+};
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 49392ecbef17..79c059e70860 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -152,6 +152,7 @@ ld_flags       = $(LDFLAGS) $(ldflags-y)
 dtc_cpp_flags  = -Wp,-MD,$(depfile).pre.tmp -nostdinc                    \
 		 -I$(srctree)/arch/$(SRCARCH)/boot/dts                   \
 		 -I$(srctree)/arch/$(SRCARCH)/boot/dts/include           \
+		 -I$(srctree)/drivers/of/testcase-data                   \
 		 -undef -D__DTS__
 
 # Finds the multi-part object the current object will be linked into
-- 
1.8.3.2

[PATCH 4/4] of: Add self test for of_match_node()

[Grant Likely]

Adds a selftest function for the of_match_node function. of_match_node
is supposed to handle precedence for the compatible property as well as
the name and device_type values. This patch adds some test case data and
a function that makes sure each test node matches against the correct
entry of an of_device_id table.

This code was written to verify the new of_match_node() implementation
that is an earlier part of this series.

Currently all but one test passes. There is one scenario where the empty
"b/name2" node is getting matched against an entry without any
device_type property at all. It is unknown why this is, but it needs to
be solved before this patch can be committed. (However, this is testing
the new of_match_table implementation, which still does far better than
the old implementation which gets the precedence completely wrong.)

Signed-off-by: Grant Likely <grant.likely@linaro.org>
Cc: Kevin Hau <haokexin@gmail.com>
---
 drivers/of/selftest.c                     | 67 +++++++++++++++++++++++++++++++
 drivers/of/testcase-data/testcases.dtsi   |  1 +
 drivers/of/testcase-data/tests-match.dtsi | 19 +++++++++
 3 files changed, 87 insertions(+)
 create mode 100644 drivers/of/testcase-data/tests-match.dtsi

diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
index e21012bde639..6643d1920985 100644
--- a/drivers/of/selftest.c
+++ b/drivers/of/selftest.c
@@ -300,6 +300,72 @@ static void __init of_selftest_parse_interrupts_extended(void)
 	of_node_put(np);
 }
 
+static struct of_device_id match_node_table[] = {
+	{ .data = "A", .name = "name0", }, /* Name alone is lowest priority */
+	{ .data = "B", .type = "type1", }, /* followed by type alone */
+
+	{ .data = "Ca", .name = "name2", .type = "type1", }, /* followed by both together */
+	{ .data = "Cb", .name = "name2", }, /* Only match when type doesn't match */
+	{ .data = "Cc", .name = "name2", .type = "type2", },
+
+	{ .data = "E", .compatible = "compat3" },
+	{ .data = "G", .compatible = "compat2", },
+	{ .data = "H", .compatible = "compat2", .name = "name5", },
+	{ .data = "I", .compatible = "compat2", .type = "type1", },
+	{ .data = "J", .compatible = "compat2", .type = "type1", .name = "name8", },
+	{ .data = "K", .compatible = "compat2", .name = "name9", },
+	{}
+};
+
+static struct {
+	const char *path;
+	const char *data;
+} match_node_tests[] = {
+	{ .path = "/testcase-data/match-node/name0", .data = "A", },
+	{ .path = "/testcase-data/match-node/name1", .data = "B", },
+	{ .path = "/testcase-data/match-node/a/name2", .data = "Ca", },
+	{ .path = "/testcase-data/match-node/b/name2", .data = "Cb", },
+	{ .path = "/testcase-data/match-node/c/name2", .data = "Cc", },
+	{ .path = "/testcase-data/match-node/name3", .data = "E", },
+	{ .path = "/testcase-data/match-node/name4", .data = "G", },
+	{ .path = "/testcase-data/match-node/name5", .data = "H", },
+	{ .path = "/testcase-data/match-node/name6", .data = "G", },
+	{ .path = "/testcase-data/match-node/name7", .data = "I", },
+	{ .path = "/testcase-data/match-node/name8", .data = "J", },
+	{ .path = "/testcase-data/match-node/name9", .data = "K", },
+};
+
+static void __init of_selftest_match_node(void)
+{
+	struct device_node *np;
+	const struct of_device_id *match;
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(match_node_tests); i++) {
+		np = of_find_node_by_path(match_node_tests[i].path);
+		if (!np) {
+			selftest(0, "missing testcase node %s\n",
+				match_node_tests[i].path);
+			continue;
+		}
+
+		match = of_match_node(match_node_table, np);
+		if (!match) {
+			selftest(0, "%s didn't match anything\n",
+				match_node_tests[i].path);
+			continue;
+		}
+
+		if (strcmp(match->data, match_node_tests[i].data) != 0) {
+			selftest(0, "%s got wrong match. expected %s, got %s\n",
+				match_node_tests[i].path, match_node_tests[i].data,
+				(const char *)match->data);
+			continue;
+		}
+		selftest(1, "passed");
+	}
+}
+
 static int __init of_selftest(void)
 {
 	struct device_node *np;
@@ -316,6 +382,7 @@ static int __init of_selftest(void)
 	of_selftest_property_match_string();
 	of_selftest_parse_interrupts();
 	of_selftest_parse_interrupts_extended();
+	of_selftest_match_node();
 	pr_info("end of selftest - %i passed, %i failed\n",
 		selftest_results.passed, selftest_results.failed);
 	return 0;
diff --git a/drivers/of/testcase-data/testcases.dtsi b/drivers/of/testcase-data/testcases.dtsi
index 3cc2f55534ac..3a5b75a8e4d7 100644
--- a/drivers/of/testcase-data/testcases.dtsi
+++ b/drivers/of/testcase-data/testcases.dtsi
@@ -1,2 +1,3 @@
 #include "tests-phandle.dtsi"
 #include "tests-interrupts.dtsi"
+#include "tests-match.dtsi"
diff --git a/drivers/of/testcase-data/tests-match.dtsi b/drivers/of/testcase-data/tests-match.dtsi
new file mode 100644
index 000000000000..c9e541129534
--- /dev/null
+++ b/drivers/of/testcase-data/tests-match.dtsi
@@ -0,0 +1,19 @@
+
+/ {
+	testcase-data {
+		match-node {
+			name0 { };
+			name1 { device_type = "type1"; };
+			a { name2 { device_type = "type1"; }; };
+			b { name2 { }; };
+			c { name2 { device_type = "type2"; }; };
+			name3 { compatible = "compat3"; };
+			name4 { compatible = "compat2", "compat3"; };
+			name5 { compatible = "compat2", "compat3"; };
+			name6 { compatible = "compat1", "compat2", "compat3"; };
+			name7 { compatible = "compat2"; device_type = "type1"; };
+			name8 { compatible = "compat2"; device_type = "type1"; };
+			name9 { compatible = "compat2"; };
+		};
+	};
+};
-- 
1.8.3.2

Re: [PATCH 4/4] of: Add self test for of_match_node()

[Kevin Hao]

[-- Attachment #1: Type: text/plain, Size: 1203 bytes --]

On Tue, Feb 18, 2014 at 10:31:20PM +0000, Grant Likely wrote:
> Adds a selftest function for the of_match_node function. of_match_node
> is supposed to handle precedence for the compatible property as well as
> the name and device_type values. This patch adds some test case data and
> a function that makes sure each test node matches against the correct
> entry of an of_device_id table.
> 
> This code was written to verify the new of_match_node() implementation
> that is an earlier part of this series.
> 
> Currently all but one test passes. There is one scenario where the empty
> "b/name2" node is getting matched against an entry without any
> device_type property at all. It is unknown why this is, but it needs to
> be solved before this patch can be committed. (However, this is testing
> the new of_match_table implementation, which still does far better than
> the old implementation which gets the precedence completely wrong.)

We can drop the above paragraph now since all the test cases passed on
the new version of of_match_node().

> 
> Signed-off-by: Grant Likely <grant.likely@linaro.org>
> Cc: Kevin Hau <haokexin@gmail.com>

s/Hau/Hao/

Thanks,
Kevin

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]