On 2021-10-25 11:19, Don Y wrote:
> On 10/25/2021 12:56 AM, Niklas Holsti wrote:
>> On 2021-10-25 0:08, Don Y wrote:
>>
>>> There are (and have been) many "safer" languages.  Many that are more
>>> descriptive (for certain classes of problem).  But, C has survived to
>>> handle all-of-the-above... perhaps in a suboptimal way but at least
>>> a manner that can get to the desired solution.
>>>
>>> Look at how few applications SNOBOL handles.  Write an OS in COBOL?
>>> Ada?
>>
>> I don't know about COBOL, but typically the real-time kernels
>> ("run-time systems") associated with Ada compilers for bare-board
>> embedded systems are written in Ada, with a minor amount of assembly
>> language for the most HW-related bits like HW context saving and
>> restoring. I'm pretty sure that C-language OS kernels also use
>> assembly for those things.
>
> Of course you *can* do these things.

Then I misunderstood your (rhetorical?) question.

> The question is how often
> they are ACTUALLY done with these other languages.

I don't find that question very interesting.

It is a typical chicken-and-egg, first-to-market conundrum. There is an
enormous amount of status-quo-favouring friction in awareness,
education, tool availability, and legacy code.

> [By the same token, expecting the past to mirror the present is equally
> naive.  People forget that tools and processes have evolved (in the 40+
> years that I've been designing embedded products).  And, that the isssues
> folks now face often weren't issues when tools were "stupider" (I've
> probably got $60K of obsolete compilers to prove this -- anyone written
> any C on an 1802 recently?  Or, a 2A03?  65816?  Z180?  6809?)  Don't
> even *think* about finding an Ada compiler for them -- in the past!]

Well, the Janus/Ada compiler was available for Z80 in its day. There are
also Ada compilers that use C as an intermediate language, with
applications for example on TI MSP430's, but those were probably not
available in the past ages you refer to.

On 2021-10-25 11:28, Don Y wrote:
> On 10/25/2021 1:09 AM, Niklas Holsti wrote:
>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>> On 10/24/2021 22:54, Don Y wrote:
>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>
>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>> the interrupt handler, the read pointer is only modified by the
>>>>> interrupted code. Has been done so for times immemorial.
>>>>
>>>> The OPs code doesn't differentiate between FIFO full and empty.
>>>
>>> So he should fix that first, there is no sane reason why not.
>>> Few things are simpler to do than that.
>>
>>
>>     [snip]
>>
>>
>>> Whatever handshakes he makes there is no problem knowing whether
>>> the fifo is full - just check if the position the write pointer
>>> will have after putting the next byte matches the read pointer
>>> at the moment.  Like I said before, few things are simpler than
>>> that, can't imagine someone working as a programmer being
>>> stuck at *that*.
>>
>> That simple check would require keeping a maximum of only N-1 entries
>> in the N-position FIFO buffer, and the OP explicitly said they did not
>> want to allocate an unused place in the buffer (which I think is
>> unreasonable of the OP, but that is only IMO).
>>
>> The simple explanation for the N-1 limit is that the difference
>> between two wrap-around pointers into an N-place buffer has at most N
>> different values, while there are N+1 possible filling states of the
>> buffer, from empty (zero items) to full (N items).
>
> But, again, that just deals with the "full check".  The easiest way to do
> this is just to check ".in" *after* advancement and inhibit the store if
> it coincides with the ".out" value.
>
> Checking for a "high water mark" to enable flow control requires more
> computation (albeit simple) as you have to accommodate the delays in
> that notification reaching the remote sender (lest he continue
> sending and overrun your buffer).
>
> And, later noting when you've consumed enough of the FIFO's contents
> to reach a "low water mark" and reenable the remote's transmissions.
>
> [And, if you ever have to deal with more "established" protocols
> that require the sequencing of specific control signals DURING
> a transfer, the ISR quickly becomes very complex!]

Of course. Perhaps you (Don) did not see that I was agreeing with your
position and objecting to the "it is very simple" stance of Dimiter
(considering the OP's expressed constraints).

Personally I would use critical sections to avoid relying on delicate
reasoning about interleaved executions. And to allow for easy future
complexification of the concurrent activities. The overhead of interrupt
disabling and enabling is seldom significant when that can be done
directly without kernel calls.

On 10/25/2021 2:06 AM, Niklas Holsti wrote:
> On 2021-10-25 11:28, Don Y wrote:
>> On 10/25/2021 1:09 AM, Niklas Holsti wrote:
>>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>>> On 10/24/2021 22:54, Don Y wrote:
>>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>>
>>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>>> the interrupt handler, the read pointer is only modified by the
>>>>>> interrupted code. Has been done so for times immemorial.
>>>>>
>>>>> The OPs code doesn't differentiate between FIFO full and empty.
>>>>
>>>> So he should fix that first, there is no sane reason why not.
>>>> Few things are simpler to do than that.
>>>
>>>
>>> [snip]
>>>
>>>
>>>> Whatever handshakes he makes there is no problem knowing whether
>>>> the fifo is full - just check if the position the write pointer
>>>> will have after putting the next byte matches the read pointer
>>>> at the moment. Like I said before, few things are simpler than
>>>> that, can't imagine someone working as a programmer being
>>>> stuck at *that*.
>>>
>>> That simple check would require keeping a maximum of only N-1 entries in the
>>> N-position FIFO buffer, and the OP explicitly said they did not want to
>>> allocate an unused place in the buffer (which I think is unreasonable of the
>>> OP, but that is only IMO).
>>>
>>> The simple explanation for the N-1 limit is that the difference between two
>>> wrap-around pointers into an N-place buffer has at most N different values,
>>> while there are N+1 possible filling states of the buffer, from empty (zero
>>> items) to full (N items).
>>
>> But, again, that just deals with the "full check". The easiest way to do
>> this is just to check ".in" *after* advancement and inhibit the store if
>> it coincides with the ".out" value.
>>
>> Checking for a "high water mark" to enable flow control requires more
>> computation (albeit simple) as you have to accommodate the delays in
>> that notification reaching the remote sender (lest he continue
>> sending and overrun your buffer).
>>
>> And, later noting when you've consumed enough of the FIFO's contents
>> to reach a "low water mark" and reenable the remote's transmissions.
>>
>> [And, if you ever have to deal with more "established" protocols
>> that require the sequencing of specific control signals DURING
>> a transfer, the ISR quickly becomes very complex!]
>
> Of course. Perhaps you (Don) did not see that I was agreeing with your position
> and objecting to the "it is very simple" stance of Dimiter (considering the
> OP's expressed constraints).

Yes, but I was afraid the emphasis would shift away from the "more involved"
case (by trivializing the "full" case).

> Personally I would use critical sections to avoid relying on delicate reasoning
> about interleaved executions. And to allow for easy future complexification of
> the concurrent activities. The overhead of interrupt disabling and enabling is
> seldom significant when that can be done directly without kernel calls.

We (developers, in general) tend to forget how often we cobble
together solutions from past implementations. And, as those past
implementations tend to be lax when it comes to enumerating the
assumptions under which they were created, we end up propagating
a bunch of dubious qualifiers that ultimately affect the code's
performance and "correctness".

Someone (including ourselves) trying to pilfer code from THIS
project might incorrectly expect the ISR to protect against buffer
wrap. Or, implement flow control. Or, be designed for a higher
data rate than it actually sees (saw!) -- will the buffer size -- and
task() timing -- be adequate to handle burst transmissions at 115Kbaud?
If not, where is the upper bound? What if the CPU clock is changed?
Or, the processor load? ...

"Steal" several bits of code -- possibly from different projects -- and
you've got an assortment of such hidden assumptions, all willing to eat
your lunch! While you remain convinced that none of those things
can happen!

My first UART driver had to manage about a dozen control signals as
the standard had a different intent and interpretation in the mid 70's,
early 80's (anyone remember TWX? TELEX? DB25s?). Porting it forward
ended up with a bunch of "issues" that no longer applied. (e.g.,
RTS/CTS weren't originally used as flow control/handshaking signals as
they are commonly used, now). *Assuming* a letter revision of the standard
was benign wrt the timing of signal transitions was folly.

You only see these things when you lay out all of your assumptions
in the codebase. And, hope the next guy actually READS what you took
the time to WRITE!

[When I wrote my 9 track tape driver, I had ~200 lines of commentary
just explaining the role of the interface wrt the formatter, transports,
etc. E.g., when you can read reverse, seek forward, rewind, etc.
with multiple transports hung off that same interface. Otherwise,
an observant developer would falsely conclude that the driver was
riddled with bugs -- as it *facilitated* a multiplicity of
concurrent operations]

On 10/25/2021 1:52 AM, Niklas Holsti wrote:
> On 2021-10-25 11:19, Don Y wrote:
>> On 10/25/2021 12:56 AM, Niklas Holsti wrote:
>>> On 2021-10-25 0:08, Don Y wrote:
>>>
>>>> There are (and have been) many "safer" languages. Many that are more
>>>> descriptive (for certain classes of problem). But, C has survived to
>>>> handle all-of-the-above... perhaps in a suboptimal way but at least
>>>> a manner that can get to the desired solution.
>>>>
>>>> Look at how few applications SNOBOL handles. Write an OS in COBOL? Ada?
>>>
>>> I don't know about COBOL, but typically the real-time kernels ("run-time
>>> systems") associated with Ada compilers for bare-board embedded systems are
>>> written in Ada, with a minor amount of assembly language for the most
>>> HW-related bits like HW context saving and restoring. I'm pretty sure that
>>> C-language OS kernels also use assembly for those things.
>>
>> Of course you *can* do these things.
>
> Then I misunderstood your (rhetorical?) question.
>
>> The question is how often
>> they are ACTUALLY done with these other languages.
>
> I don't find that question very interesting.

Why not? If a tool isn't used for a purpose for which it *should*
be "ideal", you have to start wondering "why not?" Was it NOT
suited to the task? Was it too costly (money and/or experience)?
How do we not repeat that problem, going forward? I.e., is it
better to EVOLVE a language to acquire the characteristics of the
"better" one -- rather than trying to encourage people to
"jump ship"?

> It is a typical chicken-and-egg, first-to-market conundrum. There is an
> enormous amount of status-quo-favouring friction in awareness, education, tool
> availability, and legacy code.

Of course!

And, there is also the pressure of the market. Do *you* want to be The Guy
who tries something new and sinks a product's development or market release?
If your approach proves to be a big hit, will you benefit as much as you'd
LOSE if it was a flop?

>> [By the same token, expecting the past to mirror the present is equally
>> naive. People forget that tools and processes have evolved (in the 40+
>> years that I've been designing embedded products). And, that the isssues
>> folks now face often weren't issues when tools were "stupider" (I've
>> probably got $60K of obsolete compilers to prove this -- anyone written
>> any C on an 1802 recently? Or, a 2A03? 65816? Z180? 6809?) Don't
>> even *think* about finding an Ada compiler for them -- in the past!]
>
> Well, the Janus/Ada compiler was available for Z80 in its day. There are also
> Ada compilers that use C as an intermediate language, with applications for
> example on TI MSP430's, but those were probably not available in the past ages
> you refer to.

I recall JRT Pascal and PL/M as the "high level" languages, back then.
C compilers were notoriously bad. You could literally predict the
code that would be generated for any statement. The whole idea of
"peephole optimizers" looking for:
STORE A
LOAD A
sequences to elide is testament to how little global knowledge they
had of the code they were processing.

Performance? A skilled ASM coder could beat the generated code
(in time AND space) without breaking into a sweat.

And, you bought a compiler/assembler/linker/debugger for *each*
processor -- not just a simple command line switch to alter the
code generation, etc. Vendors might have a common codebase
for the tools but built each variant conditionally.

The limits of the language were largely influenced by the targeted
hardware -- "helper routines" to support longs, floats, etc.
("Oh, did you want that support to be *reentrant*? We assumed
there would be a single floating point accumulator used throughout
the code, not one per thread!") Different sizes of addresses
(e.g., for the Z180, you could have 16b "logical" addresses
and 24b physical addresses -- mapped into that logical space
by the compiler's runtime support and linkage editor.)

Portable code? Maybe -- with quite a bit of work!

Fast/small? Meh...

On 25/10/2021 10:52, Niklas Holsti wrote:

>
> Well, the Janus/Ada compiler was available for Z80 in its day. There are
> also Ada compilers that use C as an intermediate language, with
> applications for example on TI MSP430's, but those were probably not
> available in the past ages you refer to.

Presumably there is gcc-based Ada for the msp430 (as there is for the
8-bit AVR)? There might not be a full library available, or possibly
some missing features in the language.

On 2021-10-25 14:49, David Brown wrote:
> On 25/10/2021 10:52, Niklas Holsti wrote:
>
>>
>> Well, the Janus/Ada compiler was available for Z80 in its day. There are
>> also Ada compilers that use C as an intermediate language, with
>> applications for example on TI MSP430's, but those were probably not
>> available in the past ages you refer to.
>
> Presumably there is gcc-based Ada for the msp430 (as there is for the
> 8-bit AVR)?

Indeed there seems to be one, or at least work towards one:
https://sourceforge.net/p/msp430ada/wiki/Home/.

> There might not be a full library available, or possibly
> some missing features in the language.

Certainly. I think that Janus/Ada for the Z80 was limited to the
original Ada (Ada 83), and may well have also had some significant
missing features. But I believe it was self-hosted on CP/M, quite a feat.

On 10/25/2021 11:09, Niklas Holsti wrote:
> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>> On 10/24/2021 22:54, Don Y wrote:
>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>> alternatively you'll often get away not using a fifo at all,
>>>>> unless you're blocking for a long while in some part of the code.
>>>>
>>>> Why would you do that. The fifo write pointer is only modified by
>>>> the interrupt handler, the read pointer is only modified by the
>>>> interrupted code. Has been done so for times immemorial.
>>>
>>> The OPs code doesn't differentiate between FIFO full and empty.
>>
>> So he should fix that first, there is no sane reason why not.
>> Few things are simpler to do than that.
>
>
>    [snip]
>
>
>> Whatever handshakes he makes there is no problem knowing whether
>> the fifo is full - just check if the position the write pointer
>> will have after putting the next byte matches the read pointer
>> at the moment.  Like I said before, few things are simpler than
>> that, can't imagine someone working as a programmer being
>> stuck at *that*.
>
> That simple check would require keeping a maximum of only N-1 entries in
> the N-position FIFO buffer, and the OP explicitly said they did not want
> to allocate an unused place in the buffer (which I think is unreasonable
> of the OP, but that is only IMO).

Well it might be reasonable if the fifo has a size of two, you know :-).

On 2021-10-25 16:04, Dimiter_Popoff wrote:
> On 10/25/2021 11:09, Niklas Holsti wrote:
>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>> On 10/24/2021 22:54, Don Y wrote:
>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>
>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>> the interrupt handler, the read pointer is only modified by the
>>>>> interrupted code. Has been done so for times immemorial.
>>>>
>>>> The OPs code doesn't differentiate between FIFO full and empty.
>>>
>>> So he should fix that first, there is no sane reason why not.
>>> Few things are simpler to do than that.
>>
>>
>>     [snip]
>>
>>
>>> Whatever handshakes he makes there is no problem knowing whether
>>> the fifo is full - just check if the position the write pointer
>>> will have after putting the next byte matches the read pointer
>>> at the moment.  Like I said before, few things are simpler than
>>> that, can't imagine someone working as a programmer being
>>> stuck at *that*.
>>
>> That simple check would require keeping a maximum of only N-1 entries
>> in the N-position FIFO buffer, and the OP explicitly said they did not
>> want to allocate an unused place in the buffer (which I think is
>> unreasonable of the OP, but that is only IMO).
>
> Well it might be reasonable if the fifo has a size of two, you know :-).

And if each of those two items is large, yes. But here we have a FIFO of
8-bit characters... few programs are so tight on memory that they cannot
stand one unused octet.

On 10/25/2021 8:34 AM, Niklas Holsti wrote:
> And if each of those two items is large, yes. But here we have a FIFO of 8-bit
> characters... few programs are so tight on memory that they cannot stand one
> unused octet.

It's not "unused". Rather, it's roll is that of indicating "full/overrun".
The OP seems to have decided that this is of no concern -- in *one* app?

Il 25/10/2021 17:34, Niklas Holsti ha scritto:
> On 2021-10-25 16:04, Dimiter_Popoff wrote:
>> On 10/25/2021 11:09, Niklas Holsti wrote:
>>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>>> On 10/24/2021 22:54, Don Y wrote:
>>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>>
>>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>>> the interrupt handler, the read pointer is only modified by the
>>>>>> interrupted code. Has been done so for times immemorial.
>>>>>
>>>>> The OPs code doesn't differentiate between FIFO full and empty.
>>>>
>>>> So he should fix that first, there is no sane reason why not.
>>>> Few things are simpler to do than that.
>>>
>>>
>>>     [snip]
>>>
>>>
>>>> Whatever handshakes he makes there is no problem knowing whether
>>>> the fifo is full - just check if the position the write pointer
>>>> will have after putting the next byte matches the read pointer
>>>> at the moment.  Like I said before, few things are simpler than
>>>> that, can't imagine someone working as a programmer being
>>>> stuck at *that*.
>>>
>>> That simple check would require keeping a maximum of only N-1 entries
>>> in the N-position FIFO buffer, and the OP explicitly said they did
>>> not want to allocate an unused place in the buffer (which I think is
>>> unreasonable of the OP, but that is only IMO).
>>
>> Well it might be reasonable if the fifo has a size of two, you know :-).
>
>
> And if each of those two items is large, yes. But here we have a FIFO of
> 8-bit characters... few programs are so tight on memory that they cannot
> stand one unused octet.

When I have a small (<256) power-of-two (16, 32, 64, 128) buffer (and
this is the case for a UART receiving ring-buffer), I like to use this
implementation that works and doesn't waste any element.

However I know this isn't the best implementation ever and it's a pity
the thread emphasis has been against this implementation (that was used
as *one* implementation just to have an example to discuss on).

The main point was the use of volatile (and other techniques) to
guarantee a correct compiler output, whatever legal (respect the C
standard) optimizations the compiler thinks to do.

It seems to me the arguments againts or for volatile are completely
indipendent from the implementation of ring-buffer.

On 10/25/2021 20:43, Don Y wrote:
> On 10/25/2021 8:34 AM, Niklas Holsti wrote:
>> And if each of those two items is large, yes. But here we have a FIFO
>> of 8-bit characters... few programs are so tight on memory that they
>> cannot stand one unused octet.
>
> It's not "unused".  Rather, it's roll is that of indicating "full/overrun".
> The OP seems to have decided that this is of no concern -- in *one* app?

Oh come on, I joked about the fifo of two bytes only because this whole
thread is a joke - pages and pages of C to maintain a fifo, what can be
more of a joke than this.

On 10/25/2021 10:53 AM, Dimiter_Popoff wrote:
> On 10/25/2021 20:43, Don Y wrote:
>> On 10/25/2021 8:34 AM, Niklas Holsti wrote:
>>> And if each of those two items is large, yes. But here we have a FIFO of
>>> 8-bit characters... few programs are so tight on memory that they cannot
>>> stand one unused octet.
>>
>> It's not "unused". Rather, it's roll is that of indicating "full/overrun".
>> The OP seems to have decided that this is of no concern -- in *one* app?
>
> Oh come on, I joked about the fifo of two bytes only because this whole
> thread is a joke

My comment applies regardless of the size of the FIFO.

> - pages and pages of C to maintain a fifo, what can be
> more of a joke than this.

Where do you see "pages and pages of C to maintain a FIFO"?

On 10/25/2021 10:52 AM, pozz wrote:
> However I know this isn't the best implementation ever and it's a pity the
> thread emphasis has been against this implementation (that was used as *one*
> implementation just to have an example to discuss on).

The point is that you need a COMPLETE implementation before you start
thinking about the amount of "license" the compiler can take with your code.

Here's *part* of an implementation:

a = 37;

Now, should I declare A as volatile? Use the register qualifier?
What size should the integer A be? Can the optimizer elide this
statement from my code?

All sorts of questions whose answers depend on the REST of the
implementation -- not shown!

> The main point was the use of volatile (and other techniques) to guarantee a
> correct compiler output, whatever legal (respect the C standard) optimizations
> the compiler thinks to do.
>
> It seems to me the arguments againts or for volatile are completely indipendent
> from the implementation of ring-buffer.

It has to do with indicating how YOU (the developer) see the object
being used (accessed). You, in theory, know more about the role of
the object than the compiler (because it may be accessed in other modules,
or, have "stuff" tied to it -- like special hardware, etc.) You need a way
to tell the compiler that "you know what you are doing" in your use
of the object and that it should restrain itself from making assumptions
that might not be true.

If your example doesn't bring to light those various issues, then
the decision as to its applicability is moot.

Il 23/10/2021 18:09, David Brown ha scritto:
[...]
> Marking "in" and "buf" as volatile is /far/ better than using a critical
> section, and likely to be more efficient than a memory barrier. You can
> also use volatileAccess rather than making buf volatile, and it is often
> slightly more efficient to cache volatile variables in a local variable
> while working with them.

I think I got your point, but I'm wondering why there are plenty of
examples of ring-buffer implementations that don't use volatile at all,
even if the author explicitly refers to interrupts and multithreading.

Just an example[1] by Quantum Leaps. It promises to be a *lock-free* (I
think thread-safe) ring-buffer implementation in the scenario of single
producer/single consumer (that is my scenario too).

In the source code there's no use of volatile. I could call
RingBuf_put() in my rx uart ISR and call RingBuf_get() in my mainloop code.

From what I learned from you, this code usually works, but the standard
doesn't guarantee it will work with every old, current and future compilers.

[1] https://github.com/QuantumLeaps/lock-free-ring-buffer

On 2021-10-25 20:52, pozz wrote:
> Il 25/10/2021 17:34, Niklas Holsti ha scritto:
>> On 2021-10-25 16:04, Dimiter_Popoff wrote:
>>> On 10/25/2021 11:09, Niklas Holsti wrote:
>>>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>>>> On 10/24/2021 22:54, Don Y wrote:
>>>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>>>
>>>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>>>> the interrupt handler, the read pointer is only modified by the
>>>>>>> interrupted code. Has been done so for times immemorial.
>>>>>>
>>>>>> The OPs code doesn't differentiate between FIFO full and empty.

(I suspect something is not quite right with the attributions of the
quotations above -- Dimiter probably did not suggest disabling
interrupts -- but no matter.)

[snip]

> When I have a small (<256) power-of-two (16, 32, 64, 128) buffer (and
> this is the case for a UART receiving ring-buffer), I like to use this
> implementation that works and doesn't waste any element.
>
> However I know this isn't the best implementation ever and it's a pity
> the thread emphasis has been against this implementation (that was used
> as *one* implementation just to have an example to discuss on).
>
> The main point was the use of volatile (and other techniques) to
> guarantee a correct compiler output, whatever legal (respect the C
> standard) optimizations the compiler thinks to do.
>
> It seems to me the arguments againts or for volatile are completely
> indipendent from the implementation of ring-buffer.

Of course "volatile" is needed, in general, whenever anything is written
in one thread and read in another. The issue, I think, is when
"volatile" is _enough_.

I feel that detection of a full buffer (FIFO overflow) is required for a
proper ring buffer implementation, and that has implications for the
data structure needed, and that has implications for whether critical
sections are needed.

If the FIFO implementation is based on just two pointers (read and
write), and each pointer is modified by just one of the two threads
(main thread = reader, and interrupt handler = writer), and those
modifications are both "volatile" AND atomic (which has not been
discussed so far, IIRC...), then one can do without a critical region.
But then detection of a full buffer needs one "wasted" element in the
buffer.

To avoid the wasted element, one could add a "full"/"not full" Boolean
flag. But that flag would be modified by both threads, and should be
modified atomically together with the pointer modifications, which (I
think) means that a critical section is needed.

On 25/10/2021 20:15, pozz wrote:
> Il 23/10/2021 18:09, David Brown ha scritto:
> [...]
>> Marking "in" and "buf" as volatile is /far/ better than using a critical
>> section, and likely to be more efficient than a memory barrier.  You can
>> also use volatileAccess rather than making buf volatile, and it is often
>> slightly more efficient to cache volatile variables in a local variable
>> while working with them.
>
> I think I got your point, but I'm wondering why there are plenty of
> examples of ring-buffer implementations that don't use volatile at all,
> even if the author explicitly refers to interrupts and multithreading.

You don't have to use "volatile". You can make correct code here using
critical sections - it's just a lot less efficient. (If you have a
queue where more than one context can be reading it or writing it, then
you /do/ need some kind of locking mechanism.)

You can also use memory barriers instead of volatile, but it is likely
to be slightly less efficient.

You can also use atomics instead of volatiles, but it is also quite
likely to be slightly less efficient. If you have an SMP system, on the
other hand, then you need something more than volatile and compiler
memory barriers - atomics are quite possibly the most efficient solution
in that case.

And sometimes you can make code that doesn't need any special treatment
at all, because you know the way it is being called. If the two ends of
your buffer are handled by tasks in a cooperative multi-tasking
scenario, then there is no problem - you don't need to worry about
volatile or any alternatives. If you know your interrupt can't occur
while the other end of the buffer is being handled, that can reduce your
need for volatile. (In particular, that can also avoid complications if
you have counter variables that are bigger than the processor can handle
atomically - usually not a problem for a 32-bit Cortex-M, but often
important on an 8-bit AVR.)

If you know, for a fact, that the code will be compiled by a weak
compiler or with weak optimisation, or that the "get" and "put"
implementations will always be in a separately compiled unit from code
calling these functions and you'll never use any kind of cross-unit
optimisations, then you can get often away without using volatile.

>
> Just an example[1] by Quantum Leaps. It promises to be a *lock-free* (I
> think thread-safe) ring-buffer implementation in the scenario of single
> producer/single consumer (that is my scenario too).

It's lock-free, but not safe in the face of modern optimisation (gcc has
had LTO for many years, and a lot of high-end commercial embedded
compilers have used such techniques for decades). And I'd want to study
it in detail and think a lot before accepting that it is safe to use its
16-bit counters on an 8-bit AVR. That could be fixed by just changing
the definition of the RingBufCtr type, which is a nice feature in the code.

>
> In the source code there's no use of volatile. I could call
> RingBuf_put() in my rx uart ISR and call RingBuf_get() in my mainloop code.
>

You don't want to call functions from an ISR if you can avoid it, unless
the functions are defined in the same unit and can be inlined. On many
processors (less so on the Cortex-M) calling an external function from
an ISR means a lot of overhead to save and restore the so-called
"volatile" registers (no relation to the C keyword "volatile"), usually
completely unnecessarily.

> From what I learned from you, this code usually works, but the standard
> doesn't guarantee it will work with every old, current and future
> compilers.
>

Yes, that's a fair summary.

It might be good enough for some purposes. But since "volatile" will
cost nothing in code efficiency but greatly increase the portability and
safety of the code, I'd recommend using it. And I am certainly in
favour of thinking carefully about these things - as you did in the
first place, which is why we have this thread.

>
>
> [1] https://github.com/QuantumLeaps/lock-free-ring-buffer

On 25/10/2021 17:34, Niklas Holsti wrote:

> And if each of those two items is large, yes. But here we have a FIFO of
> 8-bit characters... few programs are so tight on memory that they cannot
> stand one unused octet.

I remember a program I worked with where the main challenge for the
final features was not figuring out the implementation, but finding a
few spare bytes of code space and a couple of spare bits of ram to use.
And that was with 32 KB ROM and 512 bytes RAM (plus some bits in the
registers of peripherals that weren't used). That was probably the last
big assembly program I wrote - non-portability was a killer.

On 10/25/2021 21:33, Niklas Holsti wrote:
> ....
>
> If the FIFO implementation is based on just two pointers (read and
> write), and each pointer is modified by just one of the two threads
> (main thread = reader, and interrupt handler = writer), and those
> modifications are both "volatile" AND atomic (which has not been
> discussed so far, IIRC...), then one can do without a critical region.
> But then detection of a full buffer needs one "wasted" element in the
> buffer.

Why atomic? No need for that unless more than one interrupted task would
want to read from the fifo at the same time, which is nonsense. [I once
wasted a day looking at a garbled input from an auxiliary HV to a netMCA
only to discover I had left a shell to start via the same UART during
boot, through an outdated (but available) driver accessing the same
UART the standard driver through which the HV was used....
This across half the planet, customer was in South Africa. Not
an experience anybody would ask for, I can tell you :)].
Just like there is no need to mask interrupts, as you mentioned I
had said before.

> To avoid the wasted element, one could add a "full"/"not full" Boolean
> flag. But that flag would be modified by both threads, and should be
> modified atomically together with the pointer modifications, which (I
> think) means that a critical section is needed.

Now this is where atomic access is necessary - for no good reason in
this case, as mentioned before, but if one wants to bang their head
in the wall this is the proper way to do it.
As for "volatile" I can't say much, but if this is the way to make
the compiler access every time the address declared such instead of
using some stale data it has then it would be needed of
course.

On 2021-10-25 22:09, Dimiter_Popoff wrote:
> On 10/25/2021 21:33, Niklas Holsti wrote:
>> ....
>>
>> If the FIFO implementation is based on just two pointers (read and
>> write), and each pointer is modified by just one of the two threads
>> (main thread = reader, and interrupt handler = writer), and those
>> modifications are both "volatile" AND atomic (which has not been
>> discussed so far, IIRC...), then one can do without a critical region.
>> But then detection of a full buffer needs one "wasted" element in the
>> buffer.
>
> Why atomic?

If the read/write pointers/indices are, say, 16 bits, but the processor
has only 8-bit store/load instructions, updating a pointer/index happens
non-atomically, 8 bits at a time, and the interrupt handler can read a
half-updated value if the interrupt happens in the middle of an update.
That would certainly mess up the comparison between the read and write
points in the interrupt handler.

In the OP's code, I suppose (but I don't recall) that the indices are 8
bits, so probably atomically readable and writable.

On 10/25/2021 22:53, Niklas Holsti wrote:
> On 2021-10-25 22:09, Dimiter_Popoff wrote:
>> On 10/25/2021 21:33, Niklas Holsti wrote:
>>> ....
>>>
>>> If the FIFO implementation is based on just two pointers (read and
>>> write), and each pointer is modified by just one of the two threads
>>> (main thread = reader, and interrupt handler = writer), and those
>>> modifications are both "volatile" AND atomic (which has not been
>>> discussed so far, IIRC...), then one can do without a critical
>>> region. But then detection of a full buffer needs one "wasted"
>>> element in the buffer.
>>
>> Why atomic?
>
>
> If the read/write pointers/indices are, say, 16 bits, but the processor
> has only 8-bit store/load instructions, updating a pointer/index happens
> non-atomically, 8 bits at a time, and the interrupt handler can read a
> half-updated value if the interrupt happens in the middle of an update.
> That would certainly mess up the comparison between the read and write
> points in the interrupt handler.
>
> In the OP's code, I suppose (but I don't recall) that the indices are 8
> bits, so probably atomically readable and writable.
>

Ah, well, this is a possible scenario in a multicore system (or single
core if the two bytes are written by separate opcodes).

Don Y <blockedofcourse@foo.invalid> wrote:
> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
> >> Disable interrupts while accessing the fifo. you really have to.
> >> alternatively you'll often get away not using a fifo at all,
> >> unless you're blocking for a long while in some part of the code.
> >
> > Why would you do that. The fifo write pointer is only modified by
> > the interrupt handler, the read pointer is only modified by the
> > interrupted code. Has been done so for times immemorial.
>
> The OPs code doesn't differentiate between FIFO full and empty.

If you read carefuly what he wrote you would know that he does.
The trick he uses is that his indices may point outside buffer:
empty is equal indices, full is difference equal to buffer
size. Of course his approach has its own limitations, like
buffer size being power of 2 and with 8 bit indices maximal
buffer size is 128.

--
Waldek Hebisch

On 25/10/21 7:09 pm, Niklas Holsti wrote:
> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>> On 10/24/2021 22:54, Don Y wrote:
>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>> alternatively you'll often get away not using a fifo at all,
>>>>> unless you're blocking for a long while in some part of the code.
>>>>
>>>> Why would you do that. The fifo write pointer is only modified by
>>>> the interrupt handler, the read pointer is only modified by the
>>>> interrupted code. Has been done so for times immemorial.
>>>
>>> The OPs code doesn't differentiate between FIFO full and empty.
>>
>> So he should fix that first, there is no sane reason why not.
>> Few things are simpler to do than that.
>
>
>    [snip]
>> Whatever handshakes he makes there is no problem knowing whether
>> the fifo is full - just check if the position the write pointer
>> will have after putting the next byte matches the read pointer
>> at the moment.  Like I said before, few things are simpler than
>> that, can't imagine someone working as a programmer being
>> stuck at *that*.
>
> That simple check would require keeping a maximum of only N-1 entries in
> the N-position FIFO buffer, and the OP explicitly said they did not want
> to allocate an unused place in the buffer (which I think is unreasonable
> of the OP, but that is only IMO).

In my opinion too. If you're going to waste a memory cell, why not use
it for a count variable instead of an unused element?

CH

Il 25/10/2021 20:33, Niklas Holsti ha scritto:
> On 2021-10-25 20:52, pozz wrote:
>> Il 25/10/2021 17:34, Niklas Holsti ha scritto:
>>> On 2021-10-25 16:04, Dimiter_Popoff wrote:
>>>> On 10/25/2021 11:09, Niklas Holsti wrote:
>>>>> On 2021-10-24 23:27, Dimiter_Popoff wrote:
>>>>>> On 10/24/2021 22:54, Don Y wrote:
>>>>>>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>>>>>>> Disable interrupts while accessing the fifo. you really have to.
>>>>>>>>> alternatively you'll often get away not using a fifo at all,
>>>>>>>>> unless you're blocking for a long while in some part of the code.
>>>>>>>>
>>>>>>>> Why would you do that. The fifo write pointer is only modified by
>>>>>>>> the interrupt handler, the read pointer is only modified by the
>>>>>>>> interrupted code. Has been done so for times immemorial.
>>>>>>>
>>>>>>> The OPs code doesn't differentiate between FIFO full and empty.
>
>
> (I suspect something is not quite right with the attributions of the
> quotations above -- Dimiter probably did not suggest disabling
> interrupts -- but no matter.)
>
>    [snip]
>
>
>> When I have a small (<256) power-of-two (16, 32, 64, 128) buffer (and
>> this is the case for a UART receiving ring-buffer), I like to use this
>> implementation that works and doesn't waste any element.
>>
>> However I know this isn't the best implementation ever and it's a pity
>> the thread emphasis has been against this implementation (that was
>> used as *one* implementation just to have an example to discuss on).
>>
>> The main point was the use of volatile (and other techniques) to
>> guarantee a correct compiler output, whatever legal (respect the C
>> standard) optimizations the compiler thinks to do.
>>
>> It seems to me the arguments againts or for volatile are completely
>> indipendent from the implementation of ring-buffer.
>
>
> Of course "volatile" is needed, in general, whenever anything is written
> in one thread and read in another. The issue, I think, is when
> "volatile" is _enough_.
>
> I feel that detection of a full buffer (FIFO overflow) is required for a
> proper ring buffer implementation, and that has implications for the
> data structure needed, and that has implications for whether critical
> sections are needed.
>
> If the FIFO implementation is based on just two pointers (read and
> write), and each pointer is modified by just one of the two threads
> (main thread = reader, and interrupt handler = writer), and those
> modifications are both "volatile" AND atomic (which has not been
> discussed so far, IIRC...), then one can do without a critical region.
> But then detection of a full buffer needs one "wasted" element in the
> buffer.

Yeah, this is exactly the topic of my original post. Anyway it seems
what you say isn't always correct. As per C standard, the compiler could
reorder instructions that involve non-volatile data. So, even in your
simplified scenario (atomic access for indexes), volatile for the head
only (that ISR changes) is not sufficient.

The function called in the mainloop and that get data from the buffer
access three variables: head (changed in ISR), tail (not changed in ISR)
and buf[] (written in ISR ad read in mainloop).

The get function firstly check if some data is available in the FIFO and
*next* read from buf[]. However compiler could rearrange instructions so
reading from buf[] at first and then checking FIFO empty condition.
If the compiler goes this way, errors could occur during execution.

My original question was exactly if this could happen (without breaking
C specifications) and, if yes, how to avoid this: volatile? critical
section? memory barrier?

David Brown said this is possible and suggested to access both head and
buf[] as volatile in get() function, forcing the compiler to respect the
order of instructions.

> To avoid the wasted element, one could add a "full"/"not full" Boolean
> flag. But that flag would be modified by both threads, and should be
> modified atomically together with the pointer modifications, which (I
> think) means that a critical section is needed.

On 25/10/2021 22:02, Dimiter_Popoff wrote:
> On 10/25/2021 22:53, Niklas Holsti wrote:
>> On 2021-10-25 22:09, Dimiter_Popoff wrote:
>>> On 10/25/2021 21:33, Niklas Holsti wrote:
>>>> ....
>>>>
>>>> If the FIFO implementation is based on just two pointers (read and
>>>> write), and each pointer is modified by just one of the two threads
>>>> (main thread = reader, and interrupt handler = writer), and those
>>>> modifications are both "volatile" AND atomic (which has not been
>>>> discussed so far, IIRC...), then one can do without a critical
>>>> region. But then detection of a full buffer needs one "wasted"
>>>> element in the buffer.
>>>
>>> Why atomic?
>>
>>
>> If the read/write pointers/indices are, say, 16 bits, but the
>> processor has only 8-bit store/load instructions, updating a
>> pointer/index happens non-atomically, 8 bits at a time, and the
>> interrupt handler can read a half-updated value if the interrupt
>> happens in the middle of an update. That would certainly mess up the
>> comparison between the read and write points in the interrupt handler.
>>
>> In the OP's code, I suppose (but I don't recall) that the indices are
>> 8 bits, so probably atomically readable and writable.
>>
>
> Ah, well, this is a possible scenario in a multicore system (or single
> core if the two bytes are written by separate opcodes).

For the AVR, writing 16-bit values is not atomic - but the OP used 8-bit
counters (which are more appropriate for the AVR anyway, as they don't
have enough memory to spend on big buffers).

For multi-core systems you can have added complications. Memory
accesses are always seen in assembly-code order on one core, regardless
of how they may be re-ordered by buffers, caches, out-of-order
execution, speculative execution, etc. (CPU designers sometimes have to
work quite hard to achieve this, but anything else would be impossible
to work with.) However, the order seen by other cores could be
different. So "volatile" accesses are no longer enough - you need to
use C11/C++11 atomics, or the equivalent.

(Don't use C11/C++11 atomics on gcc for the Cortex-M or AVR, at least
not with anything that can't be done with a single read or write
instruction - the library that comes with gcc is deeply flawed.)

On 10/25/2021 2:32 PM, antispam@math.uni.wroc.pl wrote:
> Don Y <blockedofcourse@foo.invalid> wrote:
>> On 10/24/2021 4:14 AM, Dimiter_Popoff wrote:
>>>> Disable interrupts while accessing the fifo. you really have to.
>>>> alternatively you'll often get away not using a fifo at all,
>>>> unless you're blocking for a long while in some part of the code.
>>>
>>> Why would you do that. The fifo write pointer is only modified by
>>> the interrupt handler, the read pointer is only modified by the
>>> interrupted code. Has been done so for times immemorial.
>>
>> The OPs code doesn't differentiate between FIFO full and empty.
>
> If you read carefuly what he wrote you would know that he does.
> The trick he uses is that his indices may point outside buffer:
> empty is equal indices, full is difference equal to buffer

Doesn't matter as any index can increase by any amount and
invalidate the "reality" of the buffer's contents (i.e.
actual number of characters that have been tranfered to
that region of memory).

Buffer size is 128, for example. in is 127, out is 127.
What's that mean? Can you tell me what has happened prior
to this point in time? Have 127 characters been received?
Or, 383? Or, 1151?

How many characters have been removed from the buffer?
(same numeric examples).

Repeat for .in being 129, 227, 255, etc.

Remember, there is nothing that GUARANTEES that the uart
task is keeping up with the input data rate. So, the buffer
could wrap 50 times and it's instantaneous state (visible
via .in and .out) would appear unchanged to that task!

If you wanted to rely on .in != .out to indicate the
presence of data REGARDLESS OF WRAPS, then you'd need the
size of each to be "significantly larger" than the maximum
fill rate of the buffer to ensure THEY can't wrap.

> size. Of course his approach has its own limitations, like
> buffer size being power of 2 and with 8 bit indices maximal
> buffer size is 128.

The biggest practical limitation is that of expectations of
other developers who may inherit (or copy) his code expecting
the FIFO to be "well behaved".