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