From mboxrd@z Thu Jan 1 00:00:00 1970 From: presotto@plan9.bell-labs.com Message-Id: <200007311727.NAA22763@cse.psu.edu> Date: Mon, 31 Jul 2000 13:26:57 -0400 To: miller@hamnavoe.demon.co.uk, 9fans@cse.psu.edu Subject: Re: [9fans] Kernel question: i386 test-and-set problem MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="upas-dcjnzkzlcmyalacvupdyhfijru" Topicbox-Message-UUID: efebfe40-eac8-11e9-9e20-41e7f4b1d025 This is a multi-part message in MIME format. --upas-dcjnzkzlcmyalacvupdyhfijru Content-Disposition: inline Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit 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. --upas-dcjnzkzlcmyalacvupdyhfijru Content-Type: message/rfc822 Content-Disposition: inline Received: from plan9.cs.bell-labs.com ([135.104.9.2]) by plan9; Sun Jul 23 10:58:51 EDT 2000 Received: from cse.psu.edu ([130.203.3.50]) by plan9; Sun Jul 23 10:58:49 EDT 2000 Received: from localhost (majordom@localhost) by cse.psu.edu (8.8.8/8.8.8) with SMTP id KAA13237; Sun, 23 Jul 2000 10:43:35 -0400 (EDT) Received: by claven.cse.psu.edu (bulk_mailer v1.5); Sun, 23 Jul 2000 10:40:18 -0400 Received: (from majordom@localhost) by cse.psu.edu (8.8.8/8.8.8) id KAA13168 for 9fans-outgoing; Sun, 23 Jul 2000 10:40:13 -0400 (EDT) X-Authentication-Warning: claven.cse.psu.edu: majordom set sender to owner-9fans using -f Received: from tele-post-20.mail.demon.net (tele-post-20.mail.demon.net [194.217.242.20]) by cse.psu.edu (8.8.8/8.8.8) with ESMTP id KAA13164 for <9fans@cse.psu.edu>; Sun, 23 Jul 2000 10:40:06 -0400 (EDT) From: miller@hamnavoe.demon.co.uk Received: from hamnavoe.demon.co.uk ([158.152.225.204] helo=hamnavoe) by tele-post-20.mail.demon.net with smtp (Exim 2.12 #2) id 13GMvE-0009IY-0K for 9fans@cse.psu.edu; Sun, 23 Jul 2000 14:40:05 +0000 To: 9fans@cse.psu.edu Subject: Re: [9fans] Kernel question: i386 test-and-set problem Date: Sun, 23 Jul 2000 15:41:47 0100 MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Message-Id: Sender: owner-9fans@cse.psu.edu Reply-To: 9fans@cse.psu.edu Precedence: bulk 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 --upas-dcjnzkzlcmyalacvupdyhfijru--