CS 208 s21 — 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
- introduction, memory layout refresher (0:00)
- key questions (9:02)
- why dynamic memory allocation? (14:57)
- types of allocators (19:02)
- the malloc package (24:36)
- spreadsheet example (30:43)
- memory allocator requirements (36:28)
- memory allocator goals (39:49)
- fragmentation (44:04)
- allocator implementation issues (49:15)
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=7b62a760-8ea4-4ed7-8e75-ac59010dd3ae
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:
- 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
- how do we handle
malloc
andfree
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, usecalloc
to request zero-initialized memory- returns pointer to the beginning of allocated block,
NULL
indicates failed request - typically 16-byte aligned on x86-64
- returns pointer to the beginning of allocated block,
- change the size of previously allocated block with
realloc
- underneath, allocation can use
mmap
andmunmap
or use thevoid *sbrk(intptr_t incr)
functionsbrk
grows or shrinks the heap by addingincr
to the kernel'sbrk
pointer, returns old value ofbrk
free
takes a pointer to the beginning of a block previously allocated bymalloc
,calloc
, orrealloc
- marks that memory as free and available for future allocations
- behavior undefined on other arguments, no indication of error
3.2 Spreadsheet Example
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
- maximizing throughput: maximize requests per second
- 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.
- 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)
- 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.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