Date: Fri, 4 Jan 2002 10:44:07 +0100 From: Bernd Walter <ticso@cicely8.cicely.de> To: Matthew Dillon <dillon@apollo.backplane.com> Cc: John Baldwin <jhb@FreeBSD.ORG>, Terry Lambert <tlambert2@mindspring.com>, Peter Jeremy <peter.jeremy@alcatel.com.au>, Michal Mertl <mime@traveller.cz>, Bruce Evans <bde@zeta.org.au>, Mike Smith <msmith@FreeBSD.ORG>, arch@FreeBSD.ORG, Alfred Perlstein <bright@mu.org>, Bernd Walter <ticso@cicely9.cicely.de> Subject: Re: When to use atomic_ functions? (was: 64 bit counters) Message-ID: <20020104104407.D5294@cicely8.cicely.de> In-Reply-To: <200201032320.g03NKEE73347@apollo.backplane.com> References: <XFMail.020103145704.jhb@FreeBSD.org> <200201032320.g03NKEE73347@apollo.backplane.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020104104407.D5294>