Re: [rfc][patch] dynamic data structure switching

From: Nick Piggin
Date: Mon Sep 10 2007 - 16:49:00 EST


On Mon, Sep 10, 2007 at 08:58:14PM +0400, Oleg Nesterov wrote:
> Nick Piggin wrote:
> >
> > +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.

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.


> 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 ?

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).


> 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.

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.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/