Re: pserialize(9) vs. TAILQ

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

   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.