Arduino struct with pointer to itself leaks memory

Question

I have an arduino program where I want to store data in a dynamic list. For this I use the following struct:

struct Project {
  boolean         status;
  String          name;
  struct Project* nextProject;
};

Now I generate a dynamic amount of Project objects, depending on extern data. I only have the first Project object as variable, the rest i can get through the nextProject pointer.

The generation of the Project objects is done in my loop again every minute. The problem is that from time to time I loos memory till it's empty.
This is how my main loop looks like:

void loop() {
  webServer(server);
  webClient();

  if (parseTimer(60)) {
    sendRequest();
  }
}

(parseTimer is a non blocking delay function that returns true every 60 seconds; sendRequest generates the Project objects)

My method to measure the memory:

uint8_t* stackptr;
uint8_t* heapptr;

long getFreeMemory() {
  stackptr = (uint8_t *) malloc(4);
  heapptr  = stackptr;
  free(stackptr);
  stackptr = (uint8_t *) (SP);

  return long(stackptr) - long(heapptr);
}

This is the ammount of memory each loop:

1:  4716 *
2:  4716 *
3:  4716 *
4:  4671
5:  4687
6:  4587 *
7:  4736
8:  4587 *
9:  4559
10: 4577
11: 4515
12: 4527
13: 4587 *
14: 4479
15: 4497
16: 4435
17: 4447
18: 4587 *
19: 4399
20: 4417
21: 4355
22: 4367
23: 4587 *
24: 4319

Memory is getting less but after the first few loops, every 5th loop I have 4587 Bytes of free memory. After ~280 loops the program is out of memory, but till there every 5th loop has exactly 4587 Bytes free memory. Can anyone explain me what could be the cause for this strange behavior and how can I create a better dynamic list that doesn't leaks memory.

UPDATE

In each loop the Project objects are generated, used and deleted. It does sth. like this:

void sendRequest() {
  // at first it gets some remote data from a server the result is:
  String  names[]  = {"Project 1", "Project 2", "Project 3"};
  boolean states[] = {true, false, true};

  for(int i = 0; i <= projectCount; i++) {
    addProject(names[i], states[i]);
  }
}

// all variables that are not declarated here are declarated in the
// header file of the class
void addProject(String name, boolean state) {
  if (!startProject) {
    startProject = true;

    firstProject.status      = state;
    firstProject.name        = name;
    firstProject.nextProject = NULL;

    ptrToLastProject = &firstProject;
  } else {
    ptrToLastProject->nextProject = new Project();

    ptrToLastProject->nextProject->status      = tempProjectStatus;
    ptrToLastProject->nextProject->name        = tempData;
    ptrToLastProject->nextProject->nextProject = NULL;

    ptrToLastProject = ptrToLastProject->nextProject;
  }
}

void RssParser::resetParser() { 
  delete ptrToLastProject;
  [...]
}

Answer 1

After lots of research and writing unit tests for nearly every function of the project I was able to find the mistake.

In my resetParser() function i did only a delete ptrToLastProject. But there was an other Pointer to this object so the memory was not released. Adding this to the resetParser() function fixed the leak.

delete firstProject.nextProject;

The reason for this is because the firstProject is on the stack with an pointer to the other projects in the list on the heap. When I delete this pointer all other objects in the list are deleted too by their destructors.

Answer 2

First of all, you're not leaking memory because on every 5th iteration your memory is back to 4587 bytes

There is however, an interesting pattern occurring here. You'll notice that each set of calls to getFreeMemory that occurs before you have 4587 bytes is always 80 bytes less than the last set.

I'm going to guesstimate that there is more and more data being received on each sendRequest, and in return, you're attempting to allocate more memory each run through the loop. It's all well and good that you're releasing it somewhere, but at some point you're trying to allocate too much!

One possibility is that you're appending the request data, rather than overwriting it, and subsequently the projectCount is constantly increased.

As a side-note, be careful of this:

for(int i = 0; i <= projectCount; i++) {
    addProject(names[i], states[i]);
}

Looping through arrays requires a 0 based index. When you check the condition i <= projectCount you may be overrunning your buffer. If there are 3 elements in names, and your projectCount is 3, what happens when i = 3 and you access names[i]?