Problems with a string stack library

Hi, this is a follow on post from an issue I was having last week.

First some background, I’m writing an application that involves creating and sending SMS messages, if the signal strength is too weak to send the message, then I need to store the message in a list until it’s strong enough. If the signal strength stays too weak for too long then I need to start deleting the oldest messages from the message list whilst still adding new messages. Once the signal strength has been restored I need to send the whole stack of messages starting with the most recent.

To do this I’ve written a library (MiniStack.h and MiniStack.cpp, attached) and a test sketch to demonstrate it.

MiniStack.h

#ifndef MiniStack_h     //These lines (together with the #endif at the end of the file) prevent
#define MiniStack_h     //any problems occuring if this library should be included twice.

extern "C" {
  #include <string.h>
}

#include <stdlib.h>    //needed for 'free'
#include "WProgram.h"  //needed for 'Serial'


// Define the limits of the stack
#define max_chars      160
#define max_elements   12

class STACK
{
  public:

    // Constructor
    STACK(void);

    // Add a new element (i.e. string) to the array
    void AddNew(char *new_element);

    // Remove the rightmost (i.e. the newest) element from the array 
    void RemoveNew();

    // Get the rightmost (i.e. the newest) element from the array
    char* GetNew();

    // Display the full stack
    void DisplayAll();

    // Get the actual number of messages currently in the stack
    inline int GetActSize(){return sms_list_size;}


  private:
    
    char sms_mess[max_chars+1];       //full sms message (header, timestamp, location fixes and checksum)
    char *sms_list[max_elements];     //array of messages, as yet un-transmitted

    int sms_list_size;                //actual size of sms_list. (number of populated elements)

    // shift every element in the array one place to the left whislt keeping the overall array size the same
    // this will have the effect of dropping the left-most element (i.e. the oldest item on the stack) and
    // freeing up the right most element. This should only be used when a new element has to be added but 
    // the stack is already full
    void LeftShift();
    
    // endless loop. This is get around the the fact that I can't find a 'stop' function for arduino.
    // it traps the processing in an endless loop that gives me the time to examine the screen output
    // before it gets scrolled off the top.
    void EndlessLoop();

};

#endif

MiniStack.cpp

//#include <MiniStack.h>

#include "MiniStack.h"

extern "C" {
  #include <string.h>
}

#include <stdlib.h>    //needed for 'free'
#include "WProgram.h"  //needed for 'Serial'


// Constructor
STACK::STACK()
{
}

////Destructor 
//STACK::~STACK()
//{
//  end();
//}

void STACK::AddNew(char *new_element)
{
  //add a new message to the array. Records will be added as they arrive from left to right.
  //therefore the rightmost fix should allways be the most recent

  if (sms_list_size == max_elements)
  {
    //The array of messsages is already at maximum, therefore discard the oldest fix 
    //to make room for the newest.
    LeftShift();
  }

  //add fix to array. Before attempting it, check that the string isn't too big
  if ( strlen(new_element) > max_chars )
  {
    Serial.print("Error, about to strdup. Source length=<"); Serial.print(strlen(new_element));Serial.print(">. Destination size=<");Serial.print(max_chars);Serial.println(">");
    Serial.print("Existing element=<");Serial.print(sms_list[sms_list_size]);Serial.println(">");
    EndlessLoop();
  }
  sms_list[sms_list_size]=strdup(new_element); //copy the current message into the array of messages. Note this uses malloc, and will therefore
                                               //increase the amount of memory being used.
  //strcpy(sms_list[sms_list_size],new_element);

  sms_list_size++;                             //increment the counter that records the number of SMSs waiting to be transmitted.
  //curr_sms[0]=0;                               //clear / reset the current SMS message
}

void STACK::LeftShift()
{
  //shift the entire contents of the SMS array left one element. The leftmost element will be lost and
  //a space will be freed up on the righthand side

  free(sms_list[0]);                     //frees up the memory for the 1st (i.e. leftmost element in the array). Note - this
                                         //should free up the same amount of memory taken up with the strdup command earlier.
                                         //so there should be no net increase in memory usage.
  sms_list[0]=0;
  for (int n=0; n<sms_list_size; n++)
  {
    sms_list[n]=sms_list[n+1];
  }
  sms_list[sms_list_size-1]=0;           //frees up the pointer to the 'newest' element in memory
  sms_list_size--;                       //decrement the counter that records the number of fixes waiting to be transmitted.
}


void STACK::DisplayAll()
{
  //display the whole list
  Serial.println("Whole stack follows....."); 
  for (int n=0; n<=max_elements-1; n++)
  {
    Serial.print(n); Serial.print("  ");
    Serial.println(sms_list[n]);
  }
}

char* STACK::GetNew()
{
  //display the rightmost message in the arry (i.e. most recently added)
  return sms_list[sms_list_size-1];
}

void STACK::RemoveNew()
{
  //Set the rightmost element of the message array to null. 
  
  if (sms_list_size >= 1)            //Check index will be within bounds
  {
    free(sms_list[sms_list_size-1]); //free up the memory
    sms_list[sms_list_size-1]=0;     //delete/reset the pointer to the memory
    sms_list_size--;                 //decrement the size counter
  }
}

void STACK::EndlessLoop()
{
  // Endless loop to 'stop' processing. This allows errors to be trapped and examined on the screen
  // before they scroll off the top of the screen!
  while ( 1==1 )
  {
    Serial.print(".");
    //Pause 5 seconds
    delay(5000);
  }
}

The good news is that this all WORKS. The bad news is that I can’t get it to work reliably once I include it in my project. The example sketch I’ve attached seems to work all the time, once embed in the full application it seems to fail (i.e. hang) at random intervals, as far as I can tell it hangs when it gets to the strdup function in Addnew(). I know that strdup calls malloc, and I do call ‘free’ to release the memory later, however I think this may be at the root of the problem. I’ve tried to re-write the function using strcpy instead (which doesn’t call malloc) but I can’t get this to work. I’ve tried to produce an example sketch that will fail and therefore illustrate the problem but haven’t managed this either.

What I’d like is
a) Some experienced eyes to have a look at my code and ‘sanity check’ it. And, either
b) Spot the bug, or
c) Suggest a different approach to solve the problem.

Failing that, does anyone know of library that already does what I’ve after? This is my least favourite option, I’d much prefer to understand what I’ve done wrong.

Finaly, please speak slowly in your replies, I’m new to all this!

Unfortunately I can’t really include the whole project here, it relies on other libraries and custom built shields.

P.S. Example sketch to demo the library included in next post.

Thanks

Mike

Example sketch as promised…

#include <MemoryFree.h>
#include <MiniStack.h>


// NOTE - these 2 variables need to be set to the same values as 'max_chars' and 'max_elements'
// in MiniStack.h
const int sms_len = 160;             //maximum allowable SMS length
const int max_sms_list_size = 12;    //number of unsent SMSs that can be stored

char curr_sms[sms_len+1];            //current sms.
int mess_seq_num=0;                  //message sequence number
const int max_mess_seq_num=9999;     //maximum message sequence number (before reseting back to 0)
char mess_text[]="MyMessage-";

STACK mystack;

int sms_list_size=0;                 //actual size of sms_list. (number of populated elements)
long sms_lost=0;                     //counts number of messages lost because the buffer was full.

// random number
long randNumber=0;

void setup()
{
  Serial.begin(115200);                     //Communication speed for the display
  Serial.println("Starting.........");
  randomSeed(analogRead(0));
}

void loop()
{

  Serial.println();Serial.print("freeMemory reports <");Serial.print( freeMemory() );Serial.println("> (bytes) free");
  
  //create a random message
  createMess();
  
  //add message to the stack
  mystack.AddNew(curr_sms);

  //display the current message
  Serial.print("Current message is <");Serial.print(curr_sms);Serial.println(">");
  
  //display the stack
  mystack.DisplayAll();
  
  Serial.println("Current message is.....");
  Serial.print(" <");Serial.print(mystack.GetNew());Serial.println(">");

  //When signal strength is good enough, the most recent message should be sent and removed from the
  //array. Simulate this with a one in 4 chance of success.....
  int randNumber = random(4);
  if (randNumber == 1)
  {
    //Remove a random number (between zero and all) of messages from the stack
    int n=random(mystack.GetActSize());
    Serial.print("Removing most recent <");Serial.print(n);Serial.println("> messages");
    for (int i=0 ;i<n; i++)
    {
      Serial.println("About to remove the following message from the stack.");
      Serial.print(" <");Serial.print(mystack.GetNew());Serial.println(">");
      
      //Remove the rightmost (i.e. the most recent) message from the array.
      mystack.RemoveNew();
    }
  }

  //slow things down a bit...
  delay(1000);
}


void createMess()
{
  // Creates a simple, variable length text string for example only
  int message_size;
  char mess_seq_str[4+1];              //message sequence number expressed as a string
  
  message_size=random(1,8);
  
  sprintf(mess_seq_str,"%.4d",mess_seq_num);    //format the sequence number as a four digit string with leading zeros
  
  curr_sms[0]=0; //reset/clear the current message
  
  //create a message 
  for (int i=0; i<message_size ;i++)
  {
    strcat(curr_sms,mess_text);
    strcat(curr_sms,mess_seq_str);
  }

  //increment or reset the counter
  if (mess_seq_num < max_mess_seq_num)
  {
    mess_seq_num++;
  }
  else
  {
    mess_seq_num=0;
  }
}
#define max_chars      160
#define max_elements   12

That's 1,920 bytes. These 1,920 bytes are all allocated in SRAM. You have 2K bytes of SRAM on the Duemilanove. That 2K includes the message arrays and function call return data and other stuff.

It looks to me like you are simply running out of memory.

Sorry Paul I should have said, I'm using a Mega so I don't think memory is currently a problem. (I'm also using the MemoryFree.h library to monitor free memory on each iteration)

Regards

The next thing that I would do, then, is store the return pointer from strdup in a local pointer variable, and confirm that the pointer is valid before storing it in the array.

Not sure I follow, how do I do that? I'm new to C. The code seems to be hanging on the strdup command. Both the existing element sms_list[sms_list_size] and the new message (new_element) seem to be valid before the operation.

Cheers.

char *tmp = strdup(new_element);
if(tmp)
  sms_list[sms_list_size] = tmp;
else
  Serial.println("Going to hell in a handbasket; Send money, guns, and lawyers);

Thanks Paul
I’ve added your code snippet, but I am getting more puzzled than enlightened. The code snippet isn’t a fix, it should just provide a flag to warn that something has gone wrong, however what actually happened is that this change caused my project to hang at another entirely unrelated location.

In desperation I have written another even cruder stack library that does the job but is hardcoded to a fixed size stack of fixed size strings.

This new library WORKS, both in the test sketch and the full application. To me this is strongly indicative that the library was causing the problem, and the rest of the application is ok. However, I’d still like to know what’s wrong with the original library if anyones got any idea? Since I haven’t been flooded with people pointing out stupid mistakes I assume my library ‘looks about right’ even if it doesn’t actually work!

The new library is included here. Any comments appreciated?

MiniStack2.h

#ifndef MiniStack2_h     //These lines (together with the #endif at the end of the file) prevent
#define MiniStack2_h     //any problems occuring if this library should be included twice.

extern "C" {
  #include <string.h>
}

#include <stdlib.h>    //needed for 'free'
#include "WProgram.h"  //needed for 'Serial'


// Define the limits of the stack
#define max_chars      160
#define max_elements   12

class STACK
{
  public:

    // Constructor
    STACK(void);

    // Add a new element (i.e. string) to the array
    void AddNew(char *new_element);

    // Remove the rightmost (i.e. the newest) element from the array 
    void RemoveNew();

    // Get the rightmost (i.e. the newest) element from the array
    char* GetNew();

    // Display the full stack
    void DisplayAll();

    // Get the actual number of messages currently in the stack
    inline int GetActSize(){return sms_list_size;}


  private:
    
    char sms_mess[max_chars+1];       //full sms message (header, timestamp, location fixes and checksum)
    char *sms_list[max_elements];     //array of messages, as yet un-transmitted

    char sms_list_01[max_chars+1];
    char sms_list_02[max_chars+1];
    char sms_list_03[max_chars+1];
    char sms_list_04[max_chars+1];
    char sms_list_05[max_chars+1];
    char sms_list_06[max_chars+1];
    char sms_list_07[max_chars+1];
    char sms_list_08[max_chars+1];
    char sms_list_09[max_chars+1];
    char sms_list_10[max_chars+1];
    char sms_list_11[max_chars+1];
    char sms_list_12[max_chars+1];

    int sms_list_size;                //actual size of sms_list. (number of populated elements)

    // shift every element in the array one place to the left whislt keeping the overall array size the same
    // this will have the effect of dropping the left-most element (i.e. the oldest item on the stack) and
    // freeing up the right most element. This should only be used when a new element has to be added but 
    // the stack is already full
    void LeftShift();
    
    // endless loop. This is get around the the fact that I can't find a 'stop' function for arduino.
    // it traps the processing in an endless loop that gives me the time to examine the screen output
    // before it gets scrolled off the top.
    void EndlessLoop();

};

#endif

MiniStack2.cpp

//#include <MiniStack2.h>

#include "MiniStack2.h"

extern "C" {
  #include <string.h>
}

#include <stdlib.h>    //needed for 'free'
#include "WProgram.h"  //needed for 'Serial'


// Constructor
STACK::STACK()
{
}

////Destructor 
//STACK::~STACK()
//{
//  end();
//}

void STACK::AddNew(char *new_element)
{
  //add a new message to the array. Records will be added as they arrive from left to right.
  //therefore the rightmost fix should allways be the most recent

  if (sms_list_size == max_elements)
  {
    //The array of messsages is already at maximum, therefore discard the oldest fix 
    //to make room for the newest.
    LeftShift();
  }

  // copy the new entry into the next available slot
  switch (sms_list_size)
  {
    case 0:
      strcpy(sms_list_01,new_element);
      break;
    case 1:
      strcpy(sms_list_02,new_element);
      break;
    case 2:
      strcpy(sms_list_03,new_element);
      break;
    case 3:
      strcpy(sms_list_04,new_element);
      break;
    case 4:
      strcpy(sms_list_05,new_element);
      break;
    case 5:
      strcpy(sms_list_06,new_element);
      break;
    case 6:
      strcpy(sms_list_07,new_element);
      break;
    case 7:
      strcpy(sms_list_08,new_element);
      break;
    case 8:
      strcpy(sms_list_09,new_element);
      break;
    case 9:
      strcpy(sms_list_10,new_element);
      break;
    case 10:
      strcpy(sms_list_11,new_element);
      break;
    case 11:
      strcpy(sms_list_12,new_element);
      break;
  }


  sms_list_size++;                             //increment the counter that records the number of SMSs waiting to be transmitted.
}

void STACK::LeftShift()
{
  //shift the entire contents of the SMS array left one element. The leftmost element will be lost and
  //a space will be freed up on the righthand side

  strcpy(sms_list_01,sms_list_02);
  strcpy(sms_list_02,sms_list_03);
  strcpy(sms_list_03,sms_list_04);
  strcpy(sms_list_04,sms_list_05);
  strcpy(sms_list_05,sms_list_06);
  strcpy(sms_list_06,sms_list_07);
  strcpy(sms_list_07,sms_list_08);
  strcpy(sms_list_08,sms_list_09);
  strcpy(sms_list_09,sms_list_10);
  strcpy(sms_list_10,sms_list_11);
  strcpy(sms_list_11,sms_list_12);
  sms_list_12[0]=0;

  sms_list_size--;                       //decrement the counter that records the number of fixes waiting to be transmitted.
}


void STACK::DisplayAll()
{
  //display the whole list
  Serial.println("Whole stack follows....."); 
  Serial.print("1  ");Serial.println(sms_list_01);
  Serial.print("2  ");Serial.println(sms_list_02);
  Serial.print("3  ");Serial.println(sms_list_03);
  Serial.print("4  ");Serial.println(sms_list_04);
  Serial.print("5  ");Serial.println(sms_list_05);
  Serial.print("6  ");Serial.println(sms_list_06);
  Serial.print("7  ");Serial.println(sms_list_07);
  Serial.print("8  ");Serial.println(sms_list_08);
  Serial.print("9  ");Serial.println(sms_list_09);
  Serial.print("10 ");Serial.println(sms_list_10);
  Serial.print("11 ");Serial.println(sms_list_11);
  Serial.print("12 ");Serial.println(sms_list_12);
  Serial.print("Stack size is <");Serial.print(sms_list_size);Serial.println(">");

}

char* STACK::GetNew()
{
  //display the rightmost message in the arry (i.e. most recently added)

  switch (sms_list_size)
  {
    case 1:
      return sms_list_01;
      break;
    case 2:
      return sms_list_02;
      break;
    case 3:
      return sms_list_03;
      break;
    case 4:
      return sms_list_04;
      break;
    case 5:
      return sms_list_05;
      break;
    case 6:
      return sms_list_06;
      break;
    case 7:
      return sms_list_07;
      break;
    case 8:
      return sms_list_08;
      break;
    case 9:
      return sms_list_09;
      break;
    case 10:
      return sms_list_10;
      break;
    case 11:
      return sms_list_11;
      break;
    case 12:
      return sms_list_12;
      break;
  }



}

void STACK::RemoveNew()
{
  //Set the rightmost element of the message array to null. 

  switch (sms_list_size)
  {
    case 1:
      sms_list_01[0]=0;
      break;
    case 2:
      sms_list_02[0]=0;
      break;
    case 3:
      sms_list_03[0]=0;
      break;
    case 4:
      sms_list_04[0]=0;
      break;
    case 5:
      sms_list_05[0]=0;
      break;
    case 6:
      sms_list_06[0]=0;
      break;
    case 7:
      sms_list_07[0]=0;
      break;
    case 8:
      sms_list_08[0]=0;
      break;
    case 9:
      sms_list_09[0]=0;
      break;
    case 10:
      sms_list_10[0]=0;
      break;
    case 11:
      sms_list_11[0]=0;
      break;
    case 12:
      sms_list_12[0]=0;
      break;
  }

  sms_list_size--;

}

void STACK::EndlessLoop()
{
  // Endless loop to 'stop' processing. This allows errors to be trapped and examined on the screen
  // before they scroll off the top of the screen!
  while ( 1==1 )
  {
    Serial.print(".");
    //Pause 5 seconds
    delay(5000);
  }
}

In your original code, you have calls to free, in LeftShift() and RemoveNew() that assume that the array contains a valid pointer. The value in the array should be confirmed to be valid before being passed to free. I doubt that this is causing your problem, but it is always a good idea to trap every possible error, before it snarls and bites you in the derriere.

    sms_list[sms_list_size-1]=0;     //delete/reset the pointer to the memory

The array element really should be set to NULL, to acknowledge that the array element IS a pointer.

Other than these nits, I really can't see anything wrong with the code.

thanks paul