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

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

[Kevin Hao]

This implemented the matching method for __of_match_node() suggested
by Grant Likely. You can find more detail at:
  http://patchwork.ozlabs.org/patch/320286/

Kevin Hao (2):
  Revert "of: search the best compatible match first in
    __of_match_node()"
  of: reimplement the matching method for __of_match_node()

 drivers/of/base.c | 126 +++++++++++++++++++++++++++++-------------------------
 1 file changed, 67 insertions(+), 59 deletions(-)

-- 
1.8.5.3

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Kevin Hao]

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-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.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.5.3

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 2/2] 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-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.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..378091f8460c 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 *= 10;
+
+		/*
+		 * 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.5.3

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Grant Likely]

On Tue, 18 Feb 2014 15:57:29 +0800, Kevin Hao <haokexin-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> 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-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>

Acked-by: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.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.5.3
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Grant Likely]

On Tue, 18 Feb 2014 15:57:30 +0800, Kevin Hao <haokexin-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> 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.

The patch looks good, but I wasn't confident applying it directly
without some validation, so I've written a test case for this function.
I'll resend the series to the list and cc you. Unfortunately I've found
one case that is failing on the test cases, but I'm too tired to debug
it now. Maybe you'd like to take a look. The test case may very well be
wrong.

g.

> 
> Signed-off-by: Kevin Hao <haokexin-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.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..378091f8460c 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 *= 10;
> +
> +		/*
> +		 * 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.5.3
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[Kevin Hao]

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

On Tue, Feb 18, 2014 at 10:29:18PM +0000, Grant Likely wrote:
> On Tue, 18 Feb 2014 15:57:30 +0800, Kevin Hao <haokexin-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> 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.
> 
> The patch looks good, but I wasn't confident applying it directly
> without some validation, so I've written a test case for this function.
> I'll resend the series to the list and cc you. Unfortunately I've found
> one case that is failing on the test cases, but I'm too tired to debug
> it now. Maybe you'd like to take a look. The test case may very well be
> wrong.

The test case looks great. Actually there is a bug in this patch. I will make
new spin to fix it.

Thanks,
Kevin

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