From mboxrd@z Thu Jan 1 00:00:00 1970 From: presotto@plan9.bell-labs.com Message-Id: <200008021624.MAA28432@cse.psu.edu> Date: Wed, 2 Aug 2000 12:24:41 -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-xazfwventtitdlgtudawuxpmqu" Topicbox-Message-UUID: f2de0fb2-eac8-11e9-9e20-41e7f4b1d025 This is a multi-part message in MIME format. --upas-xazfwventtitdlgtudawuxpmqu Content-Disposition: inline Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit 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. --upas-xazfwventtitdlgtudawuxpmqu Content-Type: message/rfc822 Content-Disposition: inline Received: from plan9.cs.bell-labs.com ([135.104.9.2]) by plan9; Wed Aug 2 11:59:25 EDT 2000 Received: from cse.psu.edu ([130.203.3.50]) by plan9; Wed Aug 2 11:59:24 EDT 2000 Received: from localhost (majordom@localhost) by cse.psu.edu (8.8.8/8.8.8) with SMTP id LAA27009; Wed, 2 Aug 2000 11:43:56 -0400 (EDT) Received: by claven.cse.psu.edu (bulk_mailer v1.5); Wed, 2 Aug 2000 11:43:35 -0400 Received: (from majordom@localhost) by cse.psu.edu (8.8.8/8.8.8) id LAA26920 for 9fans-outgoing; Wed, 2 Aug 2000 11:43:19 -0400 (EDT) X-Authentication-Warning: claven.cse.psu.edu: majordom set sender to owner-9fans using -f Received: from plan9.cs.bell-labs.com (plan9.bell-labs.com [204.178.31.2]) by cse.psu.edu (8.8.8/8.8.8) with SMTP id LAA26912 for <9fans@cse.psu.edu>; Wed, 2 Aug 2000 11:43:11 -0400 (EDT) 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" Sender: owner-9fans@cse.psu.edu Reply-To: 9fans@cse.psu.edu Precedence: bulk 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: 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-- --upas-xazfwventtitdlgtudawuxpmqu--