Best way to implement interrupt-safe data structures

[yugr 0]

Hi guys,

 

I've recently used ring buffer in my code which I declared volatile as

I usually do for all variables which are shared between interrupts and

normal code. It occured to me after a while that volatile would force

compiler to generate a rather inefficient code. Here's an example

 

typedef struct {

char bytes[RING_BUF_SIZE];

unsigned head, tail;

} ring_buf;

#define rb_empty(rb) (rb.head == rb.tail)

#define rb_pop(rb, byte) do { \

byte = rb.bytes[rb.head]; \

rb.head = (rb.head + 1) & RING_BUF_SIZE_MASK; \

} while(0)

...

static volatile ring_buf mybuf; // Note the "volatile" here

...

// Somewhere in main()

_disable_interrupts();

if( !rb_empty(mybuf) )

rb_pop(mybuf, *byte); // 2 redundant memory accesses to rb.head

due to volatile

_enable_interrupts();

 

Because of volatile, rx_bytes.head will be read from memory three times: once in rb_empty and twice in

rb_pop. In other words volatile will force compiler to load field every time instead of

caching result in a register thus significantly decreasing

performance.

 

Is there any way to achieve interrupt safety without resorting to

volatile (and loosing precious perf) in this case? My idea is that

_enable/disable_interrupts may serve as compiler barriers (i.e. they

prevent compiler from moving memory references behind and past them)

they alone should be enough to guarantee correctness. Unfortunately

compiler mans (for CCS at least) are silent on this topic.

 

-Yuri

[oPossum 1,083]

Make head and tail volatile, but not the buffer itself -and- disable interrupts during critical sections that change the buffer. That will usually work, but is not guaranteed to.

 

For max efficiency you really have to write in assembly.

[yugr 0]

oPossum, thanks for the comment although it didn't add much to what I already know.

 

> One way is to temporally disable interrupts during critical sections of mainline code.

> That will prevent an ISR from changing something 'behind your back'.

 

It's clear that I need to disable interrupts but will it stop compiler from rearranging memory accesses? In particular from moving memreads before _disable_interrupts or after _enable_interrupts? I haven't found anything in TI compiler man on this topic.

 

> You may still need volatile for some vars - like the head and tail pointer - requires careful study.

 

The question is - do I need volatile if variable is already protected by _enable/disable_interrupts?

 

-Yuri

[oPossum 1,083]

I wasn't awake yet when I wrote the first reply or edit or it, sorry.

 

I think the fundamental problem is that the ring buffer head/tail should be handled as volatile at some specific times in the main line code, but not in the ISR. Don't know how to do that in C.

 

I would personally resort to assembly for something like this if it had to be as efficient and compact as possible.

[pabigot 355]

If you weren't aware, you can apply the volatile qualifier to the fields in the structure, rather than to the object itself:

typedef struct {
char bytes[RING_BUF_SIZE];
volatile unsigned head, tail;
} ring_buf;

The question is - do I need volatile if variable is already protected by _enable/disable_interrupts?

Yes. While some compilers may treat those intrinsics as sequence points, there is nothing about them that tells the compiler that it can't cache a copy of the variable that's being examined (for example, in a loop waiting for head to be updated) because somebody else might change it outside visible flow of control. That's what volatile does.

 

To avoid multiple reads of rx_bytes.head within the ISR, read it into a local variable, use and manipulate it, then write it back into the structure. This will be safe if the variable is not modified anywhere else.

[pabigot 355]

The question is - do I need volatile if variable is already protected by _enable/disable_interrupts?

Yes. While some compilers may treat those intrinsics as sequence points, there is nothing about them that tells the compiler that it can't cache a copy of the variable that's being examined (for example, in a loop waiting for head to be updated) because somebody else might change it outside visible flow of control. That's what volatile does.

A small correction: If all accesses (reads and writes) to the variable are while interrupts are disabled, and it's not a peripheral register that can change internally, and you're sure that everything else that might possibly ever permit a change to the value is inhibited, you could probably get away with leaving "volatile" off the declaration.

 

This will, of course, bite you in the butt if in three months you decide you need to spin-wait with interrupts enabled for the head to be updated by the ISR. Probably cost you quite a few hours to figure out why the ring buffer code that's been working so well no longer functions. But there are cases where you need to do that. (In my case just now, maintaining a 32-bit timer overflow counter in a private data structure.)

[yugr 0]

I wasn't awake yet when I wrote the first reply or edit or it, sorry.

 

Np

 

I think the fundamental problem is that the ring buffer head/tail should be handled as volatile at some specific times in the main line code, but not in the ISR. Don't know how to do that in C.

 

Looks like volatile is not precise enough. I wonder what happens if I just blindly cast it inside critical section:

ring_buf *mybuf_efficient = (ring_buf *)mybuf;

I'm afraid that would still be undefined and compiler-dependent behavior...

 

I would personally resort to assembly for something like this if it had to be as efficient and compact as possible.

 

That's an easy route but I'd try my best to avoid abstraction leakage, even when programming uC's.

 

-Yuri

[yugr 0]

If you weren't aware, you can apply the volatile qualifier to the fields in the structure, rather than to the object itself

 

Nice to know, although it won't help in this particular case.

 

The question is - do I need volatile if variable is already protected by _enable/disable_interrupts?

Yes. While some compilers may treat those intrinsics as sequence points, there is nothing about them that tells the compiler that it can't cache a copy of the variable that's being examined (for example, in a loop waiting for head to be updated) because somebody else might change it outside visible flow of control. That's what volatile does.

 

Hm, in gcc there's this infamous asm volatile ("" : : : "memory"); Maybe there's an equivalent in CCS compiler?

 

To avoid multiple reads of rx_bytes.head within the ISR, read it into a local variable, use and manipulate it, then write it back into the structure. This will be safe if the variable is not modified anywhere else.

 

Well, that is a solution but it'll force me to use internal details of my data type instead of nice abstract interface. Coming from PC world I strongly dislike abstraction leakage.

 

This will, of course, bite you in the butt if in three months you decide you need to spin-wait with interrupts enabled for the head to be updated by the ISR.

 

Good point but user code can only access this module with public API so it should not be a problem.

[Nytblade 24]

typedef struct {

char bytes[RING_BUF_SIZE];

unsigned head, tail;

} ring_buf;

#define rb_empty(rb) (rb.head == rb.tail)

#define rb_pop(rb, byte) do { \

byte = rb.bytes[rb.head]; \

rb.head = (rb.head + 1) & RING_BUF_SIZE_MASK; \

} while(0)

 

This is a little off-topic, but could you post the value of RING_BUF_SIZE and RING_BUF_SIZE_MASK? I am new at this and trying to understand how your binary & works.

[oPossum 1,083]

For that to type of ring buffer index to work RING_BUF_SIZE must be a power of 2 (1, 2, 4, 8, 16, 32, 64, ...) and RING_BUF_SIZE_MASK is simply RING_BUF_SIZE - 1

[Rickta59 589]

... edit needs more testing ...

 

-rick

[yugr 0]

For that to type of ring buffer index to work RING_BUF_SIZE must be a power of 2 (1, 2, 4, 8, 16, 32, 64, ...) and RING_BUF_SIZE_MASK is simply RING_BUF_SIZE - 1

 

Exactly!