srcu: RCU variant permitting read-side blocking
Hello Paul,
Review
Quoted 13 lines · Paul E. McKenney
(quoted diff) +12
-0+void init_srcu_struct(struct srcu_struct *sp) +{ + int cpu; + + sp->completed = 0; + sp->per_cpu_ref = (struct srcu_struct_array *) + kmalloc(NR_CPUS * sizeof(*sp->per_cpu_ref), + GFP_KERNEL); + for_each_cpu(cpu) { + sp->per_cpu_ref[cpu].c[0] = 0; + sp->per_cpu_ref[cpu].c[1] = 0; + }
Isn't it simpler to just do:
sp->per_cpu_ref = kzmalloc(NR_CPUS * sizeof(*sp->per_cpu_ref), GFP_KERNEL);
and drop 'for_each_cpu(cpu)' initialization ?
Review
Quoted 11 lines
(quoted diff) +11
-0+int srcu_read_lock(struct srcu_struct *sp) +{ + int idx; + + preempt_disable(); + idx = sp->completed & 0x1; + barrier(); + sp->per_cpu_ref[smp_processor_id()].c[idx]++; + preempt_enable(); + return idx; +}
Could you explain this 'barrier()' ?
Review
Quoted 11 lines
(quoted diff) +11
-0+void synchronize_srcu(struct srcu_struct *sp) +{ + int cpu; + int idx; + int sum; + + might_sleep(); + + mutex_lock(&sp->mutex); + + smp_mb(); /* Prevent operations from leaking in. */
Why smp_wmb() is not enough? We are doing synchronize_sched() below before reading ->per_cpu_ref, and ->completed is protected by ->mutex.
Review
Quoted 2 lines
(quoted diff) +2
-0+ idx = sp->completed & 0x1; + sp->completed++;
But srcu_read_lock()'s path and rcu_dereference() doesn't have rmb(), and the reader can block, so I can't understand how this all works.
Suppose ->completed == 0,
WRITER: READER: old = global_ptr; rcu_assign_pointer(global_ptr, new); synchronize_srcu: locks mutex, does mb, ->completed++; srcu_read_lock(); // reads ->completed == 1 // does .c[1]++ ptr = rcu_dereference(global_ptr) // reads the *OLD* value, // because we don't have rmb() block_on_something(); synchronize_sched(); // ... still blocked ... checks sum_of(.c[0]) == 0, yes synchronize_sched(); // ... still blocked ... kfree(old); // wake up do_something(ptr);
Also, I can't understand the purpose of 2-nd synchronize_sched() in synchronize_srcu().
Please help!
Oleg.
Quoted 19 lines · Oleg Nesterov
Hello Paul,
Review
Quoted 13 lines · Paul E. McKenney
(quoted diff) +12
-0+void init_srcu_struct(struct srcu_struct *sp) +{ + int cpu; + + sp->completed = 0; + sp->per_cpu_ref = (struct srcu_struct_array *) + kmalloc(NR_CPUS * sizeof(*sp->per_cpu_ref), + GFP_KERNEL); + for_each_cpu(cpu) { + sp->per_cpu_ref[cpu].c[0] = 0; + sp->per_cpu_ref[cpu].c[1] = 0; + }Isn't it simpler to just do:
Quoted 4 lines
sp->per_cpu_ref = kzmalloc(NR_CPUS * sizeof(*sp->per_cpu_ref), GFP_KERNEL);and drop '
for_each_cpu(cpu)' initialization ?
Yes, and even simpler to use the alloc_percpu(), as Andrew suggested.
Quoted 5 lines
Quoted 5 lines
(quoted diff) +5
-0+int srcu_read_lock(struct srcu_struct *sp) +{ + int idx; + + preempt_disable();
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+ idx = sp->completed & 0x1; + barrier(); + sp->per_cpu_ref[smp_processor_id()].c[idx]++; + preempt_enable(); + return idx; +}Could you explain this '
barrier()' ?
It ensures that the compiler picks up sp->completed but once. It is hard to imagine a compiler generating code that fetched sp->completed more than once, but I have been unpleasantly surprised before.
Thoughts?
Quoted 6 lines
Quoted 6 lines
(quoted diff) +6
-0+void synchronize_srcu(struct srcu_struct *sp) +{ + int cpu; + int idx; + int sum; +
Quoted 8 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ might_sleep(); + + mutex_lock(&sp->mutex); + + smp_mb(); /* Prevent operations from leaking in. */Why
smp_wmb()is not enough? We are doingsynchronize_sched()below before reading ->per_cpu_ref, and ->completed is protected by ->mutex.
Could well be that smp_wmb() is sufficient. I frankly was not engaging in that level of optimization on this round. Seems likely, given that I was not able to come up with a convincing counter-example.
That said, I am not going to change it until I can prove that it is safe. ;-)
Quoted 8 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ idx = sp->completed & 0x1; + sp->completed++;But srcu_read_lock()'s path and
rcu_dereference()doesn't havermb(), and the reader can block, so I can't understand how this all works.Suppose ->completed == 0,
Quoted 16 lines
WRITER: READER: old = global_ptr; rcu_assign_pointer(global_ptr, new); synchronize_srcu: locks mutex, does mb, ->completed++; srcu_read_lock(); // reads ->completed == 1 // does .c[1]++ ptr = rcu_dereference(global_ptr) // reads the *OLD* value, // because we don't have rmb()
Hmmm... I thought I was handling this case, but my rationale as to how is looking a bit flimsy at the moment. ;-) I will look at this more carefully. If you are correct, one fix is to replace the prior mb with synchronize_sched(). Do you agree that this would fix the problem?
Quoted 4 lines
block_on_something(); synchronize_sched();
The above synchronize_sched() guarantees that all srcu_read_lock() calls that are still in flight will either (1) already be accounted for in .c[1] or (2) do their accounting in .c[0].
Quoted 5 lines
// ... still blocked ... checks sum_of(.c[0]) == 0, yes synchronize_sched();
This one handles the srcu_read_unlock() analog of the situation you are worried about above. The reader does not have memory barriers in srcu_read_unlock(), so an access to the data structure might get reordered to follow the decrement of .c[0] -- which would get messed up by the following kfree().
The synchronize_sched() guarantees that all concurrent srcu_read_unlock() calls complete cleanly before synchronize_sched() returns, inserting a memory barrier on each CPU to enforce this.
Quoted 10 lines
// ... still blocked ... kfree(old); // wake up do_something(ptr);Also, I can't understand the purpose of 2-nd
synchronize_sched()insynchronize_srcu().
(See above.)
Quoted 1 line
Please help!
Thank you for the careful review! I will look more carefully into the scenario you called out above.
Thanx, Paul
Quoted 27 lines · Paul E. McKenney
Quoted 9 lines · Oleg Nesterov
Review
Quoted 2 lines · Paul E. McKenney
(quoted diff) +2
-0+ idx = sp->completed & 0x1; + sp->completed++;But srcu_read_lock()'s path and
rcu_dereference()doesn't havermb(), and the reader can block, so I can't understand how this all works.Suppose ->completed == 0,
Quoted 16 lines
WRITER: READER: old = global_ptr; rcu_assign_pointer(global_ptr, new); synchronize_srcu: locks mutex, does mb, ->completed++; srcu_read_lock(); // reads ->completed == 1 // does .c[1]++ ptr = rcu_dereference(global_ptr) // reads the *OLD* value, // because we don't have rmb()
Quoted 4 lines
Hmmm... I thought I was handling this case, but my rationale as to how is looking a bit flimsy at the moment. ;-) I will look at this more carefully. If you are correct, one fix is to replace the prior mb with
synchronize_sched(). Do you agree that this would fix the problem?
Never mind -- this fix would have no effect. Guess I should engage my brain before sending email. :-/
First to review my reasoning, and then to provide either the explanation should my reasoning prove true or a fix otherwise...
Thanx, Paul
Quoted 11 lines · Paul E. McKenney
Quoted 3 lines · Oleg Nesterov
Also, I can't understand the purpose of 2-nd
synchronize_sched()insynchronize_srcu().This one handles the
srcu_read_unlock()analog of the situation you are worried about above. The reader does not have memory barriers insrcu_read_unlock(), so an access to the data structure might get reordered to follow the decrement of .c[0] -- which would get messed up by the followingkfree().
Aha, I see.
The last question. The 'srcu-2' you posted today does synchronize_srcu_flip() twice. You did it this way because srcu is optimized for readers, otherwise we could just add smp_rmb() into srcu_read_lock() - this should solve the problem as well.
Is my understanding correct?
Thanks!
Oleg.
Quoted 7 lines · Oleg Nesterov
Quoted 6 lines · Paul E. McKenney
Quoted 3 lines · Oleg Nesterov
Also, I can't understand the purpose of 2-nd
synchronize_sched()insynchronize_srcu().
Quoted 7 lines
Quoted 5 lines
This one handles the
srcu_read_unlock()analog of the situation you are worried about above. The reader does not have memory barriers insrcu_read_unlock(), so an access to the data structure might get reordered to follow the decrement of .c[0] -- which would get messed up by the followingkfree().Aha, I see.
Fortunately, we understood opposite sides of the problem, so, taken together, we have it covered. ;-)
Now we just need to figure out how to find the problems that both of us missed!
Quoted 6 lines
The last question. The 'srcu-2' you posted today does
synchronize_srcu_flip()twice. You did it this way because srcu is optimized for readers, otherwise we could just addsmp_rmb()intosrcu_read_lock()- this should solve the problem as well.Is my understanding correct?
Exactly correct!!!
Thanx, Paul