[RFC] Outline of USB process integration in the kernel
taskqueue system
Matthew Fleming
mdf356 at gmail.com
Mon Nov 1 20:39:00 UTC 2010
On Mon, Nov 1, 2010 at 12:54 PM, Hans Petter Selasky <hselasky at c2i.net> wrote:
> 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
> :-)]
I'd like to make sure I understand the USB requirements.
(1) does USB need the task priority field? Many taskqueue(9) consumers do not.
(2) if there was a working taskqueue_remove(9) that removed the task
if pending or returned error if the task was currently running, would
that be sufficient to implement the required USB functionality?
(assuming that taskqueue_enqueue(9) put all tasks with equal priority
in order of queueing).
Thanks,
matthew
> 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-arch at freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-arch
> To unsubscribe, send any mail to "freebsd-arch-unsubscribe at freebsd.org"
>
More information about the freebsd-usb
mailing list