Help you learn/review C's facilities for dynamic memory management
Suppose we wish to write a general-purpose number sorting program
See sort1.c
Functionality
Reads numbers from stdin, sorts them in ascending order, writes the numbers to stdout
Design
Uses stack-resident array
Uses insertion sort (for simplicity)
Alternative: Use quick sort, heap sort, merge sort, etc.
Trace (briefly, showing stack and heap)
Problem (obvious)
Works only for 10 or fewer numbers
It's certainly not a general-purpose number sorting program
See sort2.c
(Intended) functionality
Reads numbers from stdin, sorts them in ascending order, writes the numbers to stdout
Design
Uses variable-sized stack-resident array
Problem
Compiletime errors in C90
Length of a stack-resident array must be specified at compiletime
Declaration statement must appear before any other kind of statement within its block
(Would work in C99!!!)
How to fix it?
One approach: use dynamic memory management
See C Dynamic Memory Management Fundamentals
Trace each sequence on board showing stack and heap
For elementary types
Note: free(pi) does not change the value of pi
C uses call by value, so it could not
For arrays
Question: How does free know how many bytes are in the memory block that it is freeing?
Answer: Each dynamically allocated memory block has a hidden header
For structures
Note arrow operator -- very important in this course
Changing size
If new size is less than old size:
Releases memory from block, changing its header
If new size is greater than old size:
realloc() tries to grab contiguous memory
Can => efficient
Cannot => grabs new memory, copies data from old memory to new, and frees old memory => inefficient
New memory is not initialized
See Common C Dynamic Memory Management Errors
Trace each sequence on board showing stack and heap
Memory leak
Can be difficult to find
Performance may decrease, but...
Program will behave reasonably until memory is exhausted
Significant problem when it occurs in a loop in server software -- software that is running continuously for days/months
Notoriously common problem in commercial software, especially database drivers
Tools exist (e.g. Purify) that can help you to detect memory leaks
Beyond the scope of this course
Dangling pointer
Can be difficult to find
Program will behave reasonably until freed memory is used for some other purpose
Recommendation (which I don't follow, but probably should):
After freeing memory reference by a pointer, assign NULL to that pointer
Subsequent dereference (of memory address 0) will cause segmentation fault
Predictable
Can use GDB to find
Much better than dangling pointer
Double free
Can be difficult to find
Effect is system dependent
Some systems:
No ill effects at all
Some systems:
First call to free adds memory block to free list
Second call to free adds same memory block to free list -- heap is thus corrupted
Call to malloc() grabs memory from free list
Next call to malloc() grabs same memory from free list!!!
Recommendation (as previously described)
After freeing memory reference by a pointer, assign NULL to that pointer
free(NULL) does nothing, by definition
Improper reallocation
Note failure to assign return value of realloc() to pi
Probably OK when new size is smaller than old size
Probably not OK when new size is larger than old size
Causes memory leak, dangling pointer, and double free!!!
See sort3.c
Functionality
Handles any count of numbers
Asks the user how many numbers (max) he/she will enter, and proceeds accordingly
Design
Uses a dynamically allocated (i.e. heap-resident) array
Trace (briefly, showing stack and heap)
Good to call assert() after each call of malloc(), calloc(), or realloc()
Problem
Works, but...
Asking the user how many numbers he/she will enter is awkward
See sort4.c
Functionality
Handles any count of numbers, without asking the user how many there are
Design
Uses a heap-resident array
Uses realloc() to expand its size as necessary
Note: Too inefficient to expand with every insertion, so...
Do the expansion geometrically
Trace (briefly, showing stack and heap)
Problem
None!
Copyright © 2008 by Robert M. Dondero, Jr.