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

From: Matthew Fleming <mdf356_at_gmail.com>
Date: Mon, 1 Nov 2010 13:07:29 -0700
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)
> _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;
>
> _______________________________________________
> 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"
>
Received on Mon Nov 01 2010 - 19:07:30 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:40:08 UTC