A list of memory locations from 0 to some maximum, which Process (进程) can access
Address space is powered by Virtual Memory, so everything in address space is dedicated to that particular process
4 main components
Data in Text Segment (the orange block shown above) and Data Segment (the red block shown above) are shipped with the program
Data in Heap Segment (the blue block shown above) and Stack Segment (the green block shown above) are allocated dynamically when the program is running
Heap Segment
Data is added into heap segment explicitly by Process (进程) during runtime using System Call (系统调用) like brk() for Kernel that follow POSIX. The data in heap can live indefinitely even when function returns, the data is only removed when the process make the related System Call (系统调用) explicitly
Grows and shrinks as the process allocates and deallocates memory. The heap segment grows upwards, because the Memory Address is increasing as we have more data is allocated inside the heap segment
Bigbrain
When assigning one variable to another variable, data is not duplicated, instead the Pointer to the data inside the heap segment is duplicated and assigned. A nice visualisation on heap memory allocation can be found here.
Manual memory management from the process needed!
Process is responsible of allocating memory and deallocating in the heap segment. See language examples below.
Java
Memory allocation with new keyword, and memory deallocation is done by Garbage Collector automatically
Rust
Memory allocation with Box::new() function, and memory deallocation is done automatically using Box Deallocation Principle
C
Memory allocation with malloc() function, and manual memory deallocation is done with free() function
Manual Memory Deallocation is Dangerous!
After we manually deallocated the heap memory associated with a Pointer, then try to read data from the same pointer, it will lead to undefined behaviours. Thus, resulting in Poor memory safety.
There are 2 types of heap fragmentation - Internal Fragmentation & External Fragmentation(show in the diagram above)
Internal Fragmentation
External Fragmentation
Definition
When allocated Memory frames have unused memory space, since each memory frame comes with a fixed size.
When free memory frames in the heap are scattered throughout the memory space after a series of allocations and deallocations of memory blocks of varying sizes.
Risk
Increased memory consumption than actual demand.
For example, the memory frame size is 10MB, and my program needs 10.00001MB. We will get 2 memory frames that are 10MB each, this means 9.99999MB is wasted. Imagine I have a lot of programs with 10.00001MB in my computer, that means we waste almost half of the available Main Memory!
Difficulty to allocate contiguous blocks of memory → reduced performance.
Small gaps between allocated blocks can also become unusable if Virtual Memory isn’t used, even though the total amount of free memory might be sufficient to fulfil a request.
Ways to handle memory fragmentation
Compaction - rearranging memory blocks to eliminate gaps.
Expands as functions are called and shrinks as they return
Obtain stack size
ulimit -s
Grows Downwards
Stack Segment starts at a higher Memory Address, then memory address decreases as we add in Stack Frame, thus growing downwards in terms of Memory Address, so to remove stack frame, we need to increment the Stack Pointer.
When fn1() calls fn2(), fn1()’s stack frame is created first. Then, fn2()’s stack frame is placed on top of fn1()’s on the call stack, although it may appear below the older frame in the diagram because the stack grows downwards.
Fun Fact Regarding Grow Downwards
Growing downwards is a convention from when computers had small memories and the stack was placed at the end of the Data Segment. Nowadays the stack can be anywhere, but the convention stuck on, at the end of the day it makes no difference.
Variables live in the stack
When assigning one variable to another variable, data is duplicated.
For example, a=1 and b=a, the value 1 is duplicated and assigned to b. A nice visualisation can be found here
Data management in Stack Segment is more efficient than Heap Segment
Stack memory is allocated and deallocated in a Last In, First Out (LIFO) manner, making it faster than heap memory. This is because all it needs to do is move the Stack Pointer up or down, while heap memory requires more complex memory management
No overhead of complex Synchronisation (同步), unlike data inside heap segment, data inside the stack segment is dedicated to that particular Thread. Thus, manipulation of data inside the stack segment doesn’t require the complex synchronisation
Attention
The size of variable on the stack is defined before Compilation
XV6-RISCV Kernel Stack
// xv6-riscv kernel codes, start.c#include "types.h"#include "param.h"#include "memlayout.h"#include "riscv.h"#include "defs.h"void main();void timerinit();// entry.S needs one stack per CPU.__attribute__ ((aligned (16))) char stack0[4096 * NCPU];// a scratch area per CPU for machine-mode timer interrupts.uint64 timer_scratch[NCPU][5];// assembly code in kernelvec.S for machine-mode timer interrupt.extern void timervec();// ...
A stack segment is created, and it is shared by all the CPU, each takes 4096 bytes
NCPU is hard-coded to 8, so the stack has a length of 32768 bytes
# xv6-riscv kernel codes, entry.S# qemu -kernel loads the kernel at 0x80000000# and causes each hart (i.e. CPU) to jump there.# kernel.ld causes the following code to# be placed at 0x80000000..section .text.global _entry_entry: # set up a stack for C. # stack0 is declared in start.c, # with a 4096-byte stack per CPU. # sp = stack0 + (hartid * 4096) la sp, stack0 li a0, 1024*4 csrr a1, mhartid addi a1, a1, 1 mul a0, a0, a1 add sp, sp, a0 # jump to start() in start.c call startspin: j spin
We load the base address of the stack segment
Then based on the core id (0-7), we set the Stack Pointer for each CPU. We can see the stack pointer starting point is obtained by adding (hartid * 4096) to the base address, this is because stack segment grows downwards when we are adding values to the stack
Stack Frame
A section of the Stack Segment dedicated to a specific function call
f()
void f() { c = g(2, 90);}
g()
void g(int i, int j) { int a;}
Stack frame setup
This is just one of the many ways to setup a stack frame!
Caller f():
Allocate space for the new stack frame, including space for parameters and the return address for the PC.
Pass parameters (i, j) onto the new stack frame.
Save the return address (PC) onto the new stack frame.
Transfer control to the callee: Jump to the function g() to hand over control from f() to g().
Callee g():
Save the old stack pointer onto the new stack frame.
As you can see, the teardown process only involves restoring the stack pointer and the return address. We do not reset or clear the values in the stack frame. This is why, in C, you can never assume a newly created variable has a specific values. Instead, it may contain leftover data (“garbage values”) from previously reused stack space.
Stack Overflow
Happens when the size of all the stack frame is over the default fixed size of the stack segment. Usually can be triggered easily without a proper implementation of Recurrence Function
Data Segment
This region stores global and static variables and constants used by the program, pre-defined before the execution of the program
Can be both read and write, allowing the Process (进程) to manipulate the data as needed