From: Tejun Heo <tj@kernel.org>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Ming Lei <ming.lei@canonical.com>,
Alex Riesen <raa.lkml@gmail.com>,
Alan Stern <stern@rowland.harvard.edu>,
Jens Axboe <axboe@kernel.dk>,
USB list <linux-usb@vger.kernel.org>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Arjan van de Ven <arjan@linux.intel.com>
Subject: Re: [PATCH] async: fix __lowest_in_progress()
Date: Thu, 17 Jan 2013 10:50:53 -0800 [thread overview]
Message-ID: <20130117185053.GB16568@mtj.dyndns.org> (raw)
In-Reply-To: <CA+55aFxfheczjP22pESE7zXS1hnK3=mOgcGjMHDeoQ2W4D0MDw@mail.gmail.com>
Hello,
On Thu, Jan 17, 2013 at 10:16:50AM -0800, Linus Torvalds wrote:
> Tejun, mind explaining this one a bit more to me?
>
> If ordering matters, and we have a running queue and a pending queue,
> how could the pending queue *ever* be lower than the running one?
So, before being converted to workqueue, async spooled up its own
workers and each worker would lock and move the first pending item to
the executing list and everything was in order.
The conversion to workqueue was done by adding work_struct to each
async_entry and async just schedules the work item. The queueing and
dispatching of such work items are still in order but now each worker
thread is associated with a specific async_entry and move that
specific async_entry to the executing list. So, depending on which
worker reaches that point earlier, which is completely
non-deterministic, we may end up moving an async_entry with larger
cookie before one with smaller one.
> That implies that something was taken off the pending queue and put on
> the running queue out of order, right?
>
> And that in turn implies that there isn't much of a "lowest" ordering
> at all, so how could anybody even care about what lowest is? It seems
> to be a meaningless measure.
The execution is still lowest first as workqueue would dispatch
workers in queued order. It just is that they can reach the
synchronization point at their own differing paces.
> So with that in mind, I don't see what semantics the first part of the
> patch fixes. Can you explain more?
The problem with the code is that it's keeping a global pending list
and domain-specific running lists. I don't know why it developed like
this but even before workqueue conversion the code was weird.
* It has sorted per-domain running list, so looking at the first item
is easy.
* It has sorted global pennding list, and looking for first item in a
domain involves scanning it.
Global syncing ends up scanning all per-domain running lists and
domain syncing ends up scanning global pending list, when all we need
is each async item to be queued on two lists - global and per-domain
in-flight lists - and stay there until done.
The posted patch is minimal fix while keeping the basic operation the
same so that it doesn't disturb -stable too much. I'll prep a patch
to redo synchronization for 3.9.
Thanks.
--
tejun
next prev parent reply other threads:[~2013-01-17 18:51 UTC|newest]
Thread overview: 94+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-01-11 21:04 USB device cannot be reconnected and khubd "blocked for more than 120 seconds" Alex Riesen
2013-01-12 7:48 ` Alex Riesen
2013-01-12 9:18 ` Lan Tianyu
2013-01-12 17:37 ` Alan Stern
2013-01-12 19:39 ` Alex Riesen
2013-01-12 20:33 ` Alex Riesen
2013-01-12 22:52 ` Alan Stern
2013-01-13 12:09 ` Alex Riesen
2013-01-13 16:56 ` Alan Stern
2013-01-13 17:42 ` Alex Riesen
2013-01-13 19:16 ` Oliver Neukum
2013-01-14 2:39 ` Alan Stern
2013-01-14 16:43 ` Alex Riesen
2013-01-14 3:47 ` Ming Lei
2013-01-14 7:15 ` Ming Lei
2013-01-14 17:30 ` Linus Torvalds
2013-01-14 18:04 ` Alan Stern
2013-01-14 18:34 ` Linus Torvalds
2013-01-15 1:53 ` Ming Lei
2013-01-15 6:23 ` Ming Lei
2013-01-15 17:36 ` Linus Torvalds
2013-01-15 18:18 ` Linus Torvalds
2013-01-15 23:17 ` Tejun Heo
2013-01-15 18:20 ` Alan Stern
2013-01-15 18:39 ` Tejun Heo
2013-01-15 18:32 ` Tejun Heo
2013-01-15 20:18 ` Linus Torvalds
2013-01-15 23:50 ` Tejun Heo
2013-01-16 0:25 ` Arjan van de Ven
2013-01-16 0:35 ` Tejun Heo
2013-01-16 4:01 ` Alan Stern
2013-01-16 16:12 ` Tejun Heo
2013-01-16 17:01 ` Alan Stern
2013-01-16 17:37 ` Tejun Heo
2013-01-16 17:51 ` Alan Stern
2013-01-16 0:36 ` Linus Torvalds
2013-01-16 0:40 ` Linus Torvalds
2013-01-16 2:52 ` [PATCH] module, async: async_synchronize_full() on module init iff async is used Tejun Heo
2013-01-16 3:00 ` Linus Torvalds
2013-01-16 3:25 ` Tejun Heo
2013-01-16 3:37 ` Linus Torvalds
2013-01-16 16:22 ` Arjan van de Ven
2013-01-16 16:48 ` Tejun Heo
2013-01-16 17:03 ` Arjan van de Ven
2013-01-16 17:06 ` Linus Torvalds
2013-01-16 21:30 ` [PATCH 1/2] init, block: try to load default elevator module early during boot Tejun Heo
2013-01-17 18:05 ` Linus Torvalds
2013-01-17 18:38 ` Tejun Heo
2013-01-17 18:46 ` Linus Torvalds
2013-01-17 18:59 ` Tejun Heo
2013-01-17 19:00 ` Linus Torvalds
2013-01-18 1:24 ` [PATCH 1/3] workqueue: set PF_WQ_WORKER on rescuers Tejun Heo
2013-01-18 1:25 ` [PATCH 2/3] workqueue, async: implement work/async_current_func() Tejun Heo
2013-01-18 2:47 ` Linus Torvalds
2013-01-18 2:59 ` Tejun Heo
2013-01-18 3:04 ` Tejun Heo
2013-01-18 3:18 ` Linus Torvalds
2013-01-18 3:47 ` Tejun Heo
2013-01-18 22:08 ` [PATCH 1/5] workqueue: set PF_WQ_WORKER on rescuers Tejun Heo
2013-01-18 22:10 ` [PATCH 2/5] workqueue: rename kernel/workqueue_sched.h to kernel/workqueue_internal.h Tejun Heo
2013-01-18 22:11 ` [PATCH 3/5] workqueue: move struct worker definition to workqueue_internal.h Tejun Heo
2013-01-18 22:11 ` [PATCH 4/5] workqueue: implement current_is_async() Tejun Heo
2013-01-18 22:12 ` [PATCH 5/5] async, kmod: warn on synchronous request_module() from async workers Tejun Heo
2022-06-23 5:25 ` Saravana Kannan
2013-01-18 1:27 ` [PATCH 3/3] " Tejun Heo
2013-01-23 0:53 ` [PATCH v2 1/2] init, block: try to load default elevator module early during boot Tejun Heo
2013-01-16 21:31 ` [PATCH 2/2] block: don't request module during elevator init Tejun Heo
2013-01-23 0:51 ` [PATCH v2 " Tejun Heo
2013-01-16 3:30 ` [PATCH] module, async: async_synchronize_full() on module init iff async is used Ming Lei
2013-01-16 4:24 ` Rusty Russell
2013-01-16 11:36 ` Alex Riesen
2013-08-12 7:04 ` [3.8-rc3 -> 3.8-rc4 regression] " Jonathan Nieder
2013-08-12 15:09 ` Tejun Heo
2013-11-26 21:29 ` Josh Hunt
2013-11-26 21:53 ` Linus Torvalds
2013-11-26 22:12 ` Josh Hunt
2013-11-26 22:29 ` Tejun Heo
2013-12-03 14:28 ` Josh Hunt
2013-12-03 15:19 ` Tejun Heo
2013-12-04 23:01 ` Josh Hunt
2013-12-04 23:12 ` Tejun Heo
2013-11-26 22:30 ` Linus Torvalds
2013-01-16 0:44 ` USB device cannot be reconnected and khubd "blocked for more than 120 seconds" Tejun Heo
2013-01-16 17:19 ` [PATCH] async: fix __lowest_in_progress() Tejun Heo
2013-01-17 18:16 ` Linus Torvalds
2013-01-17 18:50 ` Tejun Heo [this message]
2013-01-23 0:15 ` [PATCH v2] " Tejun Heo
2013-01-23 0:22 ` Linus Torvalds
2013-01-16 3:05 ` USB device cannot be reconnected and khubd "blocked for more than 120 seconds" Ming Lei
2013-01-16 4:14 ` Linus Torvalds
2013-01-14 8:22 ` Oliver Neukum
2013-01-14 8:40 ` Ming Lei
2013-01-12 19:56 ` Alex Riesen
-- strict thread matches above, loose matches on Subject: below --
2009-01-12 10:16 [PATCH] async: fix __lowest_in_progress() Arjan van de Ven
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20130117185053.GB16568@mtj.dyndns.org \
--to=tj@kernel.org \
--cc=arjan@linux.intel.com \
--cc=axboe@kernel.dk \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-usb@vger.kernel.org \
--cc=ming.lei@canonical.com \
--cc=raa.lkml@gmail.com \
--cc=stern@rowland.harvard.edu \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®