From owner-freebsd-current Thu Oct 10 14: 3:12 2002 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id EB4A937B401; Thu, 10 Oct 2002 14:03:10 -0700 (PDT) Received: from avocet.mail.pas.earthlink.net (avocet.mail.pas.earthlink.net [207.217.120.50]) by mx1.FreeBSD.org (Postfix) with ESMTP id 7D95143EAC; Thu, 10 Oct 2002 14:03:10 -0700 (PDT) (envelope-from tlambert2@mindspring.com) Received: from pool0397.cvx21-bradley.dialup.earthlink.net ([209.179.193.142] helo=mindspring.com) by avocet.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 17zkSO-0002cs-00; Thu, 10 Oct 2002 14:02:57 -0700 Message-ID: <3DA5EAB4.75F158BE@mindspring.com> Date: Thu, 10 Oct 2002 14:01:40 -0700 From: Terry Lambert X-Mailer: Mozilla 4.79 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Stefan Farfeleder Cc: Don Lewis , jhb@FreeBSD.ORG, jmallett@FreeBSD.ORG, current@FreeBSD.ORG, phk@FreeBSD.ORG Subject: Re: [PATCH] Re: Junior Kernel Hacker page updated... References: <20021008204605.GA252@frog.fafoe> <200210090426.g994QTvU037393@gw.catspoiler.org> <20021009225606.GC306@frog.fafoe> <3DA4B6C1.ED1BACEB@mindspring.com> <20021010203053.GA265@frog.fafoe> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG Stefan Farfeleder wrote: > Imagine this scenario where CPU 0 inserts a knote kn1 (the marker) in > knote_scan and CPU 1 kn2 in kqueue_enqueue: > > CPU 0 | CPU 1 > --------------------------------+------------------------------- > kn1->kn_tqe.tqe_next = NULL; | > | > --------------------------------+------------------------------- > kn1->kn_tqe.tqe_prev = | kn2->kn_tqe.tqe_next = NULL; > kq_head.tqh_last; | > --------------------------------+------------------------------- > *kq_head.tqh_last = kn1; | kn2->kn_tqe.tqe_prev = > | kq_head.tqh_last; > --------------------------------+------------------------------- > kq_head.tqh_last = | *kq_head.tqh_last = kn2; > &kn1->kn_tqe.tqe_next; | > --------------------------------+------------------------------- > | kq_head.tqh_last = > | &kn2->kn_tqe.tqe_next; > > The marker would never appear on the queue. The macro is broken. Here is a fix. #define TAILQ_INSERT_TAIL(head, elm, field) do { \ void **savepp; \ (elm)->field.tqe_next = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ savepp = (head)->tqh_last; \ (head)->tqh_last = &(elm)->field.tqe_next; \ (elm)->field.tqe_prev = savepp; \ *savepp = (elm); \ } while (0) I'm not sure that it's possible to totally close the race; I think the way you would have to do it is to traverse the tqh_last pointer until the tqh_last->file.tqe_next == NULL, before reference it (ugly). The failure mode with the race is an inverted insertion order, which I think, in this case, is not a problem. The double setting of the prev guarantees it has a "harmless" value for a traversal during insertion; it acts as if the insertion had not occurred, if there are two that occurred simultaneously, until both sets of data are valid. This is doable in Intel assembly, I think (CMPXCHGL). Ugh. On other architectures, there's no way to avoid a mutex (e.g. MIPS). I hate tailq's. 8-(. -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message