CS 208 s20 — Dynamic Memory Allocation: malloc and free

Table of Contents

1 Video

Here is a video lecture for the material outlined below. It covers CSPP section 9.9 through to 9.9.6 (p. 839–848). It contains sections on

  1. introduction (0:04)
  2. key questions (9:39)
  3. why dynamic memory allocation? (15:03)
  4. types of allocators (19:23)
  5. the malloc package (25:12)
  6. spreadsheet example (31:59)
  7. memory allocator requirements (37:43)
  8. memory allocator goals (41:04)
  9. fragmentation (45:27)
  10. allocator implementation issues (52:00)
  11. end notes (54:54)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=f2878a1d-4d88-4289-a37d-abc601175f06

2 Introduction

// static global data, size fixed at compile time, exists for the lifetime of the program
int array[1024]; 
void foo(int n) {
    // stack-allocated data, known lifetime (deallocated on return)
    int tmp;
    int local_array[n]; // some versions of C allow dynamically-sized stack allocation

    // dynamic (heap) data, size and lifetime known only at runtime
    int* dyn = (int*) malloc(n * sizeof(int));
    // good practices:
    //    sizeof makes code more portable
    //    void* is implicitly cast into any pointer type; explicit typecast will help you
    //      catch coding errors when pointer types don’t match
}

Two big questions we'll focus on for the next two weeks:

  1. how do we manage the scarce resource of physical memory while providing all processes as much virtual memory as they need?
    • implemented by the operating system kernel and hardware
  2. how do we handle malloc and free quickly and efficiently?
    • implemented by the C library

Lab 5 will task you with doing 2., so we will start there.

3 Dynamic Memory Allocation

We don't always know how much space we will need for certain data structures, etc. ahead of time. Hardcoded sizes everywhere can lead to problems and become a maintenance nightmare. Hence, we wany the ability to allocate memory as we go along (dynamically)

3.1 Type of Allocators

  • Allocator organizes heap as a collection of variable-sized blocks, which are either allocated or free
  • explicit allocators: require manual requests and frees (malloc package in C)
  • implicit allocators: unused blocks are automatically detected and freed (garbage collection)

3.1.1 malloc package

  • malloc does no initialization, use calloc to request zero-initialized memory
    • returns pointer to the beginning of allocated block, NULL indicates failed request
    • typically 16-byte aligned on x86-64
  • change the size of previously allocated block with realloc
  • underneath, allocation can use mmap and munmap or use the void *sbrk(intptr_t incr) function
    • sbrk grows or shrinks the heap by adding incr to the kernel's brk pointer, returns old value of brk

heapmap.png

  • free takes a pointer to the beginning of a block previously allocated by malloc, calloc, or realloc
    • marks that memory as free and available for future allocations
    • behavior undefined on other arguments, no indication of error

3.3 Allocator Goals and Requirements

3.3.1 Requirements

  • handling arbitrary request sequences: cannot make any assumptions about the sequencing of allocate and free requests
  • making immediate responses to requests: no reordering or batching of requests to improve performance
  • using only the heap: allocator's internal data structures must also be stored on the heap
  • aligning blocks: blocks need to meet alignment requirements for any type of data they might hold
  • not modifying allocated blocks: cannot modify or move blocks when they are allocated

3.3.2 Goals

  1. maximizing throughput: maximize requests per second
  2. maximizing memory utilization: use the greatest possible fraction of the space allocated for the heap. Peak utilization metric is the maximum such fraction achieved over the course of \(n\) requests.
  3. these are in tension: respond to a request faster vs respond with a better choice of block

3.4 Fragmenataion

  • internal fragmentation: allocated block is larger than the amount requested (due to minimum block size or alignment requirements)

vm_internal_frag.png

  • external fragmentation: when allocation/free pattern leaves "holes" between blocks
    • symptom: there is enough total free memory to satisfy a request, but no single free block is large enough
    • example: if final request on spreadsheet example were for 48 bytes
    • difficult to quantify as it depends on future requests

3.4.1 Quick Checks

Which of the following is NOT a source of internal fragmentation?1

  1. Placement policy (e.g., returning a larger block than requested)
  2. Padding for alignment purposes
  3. Pattern of future requests
  4. Memory used to maintain heap data structures

Which of the following statements is FALSE?2

  1. Temporary arrays should not be allocated on the heap
  2. malloc returns the address of a block that is filled with arbitrary data
  3. Memory utilization is affected by both internal and external fragmentation
  4. An allocation failure will cause your program to stop

3.5 Implementation Issues

  • free block organization: how to keep track of them
  • placement: which free block should we choose to fulfill a request
  • splitting: what do we do with the remainder of a free block after part of it is allocated
  • coalescing: what do we do when a block is freed

3.6 Implicit Free Lists

Teaser for the next topic: create an implicit list of heap blocks where the size of each block "points" to the start of the next block.

implicitblock.png

4 Homework

  1. CSPP practice problems 9.6 (p. 849)
  2. Lab 4 check-in post due 9pm tonight, May 25
  3. Lab 4 is due 9pm Wednesday, May 27
  4. The week 7 quiz is due 9pm Wednesday, May 27

Footnotes:

1

The pattern of future requests is not a source of internal fragmentation

2

The false statement is an allocation failure will cause your program to stop. When malloc fails, it doesn't crash, but returns NULL. It is the program's job to check this return value and act accordingly.