Address Space and Dynamic Memory
CSci4061: Introduction to Operating Systems
September 30, 2021
Computer Science & Engineering, University of Minnesota
1
Last lecture
Scheduling
• Goals
• Two styles
• Three basic algorithms
• Hybrid scheduling in real systems
2
Address Space
Address Spaces
• Address spaces are virtualized by OS
• Another example of virtualization
• It is the range of addresses that a process may use
• The legal address space is the range of addresses that a process may use right
now
3
Memory layout of a process address space (32-bit case)
Fig from Prof.
4
User-kernel split
• An address space is split into kernel space and user space • Kernel space
• The mode bit is set to privileged; can see all of memory • user program, arguments, etc.
• user memory is like a big data structure to the kernel
• Shared by all processes
• User space
• The mode bit is off; can only see its memory in user space • The code cannot directly access kernel space
• Each process has its own user space
5
Enforcing kernel-memory isolation
• The processor checks every reference to make sure the address is legal
• Mode bit available in the cs register of CPU for the control
6
Many address spaces in an OS
Nearly all modern operating systems support the abstraction of multiple address spaces
7
Processes and Address Spaces
• Each process has its own address space
• Process A’s memory references (reads and writes) are interpreted within
process A’s address space only
Q: Can Process A read a word from Process B’s address space?
Q: Can Process A read a word from kernel memory used by Process A?
Q: Can Process A read a word from the kernel memory that is used by Process B?
8
Dynamic Memory Management
Which regions are dynamic?
9
Stack
• Contains local variables within a function • Allocated contiguously within the stack • Deallocated on function return
void foo() {
int i;
char s;
long j; }
• Q: How are they allocated?
• Q: What would be their default values?
• Q: How about “int arr[i]” where i is a variable? • Q: Can I change i from int to long at runtime?
10
More questions about stack
• What is the size of stack?
• ulimit -a
• How does a stack restore upon function return?
• What if I have a function that has thousands of recursions?
11
Heap
• Contains objects that are created dynamically in the program • Q: Why aren’t dynamic objects allocated on the stack?
• Some languages provide automatic memory management
• Objects on heap are automatically allocated and deallocated (garbage collector)
• E.g.: Java
• Other languages put the burden on the programmer
• E.g.: C, C++
• Can be a disaster
12
Dynamic Memory: Accessed through Pointers
• Pointer: Address to a memory buffer
char *ptr = (char *) malloc(10*sizeof(char));
• Q: Where does ptr point to? • Q: What is &ptr?
• Q: What is sizeof(ptr)?
13
Stack vs. Heap Memory
void foo() {
char arr[10];
char *ptr;
ptr = (char *) malloc(10*sizeof(char)); arr[0]=‘a’;
ptr[0]=‘b’;
}
What differences do the memory objects have?
14
Stack vs. Heap Memory
void foo() {
char arr[10];
char *ptr;
ptr = (char *) malloc(10*sizeof(char)); arr[0]=‘a’;
ptr[0]=‘b’;
}
What differences do the memory objects have? After foo returns, arr is freed, but ptr is not
14
Discussion: when to use stack or heap?
15
Discussion: when to use stack or heap?
Use heap:
• Large memory to allocate • Dynamic size
• Shared globally
Use stack:
• Small memory
• Performance sensitive • Frequently accessed
15
Functions for Dynamic Memory Allocation/Deallocation
void *malloc(size_t size);
• Takes the number of bytes to allocate
• Returns a pointer to the beginning of the allocated memory region • Takes pointer to a memory buffer
• Frees the buffer pointed to by the ptr
void free(void *ptr);
16
How do malloc and free work?
• Functions implemented by a library
• Library maintains a large chunk of memory • malloc:
• Returns a block of memory from this chunk of requested size
• Records how much memory was returned
• free:
• Returns freed block of memory to a free list
• Determines how much memory to free based on information recorded at time
of malloc
17
How do malloc and free work?
p1=malloc(10);
p2=malloc(5);
p3=malloc(15);
free(p2);
Warning: fragmented!
18
Memory Problems
• Segmentation faults:
• Illegal memory accesses
• Memory Leaks:
• Allocated memory that is no longer accessible to the process
19
Segmentation Faults
• OS sends a signal called SIGSEGV to the process
• Typically results in termination of the offending process
• Indicates that the process has tried an illegal access of a memory address • What does illegal access mean?
• Process has accessed an address that is not in its mapped address space—How likely is it for a random access?
• Process has accessed an address for which it does not have access permission (e.g.: read-only, kernel memory, etc.)
20
Common Illegal Memory Accesses
• Accessing NULL pointers—have you initialized a pointer?
• Bad memory address (typically 0)
• Trying to access a pointer without doing malloc • The pointer is initialized to a junk value
• Treating a junk/random value as a pointer
• Memory corruption
• Legal pointers get corrupted such as by overflow
• This is something critical we need to discuss about
21
Heap Memory Corruption Causes
• Dangling pointers
• Bad pointer arithmetic/buffer overflow • Bad malloc/free usage
• Use-after-free
• Effects of memory corruption:
• May occur much later in the execution
• May remain hidden and appear only under certain circumstances • Pretty dangerous if exploited by attackers
22
Dangling Pointers—heap
• Pointers pointing to deallocated/freed memory
char *p1=malloc(10);
char *p2=p1;
do_something();
free(p1);
…
p2[0]=‘a’;
Q: What are the values of p1 and p2 after free(p1)?
23
Dangling Pointers—stack
• Pointers pointing to deallocated/freed memory
char *foo() {
char p1 = ‘a’; do_something(); return(&p1);
}
24
Bad Pointer Arithmetic/Buffer Overflow
• Overwrite beyond the bounds of a buffer
• Could corrupt another variable
char A[10];
char c=’z’;
int i;
for (i=0; i<11; i++)
A[i]='a';
25
Bad malloc/free usage—double free
• Freeing a pointer twice
• Undefined effect
• Might free up another pointer allocated later
char *p1=malloc(10);
do_something();
free(p1);
char *p2=malloc(10);
free(p1);
26
Use-after-free
A free heap object is further used
char *p1=malloc(10); free(p1);
// Use 1
char c = p1[0];
// Use 2
p1[1] = a;
struct mystruct *s = (struct mystruct *)p1; // Use 3
s->fp();
27
Discussion: how bad can use-after-free be?
char *p1=malloc(10); free(p1);
// Use 1
char c = p1[0];
// Use 2
p1[1] = a;
struct mystruct *s = (struct mystruct *)p1; // Use 3
s->fp();
28
Avoiding heap memory errors
29
Avoiding heap memory errors
• Be aware of these errors
• No double free, no use-after-free
• Do not overwrite/read
• Use AddressSanitizer to test the code
29
Memory Leaks
• Memory allocated on the heap that is no longer accessible to the process • What happens if foo() is called 1000 times?
• What happens if foo() is called a million times?
void foo() {
char *p1 = malloc(1000); do_something();
return;
}
30
Memory Leak: Pointer Reassignment
void foo() {
char *p1 = malloc(10);
char *p2 = malloc(1000);
p2 = p1;
do_something();
free(p1);
}
• What happens to memory allocated to p2?
• What happens if foo() is called a million times?
31
Memory Leak: Nested Pointers
• What happens to b->ptr?
• What happens if foo() is called a million times?
struct bar {char *ptr;}; void foo() {
struct bar *b = malloc(sizeof(struct bar)); b->ptr = malloc(1000);
do_something();
free(b);
}
32
Memory Leaks: Conditions
• Using malloc without free
• Allocated memory is never freed up
• Never returned to free list, cannot be reclaimed
• Lost pointer reference
• No way to refer to the buffer
• Cannot access it directly
• Causes of lost pointer reference
• Pointer going out of scope
• Pointer reassignment
• Freeing base pointer of indirect reference
33
Memory Leaks: Problems
• Performance slowdown
• May lead to more swapping, page faults
• Worst case scenario: Out of memory!
• Run out of virtual address space
• Run out of swap space
• Silent bug: Typically difficult bug to catch
• No crashes
• Imperceptible slowdown
• Cumulative effect over time
34
Avoiding Memory Leaks
• Some languages provide garbage collection
• Automatically reclaim memory that is no longer accessible to the process
• E.g.: Java, Lisp
• In C, programmer has to do the cleanup
• Always free memory you don’t need anymore
• Always free structs recursively (free fields first, then the struct) • Be careful with pointer reassignments
• Use LeakSanitizer
35
Summary
• Address space
• kernel-user split
• Heap vs. Stack
• Memory allocation: malloc and free • Memory Problems
• Segmentation Faults • Memory Leaks
36
Quiz
• A _______ is used to determine if a process is privileged or not.
• The _______ stores the local variables and the return address of a function • The _______ stores the objects that are created using malloc
• In Unix, Which signal is sent when a process tries to illegally access a memory
address ?
37
Next lecture
• System I/O—last lecture in the OS-basics section • Reading: Robbins 1.4.3, 4.1-4.3, 4.6-4.7
• Project 1 due next week
• Project 2 in one week
38
References
[1] http://courses.cs.washington.edu/courses/cse410/99au/lectures/Lecture-11- 03/Lecture-11-03.ppt
[2] http://www-users.cselabs.umn.edu/classes/Spring- 2018/csci4061/notes/dyn_mem_mgmt.pdf
39