Memory Allocation in C

Memory Allocation in C
An Overview

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Memory Allocation for Different Entities

Entities with Automatic Duration:
- Implementation dependent, but typically allocated from the stack
Entities with Static Duration:
- Implementation dependent, but typically allocated at compile/link/load time before execution begins
Entities with Dynamic Duration:
- Implementation dependent, but typically handled by memory management functions

Some Dynamic Memory Management Functions in C

(void *) malloc(size_t size):
- Allocates size bytes
- The allocated memory is not initialized
- Returns a pointer to the allocated memory
(void *) realloc(void* p, size_t size):
- Changes the size of the block pointed to by p (which, if it is not null, must have been returned by a call to malloc() or realloc()) to size bytes
- Memory up to the minimum of the old and new sizes will be unchanged; newly allocated memory will be uninitialized
- Returns a pointer to the allocated memory (or NULL) but does not change the parameter (it can't since the parameter is a void* not a void**)
- Note: If p is null then realloc() is equivalent to malloc()
void free(void *p):
- Makes the memory space pointed to by p (which must have been returned by a previous call to malloc() or realloc()) available for re-use
- Does not change p (i.e., p still points to the now free memory) -- it can't because the parameter is a void* NOT a void**
- Note: If p is null then the call does nothing

Some Other Memory-Related Functions in C

(void *) calloc(size_t number, size_t size):
- Allocates enough memory for number entities of size size
- Initializes the memory to 0
- Returns a pointer to the allocated memory (or NULL)
- Note: The caller should ensure size * number is of type size_t (e.g., does not wrap)
(void *) memset(void* buffer, int value, size_t number):
- Copies the unsigned char named value to the first number of characters pointed to by buffer
- Returns a pointer to buffer

An Often-Overlooked Issue

An Observation:
- 0 is often not treated as a special case and, as a result, requests are often made to allocate 0 bytes of memory
The C Standard:
- The behavior is implementation-defined: either a NULL pointer is returned, or the behavior is as if the size were nonzero (but the returned pointer should not be used)
- The amount of memory allocated is unspecified
Another Observation:
- This is especially problematic for realloc() since it will not free the old memory

Memory Management Functions Not Dicussed (And to be Avoided)

alloca():
- Allocates memory in the stack of the caller (that is freed when the function returns)
- Problem: Can make allocations that exceed the bounds of the stack
Calling realloc() with a size of 0:
- Frees memory

Alignment

Definition:
- An alignment is the (implementation-defined) number of bytes between successive addresses at which an entity can be allocated
Representation:
- An alignment is represented as a value of type size_t
Self-Alignment:
- The requirement that an entity begin at an address that is a multiple of its size (e.g., a 32-bit int must begin at an address that is a multiple of 32)

Memory Managers

Where Are They?
- Typically part of the operating system (e.g., libc)
- Sometimes provided by the compiler
Linking:
- May be statically linked in the executable
- May be dynamically linked at run-time

Memory Managers (cont.)

Methods:
- Best-Fit: Return the smallest available chunk of memory that is large enough
- First-Fit: Return the first available chunk of memory that is large enough
Implementations:
- Doug Lea's is one of the most common on Linux
- Microsoft has one called RtlHeap
- Most are based on work by Donald Knuth