The title is not technically correct but I think best conveys what I am asking. I have an NMI triggered at a 1 kHz rate by a CIA timer on a Commodore 64. If there is data available in a circular buffer it will send one byte to the user port B (Port B of same CIA).

The circular buffer has a head and tail pointers of course. When saving to the buffer a check of a flag is done to see if there is room, if there is the byte is written, and the head pointer incremented. When reading from the buffer it is first checked to see if there is data available and if so it is read and tail pointer adjusted. This works fine.

The potential problem, I suspect, is that if the main program is in the middle of saving to the buffer it might read a value from the tail pointer that is changed by the NMI before the save is complete (if NMI is triggered.) I'm not sure how to prevent this or if it is truly an issue.

Thinking out loud here, if the buffer is empty and the NMI is called mid save process it won't make any difference as the NMI just won't see the data is available yet. If the buffer is partially full then it should not matter as the NMI is just going to change the tail pointer which won't effect the saving at all. If the buffer is full the main process (which first check the full flag) might just waste a loop waiting for the NMI. (I hope I'm making sense.)

The important thing here is that the NMI must send a byte out if there is data without missing a cycle. If the main process has to skip one loop to write the next byte to the buffer then it is not a big deal.

So, after all of my rambling on I guess the question(s) are:
Do I really have a potential issue here?
If so, then how do I do things differently to fix it?

Thanks for any suggestions.

It shouldn't be a problem... I also use a pair of circular buffers for driving a UART as a console via IRQ. It uses head/tail pointers and a count variable. The routine that places data into the buffer updates the tail pointer and the count. The routine that sends the data via the Interrupt Service Routine (ISR) updates the head pointer and the count.

Also, once the circular buffer is empty, there's no need to continue triggering the interrupt (IRQ or NMI), so the routine that sends data and empties the buffer (which is the ISR) turns the interrupt off when there's no more data to send. Also, the routine that places data into the buffer turns on the interrupt so the ISR will kick in and start sending the data.

I can post some code if that might makes things more clearly, but my routines use CMOS instructions, so you would need to modify them to use 6502 only instructions. Hope this helps.

_________________
Regards, KM
https://github.com/floobydust

My gut tells me atomic updates may be needed on the buffer update. Updates done during the ISR are inherently atomic unless another interrupt is allowed to occur, so sending the byte out to the port shouldn’t require any additional code. But updating the circular buffer with new data may require some. If it was IRQ based I’d say simply disable interrupts before and enable interrupt after updating the buffer. However, since it’s NMI based that’s not really an option. If the CIA timer could be read to make sure there’s enough cycles available to update the buffer before the next interrupt occurs that might help. If there isn’t enough cycles then wait, otherwise do the updating. At a 1kHz rate there is only time to execute a few hundred instructions on a C64. Screen display will use up some cycles on the C64.

_________________
http://www.finitron.ca

It has been a long time since I studied the topic in any detail, but it seems to me that "well-behaved" updates should be fine, as long as the head and tail never collide.

By "well-behaved", I mean "storing" data into the buffer before updating the head pointer to "tell" the NMI routine that the data is there. The NMI routine is the consumer, and should not draw from an empty buffer. The main code is the producer, and should not store into a full buffer.



The producer should be the only entity adjusting the head pointer, and the consumer should be the only entity adjusting the tail pointer, so semaphores would be superfluous (at least in the case of one producer and one consumer). The worst that could happen in the instance you describe would be a temporarily incorrect "insufficient buffer space" indication, but no corruption. I may have oversimplified ... please correct me if I'm wrong.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

The count variable would be a problem, because it's updated both in the main program and in the interrupt handler. What I usually do is remove the count variable, and just compare head/tail pointers to see how much data is in the buffer. To avoid ambiguity between completely full and completely empty, you can either reserve 1 space in buffer, or use more bits in head/tail than necessary.

Suppose you have a 16 byte buffer, then I would take two 8-bit head/tail variables, and update the head like this (on 65C02 you could use INC A)


Note this code assumes the buffer is emptied quickly enough to avoid overflow. Consumer would do something like this:

Section 3.1 of my interrupts primer deals with almost the same thing, although receiving instead of transmitting. There's sample code, and it should help. (...and enjoy my outdated cartoons!) You only need two variables: a read pointer and a write pointer; no flags, semaphores, etc.. I've been using this regularly on the workbench for nearly 30 years with never a problem.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Thanks everyone. After posting this question last night I was wondering if my 'Flags' byte was even needed as it was one possible source of contention being written to by both the main routine and NMI handler. It seems it is not really needed as I need to touch and compare the head and tail pointers anyhow. I say pointers but really they are index's. I used a 256 byte buffer to get the free wrap around and simple indexing as Garth describes in his article above.

What I'm working on is not for communication but rather a CNC controller made from a C64. I have a PC based program that spits out 9 bytes to describe a line segment (doing 2D only at this time) and I use a form of Bresenham's line algorithm to iterate over the data and produce bytes that toggle the step pulses as needed.

One of the first things that struck me was that using a NMI handler to set/clear a step pulse was wasteful so I'm only toggling that bit when the step should be generated and used a 74LS123 set up to detect both edges of the signal and produce a 20uS pulse on either transition. Now that I have a better idea how to make the output buffer work I can do more than one buffers worth of output at a time.

BTW, I did a video explaining the basic idea here: https://youtu.be/AcXRZxbmoNU and hope to have another one up this week where I'm iterating over several lines of 'C=' code and generating the proper steps/direction pulses.

Having got rid of any shared variable, you're on firmer ground. But, with 8 bit pointers and a 256 byte buffer, you have a potential problem of not knowing whether the buffer is full or empty. As noted upthread, one approach is to use a 256 byte buffer but with a capacity of 255 - if the head and tail would become equal when writing, that's a fail. This way, when head and tail are equal, the buffer is unambiguously empty.

Well, it's true that the ISR decrements the count variable as it sends another byte of data. And of course, the output routine increments the count each time another byte of data is placed into the buffer. As the 65C02 is only processing in a single thread, you can't get the count out of sync with the two routines.

I've been using this type of buffer code since the 80's without an issue. The latest version has over 30K hours of non-stop execution on a few SBC boards without a single glitch.



and the ISR specific routine:

_________________
Regards, KM
https://github.com/floobydust

Sorry, the count variable works fine. I've been spending too much time on ARM, which doesn't have an atomic increment.

Oh, that means I'm confused too!

If 'tail==head' the buffer is empty, if tail+1=head the buffer is full. I'm always checking before writing to the buffer so I should not be able to overrun the buffer. If you are only using 255 bytes then you would not have a circular buffer, you need to be able to wrap all the way around (I think).

I think I misunderstood about using only 255 bytes, you were meaning that you could leave a one byte gap between the head and tail? So, you are still wrapping all the way around but just not saving anything into the gap byte?

Yes, that last idea, I think - you need to allocate 256 bytes, to make life easy, but you can only store 255 useful bytes in there.

As you say, it's not too hard to get the full/empty thing right, but it's a common trap to fall into so I thought it worth mentioning. It's also the sort of thing which might not be found in testing.

More generally, this is what's known as a "lock-free concurrent programming" problem. There's a lot of literature about it out there.

In many ways it's actually harder to deal with on modern CPUs, which have multiple threads and cores running simultaneously as well as interrupts, pre-emptive context switching, caches, out-of-order execution, and meddlesome optimising compilers to contend with. The one real difficulty on the 6502 is that it has only 8-bit atomic operations; in nearly all other respects it's easier to work with. Modern CPUs have 32-bit and even 64-bit atomic operations, which are enough to update an entire pointer and thereby implement an RCU (read-copy-update) structure or a linked-list safely, but you have to specifically instruct the compiler to use them correctly.