[RFC PATCH 0/2] use gnuhash to speed up device/driver match

[RFC PATCH 0/2] use gnuhash to speed up device/driver match

[Jean-Christophe PLAGNIOL-VILLARD]

Hi,

	The following patch series use the gnu hash to speedup device/driver
	matching.

	String compare is slow so we will calculate at runtime a hash that we
	can compare quickly to speed up the match

	in a second step we could speed up this more by calculating the hash
	at compile time

The following changes since commit d92ed454107b4d6f0d30fa0271da191ae5911d18:

  Merge branch 'for-next/video' into next (2017-02-27 08:51:08 +0100)

are available in the git repository at:

  git://git.jcrosoft.org/barebox.git delivery/gnuhash

for you to fetch changes up to 5ede85afc958bdf488a3c5e56061e7f27c26cbc6:

  driver: generate hash at runtime to speed up device/driver matching (2017-03-01 03:49:34 +0800)

----------------------------------------------------------------
Jean-Christophe PLAGNIOL-VILLARD (2):
      driver: remove the const of struct platform_device_id *id_table
      driver: generate hash at runtime to speed up device/driver matching

 drivers/base/bus.c    | 16 ++++++++++------
 drivers/base/driver.c | 27 ++++++++++++++++++++++++++-
 include/driver.h      |  7 ++++++-
 3 files changed, 42 insertions(+), 8 deletions(-)

Best Regards,
J.

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

[PATCH 1/2] driver: remove the const of struct platform_device_id *id_table

[Jean-Christophe PLAGNIOL-VILLARD]

so we can generate the hash at register time

This will allow speed up the device/driver matching as strcmp is slow.

Signed-off-by: Jean-Christophe PLAGNIOL-VILLARD <plagnioj@jcrosoft.com>
---
 drivers/base/bus.c | 4 ++--
 include/driver.h   | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/drivers/base/bus.c b/drivers/base/bus.c
index b889a4866..03feba502 100644
--- a/drivers/base/bus.c
+++ b/drivers/base/bus.c
@@ -55,7 +55,7 @@ int device_match(struct device_d *dev, struct driver_d *drv)
 		return of_match(dev, drv);
 
 	if (drv->id_table) {
-		const struct platform_device_id *id = drv->id_table;
+		struct platform_device_id *id = drv->id_table;
 
 		while (id->name) {
 			if (!strcmp(id->name, dev->name)) {
@@ -73,7 +73,7 @@ int device_match(struct device_d *dev, struct driver_d *drv)
 
 int device_match_of_modalias(struct device_d *dev, struct driver_d *drv)
 {
-	const struct platform_device_id *id = drv->id_table;
+	struct platform_device_id *id = drv->id_table;
 	const char *of_modalias = NULL, *p;
 	int cplen;
 	const char *compat;
diff --git a/include/driver.h b/include/driver.h
index 6abaaad8b..db7f9c780 100644
--- a/include/driver.h
+++ b/include/driver.h
@@ -107,7 +107,7 @@ struct driver_d {
 
 	struct bus_type *bus;
 
-	const struct platform_device_id *id_table;
+	struct platform_device_id *id_table;
 	const struct of_device_id *of_compatible;
 };
 
-- 
2.11.0


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

[PATCH 2/2] driver: generate hash at runtime to speed up device/driver matching

[Jean-Christophe PLAGNIOL-VILLARD]

use GNU Hash

Signed-off-by: Jean-Christophe PLAGNIOL-VILLARD <plagnioj@jcrosoft.com>
---
 drivers/base/bus.c    | 12 ++++++++----
 drivers/base/driver.c | 27 ++++++++++++++++++++++++++-
 include/driver.h      |  5 +++++
 3 files changed, 39 insertions(+), 5 deletions(-)

diff --git a/drivers/base/bus.c b/drivers/base/bus.c
index 03feba502..2da736a4b 100644
--- a/drivers/base/bus.c
+++ b/drivers/base/bus.c
@@ -58,13 +58,13 @@ int device_match(struct device_d *dev, struct driver_d *drv)
 		struct platform_device_id *id = drv->id_table;
 
 		while (id->name) {
-			if (!strcmp(id->name, dev->name)) {
+			if (dev->hash == id->hash && !strcmp(id->name, dev->name)) {
 				dev->id_entry = id;
 				return 0;
 			}
 			id++;
 		}
-	} else if (!strcmp(dev->name, drv->name)) {
+	} else if (dev->hash == drv->hash && !strcmp(dev->name, drv->name)) {
 		return 0;
 	}
 
@@ -77,6 +77,7 @@ int device_match_of_modalias(struct device_d *dev, struct driver_d *drv)
 	const char *of_modalias = NULL, *p;
 	int cplen;
 	const char *compat;
+	unsigned long hash;
 
 	if (!device_match(dev, drv))
 		return 0;
@@ -90,14 +91,17 @@ int device_match_of_modalias(struct device_d *dev, struct driver_d *drv)
 
 	p = strchr(compat, ',');
 	of_modalias = p ? p + 1 : compat;
+	if (of_modalias)
+		hash = gnu_hash(of_modalias);
 
 	while (id->name) {
-		if (!strcmp(id->name, dev->name)) {
+		if (id->hash == dev->hash && !strcmp(id->name, dev->name)) {
 			dev->id_entry = id;
 			return 0;
 		}
 
-		if (of_modalias && !strcmp(id->name, of_modalias)) {
+		if (of_modalias && id->hash == hash &&
+			!strcmp(id->name, of_modalias)) {
 			dev->id_entry = id;
 			return 0;
 		}
diff --git a/drivers/base/driver.c b/drivers/base/driver.c
index 5867fe45d..c3257f640 100644
--- a/drivers/base/driver.c
+++ b/drivers/base/driver.c
@@ -46,6 +46,17 @@ EXPORT_SYMBOL(driver_list);
 static LIST_HEAD(active);
 static LIST_HEAD(deferred);
 
+unsigned long gnu_hash(const unsigned char *name)
+{
+	unsigned long h = 5381;
+	unsigned char c;
+
+	for (c = *name; c != '\0'; c = *++name)
+		h = h * 33 + c;
+
+	return h & 0xffffffff;
+}
+
 struct device_d *get_device_by_name(const char *name)
 {
 	struct device_d *dev;
@@ -61,9 +72,10 @@ struct device_d *get_device_by_name(const char *name)
 static struct device_d *get_device_by_name_id(const char *name, int id)
 {
 	struct device_d *dev;
+	unsigned long hash = gnu_hash(name);
 
 	for_each_device(dev) {
-		if(!strcmp(dev->name, name) && id == dev->id)
+		if(hash == dev->hash && !strcmp(dev->name, name) && id == dev->id)
 			return dev;
 	}
 
@@ -165,6 +177,8 @@ int register_device(struct device_d *new_device)
 {
 	struct driver_d *drv;
 
+	new_device->hash = gnu_hash(new_device->name);
+
 	if (new_device->id == DEVICE_ID_DYNAMIC) {
 		new_device->id = get_free_deviceid(new_device->name);
 	} else {
@@ -302,6 +316,17 @@ int register_driver(struct driver_d *drv)
 
 	BUG_ON(!drv->bus);
 
+	drv->hash = gnu_hash(drv->name);
+
+	if (drv->id_table) {
+		struct platform_device_id *id = drv->id_table;
+
+		while (id->name) {
+			id->hash = gnu_hash(id->name);
+			id++;
+		}
+	}
+
 	list_add_tail(&drv->list, &driver_list);
 	list_add_tail(&drv->bus_list, &drv->bus->driver_list);
 
diff --git a/include/driver.h b/include/driver.h
index db7f9c780..64b59dc91 100644
--- a/include/driver.h
+++ b/include/driver.h
@@ -31,8 +31,11 @@
 struct filep;
 struct bus_type;
 
+unsigned long gnu_hash(const unsigned char *name);
+
 struct platform_device_id {
 	const char *name;
+	unsigned long hash;
 	unsigned long driver_data;
 };
 
@@ -42,6 +45,7 @@ struct device_d {
 	 * driver. This is a descriptive name and could be MPC5XXX_ether or
 	 * imx_serial. */
 	char name[MAX_DRIVER_NAME];
+	unsigned long hash;
 	/*! The id is used to uniquely identify a device in the system. The id
 	 * will show up under /dev/ as the device's name. Usually this is
 	 * something like eth0 or nor0. */
@@ -95,6 +99,7 @@ struct driver_d {
 	/*! The name of this driver. Used to match to
 	 * the corresponding device. */
 	const char *name;
+	unsigned long hash;
 
 	struct list_head list;
 	struct list_head bus_list; /* our bus            */
-- 
2.11.0


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

Re: [RFC PATCH 0/2] use gnuhash to speed up device/driver match

[Sascha Hauer]

On Sat, Mar 04, 2017 at 08:12:41AM +0100, Jean-Christophe PLAGNIOL-VILLARD wrote:
> Hi,
> 
> 	The following patch series use the gnu hash to speedup device/driver
> 	matching.
> 
> 	String compare is slow so we will calculate at runtime a hash that we
> 	can compare quickly to speed up the match
> 
> 	in a second step we could speed up this more by calculating the hash
> 	at compile time

On a i.MX53 quickstart board this patch reduces startup time from 115.9ms
to 115.4ms. On a i.MX35 board the startup time is reduced by 72us. I
don't think this is a valuable gain. Do you have any situation where you
really spend significant time in strcmp?

Sascha

-- 
Pengutronix e.K.                           |                             |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
Peiner Str. 6-8, 31137 Hildesheim, Germany | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

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