Re: pserialize(9) vs. TAILQ

[Masao Uebayashi <uebayasi%gmail.com@localhost>]

On Sat, Nov 22, 2014 at 5:38 AM, Taylor R Campbell
<campbell+netbsd-tech-kern%mumble.net@localhost> wrote:
>    Date: Sat, 22 Nov 2014 01:31:48 +0900
>    From: Masao Uebayashi <uebayasi%gmail.com@localhost>
>
>    On Sat, Nov 22, 2014 at 1:22 AM, Taylor R Campbell
>    <campbell+netbsd-tech-kern%mumble.net@localhost> wrote:
>    > It matters what's in the ...'s.  Are you doing this?
>    >
>    >         TAILQ_FOREACH(e, head, next) {
>    >                 if (e->key == key) {
>    >                         mutex_spin_enter(&e->lock);
>    >                         ...
>    >
>    > If so, the reader may see a stale e->key -- the membar_enter implied
>    > by mutex_spin_enter is too late.
>
>    The promise there is that, e->key is constant while it's read with
>    pserialize_read_{enter,leave}(9).  If those members have to be
>    changed, they have to be once removed from there, and re-added.
>
> The problem is not that e->key may change while e is in the list -- it
> won't (whoever wants to change it must, as you suggest, remove e from
> the list, change it, and then re-add it).
>
> The problem is that when CPU 0 does
>
>         e = pool_get(&e_pool, PR_WAITOK);
>
> then e->key, at address 0xdeadbeef, will have some garbage
> uninitialized value, say 0xa5a5a5a5, which CPU 1 may have cached.
>
> Next, CPU 0 does:
>
>         e->key = 12345;
>
>         mutex_enter(lock);
>         e->next = eq;
>         membar_producer();
>         eq = e;
>         mutex_exit(lock);
>
> From CPU 0's perspective, the stores have been issued to memory in the
> correct order: nobody who loads e from the memory at eq, and then
> loads e->key from memory at 0xdeadbeef, will see 0xa5a5a5a5 -- anyone
> who issues loads to memory in that order will see 12345.
>
> But CPU 1 already has the contents of 0xdeadbeef cached, so it won't
> load from memory there.  Instead, when it does
>
>         s = pserialize_read_enter();
>         for (e = eq; e != NULL; e = e->next) {
>                 if (e->key == 12345)
>                         ...
>         },
>
> it will load e from memory at eq (or maybe from its cache), and then
> use its cached value for the address 0xdeadbeef, which is 0xa5a5a5a5.
> Nothing prevented CPU 1 from issuing the loads in the `wrong' order --
> CPU 1 had already issued a load for 0xdeadbeef a long time ago, which
> at the time correctly yielded 0xa5a5a5a5.
>
> In order for CPU 1 to guarantee that, after it loads e, it will load
> e->key from memory instead of using the cache, it must issue a
> membar_datadep_consumer:
>
>         s = pserialize_read_enter();
>         for (e = eq; e != NULL; e = e->next) {
>                 membar_datadep_consumer();
>                 if (e->key == 12345)
>                         ...
>         }
>
> This is a general heuristic for memory barriers: when communicating
> from one CPU to another CPU, there should be a matched pair of memory
> barriers.

You are right that "key" has to be volatile.  But otherwise, you are
making things too complex, or too generic, which is not what I'm
expecting as a TAILQ-specialized-for-pserialize(9).

Consider struct ifnet.  IFNET_FOREACH() iterates ifnet_lists to
look-up a wanted ifnet, by matching most typically interface's
addresses.  How often do interface's address change in practice?  Very
rare; or probably never, once after an ifnet is added to the
ifnet_list.

It is users' choice whether using fast-changing values as a key or
not, but if you decide to change values visible by pserialize(9)
readers, you'll end up with ensuring memory order.  It is your choice,
but beyond pserialize(9)'s responsibility.

I don't understand why you resort to only memory barriers.
pserialize(9) doesn't need those tricks, because pserialize(9) relies
on another trick; help from scheduler.  Your approach might work even
without pserialize(9).  Too safe and too excessive.