Re: [Valgrind-users] New experimental skin: signal handler checker

[John R. <jr...@Bi...>]

Jeremy Fitzhardinge wrote:
> On Mon, 2003-08-18 at 06:59, John Reiser wrote:
>>Even in more complicated situations, a circular buffer between the
>>signal handler as producer and the mainline code as consumer,
>>would violate the rule about "no touching" the control pointers
>>of the circular buffer.
> 
> 
> Well, surely the buffer pointer updates need to be protected, unless
> you're using strictly atomic operations?


No, the buffer pointer updates do not need to be "protected".  As long
as the width of the pointer equals the width of the memory bus [or pointer
is narrower and the memory has natural operations of that width, and the
code uses them], and the storage for the pointer itself is naturally aligned
[width divides address], then ordinary load and store operations suffice.
This is commonly the case; the significant exceptions are on "8-bit"
(or less) microcontrollers where a pointer is wider than the memory bus.
It may be argued that this makes the ordinary read+write of the control
pointers "strictly atomic", but that is much of the point.  The ordinary
operations are enough; you don't need privilege, assembly code, a special
compiler, or special tricks.

This a major point of a [properly implemented] circular buffer.  No bus
interlock, no compare-and-swap, no semaphore.  Ordinary load and store
are atomic enough.  The interlocks are implicit in the logic of the
control pointers.

For review: A circular buffer implements a one-way reliable channel
between two process[es|ors] having read+write access to a common
memory, without any hardware interlocks except ordinary read+write
memory operations that are monotonic in time-causality.
The buffer consists of a region of memory and four indices:
FIRST, IN, OUT, LAST.  At all times FIRST <= IN <= OUT <= LAST.
FIRST and LAST are constant for the duration of the channel.  Only
the producer writes IN, and only the consumer writes OUT.
If OUT==IN then the buffer is empty.  If OUT < IN then the region
beginning at memory[OUT] and extending upto, but not including,
memory[IN] has data from the producer for the consumer.  If
IN < OUT then the region beginning at memory[OUT] and continuing
upto, but not including, memory[LAST] has the first part of data,
and the region from memory[FIRST] upto, but not including,
memory[IN] has the second part of data from the producer for the
consumer.  Both the producer and consumer can operate simultaneously
and achieve reliable one-way communication with low overhead.

An early commercial implementation appeared in the Control Data
Corporation (CDC) 6600/6500/6400 machines in the late 1960s.
They had 11 or 12 processors: 1 or 2 CPU, plus 10 PPU (Peripheral
Processor Unit).  Each PPU had a 4K-word (18 bit) memory of its own,
plus access to the 60-bit wide main memory.  All I/O channels were
connected to the PPUs, and not to the main CPU memory. Ordinarily,
user code ran only on the CPU, and only the operating system ran PPUs.
The only hardware interlock in the machine was the power-up lock
which disabled every processor except PPU0 for system initialization.

All I/O to/from main memory was conducted by a PPU using a circular
buffer in main memory.  The protocol was such that it was possible
to stream a magnetic tape drive (10.5 inch reel of 0.5 inch tape,
2400 feet long, 556/800/1600 char-per-inch) and have a block size of
30 megabytes [the whole tape, with no inter-record gaps], with a user-
mode program in the CPU doing meaningful processing of the data [not
just copying].  The usual case with records of a few kilobytes or less
[and gaps of a fraction of an inch with no data on the tape, which
enabled the drive to start and stop if necessary without losing data]
was even easier to stream.