[RFC] Outline of USB process integration in the kernel taskqueue system

Hi!

I've wrapped up an outline patch for what needs to be done to integrate the 
USB process framework into the kernel taskqueue system in a more direct way 
that to wrap it.

The limitation of the existing taskqueue system is that it only guarantees 
execution at a given priority level. USB requires more. USB also requires a 
guarantee that the last task queued task also gets executed last. This is for 
example so that a deferred USB detach event does not happen before any pending 
deferred I/O for example in case of multiple occurring events.

Mostly this new feature is targeted for GPIO-alike system using slow busses 
like the USB. Typical use case:

2 tasks to program GPIO on.
2 tasks to program GPIO off.

Example:

a) taskqueue_enqueue_odd(&sc->sc_taskqueue, &sc->sc_task_on[0], &sc-
>sc_task_on[1]);


b) taskqueue_enqueue_odd(&sc->sc_taskqueue, &sc->sc_task_off[0], &sc-
>sc_task_off[1]);


No matter how the call ordering of code-line a) and b), we are always 
guaranteed that the last queued state "on" or "off" is reached before the head 
of the taskqueue empties.


In lack of a better name, the new function was called taskqueue_enqueue_odd 
[some people obviously think that USB processes are odd, but not taskqueues 
:-)]

Manpage:

.Ft int
.Fn taskqueue_enqueue_odd "struct taskqueue *queue" "struct task *t0" "struct 
task *t1"

..

The function
.Fn taskqueue_enqueue_odd
should be used if it is important that the last queued task is also
executed last in the task queue at the given priority level. This
function requires two valid task pointers. Depending on which of the
tasks passed are queued at the calling moment, the last queued task of
the two will get dequeued and put last in the task queue, while not
touching the first queued task. If no tasks are queued at the calling
moment, this function behaves like
.Fn taskqueue_enqueue .
This function returns zero if the first task was queued last, one if
the second task was queued last.

Preliminary patch - see e-mail attachment.

Comments are welcome!

--HPS

More docs: Also see talk about the new USB stack in FreeBSD on Youtube.

=== share/man/man9/taskqueue.9
==================================================================
--- share/man/man9/taskqueue.9	(revision 214211)
+++ share/man/man9/taskqueue.9	(local)
_at__at_ -46,11 +46,15 _at__at_
 typedef void (*taskqueue_enqueue_fn)(void *context);
 
 struct task {
-	STAILQ_ENTRY(task)	ta_link;	/* link for queue */
-	u_short			ta_pending;	/* count times queued */
-	u_short			ta_priority;	/* priority of task in queue */
-	task_fn_t		ta_func;	/* task handler */
-	void			*ta_context;	/* argument for handler */
+	TAILQ_ENTRY(task) ta_link;	/* link for queue */
+#define	TASKQUEUE_SEQUENCE_MAX	255
+	u_char	ta_sequence;		/* sequence number */
+#define	TASKQUEUE_PENDING_MAX	255
+	u_char	ta_pending;		/* count times queued */
+#define	TASKQUEUE_PRIORITY_MAX	65535U
+	u_short	ta_priority;		/* priority of task in queue */
+	task_fn_t *ta_func;		/* task handler */
+	void	*ta_context;		/* argument for handler */
 };
 .Ed
 .Ft struct taskqueue *
_at__at_ -62,6 +66,8 _at__at_
 .Ft int
 .Fn taskqueue_enqueue "struct taskqueue *queue" "struct task *task"
 .Ft int
+.Fn taskqueue_enqueue_odd "struct taskqueue *queue" "struct task *t0" "struct task *t1"
+.Ft int
 .Fn taskqueue_enqueue_fast "struct taskqueue *queue" "struct task *task"
 .Ft void
 .Fn taskqueue_drain "struct taskqueue *queue" "struct task *task"
_at__at_ -134,6 +140,19 _at__at_
 if the queue is being freed.
 .Pp
 The function
+.Fn taskqueue_enqueue_odd
+should be used if it is important that the last queued task is also
+executed last in the task queue at the given priority level. This
+function requires two valid task pointers. Depending on which of the
+tasks passed are queued at the calling moment, the last queued task of
+the two will get dequeued and put last in the task queue, while not
+touching the first queued task. If no tasks are queued at the calling
+moment, this function behaves like
+.Fn taskqueue_enqueue .
+This function returns zero if the first task was queued last, one if
+the second task was queued last.
+.Pp
+The function
 .Fn taskqueue_enqueue_fast
 should be used in place of
 .Fn taskqueue_enqueue
=== sys/sys/_task.h
==================================================================
--- sys/sys/_task.h	(revision 214433)
+++ sys/sys/_task.h	(local)
_at__at_ -44,9 +44,13 _at__at_
 typedef void task_fn_t(void *context, int pending);
 
 struct task {
-	STAILQ_ENTRY(task) ta_link;	/* (q) link for queue */
-	u_short	ta_pending;		/* (q) count times queued */
-	u_short	ta_priority;		/* (c) Priority */
+	TAILQ_ENTRY(task) ta_link;	/* (q) link for queue */
+#define	TASKQUEUE_SEQUENCE_MAX	255U
+	u_char	ta_sequence;		/* (q) sequence number */
+#define	TASKQUEUE_PENDING_MAX	255U
+	u_char	ta_pending;		/* (q) count times queued */
+#define	TASKQUEUE_PRIORITY_MAX	65535U
+	u_short	ta_priority;		/* (c) priority of task in queue */
 	task_fn_t *ta_func;		/* (c) task handler */
 	void	*ta_context;		/* (c) argument for handler */
 };
=== sys/sys/taskqueue.h
==================================================================
--- sys/sys/taskqueue.h	(revision 214433)
+++ sys/sys/taskqueue.h	(local)
_at__at_ -54,6 +54,7 _at__at_
 int	taskqueue_start_threads(struct taskqueue **tqp, int count, int pri,
 				const char *name, ...) __printflike(4, 5);
 int	taskqueue_enqueue(struct taskqueue *queue, struct task *task);
+int	taskqueue_enqueue_odd(struct taskqueue *queue, struct task *t0, struct task *t1);
 void	taskqueue_drain(struct taskqueue *queue, struct task *task);
 void	taskqueue_free(struct taskqueue *queue);
 void	taskqueue_run(struct taskqueue *queue);
_at__at_ -71,6 +72,7 _at__at_
  * Initialise a task structure.
  */
 #define TASK_INIT(task, priority, func, context) do {	\
+	(task)->ta_link.tqe_prev = NULL;		\
 	(task)->ta_pending = 0;				\
 	(task)->ta_priority = (priority);		\
 	(task)->ta_func = (func);			\
=== sys/kern/subr_taskqueue.c
==================================================================
--- sys/kern/subr_taskqueue.c	(revision 214433)
+++ sys/kern/subr_taskqueue.c	(local)
_at__at_ -52,7 +52,7 _at__at_
 };
 
 struct taskqueue {
-	STAILQ_HEAD(, task)	tq_queue;
+	TAILQ_HEAD(task_head, task)	tq_queue;
 	const char		*tq_name;
 	taskqueue_enqueue_fn	tq_enqueue;
 	void			*tq_context;
_at__at_ -62,12 +62,15 _at__at_
 	int			tq_tcount;
 	int			tq_spin;
 	int			tq_flags;
+	u_char			tq_sequence;
 };
 
 #define	TQ_FLAGS_ACTIVE		(1 << 0)
 #define	TQ_FLAGS_BLOCKED	(1 << 1)
 #define	TQ_FLAGS_PENDING	(1 << 2)
 
+static void taskqueue_enqueue_locked(struct taskqueue *, struct task *);
+
 static __inline void
 TQ_LOCK(struct taskqueue *tq)
 {
_at__at_ -106,7 +109,7 _at__at_
 	if (!queue)
 		return NULL;
 
-	STAILQ_INIT(&queue->tq_queue);
+	TAILQ_INIT(&queue->tq_queue);
 	TAILQ_INIT(&queue->tq_active);
 	queue->tq_name = name;
 	queue->tq_enqueue = enqueue;
_at__at_ -155,48 +158,132 _at__at_
 int
 taskqueue_enqueue(struct taskqueue *queue, struct task *task)
 {
-	struct task *ins;
-	struct task *prev;
-
 	TQ_LOCK(queue);
 
 	/*
 	 * Count multiple enqueues.
 	 */
 	if (task->ta_pending) {
-		task->ta_pending++;
+		if (task->ta_pending != TASKQUEUE_PENDING_MAX)
+			task->ta_pending++;
 		TQ_UNLOCK(queue);
-		return 0;
+		return (0);
 	}
 
+	KASSERT(task->ta_link.tqe_prev == NULL, ("Task already queued?"));
+
+	/* Insert task in queue */
+
+	taskqueue_enqueue_locked(queue, task);
+
+	TQ_UNLOCK(queue);
+
+	return (0);
+}
+
+/* Enqueue task ordered and dualed */
+
+int
+taskqueue_enqueue_odd(struct taskqueue *queue, struct task *t0, struct task *t1)
+{
+	struct task *tx;
+	uint8_t t;
+	uint8_t d;
+
+	TQ_LOCK(queue);
+
 	/*
+	 * Compute a number based on which of the two tasks passed as
+	 * arguments to this function are queued.
+	 */
+	t = 0;
+	if (t0->ta_link.tqe_prev != NULL)
+		t |= 1;
+	if (t1->ta_link.tqe_prev != NULL)
+		t |= 2;
+
+	if (t == 0) {
+		/*
+		 * No entries are queued. Queue task "t0" last and use
+		 * the existing sequence number.
+		 */
+		tx = t0;
+	} else if (t == 1) {
+		/*
+		 * Check if we need to increment the sequence number.
+		 */
+		if (t0->ta_sequence == queue->tq_sequence)
+			queue->tq_sequence++;
+
+		tx = t1;
+	} else if (t == 2) {
+		/*
+		 * Check if we need to increment the sequence number.
+		 */
+		if (t1->ta_sequence == queue->tq_sequence)
+			queue->tq_sequence++;
+
+		tx = t0;
+	} else {
+		/*
+		 * Both tasks are queued. Re-queue the task closest to
+		 * the end which is computed by looking at the
+		 * sequence number.
+		 */
+		d = (t1->ta_sequence - t0->ta_sequence);
+
+		/* Check sign after subtraction */
+		if (d & 0x80)
+			tx = t0;
+		else
+			tx = t1;
+
+		TAILQ_REMOVE(&queue->tq_queue, tx, ta_link);
+	}
+
+	/* Insert task in queue */
+
+	taskqueue_enqueue_locked(queue, tx);
+
+	TQ_UNLOCK(queue);
+
+	if (tx == t1)
+		return (1);
+
+	return (0);
+}
+
+static void
+taskqueue_enqueue_locked(struct taskqueue *queue, struct task *task)
+{
+	struct task *ins;
+	struct task *prev;
+
+	/*
 	 * Optimise the case when all tasks have the same priority.
 	 */
-	prev = STAILQ_LAST(&queue->tq_queue, task, ta_link);
+	prev = TAILQ_LAST(&queue->tq_queue, task_head);
 	if (!prev || prev->ta_priority >= task->ta_priority) {
-		STAILQ_INSERT_TAIL(&queue->tq_queue, task, ta_link);
+		TAILQ_INSERT_TAIL(&queue->tq_queue, task, ta_link);
 	} else {
 		prev = NULL;
-		for (ins = STAILQ_FIRST(&queue->tq_queue); ins;
-		     prev = ins, ins = STAILQ_NEXT(ins, ta_link))
+		for (ins = TAILQ_FIRST(&queue->tq_queue); ins;
+		     prev = ins, ins = TAILQ_NEXT(ins, ta_link))
 			if (ins->ta_priority < task->ta_priority)
 				break;
 
 		if (prev)
-			STAILQ_INSERT_AFTER(&queue->tq_queue, prev, task, ta_link);
+			TAILQ_INSERT_AFTER(&queue->tq_queue, prev, task, ta_link);
 		else
-			STAILQ_INSERT_HEAD(&queue->tq_queue, task, ta_link);
+			TAILQ_INSERT_HEAD(&queue->tq_queue, task, ta_link);
 	}
 
+	task->ta_sequence = queue->tq_sequence;
 	task->ta_pending = 1;
 	if ((queue->tq_flags & TQ_FLAGS_BLOCKED) == 0)
 		queue->tq_enqueue(queue->tq_context);
 	else
 		queue->tq_flags |= TQ_FLAGS_PENDING;
-
-	TQ_UNLOCK(queue);
-
-	return 0;
 }
 
 void
_at__at_ -232,13 +319,14 _at__at_
 	tb.tb_running = NULL;
 	TAILQ_INSERT_TAIL(&queue->tq_active, &tb, tb_link);
 
-	while (STAILQ_FIRST(&queue->tq_queue)) {
+	while ((task = TAILQ_FIRST(&queue->tq_queue)) != NULL) {
 		/*
-		 * Carefully remove the first task from the queue and
-		 * zero its pending count.
+		 * Carefully remove the first task from the queue,
+		 * clear the previous next pointer and zero its
+		 * pending count.
 		 */
-		task = STAILQ_FIRST(&queue->tq_queue);
-		STAILQ_REMOVE_HEAD(&queue->tq_queue, ta_link);
+		TAILQ_REMOVE(&queue->tq_queue, task, ta_link);
+		task->ta_link.tqe_prev = NULL;
 		pending = task->ta_pending;
 		task->ta_pending = 0;
 		tb.tb_running = task;