From owner-freebsd-current@FreeBSD.ORG Mon Nov 1 19:53:52 2010 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 346EA106566C; Mon, 1 Nov 2010 19:53:52 +0000 (UTC) (envelope-from hselasky@c2i.net) Received: from swip.net (mailfe06.swip.net [212.247.154.161]) by mx1.freebsd.org (Postfix) with ESMTP id E0B038FC19; Mon, 1 Nov 2010 19:53:50 +0000 (UTC) X-Cloudmark-Score: 0.000000 [] X-Cloudmark-Analysis: v=1.1 cv=5UXFHLfkiY5XrCDma5uYm2T9fyMGz6t0cyN4hLfZsqg= c=1 sm=1 a=ZJKxzO8xKrIA:10 a=CL8lFSKtTFcA:10 a=i9M/sDlu2rpZ9XS819oYzg==:17 a=oRQRuTlL4tF4YFdG0KEA:9 a=ObUINUouHsCKj4En9vAA:7 a=Fy61cc9Geugf3KA_8aKYKOD7WEoA:4 a=CjuIK1q_8ugA:10 a=Bv938iqYfvFtlDwxFssA:9 a=uM761qN_FhgtPHaD6xMA:7 a=J3rm2JEZ12vxksrYZHk5wOmsnpoA:4 a=2oojFnQ6c6Waurg1:21 a=ZqU7GHg2O_BuwJCW:21 a=i9M/sDlu2rpZ9XS819oYzg==:117 Received: from [188.126.198.129] (account mc467741@c2i.net HELO laptop002.hselasky.homeunix.org) by mailfe06.swip.net (CommuniGate Pro SMTP 5.2.19) with ESMTPA id 42649858; Mon, 01 Nov 2010 20:53:48 +0100 From: Hans Petter Selasky To: Andrew Thompson Date: Mon, 1 Nov 2010 20:54:59 +0100 User-Agent: KMail/1.13.5 (FreeBSD/8.1-STABLE; KDE/4.4.5; amd64; ; ) X-Face: +~\`s("[*|O,="7?X@L.elg*F"OA\I/3%^p8g?ab%RN'(; _IjlA: hGE..Ew, XAQ*o#\/M~SC=S1-f9{EzRfT'|Hhll5Q]ha5Bt-s|oTlKMusi:1e[wJl}kd}GR Z0adGx-x_0zGbZj'e(Y[(UNle~)8CQWXW@:DX+9)_YlB[tIccCPN$7/L' MIME-Version: 1.0 Content-Type: Multipart/Mixed; boundary="Boundary-00=_TsxzMdRyDrUyIHv" Message-Id: <201011012054.59551.hselasky@c2i.net> Cc: freebsd-arch@freebsd.org, freebsd-usb@freebsd.org, freebsd-current@freebsd.org, Weongyo Jeong Subject: [RFC] Outline of USB process integration in the kernel taskqueue system X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 01 Nov 2010 19:53:52 -0000 --Boundary-00=_TsxzMdRyDrUyIHv Content-Type: Text/Plain; charset="us-ascii" Content-Transfer-Encoding: 7bit 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. --Boundary-00=_TsxzMdRyDrUyIHv Content-Type: text/plain; charset="us-ascii"; name="hps_taskqueue_patch_v001.txt" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="hps_taskqueue_patch_v001.txt" === 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; --Boundary-00=_TsxzMdRyDrUyIHv--