Week 7, session 2: Resource and memory management

class: title

5CCYB041
# OBJECT-ORIENTED PROGRAMMING
### Week 7, session 2
## Resource and memory management

---
name: memory_management
class: section

# Memory management

---

# Memory management

[Memory safety](https://www.memorysafety.org/docs/memory-safety/) is arguably
the biggest source of errors, bugs and security issues with C / C++
- ⇒ we need to understand memory, how to manage it, and the various kinds of
issues that we may encounter.

There are two broad categories of issues that we need to consider:
.columns[
.col[
- accessing invalid memory locations
  - [buffer overflow](https://en.wikipedia.org/wiki/Buffer_overflow)
  - using [stale references or pointers](https://en.wikipedia.org/wiki/Stale_pointer_bug) 
  - ...
]
.col[
- manual memory management
  - [memory leaks](https://www.geeksforgeeks.org/memory-leak-in-c-and-how-to-avoid-it/)
  - [double free](https://isab.run/paste/5aece618)
  - [dangling pointers](https://www.geeksforgeeks.org/dangling-pointers-in-cpp/)
  - ...
]
]

Modern C++ makes it is possible to produce code that is relatively safe
- without performing any manual memory management
- this is the approach taken on this course

But we are now at the stage where we need to cover this topic

---

# Memory management

On modern computers, every running process has access to its own region of
memory
- this is its [address space](https://en.wikipedia.org/wiki/Virtual_address_space)
- this region is isolated from other processes using [virtual memory](https://en.wikipedia.org/wiki/Virtual_memory)

[Memory can be allocated from two regions](https://www.geeksforgeeks.org/stack-vs-heap-memory-allocation/) of this address space:
- the stack
- the heap

---
name: stack_memory
class: section

# The stack

---

# The stack

Stack allocation takes place in the [function call stack](https://en.wikipedia.org/wiki/Call_stack)

The call stack is a data structure that holds the information about the
functions currently running in our process

.columns[
.col[
a [stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type%29) is a
  generic data structure widely used in computing

It is a way of storing items in a last-in first-out (LIFO) manner

Items are *pushed* on top of the stack, and then *popped* off the stack
]
.col[
![:scale 90%](/OOP/images/stack.png)
]
]

This structure matches the way functions work

---

## The function stack and stack frames

.columns[
.col[
- `main()` calls `run()`
  - the program *pushes* a new [stack frame](https://www.geeksforgeeks.org/stack-frame-in-computer-organization/) for `run()` onto the function call stack
  - the program then executes the code for `run()`
]
.col[
```
               │             │
               │             │
      run() → │             │
               │ main()      │
```
]
]

.columns[
.col[
- `run()` calls `load_pgm()`
  - the program *pushes* a new [stack frame](https://www.geeksforgeeks.org/stack-frame-in-computer-organization/) for `load_pgm()` onto the function call stack
  - the program then executes the code for `load_pgm()`
]
.col[
```
               │             │
 load_pgm() → │             │
               │ run()       │
               │ main()      │
```
]
]

.columns[
.col[
- `load_pgm()` completes and returns
  - the program *pops* the [stack frame](https://www.geeksforgeeks.org/stack-frame-in-computer-organization/) for `load_pgm()`
  - the program then resumes execution of the remaining code for `run()`
]
.col[
```
               │             │
               │ load_pgm()  │ → 
               │ run()       │
               │ main()      │
```
]
]

---

# The function stack and stack frames

Each item in the [function call stack](https://en.wikipedia.org/wiki/Call_stack) 
is called a [stack frame](https://www.geeksforgeeks.org/stack-frame-in-computer-organization/)

Every time a function is invoked, a new stack frame is pushed onto the call stack

The arguments and local variables needed for the function to run are stored in the stack frame
  *⇒ this is what is meant by 'stack allocation'*

The lifetime of the stack frame is tied to the lifetime of the function call
- as soon as the function returns, the stack frame is popped and its contents *destroyed*
- all local (function-scope) variables immediately go out of scope 
- ⇒ the compiler will insert code to ensure all their destructors are invoked at that point

Stack allocations are therefore very predictable and easy to manage
- memory is allocated on the stack when a local variable is declared
- memory is released when the function returns

⇒ on this course, we have so far *only* used stack allocations

---
name: recursion
class: section

# Recursive functions

---

# Recursive functions

It is important to understand that a stack frame is specific to an *invocation* of the function
- *not* the function itself

If that function is called again, that specific call will get its *own* fresh stack frame
- this allows functions to call themselves – these are called [recursive functions](https://www.geeksforgeeks.org/recursive-functions/)

--
 
This is best illustrated with a classic example: the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_sequence)
- In the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_sequence),
 each number is the sum of the two preceding numbers
 (starting with 0, 1):
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

This can be written as a recursive function:
$$
f(n) = f(n-1) + f(n-2)
$$

---

# Recursive functions: the Fibonacci sequence

We can therefore write this as:
```
int fib (int n) {
* return fib(n-1) + fib(n-2);
}
```
The part of a recursive function where the function calls itself is called the
*inductive step*

But what happens when the function eventually calls `fib(1)` or `fib(0)`?
- we need some condition that will prevent further recursion

```
int fib (int n) {
* if (n <= 1)
* return n;
 return fib(n-1) + fib(n-2);
}
```
- this is called the *anchor condition*

---
layout: true

## Recursive functions: the Fibonacci sequence

Let's track the state of the call stack when we call `fib(5)` to get the 
5th element:

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
 int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack2[
in `fib(4)`:   `n = 4`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
 int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack2[
in `fib(4)`:   `n = 4`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack2[
in `fib(4)`:   `n = 4`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack3[
in `fib(3)`:   `n = 3`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
 int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack2[
in `fib(4)`:   `n = 4`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack3[
in `fib(3)`:   `n = 3`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

---

.stack1[
in `fib(5)`:   `n = 5`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack2[
in `fib(4)`:   `n = 4`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack3[
in `fib(3)`:   `n = 3`   `a = ?`   `b = ?`   `return ?`

```
int fib (int n) {
 if (n <= 1)
 return n;
* int a = fib(n-1);
 int b = fib(n-2);
 return a + b;
}
```
]

.stack4[
in `fib(2)`:   `n = 2`   `a = ?`   `b = ?`   `return ?`