Another question regarding memory

Thread Solved
Reply

Join Date: Jan 2005
Posts: 33
Reputation: kloony is an unknown quantity at this point 
Solved Threads: 0
kloony kloony is offline Offline
Light Poster

Another question regarding memory

 
0
  #1
Mar 10th, 2005
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:

  1. void QUEUEinit(int); /* initiates queue */
  2.  
  3. static Item *q;
  4. static int N, head, tail;
  5.  
  6. void QUEUEinit(int maxN)
  7. { q=malloc((maxN+1)*sizeof(Item));
  8. if(q){
  9. N=maxN+1; head = N; tail = 0;}else{printf("memory allocation error.\n");}
  10. }

So every time in my main program, whenever I call

  1. QUEUEinit(50);

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

  1. for(i=0; i<1000; i++)
  2. 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

  1. for(i=0; i<1000; i++)
  2. {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.
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 185
Reputation: Stack Overflow is an unknown quantity at this point 
Solved Threads: 4
Stack Overflow's Avatar
Stack Overflow Stack Overflow is offline Offline
C Programmer

Re: Another question regarding memory

 
0
  #2
Mar 10th, 2005
Hello,

Originally Posted by kloony
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.
Originally Posted by kloony
What if, instead I had

Code:
  1. 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 to q 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
Following the rules will ensure you get a prompt answer to your question. If posting code, please include BB [code][/code] tags. Your question may have been asked before, try the search facility.

IRC
Channel: irc.daniweb.com
Room: #c, #shell
Reply With Quote Quick reply to this message  
Join Date: Feb 2005
Posts: 195
Reputation: Tight_Coder_Ex is an unknown quantity at this point 
Solved Threads: 13
Tight_Coder_Ex's Avatar
Tight_Coder_Ex Tight_Coder_Ex is offline Offline
Junior Poster

Re: Another question regarding memory

 
0
  #3
Mar 10th, 2005
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.
Reply With Quote Quick reply to this message  
Join Date: Jan 2005
Posts: 33
Reputation: kloony is an unknown quantity at this point 
Solved Threads: 0
kloony kloony is offline Offline
Light Poster

Re: Another question regarding memory

 
0
  #4
Mar 10th, 2005
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:

  1. typedef struct graph *Graph;
  2. Graph GRAPHinit(int);
  3. struct graph{int V; int E; int **adj;}
  4.  
  5. int **MATRIXint(int r, int c, int val)
  6. { int i,j;
  7. int **t=malloc(r*sizeof(int *));
  8. if(t){ for(i=0; i<r; i++)
  9. t[i]=malloc(c*sizeof(int)); if{t[i]}
  10. {for(i=0;i<r; i++)
  11. for(j=0;j<c;j++) t[i][j]=val;}
  12. else{printf("mem allocation error.\n"); return 0;}
  13. }else{printf("mem allocation error.\n"); return 0;}
  14. return t;
  15. }
  16.  
  17. Graph GRAPHinit(int V)
  18. { Graph G = malloc(sizeof*G);
  19. if(G){G->V=V; G->E=0; G->adj=MATRIXint(V,V,0);}
  20. else{printf("mem allocation error.\n"); return 0;}
  21. return G;
  22. }

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
  1. 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
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 185
Reputation: Stack Overflow is an unknown quantity at this point 
Solved Threads: 4
Stack Overflow's Avatar
Stack Overflow Stack Overflow is offline Offline
C Programmer

Re: Another question regarding memory

 
0
  #5
Mar 10th, 2005
Hello,

Originally Posted by kloony
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.

Originally Posted by kloony
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.

Originally Posted by kloony
Now supposed I am done with G and I want to free the memory used for G, will

  1. 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 at V-1 is because you allocated from 0 to <r 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
Following the rules will ensure you get a prompt answer to your question. If posting code, please include BB [code][/code] tags. Your question may have been asked before, try the search facility.

IRC
Channel: irc.daniweb.com
Room: #c, #shell
Reply With Quote Quick reply to this message  
Join Date: Jan 2005
Posts: 33
Reputation: kloony is an unknown quantity at this point 
Solved Threads: 0
kloony kloony is offline Offline
Light Poster

Re: Another question regarding memory

 
0
  #6
Mar 10th, 2005
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")?
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 7,541
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 704
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Another question regarding memory

 
0
  #7
Mar 10th, 2005
>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.
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 185
Reputation: Stack Overflow is an unknown quantity at this point 
Solved Threads: 4
Stack Overflow's Avatar
Stack Overflow Stack Overflow is offline Offline
C Programmer

Re: Another question regarding memory

 
0
  #8
Mar 10th, 2005
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:

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
Following the rules will ensure you get a prompt answer to your question. If posting code, please include BB [code][/code] tags. Your question may have been asked before, try the search facility.

IRC
Channel: irc.daniweb.com
Room: #c, #shell
Reply With Quote Quick reply to this message  
Join Date: Jan 2005
Posts: 33
Reputation: kloony is an unknown quantity at this point 
Solved Threads: 0
kloony kloony is offline Offline
Light Poster

Re: Another question regarding memory

 
0
  #9
Mar 10th, 2005
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?
Reply With Quote Quick reply to this message  
Join Date: Sep 2004
Posts: 185
Reputation: Stack Overflow is an unknown quantity at this point 
Solved Threads: 4
Stack Overflow's Avatar
Stack Overflow Stack Overflow is offline Offline
C Programmer

Re: Another question regarding memory

 
0
  #10
Mar 10th, 2005
Hello,

Originally Posted by kloony
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.

Originally Posted by kloony
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
Following the rules will ensure you get a prompt answer to your question. If posting code, please include BB [code][/code] tags. Your question may have been asked before, try the search facility.

IRC
Channel: irc.daniweb.com
Room: #c, #shell
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC