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)
@@ -46,11 +46,15 @@
 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 *
@@ -62,6 +66,8 @@
 .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"
@@ -134,6 +140,19 @@
 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)
@@ -44,9 +44,13 @@
 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)
@@ -54,6 +54,7 @@
 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);
@@ -71,6 +72,7 @@
  * 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)
@@ -52,7 +52,7 @@
 };
 
 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;
@@ -62,12 +62,15 @@
        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)
 {
@@ -106,7 +109,7 @@
        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;
@@ -155,48 +158,132 @@
 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
@@ -232,13 +319,14 @@
        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;
_______________________________________________
freebsd-usb@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-usb
To unsubscribe, send any mail to "freebsd-usb-unsubscr...@freebsd.org"

Reply via email to