dynamic data structure switching
Review
Quoted 12 lines · Nick Piggin
(quoted diff) +11
-0+void *dyn_data_replace(struct dyn_data *dd, dd_transfer_fn fn, void *new) +{ + int xfer_done; + void *old; + + BUG_ON(!mutex_is_locked(&dd->resize_mutex)); + old = dd->cur; + BUG_ON(dd->old); + dd->old = old; + synchronize_rcu(); + rcu_assign_pointer(dd->cur, new);
I think this all is correct, but I have a somewhat offtopic question, hopefully you can help.
Suppose that we have a global "pid_t NR = 0", and another CPU does
pid = alloc_pid(); wmb(); NR = pid->nr;
Suppose that this CPU sees dd->cur == new, and adds the new item to it.
Now, yet another CPU does:
nr = NR; rmb(); BUG_ON(nr && !find_pind(nr));
dyn_data_replace() didn't do synchronize_rcu() yet. The question is: how it is possible to "prove" that the BUG_ON() above can't happen? IOW, why find_pind() above must also see dd->cur == new if it sees NR != 0 ?
Once again, I believe this is true, but I can't find a "good" explanation for myself. To simplify the example above, consider:
A = B = X = 0; P = Q = &A;
CPU_1 CPU_2 CPU_3
P = &B; *P = 1; if (X) {
wmb(); rmb();
X = 1; BUG_ON(*P != 1 && *Q != 1);
}So, it is not possible that CPU_2 sees P == &B, but CPU_3 sees P == &A in this case, yes?
It looks "obvious" that rmb() guarantees that CPU_3 must see the new value if any other CPU (CPU_2) already saw it "before", but I can't derive this from the "all the LOAD operations specified before the barrier will appear to happen
before all the LOAD operations specified after the barrier" definition.
Thanks,
Oleg.
Quoted 25 lines · Oleg Nesterov
Review
Quoted 12 lines · Nick Piggin
(quoted diff) +11
-0+void *dyn_data_replace(struct dyn_data *dd, dd_transfer_fn fn, void *new) +{ + int xfer_done; + void *old; + + BUG_ON(!mutex_is_locked(&dd->resize_mutex)); + old = dd->cur; + BUG_ON(dd->old); + dd->old = old; + synchronize_rcu(); + rcu_assign_pointer(dd->cur, new);I think this all is correct, but I have a somewhat offtopic question, hopefully you can help.
Suppose that we have a global "
pid_tNR = 0", and another CPU doespid = alloc_pid(); wmb(); NR = pid->nr;Suppose that this CPU sees
dd->cur== new, and adds the new item to it.
Quoted 7 lines
Now, yet another CPU does:
nr = NR; rmb(); BUG_ON(nr && !find_pind(nr));
dyn_data_replace()didn't dosynchronize_rcu()yet.
Hmm, it would have to have done synchronize_rcu() otherwise the first could not see that dd->cur == new...? Or maybe you mean it hasn't done a second synchronize_rcu()? I'll assume you mean that.
Quoted 3 lines
The question is: how it is
possible to "prove" that theBUG_ON()above can't happen? IOW, whyfind_pind()above must also seedd->cur== new if it sees NR != 0 ?
Hmm, that's a very good question. I was in the middle of starting to write why I thought it would work, but after thinking about it more, I'm not sure that it is correct.
I think we have only pairwise barrier semantics, and not causal semantics (so the write to dd->cur from the 3rd CPU can be seen in any order by the others, regardless of what barriers _they_ perform).
So you do have a problem. We'd need to do another synchronize_rcu here to ensure that dd->cur gets propogated out to all CPUs before the first insert happens. This shouldn't be too hard (simplest way is probably to use a low-bit in the pointer).
Quoted 13 lines
Once again, I believe this is true, but I can't find a "good" explanation for myself. To simplify the example above, consider:
A = B = X = 0; P = Q = &A;
CPU_1CPU_2CPU_3P = &B; *P = 1; if (X) { wmb(); rmb(); X = 1; BUG_ON(*P != 1 && *Q != 1); }
Quoted 7 lines
So, it is not possible that
CPU_2sees P == &B, butCPU_3sees P == &A in this case, yes?It looks "obvious" that
rmb()guarantees thatCPU_3must see the new value if any other CPU (CPU_2) already saw it "before", but I can't derive this from the "all the LOAD operations specified before the barrier will appear to happen
before all the LOAD operations specified after the barrier" definition.
I believe this can go out of order (according to Linux memory model, I don't know if any actual implementations will do this). The invalidations from CPU1 and 2 may reach CPU3 at different times I think.
Good point. Thanks.