From owner-freebsd-current@FreeBSD.ORG Thu May 22 10:00:31 2003 Return-Path: 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 6EF0537B404 for ; Thu, 22 May 2003 10:00:31 -0700 (PDT) Received: from mail.speakeasy.net (mail15.speakeasy.net [216.254.0.215]) by mx1.FreeBSD.org (Postfix) with ESMTP id ED15C43FAF for ; Thu, 22 May 2003 10:00:29 -0700 (PDT) (envelope-from jhb@FreeBSD.org) Received: (qmail 1370 invoked from network); 22 May 2003 17:00:29 -0000 Received: from unknown (HELO server.baldwin.cx) ([216.27.160.63]) (envelope-sender )encrypted SMTP for ; 22 May 2003 17:00:29 -0000 Received: from laptop.baldwin.cx (gw1.twc.weather.com [216.133.140.1]) by server.baldwin.cx (8.12.8/8.12.8) with ESMTP id h4MH0Rp0061449; Thu, 22 May 2003 13:00:27 -0400 (EDT) (envelope-from jhb@FreeBSD.org) Message-ID: X-Mailer: XFMail 1.5.4 on FreeBSD X-Priority: 3 (Normal) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit MIME-Version: 1.0 In-Reply-To: <3ECCFFD8.74A284C7@mindspring.com> Date: Thu, 22 May 2003 13:00:39 -0400 (EDT) From: John Baldwin To: Terry Lambert cc: Robert Watson cc: re@FreeBSD.org cc: current@FreeBSD.org Subject: Re: 5.1-RELEASE TODO X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 May 2003 17:00:31 -0000 On 22-May-2003 Terry Lambert wrote: > John Baldwin wrote: >> On 22-May-2003 Terry Lambert wrote: >> > You don't care if another CPU re-does the work, so long as it >> > re-does it atomically. That makes it thread safe without the >> > introduction of locks. >> >> We aren't talking about re-doing the work, we're talking about one >> CPU trying to walk the list while it's an inconsistent state and >> walking off into the weeds through a stale pointer. I.e, CPU 0 >> removes an item from the list while CPU 1 is walking over that item. >> Duh. > > A singly linked list can be maintained in a consistent state > at all times, so long as pointer updates are atomic to a CPU. > > As I said before, this is an order of operation problem, not > a locking problem. For a single linked-list, yes. For doubly-linked lists (which is what I primarily had in mind since most structures I've worked with use LIST and TAILQ rather than SLIST or STAILQ) it is a different matter. >> > Just because your friend jumped off a cliff... >> >> So what is your magic solution for making rtld thread-safe when >> looking up unresolved symbols on first reference? > > Change the order of operation. Basic database theory: > > o write new record > o atomically update index to point from old > record to new record > o remove old record > > No matter how many time you reenter this, you end up with a > consistent view. Have you brought this up on the threads@ list? Assuming symbol lookup is indeed this simple, then I agree that this algorithm seems sound to me. -- John Baldwin <>< http://www.FreeBSD.org/~jhb/ "Power Users Use the Power to Serve!" - http://www.FreeBSD.org/