|
|
e
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
| CPSC 223b: Data Structures and Programming Techniques | Handout #9 | |
| Professor M. J. Fischer | February 10, 2008 | |
Memory Management and Flex Demo
Proper use of the Flex module provided for use in problem set 4 requires careful attention to issues of memory management. We describe them in some detail below.
The Flex data structure consists of two dynamically allocated parts:
The user who calls newFlex() owns the Flex instance and is responsible for calling freeFlex() when it is no longer needed. The slot array is owned by the Flex instance until extractFlex() is called. At that point, ownership is transferred to the caller, and the slot field is set back to NULL. A decision was made in the design of Flex that the user must assume responsibility for the slot array before freeFlex() is called. Thus, freeFlex() should only be called when the data structure is empty, as is the case right after extractFlex() is called. Otherwise, it gives the fatal error, “Attempt to free non-empty flex”.
extractFlex() returns a value of type String⋆ (which is the same as type char⋆⋆). This is a pointer to an array of strings. Each element of this array is a String, i.e., a pointer to another array of char. Figure 1 gives a picture of such a structure.
Notice in this example that four blocks of memory are involved: A block of three pointers and three blocks of characters. The block of pointers was allocated by Flex. The blocks of characters are the user’s responsibility to allocate and to later free.
A demonstration program, demo.c and accompanying Makefile have been placed in the PS4 assignment directory on the Zoo. The program is largely self-explanatory, but I want to point out in particular how the character buffers to store the individual strings get allocated and deallocated.
The function fill() in Figure 2 reads words from the user into the buffer buf and puts them in the Flex structure cart (line 15). However, before inserting into the cart, a new storage block, just large enough to store the newly-read string, is allocated in line 13. Line 14 copies the characters from buf into the new storage area newStr. strcpy() also copies the terminating NUL byte, so nothing special needs to be done to preserve it. Line 15 puts a pointer to the new string into the slot array inside of cart.
(As an aside, note that the long format in the printf() statement that begins on line 5 has been broken into two parts and placed on separate lines. Standard C permits string constants to be broken in this way and treats the multipart string just as if it had been written as a single long string.)
|
20 void process( Flex cart )
21 { 22 // sort cart 23 sortFlex( cart ); 24 25 // get its length and contents 26 int len = lenFlex( cart ); 27 String⋆ wordList = extractFlex( cart ); 28 // ExtractFlex passes ownership of wordList 29 // and the strings to which its elements point. 30 // We are responsible for freeing them when we're 31 // done processing them. 32 33 // print out our word list 34 for (int k=0; k<len; k++) { 35 printf( "word[%2i]=\"%s\"\n", k, wordList[k] ); 36 } 37 38 // free each of the Strings on our word list 39 for (int k=0; k<len; k++) { 40 free( wordList[k] ); 41 } 42 43 // free the word list itself 44 free( wordList ); 45 }
|
The strings that were allocated in line 13 of fill() must eventually be freed when we are done with them. The is done in process(), shown in Figure 3. The String array that was pointed to by slot in cart is extracted from the cart in line 27 and a pointer to it placed in wordList. The data is used in lines 34–35. The remainder of the code is to free the storage that we are done with. Lines 39-40 run down the String array, freeing each character block in turn. Finally, line 44 frees the String array itself.
One of the most difficult aspects of C programming is doing memory management correctly. There are three kinds of management errors: Failing to allocate (enough) storage before it is used, freeing storage before you are done with it, and failing to free storage after it is no longer needed. The first two kinds of errors lead to faulty programs: segmentation faults or simply wrong (and oft times bizarre) behavior of the program. The third kind of error, memory leaks, do not make the program produce incorrect answers, but they consume unnecessary resources. In a large or long-running program, memory leaks can cause a program to eventually consume all of available memory, at which point it (and perhaps other applications running at the same time) fail due to insufficient memory.
My goal in this course is for all programs submitted to have no memory management errors and to have freed all dynamic memory at the time of exit. Eliminating all memory leaks is not easy to do at first, so I will be tolerant of memory leaks on PS4.
|
There is a tool on the Zoo called valgrind that is very helpful in eliminating memory leaks. To use it, just type the command valgrind followed by the name of your program and any arguments that it takes.
Figure 4 shows the result of running the demo program under valgrind. Note that the input and output for the demo program appears in the middle of the output. If there had been any memory management errors of the first two kinds, they would have been noted there. At the end, valgrind reports separately on memory that was never freed and is no longer accessible, and memory that was never freed but still appears to be in use. It also gives some statistics on the use of malloc and free.
|
Figure 5 shows what happens when valgrind is run on a program with a memory leak. In this case, I commented out line 44 of process() which is supposed to free the String array. Notice the report of definitely lost memory. Rerunning with the --leak-check=full flag as instructed gives additional output that will help one identify where in the code the lost memory was originally allocated.
Copyright 2008 by Michael J. Fischer
