Re: [9fans] Kernel question: i386 test-and-set problem

Re: [9fans] Kernel question: i386 test-and-set problem

[jmk]

[-- Attachment #1: Type: text/plain, Size: 178 bytes --]

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?

[-- Attachment #2: Type: message/rfc822, Size: 3269 bytes --]

From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Wed, 2 Aug 2000 15:51:33 0100
Message-ID: <E13Jzoi-000AkU-0A@finch-post-10.mail.demon.net>

> 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

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

> 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

Re: [9fans] Kernel question: i386 test-and-set problem

[presotto]

[-- Attachment #1: Type: text/plain, Size: 778 bytes --]

As I said in the last message, there has to be synchronization
external to the sleep code to make such a situation work.  For
example

	lock list
	add to list
	unlock list
	sleep
	lock list
	free
	unlock list

and another process will do

	lock list
	if(something to wakeup)
		wakeup
	unlock list

Things calling sleep/wakeup can and do perform such
synchronization.  It's part of writing a multithreaded
kernel, i.e., snchronizing accesses to structures.
You don't haphazardly free things when there are
possible accesses to them outstanding in other threads,
or at least I try not to.

Unfortunately, postnote is an asyncronous event often
initiated by someone that's trying to stop something.
It doesn't know about this external synchronization.

[-- Attachment #2: Type: message/rfc822, Size: 4982 bytes --]

[-- Attachment #2.1.1: Type: text/plain, Size: 178 bytes --]

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?

[-- Attachment #2.1.2: Type: message/rfc822, Size: 3269 bytes --]

From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Wed, 2 Aug 2000 15:51:33 0100
Message-ID: <E13Jzoi-000AkU-0A@finch-post-10.mail.demon.net>

> 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

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

> 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

Re: [9fans] Kernel question: i386 test-and-set problem

[presotto]

[-- Attachment #1: Type: text/plain, Size: 891 bytes --]

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.  Sleep and wakeup have to
be syncronized somewhat in the first place just to work.
Wakeup inherenly has to expect that the sleep won't
free r before it's called.  Since the sleep and wakeup
are called by code that knows about the structures the
Rendezvous is kept in, they can do this.  For example,
if we're descending a list that contains rendezvous
structures and the list operations are made atomic,
the structure won't be in the list if the returning
sleep freed it and the wakeup won't find it.

However, that is not true of postnote which is coming out
of left field and doesn't have any knowledge of the
deep structure of the process it is noting.  It can
take into account no invariants implicit in the process
itself.

[-- Attachment #2: Type: message/rfc822, Size: 2752 bytes --]

From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Wed, 2 Aug 2000 09:32:59 0100
Message-ID: <E13JuLT-0005k5-0V@anchor-post-31.mail.demon.net>

> We did try your solution since it was the obious one.

Wasn't obvious to me.  It emerged from an attempt to sketch a
correctness proof and then derive a version of the algorithm
which would correspond to it.

> 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 x does its lock(r).  We've just
> clobbered some other processes kernel structure.

Ah.  It had not actually occurred to me that a kernel
process might be freeing a data structure while another
process still held a pointer into it.  How naive of me.

If the scenario above is really allowed, I don't see
why it isn't just as much a problem with the existing
kernel.  Even without the interference of postnote(),
we might have sleep(r) finding the wakeup condition
true and returning immediately, so that the free(r) and
malloc() could happen while or even before wakeup(r)
runs.  So when /sys/src/9/port/proc.c:#10217,#10286
is executed, r points to something which is no longer
a Rendez structure.  Therefore r->p could be anything,
and  the lock(&p->rlock) could clobber something or
even cause a memory fault.

Or am I missing something obvious again?

-- Richard

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

> We did try your solution since it was the obious one.

Wasn't obvious to me.  It emerged from an attempt to sketch a
correctness proof and then derive a version of the algorithm
which would correspond to it.

> 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 x does its lock(r).  We've just
> clobbered some other processes kernel structure.

Ah.  It had not actually occurred to me that a kernel
process might be freeing a data structure while another
process still held a pointer into it.  How naive of me.

If the scenario above is really allowed, I don't see
why it isn't just as much a problem with the existing
kernel.  Even without the interference of postnote(),
we might have sleep(r) finding the wakeup condition
true and returning immediately, so that the free(r) and
malloc() could happen while or even before wakeup(r)
runs.  So when /sys/src/9/port/proc.c:#10217,#10286
is executed, r points to something which is no longer
a Rendez structure.  Therefore r->p could be anything,
and  the lock(&p->rlock) could clobber something or
even cause a memory fault.

Or am I missing something obvious again?

-- Richard

Re: [9fans] Kernel question: i386 test-and-set problem

[presotto]

[-- Attachment #1: Type: text/plain, Size: 1191 bytes --]

We did try your solution since it was the obious one.  Consider the
following:

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

Immediately after the r = p->r is executed,
process q calls wakeup

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

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 x does its lock(r).  We've just
clobbered some other processes kernel structure.

We don't know that p->r really points to a valid
Rendzvous structure: they are in malloc'd structures
and p->r may easily be pointing to something in
another structure.  That means that the lock(r)
steps on some random piece of memory.  Usually that's
not a problem.  This took forever to track down.

A possible solution is to use both locks in all three
places which runs into lock ordering problems.

[-- Attachment #2: Type: message/rfc822, Size: 4955 bytes --]

From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Sun, 23 Jul 2000 15:41:47 0100
Message-ID: <E13GMvE-0009IY-0K@tele-post-20.mail.demon.net>

presotto@plan9.bell-labs.com writes:
> If I have two locks,
> one in r and one in p, I can't figure out how to get them both to lock
> in the same order.

My suggestion is below.  The interaction between sleep() and wakeup() is
exactly as in the beautiful and succinct algorithm in your paper, using
the lock on r.  Adding postnote() introduces the pointer p->r to enable
postnote() to find r, so the lock p->rlock is introduced to protect it
in the interaction between sleep() and postnote().  The interaction
between wakeup() and postnote() is protected by the lock on r.

Eliminating interrupt dis/en-abling for simplicity:

sleep(r):    {'up' is the current Proc}
	lock(up->rlock)
	lock(r)
	if wakeup condition is satisfied or up->notepending != 0
		unlock(r)
		unlock(up->rlock)
	else
		r->p = up
		up->r = r
		up->state = Wakeme
		unlock(r)
		unlock(up->rlock)
		-- reschedule --
	if up->notepending
		up->notepending = 0
		error(Eintr)

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

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

Explanation: we can think of locks in terms of the invariants they
protect.  Define S(p,r) = "Proc p is sleeping or committed to
sleeping on Rendez r", where committed means that p will sleep on r
without first testing the wakeup condition or testing for pending
notes.  Define T(p,r) =  "Proc p is not sleeping on r, and will not
sleep on r without first testing both the wakeup condition and
notepending".  The significance of these predicates is that
if S(p,r) holds, then wakeup(r) or postnote(p) must take steps
to awaken p from r; whereas if T(p,r) holds, then wakeup(r) or
postnote(p) need not -- must not -- do so.

The invariant we want to maintain on each Rendez r is:

IR(r): { for all p: (p = r->p) <=> S(p,r) }

or informally, r->p points to a Proc if and only if that Proc is
sleeping or committed to sleeping on r.  Any critical section of
code where IR(r) is temporarily untrue (e.g. while testing conditions
or manipulating r->p) must be protected by locking r.  Because the
inverse of S(p,r) is not quite the same as T(p,r) -- p may have
tested only one of the two conditions -- we also impose a global
invariant:

IPR: { for all p,r: !S(p,r) => T(p,r) }

To protect this invariant, testing of the wakeup condition and
notepending before sleeping on r must be within a lock on r.
The invariant for Proc p, protected by p->rlock, is weaker than IR:

IP(p): { for all r: S(p,r) => (r = p->r) }

or informally, if p is sleeping or committed to sleeping on a Rendez,
then p->r points to that Rendez.  Note that the reverse implication
is not stipulated: if p->r points to a Rendez, we can't necessarily
conclude that S(p,p->r) holds; only that !S(p,r) -- and therefore
T(p,r), by IPR -- holds for all other r.  But the uncertainty over
S(p,p->r) can be resolved using IR(p->r).

Key point: wakeup() can safely set p->r = 0 without locking p->rlock,
because this assignment does not affect the invariant IP(p).  In fact
the assignment could be deleted and the algorithm would still work;
it is only an optimisation to avoid postnote() looking at a Rendez
unnecessarily.  This observation is what saves us from the dilemma
of locking order.

-- Richard Miller

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

presotto@plan9.bell-labs.com writes:
> If I have two locks,
> one in r and one in p, I can't figure out how to get them both to lock
> in the same order.

My suggestion is below.  The interaction between sleep() and wakeup() is
exactly as in the beautiful and succinct algorithm in your paper, using
the lock on r.  Adding postnote() introduces the pointer p->r to enable
postnote() to find r, so the lock p->rlock is introduced to protect it
in the interaction between sleep() and postnote().  The interaction
between wakeup() and postnote() is protected by the lock on r.

Eliminating interrupt dis/en-abling for simplicity:

sleep(r):    {'up' is the current Proc}
	lock(up->rlock)
	lock(r)
	if wakeup condition is satisfied or up->notepending != 0
		unlock(r)
		unlock(up->rlock)
	else
		r->p = up
		up->r = r
		up->state = Wakeme
		unlock(r)
		unlock(up->rlock)
		-- reschedule --
	if up->notepending
		up->notepending = 0
		error(Eintr)

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

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

Explanation: we can think of locks in terms of the invariants they
protect.  Define S(p,r) = "Proc p is sleeping or committed to
sleeping on Rendez r", where committed means that p will sleep on r
without first testing the wakeup condition or testing for pending
notes.  Define T(p,r) =  "Proc p is not sleeping on r, and will not
sleep on r without first testing both the wakeup condition and
notepending".  The significance of these predicates is that
if S(p,r) holds, then wakeup(r) or postnote(p) must take steps
to awaken p from r; whereas if T(p,r) holds, then wakeup(r) or
postnote(p) need not -- must not -- do so.

The invariant we want to maintain on each Rendez r is:

IR(r): { for all p: (p = r->p) <=> S(p,r) }

or informally, r->p points to a Proc if and only if that Proc is
sleeping or committed to sleeping on r.  Any critical section of
code where IR(r) is temporarily untrue (e.g. while testing conditions
or manipulating r->p) must be protected by locking r.  Because the
inverse of S(p,r) is not quite the same as T(p,r) -- p may have
tested only one of the two conditions -- we also impose a global
invariant:

IPR: { for all p,r: !S(p,r) => T(p,r) }

To protect this invariant, testing of the wakeup condition and
notepending before sleeping on r must be within a lock on r.
The invariant for Proc p, protected by p->rlock, is weaker than IR:

IP(p): { for all r: S(p,r) => (r = p->r) }

or informally, if p is sleeping or committed to sleeping on a Rendez,
then p->r points to that Rendez.  Note that the reverse implication
is not stipulated: if p->r points to a Rendez, we can't necessarily
conclude that S(p,p->r) holds; only that !S(p,r) -- and therefore
T(p,r), by IPR -- holds for all other r.  But the uncertainty over
S(p,p->r) can be resolved using IR(p->r).

Key point: wakeup() can safely set p->r = 0 without locking p->rlock,
because this assignment does not affect the invariant IP(p).  In fact
the assignment could be deleted and the algorithm would still work;
it is only an optimisation to avoid postnote() looking at a Rendez
unnecessarily.  This observation is what saves us from the dilemma
of locking order.

-- Richard Miller

Re: [9fans] Kernel question: i386 test-and-set problem

[presotto]

I would have left the lock in if I could have figured out how to do
it and fix the other problems.  The main problem is that one side knows
p and the other side knows r.  If I have one lock, one side is going
to have to look at something not under a lock.  If I have two locks,
one in r and one in p, I can't figure out how to get them both to lock
in the same order.

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

> r->p is either 0 or a valid process number.  Therefore, the r->p
> access shouldn't cause a crash.

Sorry, I'm being sloppy with terminology.  By "crash" I meant that
kfs became internally deadlocked by the failure of sleep/wakeup,
forcing me to reboot without syncing the local file system.

> In v2 the lock was providing the coherence() that we put herein v3.

Yes, I agree -- that's exactly my point.  Locking instructions should
imply memory coherence, however outlandish the memory architecture
might be.  So a conservative locking discipline means not having
to worry about coherence issues.

I know I'm being annoyingly preachy here.  You could say that my
preference for lock() over coherence() is just personal bias.  But
it seems to me that reasoning about weakly coherent memory is
subtle and difficult -- I certainly don't understand it fully.
Synchronisation with locks is more straightforward, and makes sense
on any shared memory architecture.

I'll shut up now.

-- Richard

Re: [9fans] Kernel question: i386 test-and-set problem

[presotto]

r->p is either 0 or a valid process number.  Therefore, the r->p
access shouldn't cause a crash.  We later check the p->r against r
under lock to make sure the process is still waiting on that
rendezvouz.  The worst the unlocked access should do is miss
a sleep which was in the process of happening.  That would have happened
even with the lock with a small delta in timing.

In v2 the lock was providing the coherence() that we put herein v3.
However, v2 also had deadlock problems twixt sleep and postnote
that v3 fixes.

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

jmk@plan9.bell-labs.com writes:

> The sleep/wakeup/postnote Rendez structure still has a lock which
> protects it, it just moved somewhere else.

Sorry, I didn't explain in enough detail.  In /sys/src/9/port/proc.c:588
wakeup() looks at r->p (pointer from Rendez to sleeping process)
without first acquiring any lock.  That's the unprotected access I was
referring to: it's dangerous because r->p is shared asynchronously
by sleep() and postnote().

The original 2nd edition kernel (CD version) had a lock in the Rendez
structure, and all accesses to r->p  were protected by acquiring
the lock first.  However, p->r (pointer from sleeping process to Rendez)
was shared between sleep() and postnote() without locking.

A later kernel update (845586056.rc) introduced a new lock in the Proc
structure (p->rlock) to protect the shared access to p->r, but eliminated
the lock in the Rendez structure.  This left r->p exposed again.  I believe
that's why you need coherence() calls.

> The 2nd Edition code would
> have needed coherence() calls too, but in different places, had it not
> been rewritten before we tried running on a multiprocessor Pentium Pro.

When I added mp support to the 2nd edition for my dual ppro system,
I reinstated the Rendez lock, and kept p->rlock as well, so in the
three-way conversation between sleep(), wakeup() and postnote() both
r->p and p->r are protected.  I didn't add any explicit coherence()
calls anywhere, and the system has been running stably for over two years.
If I remove the lock around the r->p access in wakeup(), a few simultaneous
'du -a /' commands will quickly cause a crash.

-- Richard Miller

Re: [9fans] Kernel question: i386 test-and-set problem

[jmk]

	>Richard Miller <miller@hamnavoe.demon.co.uk> writes:
	>
	>Russ Cox <rsc@plan9.bell-labs.com> writes:
	>
	>> ... Since we don't
	>> play funny games with lock-free data structures, ...
	>
	>A notable exception is the funny game which sleep() and wakeup()
	>play with the Rendez structure, which no longer has the lock
	>which protected it in the original 2nd edition kernel.  This game
	>is not just funny but dangerous, as evidenced by the new coherence()
	>calls introduced to counteract the resulting vulnerability to weakly
	>coherent memory on some multiprocessors, and the long explanatory
	>comment.
	>
	>Kids, don't try this at home ... practise the discipline of Safe
	>Sharing (always use a lock) and you won't need to worry about
	>memory coherence. 
	>
	>-- Richard Miller

I think that's a misrepresentation.

The sleep/wakeup/postnote Rendez structure still has a lock which
protects it, it just moved somewhere else. The 2nd Edition code would
have needed coherence() calls too, but in different places, had it not
been rewritten before we tried running on a multiprocessor Pentium Pro.
Sleep/wakeup/postnote in the 2nd Edition was hopelessy broken in many
other ways.

--jim

Re: [9fans] Kernel question: i386 test-and-set problem

[Jakub Jermar]

> It looks atomic to me.  The Intel 386 instruction set
> manual says
>
> XCHG exchanges two operands.  The operands can be in either
> order.  If a memory operand is involved, BUS LOCK is
> asserted for the duration of the exchange, regardless of the
> presence or absence of the LOCK prefix or of the value of
> the IOPL.

Ok, thank you for clarification. Now I see how it works. It really is atomic
in the terms of atomic exchange (which is good because nobody can be
exchanging it concurrently). Looks like I was confused by its name -
test-and-set - which it is really not. It's rather
safely-set-and-leave-the-test-to-the-caller.

Thanks,
Jakub Jermar

Re: [9fans] Kernel question: i386 test-and-set problem

[miller]

Russ Cox <rsc@plan9.bell-labs.com> writes:

> ... Since we don't
> play funny games with lock-free data structures, ...

A notable exception is the funny game which sleep() and wakeup()
play with the Rendez structure, which no longer has the lock
which protected it in the original 2nd edition kernel.  This game
is not just funny but dangerous, as evidenced by the new coherence()
calls introduced to counteract the resulting vulnerability to weakly
coherent memory on some multiprocessors, and the long explanatory
comment.

Kids, don't try this at home ... practise the discipline of Safe
Sharing (always use a lock) and you won't need to worry about
memory coherence. 

-- Richard Miller

Re: [9fans] Kernel question: i386 test-and-set problem

[Russ Cox]

	The weird thing is that it looks as though this function only exchanged %eax
	and (%ebx) by XCHG instruction which is NOT atomic. The C source looks
	satisfied with it (I have no opportunity to try it, because I am not running

It looks atomic to me.  The Intel 386 instruction set
manual says

	XCHG exchanges two operands.  The operands can be in either
	order.  If a memory operand is involved, BUS LOCK is
	asserted for the duration of the exchange, regardless of the
	presence or absence of the LOCK prefix or of the value of
	the IOPL.

As for cas, ...

	By further searching, I found (in /sys/src/libthread/386cas.s ... or
	something) a routine called cas(). This routine uses the proper 386 atomic
	instruction CMPXCHG.

	Well, what's going on? I'd expect all those C functions to call cas()
	instead of tas(). Mys second question is why cas() is not the only tas()
	(test-end-set) within the 386 part of the kernel. My last question is why
	the cas() is outside the kernel tree.

The main problem with cas() is that it's not on the 386.
It is on the Pentium, and if memory serves, is on the 486.

Libthread is a user-level thread library and not part of
the kernel.  The lack of cas() for any othe architecture
suggests that it was written but never used, probably
for exactly the reason above.  I poked around in the
past and can't find any calls to it, ever.

You'll also note that 386xadd.s does not actually use
the XADD instruction, for the same reason.  Since we
only need increment and decrement, we use
INC and DEC instructions with a LOCK prefix, since
that will work on a 386 (which lacks XADD as well).

The choice of locking primitive is fairly arbitrary,
and tas got chosen a long time ago.  Since we don't
play funny games with lock-free data structures, the
absence of cas or cas2 is not felt.  You could have cas
instead, but it'd be clumsy to implement on a 386
(and maybe on the early Sparcs?).

Russ

[9fans] Kernel question: i386 test-and-set problem

[Jakub Jermar]

Hi all,

I've just been studying the 9 kernel and found something very weird.
In /sys/src/9/pc/l.s, there is an assembly function called tas() that should
provide its callers with an atomic test-and-set operation. This function is
called, for instance, by lock() from taslock.c.

The weird thing is that it looks as though this function only exchanged %eax
and (%ebx) by XCHG instruction which is NOT atomic. The C source looks
satisfied with it (I have no opportunity to try it, because I am not running
Plan 9 - yet :-).
By further searching, I found (in /sys/src/lithread/386cas.s... or
something) a routine called cas(). This routine uses the proper 386 atomic
instruction CMPXCHG.

Well, what's going on? I'd expect all those C functions to call cas()
instead of tas(). Mys second question is why cas() is not the only tas()
(test-end-set) within the 386 part of the kernel. My last question is why
the cas() is outside the kernel tree.

Regards,
Jakub Jermar