Paul Carpenter wrote:
> On Saturday, in article
>      <e...@4ax.com> k...@sci.fi
>      "Paul Keinanen" wrote:
> >On Sat, 14 May 2005 06:00:09 GMT, Neil Kurzman <n...@mail.asb.com>
> >wrote:
> >
> >>OK so how do you do a ring buffer without disabling interrupts
during RX read ,
> >> or a Tx write?
> >>The Interrupt could hit during that time.  The Keil C sample
disables RI
> >> during that time.
> >
> >The basic principle in avoiding interrupt disabling is to make sure
> >that only one partner updates a specific variable (unless the
hardware
> >supports some kind of interlocked manipulate and test instructions)
> >and maintaining a strict rules in which order variables are updated.
> >
> >One way of doing a ring buffer is to have two globally visible
> >pointers, one for writing and the other for reading the ring buffer.
> >
> >On the insertion side, first verify that there is space for at least
> >one byte in the ring buffer by comparing the visible pointers. Make
a
> >private copy (e.g. a register) of the write pointer, update it to
> >point to the first free location, insert the byte into that location
> >and finally copy the private pointer to the globally visible write
> >pointer. Depending on the OS, you might inform the reader about new
> >data e.g. by raising a signal.
> >
> >On the reading side, verify that there is at least one byte in the
> >buffer by comparing the publicly visible pointers. Extract the byte,
> >make a private copy (a register) of the read pointer, update it to
> >point to the next position and write the updated value to the
globally
> >visible read pointer.
>
> The only issue with using pointers (or indecii) on ring buffers is
the
> issue of when the pointers are identical knowing whether the buffer
> is full or empty. Especially on RX buffers as this is truely
aysnchronous
> to the system

For this you leave one slot empty, the empty condition is when both
pointers are equal and the full is when there is only one slot in
between.

> >When using C/C++, it is very important to declare the globally
visible
> >pointers with the volatile attribute to prevent the compiler from
> >optimising the pointer references.
>
> Better still keep all the functions related in one or two modules
where
> the only globally visible parts of that module are function calls and
> definitions (baud rates, error codes) and the like. The module will
need
> access to globally defined information like I/O registers. A second
module
> maybe needed to handle setting of timers or other external timers for
> baud rate generation depending on platforms.
>
> --
> Paul Carpenter          | p...@pcserviceselectronics.co.uk
> <http://www.pcserviceselectronics.co.uk/>;    PC Services
> <http://www.gnuh8.org.uk/>;              GNU H8 & mailing list info
> <http://www.badweb.org.uk/>;             For those web sites you hate

On Sat, 14 May 2005 13:22:53 +0100 (BST), paul$@pcserv.demon.co.uk
(Paul Carpenter) wrote:

>The only issue with using pointers (or indecii) on ring buffers is the
>issue of when the pointers are identical knowing whether the buffer
>is full or empty. Especially on RX buffers as this is truely aysnchronous
>to the system

That is only a problem, if you can not resist the temptation to use
the last free position in the ring buffer :-).

If you declare "buffer full" at N-1 elements in the buffer (instead of
at N elements), you can avoid the ambiguity.

Paul

Paul Carpenter wrote:
> The only issue with using pointers (or indecii) on ring buffers is the
> issue of when the pointers are identical knowing whether the buffer
> is full or empty. Especially on RX buffers as this is truely aysnchronous
> to the system

Not really. Just define that when the pointers are equal, the buffer is
empty. More generally, the number of items in the buffer is the difference
between the pointers modulo the buffer length. This simplification means
that your buffer needs no other state information besides the two pointers,
and each pointer is updated by only one process, so there's no need for
critical sections at all. Sure, this means that you can't fill that last
spot in the buffer, but if you really need that, you're probably running
too close to the edge for the system to be reliable anyway.

-- Dave Tweed

On Saturday, in article <4...@acm.org>
     d...@acm.org "David Tweed" wrote:

>Paul Carpenter wrote:
>> The only issue with using pointers (or indecii) on ring buffers is the
>> issue of when the pointers are identical knowing whether the buffer
>> is full or empty. Especially on RX buffers as this is truely aysnchronous
>> to the system
>
>Not really. Just define that when the pointers are equal, the buffer is
>empty. More generally, the number of items in the buffer is the difference
>between the pointers modulo the buffer length. This simplification means
>that your buffer needs no other state information besides the two pointers,
>and each pointer is updated by only one process, so there's no need for
>critical sections at all. Sure, this means that you can't fill that last
>spot in the buffer, but if you really need that, you're probably running
>too close to the edge for the system to be reliable anyway.

It is a common pitfall many people get wrong, that is why it was mentioned
in the context of the description I followed up on.

-- 
Paul Carpenter          | p...@pcserviceselectronics.co.uk
<http://www.pcserviceselectronics.co.uk/>;    PC Services
<http://www.gnuh8.org.uk/>;              GNU H8 & mailing list info
<http://www.badweb.org.uk/>;             For those web sites you hate

David Tweed wrote:
> Paul Carpenter wrote:
> 
>> The only issue with using pointers (or indecii) on ring buffers
>> is the issue of when the pointers are identical knowing whether
>> the buffer is full or empty. Especially on RX buffers as this is
>> truely aysnchronous to the system
> 
> Not really. Just define that when the pointers are equal, the
> buffer is empty. More generally, the number of items in the buffer
> is the difference between the pointers modulo the buffer length.
> This simplification means that your buffer needs no other state
> information besides the two pointers, and each pointer is updated
> by only one process, so there's no need for critical sections at
> all. Sure, this means that you can't fill that last spot in the
> buffer, but if you really need that, you're probably running too
> close to the edge for the system to be reliable anyway.

Not really, when you have uncoordinated processes accessing the
data at random times.  This will be the situation when you have,
for example, an interrupt driven process filling the buffer, and
another process emptying it.  In this case you need a critical
section, which you can implement by disabling and reenabling
interrupts.

   MAIN_PROCESS             INTERRUPT_PROCESS
   1: read input  ptr
      read output ptr
      compare ptrs
      if empty goto 1
      read output data
      increment output ptr
      write output ptr back
      other operations

                            2: read output ptr
                               read input ptr
                               compare ptrs
                               if full go to 2
                               write input data via ptr
                               advance ptr
                               write input ptr back
                               other operations

Now shuffle these two sequences around and intermix them, and you
will find that you have to make the decision sequence (up to
compare ptrs) critical sections.  The compares decide whether there
is data to be taken (not empty) or space to be filled (not full).

In some systems you can have other problems if the write actions
are not single operations, such as writing high and low bytes of
pointers, with interrupts between them.

You can interchange the roles of MAIN and INTERRUPT PROCESS, and
have the same problem.  In fact both may be interrupt driven (for
example by a background data transfer operation).  In that case the
natural inhibition of further interrupts during interrupt service
can implement the critical section function.

-- 
 Some informative links:
   news:news.announce.newusers
   http://www.geocities.com/nnqweb/
   http://www.catb.org/~esr/faqs/smart-questions.html
   http://www.caliburn.nl/topposting.html
   http://www.netmeister.org/news/learn2quote.html

On Sat, 14 May 2005 21:33:56 GMT, CBFalconer <c...@yahoo.com>
wrote:


>   MAIN_PROCESS             INTERRUPT_PROCESS
>   1: read input  ptr
>      read output ptr
>      compare ptrs
>      if empty goto 1
>      read output data
>      increment output ptr
>      write output ptr back
>      other operations
>
>                            2: read output ptr
>                               read input ptr
>                               compare ptrs
>                               if full go to 2
>                               write input data via ptr
>                               advance ptr
>                               write input ptr back
>                               other operations
>
>Now shuffle these two sequences around and intermix them, and you
>will find that you have to make the decision sequence (up to
>compare ptrs) critical sections.  The compares decide whether there
>is data to be taken (not empty) or space to be filled (not full).

   1: read input  ptr
                                     <--- interrupt updates input ptr
      read output ptr
      compare ptrs
      if empty goto 1

The only problem here is that you get the "empty" indication, even
though there would be a value available at the time of the compare
instruction. In a polled system like this, the pending value would be
extracted at the next cycle anyway.

>In some systems you can have other problems if the write actions
>are not single operations, such as writing high and low bytes of
>pointers, with interrupts between them.

With extremely primitive processors you would have to perform the
comparison byte by byte, first compare the high bytes of the pointers
and then the low bytes of these two pointers. If the insertion "full"
check is needed on the interrupt side, then a critical section is
indeed needed. 

The "empty" check on the main program side can be done by reading the
high and low bytes multiple times until the same value is returned in
two consecutive reads. Since we are interested only if in and out
pointer have the same value, a difference in either byte would
indicate that the buffer is not empty when the input pointer is
compared twice. Thus the only need for a critical section would be the
input overflow test, if such overflows can happen or the "overflow"
status is needed.
    
For complex processors allowing unaligned access, partial pointer
update would be a problem if the pointers are unaligned and thus split
into two memory words, especially at the cache line border or virtual
memory page boundary. Using aligned pointers solves this problem,
especially with packed structures, the pointers should be placed in
the beginning of structure to ensure proper alignment. 

Paul
 

CBFalconer wrote:

> David Tweed wrote:
>> Paul Carpenter wrote:
>> 
>>> The only issue with using pointers (or indecii) on ring buffers
>>> is the issue of when the pointers are identical knowing whether
>>> the buffer is full or empty. Especially on RX buffers as this is
>>> truely aysnchronous to the system
>> 
>> Not really. Just define that when the pointers are equal, the
>> buffer is empty. More generally, the number of items in the buffer
>> is the difference between the pointers modulo the buffer length.
>> This simplification means that your buffer needs no other state
>> information besides the two pointers, and each pointer is updated
>> by only one process, so there's no need for critical sections at
>> all. Sure, this means that you can't fill that last spot in the
>> buffer, but if you really need that, you're probably running too
>> close to the edge for the system to be reliable anyway.
> 
> Not really, when you have uncoordinated processes accessing the
> data at random times.  This will be the situation when you have,
> for example, an interrupt driven process filling the buffer, and
> another process emptying it.  In this case you need a critical
> section, which you can implement by disabling and reenabling
> interrupts.
> 
>    MAIN_PROCESS             INTERRUPT_PROCESS
>    1: read input  ptr
>       read output ptr
>       compare ptrs
>       if empty goto 1
>       read output data
>       increment output ptr
>       write output ptr back
>       other operations
> 
>                             2: read output ptr
>                                read input ptr
>                                compare ptrs
>                                if full go to 2
>                                write input data via ptr
>                                advance ptr
>                                write input ptr back
>                                other operations
> 
> Now shuffle these two sequences around and intermix them, and you
> will find that you have to make the decision sequence (up to
> compare ptrs) critical sections.  The compares decide whether there
> is data to be taken (not empty) or space to be filled (not full).

I certainly hope you would never recommend a potential infinite loop inside
an ISR. Your ISR code really should produce an error if the buffer is full.
> 
> In some systems you can have other problems if the write actions
> are not single operations, such as writing high and low bytes of
> pointers, with interrupts between them.
> 

This is commonly known as the shared data problem and can occur whenever two
independent processes share data and the operations on the data are not
atomic.

Ian

Paul Keinanen wrote:

snip
> 
>    1: read input  ptr
>                                      <--- interrupt updates input ptr
>       read output ptr
>       compare ptrs
>       if empty goto 1
> 
> The only problem here is that you get the "empty" indication, even
> though there would be a value available at the time of the compare
> instruction. In a polled system like this, the pending value would be
> extracted at the next cycle anyway.
> 

Depends, if the read of each pointer is not atomic i.e. requires more than
one instruction, then it can be interrupted part way through the read, its
value altered then the read completed. This is the well known shared data
problem.

Ian

Ian Bell wrote:
> 
... snip ...
> 
> I certainly hope you would never recommend a potential infinite
> loop inside an ISR. Your ISR code really should produce an error
> if the buffer is full.

Of course not.  That was just to illustrate the cause of the
problems.  You have all sorts of mechanisms, including signal/wait,
monitors, etc. available.

-- 
 Some informative links:
   news:news.announce.newusers
   http://www.geocities.com/nnqweb/
   http://www.catb.org/~esr/faqs/smart-questions.html
   http://www.caliburn.nl/topposting.html
   http://www.netmeister.org/news/learn2quote.html

CBFalconer wrote:
> Ian Bell wrote:
> >
> ... snip ...
> >
> > I certainly hope you would never recommend a potential infinite
> > loop inside an ISR. Your ISR code really should produce an error
> > if the buffer is full.
>
> Of course not.  That was just to illustrate the cause of the
> problems.  You have all sorts of mechanisms, including signal/wait,
> monitors, etc. available.

Or some counter is incremented each time a new item is placed in
the buffer. The sender increments the counter that the receiver
reads and stores in a local variable. On the next cycle
the receiver checks the counter against its local variable
in order to see if new items were added to the buffer.

The receiver reads the counter but never writes to it, thus it
needs not to be protected by a semaphore or the like.

The receiver then reads the data and increments another counter.
The sender will check that counter in order to verify that the
buffer is not full.

This works well if you have a periodic activation of the receiver
or if the sender activates the receiver whenever the counter is
incremented.

The counter must be incremented once the data has been put to
the buffer not before. Then if the sender is interrupted by
the receiver after the data were written but before the counter
was incremented, the receiver will not retrieve them since
the counter will be equal to the local value.