Another question regarding memory

[kloony]

Hi Guys, it's me again! I have been posing memory-related problems for the past few days because I don't seem to understand what is the problem with my code. I kind of figured it's due to memory issues....so here's my question.

Suppose I have a (first in first out) queue that contain "Items", which is a structure previously defined:

void QUEUEinit(int); /* initiates queue */

static Item *q;
static int N, head, tail;

void QUEUEinit(int maxN)
{ q=malloc((maxN+1)*sizeof(Item));
   if(q){
   N=maxN+1; head = N; tail = 0;}else{printf("memory allocation error.\n");}
  }

So every time in my main program, whenever I call

QUEUEinit(50);

the system sets aside memory, say of amount X, for my queue. Suppose (just for testing purposes) if I do this:

for(i=0; i<1000; i++)
QUEUEinit(50);

does this mean that a total of 1000X amount of memory will be used? If this is the case, very soon (by increasing i to 2000, or more) my system is going to run out of memory and I am going to get a "memory allocation error" message.

What if, instead I had

for(i=0; i<1000; i++)
{QUEUEinit(50); free(q); q=NULL;}

Does this mean that every time QUEUEinit() is called, the memory set aside for it will be freed before the next i, so I will never run out of memory?

Sorry if this is a little confusing, hope it is understandable and any help will be appreciated.

[Stack Overflow]

Hello,

for(i=0; i<1000; i++) QUEUEinit(50);

If I am correct in my thinking, you will have lost allocated memory in your program. Your pointer,q, is a variable. Allocating memory to it 1000 times will cause a problem.

According to the C89 Sec. 4.10.3: The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object in the space allocated (until the space is explicitly freed or reallocated).

Each time you call malloc, you request a block of freed space, if successful. You will have 1000 blocks of memory, as each time malloc is called, while q may point to only one, and the last, block of memory allocated.

According to the C89 Sec. 4.10.3: If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation-defined; the value returned shall be either a null pointer or a unique pointer. The value of a pointer that refers to freed space is indeterminate.

Onto your next question.
What if, instead I had

Code:

for(i=0; i<1000; i++) {QUEUEinit(50); free(q); q=NULL;}

Does this mean that every time QUEUEinit() is called, the memory set aside for it will be freed before the next i, so I will never run out of memory?
I believe so. Each time QUEUEinit() is called, you request a block of memory. As in this loop, you free the memory block given toq each time, ensuring the memory allocated is de-allocated per loop increment:

According to the C89 Sec. 4.10.3: The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc , malloc , or realloc function, or if the space has been deallocated by a call to free or realloc , the behavior is undefined.

- Stack Overflow

[Tight_Coder_Ex]

Yes you will eventually run out of memory by continuously allocating with malloc and never freeing.

In the second case, theroetically you shouldn't run out of memory by freeing each time, but Linux and Unix like XP handle memory a lot better than 95 or 98 do. I have no experience with OSX, but assume it's similar to Linux. In 95 and 98 they just keep using memory until nothing is left and only relinquish it when application is closed. That is why you can run out of resourses with these two operating systems and have few programs running.

Long story short. It's good practice to determine how heap resourses are handled on the platform you are using and pay attention to those API's that will relinquish memory to operating system and/or coalesce fragmented segments while program is running.

If you have the oportunity to look at Linux man pages and sources that will give you a real good understanding how modern operating system handles memory.

[kloony]

Thanks, Stack Overflow and Tight_Coder_Ex.

Stack Overflow - I understand what you mean about the variable q can only point to one thing at a time and the problem that might arise. So if the free(q) and q=NULL is included in the loop, this will avoid the problem right?

I have been trying out these memory tests on both my laptop which runs on Windows 2000, using a Borland 5.5 compiler and also using UNIX in my office which has a gcc compiler. Both systems runs out of memory (as predicted) if no free() is called, but at different stages of the loop. That is understandable as both systems have different memory sizes. However, I was told that it is much safer to use UNIX as Windows sometimes allows you to use memory that is not supposed to be used, which could result in a problem later. Is this correct?

Ok, something else on free(). Suppose I am working with graphs (nodes and vertices) using adjacency matrices. Each graph G is defined as a structure containing 2 integers (V and E, the number of vertices and edges in the graph) and its adjacency matrix:

typedef struct graph *Graph;
Graph GRAPHinit(int);
struct graph{int V; int E; int **adj;}

int **MATRIXint(int r, int c, int val)
{ int i,j;
  int **t=malloc(r*sizeof(int *));
   if(t){ for(i=0; i<r; i++) 
              t[i]=malloc(c*sizeof(int)); if{t[i]}
                                                     {for(i=0;i<r; i++)
                                                       for(j=0;j<c;j++) t[i][j]=val;}
                                                    else{printf("mem allocation error.\n"); return 0;}
          }else{printf("mem allocation error.\n"); return 0;}
    return t;
}

Graph GRAPHinit(int V)
{ Graph G = malloc(sizeof*G);
   if(G){G->V=V; G->E=0; G->adj=MATRIXint(V,V,0);}
                  else{printf("mem allocation error.\n"); return 0;}
 return G;
}

So everytime I call G=GRAPHinit(50), I have a graph with 50 vertices, no edges, and a 50x50 adjacency matrix. Now supposed I am done with G and I want to free the memory used for G, will

free(G); G=NULL;

suffice? Or do I need to free() the adjacency matrix row by row, set to NULL and then free(G) and set G=NULL?

apologies for such a long post again :)

[Stack Overflow]

Hello,

So if the free(q) and q=NULL is included in the loop, this will avoid the problem right?

Indeed it should. Each call to malloc will be subsequently freed during each loop iteration.However, I was told that it is much safer to use UNIX as Windows sometimes allows you to use memory that is not supposed to be used, which could result in a problem later. Is this correct?I'm not entirely sure. I don't have any hard evidence or facts at the moment, though I have run into cases were Windows can grab a hold of non-valid memory, thus causing a segmentation fault. While sometimes, its a programming error.

As a side note, a segmentation fault is an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.Now supposed I am done with G and I want to free the memory used for G, will

free(G); G=NULL;

suffice? Or do I need to free() the adjacency matrix row by row, set to NULL and then free(G) and set G=NULL?I'm afraid not. Freeing the memory allocated to G will free, but not G->adj. As G->adj points to MATRIXint(). You will have to de-allocate that memory first, and then de-allocated G. Like as the following:

/* free rows made by MATRIXint() */
/* where V represents the rows */
for (i = V-1; i >= 0; i--) {
	if (G->adj[i] != NULL) {
		free(G->adj[i]);
		G->adj[i] = NULL;
	}
}

/* free 2-dimensional pointer */
if (G->adj != NULL) {
	free(G->adj)
	G->adj = NULL;
}

/* free Graph */
if (G != NULL) {
	free(G);
	G = NULL;
}

The reason my loop starts atV-1 is because you allocated from 0 to which is one less than r. While <= would represent r and not r-1.

If you have further questions, please feel free to ask.


- Stack Overflow

[kloony]

Hmm...interesting. Maybe this will unravel the mystery behind my recent encounters with "segementation faults" when I try to run my program in UNIX. Although I am aware of the various reasons for "segementation faults" you mentioned, I figured that it probably was due to the system running out of memory to allocate, as I have been using free(G) all along, thinking that this would free up all memory used by G, including the adjacency matrix.

So theoretically speaking again, just like the queue example, if I initiate a graph G in a loop (say, 1000 times), without freeing the memory (properly), I will run out of memory very quickly. However, if I free the memory like you did before the loop is exited, my program should never crash (although "never say never")?

[Narue]

>I figured that it probably was due to the system running out of memory to allocate
No, not directly at least. You can get a segmentation fault because malloc failed and returned a null pointer, but the system running out of memory (while incredibly unlikely) wouldn't result in a seg fault. A seg fault is caused by accessing memory outside of your address space. You're given a chunk of memory from address m to address n. If you try to access address p, you'll get a seg fault because it's not within m to n.

>However, if I free the memory like you did before the loop is exited, my program should never crash
No. Memory leaks will only slow your system down and possibly grind it to a halt. If you program crashes, it's because you did something wrong. Though releasing memory you allocate is always a good idea.

[Stack Overflow]

Hello,

In addition, you may find this short tutorial on Segmentation Faults handy: Locating a Segmentation Fault

Or if you have access to gdb or Valgrind, the following articles may be of use:
Debugging Segmentation Faults
Finding Memory Leaks and Invalid Memory Use Using Valgrind

Also, I put together a C example of healthy memory allocation techniques:

#include <stdio.h>
#include <stdlib.h>

#define DATA 2

struct List {
	char **data;
};

struct Page {
	struct List *list;
};

int main() {
	/* local variables */
	int i, j, k;

	/* allocate memory; page */
	struct Page *page_1 = malloc(sizeof *page_1);
	if (page_1 == NULL) {
		fprintf(stderr, "page_1 allocation failed\n");
		return 0;
	}
	printf("page_1 allocated\n");

	/* allocate memory; list */
	page_1->list = malloc(sizeof *page_1->list);
	/* if allocation failed */
	if (page_1->list == NULL) {
		fprintf(stderr, "page_1->list allocation failed\nfree page_1\n");
		/* free memory; page */
		free(page_1);
		page_1 = NULL;
		return 0;
	}
	printf("page_1->list allocated\n");

	/* allocate memory; data */
	page_1->list->data = malloc(DATA * sizeof *page_1->list->data);
	/* if allocation failed */
	if (page_1->list->data == NULL) {
		fprintf(stderr, "page_1->list->data allocation failed\nfree page_1->list & page_1\n");
		/* free memory; list */
		free(page_1->list);
		page_1->list = NULL;
		/* free memory; page */
		free(page_1);
		page_1 = NULL;
	}
	printf("page_1->list->data allocated\n");

	/* allocate memory; data rows */
	for (i = 0; i < DATA; i++) {
		page_1->list->data[i] = malloc(10);
		/* allocation failed */
		if (page_1->list->data[i] == NULL) {
			fprintf(stderr, "page_1->list->data[%i] allocation failed\nfree page_1->data & page_1->list & page_1", i);
			/* free any memory done during the loop */
			for (k = i-1; k >= 0; k--) {
				/* free memory; data rows */
				free(page_1->list->data[k]);
				page_1->list->data[k] = NULL;
			}
			/* free memory; data */
			free(page_1->list->data);
			page_1->list->data = NULL;
			/* free memory; list */
			free(page_1->list);
			page_1->list = NULL;
			/* free memory; page */
			free(page_1);
			page_1 = NULL;
		}
		printf("page_1->list->data[%i] allocated\n", i);
	}

	/* free memory; data rows */
	for (j = DATA-1; j >= 0; j--) {
		if (page_1->list->data[j] != NULL) {
			free(page_1->list->data[j]);
			page_1->list->data[j] = NULL;
		}
		printf("page_1->list->data[%i] freed\n", j);
	}
	/* free memory; data */
	if (page_1->list->data != NULL) {
		free(page_1->list->data);
		page_1->list->data = NULL;
		printf("page_1->list->data freed\n");
	}
	/* free memory; list */
	if (page_1->list != NULL) {
		free(page_1->list);
		page_1->list = NULL;
		printf("page_1->list freed\n");
	}
	/* free memory; page */
	if (page_1 != NULL) {
		free(page_1);
		page_1 = NULL;
		printf("page_1 freed\n");
	}

	return 0;
}

Hope this helps.

-Stack Overflow

[kloony]

Thanks Narue,

"You can get a segmentation fault because malloc failed and returned a null pointer,"

what could be reasons for malloc to fail then? What I meant when I said that the system running out of memory was that malloc could not find memory to allocate, causing seg fault.

"Memory leaks will only slow your system down and possibly grind it to a halt. If you program crashes, it's because you did something wrong."

May I know what is meant by memory leaks? My program crashed (seg fault encountered) after doing 100 out of 300 loops, so my guess was that at the end of each loop, memory allocated was not freed, causing malloc to fail later on. Is this a reasonable guess?

[Stack Overflow]

Hello,

what could be reasons for malloc to fail then?

Keep in mind if the space cannot be allocated, a null pointer is returned. If you try to write to the NULL block of memory, it will cause a segmentation fault. It's best to test for NULL values before writing to the address.May I know what is meant by memory leaks?Definition: Memory leaks are often thought of as failures to release unused memory by a computer program. Strictly speaking, that behaviour is just more memory consumption. A memory leak occurs when the program loses even the ability to free the memory. Either behaviour diminishes the performance of the computer, as it becomes unable to use all its available memory.

-Stack Overflow

[kloony]

Thanks, Narue and Stack Overflow (esp. for your memory allocation techniques). :)

[Stack Overflow]

Hello,

You're welcome. If you have any further questions regarding the information I provided, don't hesitate to ask.

- Stack Overflow

[kloony]

Dear Stack Overflow,

I have a funny observation which I am not sure if it makes any sense. With regards to your code

/* free rows made by MATRIXint() */
/* where V represents the rows */
for (i = V-1; i >= 0; i--) {
	if (G->adj[i] != NULL) {
		free(G->adj[i]);
		G->adj[i] = NULL;
	}
}

/* free 2-dimensional pointer */
if (G->adj != NULL) {
	free(G->adj)
	G->adj = NULL;
}

/* free Graph */
if (G != NULL) {
	free(G);
	G = NULL;
}

it appears that when I use it to free up memory used for my graph G in the main program, it works, but when I write it as a function and include it as a header file as follows

void freegraph(G)
{ int i;
/* free rows made by MATRIXint() */
/* where V represents the rows */
for (i = (G->V)-1; i >= 0; i--) {
	if (G->adj[i] != NULL) {
		free(G->adj[i]);
		G->adj[i] = NULL;
	}
}

/* free 2-dimensional pointer */
if (G->adj != NULL) {
	free(G->adj)
	G->adj = NULL;
}

/* free Graph */
if (G != NULL) {
	free(G);
	G = NULL;
}

it doesn't work. I passed my graph G to this function and then had the following code in my main function

if(G==NULL)printf("success"); else printf("fail");

I got fail instead of the expected success. Why is this so?

[kloony]

I think I have just found the answer to my own question....thanks to all for looking! :)