On Sun, May 13, 2018 at 07:22:06PM -0700, Paul E. McKenney wrote:
[..]
> > > > > > If you don't mind going through the if conditions in the funnel
> > > > > > locking loop
> > > > > > with me, it would be quite helpful so that I don't mess the code up
> > > > > > and would
> > > > > > also help me add tracing correctly.
> > > > > >
> > > > > > The if condition for prestarted is this:
> > > > > >
> > > > > > if (need_future_gp_element(rnp_root, c) ||
> > > > > > ULONG_CMP_GE(rnp_root->gpnum, c) ||
> > > > > > (rnp != rnp_root &&
> > > > > > rnp_root->gpnum != rnp_root->completed)) {
> > > > > > trace_rcu_this_gp(rnp_root, rdp, c,
> > > > > > TPS("Prestarted"));
> > > > > > goto unlock_out;
> > > > > > need_future_gp_element(rnp_root, c) = true;
> > > > > >
> > > > > > As of 16/21, the heart of the loop is the above (excluding the
> > > > > > locking bits)
> > > > > >
> > > > > > In this what confuses me is the second and the third condition for
> > > > > > pre-started.
> > > > > >
> > > > > > The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c).
> > > > > > AIUI the goal of this condition is to check whether the requested
> > > > > > grace
> > > > > > period has already started. I believe then the above check is
> > > > > > insufficient.
> > > > > > The reason I think its insufficient is I believe we should also
> > > > > > check the
> > > > > > state of the grace period to augment this check.
> > > > > > IMO the condition should really be:
> > > > > > (ULONG_CMP_GT(rnp_root->gpnum, c) ||
> > > > >
> > > > > The above asks whether the -next- grace period -after- the requested
> > > > > one had started.
> > > > >
> > > > > > (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))
> > > > >
> > > > > This asks that the requested grace period not have completed.
> > > > >
> > > > > What about the case where the requested grace period has completed,
> > > > > but the one after has not yet started? If you add that in, I bet you
> > > > > will have something that simplifies to my original.
> > > > >
> > > > > > In a later patch you replaced this with
> > > > > > rseq_done(&rnp_root->gp_seq, c) which
> > > > > > kind of accounts for the state, except that rseq_done uses
> > > > > > ULONG_CMP_GE,
> > > > > > whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to
> > > > > > be equivalent
> > > > > > to the above check. Do you agree?
> > > > >
> > > > > I do not believe that I do. The ULONG_CMP_GE() allows for the
> > > > > missing case
> > > > > where the requested grace period completed, but the following grace
> > > > > period
> > > > > has not yet started.
> > > >
> > > > Ok thanks that clears it up. For some reason I was thinking if
> > > > rnp_root->gpnum == c, that could means 'c' has not yet started, unless
> > > > we
> > > > also checked the state. Obviously, now I realize gpnum == c can only
> > > > mean 2
> > > > things:
> > > > - c has started but not yet completed
> > > > - c has completed
> > > >
> > > > Both of these cases should cause a bail out so I agree now with your
> > > > condition ULONG_CMP_GE, thanks.
> > > >
> > > > >
> > > > > > The third condition for pre-started is:
> > > > > > (rnp != rnp_root && rnp_root->gpnum !=
> > > > > > rnp_root->completed))
> > > > > > This as I followed from your commit message is if an intermediate
> > > > > > node thinks
> > > > > > RCU is non-idle, then its not necessary to mark the tree and we can
> > > > > > bail out
> > > > > > since the clean up will scan the whole tree anyway. That makes
> > > > > > sense to me
> > > > > > but I think I will like to squash the diff in your previous email
> > > > > > into this
> > > > > > condition as well to handle both conditions together.
> > > > >
> > > > > Please keep in mind that it is necessary to actually record the
> > > > > request
> > > > > in the leaf case. Or are you advocating use of ?: or similar to make
> > > > > this
> > > > > happen?
> > > >
> > > > Yes, I realized yesterday you wanted to record it for the leaf that's
> > > > why
> > > > you're doing things this way. I'll let you know if I find any other
> > > > ways of
> > > > simplifying it once I look at your latest tree.
> > > >
> > > > Btw, I checked your git tree and couldn't see the update that you
> > > > mentioned
> > > > you queued above. Could you push those changes?
> > >
> > > Good point, pushed now. And the patch that I forgot to include in the
> > > last email is below.
> >
> > Cool, thanks. Also one thing I wanted to discuss, I am a bit unclear about
> > the if (rcu_seq_done..) condition in the loop which decides if the GP
> > requested is pre-started.
>
> Actually, rcu_seq_done() instead determines whether or not the GP has
> -completed-.
>
> > Say c is 8 (0b1000) - i.e. gp requested is 2.
> > I drew some tables with some examples, the result column is what the
> > current code will do.
> >
> > Say gp_seq is 12 and its not progress (0b1100),
> >
> > gp_seq gp_num state analysis of gp_seq result
> > 12 3 0 gp 3 not started pre-started
> > (gp 2 completed)
> >
> > For this, the "greater than" check in rcu_seq_done will work because 2
> > already
> > completed (The check essentially does 12 >= 8 which implies prestarted).
>
> Agreed.
>
> > Say gp_seq is 9 and it is in progress (0b1001)
> > gp_seq gp_num state state of gp_seq result
> > 9 2 1 gp 2 in progress pre-started
> > (gp 1 completed)
> >
> > Here also the "greater than" check is correct (9 >= 8 which implies
> > prestarted).
>
> Yes, ->gp_seq of 9 implies that _snap() of 8 is done and gone.
According to the above table, I was trying to indicate that gp_seq = 9
implies, gp_num of 2 is in progress, not done. So in my view, whatever the
_snap returned is in progress now (state bit is set).
> > However, say gp_seq is 8
> > gp_seq gp_num state state of gp_seq result
> > 8 2 0 gp 2 not started pre-started
> > (gp 1 completed)
> >
> > In this case, rcu_seq_done will incorrectly say that its pre-started when 2
> > has not yet started. For this reason, I feel the equal-to check in
> > rcu_seq_done will incorrectly predict prestarted.
>
> If _snap() said 8, then it meant that when ->gp_seq reached 8, the needed
> grace periods had elapsed. So ULONG_CMP_GE() really is what we want.
I kind of don't agree still according to the below (but I'm pretty sure I'm
missing something so I probably need to go through some more examples, do
some more tracing etc.)
Forgetting about _snap for a second, can we not look at gp_seq independently
and determine what the grace period is currently doing? In my view, if gp_seq
reaches 8 (gp_num is 2) - that means that gp_num of 1 was just done. It
doesn't mean 2 completed.. 2 could have either started or not yet started, we
can't tell without look at the state bits... this is the part I didn't get.
rcu_seq_start only sets the state bit. rcu_seq_end increments the gp_num
value.
I thought when rcu_seq_end sets the value part of gp_seq to gp_num, I thought
that means that gp_num - 1 just completed. Is that not true?
>
> > I think to fix this, the rseq_done condition could be replaced with:
> > if (ULONG_CMP_GT(rnp_root->gpseq, c)) {
> > // pre-started
> > }
> >
> > I believe the difference arises because one of the patches during the
> > conversion to use gp_seq in the tree replaced rcu_seq_done with
> > ULONG_CMP_GE,
> > where as such a replacement doesn't work in the gp_seq regime because of
> > difference in the way a gp's starte/end is accounted (vs the old way).
> >
> > Does it make sense or was I way off about something :D ?
>
> I believe that you need to start with where the value passed via "c"
> to rcu_start_this_gp() came from. I suggest starting with the call
> from the rcu_seq_snap() in rcu_nocb_wait_gp(), whose return value is
> then passed to rcu_start_this_gp(), the reason being that it doesn't
> drag you through the callback lists.
Ok I'll try to do some more tracing / analysis and think some more following
your suggestions about starting from rcu_nocb_wait_gp. Most likely I am
wrong, but I am yet to convince myself about it :-(
thanks so much!
- Joel
