Linux Beyond the Basics: Process Memory Layout and Dynamic Allocation
8 min readJul 7, 2024
This blog post is part of the series Linux Beyond the Basics.
Introduction
Welcome back to the Linux Beyond the Basics series! Efficient memory management is crucial for any operating system, and Linux is no exception. In this episode, we’ll explore the Linux process memory layout and dynamic allocation.
Kernel Space vs. User Space
To understand how Linux handles memory, it’s important to first grasp the distinction between kernel space and user space. In Linux, a process memory space is divided into two distinct areas:
- Kernel Space: This is a protected area of memory where the core of the operating system (the kernel) resides. The kernel is responsible for managing hardware, scheduling tasks, and providing essential services to applications. The kernel space is shared and identical for all processes.
- User Space: This is where your applications and their data live. Applications cannot directly access kernel space for security reasons. Each process has its own isolated user space, ensuring that one process cannot interfere with the memory of another.
This separation is crucial for system stability and security. It prevents misbehaving applications from corrupting the kernel or accessing sensitive data.
The User Space Memory Layout
Within a process’s user memory space, there are different regions with specific purposes:
Higher Addresses
|--------------|
| Stack | (Grows Downwards)
|______________|
| |
| | (Unavailable)
|______________|
| Heap | (Grows Upwards)
| | <-- Program Break (Manipulated by sbrk)
| | <-- malloc/free work within this area
| |
|--------------|
| BSS Segment | (Uninitialized Data)
|--------------|
| Data Segment | (Initialized Data)
|--------------|
| Text Segment | (Code)
|--------------|
Lower AddressesKey Points:
- Stack and Heap: These are the dynamic parts of memory that grow and shrink during program execution.
- Heap Growth: The
sbrksystem call is used to move the program break, which effectively expands or (in some cases) attempts to shrink the heap. - Heap Management: The
mallocandfreefunctions work within the existing heap space, managing the allocation and deallocation of memory blocks for your program. - Other Segments: The text, data, and BSS segments are relatively static and hold the program’s code and global variables.
The sbrk Syscall
sbrk is a system call that allows your program to request memory directly from the kernel. It's a low-level building block, primarily used to change the size of the heap by adjusting the program break.
How sbrk Works
- You call
sbrk(increment)to indicate how much you want to change the heap size. A positive value increase the heap size; while a negative value decreases the heap size; when the value is 0, it simply returns the current location of the heap. - The kernel moves the program break to adjust the heap accordingly.
sbrkreturns the previous location of the program break.
User-Space Memory Management: malloc and free
While sbrk is powerful, it's also quite low-level. Most programs use malloc and free instead. These C library functions provide a more convenient way to allocate and deallocate memory within the heap.
How malloc and free Work (Simplified)
malloc(size): Finds a free block in the heap or requests more memory if needed (potentially usingsbrk).free(ptr): Marks the memory block pointed to byptras available for reuse.
Simplified Implementation of malloc and free
Here’s a simplified implementation of malloc and free in C++, along with explanations to illustrate the core concepts:
#include <cstdio>
#include <unistd.h>
#include <cstring>
#define BLOCK_SIZE sizeof(struct Block)
// Memory block structure
struct Block {
size_t size;
int free;
struct Block *next;
};
struct Block *heap_start = NULL;
// Note: This implementation is not thread-safe. In a multi-threaded environment,
// proper synchronization mechanisms would be necessary to ensure correct behavior.
// sbrk wrapper for clarity
void* my_sbrk(intptr_t increment) {
void *result = sbrk(increment);
if (result == (void*)-1) {
return NULL; // sbrk failed
}
return result;
}
// Initialize a new block of memory
struct Block *init_block(void *addr, size_t size) {
struct Block *block = static_cast<struct Block*>(addr);
block->size = size - BLOCK_SIZE;
block->free = 1; // Initially set as free
block->next = NULL;
return block;
}
/**
* my_malloc: Allocates memory of specified size
*
* Overview:
* This function implements a simple memory allocation scheme. It manages a linked list
* of memory blocks, each with metadata about its size and whether it's free or not.
*
* Algorithm:
* 1. Align the requested size to 8 bytes for better memory access.
* 2. If it's the first allocation, initialize the heap using sbrk.
* 3. Search through the existing blocks for a free block of sufficient size.
* 4. If a suitable block is found:
* a. If the block is significantly larger, split it.
* b. Mark the block as used and return it.
* 5. If no suitable block is found, extend the heap using sbrk and create a new block.
*
* @param size: The number of bytes to allocate
* @return: Pointer to the allocated memory, or NULL if allocation fails
*/
void *my_malloc(size_t size) {
struct Block *current, *prev;
void *block_addr;
// Align size to multiple of 8 bytes
size = (size + 7) & ~7;
if (heap_start == NULL) {
// First allocation, initialize heap
block_addr = my_sbrk(size + BLOCK_SIZE);
if (block_addr == NULL) {
return NULL;
}
heap_start = init_block(block_addr, size + BLOCK_SIZE);
heap_start->free = 0; // Mark as not free
return static_cast<void*>(static_cast<char*>(static_cast<void*>(heap_start)) + BLOCK_SIZE);
}
// Search for a free block
current = heap_start;
prev = NULL;
while (current && !(current->free && current->size >= size)) {
prev = current;
current = current->next;
}
if (current == NULL) {
// No free block found, extend heap
block_addr = my_sbrk(size + BLOCK_SIZE);
if (block_addr == NULL) {
return NULL;
}
current = init_block(block_addr, size + BLOCK_SIZE);
current->free = 0; // Mark as not free
prev->next = current;
} else if (current->size >= size + BLOCK_SIZE + 8) {
// Split block if it's much larger than needed
struct Block *new_block = reinterpret_cast<struct Block*>(
reinterpret_cast<char*>(current) + BLOCK_SIZE + size
);
new_block->size = current->size - size - BLOCK_SIZE;
new_block->free = 1; // The split-off block is free
new_block->next = current->next;
current->size = size;
current->next = new_block;
current->free = 0; // Mark the allocated block as not free
} else {
// Use the entire block
current->free = 0; // Mark as not free
}
return static_cast<void*>(static_cast<char*>(static_cast<void*>(current)) + BLOCK_SIZE);
}
/**
* my_free: Deallocates the memory pointed to by ptr
*
* Overview:
* This function marks a previously allocated block of memory as free. It also
* performs coalescing with the next block if it's also free, to reduce fragmentation.
*
* Algorithm:
* 1. If the pointer is NULL, return immediately (it's valid to free a NULL pointer).
* 2. Find the block metadata by subtracting the block size from the given pointer.
* 3. Mark the block as free.
* 4. If the next block is also free, merge this block with the next one:
* a. Add the size of the next block (including its metadata) to this block.
* b. Update this block's 'next' pointer to skip the merged block.
*
* Note: This implementation doesn't coalesce with the previous block or return
* memory to the OS, which a more complete implementation might do.
*
* @param ptr: Pointer to the memory to be freed
*/
void my_free(void *ptr) {
if (!ptr) return;
struct Block *block = reinterpret_cast<struct Block*>(static_cast<char*>(ptr) - BLOCK_SIZE);
block->free = 1;
// Merge with next block if it's free
if (block->next && block->next->free) {
block->size += BLOCK_SIZE + block->next->size;
block->next = block->next->next;
}
// Note: In a real implementation, we might consider returning memory to the OS
// using brk() if a large chunk at the end of the heap becomes free
}
void print_heap() {
struct Block *current = heap_start;
int i = 0;
while (current) {
printf("Block %d: Address: %p, Size: %zu, Free: %d\n",
i++, static_cast<void*>(current), current->size, current->free);
current = current->next;
}
printf("Program break: %p\n\n", sbrk(0));
}Example usage:
int main() {
printf("Initial state:\n");
print_heap();
// Allocate an array of 10 integers
int *p_int = static_cast<int*>(my_malloc(sizeof(int) * 10));
printf("After allocating 10 ints:\n");
print_heap();
// Set values for integers
for (int i = 0; i < 10; i++) {
p_int[i] = i * 10;
}
// Print integer values
printf("Integer values:\n");
for (int i = 0; i < 10; i++) {
printf("%d ", p_int[i]);
}
printf("\n\n");
// Allocate a single char
char *p_char = static_cast<char*>(my_malloc(sizeof(char)));
printf("After allocating 1 char:\n");
print_heap();
// Set value for char
*p_char = 'A';
// Print char value
printf("Char value: %c\n\n", *p_char);
// Allocate another array of 5 integers
int *p_int2 = static_cast<int*>(my_malloc(sizeof(int) * 5));
printf("After allocating 5 more ints:\n");
print_heap();
// Set values for second integer array
for (int i = 0; i < 5; i++) {
p_int2[i] = i * 100;
}
// Print second integer array values
printf("Second integer array values:\n");
for (int i = 0; i < 5; i++) {
printf("%d ", p_int2[i]);
}
printf("\n\n");
// Free the allocations in a different order
my_free(p_char);
printf("After freeing char:\n");
print_heap();
my_free(p_int);
printf("After freeing first int array:\n");
print_heap();
my_free(p_int2);
printf("After freeing second int array:\n");
print_heap();
return 0;
}Output:
Initial state:
Program break: 0x558f48c08000
After allocating 10 ints:
Block 0: Address: 0x558f48c08000, Size: 40, Free: 0
Program break: 0x558f48c08040
Integer values:
0 10 20 30 40 50 60 70 80 90
After allocating 1 char:
Block 0: Address: 0x558f48c08000, Size: 40, Free: 0
Block 1: Address: 0x558f48c08040, Size: 8, Free: 0
Program break: 0x558f48c08060
Char value: A
After allocating 5 more ints:
Block 0: Address: 0x558f48c08000, Size: 40, Free: 0
Block 1: Address: 0x558f48c08040, Size: 8, Free: 0
Block 2: Address: 0x558f48c08060, Size: 24, Free: 0
Program break: 0x558f48c08090
Second integer array values:
0 100 200 300 400
After freeing char:
Block 0: Address: 0x558f48c08000, Size: 40, Free: 0
Block 1: Address: 0x558f48c08040, Size: 8, Free: 1
Block 2: Address: 0x558f48c08060, Size: 24, Free: 0
Program break: 0x558f48c08090
After freeing first int array:
Block 0: Address: 0x558f48c08000, Size: 72, Free: 1
Block 1: Address: 0x558f48c08060, Size: 24, Free: 0
Program break: 0x558f48c08090
After freeing second int array:
Block 0: Address: 0x558f48c08000, Size: 72, Free: 1
Block 1: Address: 0x558f48c08060, Size: 24, Free: 1
Program break: 0x558f48c08090Another Powerful Syscall: mmap
Note that in addition to sbrk, mmap is another powerful system call. It can be used for various purposes, but one common use case is mapping files directly into your program's memory. This allows you to read and write to files as if they were just another region of memory, often providing performance benefits.
Why mmap is Useful:
- File I/O: Efficiently read/write large files.
- Shared Memory: Create memory regions that multiple processes can access.
- Custom Allocations: Allocate memory with specific properties (e.g., not backed by swap space).
Takeaways
- Linux Memory Layout: Understand the distinct regions of a process’s memory space, divided into kernel space and user space.
sbrk: A system call for adjusting the heap size (primarily used for expansion).mallocandfree: User-friendly functions that simplify memory management within the heap.mmap: A versatile system call, often used for file mapping and shared memory.
