On Sat, Nov 22, 2014 at 5:38 AM, Taylor R Campbell <campbell+netbsd-tech-k...@mumble.net> wrote: > Date: Sat, 22 Nov 2014 01:31:48 +0900 > From: Masao Uebayashi <uebay...@gmail.com> > > On Sat, Nov 22, 2014 at 1:22 AM, Taylor R Campbell > <campbell+netbsd-tech-k...@mumble.net> 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.