Searching \ for 'Wanted: two ring buffers on PIC, in assembly' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'Wanted: two ring buffers on PIC, in assembly'.

Truncated match.
PICList Thread
'Wanted: two ring buffers on PIC, in assembly'
1998\07\21@142943 by Peter L. Peres

picon face
Hello,

 I have a small question re: $SUBJ. PICs with interrupts often act as
dumb bridges between SPI/RS232/I2C and whatnot. I happen to be doing such
a thing right now. I have run into a small problem: There is only one
index register on a PIC.

 I need 2 small ring buffers, one for each direction, and maybe a third
one for commands. There being only one FSR, I was thinking of 2 ways to
ensure atomic access to the rings:

1. polling. It works, but it's an ugly interleaved state machine, because
I do RS232 with bit-bashing.

2. interrupt driven drivers for each source (4 sources in all: 2 tx 2 rx)
and polling supervisor task with error checking/flagging for the interrupt
drivers.

 So, for #2: I want to use a mutex driver (no interrupts allowed while in
any driver), grab FSR, use it as an index to read/write from the
respective ring, and exit asap, re-enabling interrupts. I'd use a flag
register in which each ISR 'signs', but not before checking the previous
signature. If it is its own, then something is wrong and the task should
signal this to the supervisor using another flag. The supervisor would
spin around this flag and test Test Inputs and do some LED flashing if the
flag(s) are set. I figure 10-15 T's per ISR this way.

 The RS232 bit-bashing task would be triggered by a timer interrupt at a
constant rate, at 3 x bit rate (2400 Bauds * 3 ~= 100 usec). The theory
says that 4 15 T ISRs should co-operate peacefully under these conditions,
at a load of about 70%.

 Questions: Before I commit serious time to do this, can any1 point out
something that I'm missing here, and whether there is something already
done on this (an AN ?). Also, is there a SMALL PIC with SPI ? The only
choice I have for now is C64, which is going to be VERY poorly used.

thanks,

       Peter

1998\07\21@223317 by Eric Smith

flavicon
face
"Peter L. Peres" <spam_OUTplpTakeThisOuTspamACTCOM.CO.IL> wrote:
>   I need 2 small ring buffers, one for each direction, and maybe a third
> one for commands. There being only one FSR, I was thinking of 2 ways to
> ensure atomic access to the rings:

Peter,

I think you might be going overboard in your synchronization.  If you
use three variables per ring, there is no synchronization problem.

For each ring, you have an input pointer, an output pointer, and a
count of how many characters are in the ring.  In theory you don't need
the count if you have some other way to disambiguate ring empty from ring
full conditions.  However, by using the count, the only mutual exclusion
safeguard that is necessary is to only do atomic increments and decrements
on the count.  Since the incf and decf instruction of the PIC are atomic,
this requirement is satisfied.

If you didn't have the count, the code would need a bunch of comparisons
between the input and output pointers, and a semaphore (or disabling
interrupts) would be necessary becase the PIC has no atomic instruction to
compare to register file locations.

The code that inserts characters into the ring does this:

 if (count < max)  /* note: it doesn't matter that this test is not atomic */
   {
     FSR = input_pointer;
     *FSR = character;
     input_pointer++;
     if (input_pointer == end_of_buffer)
       input_pointer = start_of_buffer;
     count++;  /* this increment MUST be atomic! */
   }

The code that extracts characters does this:

 if (count > 0)  /* note: it doesn't matter that this test is not atomic */
   {
     FSR = output_pointer;
     character = *FSR;
     output_pointer++;
     if (output_pointer == end_of_buffer)
       output_pointer = start_of_buffer;
     count--;  /* this decrement MUST be atomic! */
   }

Note that only the count variable is shared between the input and output
processes.

An example of PIC code using this technique to manage two ring buffers,
along with a macro to advance a ring buffer pointer and wrap it if
necessary, is available at:

       http://www.brouhaha.com/~eric/pic/uarttest.html

Cheers,
Eric

1998\07\22@125450 by Peter L. Peres

picon face
On Wed, 22 Jul 1998, Eric Smith wrote:

> I think you might be going overboard in your synchronization.  If you
> use three variables per ring, there is no synchronization problem.
- snip -

Eric, thank you for your insight, but I'd like to use only 2 variables per
ring, both pointers. (The length of ea. ring will be hard-coded). My
system of allowing only 1 interrupt served at a time (no stacking
concurrent ISRs) guarantees atomic access to these. It also guarantees
that the supervisor can call subroutines without running out of stack. I
am used to set head==end for empty ring. Also, this has to be assembly (I
don't use C or BASIC on PICs, and usec-timing is 1/2 of my life ;).

Peter

1998\07\22@142738 by Andy Kunz

flavicon
face
>Eric, thank you for your insight, but I'd like to use only 2 variables per
>ring, both pointers. (The length of ea. ring will be hard-coded). My

You can use 2 pointers and no counters, but it means you have to do more
calculations --> more time.

The _length_ isn't the problem he's referring to, it's the "fullness" of
the ring.

Andy

==================================================================
Andy Kunz - Statistical Research, Inc. - Westfield, New Jersey USA
==================================================================

1998\07\22@145539 by Mike Keitz

picon face
On Wed, 22 Jul 1998 18:37:25 +0000 "Peter L. Peres" <.....plpKILLspamspam@spam@ACTCOM.CO.IL>
writes:

>
>Eric, thank you for your insight, but I'd like to use only 2 variables
>per
>ring, both pointers. (The length of ea. ring will be hard-coded)

Usually I just use two pointers for a buffer, when it is empty the output
pointer equals the input pointer.  It doesn't seem worth the complexity
to be able to fill the buffer to the last byte (requiring another
variable besides the two pointers to distingush "full" from "empty").
Just accept that the useful capacity will be one less than the number of
locations reserved.

If your reading routine finds the pointers are not equal, it is defintely
safe to remove an element from the buffer.  If the writing routine finds
that In <> Out-1, it is definitely safe to store an element in the
buffer.  If the full/empty testing reads the "other pointer" (In for the
read routine, Out for the store routine) only once as part of the test,
it should be safe to interrupt either routine and do the other routine.

You could simulate indirect access for reading a small buffer by using a
computed goto into a table of MOVFW's, one for each buffer location--

[have buffer index * 2 in W here]
       addwf   PCL,f
       movfw   buffer+0
       return
       movfw   buffer+1
       return
[etc].

I don't see a good way for writing other than using FSR and INDF since W
needs to be used to set up the PC modification.



_____________________________________________________________________
You don't need to buy Internet access to use free Internet e-mail.
Get completely free e-mail from Juno at http://www.juno.com
Or call Juno at (800) 654-JUNO [654-5866]

1998\07\22@153915 by Eric Smith

flavicon
face
I wrote:
> I think you might be going overboard in your synchronization.  If you
> use three variables per ring, there is no synchronization problem.

"Peter L. Peres" <plpspamKILLspamACTCOM.CO.IL> replied:
> Eric, thank you for your insight, but I'd like to use only 2 variables per
> ring, both pointers. (The length of ea. ring will be hard-coded). My
> system of allowing only 1 interrupt served at a time (no stacking
> concurrent ISRs) guarantees atomic access to these. It also guarantees
> that the supervisor can call subroutines without running out of stack. I
> am used to set head==end for empty ring. Also, this has to be assembly (I
> don't use C or BASIC on PICs, and usec-timing is 1/2 of my life ;).

I think you may have overlooked a few points.

1)  I only use three variables per ring.  I know you want to use only two,
   but your reply suggests to me that you thought I was using a bunch.

2)  My code is assembly.  I posted C code to explain the concept.  The
   assembly code is available at the URL given in my original post.  I
   *never* use anything but assembly on PICs.  Nanosecond timing is my life.
   Using three variables makes the code faster.

3)  My code doesn't involve any unnecessary subroutine calls in the ring
   management.  It's not going to cause stack problems.

4)  If you are using only the two pointers (no count), and head==end for
   empty, the test for ring full gets complicated:

     if ((head+1) != tail)
       {
         /* OK, we can stick another item in the buffer here */
         buffer [head] = data;
         head = head + 1;
         if (head > end_of_buffer)
           head = start_of_buffer;
       }
     else
       {
         /* oops, the ring is already full */
       }

   doesn't work because head may be pointing to the last location of the
   ring.  The comparison must actually do something like this:

     temp = head + 1;
     if (temp > end_of_buffer)
       temp = start_of_buffer;
     if (temp != tail)
       {
         /* OK, we can stick another item in the buffer here */
         buffer [head] = data;
         head = temp;
       }
       {
         /* oops, the ring is already full */
       }

   or perhaps:

     temp = head;
     head = head + 1;
     if (head > end_of_buffer)
       head = start_of_buffer;
     if (head != tail)
       {
         /* OK, we can stick another item in the buffer here */
         buffer [temp] = data;
       }
     else
       {
         /* oops, the ring was already full, back up the head pointer */
         head = head - 1;
         if (head < start_of_buffer)
           head = end_of_buffer;
       }

   Using my three-variable scheme, this is not necessary.

5)  The PIC doesn't well support nested interrupts.  You comment about
   the interrupt guaranteeing atomic access to the pointer is correct as
   far as the interrupt handler is concerned.  However, in most applications
   one of the users of the ring (either the producer or the consumer) tends
   to be run at non-interrupt time.  Therefore it is necessary to carefully
   scrutinize the use of the pointers at non-interrupt time.  It may be
   necessary to disable interrupts around the non-interrupt code that
   accesses the ring.

   Disabling the interrupts on a PIC is actually tricky.  If an interrupt
   happens just as you are clearing the GIE bit, it may not get cleared.
   This is a known problem, and is covered in the Microchip data sheets and
   application notes.  You have to use a loop to clear the GIE bit:

     cleargie:  bcf   intcon,gie
                btfsc intcon,gie
                goto  cleargie

   (If you are *sure* that back-to-back interrupts can't happen, you can
   get by with two consecutive "bcf intcon,gie" instructions.)

   Using my three-variable scheme, it is not necessary to disable interrupts
   when accessing the ring from non-interrupt code.

Cheers,
Eric

1998\07\22@184442 by Peter L. Peres

picon face
On Wed, 22 Jul 1998, Andy Kunz wrote:

> >Eric, thank you for your insight, but I'd like to use only 2 variables per
> >ring, both pointers. (The length of ea. ring will be hard-coded). My
>
> You can use 2 pointers and no counters, but it means you have to do more
> calculations --> more time.
>
> The _length_ isn't the problem he's referring to, it's the "fullness" of
> the ring.

My code to handle the pointer looks like this (f. example) (HEADP is
initialized to RINGBOTTOM at start, but the 1st and not the 0th location
is used during the 1st ring spin only):

(Code snippet #1) (13 W, 14 T, uses one file: HEADP, constant run time)

SomeISR
       ; handle specific interrupt here

       ; increment head pointer and wrap
       incf    HEADP, W
       addlw   100h - RINGTOP  ; some PICs can't sublw

       btfsc   PSW, ZF
       addlw   RING_BOTTOM - RING_TOP  ; negative: ignore carry (mod 100h)

       addlw   RING_TOP

       movwf   HEADP           ; pointer is now ok
       movwf   FSR             ; also index reg, used later

       ; compare to tail
       subwf   TAILP, W
       btfsc   PSW, ZF
       goto    HandleException ; stepped on the tail

       ; good code continues here
       movf    INREG, W
       movwf   FSRP            ; FSRP is R0 in my mnemonic notation

       ; return fm. interrupt via common interrupt-enable code
       goto    AllDoneISR

You are suggesting that I use a counter to keep track, which would indeed
make the code for the pointer arithmetics shorter, but would make me have
to add a constant every time i use FSR, to convert the index into an
address. That code would be:

(Code snippet #2) (14 W, 15 T, uses one file: HEADP, constant run time)

SomeISR
       ; handle interrupts here

       ; handle pointer, HEADP indexes ring top, ring grows downwds.
       movf    HEADP, W
       decfsz  HEADP, W
       goto    DontWrap
       movlw   RINGTOP         ; reload top

DontWrap
       movwf   HEADP
       movwf   FSR

       subwf   TAILP, W
       btfsc   PSW, ZF
       goto    HandleException

       movlw   RING_OFFSET
       addwf   FSR, F ; can one do this ?

       ; move data into ring
       movf    INPUTREG, W
       movwf   FSRP ; FSRP is file #0

       ; done, jump to common exit code
       goto    AllExitISR

Now, you say that I should use a pointer AND a counter:

(Code snippet #3) (16 W, 13/16 T, uses 2 files: HEADC, HEADP, n/c run
time)

SomeISR
       ; handle interrupts here

       ; increment pointer, and wrap
       decfsz  HEADC, W
       goto    DontWrap

       ; wrap: reload
       movlw   RING_SIZE
       movwf   HEADC
       movlw   RING_BOTTOM - 1
       movwf   HEADP

DontWrap
       incf    HEADP, F
       movf    HEADP, W
       movwf   FSR

       ; caught tail ?
       subwf   TAILP, W
       btfsc   PSW, ZF
       goto    HandleException

       ; transfer data
       movf    INPUT_REG, W
       movwf   FSRP ; FSRP == R0

       ; done, jump to common exit code
       goto    AllDoneISR

imho, my approach (snippet #1) leads, but smb. may beat me to it ;)
Opinions ? (BTW, I was taught that Occam's razor is very sharp. The less
things you move in your passing, the easier the going <G>).

Peter

PS: Sorry for the longish email.

PS2: warning: None of the code was tested. It is 11 PM after a long day.
Numbers are quoted off of my head.

1998\07\22@224346 by Eric Smith

flavicon
face
"Peter L. Peres" <.....plpKILLspamspam.....ACTCOM.CO.IL> writes:
> My code to handle the pointer looks like this (f. example) (HEADP is
> initialized to RINGBOTTOM at start, but the 1st and not the 0th location
> is used during the 1st ring spin only):

[code to add a byte to a ring buffer from an ISR deleted]

OK.  Now suppose that the producer is non-interrupt code, and the consumer
is the ISR (as would often be the case for a serial transmitter).

Unless you disable interrupts between when you update HEADP and when you decide
whether the ring was full (and correct HEADP if it was), there is a race
condition which can occur causing the receive interrupt handler to believe
the ring is empty when in fact it is full.

The three variable case may take a cycle or three longer, but it has less
code because it deals with buffer full conditions more elegantly, and avoids
the potential race condition without needing to disable interrupts.

The code I'm actually using is faster than yours because its macros use
shortcuts where possible due to special cases of buffer size and alignment.

The macro I use for advancing a ring pointer takes six instructions and cycles
(same as yours), except that it detects a case where it can optimize to two
instructions.

The macros I use for detecting that a ring is full take three cycles, unless
the size of the ring happens to be a power of two, in which case it only
takes one cycle.  (This macro is not yet in the code on my web site; I'll
update it within the next few days.)

Some of this optimization can undoubtedly be done to your code as well, but
I don't think there's an easy way to avoid the race condition without
either disabling interrupts or using an extra RAM location for temporary
storage of HEADP.

If you never need to access rings from non-interrupt code, and you're not
using nested interrupts, there is no race condition.  However, in my
experience usually at least one of the users of the ring is non-interrupt
code.

Cheers,
Eric

1998\07\22@233441 by Mike Keitz

picon face
On Thu, 23 Jul 1998 02:31:37 -0000 Eric Smith <EraseMEericspam_OUTspamTakeThisOuTBROUHAHA.COM> writes:

>Unless you disable interrupts between when you update HEADP and when
>you decide
>whether the ring was full (and correct HEADP if it was), there is a
>race
>condition which can occur causing the receive interrupt handler to
>believe
>the ring is empty when in fact it is full.

I found it simplest to work around this problem by not allowing the
buffer to become completely full, so the condition of head=tail always
indicates it is empty.  The code is quite simple and fast and there is no
need to disable interrupts if things are done in the proper order.  The
buffer will become "full" one store early so if 16 locations are
reserved, only 15 are ever in use.  But this is offest by not needing to
keep any buffer-related variables other than the two pointers.  If the
buffer is small enough the two pointers can be packed into one byte.

Producer:

buffer[tail] = data   (This is always legal, since buffer is never full.)
temp = (tail+1) mod SIZE
If head = temp, buffer will be overfull.  Do not update tail yet.
otherwise tail = temp

Rather than use a temporary variable, it may be faster to just compute
(tail+1) mod SIZE twice, especially if SIZE is a power of two.  Don't try
any add/subtract or xor games with 'head' since the consumer ISR may
change it at any time.

Consumer:

If head=tail, buffer is empty.
otherwise data = buffer[head]
          head = (head+1) mod SIZE


The producer routine can interrupt the consumer or vice versa at any time
(In this version, the consumer must be able to interrupt the producer in
order to make it stop waiting if the buffer is full).  If the first byte
is being placed in the buffer the producer routine is interrupted before
tail is updated, the consumer will just think the buffer is empty.

In some situations, it is possible to guarantee that the buffer will
never overfill.  For example, serial data is being sent at a certain
rate, and the application never queues more than the size of the buffer
(-1) at a time before it is certain to be sent.  In that case it would be
possible to omit the check for full.  Do that at your own risk!


_____________________________________________________________________
You don't need to buy Internet access to use free Internet e-mail.
Get completely free e-mail from Juno at http://www.juno.com
Or call Juno at (800) 654-JUNO [654-5866]

1998\07\23@064732 by Caisson

flavicon
face
----------
> Van: Mike Keitz <mkeitzspamspam_OUTJUNO.COM>
> Aan: @spam@PICLISTKILLspamspamMITVMA.MIT.EDU
> Onderwerp: Re: Wanted: two ring buffers on PIC, in assembly
> Datum: woensdag 22 juli 1998 20:45

[Cut]

{Quote hidden}

ReadPtr := Ptr to byte to read  ( Post-increment )
WritePtr := Ptr to byte last written  ( Pre-increment ! )

For Reading : ReadPtr <> WritePtr -> OK to Read
For Writing : WritePtr +1 <> ReadPtr -> OK to Write

Result : The full buffer is used

Greetz,
 Rudy Wieser

1998\07\23@122301 by Peter L. Peres

picon face
On Thu, 23 Jul 1998, Caisson wrote:

> ReadPtr := Ptr to byte to read  ( Post-increment )
> WritePtr := Ptr to byte last written  ( Pre-increment ! )
>
> For Reading : ReadPtr <> WritePtr -> OK to Read
> For Writing : WritePtr +1 <> ReadPtr -> OK to Write
>
> Result : The full buffer is used
>
> Greetz,
>   Rudy Wieser

The full buffer is used all the time with my code, except when it is empty
and the consumer is fooled by reading the HEADP before it increments, into
thinking it is still empty. This is of no further consequence here.

If the head steps on the tail, there is an overrun, and if the tail steps
on the head, it's empty.

Peter

1998\07\23@122313 by Peter L. Peres

picon face
On Thu, 23 Jul 1998, Eric Smith wrote:

> "Peter L. Peres" <KILLspamplpKILLspamspamACTCOM.CO.IL> writes:
> > My code to handle the pointer looks like this (f. example) (HEADP is
> > initialized to RINGBOTTOM at start, but the 1st and not the 0th location
> > is used during the 1st ring spin only):
>
> [code to add a byte to a ring buffer from an ISR deleted]
>
> OK.  Now suppose that the producer is non-interrupt code, and the consumer
> is the ISR (as would often be the case for a serial transmitter).

I have stated clearly that all the code snippets that handle the ring
buffers are ISRs in my case, in the 1st message. In your case, it is very
trivial to implement a mutex flag on the pointer that is physically set by
the non-interrupt code before tampering with it.

- snip -
> The three variable case may take a cycle or three longer, but it has less
> code because it deals with buffer full conditions more elegantly, and avoids
> the potential race condition without needing to disable interrupts.

Ok, I understand, but one usually runs out of registers before running out
of program space on a PIC. So using one pointer instead of 3 is a net
advantage imho.

> The code I'm actually using is faster than yours because its macros use
> shortcuts where possible due to special cases of buffer size and alignment.

That's cheating <g>. I know how to do that (ring size is 2's power, ring
start aligned on a paragraph start of that size ;).

> The macro I use for advancing a ring pointer takes six instructions and cycles
> (same as yours), except that it detects a case where it can optimize to two
> instructions.

I don't like code with non-constant run time because I often do
bit-bashing and I have better things to do than figure timing
compensations for a library I wrote 3 months ago. Apart from that, you win
;)

> Some of this optimization can undoubtedly be done to your code as well, but
> I don't think there's an easy way to avoid the race condition without
> either disabling interrupts or using an extra RAM location for temporary
> storage of HEADP.

You are right, but instead, I can use a flag set by this code that
stops the other concurrent at a spinlock, while it is running. It's easier
to lock the access than to make it atomic in this case, especially since
the run time of the code is small and known.

I'm looking over my code again (snippet #1), and I can say that I believe
that there will be no race, at most the consumer will think that the ring
is one 'shorter' than it really is. Since both pieces of code update in
the same sequence type, it is guaranteed that the TAILP will not advance
past HEADP. The fact that the consumer will think that the ring is empty
while it is not, is of no consequence (the consumer is driven by a timer,
and will come looking again).

> If you never need to access rings from non-interrupt code, and you're not
> using nested interrupts, there is no race condition.  However, in my
> experience usually at least one of the users of the ring is non-interrupt
> code.

If there is only one writer and many readers then there is no problem with
this, even if not locked, in my case. If it is necessary for the consumer
to know about contiguous data, then the producer can use some sort of flag
or an end marker symbol.

Peter

1998\07\23@145951 by Eric Smith

flavicon
face
"Peter L. Peres" <RemoveMEplpTakeThisOuTspamACTCOM.CO.IL> wrote:
> I have stated clearly that all the code snippets that handle the ring
> buffers are ISRs in my case, in the 1st message. In your case, it is very
> trivial to implement a mutex flag on the pointer that is physically set by
> the non-interrupt code before tampering with it.
...
> You are right, but instead, I can use a flag set by this code that
> stops the other concurrent at a spinlock, while it is running. It's easier
> to lock the access than to make it atomic in this case, especially since
> the run time of the code is small and known.

No, that won't help because you can't use a spin-lock in the interrupt
handler to wait for the non-interrupt code to complete.  The only ways to
solve the specific problem I described are to either disable interrupts
around a portion of the non-interrupt "producer" code, or modify the
ISR "consumer" code to not advance HEADP until it is sure there is room
in the buffer.

> Ok, I understand, but one usually runs out of registers before running out
> of program space on a PIC. So using one pointer instead of 3 is a net
> advantage imho.

You haven't explained how you can do a ring buffer with one pointer.  Your
code had two variables, both of which are pointers.  My code has three, of
which two are the same pointers you use, and one is a count.  Admittedly
that is 50% more overhead than you have.

> I don't like code with non-constant run time because I often do
> bit-bashing and I have better things to do than figure timing
> compensations for a library I wrote 3 months ago. Apart from that, you win
> ;)

My code has constant run time; at assembly time the macro generates the
appropriate case.  When I need to know exactly how many cycles it will
take, I explicitly use "org" pseudo-ops and an "assert" macro to guarantee
that my ring buffer meets the size and alignment conditions needed for the
fast case.  Or (alternately), to guarantee that it doesn't.

> I'm looking over my code again (snippet #1), and I can say that I believe
> that there will be no race, at most the consumer will think that the ring
> is one 'shorter' than it really is. Since both pieces of code update in
> the same sequence type, it is guaranteed that the TAILP will not advance
> past HEADP. The fact that the consumer will think that the ring is empty
> while it is not, is of no consequence (the consumer is driven by a timer,
> and will come looking again).

In your case that is so.  In the hypothetical case I suggested, where the
serial transmit ISR thinks the ring is empty, the race condition can matter.
Usually the serial transmit ISR will disable the transmit interrupt if the
ring is empty, and the non-interrupt code that adds queues bytes for
transmission will enable the interrupt if the queue was empty.  But if the
transmit ISR every falsely believes the ring is empty, the transmit queue will
never get restarted.  Unless you add an otherwise unnecessary timer poll, or
you have the producer always enable interrupts when it queues bytes for
transmit.  The latter sounds appealing, but it can actually cause another race
condition.

I understand that your situation is different that the one I describe, and
that your solution works well for the constrained case that ring access is
only done by ISRs.  My point is that I don't believe it is a good solution for
the more general case where ring access is possible from non-ISR code.
Therefore I think it is a disservice to describe your solution without very
explicitly stating the limitations, because it could cause someone to spend
an inordinate amount of time debugging the potential race condition.

Cheers,
Eric

1998\07\24@084236 by Peter L. Peres

picon face
On Thu, 23 Jul 1998, Eric Smith wrote:

> "Peter L. Peres" <spamBeGoneplpspamBeGonespamACTCOM.CO.IL> wrote:
> ...
> > You are right, but instead, I can use a flag set by this code that
> > stops the other concurrent at a spinlock, while it is running. It's easier
> > to lock the access than to make it atomic in this case, especially since
> > the run time of the code is small and known.
>
> No, that won't help because you can't use a spin-lock in the interrupt
> handler to wait for the non-interrupt code to complete.  The only ways to

Of course the spin-lock is in the non-interrupt code.

> solve the specific problem I described are to either disable interrupts
> around a portion of the non-interrupt "producer" code, or modify the
> ISR "consumer" code to not advance HEADP until it is sure there is room
> in the buffer.

But that's exactly what it does now.

> > Ok, I understand, but one usually runs out of registers before running out
> > of program space on a PIC. So using one pointer instead of 3 is a net
> > advantage imho.
>
> You haven't explained how you can do a ring buffer with one pointer.  Your

By using a start and end marker character, and it's not very efficient,
unless writes are always made at the ring bottom, with variable lengths.
OTOH this is often the case with messages issued by an embedded system
signaling to a remote host over serial. But that's not what I had meant
here. We had a misunderstanding, in that I did not notice that you said 3
variables PER RING. Of course I use two variables.

{Quote hidden}

I'm looking forward to see your macro implementation. It sounds good.
Please post a notice when you update your web page. Thank you in advance
;)

{Quote hidden}

Why ? This is not a general purpose computer, I let it run 'idle' all the
time usually. Anyway I pace my serial transmissions from a timer and poll
the txrempty bit because the receiver is also bit-bashing and it needs
some time to do things between characters.

> and the non-interrupt code that adds queues bytes for
> transmission will enable the interrupt if the queue was empty.  But if the
> transmit ISR every falsely believes the ring is empty, the transmit queue will
> never get restarted.  Unless you add an otherwise unnecessary timer poll, or
> you have the producer always enable interrupts when it queues bytes for
> transmit.  The latter sounds appealing, but it can actually cause another race
> condition.

I try to do all the system flag updates in one subroutine, by posting
things to be done in a global flag. The code runs sans interrupts. I've
yet to see a race appear like this, although it's a speed bottleneck ;)
Also, this removes the constant worrying about whether things work or not
and whether all access instances were updated after fixing a bug... OK,
macros are handier, but tend to generate longer code.

> I understand that your situation is different that the one I describe, and
> that your solution works well for the constrained case that ring access is
> only done by ISRs.  My point is that I don't believe it is a good solution for
> the more general case where ring access is possible from non-ISR code.
> Therefore I think it is a disservice to describe your solution without very
> explicitly stating the limitations, because it could cause someone to spend
> an inordinate amount of time debugging the potential race condition.

Hmm, ok. So I'll try to put it in many words:

 The code snippet #1 in my previous posting can potentially generate a
race condition when its variable file (HEADP) and dependent variable
(TAILP) are accessed by another piece of code, concurrently. The code is
meant for use with interrupts disabled, as no locking of these variables
is done.

 For the particular case where the code is running with interrupts
disabled, this problem does not occur.

 For the particular case, where the code runs with interrupts enabled,
it is necessary to lock the variable accesses on TAILP and HEADP. This
would make the code longer, and slower, leaving the choice for another
implementation open. The same considerations apply for when the consumer
runs as non-ISR task concurrently with this task.

Peter

1998\07\24@154350 by Eric Smith

flavicon
face
I wrote:

> > solve the specific problem I described are to either disable interrupts
> > around a portion of the non-interrupt "producer" code, or modify the
> > ISR "consumer" code to not advance HEADP until it is sure there is room
> > in the buffer.

"Peter L. Peres" <TakeThisOuTplpEraseMEspamspam_OUTACTCOM.CO.IL> replied:

> But that's exactly what it does now.

I don't think so.  Here's the code as you posted it on 22 Jul 1998, with
line numbers added for ease of reference:

1   (Code snippet #1) (13 W, 14 T, uses one file: HEADP, constant run time)
2
3   SomeISR
4   ; handle specific interrupt here
5
6   ; increment head pointer and wrap
7           incf    HEADP, W
8           addlw   100h - RINGTOP  ; some PICs can't sublw
9
10          btfsc   PSW, ZF
11          addlw   RING_BOTTOM - RING_TOP  ; negative: ignore carry (mod 100h)
12
13          addlw   RING_TOP
14
15          movwf   HEADP           ; pointer is now ok
16          movwf   FSR             ; also index reg, used later
17
18  ; compare to tail
19          subwf   TAILP, W
20          btfsc   PSW, ZF
21          goto    HandleException ; stepped on the tail
22
23  ; good code continues here
24          movf    INREG, W
25          movwf   FSRP            ; FSRP is R0 in my mnemonic notation
26
27  ; return fm. interrupt via common interrupt-enable code
28          goto    AllDoneISR

Your code updates HEADP on line 15.  However, it doesn't make the
determination as to whether the buffer is full until lines 19 through 21.
Presumably your "HandleException" routine would back HEADP up one position,
wrapping it back to the end of the buffer if necessary.

If the "producer" code above was running at non-interrupt level, the buffer
was full, and the "consumer" code ran at interrupt level after line 15
was executed but before HandleException had completed, the consumer would
see that HEADP == TAILP, and conclude that the buffer was empty.

As I stated before, I agree that this is not a problem if both the producer
and consumer ran at interrupt-level (and nested interrupts are not allowed).

The three-variable approach avoids this problem without the need to disable
interrupts.  It only depends on atomic increments and decrements of the
count.

> I'm looking forward to see your macro implementation. It sounds good.
> Please post a notice when you update your web page. Thank you in advance
> ;)

I'll be happy to do so.  I have to pull the macros out of some production
code which I am not free to post, and merge them back into the uarttest
program, and make sure I don't break it in the process.  I'll let everyone
know when it's done.

In the mean time, the version on my web page does demonstrate my
ringadv macro.
       http://www.brouhaha.com/~eric/pic/uarttest.html

There's also a version for the Scenix SX on another page:
       http://www.brouhaha.com/~eric/scenix/fduart/
This program demonstrates a 115.2 Kbps full duplex software UART.

Cheers,
Eric

1998\07\24@172901 by Mark Willis

flavicon
face
Peter L. Peres wrote:
> <snipped>
> I try to do all the system flag updates in one subroutine, by posting
> things to be done in a global flag. The code runs sans interrupts. I've
> yet to see a race appear like this, although it's a speed bottleneck ;)
> Also, this removes the constant worrying about whether things work or not
> and whether all access instances were updated after fixing a bug... OK,
> macros are handier, but tend to generate longer code.
> <snipped>
> Peter

 Looks like you've learned how NOT to do things, i.e. either use a
Macro, or do all the work in one subroutine;  I won't count the number
of contracts I've done where major problems were solved by this wise
"One MASTER" method of coding, problem solving, and bug removal <VBG>
Same for databases but that's another bunch of ugly stories...

 One other potential problem with macros:  In cases where you have
dual-port RAM (different machines, sometimes different processors) or
where you cannot include macros from a common include file, into each
file that uses the macros, you can have real "bugfix propogation
problems" to coin a phrase <G>  I've seen one workplace where initially
each of 3 pieces of code, edited by the same team, had a different
version of the same 2 handy macros (they didn't even bother to re-name
the macros.  Ugh!)  And on the other side, on a different processor,
some instances of dual-port RAM access were in macros and some hardcoded
as they were slightly different & needed to be speedy (processor on that
side was quite busy!)  Scary initially, much improved by the end of the
project...

 I still like to use macros.  Just use 'em carefully!

 "Multiple masters, multiple disasters": just don't do it around me!

 Mark Willis, RemoveMEmwillisspamTakeThisOuTnwlink.com

1998\07\24@175357 by Peter L. Peres

picon face
On Fri, 24 Jul 1998, Eric Smith wrote:

{Quote hidden}

Nonono. Nobody backs up any pointers. That's the key, together with the
fact that the consumer uses the same structure of code and the virtual
'distance' between the HEADP update and check and the TAILP update and
check is exactly the same. This is in effect as if the update was atomic
in this particular case. It's a bit mind-boggling until one understands
it, but that's the way it works. There is only one special case, when the
consumer thinks the buffer is empty while it is not. This happens at the
START of the buffer being filled, so there is no problem really.

{Quote hidden}

Ok, I agree with you. mine is a very customized solution, not a general
implementation.

Oops, I see that my old .sig slipped out from somewhere. It's invalid, and
please ignore that ancient web page. I can't update it easily because CIS
has decided that one must use a proprietary tool available only under
L3.11/L95/NT and I don't run any of that here.

Peter

1998\07\24@183156 by Peter L. Peres

picon face
On Fri, 24 Jul 1998, Mark Willis wrote:

- snip -
>   Looks like you've learned how NOT to do things, i.e. either use a
> Macro, or do all the work in one subroutine;  I won't count the number
> of contracts I've done where major problems were solved by this wise
> "One MASTER" method of coding, problem solving, and bug removal <VBG>
> Same for databases but that's another bunch of ugly stories...

 It's called object-oriented programming. You mix all the sources of
serious trouble and stench and all the hacks in a container with some
glue, screw the lid on, weld it shut, paint it bright, and sell it for
good money to your followers. There are firms out there who got filthy
rich doing that over the years. Too bad if someone opens the can... Want a
name ? <G>

BTW, there are people who *sell* MACROS...

Peter

1998\07\24@202757 by Eric Smith

flavicon
face
"Peter L. Peres" <EraseMEplpspamACTCOM.CO.IL> wrote:
> Nonono. Nobody backs up any pointers. That's the key, together with the
> fact that the consumer uses the same structure of code and the virtual
> 'distance' between the HEADP update and check and the TAILP update and
> check is exactly the same. This is in effect as if the update was atomic
> in this particular case. It's a bit mind-boggling until one understands
> it, but that's the way it works. There is only one special case, when the
> consumer thinks the buffer is empty while it is not. This happens at the
> START of the buffer being filled, so there is no problem really.

I guess I must just be really dense.  If lines 19 through 21 of your code
just detect that the buffer is *about* to become full, what happens if the
buffer is already full when the code is initially entered?

1998\07\25@044440 by Peter L. Peres

picon face
On Sat, 25 Jul 1998, Eric Smith wrote:

> "Peter L. Peres" <RemoveMEplpEraseMEspamEraseMEACTCOM.CO.IL> wrote:
> > Nonono. Nobody backs up any pointers. That's the key, together with the
> > fact that the consumer uses the same structure of code and the virtual
> > 'distance' between the HEADP update and check and the TAILP update and
> > check is exactly the same. This is in effect as if the update was atomic
> > in this particular case. It's a bit mind-boggling until one understands
> > it, but that's the way it works. There is only one special case, when the
> > consumer thinks the buffer is empty while it is not. This happens at the
> > START of the buffer being filled, so there is no problem really.
>
> I guess I must just be really dense.  If lines 19 through 21 of your code
> just detect that the buffer is *about* to become full, what happens if the
> buffer is already full when the code is initially entered?


xx WH                     XXXXXXXXX RT xx
    xx RH XXXXXXXXX WT xx

Head is incremented, tail thinks there is something in the buffer while
there is not. Error. You are right !

Sorry for the diagrams, I am the one who's dense. I must stop doing this
when late (early) in the morning. Look at my TZ !

You were 100% right, there is a race in my #1 type code when used with
concurrent interrupts and/or interrupt-less operation.

And now I think I can see how a counter can help. Hmm. Does your counter
ever decrement under '0' and exceed RING_LENGTH by 1 or not ?

thank you for discussing this with me, it was most useful !

       Peter

1998\07\25@051837 by Eric Smith

flavicon
face
> And now I think I can see how a counter can help. Hmm. Does your counter
> ever decrement under '0' and exceed RING_LENGTH by 1 or not ?

My producer code tests for the full condition before adjusting any of
the variables.  Similarly my consumer code tests for the empty condition
first.  The counter value is never out of range.

Note that in my implementation the counter is not adjusted by the
macros I've mentioned previously, so it is still up to the programmer to
remember to do things in the right order.  This could be fixed by having
separate macros to advance the head and tail pointers; right now I just
use a single macro for either one.

Cheers,
Eric

More... (looser matching)
- Last day of these posts
- In 1998 , 1999 only
- Today
- New search...