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-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"
