From mboxrd@z Thu Jan  1 00:00:00 1970
From: jmk@plan9.bell-labs.com
Message-Id: <200008021543.LAA26912@cse.psu.edu>
Date: Wed,  2 Aug 2000 11:43:06 -0400
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
MIME-Version: 1.0
Content-Type: multipart/mixed;
	boundary="upas-wpdzquntislbwsfcohkecudowg"
Topicbox-Message-UUID: f2cc8300-eac8-11e9-9e20-41e7f4b1d025

This is a multi-part message in MIME format.
--upas-wpdzquntislbwsfcohkecudowg
Content-Disposition: inline
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit

Doesn't
	/*
	 * Expects that only one process can call wakeup for any given Rendez
	 */
	int
	wakeup(Rendez *r)
	{

mean that process p cannot continue after the sleep?

--upas-wpdzquntislbwsfcohkecudowg
Content-Type: message/rfc822
Content-Disposition: inline

Received: from plan9.cs.bell-labs.com ([135.104.9.2]) by plan9; Wed Aug  2 11:07:25 EDT 2000
Received: from cse.psu.edu ([130.203.3.50]) by plan9; Wed Aug  2 11:07:24 EDT 2000
Received: from localhost (majordom@localhost)
	by cse.psu.edu (8.8.8/8.8.8) with SMTP id KAA24974;
	Wed, 2 Aug 2000 10:48:58 -0400 (EDT)
Received: by claven.cse.psu.edu (bulk_mailer v1.5); Wed, 2 Aug 2000 10:48:40 -0400
Received: (from majordom@localhost)
	by cse.psu.edu (8.8.8/8.8.8) id KAA24915
	for 9fans-outgoing; Wed, 2 Aug 2000 10:48:31 -0400 (EDT)
X-Authentication-Warning: claven.cse.psu.edu: majordom set sender to owner-9fans using -f
Received: from finch-post-10.mail.demon.net (finch-post-10.mail.demon.net [194.217.242.38])
	by cse.psu.edu (8.8.8/8.8.8) with ESMTP id KAA24902
	for <9fans@cse.psu.edu>; Wed, 2 Aug 2000 10:48:22 -0400 (EDT)
From: miller@hamnavoe.demon.co.uk
Received: from hamnavoe.demon.co.uk ([158.152.225.204] helo=hamnavoe)
	by finch-post-10.mail.demon.net with smtp (Exim 2.12 #1)
	id 13Jzoi-000AkU-0A
	for 9fans@cse.psu.edu; Wed, 2 Aug 2000 14:48:20 +0000
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Wed, 2 Aug 2000 15:51:33 0100
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Message-Id: <E13Jzoi-000AkU-0A@finch-post-10.mail.demon.net>
Sender: owner-9fans@cse.psu.edu
Reply-To: 9fans@cse.psu.edu
Precedence: bulk

> If it were at all possible for wakeup to be called with
> r already freed, the code would be wrong to begin with
> since r is an argument to wakeup.

For things to go wrong it's not necessary for wakeup to be
called after r is freed; what I said was "the free(r) and
malloc() could happen *while* or even before wakeup(r) runs".
It's sufficient to have sleep(r) and wakeup(r) racing on
two processors.  We could have this interleaving of events:

sleep(r) is called
  wakeup(r) is called
sleep tests wakeup condition, returns
  wakeup is delayed by an interrupt on its processor
caller of sleep deallocates structure containing r
some other process reallocates r and clobbers r->p
  wakeup resumes, dereferences r->p, ka-boom!

If you think sleep and wakeup are sufficiently interlocked
by higher level considerations that this can't happen,
then let's use your scenario with postnote, mutatis mutandis
to apply to the existing kernel algorithm:

process x calls postnote:
	postnote(p):
		p->notepending = 1
		lock(p->rlock)
		r = p->r
		if r != 0
			if(r->p == p && p->r == r)
				r->p = 0
				p->r = 0
				ready(p)
		unlock(p->rlock)

Immediately after the unlock(p->rlock) is executed,
process q calls wakeup

	process q:
		wakeup(r):    {wakeup condition is satisfied}
			coherence()
			p = r->p
			if p != 0
				lock(p->rlock)
				if (r->p == p && p->r == r)
				    r->p = 0
				    p->r = 0	
				    ready(p)
			    unlock(p->rlock)

During the call to coherence() process q is interrupted.
Process p now continues after the sleep:

	process p:
		sleep(r);
		free(r)

Process y now does

		xxx = malloc(234);
		xxx->a = 12;

And finally process q resumes, and loads and dereferences
r->p which is no longer vald.  ka-boom again.

-- Richard

--upas-wpdzquntislbwsfcohkecudowg--