From mboxrd@z Thu Jan  1 00:00:00 1970
From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Thu,  3 Aug 2000 10:56:36 +0100
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Message-Id: <E13KHic-000L8t-0B@finch-post-11.mail.demon.net>
Topicbox-Message-UUID: f502e826-eac8-11e9-9e20-41e7f4b1d025

> Things calling sleep/wakeup can and do perform such
> synchronization.
> ...
> Unfortunately, postnote is an asyncronous event often
> initiated by someone that's trying to stop something.
> It doesn't know about this external synchronization.

Thank you for patiently re-explaining -- now I see my mistake.
I misunderstood your scenario which showed the flaw in my
suggested algorithm: I thought it was the lock(r) in wakeup()
which might use an invalid r, but -- as you have shown --
there are higher level locks elsewhere in the kernel which
prevent any race between wakeup(r) and sleep(r)..free(r), 
in both your version and mine.  It's the lock(r) in my version
of postnote() which might go wrong, because of a race between
postnote() and wakeup(r)..free(r).  Sorry for not reading
your posting carefully enough.

My sketched "proof" didn't take this race into account because
I hadn't realised that a Rendez could be deallocated.  I think
it's not difficult to remedy, though.

You said "We don't know that p->r really points to a valid
Rendzvous structure", but in fact that's just what I want to
be able to guarantee, in order to make asynchronous postnote(p)
safe.  Let's stipulate another invariant IPV(p) for each Proc p:
"if p->r is nonzero, then it points to a valid Rendez which
will not be deallocated without first setting p->r to zero".
To maintain this, after p sleeps on r there must be an assignment
of p->r=0 under control of p->rlock before r can be deallocated --
the lock is now necessary to prevent a race with another
process which is looking at p->r (e.g. in postnote).

I think we can do this in my wakeup() without lock ordering
problems, as follows:

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

Strictly speaking this makes my original invariant IR(r)
invalid between the two locked sections; but we can redefine
S(p,r) to mean "Proc p is sleeping or committed to sleeping
on Rendez r, and no other proc is committed to waking p"
and I think everything then still works.

-- Richard