9fans archive / 1997 / 04 / 63 /    prev next

From: presotto@pla... presotto@pla...
Subject: porting linux programs and drivers to plan9
Date: Sun, 20 Apr 1997 23:36:37 -0400

Jmk's on vacation so I'm answering for him.  The Pentium
Pro does speculative reads.  The result of these reads is
a relaxed coherence described below.  The thing most
affected was our sleep wakeup.  To paraphrase sleep and wakeup:

A sleeper does:

	p = u->p;
	lock(&p->rlock);
	r->p = u->p;		/* put myself in the rendezvous structure */
A:	if(wakeup_condition){
		r->p = 0;		/* no need to sleep */
		unlock(&p->rlock);
		return;
	} else {
		/* go to sleep */
		p->state = Wakeme;
		p->r = r;
		unlock(&p->rlock);
		sched();
	}

A waker does:

	wakeup_condition = 1;

	p = r->p;
	if(p == 0)
		return;
	lock(&p->rlock);
B:	if(r->p == p && p->r == r){
		r->p = 0;
		p->r = 0;
		ready(p);
	}
	unlock(&p->rlock);

The assumed invariant was that given any interleaving of these
two sequences, we would always have either

	wakeup_condition == 1  at point A:
or
	p == 1 at point B:

that is, either the process wouldn't sleep or the wakeup would
get it going again.

Unfortunately, on the Pro we found that, for example, the
following execution ordering on different processors could result
in both being 0 at those points:

	wakeup_condition = 1;

			p = u->p;
			lock(&p->rlock);
			r->p = p;		/* put myself in the rendezvous structure */
		A:	if(wakeup_condition){
				r->p = 0;		/* no need to sleep */
				unlock(&p->rlock);
				return;
			} else {

	p = r->p;
	if(p == 0)
		return;
	lock(&p->rlock);
B:	if(r->p == p && p->r == r){
		r->p = 0;
		p->r = 0;
		ready(p);
	}
	unlock(r);

				/* go to sleep */
				p->state = Wakeme;
				p->r = r;
				unlock(&p->rlock);
				sched();
			}

Ordering of remote writes and local reads to the same
location can no longer be trusted since the speculative
read may have happened before the write was performed.
The caches are still 'coherent' but since the value has
already been read out of the cache and is lurking in the
cpu, it doesn't necessarily match reality.  This is a case
where the caches are coherent but the processors aren't. 
An interlock instruction will force coherence at the processor
level.  That means that we had to make sure some sort of interlocked instruction
occurs after any setting of state that another cooperating process
must see.  The lock(r) following the 'wakeup_condition = 1'
was sufficient for the wakeup() side.  However, the 'r->p = u->p'
had no interlock following it, hence the screw up.

We've fixed it by putting an interlock after 'r->p = u->p'.
However, this has made us very scared.  We don't know of
other places in the kernel where this applies but that
doesn't mean there aren't any.  Ken is instrumenting the
compiler to help us check.

cheers.

------ forwarded message follows ------

>From cse.psu.edu!owner-9fans Sun Apr 20 12:39:20 EDT 1997
Received: from cse.psu.edu by plan9; Sun Apr 20 12:39:20 EDT 1997
Received: from localhost (majordom@localhost) by cse.psu.edu (8.8.5/8.7.3) with SMTP id MAA11975; Sun, 20 Apr 1997 12:17:36 -0400 (EDT)
Received: by claven.cse.psu.edu (bulk_mailer v1.5); Sun, 20 Apr 1997 12:17:07 -0400
Received: (from majordom@localhost) by cse.psu.edu (8.8.5/8.7.3) id MAA11933 for 9fans-outgoing; Sun, 20 Apr 1997 12:17:01 -0400 (EDT)
X-Authentication-Warning: claven.cse.psu.edu: majordom set sender to owner-9fans using -f
Received: from hamnavoe.demon.co.uk (hamnavoe.demon.co.uk [158.152.225.204]) by cse.psu.edu (8.8.5/8.7.3) with SMTP id MAA11929 for <9fans@cse...>; Sun, 20 Apr 1997 12:16:54 -0400 (EDT)
From: hamnavoe.demon.co.uk!miller
Message-Id: <199704201616.MAA11929@cse...>
To: cse.psu.edu!9fans
Date: Sun, 20 Apr 1997 17:12:45 BST
Subject: Re: porting linux programs and drivers to plan9
Sender: cse.psu.edu!owner-9fans
Reply-To: cse.psu.edu!9fans
Precedence: bulk

plan9.bell-labs.com!jmk wrote:

> ... we've found one problem caused by the weak memory ordering of the Pentium
> Pro

Can you be more explicit, please?

-- Richard Miller