On Thu 03-03-22 10:00:33, Byungchul Park wrote:
> On Mon, Feb 28, 2022 at 11:14:44AM +0100, Jan Kara wrote:
> > On Mon 28-02-22 18:28:26, Byungchul Park wrote:
> > > case 1. Code with an actual circular dependency, but not deadlock.
> > >
> > > A circular dependency can be broken by a rescue wakeup source e.g.
> > > timeout. It's not a deadlock. If it's okay that the contexts
> > > participating in the circular dependency and others waiting for the
> > > events in the circle are stuck until it gets broken. Otherwise, say,
> > > if it's not meant, then it's anyway problematic.
> > >
> > > 1-1. What if we judge this code is problematic?
> > > 1-2. What if we judge this code is good?
> > >
> > > case 2. Code with an actual circular dependency, and deadlock.
> > >
> > > There's no other wakeup source than those within the circular
> > > dependency. Literally deadlock. It's problematic and critical.
> > >
> > > 2-1. What if we judge this code is problematic?
> > > 2-2. What if we judge this code is good?
> > >
> > > case 3. Code with no actual circular dependency, and not deadlock.
> > >
> > > Must be good.
> > >
> > > 3-1. What if we judge this code is problematic?
> > > 3-2. What if we judge this code is good?
> > >
> > > ---
> > >
> > > I call only 3-1 "false positive" circular dependency. And you call 1-1
> > > and 3-1 "false positive" deadlock.
> > >
> > > I've been wondering if the kernel guys esp. Linus considers code with
> > > any circular dependency is problematic or not, even if it won't lead to
> > > a deadlock, say, case 1. Even though I designed Dept based on what I
> > > believe is right, of course, I'm willing to change the design according
> > > to the majority opinion.
> > >
> > > However, I would never allow case 1 if I were the owner of the kernel
> > > for better stability, even though the code works anyway okay for now.
> >
> > So yes, I call a report for the situation "There is circular dependency but
> > deadlock is not possible." a false positive. And that is because in my
> > opinion your definition of circular dependency includes schemes that are
> > useful and used in the kernel.
> >
> > Your example in case 1 is kind of borderline (I personally would consider
> > that bug as well) but there are other more valid schemes with multiple
> > wakeup sources like:
> >
> > We have a queue of work to do Q protected by lock L. Consumer process has
> > code like:
> >
> > while (1) {
> > lock L
> > prepare_to_wait(work_queued);
> > if (no work) {
> > unlock L
> > sleep
> > } else {
> > unlock L
> > do work
> > wake_up(work_done)
> > }
> > }
> >
> > AFAIU Dept will create dependency here that 'wakeup work_done' is after
> > 'wait for work_queued'. Producer has code like:
>
> First of all, thank you for this good example.
>
> > while (1) {
> > lock L
> > prepare_to_wait(work_done)
> > if (too much work queued) {
> > unlock L
> > sleep
> > } else {
> > queue work
> > unlock L
> > wake_up(work_queued)
> > }
> > }
> >
> > And Dept will create dependency here that 'wakeup work_queued' is after
> > 'wait for work_done'. And thus we have a trivial cycle in the dependencies
> > despite the code being perfectly valid and safe.
>
> Unfortunately, it's neither perfect nor safe without another wakeup
> source - rescue wakeup source.
>
> consumer producer
>
> lock L
> (too much work queued == true)
> unlock L
> --- preempted
> lock L
> unlock L
> do work
> lock L
> unlock L
> do work
> ...
> (no work == true)
> sleep
> --- scheduled in
> sleep
>
> This code leads a deadlock without another wakeup source, say, not safe.
So the scenario you describe above is indeed possible. But the trick is
that the wakeup from 'consumer' as is doing work will remove 'producer'
from the wait queue and change the 'producer' process state to
'TASK_RUNNING'. So when 'producer' calls sleep (in fact schedule()), the
scheduler will just treat this as another preemption point and the
'producer' will immediately or soon continue to run. So indeed we can think
of this as "another wakeup source" but the source is in the CPU scheduler
itself. This is the standard way how waitqueues are used in the kernel...
> Lastly, just for your information, I need to explain how Dept works a
> little more for you not to misunderstand Dept.
>
> Assuming the consumer and producer guarantee not to lead a deadlock like
> the following, Dept won't report it a problem:
>
> consumer producer
>
> sleep
> wakeup work_done
> queue work
> sleep
> wakeup work_queued
> do work
> sleep
> wakeup work_done
> queue work
> sleep
> wakeup work_queued
> do work
> sleep
> ... ...
>
> Dept does not consider all waits preceeding an event but only waits that
> might lead a deadlock. In this case, Dept works with each region
> independently.
>
> consumer producer
>
> sleep <- initiates region 1
> --- region 1 starts
> ... ...
> --- region 1 ends
> wakeup work_done
> ... ...
> queue work
> ... ...
> sleep <- initiates region 2
> --- region 2 starts
> ... ...
> --- region 2 ends
> wakeup work_queued
> ... ...
> do work
> ... ...
> sleep <- initiates region 3
> --- region 3 starts
> ... ...
> --- region 3 ends
> wakeup work_done
> ... ...
> queue work
> ... ...
> sleep <- initiates region 4
> --- region 4 starts
> ... ...
> --- region 4 ends
> wakeup work_queued
> ... ...
> do work
> ... ...
>
> That is, Dept does not build dependencies across different regions. So
> you don't have to worry about unreasonable false positives that much.
>
> Thoughts?
Thanks for explanation! And what exactly defines the 'regions'? When some
process goes to sleep on some waitqueue, this defines a start of a region
at the place where all the other processes are at that moment and wakeup of
the waitqueue is an end of the region?
Honza
--
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR
