login
Search
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: 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 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.
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, _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
No, USB does not need a task priority field, but a sequence field associated with the task and task queue head to figure out which task was queued first No, not completely. See comment above. I also need information about which task was queued first, or else I have to keep this information separately, which again, confuse people. The more layers the more confusion? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I don't follow why keeping the information about which task was queued first privately rather than having taskqueue(9) maintain it is confusing. So far, USB seems to be the only taskqueue consumer which needs this information, so it makes a lot more sense to me for it to be USB private. To my mind, there's primary operations, and secondary ones. A secondary operation can be built from the primary ones. It reads to me that, if there was a taskqueue_cancel(9) (and there is in Jeff's OFED branch) then you could build the functionality you want (and maybe you don't need cancel, even). While there is sometimes an argument for making secondary operations available in a library, in this case you need extra data which most other taskqueue consumers do not. That would break the KBI. That is another argument in favor of keeping the implementation private to USB. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Probably I can check which task is pending when I queue them and store that in a separate variable. Still I need a way to remove a task from the queue, which That is right, if there is a way to remove a task from a queue without The only reason I want to break the KBI is because it is slow to remove a task from the taskqueue using STAILQ's when you don't know the previous task- element in the queue. --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
My sense is that I certainly agree. The fact that you can't think of a good name for the operation certainly indicates that it is not generic. Unfortunately, I don't really understand the problem that is being solved. I do agree that due to the 'pending' feature and automatic-coalescing of task enqueue operations, taskqueues do not lend themselves to a barrier operation. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Is there a link to this branch? I would certainly have a look at his work and re-base my patch. --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
It's on svn.freebsd.org: http://svn.freebsd.org/viewvc/base/projects/ofed/head/sys/kern/subr_taskqueue.c?view=log http://svn.freebsd.org/viewvc/base?view=revision&revision=209422 For the purpose of speed, I'm not opposed to breaking the KBI by using a doubly-linked TAILQ, but I don't think the difference will matter all that often (perhaps I'm wrong and some taskqueues have dozens of pending tasks?) Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hi, In my case we are talking about 10-15 tasks at maximum. But still (10*9) / 2 = 45 iterations is much more than 2 steps to do the unlink. Anyway. I will have a look at your work and suggest a new patch for my needs. --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
At first look I see that I need a non-blocking version of: taskqueue_cancel( At the point in the code where these functions are called I cannot block. Is this impossible to implement? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
It depends on whether the queue uses a MTX_SPIN or MTX_DEF. It is not possible to determine whether a task is running without taking the taskqueue lock. And it is certainly impossible to dequeue a task without the lock that was used to enqueue it. However, a variant that dequeued if the task was still pending, and returned failure otherwise (rather than sleeping) is definitely possible. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I think that if a task is currently executing, then there should be a drain method for that. I.E. two methods: One to stop and one to cancel/drain. Can you implement this? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I agree, this would also be consistent with the callout_*() API if you had both "stop()" and "drain()" methods. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Here's my proposed code. Note that this builds but is not yet tested. Implement a taskqueue_cancel(9), to cancel a task from a queue. Requested by: hps Original code: jeff MFC after: 1 week http://people.freebsd.org/~mdf/bsd-taskqueue-cancel.diff Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
For FreeBSD taskqueue_cancel() should return EBUSY, not -EBUSY. However, I would prefer that it follow the semantics of callout_stop() and return true if it stopped the task and false otherwise. The Linux wrapper for taskqueue_cancel() can convert the return value. I'm not sure I like reusing the memory allocation flags (M_NOWAIT / M_WAITOK) for this blocking flag. In the case of callout(9) we just have two functions that pass an internal boolean to the real routine (callout_stop() and callout_drain() are wrappers for _callout_stop_safe()). It is a bit unfortunate that taskqueue_drain() already exists and has different semantics than callout_drain(). It would have been nice to have the two APIs mirror each other instead. Hmm, I wonder if the blocking behavior cannot safely be provided by just doing: if (!taskqueue_cancel(queue, task, M_NOWAIT) taskqueue_drain(queue, task); If that works ok (I think it does), I would rather have taskqueue_cancel() always be non-blocking. Even though there is a "race" where the task could be rescheduled by another thread in between cancel and drain, the race still exists since if the task could be scheduled between the two, it could also be scheduled just before the call to taskqueue_cancel() (in which case a taskqueue_cancel(queue, task, M_WAITOK) would have blocked to wait for it matching the taskqueue_drain() above). The caller still always has to provide synchronization for preventing a task's execution outright via their own locking. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I used -EBUSY since positive return values reflect the old pending count. ta_pending was zero'd, and I think needs to be to keep the task sane, because all of taskqueue(9) assumes a non-zero ta_pending means the task is queued. I don't know that the caller often needs to know the old value of ta_pending, but it seems simpler to return that as the return value and use -EBUSY than to use an optional pointer to a place to store the old ta_pending just so we can keep the error return positive. Note that phk (IIRC) suggested using -error in the returns for sbuf_drain to indicate the difference between success (> 0 bytes drained) and an error, so FreeBSD now has precedent. I'm not entirely sure that's a good thing, since I am not generally fond of Linux's use of -error, but for some cases it is convenient. But, I'll do this one either way, just let me know if the above hasn't This seems reasonable and correct. I will add a note to the manpage about this. Thanks, _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hmm, I hadn't considered if callers would want to know the pending count of In that case, would you be fine with dropping the blocking functionality from taskqueue_cancel() completely and requiring code that wants the blocking semantics to use a cancel followed by a drain? -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
New patch is at http://people.freebsd.org/~mdf/0001-Implement-taskqueue_cancel-9-to-cancel-a-task-from... I'll try to set up something to test it today too. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I think the:
+ if (!task_is_running(queue, task)) {
check needs to be omitted. Else you block the possibility of enqueue and
cancel a task while it is actually executing/running ??
--HPS
_______________________________________________
freebsd-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Huh? If the task is currently running, there's nothing to do except return failure. Task running means it can't be canceled, because... it's running. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
If it is running, it is dequeued from the the taskqueue, right? And while it is running it can be queued again, which your initial code didn't handle? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
True, but no taskqueue(9) code can handle that. Only the caller can prevent a task from becoming enqueued again. The same issue exists with taskqueue_drain(). BTW, I planned to commit the patch I sent today after testing, assuming jhb@ has no more issues. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I find that strange, because that means if I queue a task again while it is running, then I doesn't get run? Are you really sure? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
If a task is currently running when enqueued, the task struct will be re-enqueued to the taskqueue. When that task comes up as the head of the queue, it will be run again. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Right, and the taskqueue_cancel has to cancel in that state to, but it doesn't because it only checks pending if !running() :-) ?? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
You can't close that race in taskqueue_cancel(). You have to manage that race yourself in your task handler. For the callout(9) API we are only able to close that race if you use callout_init_mtx() so that the code managing the callout wheel can make use of your lock to resolve the races. If you use callout_init() you have to explicitly manage these races in your callout handler. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hi,
I think you are getting me wrong! In the initial "0001-Implement-
taskqueue_cancel-9-to-cancel-a-task-from-a.patch" you have the following code-
chunk:
+int
+taskqueue_cancel(struct taskqueue *queue, struct task *task)
+{
+ int rc;
+
+ TQ_LOCK(queue);
+ if (!task_is_running(queue, task)) {
+ if ((rc = task->ta_pending) > 0)
+ STAILQ_REMOVE(&queue->tq_queue, task, task, ta_link);
+ task->ta_pending = 0;
+ } else
+ rc = -EBUSY;
+ TQ_UNLOCK(queue);
+ return (rc);
+}
This code should be written like this, having the if (!task_is_running())
after checking the ta_pending variable.
+int
+taskqueue_cancel(struct taskqueue *queue, struct task *task)
+{
+ int rc;
+
+ TQ_LOCK(queue);
+ if ((rc = task->ta_pending) > 0) {
+ STAILQ_REMOVE(&queue->tq_queue, task, task, ta_link);
+ task->ta_pending = 0;
+ }
+ if (!task_is_running(queue, task))
+ rc = -EBUSY;
+ TQ_UNLOCK(queue);
+ return (rc);
+}
Or completely skip the !task_is_running() check. Else you are opening up a
race in this function! Do I need to explain that more? Isn't it obvious?
--HPS
_______________________________________________
freebsd-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I think you're misunderstanding the existing taskqueue(9) implementation. As long as TQ_LOCK is held, the state of ta->ta_pending cannot change, nor can the set of running tasks. So the order of checks is irrelevant. As John said, the taskqueue(9) implementation cannot protect consumers of it from re-queueing a task; that kind of serialization needs to happen at a higher level. taskqueue(9) is not quite like callout(9); the taskqueue(9) implementation drops all locks before calling the task's callback function. So once the task is running, taskqueue(9) can do nothing about it until the task stops running. This is why Jeff's implementation of taskqueue_cancel(9) slept if the task was running, and why mine returns an error code. The only way to know for sure that a task is "about" to run is to ask taskqueue(9), because there's a window where the TQ_LOCK is dropped before the callback is entered. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hi,
I agree that the order of checks is not important. That is not the problem.
Cut & paste from suggested taskqueue patch from Fleming:
What happens in this case if ta_pending > 0. Are you saying this is not
Agreed, but that is not what I'm pointing at. I'm pointing at what happens if
you re-queue a task and then cancel while it is actually running. Will the
And if you re-queue and cancel in this window, shouldn't this also be handled
like in the other cases?
Cut & paste from kern/subr_taskqueue.c:
task->ta_pending = 0;
tb.tb_running = task;
TQ_UNLOCK(queue);
If a concurrent thread at exactly this point in time calls taskqueue_enqueue()
on this task, then we re-add the task to the "queue->tq_queue". So far we
agree. Imagine now that for some reason a following call to taskqueue_cancel()
on this task at same point in time. Now, shouldn't taskqueue_cancel() also
remove the task from the "queue->tq_queue" in this case aswell? Because in
your implementation you only remove the task if we are not running, and that
is not true when we are at exactly this point in time.
task->ta_func(task->ta_context, pending);
TQ_LOCK(queue);
tb.tb_running = NULL;
wakeup(task);
Another issue I noticed is that the ta_pending counter should have a wrap
protector.
--HPS
_______________________________________________
freebsd-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Ah! I see what you mean. I'm not quite sure what the best thing to do here is; I agree it would be nice if taskqueue_cancel(9) dequeued the task, but I believe it also needs to indicate that the task is currently running. I guess the best thing would be to return the old pending count by reference parameter, and 0 or EBUSY to also indicate if there is a task currently running. Adding jhb@ to this mail since he has good thoughts on interfacing. Thanks, _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I agree we should always dequeue when possible. I think it should return -EBUSY in that case. That way code that uses 'cancel' followed by a conditional 'drain' to implement a blocking 'cancel' will DTRT. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Do we not also want the old ta_pending to be returned? In the case where a task is pending and is also currently running (admittedly a narrow window), how would we do this? This is why I suggested returning the old ta_pending by reference. This also allows callers who don't care about the old pending to pass NULL and ignore it. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I would be fine with that then. I wonder if taskqueue_cancel() could then return a simple true/false. False if the task is running, and true otherwise? -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Sure, though since we don't really have a bool type in the kernel I'd still prefer to return an int with EBUSY meaning a task was running. Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
The only reason I would prefer the other sense (false if already running) is that is what callout_stop()'s return value is (true if it "stopped" the callout, false if it couldn't stop it)). However, returning EBUSY is ok. One difference is that callout_stop() returns false if the callout is not pending (i.e. not on softclock). Right now taskqueue_cancel() returns 0 in that case (ta_pending == 0), but that is probably fine as long as it is documented. If you wanted to return EINVAL instead, that would be fine, too. -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I think the symmetry with callout(9) can't go very far, mostly because callout generally takes a specified mtx before calling the callback, and taskqueue(9) does not. That means fundamentally that, when using a taskqueue(9) the consumer has much less knowledge of the exact state of a task. Thanks, _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
I'll commit this later today unless there are objections. http://people.freebsd.org/~mdf/0001-Add-a-taskqueue_cancel-9-to-cancel-a-pending-task-... Thanks, matthew _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hi, In the patch attached to this e-mail I included Matthew Fleming's patch aswell. 1) I renamed taskqueue_cancel() into taskqueue_stop(), hence that resembles the words of the callout and USB API's terminology for doing the same. 2) I turns out I need to have code in subr_taskqueue.c to be able to make the operations atomic. 3) I did not update the manpage in this patch. Will do that before a commit. 4) My patch implements separate state keeping in "struct task_pair", which avoids having to change any KPI's for now, like suggested by John Baldwin I think. 5) In my implementation I hard-coded the priority argument to zero, so that enqueuing is fast. Comments are welcome! --HPS
The patch looks almost you moved usb_process.c code into taskqueue(9) that I means it still follows that a entry which enqueued at last should be executed at last. It seems that at least it's not a general for taskqueue(9). In my humble opinion it looks a trick. I think it'd better to find a general solution to solve it though I used sx(9) lock in my patches. regards, Weongyo Jeong _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
It feels like this should be something you could manage with a state machine internal to USB rather than forcing that state into the taskqueue code itself. If you wanted a simple barrier task (where a barrier task is always queued at the tail of the list and all subsequent tasks are queued after the barrier task) then I would be fine with adding that. You could manage this without having to alter the task KBI by having the taskqueue maintain a separate pointer to the current "barrier" task and always enqueue entries after that task (the barrier would be NULL before a barrier is queued, and set to NULL when a barrier executes). I think this sort of semantic is a bit simpler and also used in other parts of the tree (e.g. in bio queues). -- John Baldwin _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Hi John, No, this is not possible without keeping my own queue, which I want to avoid. By state-machine you mean remembering the last state as a separate variable and checking that in the task-callback, right? Yes, I do that in addition to the new queuing mechanism. A task barrier does not solve my problem. The barrier in my case is always last in the queue. I need to pull out previously queued tasks and put them last. That is currently not supported. I do this because I don't want to have a FIFO signalling model, and a neither want the pure taskqueue, which only ensures execution, not order of execution when at the same priority. Another issue: Won't the barrier model lead to blocking the caller once the task in question is being issued the second time? _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
Any more comments on this matter or someone still doing review? --HPS _______________________________________________ freebsd-current@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
