Go Down

Topic: Avrheap class - peek into the heap  (Read 370 times) previous topic - next topic

robtillaart

Oct 26, 2015, 08:09 pm Last Edit: Dec 10, 2015, 08:24 pm by robtillaart
Latest version - https://github.com/RobTillaart/Arduino/tree/master/libraries/AvrHeap

Yesterday I wrote a class to peek into the heap of an Arduino UNO (IDE1.5.8 ). It is still beta but complete enough to share. The library can be used to analyse the effect of dynamic memory allocating classes (like String) on the heap - do they cause fragmentation and if so how much?

The class extends code discussed here - http://forum.arduino.cc/index.php?topic=27536.15 -

Code: ("demo sketch") [Select]
//
//    FILE: heapdemo.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: heapdemo
//    DATE: 2015-10-25
//     URL:
//
// Released to the public domain
//

#include "avrheap.h"

Avrheap myheap;

int *par[10];

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);
  Serial.println(AVRHEAP_LIB_VERSION);

  Serial.println();
  Serial.print("HEAP ADDR:\t");
  Serial.println(myheap.startAddress());
  Serial.println();

  // allocate 10 chunks
  Serial.println("ptr\taddr");
  for (int i = 0; i < 10; i++)
  {
    par[i] = (int*) malloc(i * 3);  // all different sizes
    *par[i] = 0;
    Serial.print(i);
    Serial.print('\t');
    Serial.println((int)par[i], DEC);
  }
  Serial.println();
  Serial.println();
  myheap.dump(80);
  Serial.println("\nfollowHeap");
  myheap.followHeap();


  Serial.print("fragmented: ");
  Serial.println(myheap.isFragmented() ? "True" : "False");
  Serial.print("count: ");
  Serial.println(myheap.freeListCount());
  Serial.print("size: ");
  Serial.println(myheap.freeListSize());
  Serial.println("dump: ");
  myheap.freeListDump();

  Serial.println("free 3 pointers");
  free(par[3]);
  free(par[5]);
  free(par[7]);

  Serial.print("fragmented: ");
  Serial.println(myheap.isFragmented() ? "True" : "False");
  Serial.print("count: ");
  Serial.println(myheap.freeListCount());
  Serial.print("size: ");
  Serial.println(myheap.freeListSize());
  Serial.println("dump: ");
  myheap.freeListDump();

  Serial.println("1 malloc");
  par[3] = (int*) malloc(10);

  Serial.print("fragmented:\t");
  Serial.println(myheap.isFragmented() ? "True" : "False");
  Serial.print("count:\t");
  Serial.println(myheap.freeListCount());
  Serial.print("size:\t");
  Serial.println(myheap.freeListSize());
  Serial.println("dump: ");
  myheap.freeListDump();

  Serial.println();
  myheap.dump(80);
  Serial.println("\nfollowHeap");
  myheap.followHeap();
  Serial.println("\ndone");
}

void loop()
{}


partial output
followHeap
addr   size
657      2
661      3
666      6
674      9    (free)
685      12
699      3    (free)
704      10
716      18
736      21    (free)
759      24
785      27



The above output shows the heap is fragmented and has 3 free positions in memory => the heap consists of 4 fragments.

TODO:
* testing
* add more (visualization) methods
* add other memory related functions
* derive class from printable to allow Serial.print(myHeap); and get the output of followHeap
* improve naming of methods (class?), refactor etc
* add to github when stabilized.

As always remarks and comments are welcome.

(library version 0.1.02 see attachment)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

update: the dump() method is wrong, to be replaced by a good one.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Whandall

I played a little with your heap library.

Code: [Select]
//
//    FILE: heapdemo.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: heapdemo
//    DATE: 2015-10-25
//     URL:
//
// Released to the public domain
//

#include "avrheap.h"

Avrheap myheap;

int *par[10];

void setup()
{
  int seed = analogRead(A0) + analogRead(A3) + analogRead(A2);
  seed ^= (int)micros();
  randomSeed(seed);
  Serial.begin(115200);
  Serial.print(F("Start "));
  Serial.print(F(__FILE__));
  Serial.print(F("\nLibVersion "));
  Serial.println(F(AVRHEAP_LIB_VERSION));

  Serial.println();
  Serial.print(F("HEAP ADDR: "));
  hWord(Serial, myheap.startAddress());
  Serial.println();

  Serial.println(F("\nallocate 10 chunks\n"));
  for (int i = 0; i < 10; i++)
  {
    int mSize = random(1, 40) * sizeof(int);
    par[i] = (int*) malloc(mSize); // all different sizes
    *par[i] = 0;
    dumpAlloced((byte*)par[i], false);
  }
  Serial.println();

  myheap.dumpHeap(80);
  Serial.println();
  Serial.println(myheap);
  myheap.freeListWalk();

  Serial.println(F("free 3 pointers"));
  free(par[3]);
  par[3] = 0;
  free(par[5]);
  par[5] = 0;
  free(par[7]);
  par[7] = 0;

  myheap.freeListWalk();

  Serial.println(F("1 malloc"));
  par[3] = (int*) malloc(10);

  myheap.freeListWalk();
  myheap.dumpHeap(80);
  Serial.println();
  Serial.println(myheap);

  Serial.println(F("done"));
}

void loop()
{}
Ah, this is obviously some strange usage of the word 'safe' that I wasn't previously aware of. (D.Adams)

Whandall

The lib code
Code: [Select]
#ifndef AVRHEAP_H
#define AVRHEAP_H
//
//    FILE: Avrheap.h
//  AUTHOR: Rob dot Tillaart at gmail dot com
// VERSION: 0.1.02
// PURPOSE: heap library for Arduino (AVR)
// HISTORY: See avrheap.cpp
//
// Released to the public domain
//

#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"
#else
#include "WProgram.h"
#endif

#include "Printable.h"

#define AVRHEAP_LIB_VERSION "0.1.02"

class Avrheap : public Printable
{
public:
    Avrheap();

    bool     isFragmented();
    uint16_t freeListCount();
    uint16_t freeListSize();
    void     freeListWalk(bool withDump=true);
    uint16_t freeListLargest();

    uint16_t startAddress();
    void     dumpHeap(uint16_t count);
    size_t   heapWalk(Print& p, bool withDump=true) const;
    size_t   heapWalk(bool withDump=true);
    virtual size_t   printTo(Print& p) const;
private:
    bool     inFreeList(uint16_t addr);

};

size_t hNibble(Print& p, byte val);
size_t hByte(Print& p, byte val);
size_t hWord(Print& p, unsigned int val);
size_t dumpR(Print& p, byte* adr, int len);
size_t dumpAlloced(Print& p, byte *ptr, bool withDump=true);
size_t dumpAlloced(byte *ptr, bool withDump=true);

#endif

Code: [Select]
//
//    FILE: avrheap.cpp
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.02
// PURPOSE: library for avrheap Arduino
//     URL:
//
// REFERENCES
// http://forum.arduino.cc/index.php?topic=27536.15
//
// Released to the public domain
//
// 0.1.02 - added followHeap()
// 0.1.01 - refactor, added startAddress()
// 0.1.00 - initial version

#include "Avrheap.h"

struct __freelist
{
    size_t size;
    struct __freelist *next;
};

extern struct   __freelist *__flp;
extern uint16_t __heap_start;
extern uint16_t *__brkval;
extern char     *__malloc_heap_start;
extern char     *__malloc_heap_end;
extern size_t   __malloc_margin;
extern uint16_t __data_start;
extern uint16_t __data_end;
extern uint16_t __bss_start;
extern uint16_t __bss_end;

size_t hNibble(Print& p, byte val) {
  val &= 0xF;
  return(p.write(val+(val<10 ? '0' : 'A'-10)));
}

size_t hByte(Print& p, byte val) {
size_t len = hNibble(p, val>>4);
  len += hNibble(p, val);
  return len;
}

size_t hWord(Print& p, unsigned int val) {
size_t len = hByte(p, (byte)(val>>8));
  len += hByte(p, (byte)val);
  return len;
}

size_t dumpR(Print& p, byte* adr, int len) {
size_t glen = 0;
byte idx;
  if (!len) {
    len = 16;
  }
  for (; len > 0; len -= 16, adr += 16) {
    glen += hWord(p, (unsigned int)adr);
    glen += p.print(F(": "));
    for (idx = 0; idx < 16; idx++) {
      if (idx < len ) {
        glen += hByte(p, adr[idx]);
        glen += p.write(' ');
      } else {
        glen += p.print(F("   "));
      }
    }
    glen += p.write('\'');
    for (idx = 0; (idx < 16) && (idx < len); idx++) {
      glen += p.write(adr[idx] < 0x20 ? '.' : adr[idx]);
    }
    glen += p.write('\'');
    glen += p.println();
  }
  return glen;
}

size_t dumpAlloced(byte *ptr, bool withDump) {
   return dumpAlloced(Serial, ptr, withDump);
}

size_t dumpAlloced(Print& p, byte *ptr, bool withDump) {
size_t len = hWord(p, (uint16_t)ptr);
  if (!ptr) {
    len += p.println(F(": NULL"));
  } else {
    size_t size = *(size_t*)(ptr-sizeof(size_t));
    if (size < __malloc_margin) {
      len += p.print(F(": size "));
      len += p.println(size);
    } else {
      len += p.print(F(": invalid size "));
      len += p.println(size);
      size = 16;
    }
    if (withDump) {
      len += dumpR(p, ptr, size);
      len += p.println();
    }
  }
  return len;
}

Avrheap::Avrheap()
{
};

bool Avrheap::isFragmented()
{
    return freeListCount() > 0;
};

uint16_t Avrheap::freeListCount()
{
    uint16_t count = 0;
    for (struct __freelist*  p = __flp; p; p = p->next) count++;
    return count;
}

uint16_t Avrheap::freeListSize()
{
    uint16_t total = 0;
    for (struct __freelist*  p = __flp; p; p = p->next)
    {
        total += 2;     // malloc size
        total += (uint16_t) p->size;
    }
    return total;
}

void Avrheap::freeListWalk(bool withDump)
{
int elements = freeListCount();
    Serial.print(F("\nFreeList: "));
    Serial.print(isFragmented() ? F("fragmented") : F("clean"));
    Serial.print(F(", count "));
    Serial.print(elements);
    Serial.print(F(", largest "));
    Serial.print(freeListLargest());
    Serial.print(F(", total size "));
    Serial.println(freeListSize());
    Serial.println();
    if (elements) {
      for (struct __freelist* p = __flp; p; p = p->next)
      {
          hWord(Serial, (uint16_t)p);
          Serial.print(F(": size "));
          Serial.print((uint16_t)p->size);
          Serial.print(F(" next "));
          hWord(Serial, (uint16_t)p->next);
          Serial.println();
          if (withDump) {
            dumpR(Serial, ((byte*)p)+2, p->size);
            Serial.println();
          }
      }
  }
}

uint16_t Avrheap::startAddress()
{
    return (uint16_t) &__heap_start;
}

// PRINTTO?
void Avrheap::dumpHeap(uint16_t count)
{
    hWord(Serial, (uint16_t)RAMEND);
    Serial.println(F(" RAMEND"));
    hWord(Serial, (uint16_t)SP);
    Serial.println(F(" SP"));
    hWord(Serial, (uint16_t)__brkval);
    Serial.println(F(" __brkval"));
    hWord(Serial, (uint16_t)__malloc_heap_end);
    Serial.println(F(" __malloc_heap_end"));
    hWord(Serial, (uint16_t)__malloc_heap_start);
    Serial.println(F(" __malloc_heap_start"));
    hWord(Serial, (uint16_t)&__heap_start);
    Serial.println(F(" __heap_start"));
    hWord(Serial, (uint16_t)&__bss_end);
    Serial.println(F(" __bss_end"));
    hWord(Serial, (uint16_t)&__bss_start);
    Serial.println(F(" __bss_start"));
    hWord(Serial, (uint16_t)&__data_end);
    Serial.println(F(" __data_end"));
    hWord(Serial, (uint16_t)&__data_start);
    Serial.println(F(" __data_start"));
    hWord(Serial, (uint16_t)__malloc_margin);
    Serial.println(F(" __malloc_margin"));
    Serial.println();
    Serial.println(F("start of heap"));
    Serial.println();
    dumpR(Serial, (byte*)startAddress(), count);
}
size_t Avrheap::heapWalk(bool withDump) {
    return heapWalk(Serial, withDump);
}

// EXPERIMENTAL
size_t Avrheap::heapWalk(Print& pr, bool withDump) const
{
    byte* p = (byte*) &__heap_start;
    struct __freelist* fp = __flp;

    size_t len = pr.println(F("Heap\n"));
    while ((int)p < (int)__brkval)
    {
        len += hWord(pr, (uint16_t)p); // p+2 ?
        len += pr.write(' ');
        len += pr.print(*p, DEC);
        if ( (fp != NULL) && ((uint16_t)p == (uint16_t)fp))
        {
            len += pr.print(F(" (free)"));
            fp = fp->next;
        }
        len += pr.println();
        if (withDump) {
          len += dumpR(pr, p, *p+2);
          len += pr.println();
        }
        p += (byte) *p + 2;
    }
    return len;
}

bool Avrheap::inFreeList(uint16_t addr)
{
    for (struct __freelist* p = __flp; p; p = p->next)
    {
        if (addr == (uint16_t)p) return true;
    }
    return false;
}

uint16_t Avrheap::freeListLargest()
{
    uint16_t largest = 0;
    for (struct __freelist*  p = __flp; p; p = p->next)
    {
        largest = max(largest, (uint16_t) p->size);
    }
    return largest;
}

size_t Avrheap::printTo(Print& p) const {
  size_t len = heapWalk(p, true);
  return len;
}

// --- END OF FILE ---
Ah, this is obviously some strange usage of the word 'safe' that I wasn't previously aware of. (D.Adams)

Whandall

The output
Code: [Select]
Start AVRHeap.ino
LibVersion 0.1.02

HEAP ADDR: 02F2

allocate 10 chunks

02F4: size 2
02F8: size 6
0300: size 10
030C: size 6
0314: size 10
0320: size 2
0324: size 10
0330: size 2
0334: size 2
0338: size 14

21FF RAMEND
21F2 SP
0346 __brkval
0000 __malloc_heap_end
02F2 __malloc_heap_start
02F2 __heap_start
02F2 __bss_end
0232 __bss_start
0232 __data_end
0200 __data_start
0080 __malloc_margin

start of heap

02F2: 02 00 00 00 06 00 00 00 03 00 00 04 0A 00 00 00 '................'
0302: 00 3C 00 48 00 00 22 00 06 00 00 00 00 00 00 46 '.<.H.."........F'
0312: 0A 00 00 00 00 00 16 00 00 00 28 00 02 00 00 00 '..........(.....'
0322: 0A 00 00 00 03 18 00 00 00 0E 10 00 02 00 00 00 '................'
0332: 02 00 00 00 0E 00 00 00 00 00 00 89 0E 00 92 03 '...........‰..'.'

Heap

02F2 2
02F2: 02 00 00 00                                     '....'

02F6 6
02F6: 06 00 00 00 03 00 00 04                         '........'

02FE 10
02FE: 0A 00 00 00 00 3C 00 48 00 00 22 00             '.....<.H..".'

030A 6
030A: 06 00 00 00 00 00 00 46                         '.......F'

0312 10
0312: 0A 00 00 00 00 00 16 00 00 00 28 00             '..........(.'

031E 2
031E: 02 00 00 00                                     '....'

0322 10
0322: 0A 00 00 00 03 18 00 00 00 0E 10 00             '............'

032E 2
032E: 02 00 00 00                                     '....'

0332 2
0332: 02 00 00 00                                     '....'

0336 14
0336: 0E 00 00 00 00 00 00 89 0E 00 92 03 00 00 00 4C '.......‰..'....L'



FreeList: clean, count 0, largest 0, total size 0

free 3 pointers

FreeList: fragmented, count 3, largest 6, total size 16

030A: size 6 next 031E
030C: 1E 03 00 00 00 46                               '.....F'

031E: size 2 next 032E
0320: 2E 03                                           '..'

032E: size 2 next 0000
0330: 00 00                                           '..'

1 malloc

FreeList: fragmented, count 3, largest 6, total size 16

030A: size 6 next 031E
030C: 1E 03 00 00 00 46                               '.....F'

031E: size 2 next 032E
0320: 2E 03                                           '..'

032E: size 2 next 0000
0330: 00 00                                           '..'

21FF RAMEND
21F2 SP
0352 __brkval
0000 __malloc_heap_end
02F2 __malloc_heap_start
02F2 __heap_start
02F2 __bss_end
0232 __bss_start
0232 __data_end
0200 __data_start
0080 __malloc_margin

start of heap

02F2: 02 00 00 00 06 00 00 00 03 00 00 04 0A 00 00 00 '................'
0302: 00 3C 00 48 00 00 22 00 06 00 1E 03 00 00 00 46 '.<.H.."........F'
0312: 0A 00 00 00 00 00 16 00 00 00 28 00 02 00 2E 03 '..........(.....'
0322: 0A 00 00 00 03 18 00 00 00 0E 10 00 02 00 00 00 '................'
0332: 02 00 00 00 0E 00 00 00 00 00 00 89 0E 00 92 03 '...........‰..'.'

Heap

02F2 2
02F2: 02 00 00 00                                     '....'

02F6 6
02F6: 06 00 00 00 03 00 00 04                         '........'

02FE 10
02FE: 0A 00 00 00 00 3C 00 48 00 00 22 00             '.....<.H..".'

030A 6 (free)
030A: 06 00 1E 03 00 00 00 46                         '.......F'

0312 10
0312: 0A 00 00 00 00 00 16 00 00 00 28 00             '..........(.'

031E 2 (free)
031E: 02 00 2E 03                                     '....'

0322 10
0322: 0A 00 00 00 03 18 00 00 00 0E 10 00             '............'

032E 2 (free)
032E: 02 00 00 00                                     '....'

0332 2
0332: 02 00 00 00                                     '....'

0336 14
0336: 0E 00 00 00 00 00 00 89 0E 00 92 03 00 00 00 4C '.......‰..'....L'

0346 10
0346: 0A 00 00 00 00 28 00 00 08 00 00 00             '.....(......'


done
Ah, this is obviously some strange usage of the word 'safe' that I wasn't previously aware of. (D.Adams)

robtillaart

I still have to publish this library on my Github repo. Will do that this evening.

May I use your demo sketch as demo?
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Whandall

Ah, this is obviously some strange usage of the word 'safe' that I wasn't previously aware of. (D.Adams)

robtillaart

#7
Dec 10, 2015, 08:22 pm Last Edit: Dec 10, 2015, 08:26 pm by robtillaart
Posted version 0.1.00 - 0.104 on Github (older versions for history). The latest is now 0.1.04

- https://github.com/RobTillaart/Arduino/tree/master/libraries/AvrHeap -


Many Thanks to Whandall for his contributions to improve the interface and the output style. Most of your changes made it into the class - karma to you!


As always remarks and comments are welcome
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Thomas499

#8
Dec 18, 2015, 08:23 pm Last Edit: Dec 18, 2015, 10:16 pm by Thomas499
I'm trying to do something very similar I'm new to programing though, and I'm having a hard time figuring out certain things in your library.


What I would like it to do is when I call
Quote
myheap.freeListWalk();
All I want it to print on the serial monitor is something like this (used made up numbers here)
Quote
Largest RamSpace is 154, fragmented 4%, count 47, total size 777, largest 159
basically I don't want to see the all the extra stuff, unless I use the functions to make the extra stuff show up. The purpose is to quickly identify how memory fragmentation is occuring in my particular sketch.

Here is the code I wrote when I tried modifying your sketch on my own.

Code: [Select]
void Avrheap::freeListWalk(bool withDump)
{   unsigned int largestFrag=freeListLargest();
     __heap_start,*__brkval;
    int v;
    unsigned int currentUfRam = (((int)&v - (__brkval == 0 ? (int)&__heap_start : (int) __brkval))-freeListSize()/*+InsertAmountOfFreeRamUsedToCallEverythingInClassUpToThisPointHereLater*/); // this is basicly (freeRam() - freeListSize()/*+InsertAmountOfFreeRamUsedToCallEverythingInClassUpToThisPointHereLater*/)
    int elements = freeListCount();
    Serial.print(F("\nLargest RamSpace is "));
    if (currentUfRam>largestFrag) // if largest whole space available is fragmented, then we'll print that that rather than the largest unfragmented space availble.
      Serial.print(currentUfRam);
    else
      Serial.print(largestFrag);
    if (isFragmented())
    {
      Serial.print(F(", fragmented " ));
      Serial.print(((int)&v - (__brkval == 0 ? (int)&__heap_start : (int) __brkval))/currentUfRam); // freeRam()/(freeRam()-freeListSize()
      Serial.print(F("%"));
    }
    else
      Serial.print(F(", clean"));
    Serial.print(F(", count "));
    Serial.print(elements);
    Serial.print(F(", total size "));
    Serial.print(freeListSize());
    Serial.print(F(", largest "));
    Serial.println(largestFrag);
The problem is, when i load this code as the main sketch
Quote
String RamFrager="";
   void setup(){
    Serial.begin(115200);
  }
 
  void loop(){
    RamFrager+='c'; // purposely frag the memory so we can see it
  //myheap.dumpHeap(80);
  Serial.println();
  Serial.println(myheap);
  myheap.freeListWalk();
  }
it currently prints
Code: [Select]
0266 2
0266: 02 00 63 00                                     '..c.'



Largest RamSpace is 1668, clean, count 0, total size 0, largest 0

Heap

0266 3
0266: 03 00 63 63 00                                  '..cc.'



Largest RamSpace is 1667, clean, count 0, total size 0, largest 0

Heap

0266 4
0266: 04 00 63 63 63 00                               '..ccc.'



Largest RamSpace is 1666, clean, count 0, total size 0, largest 0

Heap

0266 5
0266: 05 00 63 63 63 63 00                            '..cccc.'



Largest RamSpace is 1665, clean, count 0, total size 0, largest 0

Heap
which I think is close, but I can't figure out why it keeps printing
Quote
count 0, total size 0, largest 0
instead of the correct information. Can you help me get this to work please?

Go Up
 


Please enter a valid email to subscribe

Confirm your email address

We need to confirm your email address.
To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy