[PATCH 1/2] hwdb: Remove unutilized return value

[PATCH 1/2] hwdb: Remove unutilized return value

[Mat Martineau]

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

trie_fnmatch always returned 0. Make it return void instead.
---
 ell/hwdb.c | 18 +++++++-----------
 1 file changed, 7 insertions(+), 11 deletions(-)

diff --git a/ell/hwdb.c b/ell/hwdb.c
index caa8eb3..b251f27 100644
--- a/ell/hwdb.c
+++ b/ell/hwdb.c
@@ -198,8 +198,9 @@ LIB_EXPORT void l_hwdb_unref(struct l_hwdb *hwdb)
 	l_free(hwdb);
 }
 
-static int trie_fnmatch(const void *addr, uint64_t offset, const char *prefix,
-			const char *string, struct l_hwdb_entry **entries)
+static void trie_fnmatch(const void *addr, uint64_t offset, const char *prefix,
+				const char *string,
+				struct l_hwdb_entry **entries)
 {
 	const struct trie_node *node = addr + offset;
 	const void *addr_ptr = addr + offset + sizeof(*node);
@@ -217,25 +218,22 @@ static int trie_fnmatch(const void *addr, uint64_t offset, const char *prefix,
 
 	for (i = 0; i < child_count; i++) {
 		const struct trie_child *child = addr_ptr;
-		int err;
 
 		scratch_buf[scratch_len] = child->c;
 
-		err = trie_fnmatch(addr, le64_to_cpu(child->child_offset),
-						scratch_buf, string, entries);
-		if (err)
-			return err;
+		trie_fnmatch(addr, le64_to_cpu(child->child_offset),
+				scratch_buf, string, entries);
 
 		addr_ptr += sizeof(*child);
 	}
 
 	if (!entry_count)
-		return 0;
+		return;
 
 	scratch_buf[scratch_len] = '\0';
 
 	if (fnmatch(scratch_buf, string, 0))
-		return 0;
+		return;
 
 	for (i = 0; i < entry_count; i++) {
 		const struct trie_entry *entry = addr_ptr;
@@ -254,8 +252,6 @@ static int trie_fnmatch(const void *addr, uint64_t offset, const char *prefix,
 
 		addr_ptr += sizeof(*entry);
 	}
-
-	return 0;
 }
 
 LIB_EXPORT struct l_hwdb_entry *l_hwdb_lookup(struct l_hwdb *hwdb,
-- 
2.9.2

[PATCH 2/2] hwdb: Optimize lookup execution

[Mat Martineau]

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

Decide whether to descend into child nodes based on fnmatch() results,
rather than performing a depth-first search of all nodes.

Using test-hwdb as an example, it now takes an average of ~50 calls to
trie_fnmatch to perform a lookup instead of ~100000.
---
 ell/hwdb.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/ell/hwdb.c b/ell/hwdb.c
index b251f27..0addaa2 100644
--- a/ell/hwdb.c
+++ b/ell/hwdb.c
@@ -216,6 +216,18 @@ static void trie_fnmatch(const void *addr, uint64_t offset, const char *prefix,
 	sprintf(scratch_buf, "%s%s", prefix, prefix_str);
 	scratch_buf[scratch_len + 1] = '\0';
 
+	/*
+	 * Only incur the cost of this fnmatch() if there are children
+	 * to visit.  In practice, nodes have either entries or children
+	 * so fnmatch() will only be called once per node.
+	 */
+	if (child_count) {
+		scratch_buf[scratch_len] = '*';
+
+		if (fnmatch(scratch_buf, string, 0) == FNM_NOMATCH)
+			child_count = 0;
+	}
+
 	for (i = 0; i < child_count; i++) {
 		const struct trie_child *child = addr_ptr;
 
@@ -281,13 +293,6 @@ LIB_EXPORT struct l_hwdb_entry *l_hwdb_lookup_valist(struct l_hwdb *hwdb,
 	if (len < 0)
 		return NULL;
 
-	/*
-	 * This search operation is not optimized for the Patricia Trie
-	 * and will compare every single entry in the database.
-	 *
-	 * An optimized version should allow using the Patricia Trie data
-	 * structure and follow the shortest path to the matching entry.
-	 */
 	trie_fnmatch(hwdb->addr, hwdb->root, "", modalias, &entries);
 
 	free(modalias);
-- 
2.9.2

Re: [PATCH 2/2] hwdb: Optimize lookup execution

[Mat Martineau]

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

On Tue, 2 Aug 2016, Mat Martineau wrote:

> Decide whether to descend into child nodes based on fnmatch() results,
> rather than performing a depth-first search of all nodes.
>
> Using test-hwdb as an example, it now takes an average of ~50 calls to
> trie_fnmatch to perform a lookup instead of ~100000.

Before I forget, the other potential trie_fnmatch optimization I spotted 
was to reduce stack usage. alloca isn't expensive in terms of runtime, but 
there's no reason to have so many copies of pattern prefixes sitting 
around. It would work to allocate a pattern buffer at the beginning. The 
matching pattern will not typically be longer than the string being 
matched, but '*' may match nothing so reallocs would be a possibility.

--
Mat Martineau
Intel OTC

Re: [PATCH 1/2] hwdb: Remove unutilized return value

[Denis Kenzior]

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

Hi Mat,

On 08/02/2016 02:21 PM, Mat Martineau wrote:
> trie_fnmatch always returned 0. Make it return void instead.
> ---
>   ell/hwdb.c | 18 +++++++-----------
>   1 file changed, 7 insertions(+), 11 deletions(-)
>

Both applied, thanks.

Regards,
-Denis