You can use the visualization below to explore the effects of the library functions, system calls, and common algorithms involved dynamic memory allocation.
| Function | Purpose | Behavior |
|---|---|---|
malloc() | Allocate memory | Allocates a block of memory of the specified size and returns a pointer to the first byte of the block. The contents are uninitialized. |
calloc() | Allocate and zero-initialize memory | Allocates a block of memory for an array of elements of the specified size and initializes the contents to zero. |
realloc() | Resize an existing memory block | Changes the size of an existing memory block to the specified size. If the size is smaller, the excess memory is deallocated. |
free() | Deallocate previously allocated memory | Deallocates a previously allocated memory block. The behavior is undefined if the block has already been freed or was not allocated. |
void *malloc(size_t size);
The malloc() function allocates a block of memory of size bytes and returns a pointer to the first byte of the block. The contents of the block are uninitialized and may contain garbage data. If the allocation fails, malloc() returns a null pointer.
void *calloc(size_t nmemb, size_t size);
The calloc() function allocates a block of memory for an array of nmemb elements, each of size bytes, and returns a pointer to the first byte of the block. The contents of the block are initialized to zero. If the allocation fails, calloc() returns a null pointer.
void *realloc(void *ptr, size_t size);
The realloc() function changes the size of the memory block pointed to by ptr to size bytes. If ptr is a null pointer, realloc() behaves like malloc(size). If size is zero and ptr is not a null pointer, realloc() behaves like free(ptr). If the reallocation fails, realloc() returns a null pointer, and the original block of memory is left intact.
void free(void *ptr);
The free() function deallocates the memory block pointed to by ptr. If ptr is a null pointer, free() does nothing. If ptr has already been freed, free() may have unpredictable behavior.
The operating system maintains a pointer called the
If you your program uses a memory allocator and you use these system calls directly, you will likely corrupt the metadata and/or program data in the heap.
Reads and writes the memory locations after the program break have undefined behavior and typically cause segmentation faults.
| Function | Purpose | Behavior |
|---|---|---|
sbrk() |
Extend the heap by a specified amount | Increments (or decrements) the end of the program's heap segment, effectively changing the heap size by a specified number of bytes. |
brk() |
Set the end of the heap segment to a value | Sets the end of the program's heap segment to a specified address, effectively resizing the heap to a specific size. Returns 0 on success, -1 on error. |
void * sbrk(int numBytes);
The sbrk() system call is used to dynamically adjust the program break of a process. It takes a single argument, which specifies the number of bytes by which to adjust the program break. If the argument is positive, sbrk() extends the data segment of the process by the specified number of bytes. If the argument is negative, sbrk() reduces the size of the data segment by that amount. The new program break address is returned on success, or (void *) -1 on failure. sbrk() is often used by the memory allocation functions of programming languages such as C to allocate and deallocate memory.
int brk(void * address);
The brk() system call is used to set the program break of a process explicitly. It takes a single argument, which is the new address of the program break. If the new address is greater than the current program break, the data segment is expanded to include the new address. If the new address is less than the current program break, the data segment is reduced to the new address. brk() returns zero on success, or -1 on failure. brk() is less frequently used than sbrk() because it is more difficult to use for dynamic memory allocation, but it is still used in some low-level system programming tasks.
| Algorithm | Searching | Fragmentation | Efficiency |
|---|---|---|---|
| First Fit | Begins searching from the beginning of the list of free blocks | Can lead to significant fragmentation as it may leave smaller blocks of memory scattered throughout the heap | Simple and efficient approach |
| Best Fit | Searches for the smallest free block of memory that is larger than the requested size | Reduces fragmentation by leaving smaller blocks of free memory that can be used in the future | Slower than other algorithms as it requires a search through the entire list of free blocks for each memory request |
| Next Fit | Starts searching from the last allocation point | Improves efficiency and reduces fragmentation compared to the first fit algorithm | Can still suffer from fragmentation if blocks are repeatedly allocated and deallocated in a non-linear pattern |
The first fit algorithm for a memory allocator works by searching for the first free block of memory that is large enough to satisfy the requested size. This algorithm starts searching from the beginning of the list of free blocks, which makes it a simple and efficient approach. Once a free block is found, it is allocated to the requesting process. However, the first fit algorithm can lead to significant fragmentation as it may leave smaller blocks of memory scattered throughout the heap. This can cause problems if the system needs to allocate larger blocks of memory in the future. Despite its limitations, the first fit algorithm is a popular choice for simple memory allocation systems.
The best fit algorithm for a memory allocator works by searching for the smallest free block of memory that is larger than the requested size. This algorithm iterates through the entire list of free blocks and selects the block that is closest in size to the requested memory. This approach helps to reduce fragmentation as it leaves smaller blocks of free memory that can be used in the future. However, it can be slower than other algorithms as it requires a search through the entire list of free blocks for each memory request. Despite its limitations, the best fit algorithm is a popular choice for memory allocation in systems where fragmentation is a concern.
The next fit algorithm for a memory allocator works by searching for the next free block of memory that is large enough to satisfy the requested size. It starts searching from the last allocation point rather than the beginning of the free block list, which improves efficiency and reduces fragmentation. Once a free block is found, it is allocated to the requesting process. The next fit algorithm then updates the allocation point to the end of the newly allocated block so that the next search can start from that point. This approach helps to reduce fragmentation and can be faster than the best fit algorithm. However, it can still suffer from fragmentation if blocks are repeatedly allocated and deallocated in a non-linear pattern.
Coalescing is a technique used when memory is deallocated to reduce external fragmentation by merging adjacent free memory blocks. This process helps create larger, contiguous free memory blocks that can be used to satisfy allocation requests, improving the overall efficiency of memory usage. The metadata of the combined block is updated to reflect the new size. There are four cases of coalescing:
| Case | Description | Diagram |
|---|---|---|
| No coalescing | The free memory block being deallocated does not have any adjacent free blocks. The block remains as a separate free block. |
Allocated
Deallocated
Allocated
⟶
Allocated
Free
Allocated
⟶
Allocated
Free
Allocated
|
| Coalescing with the previous free block | When a block is deallocated and its preceding block is free, the two blocks are coalesced into a single, larger free block. |
Free
Deallocated
Allocated
⟶
Free
Free
Allocated
⟶
Free
Allocated
|
| Coalescing with the next free block | When a block is deallocated and its following block is free, the two blocks are coalesced into a single, larger free block. |
Allocated
Deallocated
Free
⟶
Allocated
Free
Free
⟶
Allocated
Free
|
| Coalescing with both the previous and next free blocks | When a block is deallocated and both its preceding and following blocks are free, all three blocks are coalesced into a single, larger free block. |
Free
Deallocated
Free
⟶
Free
Free
Free
⟶
Free
|
| Error | Description |
|---|---|
| Memory leak | Dynamically allocated memory is not freed after it is no longer needed, resulting in unreclaimable memory. |
| Double-free error | A block of memory is freed more than once, potentially causing memory corruption and program crashes. |
| Buffer underflow | Data is read outside the bounds of a dynamically allocated block of memory, potentially causing undefined behavior. |
| Use-after-free error | Memory is accessed after it has been freed, potentially causing undefined behavior or program crashes. |
Memory leaks occur when dynamically allocated memory is not freed after it is no longer needed. This can result in the program consuming more memory than necessary, potentially leading to performance issues and even crashes in extreme cases. To avoid memory leaks, it's important to keep track of allocated memory and ensure that it is properly freed when it is no longer needed.
Double-free errors occur when a block of memory is freed more than once, potentially causing memory corruption and program crashes. This can happen when a program attempts to free a block of memory that has already been freed, or when a program mistakenly frees a block of memory that is still in use. To avoid double-free errors, it's important to keep track of which blocks of memory have been freed and ensure that each block is freed only once.
Buffer overflows occur when data is written outside the bounds of a dynamically allocated block of memory, potentially overwriting other data or causing crashes. This can happen when a program writes more data to a buffer than the buffer was allocated to hold. To avoid buffer overflows, it's important to ensure that buffers are properly sized and that all memory accesses are within the bounds of the allocated memory.
A use-after-free error occurs when memory is accessed after it has been freed. This can happen when a program continues to use a pointer to memory that has been freed. A pointer to freed memory is called a dangaling pointer. When a read occurs on a dangling pointer, any of following may occur:
| Action | Result | Condition |
|---|---|---|
| Read | Garbage data is returned | If the memory pointed to by the dangling pointer has been reallocated and overwritten with new data |
| Write | Memory Corruption | |
| Read | Valid data is returned | If the memory pointed to by the dangling pointer has not yet been overwritten, regardless of whether it has been reallocated |
| Write | Nothing | |
| Read/Write | A segmentation fault occurs | If the size of the heap has contracted and the memory address pointed to by the dangling pointer is no longer within the heap and on a page that the OS has reclaimed, a segmentation fault may occur. |
To avoid use-after-free errors, it's important to carefully manage dynamically allocated memory and ensure that memory is only freed when there will no longer be any pointers to that block of memory.
| Term | Definition |
|---|---|
| Allocate | To reserve a block of memory for a specific purpose or data structure during program execution. |
| Base Address | The starting address of a block or region in memory. |
| Data Segment | A portion of a program's memory space that contains statically allocated variables. A small amount of metadata for managaging the heap resides here, such as pointers to the heap base address and/or the free list head(s). |
| Dynamic Memory Allocation | Process of allocating memory during program execution, allowing programs to request and release memory as needed. |
| Fragmentation | A condition in which memory is inefficiently used due to the presence of small, unusable gaps (external fragmentation) or memory allocated for alignment purposes but not used (internal fragmentation). |
| Garbage Collector | A utility that automatically identifies and frees unused memory, preventing memory leaks and reducing the need for manual memory management. These are used by high level languages and will be explained in an upcoming visualization tool. |
| Heap Segment / The Heap | A region of memory used for dynamic memory allocation, where blocks of memory can be allocated and deallocated in an arbitrary order. |
| Metadata | i) Information about a memory block, such as its size and status (allocated or free), stored with the block in the heap. ii) Information about the heap overall, such as the location of the heap base address, stored in the data segment. |
| Payload | The actual data or content stored within an allocated memory block, separate from its metadata. |
| Program Break | The location of the end of the heap segment in a program's memory space, which can be adjusted to increase or decrease the size of the heap. |
| Sentinel Value | A special value used to mark the end of a list. NULL and -1 are the two most commonly used sentinal values. |
| Static Memory Allocation | Process of allocating memory at compile time for storing global and static variables. |
| System Call | A request made by a program to the operating system to perform a low-level operation, such as adjusting the program break or accessing hardware resources. |
| Word Size | The number of bits that a processor can manipulate in a single operation, which influences the size of memory addresses and the maximum amount of memory that can be accessed. |