From owner-freebsd-arch Fri Jan 4 1:49:36 2002 Delivered-To: freebsd-arch@freebsd.org Received: from srv1.cosmo-project.de (srv1.cosmo-project.de [213.83.6.106]) by hub.freebsd.org (Postfix) with ESMTP id 9673D37B405; Fri, 4 Jan 2002 01:49:31 -0800 (PST) Received: (from uucp@localhost) by srv1.cosmo-project.de (8.11.6/8.11.6) with UUCP id g049nIq50937; Fri, 4 Jan 2002 10:49:18 +0100 (CET) (envelope-from ticso@cicely8.cicely.de) Received: from mail.cicely.de (cicely20.cicely.de [10.1.1.22]) by cicely5.cicely.de (8.12.1/8.12.1) with ESMTP id g049iGtx056967; Fri, 4 Jan 2002 10:44:17 +0100 (CET)?g (envelope-from ticso@cicely8.cicely.de) Received: from cicely8.cicely.de (cicely8.cicely.de [10.1.2.10]) by mail.cicely.de (8.11.0/8.11.0) with ESMTP id g049iFW15638; Fri, 4 Jan 2002 10:44:15 +0100 (CET) Received: (from ticso@localhost) by cicely8.cicely.de (8.11.6/8.11.6) id g049i8b08251; Fri, 4 Jan 2002 10:44:08 +0100 (CET) (envelope-from ticso) Date: Fri, 4 Jan 2002 10:44:07 +0100 From: Bernd Walter To: Matthew Dillon Cc: John Baldwin , Terry Lambert , Peter Jeremy , Michal Mertl , Bruce Evans , Mike Smith , arch@FreeBSD.ORG, Alfred Perlstein , Bernd Walter Subject: Re: When to use atomic_ functions? (was: 64 bit counters) Message-ID: <20020104104407.D5294@cicely8.cicely.de> References: <200201032320.g03NKEE73347@apollo.backplane.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200201032320.g03NKEE73347@apollo.backplane.com> User-Agent: Mutt/1.3.23i X-Operating-System: FreeBSD cicely8.cicely.de 5.0-CURRENT i386 Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG On Thu, Jan 03, 2002 at 03:20:14PM -0800, Matthew Dillon wrote: > There are a number of ways to do queue management without the use of > mutexes or locks or critical sections. The easiest is to use a fixed > length FIFO with a separate read and write index. > > struct { > struct foo *fifo[64]; > int read_index; > int filler[(cacheline calculation)]; > int write_index; > int filler[(cacheline calculation)]; > } Foo; > > If there is only one reader and one writer, only lazy synchronization > is necessary and no locks or mutexes are necessary at all. This isn't save for some SMP architectures - e.g. alpha. CPU-A writes fifo and updates write_index. Out of your control CPU-A now pushes the write_index to the memory, but not yet the new data in fifo. CPU-B now sees the new read_index and fetches left garbadge from the fifo. Even if you use atomic_ calls for write_index this doesn't necessarily influence fifo data. You have at to put an barrier between updating fifo and write_index. And another barrier after reading read_index just before reading fifo. You also create a latency problem as you never know when the reader sees the updated write_index. If you would update write_index atomic_ you request a coherent view for the complete cacheline and the next read request is gets the last value. > If there are multiple readers or multiple writers then it is possible > to use cmpexg type instructions and still avoid any locks or mutexes, > though in this case it is easier to simply use a mutex. No. A writer does: read the write_index write the fifo using the information from the write_index update the write_index If they aren't protected we end up writing the fifo on an already used location. > For example, if we have a per-cpu queue of pending interrupts our > interrupt handler can 'write' to the queue without any sort of > synchronization, mutexes, or locks, and other (idle or in-scheduler) > cpu's may compete to read from the queue by obtaining a mutex. But you shouldn't forget the barrier in the writer, otherwise the same problem as in the first example ariese. And you still never know when another CPU actualy sees the change. But you write to the queue in interrupt context. What happens if you write to the fifo and before you wrote the index a higher priorised interrupt gets handled? Effectivly you have multiplex writes as in the example before, but can't use mutexes because you are in interrupt context. What is missing here is blocking other interrupts to use the same queue. -- B.Walter COSMO-Project http://www.cosmo-project.de ticso@cicely.de Usergroup info@cosmo-project.de To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message