Dynamic Memory Allocation
(i.e. how to manage allocation on the heap)

Recap:

The address space of a process

stack
...
...
heap
data (initialized,uninitialized, r/o)
program text

Mark the location of local variable, global variable, malloc-ed stuff

Who decides what variables goes where in the stack/data/heap: local/global
variables (compiler), malloced-stuff (dynamic memory allocator)

Dynamic memory allocator:
* allocates arbitary sized objects on the heap
* keeps track which parts of heap are free 

Dynamic memory allocation can be 
* explicit: C, C++
* implicit: Java, Go, Python, 

Draw a graph

applications
   | 
   | (void *) malloc(size_t), free(void *)
   |
dynamic memory allocator
   |
   | sbrk(int)
   |
   OS


Go back to the previous address space graph, and draw the effects of malloc, free, sbrk

Let's go at how to implement malloc/free

The setup:

Assumed behavior of applications:
* Can issue arbitary sequence of malloc (for arbitary sizes), free 
* The argument of free must be the return value of a previous malloc
* No double free

Requirements of allocator:
* Must allocate from free memory (correctness)
* Once allocated, cannot be moved.
* Must return (16-byte) aligned addresses

Performance goal:
* high throughput (how many mallocs/frees can be done per second)
* high utilization (fraction of allocated size / total heap size)

Design questions:
* How to keep track which bytes are free and which are not?
* Which of the free chunks to allocate?
* Free() only supplies a pointer, how to know its corresponding chunk size?

Naive strategy
* Works only with applications that malloc < K bytes
* Divide the heap of size M into M/K blocks
* Use a bitmap of M/K bits to represent the allocated/free status of each block

void *heap_start;
void *heap_end;
unsigned char bitmap[LARGE_CONSTANT];

void *
malloc(size_t size)
{
   assert(size < K);
   for (int i = 0; i < (heap_end-heap_start)/K; i++) {
       if bitmap_at_ith_position is zero {
          return heap_start + i * K;
       }
   }
}

void
free(void *p)
{
   int i = (p - heap_start) / K;
   set bitmap_at_ith_position to one
}

Main problems with naive strategy:
* only allow malloc of size < K!!


How to let a malloc of size > K to allocate more than one block?
Which design question must we address?

Ideas?
* hash table of address to size mapping? No plausible, since implementing a hash table 
requires dynamic memory management.
* store size in the allocated blocks?

Say malloc(2K), the straightforward strategy, allocate two consective blocks
Draw two blocks. Can I store size in the head? Can I store size in the tail?
Idea: allocate one more than needed? Store size information in the first block. 
Return address of the second block.

Draw picture

void *
malloc(size_t size)
{
   int n = size / K;
   for (int i = 0; i < (heap_end-heap_start)/K; i++) {
       if bitmap_at_[i..i+n] is zero {
          *(int *)(heap_start + i * k) = n;
          return heap_start + (i+1) * K;
       }
   }
}

void
free(void *p)
{
   int i = (p - heap_start) / K;
   int n = *(int *)(heap_start + (i-1) * K)
   set bitmap_at_[i..i+n] to zero
}

Issues with this approach?
* Utilization is bad: cannot make K too low, otherwise bitmap is too big. 
cannot make K too large, otherwise small allocation take up large space

Challenge:
Can we only keep track of consecutive free/allocated bytes?

ideas:
* a hash table of address to <size, free/allocated> of all chunks? 
* a linked list containing <address, size, free/allocated> tuples of all chunks?