Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1522006 > unrolled thread

[PATCH RFC tip/core/rcu] SRCU rewrite

Back to article view | Back to linux.kernel

Contents

  [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-14 19:40 +0100
    Re: [PATCH RFC tip/core/rcu] SRCU rewrite Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-11-14 20:10 +0100
    Re: [PATCH RFC tip/core/rcu] SRCU rewrite Boqun Feng <boqun.feng@gmail.com> - 2016-11-15 02:50 +0100
      Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-15 15:40 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite Boqun Feng <boqun.feng@gmail.com> - 2016-11-17 15:40 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-11-17 18:10 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 18:20 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lai Jiangshan <jiangshanlai@gmail.com> - 2016-11-17 18:30 +0100
            Re: [PATCH RFC tip/core/rcu] SRCU rewrite Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-11-17 19:00 +0100
              Re: [PATCH RFC tip/core/rcu] SRCU rewrite Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-11-17 19:10 +0100
                Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 22:30 +0100
            Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lance Roy <ldr709@gmail.com> - 2016-11-17 21:40 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 18:20 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 18:50 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lai Jiangshan <jiangshanlai@gmail.com> - 2016-11-17 19:20 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite Boqun Feng <boqun.feng@gmail.com> - 2016-11-17 19:40 +0100
            Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 20:20 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-17 19:50 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lai Jiangshan <jiangshanlai@gmail.com> - 2016-11-17 19:50 +0100
    Re: [PATCH RFC tip/core/rcu] SRCU rewrite Peter Zijlstra <peterz@infradead.org> - 2016-11-15 09:00 +0100
      Re: [PATCH RFC tip/core/rcu] SRCU rewrite Peter Zijlstra <peterz@infradead.org> - 2016-11-15 15:00 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-15 15:30 +0100
          Re: [PATCH RFC tip/core/rcu] SRCU rewrite Peter Zijlstra <peterz@infradead.org> - 2016-11-15 16:00 +0100
            Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-15 16:50 +0100
      Re: [PATCH RFC tip/core/rcu] SRCU rewrite Mathieu Desnoyers <mathieu.desnoyers@efficios.com> - 2016-11-15 15:00 +0100
    Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lai Jiangshan <jiangshanlai@gmail.com> - 2016-11-17 19:00 +0100
      Re: [PATCH RFC tip/core/rcu] SRCU rewrite Lance Roy <ldr709@gmail.com> - 2016-11-17 21:00 +0100
        Re: [PATCH RFC tip/core/rcu] SRCU rewrite "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-11-18 14:40 +0100

Page 2 of 2 — ← Prev page 1 [2]

#1522741

On Tue, Nov 15, 2016 at 01:54:50PM +0000, Mathieu Desnoyers wrote:
> ----- On Nov 15, 2016, at 2:51 AM, Peter Zijlstra peterz@infradead.org wrote:
> 
> > On Mon, Nov 14, 2016 at 10:36:36AM -0800, Paul E. McKenney wrote:
> >> SRCU uses two per-cpu counters: a nesting counter to count the number of
> >> active critical sections, and a sequence counter to ensure that the nesting
> >> counters don't change while they are being added together in
> >> srcu_readers_active_idx_check().
> >> 
> >> This patch instead uses per-cpu lock and unlock counters. Because the both
> >> counters only increase and srcu_readers_active_idx_check() reads the unlock
> >> counter before the lock counter, this achieves the same end without having
> >> to increment two different counters in srcu_read_lock(). This also saves a
> >> smp_mb() in srcu_readers_active_idx_check().
> > 
> > A very small improvement... I feel SRCU has much bigger issues :/
> 
> Do you have specific issues in mind ?

The smp_mb()s in read_{un,}lock() and the lock in call_srcu() come to
mind.

[toc] | [prev] | [next] | [standalone]

#1522768

On Tue, Nov 15, 2016 at 02:59:12PM +0100, Peter Zijlstra wrote:
> On Tue, Nov 15, 2016 at 01:54:50PM +0000, Mathieu Desnoyers wrote:
> > ----- On Nov 15, 2016, at 2:51 AM, Peter Zijlstra peterz@infradead.org wrote:
> > 
> > > On Mon, Nov 14, 2016 at 10:36:36AM -0800, Paul E. McKenney wrote:
> > >> SRCU uses two per-cpu counters: a nesting counter to count the number of
> > >> active critical sections, and a sequence counter to ensure that the nesting
> > >> counters don't change while they are being added together in
> > >> srcu_readers_active_idx_check().
> > >> 
> > >> This patch instead uses per-cpu lock and unlock counters. Because the both
> > >> counters only increase and srcu_readers_active_idx_check() reads the unlock
> > >> counter before the lock counter, this achieves the same end without having
> > >> to increment two different counters in srcu_read_lock(). This also saves a
> > >> smp_mb() in srcu_readers_active_idx_check().
> > > 
> > > A very small improvement... I feel SRCU has much bigger issues :/
> > 
> > Do you have specific issues in mind ?
> 
> The smp_mb()s in read_{un,}lock() and the lock in call_srcu() come to
> mind.

There is some possibility of weakening the srcu_read_unlock() ordering,
but one step at a time.

Has the lock in call_srcu() been causing trouble?  Easy to fix if so,
but as you noted in another email today, we don't need complexity for
complexity's sake.  And no reports of problems with this have reached
me thus far.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1522796

On Tue, Nov 15, 2016 at 06:26:27AM -0800, Paul E. McKenney wrote:
> On Tue, Nov 15, 2016 at 02:59:12PM +0100, Peter Zijlstra wrote:

> > The smp_mb()s in read_{un,}lock() and the lock in call_srcu() come to
> > mind.
> 
> There is some possibility of weakening the srcu_read_unlock() ordering,
> but one step at a time.
> 
> Has the lock in call_srcu() been causing trouble?  Easy to fix if so,
> but as you noted in another email today, we don't need complexity for
> complexity's sake.  And no reports of problems with this have reached
> me thus far.

It was a cause for concern in the optimistic fault series, but since
that never got sorted, it hasn't shown up in practise afaik.

[toc] | [prev] | [next] | [standalone]

#1522863

On Tue, Nov 15, 2016 at 03:55:36PM +0100, Peter Zijlstra wrote:
> On Tue, Nov 15, 2016 at 06:26:27AM -0800, Paul E. McKenney wrote:
> > On Tue, Nov 15, 2016 at 02:59:12PM +0100, Peter Zijlstra wrote:
> 
> > > The smp_mb()s in read_{un,}lock() and the lock in call_srcu() come to
> > > mind.
> > 
> > There is some possibility of weakening the srcu_read_unlock() ordering,
> > but one step at a time.
> > 
> > Has the lock in call_srcu() been causing trouble?  Easy to fix if so,
> > but as you noted in another email today, we don't need complexity for
> > complexity's sake.  And no reports of problems with this have reached
> > me thus far.
> 
> It was a cause for concern in the optimistic fault series, but since
> that never got sorted, it hasn't shown up in practise afaik.

Sounds like it is not too early for me to be thinking about fixes,
probably similar to the approach used for expedited grace periods.

And thank you for letting me know!

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1522747

----- On Nov 15, 2016, at 2:51 AM, Peter Zijlstra peterz@infradead.org wrote:

> On Mon, Nov 14, 2016 at 10:36:36AM -0800, Paul E. McKenney wrote:
>> SRCU uses two per-cpu counters: a nesting counter to count the number of
>> active critical sections, and a sequence counter to ensure that the nesting
>> counters don't change while they are being added together in
>> srcu_readers_active_idx_check().
>> 
>> This patch instead uses per-cpu lock and unlock counters. Because the both
>> counters only increase and srcu_readers_active_idx_check() reads the unlock
>> counter before the lock counter, this achieves the same end without having
>> to increment two different counters in srcu_read_lock(). This also saves a
>> smp_mb() in srcu_readers_active_idx_check().
> 
> A very small improvement... I feel SRCU has much bigger issues :/

Do you have specific issues in mind ?

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

[toc] | [prev] | [next] | [standalone]

#1524621

On Tue, Nov 15, 2016 at 2:36 AM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> SRCU uses two per-cpu counters: a nesting counter to count the number of
> active critical sections, and a sequence counter to ensure that the nesting
> counters don't change while they are being added together in
> srcu_readers_active_idx_check().
>
> This patch instead uses per-cpu lock and unlock counters. Because the both
> counters only increase and srcu_readers_active_idx_check() reads the unlock
> counter before the lock counter, this achieves the same end without having
> to increment two different counters in srcu_read_lock(). This also saves a
> smp_mb() in srcu_readers_active_idx_check().
>
> A possible problem with this patch is that it can only handle
> ULONG_MAX - NR_CPUS simultaneous readers, whereas the old version could
> handle up to ULONG_MAX.
>
> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Signed-off-by: Lance Roy <ldr709@gmail.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> [ paulmck: Queued for 4.12, that is, merge window after this coming one. ]
>
> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> index dc8eb63c6568..0caea34d8c5f 100644
> --- a/include/linux/srcu.h
> +++ b/include/linux/srcu.h
> @@ -34,8 +34,8 @@
>  #include <linux/workqueue.h>
>
>  struct srcu_struct_array {
> -       unsigned long c[2];
> -       unsigned long seq[2];
> +       unsigned long lock_count[2];
> +       unsigned long unlock_count[2];
>  };
>
>  struct rcu_batch {
> diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c
> index 87c51225ceec..6e4fd7680c70 100644
> --- a/kernel/rcu/rcutorture.c
> +++ b/kernel/rcu/rcutorture.c
> @@ -564,10 +564,24 @@ static void srcu_torture_stats(void)
>         pr_alert("%s%s per-CPU(idx=%d):",
>                  torture_type, TORTURE_FLAG, idx);
>         for_each_possible_cpu(cpu) {
> +               unsigned long l0, l1;
> +               unsigned long u0, u1;
>                 long c0, c1;
> +               struct srcu_struct_array* counts =
> +                       per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu);
>
> -               c0 = (long)per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu)->c[!idx];
> -               c1 = (long)per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu)->c[idx];
> +               u0 = counts->unlock_count[!idx];
> +               u1 = counts->unlock_count[idx];
> +
> +               /* Make sure that a lock is always counted if the corresponding
> +                  unlock is counted. */
> +               smp_rmb();
> +
> +               l0 = counts->lock_count[!idx];
> +               l1 = counts->lock_count[idx];
> +
> +               c0 = (long)(l0 - u0);
> +               c1 = (long)(l1 - u1);
>                 pr_cont(" %d(%ld,%ld)", cpu, c0, c1);
>         }
>         pr_cont("\n");
> diff --git a/kernel/rcu/srcu.c b/kernel/rcu/srcu.c
> index 9b9cdd549caa..edfdfadec821 100644
> --- a/kernel/rcu/srcu.c
> +++ b/kernel/rcu/srcu.c
> @@ -141,34 +141,38 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
>  #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
>
>  /*
> - * Returns approximate total of the readers' ->seq[] values for the
> + * Returns approximate total of the readers' ->lock_count[] values for the
>   * rank of per-CPU counters specified by idx.
>   */
> -static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
> +static unsigned long srcu_readers_lock_idx(struct srcu_struct *sp, int idx)
>  {
>         int cpu;
>         unsigned long sum = 0;
>         unsigned long t;
>
>         for_each_possible_cpu(cpu) {
> -               t = READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
> +               struct srcu_struct_array* cpu_counts =
> +                       per_cpu_ptr(sp->per_cpu_ref, cpu);
> +               t = READ_ONCE(cpu_counts->lock_count[idx]);
>                 sum += t;
>         }
>         return sum;
>  }
>
>  /*
> - * Returns approximate number of readers active on the specified rank
> - * of the per-CPU ->c[] counters.
> + * Returns approximate total of the readers' ->unlock_count[] values for the
> + * rank of per-CPU counters specified by idx.
>   */
> -static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
> +static unsigned long srcu_readers_unlock_idx(struct srcu_struct *sp, int idx)
>  {
>         int cpu;
>         unsigned long sum = 0;
>         unsigned long t;
>
>         for_each_possible_cpu(cpu) {
> -               t = READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
> +               struct srcu_struct_array* cpu_counts =
> +                       per_cpu_ptr(sp->per_cpu_ref, cpu);
> +               t = READ_ONCE(cpu_counts->unlock_count[idx]);
>                 sum += t;
>         }
>         return sum;
> @@ -176,79 +180,43 @@ static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
>
>  /*
>   * Return true if the number of pre-existing readers is determined to
> - * be stably zero.  An example unstable zero can occur if the call
> - * to srcu_readers_active_idx() misses an __srcu_read_lock() increment,
> - * but due to task migration, sees the corresponding __srcu_read_unlock()
> - * decrement.  This can happen because srcu_readers_active_idx() takes
> - * time to sum the array, and might in fact be interrupted or preempted
> - * partway through the summation.
> + * be zero.
>   */
>  static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
>  {
> -       unsigned long seq;
> +       unsigned long unlocks;
>
> -       seq = srcu_readers_seq_idx(sp, idx);
> +       unlocks = srcu_readers_unlock_idx(sp, idx);
>
>         /*
> -        * The following smp_mb() A pairs with the smp_mb() B located in
> -        * __srcu_read_lock().  This pairing ensures that if an
> -        * __srcu_read_lock() increments its counter after the summation
> -        * in srcu_readers_active_idx(), then the corresponding SRCU read-side
> -        * critical section will see any changes made prior to the start
> -        * of the current SRCU grace period.
> +        * Make sure that a lock is always counted if the corresponding unlock
> +        * is counted. Needs to be a smp_mb() as the read side may contain a
> +        * read from a variable that is written to before the synchronize_srcu()
> +        * in the write side. In this case smp_mb()s A and B act like the store
> +        * buffering pattern.
>          *
> -        * Also, if the above call to srcu_readers_seq_idx() saw the
> -        * increment of ->seq[], then the call to srcu_readers_active_idx()
> -        * must see the increment of ->c[].
> +        * This smp_mb() also pairs with smp_mb() C to prevent writes after the
> +        * synchronize_srcu() from being executed before the grace period ends.
>          */
>         smp_mb(); /* A */
>
>         /*
> -        * Note that srcu_readers_active_idx() can incorrectly return
> -        * zero even though there is a pre-existing reader throughout.
> -        * To see this, suppose that task A is in a very long SRCU
> -        * read-side critical section that started on CPU 0, and that
> -        * no other reader exists, so that the sum of the counters
> -        * is equal to one.  Then suppose that task B starts executing
> -        * srcu_readers_active_idx(), summing up to CPU 1, and then that
> -        * task C starts reading on CPU 0, so that its increment is not
> -        * summed, but finishes reading on CPU 2, so that its decrement
> -        * -is- summed.  Then when task B completes its sum, it will
> -        * incorrectly get zero, despite the fact that task A has been
> -        * in its SRCU read-side critical section the whole time.
> -        *
> -        * We therefore do a validation step should srcu_readers_active_idx()
> -        * return zero.
> -        */
> -       if (srcu_readers_active_idx(sp, idx) != 0)
> -               return false;
> -
> -       /*
> -        * The remainder of this function is the validation step.
> -        * The following smp_mb() D pairs with the smp_mb() C in
> -        * __srcu_read_unlock().  If the __srcu_read_unlock() was seen
> -        * by srcu_readers_active_idx() above, then any destructive
> -        * operation performed after the grace period will happen after
> -        * the corresponding SRCU read-side critical section.
> +        * If the locks are the same as the unlocks, then there must of have
> +        * been no readers on this index at some time in between. This does not
> +        * mean that there are no more readers, as one could have read the
> +        * current index but have incremented the lock counter yet.
>          *
> -        * Note that there can be at most NR_CPUS worth of readers using
> -        * the old index, which is not enough to overflow even a 32-bit
> -        * integer.  (Yes, this does mean that systems having more than
> -        * a billion or so CPUs need to be 64-bit systems.)  Therefore,
> -        * the sum of the ->seq[] counters cannot possibly overflow.
> -        * Therefore, the only way that the return values of the two
> -        * calls to srcu_readers_seq_idx() can be equal is if there were
> -        * no increments of the corresponding rank of ->seq[] counts
> -        * in the interim.  But the missed-increment scenario laid out
> -        * above includes an increment of the ->seq[] counter by
> -        * the corresponding __srcu_read_lock().  Therefore, if this
> -        * scenario occurs, the return values from the two calls to
> -        * srcu_readers_seq_idx() will differ, and thus the validation
> -        * step below suffices.
> +        * Note that there can be at most NR_CPUS worth of readers using the old
> +        * index that haven't incremented ->lock_count[] yet.  Therefore, the
> +        * sum of the ->lock_count[]s cannot increment enough times to overflow
> +        * and end up equal the sum of the ->unlock_count[]s, as long as there
> +        * are at most ULONG_MAX - NR_CPUS readers at a time.  (Yes, this does

from the changelog, it sounds like that "ULONG_MAX - NR_CPUS" is the limit
of the implements(old or this one). but actually the real max number of
active readers is much smaller, I think ULONG_MAX/4 can be used here instead
and that part of the changelog can be removed.


> +        * mean that systems having more than a billion or so CPUs need to be
> +        * 64-bit systems.)  Therefore, the only way that the return values of
> +        * the two calls to srcu_readers_(un)lock_idx() can be equal is if there
> +        * are no active readers using this index.
>          */
> -       smp_mb(); /* D */
> -
> -       return srcu_readers_seq_idx(sp, idx) == seq;
> +       return srcu_readers_lock_idx(sp, idx) == unlocks;
>  }
>
>  /**
> @@ -266,8 +234,12 @@ static bool srcu_readers_active(struct srcu_struct *sp)
>         unsigned long sum = 0;
>
>         for_each_possible_cpu(cpu) {
> -               sum += READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[0]);
> -               sum += READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[1]);
> +               struct srcu_struct_array* cpu_counts =
> +                       per_cpu_ptr(sp->per_cpu_ref, cpu);
> +               sum += READ_ONCE(cpu_counts->lock_count[0]);
> +               sum += READ_ONCE(cpu_counts->lock_count[1]);
> +               sum -= READ_ONCE(cpu_counts->unlock_count[0]);
> +               sum -= READ_ONCE(cpu_counts->unlock_count[1]);
>         }
>         return sum;
>  }
> @@ -298,9 +270,8 @@ int __srcu_read_lock(struct srcu_struct *sp)
>         int idx;
>
>         idx = READ_ONCE(sp->completed) & 0x1;
> -       __this_cpu_inc(sp->per_cpu_ref->c[idx]);
> +       __this_cpu_inc(sp->per_cpu_ref->lock_count[idx]);
>         smp_mb(); /* B */  /* Avoid leaking the critical section. */
> -       __this_cpu_inc(sp->per_cpu_ref->seq[idx]);
>         return idx;
>  }
>  EXPORT_SYMBOL_GPL(__srcu_read_lock);
> @@ -314,7 +285,7 @@ EXPORT_SYMBOL_GPL(__srcu_read_lock);
>  void __srcu_read_unlock(struct srcu_struct *sp, int idx)
>  {
>         smp_mb(); /* C */  /* Avoid leaking the critical section. */
> -       this_cpu_dec(sp->per_cpu_ref->c[idx]);
> +       this_cpu_inc(sp->per_cpu_ref->unlock_count[idx]);
>  }
>  EXPORT_SYMBOL_GPL(__srcu_read_unlock);
>
> @@ -349,7 +320,7 @@ static bool try_check_zero(struct srcu_struct *sp, int idx, int trycount)
>
>  /*
>   * Increment the ->completed counter so that future SRCU readers will
> - * use the other rank of the ->c[] and ->seq[] arrays.  This allows
> + * use the other rank of the ->(un)lock_count[] arrays.  This allows
>   * us to wait for pre-existing readers in a starvation-free manner.
>   */
>  static void srcu_flip(struct srcu_struct *sp)
>

Acked-by: Lai Jiangshan <jiangshanlai@gmail.com>

[toc] | [prev] | [next] | [standalone]

#1524787

On Thu, 17 Nov 2016 21:58:34 +0800
Lai Jiangshan <jiangshanlai@gmail.com> wrote:
> from the changelog, it sounds like that "ULONG_MAX - NR_CPUS" is the limit
> of the implements(old or this one). but actually the real max number of
> active readers is much smaller, I think ULONG_MAX/4 can be used here instead
> and that part of the changelog can be removed.
In the old version, there are two separate limits. There first is that there
are no more than ULONG_MAX nested or parallel readers, as otherwise ->c[] would
overflow.

The other limit is to prevent ->seq[] from overflowing during
srcu_readers_active_idx_check(). For this to happen, there must be ULONG_MAX+1
readers that loaded ->completed before srcu_flip() was run which then increment
->seq[]. The ->seq[] array is supposed to prevent
srcu_readers_active_idx_check() from completing successfully if any such
readers increment ->seq[], because otherwise they could decrement ->c[] while
it is being read, which could cause it to incorrectly report that there are no
active readers. If ->seq[] overflows then there is nothing (except how
improbable it is) to prevent this from happening.

I used to think (because of the previous comment) that there could be at most
one such increment of ->seq[] per CPU, as they would have to be using to old
value of ->completed and preemption would be disabled. This is not the case
because there are no barriers around srcu_flip(), so the processor is not
required to increment ->completed before reading ->seq[] the first time, nor is
it required to wait until it is done reading ->seq[] the second time before
incrementing. This means that the following code could cause ->seq[] to
increment an arbitrarily large number of times between the two ->seq[] loads in
srcu_readers_active_idx_check().
	while (true) {
		int idx = srcu_read_lock(sp);
		srcu_read_unlock(sp, idx);
	}

Thanks,
Lance

[toc] | [prev] | [next] | [standalone]

#1525331

On Thu, Nov 17, 2016 at 11:53:04AM -0800, Lance Roy wrote:
> On Thu, 17 Nov 2016 21:58:34 +0800
> Lai Jiangshan <jiangshanlai@gmail.com> wrote:
> > from the changelog, it sounds like that "ULONG_MAX - NR_CPUS" is the limit
> > of the implements(old or this one). but actually the real max number of
> > active readers is much smaller, I think ULONG_MAX/4 can be used here instead
> > and that part of the changelog can be removed.
> In the old version, there are two separate limits. There first is that there
> are no more than ULONG_MAX nested or parallel readers, as otherwise ->c[] would
> overflow.
> 
> The other limit is to prevent ->seq[] from overflowing during
> srcu_readers_active_idx_check(). For this to happen, there must be ULONG_MAX+1
> readers that loaded ->completed before srcu_flip() was run which then increment
> ->seq[]. The ->seq[] array is supposed to prevent
> srcu_readers_active_idx_check() from completing successfully if any such
> readers increment ->seq[], because otherwise they could decrement ->c[] while
> it is being read, which could cause it to incorrectly report that there are no
> active readers. If ->seq[] overflows then there is nothing (except how
> improbable it is) to prevent this from happening.
> 
> I used to think (because of the previous comment) that there could be at most
> one such increment of ->seq[] per CPU, as they would have to be using to old
> value of ->completed and preemption would be disabled. This is not the case
> because there are no barriers around srcu_flip(), so the processor is not
> required to increment ->completed before reading ->seq[] the first time, nor is
> it required to wait until it is done reading ->seq[] the second time before
> incrementing. This means that the following code could cause ->seq[] to
> increment an arbitrarily large number of times between the two ->seq[] loads in
> srcu_readers_active_idx_check().
> 	while (true) {
> 		int idx = srcu_read_lock(sp);
> 		srcu_read_unlock(sp, idx);
> 	}

I also initially thought that there would need to be a memory barrier
immediately after srcu_flip().  But after further thought, I don't
believe that this is the case.

The key point is that updaters do the flip, sum the unlock counters,
do a full memory barrier, then sum the lock counters.

We therefore know that if an updater sees an unlock, it is guaranteed
to see the corresponding lock.  Which prevents negative sums.  However,
it is true that the flip and the unlock reads can be interchanged.
This can result in failing to see a count of zero, but it cannot result
in spuriously seeing a count of zero.

More to this point, if an updater fails to see a lock, the next time
that CPU/task does an srcu_read_lock(), that CPU/task is guaranteed
to see the new value of the index.  This limits the number of CPUs/tasks
that can be using the old value of the index.  Given that preemption
is disabled across the fetch of the index and the increment of the lock
count, that number is NR_CPUS-1, given that the updater has to be running
on one of the CPUs (as Mathieu pointed out earlier in this thread).

Or am I missing something?

							Thanx, Paul

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web