On Fri, Sep 28, 2007 at 06:47:14PM +0400, Oleg Nesterov wrote:
> On 09/27, Paul E. McKenney wrote:
> >
> > On Wed, Sep 26, 2007 at 07:13:51PM +0400, Oleg Nesterov wrote:
> > >
> > > Yes, yes, I see now. We really need this barriers, except I think
> > > rcu_try_flip_idle() can use wmb. However, I have a bit offtopic question,
> > >
> > > // rcu_try_flip_waitzero()
> > > if (A == 0) {
> > > mb();
> > > B == 0;
> > > }
> > >
> > > Do we really need the mb() in this case? How it is possible that STORE
> > > goes before LOAD? "Obviously", the LOAD should be completed first, no?
> >
> > Suppose that A was most recently stored by a CPU that shares a store
> > buffer with this CPU. Then it is possible that some other CPU sees
> > the store to B as happening before the store that "A==0" above is
> > loading from. This other CPU would naturally conclude that the store
> > to B must have happened before the load from A.
>
> Ah, I was confused by the comment,
>
> smp_mb(); /* Don't call for memory barriers before we see zero. */
> ^^^^^^^^^^^^^^^^^^
> So, in fact, we need this barrier to make sure that _other_ CPUs see these
> changes in order, thanks. Of course, _we_ already saw zero.
Fair point!
Perhaps: "Ensure that all CPUs see their rcu_mb_flag -after- the
rcu_flipctrs sum to zero" or some such?
> But in that particular case this doesn't matter, rcu_try_flip_waitzero()
> is the only function which reads the "non-local" per_cpu(rcu_flipctr), so
> it doesn't really need the barrier? (besides, it is always called under
> fliplock).
The final rcu_read_unlock() that zeroed the sum was -not- under fliplock,
so we cannot necessarily rely on locking to trivialize all of this.
> > In more detail, suppose that CPU 0 and 1 share a store buffer, and
> > that CPU 2 and 3 share a second store buffer. This happens naturally
> > if CPUs 0 and 1 are really just different hardware threads within a
> > single core.
> >
> > So, suppose the cacheline for A is initially owned by CPUs 2 and 3,
> > and that the cacheline for B is initially owned by CPUs 0 and 1.
> > Then consider the following sequence of events:
> >
> > o CPU 0 stores zero to A. This is a cache miss, so the new value
> > for A is placed in CPU 0's and 1's store buffer.
> >
> > o CPU 1 executes the above code, first loading A. It sees
> > the value of A==0 in the store buffer, and therefore
> > stores zero to B, which hits in the cache. (I am assuming
> > that we left out the mb() above).
> >
> > o CPU 2 loads from B, which misses the cache, and gets the
> > value that CPU 1 stored. Suppose it checks the value,
> > and based on this check, loads A. The old value of A might
> > still be in cache, which would lead CPU 2 to conclude that
> > the store to B by CPU 1 must have happened before the store
> > to A by CPU 0.
> >
> > Memory barriers would prevent this confusion.
>
> Thanks a lot!!! This fills another gap in my understanding.
Glad it helped! ;-)
> OK, the last (I promise :) off-topic question. When CPU 0 and 1 share a
> store buffer, the situation is simple, we can replace "CPU 0 stores" with
> "CPU 1 stores". But what if CPU 0 is equally "far" from CPUs 1 and 2?
>
> Suppose that CPU 1 does
>
> wmb();
> B = 0
>
> Can we assume that CPU 2 doing
>
> if (B == 0) {
> rmb();
>
> must see all invalidations from CPU 0 which were seen by CPU 1 before wmb() ?
Yes. CPU 2 saw something following CPU 1's wmb(), so any of CPU 2's
reads following its rmb() must therefore see all of CPU 1's stores
preceding the wmb().
> > > > > If this is possible, can't we move the code doing "s/rcu_flipped/rcu_flip_seen/"
> > > > > from __rcu_advance_callbacks() to rcu_check_mb() to unify the "acks" ?
> > > >
> > > > I believe that we cannot safely do this. The rcu_flipped-to-rcu_flip_seen
> > > > transition has to be synchronized to the moving of the callbacks --
> > > > either that or we need more GP_STAGES.
> > >
> > > Hmm. Still can't understand.
> >
> > Callbacks would be able to be injected into a grace period after it
> > started.
>
> Yes, but this is _exactly_ what the current code does in the scenario below,
>
> > Or are you arguing that as long as interrupts remain disabled between
> > the two events, no harm done?
>
> no,
>
> > > Suppose that we are doing call_rcu(), and __rcu_advance_callbacks() sees
> > > rdp->completed == rcu_ctrlblk.completed but rcu_flip_flag = rcu_flipped
> > > (say, another CPU does rcu_try_flip_idle() in between).
> > >
> > > We ack the flip, call_rcu() enables irqs, the timer interrupt calls
> > > __rcu_advance_callbacks() again and moves the callbacks.
> > >
> > > So, it is still possible that "move callbacks" and "ack the flip" happen
> > > out of order. But why this is bad?
>
> Look, what happens is
>
> // call_rcu()
> rcu_flip_flag = rcu_flipped
> insert the new callback
> // timer irq
> move the callbacks (the new one goes to wait[0])
>
> But I still can't understand why this is bad,
>
> > > This can't "speedup" the moving of our callbacks from next to done lists.
> > > Yes, RCU state machine can switch to the next state/stage, but this looks
> > > safe to me.
>
> Before this callback will be flushed, we need 2 rdp->completed != rcu_ctrlblk.completed
> further events, we can't miss rcu_read_lock() section, no?
>
> > > Help!
>
> Please :)
Quite possibly my paranoia -- need to think about this some more.
Guess I need to expand the code-level portion of the document to cover
the grace-period side. That would force me either to get my explanation
into shape or admit that you are correct, as the case might be. ;-)
> > > if (rcu_ctrlblk.completed == rdp->completed)
> > > rcu_try_flip();
> > >
> > > Could you clarify the check above? Afaics this is just optimization,
> > > technically it is correct to rcu_try_flip() at any time, even if ->completed
> > > are not synchronized. Most probably in that case rcu_try_flip_waitack() will
> > > fail, but nothing bad can happen, yes?
> >
> > >From a conceptual viewpoint, if this CPU hasn't caught up with the
> > last grace-period stage, it has no business trying to push forward to
> > the next stage. So this might (or might not) happen to work with this
> > particular implementation, it needs to stay as is. We need this code
> > to be robust enough to optimize the grace-period latencies, right?
>
> Yes, yes. I just wanted to be sure I didn't miss some other subtle reason.
>
> > > void synchronize_sched(void)
> > > {
> > > struct migration_req req;
> > >
> > > req->task = NULL;
> > > init_completion(&req.done);
> > >
> > > for_each_online_cpu(cpu) {
> > > struct rq *rq = cpu_rq(cpu);
> > > int online;
> > >
> > > spin_lock_irq(&rq->lock);
> > > online = cpu_online(cpu); // HOTPLUG_CPU
> > > if (online) {
> > > list_add(&req->list, &rq->migration_queue);
> > > req.done.done = 0;
> > > }
> > > spin_unlock_irq(&rq->lock);
> > >
> > > if (online) {
> > > wake_up_process(rq->migration_thread);
> > > wait_for_completion(&req.done);
> > > }
> > > }
> > > }
> > >
> >
> > I need to think about your approach above. It looks like you are
> > leveraging the migration tasks, but I am concerned about concurrent
> > hotplug events.
>
> I hope this is OK, note that migration_call(CPU_DEAD) flushes ->migration_queue,
> if we take rq->lock after that we must see !cpu_online(cpu). CPU_UP event is not
> interesting for us, we can miss it.
>
> Hmm... but wake_up_process() should be moved under spin_lock().
The other approach would be to simply have a separate thread for this
purpose. Batching would amortize the overhead (a single trip around the
CPUs could satisfy an arbitrarily large number of synchronize_sched()
requests).
Thanx, Paul
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
