process non-dependant hotplug events in parallel

Calculate event dependancy of hotplug events based of their sysfs_path. In
hotplug_event_process_queue if an event is dependant on an event in progress,
it will be held back in in the queue.

The event dependancy calculation is cribbed from udev. It requires the event
sequnce number in order to order the dependancies. We don't get event sequence
numbers during coldplug, so we emulate them using a simple counter.

6 files changed, 268 insertions, 51 deletions

diff --git a/hald/device.c b/hald/device.c
index 344d88d8..170d06ff 100644
--- a/hald/device.c
+++ b/hald/device.c
@@ -370,6 +370,7 @@ enum {
 	CAPABILITY_ADDED,
         LOCK_ACQUIRED,
         LOCK_RELEASED,
+	PRE_PROPERTY_CHANGED,
 	LAST_SIGNAL
 };
 
@@ -425,6 +426,19 @@ hal_device_class_init (HalDeviceClass *klass)
 			      G_TYPE_BOOLEAN,
 			      G_TYPE_BOOLEAN);
 
+	signals[PRE_PROPERTY_CHANGED] =
+		g_signal_new ("pre_property_changed",
+			      G_TYPE_FROM_CLASS (klass),
+			      G_SIGNAL_RUN_LAST,
+			      G_STRUCT_OFFSET (HalDeviceClass,
+					       property_changed),
+			      NULL, NULL,
+			      hald_marshal_VOID__STRING_BOOL,
+			      G_TYPE_NONE, 2,
+			      G_TYPE_STRING,
+			      G_TYPE_BOOLEAN);
+
+
 	signals[CAPABILITY_ADDED] =
 		g_signal_new ("capability_added",
 			      G_TYPE_FROM_CLASS (klass),
@@ -1058,6 +1072,9 @@ hal_device_property_set_string (HalDevice *device, const char *key,
 		if (strcmp (hal_property_get_string (prop), value != NULL ? value : "") == 0)
 			return TRUE;
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		hal_property_set_string (prop, value);
 
 		g_signal_emit (device, signals[PROPERTY_CHANGED], 0,
@@ -1094,6 +1111,9 @@ hal_device_property_set_int (HalDevice *device, const char *key,
 		if (hal_property_get_int (prop) == value)
 			return TRUE;
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		hal_property_set_int (prop, value);
 
 		g_signal_emit (device, signals[PROPERTY_CHANGED], 0,
@@ -1129,6 +1149,9 @@ hal_device_property_set_uint64 (HalDevice *device, const char *key,
 		if (hal_property_get_uint64 (prop) == value)
 			return TRUE;
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		hal_property_set_uint64 (prop, value);
 
 		g_signal_emit (device, signals[PROPERTY_CHANGED], 0,
@@ -1164,6 +1187,9 @@ hal_device_property_set_bool (HalDevice *device, const char *key,
 		if (hal_property_get_bool (prop) == value)
 			return TRUE;
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		hal_property_set_bool (prop, value);
 
 		g_signal_emit (device, signals[PROPERTY_CHANGED], 0,
@@ -1199,6 +1225,9 @@ hal_device_property_set_double (HalDevice *device, const char *key,
 		if (hal_property_get_double (prop) == value)
 			return TRUE;
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		hal_property_set_double (prop, value);
 
 		g_signal_emit (device, signals[PROPERTY_CHANGED], 0,
@@ -1246,6 +1275,9 @@ hal_device_property_set_strlist (HalDevice *device, const char *key,
 			if (equal) return TRUE;
 		}
 
+		g_signal_emit (device, signals[PRE_PROPERTY_CHANGED], 0,
+			       key, FALSE);
+
 		/* TODO: check why  hal_property_strlist_clear (prop) not work and why
 		 *       we need to remove the key and a new one to get this running:
 		 *	 - multiple copy calls mixed with e.g. append rules   
diff --git a/hald/device_store.c b/hald/device_store.c
index 23c054d3..aff8f132 100644
--- a/hald/device_store.c
+++ b/hald/device_store.c
@@ -137,6 +137,7 @@ hal_device_store_class_init (HalDeviceStoreClass *klass)
 static void
 hal_device_store_init (HalDeviceStore *device)
 {
+	device->property_index = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
 }
 
 GType
@@ -175,6 +176,27 @@ hal_device_store_new (void)
 }
 
 static void
+property_index_check_all (HalDeviceStore *store, HalDevice *device, gboolean add);
+
+static void
+property_index_modify_string (HalDeviceStore *store, HalDevice *device,
+			      const char *key, gboolean added);
+
+static void
+device_pre_property_changed (HalDevice *device,
+			      const char *key,
+			      gboolean removed,
+			      gpointer data)
+{
+	HalDeviceStore *store = HAL_DEVICE_STORE (data);
+
+	if (hal_device_property_get_type (device, key) == HAL_PROPERTY_TYPE_STRING) {
+		property_index_modify_string(store, device, key, FALSE);
+	}
+}
+
+
+static void
 emit_device_property_changed (HalDevice *device,
 			      const char *key,
 			      gboolean added,
@@ -183,6 +205,10 @@ emit_device_property_changed (HalDevice *device,
 {
 	HalDeviceStore *store = HAL_DEVICE_STORE (data);
 
+	if (hal_device_property_get_type (device, key) == HAL_PROPERTY_TYPE_STRING) {
+		property_index_modify_string(store, device, key, TRUE);
+	}
+
 	g_signal_emit (store, signals[DEVICE_PROPERTY_CHANGED], 0,
 		       device, key, added, removed);
 }
@@ -238,6 +264,8 @@ hal_device_store_add (HalDeviceStore *store, HalDevice *device)
 
 	g_signal_connect (device, "property_changed",
 			  G_CALLBACK (emit_device_property_changed), store);
+	g_signal_connect (device, "pre_property_changed",
+			  G_CALLBACK (device_pre_property_changed), store);
 	g_signal_connect (device, "capability_added",
 			  G_CALLBACK (emit_device_capability_added), store);
 	g_signal_connect (device, "lock_acquired",
@@ -245,6 +273,7 @@ hal_device_store_add (HalDeviceStore *store, HalDevice *device)
 	g_signal_connect (device, "lock_released",
 			  G_CALLBACK (emit_device_lock_released), store);
 
+	property_index_check_all (store, device, TRUE);
 	g_signal_emit (store, signals[STORE_CHANGED], 0, device, TRUE);
 
 out:
@@ -272,6 +301,8 @@ hal_device_store_remove (HalDeviceStore *store, HalDevice *device)
 					      (gpointer)emit_device_lock_released,
 					      store);
 
+	property_index_check_all (store, device, FALSE);
+
 	g_signal_emit (store, signals[STORE_CHANGED], 0, device, FALSE);
 
 	g_object_unref (device);
@@ -345,25 +376,37 @@ hal_device_store_match_key_value_string (HalDeviceStore *store,
 					 const char *value)
 {
 	GSList *iter;
+	GSList *devices;
+	GHashTable *index;
 
 	g_return_val_if_fail (store != NULL, NULL);
 	g_return_val_if_fail (key != NULL, NULL);
 	g_return_val_if_fail (value != NULL, NULL);
 
-	for (iter = store->devices; iter != NULL; iter = iter->next) {
-		HalDevice *d = HAL_DEVICE (iter->data);
-		int type;
-
-		if (!hal_device_has_property (d, key))
-			continue;
-
-		type = hal_device_property_get_type (d, key);
-		if (type != HAL_PROPERTY_TYPE_STRING)
-			continue;
-
-		if (strcmp (hal_device_property_get_string (d, key),
-			    value) == 0)
-			return d;
+	index = g_hash_table_lookup (store->property_index, key);
+
+	if (index) {
+		devices = g_hash_table_lookup (index, value);
+		if (devices)
+			return (HalDevice*) devices->data;
+		else
+			return NULL;
+	} else {
+		for (iter = store->devices; iter != NULL; iter = iter->next) {
+			HalDevice *d = HAL_DEVICE (iter->data);
+			int type;
+
+			if (!hal_device_has_property (d, key))
+				continue;
+
+			type = hal_device_property_get_type (d, key);
+			if (type != HAL_PROPERTY_TYPE_STRING)
+				continue;
+
+			if (strcmp (hal_device_property_get_string (d, key),
+				    value) == 0)
+				return d;
+		}
 	}
 
 	return NULL;
@@ -404,26 +447,89 @@ hal_device_store_match_multiple_key_value_string (HalDeviceStore *store,
 {
 	GSList *iter;
 	GSList *matches = NULL;
+	GSList *devices;
+	GHashTable *index;
 
 	g_return_val_if_fail (store != NULL, NULL);
 	g_return_val_if_fail (key != NULL, NULL);
 	g_return_val_if_fail (value != NULL, NULL);
 
-	for (iter = store->devices; iter != NULL; iter = iter->next) {
-		HalDevice *d = HAL_DEVICE (iter->data);
-		int type;
+	index = g_hash_table_lookup (store->property_index, key);
 
-		if (!hal_device_has_property (d, key))
-			continue;
+	if (index) {
+		devices = g_hash_table_lookup (index, value);
+		return g_slist_copy(devices);
+	} else {
+		for (iter = store->devices; iter != NULL; iter = iter->next) {
+			HalDevice *d = HAL_DEVICE (iter->data);
+			int type;
 
-		type = hal_device_property_get_type (d, key);
-		if (type != HAL_PROPERTY_TYPE_STRING)
-			continue;
+			if (!hal_device_has_property (d, key))
+				continue;
+
+			type = hal_device_property_get_type (d, key);
+			if (type != HAL_PROPERTY_TYPE_STRING)
+				continue;
 
-		if (strcmp (hal_device_property_get_string (d, key),
-			    value) == 0)
-			matches = g_slist_prepend (matches, d);
+			if (strcmp (hal_device_property_get_string (d, key),
+				    value) == 0)
+				matches = g_slist_prepend (matches, d);
+		}
 	}
 
 	return matches;
 }
+
+
+void
+hal_device_store_index_property (HalDeviceStore *store, const char *key)
+{
+	GHashTable *index;
+
+	index = g_hash_table_lookup (store->property_index, key);
+
+	if (!index) {
+		index = g_hash_table_new (g_str_hash, g_str_equal);
+		g_hash_table_insert (store->property_index, g_strdup (key), index);
+	}
+}
+
+static void
+property_index_modify_string (HalDeviceStore *store, HalDevice *device,
+			      const char *key, gboolean added)
+{
+	GHashTable *index;
+	const char *value;
+	GSList *devices;
+
+	value = hal_device_property_get_string (device, key);
+	index = g_hash_table_lookup (store->property_index, key);
+
+	if (!index) return;
+
+	devices = g_hash_table_lookup (index, value);
+
+	if (added) { /*add*/
+		HAL_DEBUG (("adding %p to (%s,%s)", device, key, value));
+		devices = g_slist_prepend (devices, device);
+	} else { /*remove*/
+		HAL_DEBUG (("removing %p from (%s,%s)", device, key, value));
+		devices = g_slist_remove_all (devices, device);
+	}
+	g_hash_table_insert (index, (gpointer) value, devices);
+}
+
+
+static void
+property_index_check_all (HalDeviceStore *store, HalDevice *device, gboolean added)
+{
+	GList *indexed_properties, *lp;
+
+	indexed_properties = g_hash_table_get_keys (store->property_index);
+	for (lp = indexed_properties; lp; lp = g_list_next (lp)) {
+		if (hal_device_property_get_type (device, lp->data) == HAL_PROPERTY_TYPE_STRING) {
+			property_index_modify_string (store, device, lp->data, added);
+		}
+	}
+}
+
diff --git a/hald/device_store.h b/hald/device_store.h
index 300f4c70..c79d2f69 100644
--- a/hald/device_store.h
+++ b/hald/device_store.h
@@ -38,6 +38,7 @@ struct _HalDeviceStore {
 	GObject parent;
 
 	GSList *devices;
+	GHashTable *property_index;
 };
 
 struct _HalDeviceStoreClass {
@@ -121,5 +122,6 @@ GSList         *hal_device_store_match_multiple_key_value_string (HalDeviceStore
 
 void hal_device_store_print (HalDeviceStore *store);
 
+void		hal_device_store_index_property (HalDeviceStore *store, const char *key);
 
 #endif /* DEVICE_STORE_H */
diff --git a/hald/hald_marshal.list b/hald/hald_marshal.list
index 14dd6f82..28439b60 100644
--- a/hald/hald_marshal.list
+++ b/hald/hald_marshal.list
@@ -1,6 +1,7 @@
 VOID:OBJECT,STRING,STRING
 VOID:STRING,STRING
 VOID:STRING,BOOL,BOOL
+VOID:STRING,BOOL
 VOID:STRING
 VOID:OBJECT,BOOL
 VOID:OBJECT,STRING,BOOL,BOOL
diff --git a/hald/linux/coldplug.c b/hald/linux/coldplug.c
index dbc18309..7e65951a 100644
--- a/hald/linux/coldplug.c
+++ b/hald/linux/coldplug.c
@@ -56,7 +56,7 @@ static GHashTable *sysfs_to_udev_map;
 static GSList *device_list;
 static char dev_root[HAL_PATH_MAX];
 static gchar *udevinfo_stdout = NULL;
-
+static unsigned long long coldplug_seqnum = 0;
 typedef struct _UdevInfo UdevInfo;
 
 struct _UdevInfo
@@ -309,6 +309,8 @@ no_node:
 	hotplug_event->action = HOTPLUG_ACTION_ADD;
 	hotplug_event->type = type;
 	hotplug_event->sysfs.net_ifindex = -1;
+	/*emulate sequence numbers for coldplug events*/
+	hotplug_event->sysfs.seqnum = coldplug_seqnum++;
 	return hotplug_event;
 }
 
diff --git a/hald/linux/hotplug.c b/hald/linux/hotplug.c
index 2ca62ef3..ec1880f6 100644
--- a/hald/linux/hotplug.c
+++ b/hald/linux/hotplug.c
@@ -50,17 +50,20 @@
 #include "hotplug.h"
 
 /** Queue of ordered hotplug events */
-static GQueue *hotplug_event_queue;
+static GQueue *hotplug_event_queue = NULL;
 
 /** List of HotplugEvent objects we are currently processing */
-static GSList *hotplug_events_in_progress = NULL;
+static GList *hotplug_events_in_progress = NULL;
+
+/** List of HotplugEvent objects that are blocked on a event in process */
+GList *hotplug_events_blocked = NULL;
 
 void
 hotplug_event_end (void *end_token)
 {
 	HotplugEvent *hotplug_event = (HotplugEvent *) end_token;
 
-	hotplug_events_in_progress = g_slist_remove (hotplug_events_in_progress, hotplug_event);
+	hotplug_events_in_progress = g_list_remove (hotplug_events_in_progress, hotplug_event);
 
 	g_slice_free (HotplugEvent, hotplug_event);
 }
@@ -71,7 +74,7 @@ hotplug_event_reposted (void *end_token)
 	HotplugEvent *hotplug_event = (HotplugEvent *) end_token;
 
 	hotplug_event->reposted = TRUE;
-	hotplug_events_in_progress = g_slist_remove (hotplug_events_in_progress, hotplug_event);
+	hotplug_events_in_progress = g_list_remove (hotplug_events_in_progress, hotplug_event);
 }
 
 static void
@@ -310,7 +313,7 @@ hotplug_event_begin (HotplugEvent *hotplug_event)
 void 
 hotplug_event_enqueue (HotplugEvent *hotplug_event)
 {
-	if (hotplug_event_queue == NULL)
+	if (G_UNLIKELY (hotplug_event_queue == NULL))
 		hotplug_event_queue = g_queue_new ();
 
 	g_queue_push_tail (hotplug_event_queue, hotplug_event);
@@ -319,40 +322,111 @@ hotplug_event_enqueue (HotplugEvent *hotplug_event)
 void 
 hotplug_event_enqueue_at_front (HotplugEvent *hotplug_event)
 {
-	if (hotplug_event_queue == NULL)
+	if (G_UNLIKELY (hotplug_event_queue == NULL))
 		hotplug_event_queue = g_queue_new ();
 
 	g_queue_push_head (hotplug_event_queue, hotplug_event);
 }
 
+static gboolean
+compare_sysfspath(const char *running, const char *waiting)
+{
+	int i;
+
+	for (i = 0; i < HAL_PATH_MAX; i++) {
+		/* identical device event found */
+		if (running[i] == '\0' && waiting[i] == '\0')
+			return TRUE;
+
+		/* parent device event found */
+		if (running[i] == '\0' && waiting[i] == '/')
+			return TRUE;
+
+		/* child device event found */
+		if (running[i] == '/' && waiting[i] == '\0')
+			return TRUE;
+
+		/* no matching event */
+		if (running[i] != waiting[i])
+			break;
+	}
+
+	return FALSE;
+}
+
+/*
+ * Returns TRUE if @eventl depends on @eventr
+ */
+static gboolean
+compare_event (HotplugEvent *eventl, HotplugEvent *eventr)
+{
+	if (*eventl->sysfs.sysfs_path_old != '\0')
+		if (strcmp (eventr->sysfs.sysfs_path_old, eventl->sysfs.sysfs_path_old) == 0)
+			return TRUE;
+	return compare_sysfspath (eventr->sysfs.sysfs_path, eventl->sysfs.sysfs_path);
+}
+
+/*
+ * Returns TRUE if @hotplug_event depends on any event in @events
+ */
+static gboolean
+compare_events (HotplugEvent *hotplug_event, GList *events)
+{
+	GList *lp;
+	HotplugEvent *loop_event;
+
+	switch (hotplug_event->type) {
+
+	/* explicit fallthrough */
+	case HOTPLUG_EVENT_SYSFS:
+	case HOTPLUG_EVENT_SYSFS_DEVICE:
+	case HOTPLUG_EVENT_SYSFS_BLOCK:
+
+		for (lp = events; lp; lp = g_list_next (lp)) {
+			loop_event = (HotplugEvent*) lp->data;
+			/* skip ourselves and all later events*/
+			if (loop_event->sysfs.seqnum >= hotplug_event->sysfs.seqnum)
+				break;
+			if (compare_event (hotplug_event, loop_event)) {
+				HAL_DEBUG (("event %s dependant on %s", hotplug_event->sysfs.sysfs_path, loop_event->sysfs.sysfs_path));
+				return TRUE;
+			}
+		}
+		return FALSE;
+
+	default:
+		return FALSE;
+	}
+}
+
+
 void 
 hotplug_event_process_queue (void)
 {
 	HotplugEvent *hotplug_event;
+	GList *lp, *lp2;
 
-        while (hotplug_events_in_progress != NULL ||
-		(hotplug_event_queue != NULL &&
-		 !g_queue_is_empty (hotplug_event_queue))) {
-
-		/* do not process events if some other event is in progress 
-		 *
-		 * TODO: optimize so we can do add events in parallel by inspecting the
-		 *       wait_for_sysfs_path parameter and hotplug_events_in_progress list
-		 */
-		if (hotplug_events_in_progress != NULL && g_slist_length (hotplug_events_in_progress) > 0)
-			goto out;
-
-		hotplug_event = g_queue_pop_head (hotplug_event_queue);
-		if (hotplug_event == NULL)
-			goto out;
+	if (G_UNLIKELY (hotplug_event_queue == NULL))
+		return;
 
-		hotplug_events_in_progress = g_slist_append (hotplug_events_in_progress, hotplug_event);
-		hotplug_event_begin (hotplug_event);
+	for (lp = hotplug_event_queue->head; lp; lp = g_list_next (lp) ) {
+		hotplug_event = lp->data;
+		HAL_INFO (("checking event %s", hotplug_event->sysfs.sysfs_path));
+		if (!compare_events (hotplug_event, hotplug_event_queue->head)
+		 && !compare_events (hotplug_event, hotplug_events_in_progress)) {
+			lp2 = lp->prev;
+			g_queue_unlink(hotplug_event_queue, lp);
+			hotplug_events_in_progress = g_list_concat (hotplug_events_in_progress, lp);
+			hotplug_event_begin (hotplug_event);
+			lp = lp2;
+		} else {
+			HAL_DEBUG (("event held back: %s", hotplug_event->sysfs.sysfs_path));
+		}
 	}
+	HAL_DEBUG (("events queued = %d, events in progress = %d", hotplug_event_queue->length, g_list_length (hotplug_events_in_progress)));
+
 
 	hotplug_queue_now_empty ();
-out:
-        ;
 }
 
 gboolean