lkml.org 
[lkml]   [1998]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: test_and_set_bit() not atomic forever? [cli/sti in char/vt.c [patch]]
Hi Mike,

You are right, perhaps it's better to document this issue, so we can
avoid fruitless discussions in the future. Sorry about the length of
this post, though.

Mike Ford Ditto wrote:
>
> > > > test_and_set is *by* *definition* an atomic operation. However, some
> >
> > Does everyone agree on this? If so I'm going back to the original patch,
> > test_and_set feels so much simpler and to the point than these
> > atomic_dec_and_test, atomic_..., etc
>
> There seems to be some terminology confusion here. There are two kinds
> of atomicity... many CPUs provide an "atomic" test-and-set instruction
> which can not be interrupted (by interrupts, that is). These
> instructions usually are not atomic at the bus level, only at the CPU
> instruction level. Another bus master (a DMA device or another CPU) can
> access the same memory word in between the test and the set.

100% correct. CPUs will _usually_ finish an instruction before they
acknowledge an interrupt (some instructions involve many, many memory
accesses {e.g. string instructions, see below the x86 example} and so
can be interrupted). CPUs that implement a test_and_set opcode *always*
make it non-interruptible (obviously). Just a small caveat: this is not
called atomicity per se. Atomicity is what you describe in the next
paragraph:
> So another kind of atomicity is often provided which is guaranteed
> atomic even against other CPUs contending for the same word using the
> same mechanism. Some CPUs don't provide such a mechanism in hardware so
> it has to be implemented on top of spinlocks or somesuch device.

Just to make this clear: if an atomic test_and_set instruction is not
available, one can build it using either:

a) another atomic instruction, if the chip has one. The important point
is that the read-test/modify-write sequence is atomic. In this sense, a
minimal instruction set needs just a single atomic instruction; for
performance reasons, modern CPUs feature various atomic instructions.

b) disabling interrupts, running a small routine that does the
read-test/modify-write using the smallest possible number of
instructions, restoring interrupts. This may or may not be SMP-safe,
depending on the SMP implementation.

You can read the /include/generic/bitops.h by T. Ts'o, they are quite
neat and they show clearly that only the read-test/modify-write
instruction sequence is protected by cli()-sti().

>
> It looks like somebody needs to define and document which kind of
> atomicity is guaranteed by each of these various macros in Linux.

In fact, there is just one kind of atomicity: that in which the
read-test/modify-write sequence is guaranteed to be indivisible.

-----------x86 example - skip if you are not interested --------------
In the x86 architecture, most instructions are not interruptible.
Quoting from the Cyrix manual:

"With the exception of string operations, interrupts are acknowledged
[*only*] between instructions. Long string operations have interrupt
windows between memory moves that allow interrupts to be acknowledged."

Atomicity here is with regard to SMP. It is guaranteed under Linux using
the LOCK prefix (which you will find in the Linux i386
test_and_set_bit() function). Again quoting:

"The LOCK prefix may be placed before certain instructions that read,
modify, then write back to memory. The prefix asserts the LOCK# signal
to indicate to the external hardware that the CPU is in the process of
running multiple indivisible memory accesses. The LOCK prefix can be
used with the following instructions:

Bit Test Instructions (BTS,BTR,BTC).
Exchange Instructions (XADD,XCHG,CMPXCHG)
One-operand Arithmetical and Logical Instructions (DEC, INC, NEG, NOT)
Two-operand Arithmetical and Logical Instructions (ADC, ADD, AND, OR,
SBB, SUB, XOR)

An invalid opcode exception is generated if the LOCK prefix is used with
any other instruction, or with the above instructions when no write
operation to memory occurs (i.e. the destination is a register)."

----------end of x86 example: resume here ------------

The SPARC bitops.h code is ...hummm... interesting. It reads (quoting):

/* User mode bitops, defined here for convenience. Note: these are not
* atomic, so packages like nthreads should do some locking around these
* themself.
*/
So, under Linux-SPARC, test_and_set_bit() is *not* atomic. Perhaps this
is the example Pavel was looking for ? [1]

OTOH Linux-SPARC64 has atomic test_and_set_bit(), correctly implemented
as a sequence of instructions built around an atomic primitive, as
described above.

Summarizing: there is just one kind of atomicity. Depending on the
available hardware primitives and SMP requirements, it can be
implemented in different ways in the various architectures supported by
Linux.

I hope this clears this issue a bit, atomically speaking ;-)
------------------------
André Balsa
andrebalsa@altern.org
[1] The SPARC also doesn't have a 8253/82C54 based speaker port, so
Rafael's original patch was still correct in this respect.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu

\
 
 \ /
  Last update: 2005-03-22 13:42    [from the cache]
©2003-2014 Jasper Spaans. Advertise on this site