Arduino Memory Utilisation Statistics using a Linked List Example

CatweazleNZ · August 2, 2014, 12:16am

All

In my home automation system at http://www.2wg.co.nz I am intending to use caching to optimise system performance by storing emails and activity records for a short time in an in-memory cache which is processed (emails sent, activity log records written to a file on an SD card) when the system becomes inactive. Sending emails is typically a multi-second internet activity and the current process of writing activity records line by line (open file, append one activity record line, close the file) is also inefficient.

My in-memory cache will be a linked list using dynamic memory allocation. In order for the cache to work reliably I need to ensure that I do not add more records to the linked list cache than there is available memory. This requires my application to have a precise and current knowledge of current memory utilisation and to force cache processing (clearance by sending emails and writing out the activity records) whenever free memory is getting low - even if the application is very busy doing something and the cache processing operation would cause application delays.

I have now completed a reimplementation of my memory utilisation procedure and built linked list cache functionality in a prototype application. This application generates random email and activity records, appends then dynamically to the linked list cache and clears the cache at random intervals by pretending to send emails and write activity records to SD card log files. When I run the application through a loop 99 times I get a very good profile of what is going on with my application's memory through all 99 iterations.

For anyone who wants to analyse and manage Arduino application memory use and for those interested in using linked lists within their applications I will attach the prototype application source code to this thread in another post(s) to overcome the 9500 byte post limitation.

For people who don't like using Arduino Strings and claim they can fragment HEAP memory this program provides an excellent demonstration. However I would point out that a simple change to this application to fully clear the cache from time to time (send the emails AND write the log records at the same time - one after the other) would eliminate HEAP fragmentation and reduce HEAP size and FREE HEAP space to zero. (And this is what I will do in my production system.)

In my production home automation system I intend to implement the new memory utilisation analysis procedure and the linked list cache. I will also let the application manage free space and under various conditions (including when free ram drops below 750 bytes) fully process and clear the cache.

I run my applications on a Freetronics Ethermega card if you need to know that.

Here is a sample or the Serial monitor output for the prototype application:

Setup
DATA/BSS 1043, HEAP 0, FREE 7063, STACK 86, TOTAL 8192, FREE HEAP 0, FREE LIST <<NULL>>
DATA/BSS 1043, HEAP 67, FREE 6996, STACK 86, TOTAL 8192, FREE HEAP 39, FREE LIST 39
DATA/BSS 1043, HEAP 127, FREE 6936, STACK 86, TOTAL 8192, FREE HEAP 67, FREE LIST 40, 23, 4
DATA/BSS 1043, HEAP 212, FREE 6851, STACK 86, TOTAL 8192, FREE HEAP 36, FREE LIST 23, 9, 4
<<EMAILS SEND>> 1
DATA/BSS 1043, HEAP 127, FREE 6936, STACK 86, TOTAL 8192, FREE HEAP 67, FREE LIST 40, 23, 4

...

DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 622, FREE LIST 290, 184, 61, 20, 20, 19, 9, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 594, FREE LIST 290, 184, 45, 20, 20, 9, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 562, FREE LIST 290, 184, 20, 20, 13, 9, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 444, FREE LIST 290, 99, 20, 9, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 412, FREE LIST 290, 47, 20, 20, 9, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 384, FREE LIST 290, 20, 20, 19, 9, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 352, FREE LIST 270, 20, 20, 9, 7, 7, 7, 7, 5
DATA/BSS 1043, HEAP 1136, FREE 5927, STACK 86, TOTAL 8192, FREE HEAP 320, FREE LIST 238, 20, 20, 9, 7, 7, 7, 7, 5

...

DATA/BSS 1043, HEAP 458, FREE 6605, STACK 86, TOTAL 8192, FREE HEAP 254, FREE LIST 195, 20, 20, 8, 7, 4
DATA/BSS 1043, HEAP 458, FREE 6605, STACK 86, TOTAL 8192, FREE HEAP 222, FREE LIST 163, 20, 20, 8, 7, 4
DATA/BSS 1043, HEAP 458, FREE 6605, STACK 86, TOTAL 8192, FREE HEAP 190, FREE LIST 131, 20, 20, 8, 7, 4
<<FINAL CACHE TO BE CLEARED>>
<<LIST OF CACHE RECORDS>>
Type 3, Item Activity 2512
Type 0, Item Email Connection
Type 1, Item Email Line 1
Type 1, Item Email Line 2
Type 2, Item Email Disconnect
Type 3, Item Activity 8276
Type 4, Item HTML Request 5391
Type 5, Item Hack Attempt 2411
Type 5, Item Hack Attempt 8571
Cache Record Count 9
DATA/BSS 1043, HEAP 458, FREE 6605, STACK 86, TOTAL 8192, FREE HEAP 190, FREE LIST 131, 20, 20, 8, 7, 4
<<EMAILS SEND>> 1
<<LIST OF CACHE RECORDS>>
Type 3, Item Activity 2512
Type 3, Item Activity 8276
Type 4, Item HTML Request 5391
Type 5, Item Hack Attempt 2411
Type 5, Item Hack Attempt 8571
Cache Record Count 5
DATA/BSS 1043, HEAP 458, FREE 6605, STACK 86, TOTAL 8192, FREE HEAP 306, FREE LIST 147, 131, 20, 8
<<LOG FILE WRITE>> 5
<<LIST OF CACHE RECORDS>>
Cache Record Count 0
DATA/BSS 1043, HEAP 0, FREE 7063, STACK 86, TOTAL 8192, FREE HEAP 0, FREE LIST <<NULL>>
End

Happy to answer questions.

Cheers

Catweazle NZ

CatweazleNZ · August 2, 2014, 12:17am

All

Here is most of the code:

//This defines the size of our list of the
//largest HEAP freelist memory blocks
//I normally keep this value at 5 or 6 because I am only interested in the larger blocks
//Currently set to 20 to show the extent of heap fragmentation
#define DC_HeapListCount 20

//These are our linked list cache record types
#define DC_Email_Connect 0
#define DC_Email_Line 1
#define DC_Email_Disconnect 2
#define DC_Activity_Log 3
#define DC_HTML_Request_Log 4
#define DC_Hack_Attempt_Log 5

//Define the nodes for our linked list cache
typedef struct TCacheItem *PCacheItem;
struct TCacheItem {
  String ItemData;
  byte Type;
  PCacheItem Next;
};  

//Set up the head and tail or the linked list cache
PCacheItem G_CacheHead;
PCacheItem G_CacheTail;
int G_CacheCount; //count of records in the cache

//--------------

void setup() { //Initialise
  Serial.begin(9600);
  Serial.println("");
  Serial.println("Setup");

  G_CacheHead = NULL;
  G_CacheTail = NULL;
  G_CacheCount = 0;
}

//--------------

void loop() {
  PrintMemoryStats(); //The baseline

  randomSeed(756851);
  for (int l_count = 1; l_count <= 99; l_count++)  {
    int l_action = random(10);
    if (l_action < 7) //70% of the time append new cache items
      AppendCacheRecord();
    else if (l_action < 9) //20% of the time clear cached emails
      EmailsSend();
    else //if (l_action == 9) //10% of the time clear our caches activity log records
      WriteLogFileRecords();
    //
    //After every task show how our memory statistics are moving
    PrintMemoryStats();
  }
  
  //Now we clear the final cached records
  Serial.println("<<FINAL CACHE TO BE CLEARED>>");
  ListCache(); //print the cache - may have email and activity records
  PrintMemoryStats();

  EmailsSend();
  ListCache(); //print the cache - only activity cache records left
  PrintMemoryStats();

  WriteLogFileRecords();
  ListCache(); //Nothing left in the cache

  //Should be back to the baseline (HEAP and FREE HEAP bothe zero)
  PrintMemoryStats(); 

  Serial.println("End");

  while (true) {
   ;
  }
}  

//--------------

void PrintMemoryStats() {
  //Extract current memory use statistics and print
  //them to the Serial monitor on a single line.
  int l_data_bss_size;
  int l_heap_size;
  int l_free_ram;
  int l_stack_size;
  int l_heap_free;
  int l_heap_list_sizes[DC_HeapListCount];

  //The source code for this is in the following post
  RamUsage(l_data_bss_size, l_heap_size, l_free_ram, l_stack_size, l_heap_free, l_heap_list_sizes);
  
  Serial.print("DATA/BSS ");
  Serial.print(l_data_bss_size);
  Serial.print(", HEAP ");
  Serial.print(l_heap_size);
  Serial.print(", FREE ");
  Serial.print(l_free_ram);
  Serial.print(", STACK ");
  Serial.print(l_stack_size);
  Serial.print(", TOTAL ");
  Serial.print(l_data_bss_size + l_heap_size + l_free_ram + l_stack_size);
  Serial.print(", FREE HEAP ");
  Serial.print(l_heap_free);
  Serial.print(", FREE LIST ");
  for (int l_index = 0; l_index < DC_HeapListCount; l_index++) {
    if (l_heap_list_sizes[l_index] == 0) {
      if (l_index == 0)
        Serial.print("<<NULL>>");
      //
      break;
    }
    if (l_index != 0)
      Serial.print(", ");
    //
    Serial.print(l_heap_list_sizes[l_index]);
  }
  Serial.println();
}

//--------------

void AppendCacheNode(byte p_type, String p_data) {
//Pass in the two data fields for this new linked list cache item
//Dynamically allocate some rame for this new cached item using new()
//malloc() cannot be used - it will not instantiate the cached item ItemData String
//Add the new cache record to the end of the cache linked list.
//We want to process (clear) the linked list later in chronological order
  PCacheItem l_Curr;
  l_Curr = new(TCacheItem);
  
  l_Curr->Type     = p_type;
  l_Curr->ItemData = p_data;
  l_Curr->Next     = NULL;
  
  if (G_CacheHead == NULL)
    G_CacheHead = l_Curr;
  else
    G_CacheTail->Next = l_Curr;
  //
  G_CacheTail = l_Curr;
  G_CacheCount++;

  //Serial.print(Curr->Type);
  //Serial.print(" ");
  //Serial.println(Curr->ItemData);
}  

//--------------

void AppendCacheRecord() {
//This procedure generates random linked list cache records.
//In the production application real data will be written to the cache.
  //Serial.println("<<APPEND>>");
  byte l_type =  random(6);
  if (l_type == 0) { //17% emails
    AppendCacheNode(DC_Email_Connect,"Email Connection");
    AppendCacheNode(DC_Email_Line,"Email Line 1");
    AppendCacheNode(DC_Email_Line,"Email Line 2");
    AppendCacheNode(DC_Email_Disconnect,"Email Disconnect");
  }
  else if (l_type < 3) //33% activity
    AppendCacheNode(DC_Activity_Log, String("Activity " + String(random(10000))));
  else if (l_type < 5) //33% HTML requests
    AppendCacheNode(DC_HTML_Request_Log, String("HTML Request " + String(random(10000))));
  else if (l_type = 5) //17% HTML hack attempts
    AppendCacheNode(DC_Hack_Attempt_Log, String("Hack Attempt " + String(random(10000))));
  //
}  

//--------------

void CacheNodeDelete(struct TCacheItem *&p_Prev, struct TCacheItem *&p_Curr) {
//Delete the current node from the linked list
//We may need to reset the value of Next in the previous node to skip the node we delete
//If the current node is the head of the linked list we need to update G_CacheHead
//If the current node is the end (tail) of the free list we need to adjust G_CacheTail to the new 

(prev) tail.
//We might be deleting the last node in the cache linked list so G_CacheHead & G_CacheTail are both 

reset to NULL.
  G_CacheCount--;
  if (p_Curr == G_CacheHead) {
    G_CacheHead = p_Curr->Next;
    delete(p_Curr); 
    if (G_CacheHead == NULL)
      G_CacheTail = NULL;
    //
    p_Curr = G_CacheHead; }
  else {
    p_Prev->Next = p_Curr->Next;
    delete(p_Curr);
    if (p_Prev->Next == NULL)
      G_CacheTail = p_Prev; //NULL
    //
    p_Curr = p_Prev->Next;
  } //
}

//--------------

void EmailsSend() {
//In the production application correct calls to email transmission
//functionality will be used to actually send the cached emails.
  Serial.print("<<EMAILS SEND>> ");
  PCacheItem l_Curr = G_CacheHead;
  PCacheItem l_Prev = NULL;
  int l_count = 0;
  while (l_Curr) {
    if (l_Curr->Type < 3) {
      if (l_Curr->Type == DC_Email_Connect) {
        //Serial.println(Curr->ItemData); //CONNECT
        l_count++;}
      else if (l_Curr->Type == DC_Email_Line) {
        ; //Serial.println(Curr->ItemData); //LINE
        }
      else if (l_Curr->Type == DC_Email_Disconnect) {
        ; //Serial.println(Curr->ItemData); //DISCONNECT
        }
      //
      CacheNodeDelete(l_Prev,l_Curr);
    }
    else {
      l_Prev = l_Curr;
      l_Curr = l_Curr->Next; 
    }
  } //while
  Serial.println(l_count);
} //EmailsSend 

//--------------

void WriteLogFileRecords() {
//In the production application this procedure will actually
//write the cached activity records to one of three logs files
  Serial.print("<<LOG FILE WRITE>> ");
  int l_count = 0;
  String l_filename = "";
  for (byte l_type = DC_Activity_Log; l_type <= DC_Hack_Attempt_Log;l_type ++) {
    if (l_type == DC_Activity_Log) {
      //Serial.println("ACTIVITY LOG");
      //Determine activity log filename
      //l_filename = "ACTVMMDD.TXT";
      }
    else if (l_type == DC_HTML_Request_Log) {
      //Serial.println("HTML REQUEST LOG");
      //Determine html request log filename
      //l_filename = "HTMMMDDZ.TXT";
      }
    else { //DC_Hack_Attempt_Log
      //Serial.println("HACK LOG");
      //Determine hack attempt log filename
      //l_filename = "HACKMMDD.TXT";
      }
    //
    //Open the log file here
    //File l_SDfile = SD.open(&l_filename[0], FILE_WRITE);
    PCacheItem l_Prev = NULL;
    PCacheItem l_Curr = G_CacheHead;
    while (l_Curr) {
      if (l_Curr->Type == l_type) {
        l_count++;
        //While the activity record to the log file
        //The correct log file is open;
        //l_SDFile.println(Curr->ItemData);
        CacheNodeDelete(l_Prev,l_Curr);
      } //selected file type
      else {
        l_Prev = l_Curr;      
        l_Curr = l_Curr->Next;
      } //
    }  //iterate through the list for this record type
    //close the log file here
    //l_SDFile.close();
  } //For each log file type
  Serial.println(l_count); //of log records written to a log file and removed from the cache
} //WriteLogFileRecords

//--------------

void ListCache() {
//In a production application we should not have to print
//out the cache to the Serial monitor.
  Serial.println("<<LIST OF CACHE RECORDS>>");
  PCacheItem l_Curr;
  l_Curr = G_CacheHead;
  while (l_Curr) {
    Serial.print("Type ");
    Serial.print(l_Curr->Type);
    Serial.print(", Item ");
    Serial.println(l_Curr->ItemData);
    l_Curr = l_Curr->Next;
  }
  Serial.print("Cache Record Count ");
  Serial.println(G_CacheCount);
}  

//--------------

Catweazle NZ

CatweazleNZ · August 2, 2014, 12:19am

All

Here is the final piece of the code that extracts the RAM/memory statistics:

void RamUsage(int &p_data_bss_size, int &p_heap_size, int &p_free_ram, int &p_stack_size, int 

&p_heap_free, int p_heap_list_sizes[]) {
//PART I - work out the basic memory split
//Total memory is (int)&__stack - (int)&__data_start + 1; 
//From bottom (low memory) to top (high memory) RAM divides as follows:
//DATA + BSS + H EA P>> (if any) + FREE + <<STACK
//"H EA P" indicates a heap with embedded free space.
//The HEAP moves up into FREE space and the STACK moves down into FREE space.
//If the two collide you are out of FREE ram and your program goes crazy.

  extern int __data_start, __stack,  __bss_end, __data_end, __heap_start, *__brkval, _end;
  
  p_data_bss_size = (int)&__bss_end - (int)&__data_start;

  int l_heap_end;
  //__brkval is a pointer
  if ((int)__brkval == 0)
    //If there are no heap records then the end of the heap is the start of the heap
    l_heap_end = (int)&__heap_start;
  else
    l_heap_end = (int)__brkval;
  //

  p_heap_size  = l_heap_end - (int)&__bss_end;
  p_free_ram   = (int)&l_heap_end - l_heap_end;
  p_stack_size = (int)&__stack - (int)&l_heap_end + 1;

//PART II - Walk the HEAP free linked list
//We count how many blocks of free space are hiding within the heap.
//We calculate the size of total HEAP free space.

  extern struct __freelist *__flp;
  struct __freelist {
    size_t sz;
    struct __freelist *nx;
  };
  struct __freelist *current;

  //Reset our heap free list of the largest free list memory blocks
  for (int l_index = 0; l_index < DC_HeapListCount; l_index++)
    p_heap_list_sizes[l_index] = 0;
  //

  //Now walk the free list
  p_heap_free = 0;
  int l_size; 
  for (current = __flp; current; current = current->nx) {
    l_size = (int) current->sz + 2; // Add two bytes for the memory block's header
    p_heap_free += l_size;
    //update our list of the largest heap free memory blocks
    for (int l_index = 0; l_index < DC_HeapListCount; l_index++) {
      if (p_heap_list_sizes[l_index] < l_size) { //Insert here - shuffle the list
        for (int l_index2 = DC_HeapListCount - 1; l_index2 > l_index; l_index2--)
          p_heap_list_sizes[l_index2] = p_heap_list_sizes[l_index2 - 1];
        //
        p_heap_list_sizes[l_index] = l_size;
        break;
      } //insert here and break
    } //iterate of free list to find the insertion point
  } //for each heap free list node
}

Cheers

Catweazle NZ

westfw · August 2, 2014, 5:22am

Nice. Your RamUsage() function is based on the way the avr-libc malloc/free work, right? (I HATE working with un-instrumented memory allocators. The one I'm used to kept all sorts of data...)

I run my applications on a Freetronics Ethermega card if you need to know that.

I was thinking that the 2k of RAM in an Uno wasn't going to allow you to cache very many "typical" email messages

CatweazleNZ · August 2, 2014, 9:25am

westfw:
Nice. Your RamUsage() function is based on the way the avr-libc malloc/free work, right? (I HATE working with un-instrumented memory allocators. The one I'm used to kept all sorts of data...)

Not sure - I harvested a few ideas here and there on the internet and did not attempt to trace back to their original sources.

"I run my applications on a Freetronics Ethermega card if you need to know that."

I was thinking that the 2k of RAM in an Uno wasn't going to allow you to cache very many "typical" email messages

My Freetronics Ethermega card has 256KB Flash, 8KB SRAM, 4KB EPROM and I use a 1GB SD card for data storage. My application runs to over 9000 lines of my own code and compiles to 134KB.

My application's emails are just short messages being sent to my iPhone using push emails whenever my system wants to tell me something important such as an intruder or fire alert. Typically a heading and one or two lines of detail in the email.

Cached data will be written out and cleared from the cache within a minute typically - I doubt the cache would exceed 1KB ever - but I will have code in place to prevent it causing minimum free ram to fall below a specified level - if RAM is getting too low the cache will be immediately cleared under application control.

I abandoned 2KB Arduino cards after about six weeks of development. That said I have had to learn a tremendous amount to get my application to comfortably fit within the 8KB RAM. You can check my application's memory utilisation at http://www.2wg.co.nz/34993/ - I currently run about 1200 bytes minimum RAM at any one time which is why I am implementing a cache to remove processing delays and increase application performance.

Cheers

Catweazle NZ

Glenn81 · August 2, 2014, 11:48am

Thanks !

Brilliant. I have used it to prove that the array allocation new[] works correctly in my post about pointer problems.
Thanks, again
Glenn

CatweazleNZ · August 3, 2014, 8:12am

Glenn81:
Thanks !

Brilliant. I have used it to prove that the array allocation new[] works correctly in my post about pointer problems.
Thanks, again
Glenn

Happy to be of assistance. In order to be sure any application will run error free long term you need to be sure that you have memory management under control. Something like my RAMUsage() procedure can be a big help managing Arduino memory within applications.

Catweazle NZ

Topic		Replies	Views
ESP Program Memory/ RAM: Avoiding using too much Programming	66	1005	June 30, 2025
Memory questions UNO R4 Minima	18	577	January 5, 2025
Trying to better understand memory usage Programming	42	2622	August 6, 2023
Memory usage with delete keyword in a sketch Programming	44	384	May 18, 2025
Sketch size and memory Programming	40	452	July 6, 2025

Arduino Memory Utilisation Statistics using a Linked List Example

Related topics