Paul Carpenter wrote:> On Saturday, in article > <ekbb81dio08nc67q65o9mfv5eidahn7q0i@4ax.com> keinanen@sci.fi > "Paul Keinanen" wrote: > >On Sat, 14 May 2005 06:00:09 GMT, Neil Kurzman <nsk@mail.asb.com> > >wrote: > > > >>OK so how do you do a ring buffer without disabling interruptsduring RX read ,> >> or a Tx write? > >>The Interrupt could hit during that time. The Keil C sampledisables RI> >> during that time. > > > >The basic principle in avoiding interrupt disabling is to make sure > >that only one partner updates a specific variable (unless thehardware> >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. Makea> >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 theglobally> >visible read pointer. > > The only issue with using pointers (or indecii) on ring buffers isthe> issue of when the pointers are identical knowing whether the buffer > is full or empty. Especially on RX buffers as this is truelyaysnchronous> to the systemFor 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 globallyvisible> >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 moduleswhere> the only globally visible parts of that module are function calls and > definitions (baud rates, error codes) and the like. The module willneed> access to globally defined information like I/O registers. A secondmodule> maybe needed to handle setting of timers or other external timers for > baud rate generation depending on platforms. > > -- > Paul Carpenter | paul@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
UARTs and interrupts
Started by ●May 11, 2005
Reply by ●May 14, 20052005-05-14
Reply by ●May 14, 20052005-05-14
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 systemThat 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
Reply by ●May 14, 20052005-05-14
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 systemNot 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
Reply by ●May 14, 20052005-05-14
On Saturday, in article <4286002E.2CB44E50@acm.org> dtweed@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 | paul@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
Reply by ●May 14, 20052005-05-14
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
Reply by ●May 15, 20052005-05-15
On Sat, 14 May 2005 21:33:56 GMT, CBFalconer <cbfalconer@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
Reply by ●May 15, 20052005-05-15
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
Reply by ●May 15, 20052005-05-15
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
Reply by ●May 16, 20052005-05-16
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
Reply by ●May 16, 20052005-05-16
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.