$9.9.$Dynamic Memory Allocation

1.Heap Struction

2.The malloc and free Functions

  Programs allocate blocks from the heap by calling the malloc function:

#include <stdlib.h>

void *malloc(size_t size);
/* Returns: pointer to allocated block if OK, NULL on error */

  The malloc function returns a pointer to a block of memory of at least size bytes.

• If malloc encounters a problem (e.g., the program requests a block of memory that is larger than the available virtual memory), then it returns NULL and sets errno.

  We can use sbrk function to manage the heap size:

#include <unistd.h>

void *sbrk(intptr_t incr);

/* Returns: old brk pointer on success, −1 on error */

  The sbrk function grows or shrinks the heap by adding incr to the kernel's brk pointer. If successful, it returns the old value of brk, otherwise it returns −1 and sets errno to ENOMEM.

  We can use the free function to free allocated heap blocks:

#include <stdlib.h>
void free(void *ptr);

/* Returns: nothing */

• The ptr argument must point to the beginning of an allocated block that was obtained from malloc, calloc, or realloc.

3.Fragementation

• Internal fragmentation: It occurs when an allocated block is larger than the payload.

• External fragmentation: It occurs when there is enough aggregate free memory to satisfy an allocate request, but no single free block is large enough to handle the request.

4.Basic Implementation Model

  The simplest imaginable allocator would organize the heap as a large array of bytes and a pointer p that initially points to the first byte of the array.

• To allocate size bytes, malloc would save the current value of p on the stack, increment p by size, and return the old value of p to the caller.

5.Implicit Free Lists

  Any practical allocator needs some data structure that allows it to distinguish block boundaries and to distinguish between allocated and free blocks:

• A block consists of a one-word header, the payload, and possibly some additional padding.

• The header encodes the block size(including the header and any padding) as well as whether the block is allocated or free.

• When malloc is called, the application request the payload. The payload is followed by a chunk of unused padding that can be any size.

• The free blocks are linked implicitly by the size fields in the headers. The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap.

---

• The system's alignment requirement imposes a minimum block size on the allocator. For example, if we assume a double-word alignment requirement, then the size of each block must be a multiple of two words(8 bytes).

6.Placing Allocated Blocks

• Next fit starts each search where the previous search left off for a suitable free list.

• It's motivated by the idea that if we found a fit in some free block the last time, there is a good chance that we will find a fit the next time in the remainder of the block.

7. Getting Additional Heap Memory

• The allocator asks the kernel for additional heap memory by calling the sbrk function

7.Coalescing with Boundary Tags

• The header of the current block points to the header of the next block, which can be checked to determine if the next block is free.

• Similarly, we can add a footer (the boundary tag) at the end of each block to check the previous block: