Title: CSE 351 23au / LS20 Memory Allocation I

Q: Data whose characteristics (e.g., size or lifetime) can only be determined at runtime are known as ___
A: dynamically allocated data

Q: What section does dynamically allocated data live in the program memory?
A: The Heap

Q: In C, what is the function that requests a specific number of continuous bytes of uninitialized memory?
A: `malloc`
`void* malloc(size_t size);`
Malloc returns the pointer to the beginning of the allocated space (specifically the payload) using the void* type

Q: In C, what is the function that deallocates the entirety of a heap block given by the pointer returned from malloc?
A: `free`
`void free(void* p);`

Q: What is the name of the pointer that indicates the top of the heap?
A: brk pointer

Q: An allocator that only expects the programmer to be responsible for allocations and the allocator handles the deallocations (e.g., Java garbage collection) is known as an ___ allocator.
A: implicit

Q: An alloctor that expects the programmer to be responsible for both allocations and deallocations (e.g., C) is known as an ___ allocator.
A: explicit

Q: The goal for allocators to complete as many allocation and deallocation requests as possible per unit of time is known as ___
A: throughput

Q: For allocators, having good memory utilization would mean that the allocator is using the heap space ___ (efficiently / inefficiently)
A: efficiently

Q: The actual data in the heap that is being used by the system is defined as the ___
A: payload

Q: The size parameter in malloc(size) is equivalent to the size of the ___
A: payload

Q: Where can we find the information about the size of an allocated heap block?
A: The header

Q: True or false: The last bit of the header also stores an ‘is-allocated’ bit, where 1 indicates that the block is allocated and 0 indicates that the block isn’t
A: True

Q: Given the header `x` that is 64 bits wide, how can we encode the “is-allocated” `a` bit and the payload `size` into `x`?
x = size ___ a
A: x = size | a
or
x = size + a
Because the block size must be a multiple of 8, the last 3 bits of size in binary are all 0s.

Q: Given the header `x` that is 64 bits wide, how can we extract the “is-allocated” `a` bit from `x`?
a = x ___ 1
A: a = x & 1
We bitmask the last bit of `x` with 1 and the & operator which gives us the final bit of `x`

Q: Given the header `x` that is 64 bits wide, how can we extract the payload `size` bits from `x`?
size = x __ ~1 / size = x ___ ~2 (for signed integers)
A: size = x & ~1 / size = x & ~2 (for signed integers)
We bitmask the most significant 63 bits which will get rid of the final “is-allocated” bit.

Q: To keep track of the free blocks in the heap, the structure that traverses the heap blocks via arithmetic of the size of each block from the headers is known as the ___ free list
A: implicit

Q: To keep track of the free blocks in the heap, the structure that uses a linked list to traverse the heap blocks is known as the ___ free list
A: explicit