Memory Leak

[death_oclock]

My program is getting hung up somewhere in the function evolveRealization and while it is stuck its memory usage is increasing by around 1MB per second! While it is building up generations, it was designed to only use the most recent one, and the old ones should be freed. So where is this memory leak coming from?

#include "stdafx.h"
#include "types.h"
#include "pitch.h"
#include "chord.h"
#include "phrase.h"
#include "realization.h"

ACTUAL_CHORD randomActualChord(CHORD_SYMBOL *chordSymbol)
{
	ACTUAL_CHORD actualChord;
	PITCH *pitches;

	pitches = chordSymbolPitches(chordSymbol);

	actualChord.soprano = pitches[rand() % ((chordSymbol->quality >= major7) ? 4 : 3)];
	actualChord.alto = pitches[rand() % ((chordSymbol->quality >= major7) ? 4 : 3)];
	actualChord.tenor = pitches[rand() % ((chordSymbol->quality >= major7) ? 4 : 3)];
	actualChord.bass = pitches[rand() % ((chordSymbol->quality >= major7) ? 4 : 3)];

	return actualChord;
}

//return pointer must be freed
ACTUAL_CHORD *randomRealization(int length, CHORD_SYMBOL *sequence)
{
	ACTUAL_CHORD *realization;
	int i;

	realization = malloc(sizeof(ACTUAL_CHORD) * length);
	if(!realization)
		return NULL;

	for(i = 0; i < length; i++)
	{
		realization[i] = randomActualChord(&sequence[i]);
	}

	return realization;
}

int calcFitnessRealization(int length, REALIZATION realization, SEQUENCE sequence)
{
	PITCH *pitches;
	int fitness = 0;
	int count;
	int diff;
	bool bad;
	int i;

	for(i = 0; i < length; i++)
	{
		bad = false;

		pitches = chordSymbolPitches(&sequence[i]);
		if(!pitches)
			return -1;

		if(!pitchEquals(realization[i].bass, pitches[sequence[i].inversion]))
			bad = true; //wrong inversion
		
		else if(!pitchEquals(realization[i].soprano, pitches[0]) &&
				!pitchEquals(realization[i].alto, pitches[0]) &&
				!pitchEquals(realization[i].tenor, pitches[0]) &&
				!pitchEquals(realization[i].bass, pitches[0]))
			bad = true; //missing root of the chord

		else if(!pitchEquals(realization[i].soprano, pitches[1]) &&
				!pitchEquals(realization[i].alto, pitches[1]) &&
				!pitchEquals(realization[i].tenor, pitches[1]) &&
				!pitchEquals(realization[i].bass, pitches[1]))
			bad = true; //missing third of the chord

		else if(!pitchEquals(realization[i].soprano, pitches[2]) &&
				!pitchEquals(realization[i].alto, pitches[2]) &&
				!pitchEquals(realization[i].tenor, pitches[2]) &&
				!pitchEquals(realization[i].bass, pitches[2]))
			bad = true; //missing fifth of the chord

		else if(sequence[i].quality >= major7 &&
				!pitchEquals(realization[i].soprano, pitches[3]) &&
				!pitchEquals(realization[i].alto, pitches[3]) &&
				!pitchEquals(realization[i].tenor, pitches[3]) &&
				!pitchEquals(realization[i].bass, pitches[3]))
			bad = true; //missing seventh of the chord

		else
		{
			if(sequence[i].inversion == 0)
			{
				count = 0;
				if(pitchEquals(realization[i].soprano, pitches[0]))
					count++;
				if(pitchEquals(realization[i].alto, pitches[0]))
					count++;
				if(pitchEquals(realization[i].tenor, pitches[0]))
					count++;
				if(pitchEquals(realization[i].bass, pitches[0]))
					count++;

				if(count < 2)
					bad = true; //root not doubled
			}

			else if(sequence[i].inversion == 1)
			{
				count = 0;
				if(pitchEquals(realization[i].soprano, pitches[0]))
					count++;
				if(pitchEquals(realization[i].alto, pitches[0]))
					count++;
				if(pitchEquals(realization[i].tenor, pitches[0]))
					count++;
				if(pitchEquals(realization[i].bass, pitches[0]))
					count++;

				if(count < 2)
				{
					count = 0;
					if(pitchEquals(realization[i].soprano, realization[i].soprano))
						count++;
					if(pitchEquals(realization[i].alto, realization[i].soprano))
						count++;
					if(pitchEquals(realization[i].tenor, realization[i].soprano))
						count++;
					if(pitchEquals(realization[i].bass, realization[i].soprano))
						count++;

					if(count < 2)
						bad = true; //root or soprano not doubled
				}
			}

			else if(sequence[i].inversion == 2)
			{
				count = 0;
				if(pitchEquals(realization[i].soprano, pitches[2]))
					count++;
				if(pitchEquals(realization[i].alto, pitches[2]))
					count++;
				if(pitchEquals(realization[i].tenor, pitches[2]))
					count++;
				if(pitchEquals(realization[i].bass, pitches[2]))
					count++;

				if(count < 2)
					bad = true; //fifth not doubled
			}
		}

		free(pitches);

		if(!bad)
			++fitness;

		if(i > 0)
		{
			bad = false;

			diff = absInterval(realization[i - 1].soprano, realization[i - 1].alto);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].soprano, realization[i].alto) == diff &&
					!pitchEquals(realization[i - 1].soprano, realization[i].alto))
					bad = true; //parallel octave/fifth between soprano-alto

			diff = absInterval(realization[i - 1].alto, realization[i - 1].tenor);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].alto, realization[i].tenor) == diff &&
					!pitchEquals(realization[i - 1].alto, realization[i].tenor))
					bad = true; //parallel octave/fifth between alto-tenor

			diff = absInterval(realization[i - 1].tenor, realization[i - 1].bass);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].tenor, realization[i].bass) == diff &&
					!pitchEquals(realization[i - 1].tenor, realization[i].bass))
					bad = true; //parallel octave/fifth between tenor-bass

			diff = absInterval(realization[i - 1].soprano, realization[i - 1].tenor);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].soprano, realization[i].tenor) == diff &&
					!pitchEquals(realization[i - 1].soprano, realization[i].tenor))
					bad = true; //parallel octave/fifth between soprano-tenor

			diff = absInterval(realization[i - 1].alto, realization[i - 1].bass);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].alto, realization[i].bass) == diff &&
					!pitchEquals(realization[i - 1].alto, realization[i].bass))
					bad = true; //parallel octave/fifth between alto-bass

			diff = absInterval(realization[i - 1].soprano, realization[i - 1].bass);
			if(diff == 0 || diff == 7)
				if(absInterval(realization[i].soprano, realization[i].bass) == diff &&
					!pitchEquals(realization[i - 1].soprano, realization[i].bass))
					bad = true; //parallel octave/fifth between soprano-bass
		}
	}

	return fitness;
}

ACTUAL_CHORD **getEliteRealizations(int length, REALIZATION *generation, SEQUENCE sequence, int generationSize, int eliteSize)
{
	ACTUAL_CHORD **elite;
	int *fitnesses;
	int *sequences;
	bool swapped;
	int temp;
	int i;

	elite = malloc(sizeof(PHRASE) * eliteSize);
	if(!elite)
		return NULL;

	fitnesses = malloc(sizeof(int) * generationSize);
	if(!fitnesses)
		return NULL;
	
	sequences = malloc(sizeof(int) * generationSize);
	if(!sequences)
		return NULL;
	
	for(i = 0; i < generationSize; i++)
	{
		fitnesses[i] = calcFitnessRealization(length, generation[i], sequence);
		if(fitnesses[i] == -1)
			return NULL;

		sequences[i] = i;
	}

	//bubble sort
	do
	{
		swapped = false;
		for(i = 1; i < generationSize; i++)
		{
			if(fitnesses[i] > fitnesses[i - 1])
			{
				temp = fitnesses[i];
				fitnesses[i] = fitnesses[i - 1];
				fitnesses[i - 1] = temp;
				temp = sequences[i];
				sequences[i] = sequences[i - 1];
				sequences[i - 1] = temp;

				swapped = true;
			}
		}
	} while(swapped);

	for(i = 0; i < eliteSize; i++)
	{
		if(!copyRealization(length, &elite[i], &generation[sequences[i]]))
			return NULL;
	}

	free(fitnesses);
	free(sequences);

	return elite;
}

ACTUAL_CHORD *spawnRealization(int length, SEQUENCE sequence, ACTUAL_CHORD *parent1, ACTUAL_CHORD *parent2, double mutationProb)
{
	REALIZATION realization;
	int i;

	realization = malloc(sizeof(ACTUAL_CHORD) * length);
	if(!realization)
		return NULL;

	for(i = 0; i < length; i++)
	{
		if(rand() / (double)RAND_MAX < mutationProb)
		{
			realization[i] = randomActualChord(&sequence[i]);
		}
		else
		{
			/*realization[i].soprano = (rand() % 2) ? parent1[i].soprano : parent2[i].soprano;
			realization[i].alto = (rand() % 2) ? parent1[i].alto : parent2[i].alto;
			realization[i].tenor = (rand() % 2) ? parent1[i].tenor : parent2[i].tenor;
			realization[i].bass = (rand() % 2) ? parent1[i].bass : parent2[i].bass;*/
			realization[i] = (rand() % 2) ? parent1[i] : parent2[i];
		}
	}

	return realization;
}

ACTUAL_CHORD *evolveRealization(int length, SEQUENCE sequence, int generationSize, int eliteSize, double mutationProb)
{
	REALIZATION *generation;
	REALIZATION *elite;
	ACTUAL_CHORD *best;
	int max = 0;
	int parent1, parent2;
	int fitness;
	int i;

	//init 0 generation
	generation = malloc(generationSize * sizeof(ACTUAL_CHORD *));
	if(!generation)
		return NULL;

	for(i = 0; i < generationSize; i++)
	{
		generation[i] = randomRealization(length, sequence);
		if(!generation[i])
			return NULL;
	}

	while(max < length)
	{
		elite = getEliteRealizations(length, generation, sequence, generationSize, eliteSize);
		if(!elite)
			return NULL;

		for(i = 0; i < generationSize; i++)
		{
			free(generation[i]);

			parent1 = rand() % eliteSize;
			parent2 = rand() % eliteSize;
			generation[i] = spawnRealization(length, sequence, elite[parent1], elite[parent2], mutationProb);
			if(!generation[i])
				return NULL;

			fitness = calcFitnessRealization(length, generation[i], sequence);
			if(fitness == -1)
				return NULL;

			if(fitness > max)
			{
				max = fitness;
				printf("%d%%\n", max * 100 / length);
				//best = generation[i];
				if(!copyRealization(length, &best, &generation[i]))
					return NULL;
			}
		}

		for(i = 0; i < eliteSize; i++)
		{
			free(elite[i]); //get rid of old sequence
		}
		free(elite);
	}

	for(i = 0; i < generationSize; i++)
	{
		free(generation[i]);
	}
	free(generation);

	return best;
}

The other files really aren't relevant; the only external function that allocated memory is chordPitches and the memory from that is clearly freed. I have looked the entire thing over many times and I am still clueless. Is there something I am missing?

[death_oclock]

Nevermind, I caught it. I didn't free pitches inside randomActualChord() .

[Ancient Dragon]

Learn to use your compiler's debugger and step through the code one line at a time so that you can see what it is doing.

line 292: you are attempting to treat a 2d array of REALIZATION structures as if it were a 1d array. It needs two stars, not one =REALIZATION** generation = 0; . The rest of the code in that function should then work ok.

After allocating the array you need to set all elements to NULL so that they can be correctly free()ed, expecially if the function returns prematurely (see below). memset(generation, 0, generationSize * sizeof(ACTUAL_CHORD *)); lines 309, 330 and 338: memory leak here. You need to free() variable generation and each of the pointers that were returned from spawnRealization().

[death_oclock]

Sorry, I should have posted the types I defined; REALIZATION is a pointer in itself, so in that aspect the program works. What is the benefit to clearing a block of memory before freeing it though?

[Ancient Dragon]

don't clear it before freeing, clear it immediately after using it. The purpose is so that unused elements can be easily detected. For example line 309: before the return statement you have to free up all the memory that was allocated up to that point. If you don't then it will cause memory leak.