Linked Lists & ISRs

Go To Last Post
19 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm working on some linked lists that get modified both inside and outside ISRs, and sometimes result in corruption.  I've tried to wrap all the relevant bits that modify the list in ATOMIC_BLOCK macros, but ultimately, the same thing happens.  If I throw too much data at the list too fast, it gets confused.  

 

Rather than struggling to create my own, I was hoping there was an existing void* list that was statically allocated and ISR/Thread safe that I might be able to use.  Does anybody know of one?  If none exists, I'll post my code and ask for anybody's help diagnosing it.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Do you have all the necessary volatiles ?

 

Do you really need to be doing the lists in the ISR?

 

Not sure that static vs dynamic allocation would make any difference here.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I've checked and double checked.  All the pointers are volatile whenever they're in the list.  When I pull the objects out of the list, I cast away their volatile.  They include a volatile status flag to indicate free/inuse.

 

THe purpose of the ISR is to pass messages back to main to be processed in the main loop.  The serial data is stuffed into a string.  The string gets shoved into a list and then a callback is called.  Main can then parse that string at leisure, and return the string/list item setup to the pool with a simple function call.  I trimmed out some unnecesarry code to keep a "Free list", since the status flag is enough to ensure I can always find a free list node if one exists.

 

Static allocation is because the application is very memory constrained.  9x% RAM usage.  I need to start counting bits.  Most of this is output buffers :-S

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Enable and disable interrupts during the link list routines that change the link parameters

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You only need the atomic_block wrapper for your non isr accesses. Have you checked to see that your stack isn’t colliding with the list?
Do you really need to use callbacks ? If it is a small system, then the number of call targets is probably small.

Last Edited: Wed. Dec 6, 2017 - 07:39 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This

aarcane wrote:
THe purpose of the ISR is to pass messages back to main to be processed in the main loop.  The serial data is stuffed into a string.  The string gets shoved into a list and then a callback is called.

And this

the application is very memory constrained

Don't seem to jive!

 

Why not just use a so-called Ring Buffer (aka "Circular Buffer" or "FIFO")?

 

That would be the more usual approach, I think ...

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 2

aarcane wrote:
9x% RAM usage.
Does that really mean 90%..99% ?? If so there's no hope of that code working. That figure is just link time allocation and doe not include stack and heap usage. Even without the heap you need that down at 80% or below. For Heap use it depends how heavily you use it but maybe below 50% ?

 

Which AVr is this? How much RAM?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
That figure is just link time allocation and doe not include stack and heap usage.

I recently did a sketchy analysis of a case here to give a picture of some of the aspects of RAM usage at runtime. It's here: http://www.avrfreaks.net/comment... . It might give you a hunch about that there's much more to RAM usage than the figure presented at the end of a build. You need to read the surrounding posts to get a reasonably clear picture.

Happy 75th anniversary to one of the best movies ever made! Rick Blane [Bogart]: "Of all the gin joints, in all the towns, in all the world, she walks into mine."

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Overall the project has sufficient RAM.  communication with the outside world being the largest offender.  The end of build report is:

 

Program Memory Usage : 17392 bytes   53.1 % Full
Data Memory Usage : 1783 bytes   87.1 % Full

 

With the data memory including: 

#define AERIAL_RECV_LINE_LEN 80
#define AERIAL_RECV_NUM_LINES 2
#define AERIAL_SEND_LINE_LEN 240
#define AERIAL_SEND_NUM_LINES 2

 

These are defined like so:

typedef struct ae_recv_line ae_recv_line;
struct ae_recv_line
{
    volatile char status;
    size_t len;
    char data[AERIAL_RECV_LINE_LEN];
    volatile ae_recv_line* next;
};

typedef struct ae_send_line ae_send_line;
struct ae_send_line
{
    volatile char status;
    size_t len;
    size_t idx;
    char data[AERIAL_SEND_LINE_LEN];
    volatile ae_send_line* next;
};

 

and these use up a significant portion of available RAM.  As for other functions throughout the project, they mainly pass pointers and indices around to globally defined state variables and structures.  memory copies are generally kept to a minimum, there is no heap usage.  No malloc or friends.  No recursion.  Maximum call depth hasn't been rigorously analyzed, but should run approximately 6-ish functions deep, the bottom levels of which are all defined static inline since I've plenty of program space to play with.  The big problem is the passing back of long status reports and data dumping of complex control structures.

 

That's why I'm dynamically selecting an available object into which to stuff a string for send or receive.  Anyway, last night I pretty much sorted everything out.  It's all working perfectly, and if my employer will let me, I'll release the full code of the serial library I had to write since nobody else has a good one out right now.

Last Edited: Wed. Dec 6, 2017 - 07:40 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Kartman wrote:
Do you really need to use callbacks ? If it is a small system, then the number of call targets is probably small.

 

The callback is generated by an ISR.  In response to this callback, main is expected to perform some action which may include sending several messages over serial, or other long-running tasks.  Multiple of these tasks may be queued up at once (presently 2, possibly as many as 4 in another project using the same code).  Yes, I really need callbacks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How to properly post source code: http://www.avrfreaks.net/comment...

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

aarcane wrote:
Yes, I really need callbacks.

Well, suit yourself.  The raw numbers shown of 80+% static RAM usage are scary.  Not necessarily drop-dead but certainly the alarm is going off.  and you've shown lots of large buffers, so you know where the usage is.

 

As I said -- suit yourself.  If you have chosen to use a microcontroller with limited SRAM resources, then perhaps you cannot use the straight-forward approach of "unlimited" buffers.  Perhaps some messages need to be parsed/built "on the fly" a token at a time.  "Need" callbacks?  You are further straining stack usage with callbacks. Yes, they might be the most convenient for e.g. ModbusRTU.  But one can "unroll" them with the needed code inline and invoked by conditional logic; then the compiler can do more save/restore optimization.

 

It is a tradeoff that you will need to decide on.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

aarcane wrote:
Overall the project has sufficient RAM.

 

No it does not, see reply #7!

Is there a RTOS involved here?

 

Jim

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ki0bk wrote:

Is there a RTOS involved here?

 

I gave serious consideration to using one, but given that it would introduce overhead and I only have a single CPU thread with ISRs, I decided that adding the functionality of an RTOS was overkill.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

aarcane wrote:
Data Memory Usage : 1783 bytes 87.1 % Full

Which leaves 265 bytes free for run-time allocation.

 

Six levels of calls will eat (maximum) 12 bytes of that for return addresses. If yo're not allocating much local storage, i.e. not passing structs, not defining large(ish) local variables (structs, arrays) then 250'ish bytes should suffice.

 

Your description of how and what you allocate suggests you know what you're doing. (-:

 


 

Re code for a circular buffer, perhaps have a look at Dean Cameras work? Here: http://www.fourwalledcubicle.com... .

 

(Dean Camera is the person behind the LUFA USB framework for AVRs. He's also, IIRC, the one who took the initiative for the ATOMIC_BLOCK macros in the avr-gcc runtime library, avrlibc. I have not seen anything he has produced that has been other than top notch.)

Happy 75th anniversary to one of the best movies ever made! Rick Blane [Bogart]: "Of all the gin joints, in all the towns, in all the world, she walks into mine."

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JohanEkdahl wrote:

If yo're not allocating much local storage, i.e. not passing structs, not defining large(ish) local variables (structs, arrays) then 250'ish bytes should suffice.

Nothing fancy gets allocated on either stack nor heap.  A few uint8_ts, a couple size_ts, and some struct*s.  Everything else is global/static.

 

JohanEkdahl wrote:

Your description of how and what you allocate suggests you know what you're doing. (-:

Thank you.  I'm good at what I do, just not at talking about it.

 

JohanEkdahl wrote:

Re code for a circular buffer, perhaps have a look at Dean Cameras work? Here: http://www.fourwalledcubicle.com... .

That code is beautiful, but it leaves some interesting loopholes, such as double reading from the buffer, pointer manipulation outside atomic_blocks, and read-past-ends on the buffer.  Otherwise, it looks like a solid replacement for linked lists in my use case.

 

It would really only save me one ptr per object though, and would add 6 bits per buffer, as well as introduce a new dependency if I'm able to release the serial library.  Since I'm working with relatively short lists, I don't think I need to switch, but I'll keep it in mind for future use.  Thanks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

aarcane wrote:
That code is beautiful, but it leaves some interesting loopholes, such as double reading from the buffer,

I don't see any double reading from the buffer. Which function does that?

 

aarcane wrote:
pointer manipulation outside atomic_blocks,

The functions are well documented that "Insertion and removal may occur from different execution threads." You just can't insert into, or remove from, a buffer from two execution threads, "otherwise data corruption may occur". If you want to do so you can wrap ATOMIC_BLOCK around your calls to RingBuffer_Insert or RingBuffer_Remove.

 

aarcane wrote:
and read-past-ends on the buffer.

I don't see any of that happening in the code. Are you think of lines like this?

if (++Buffer->Out == &Buffer->Buffer[BUFFER_SIZE])

That is not accessing an element past the end of the buffer. That line is perfectly legal.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

christop wrote:

aarcane wrote:
That code is beautiful, but it leaves some interesting loopholes, such as double reading from the buffer,

I don't see any double reading from the buffer. Which function does that?

aarcane wrote:
pointer manipulation outside atomic_blocks,

The functions are well documented that "Insertion and removal may occur from different execution threads." You just can't insert into, or remove from, a buffer from two execution threads, "otherwise data corruption may occur". If you want to do so you can wrap ATOMIC_BLOCK around your calls to RingBuffer_Insert or RingBuffer_Remove.

 

You're correct, it is documented.

 

christop wrote:

aarcane wrote:
and read-past-ends on the buffer.

I don't see any of that happening in the code. Are you think of lines like this?

if (++Buffer->Out == &Buffer->Buffer[BUFFER_SIZE])

That is not accessing an element past the end of the buffer. That line is perfectly legal.

 

It won't perform an out of bounds read on the actual internal array named Buffer, but it will allow you to read past the end of the circular buffer data type to the point where there's no valid data to be read and Out is now located after In.

Last Edited: Wed. Dec 6, 2017 - 11:22 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

aarcane wrote:

It won't perform an out of bounds read on the actual internal array named Buffer, but it will allow you to read past the end of the circular buffer data type to the point where there's no valid data to be read and Out is now located after In.

 

Aha! I see what you mean. Apparently the caller is expected to check to see if there's any data to read from or space to write into the queue?