CS 240 Lab 11: Malloc Launch

Peter Mawhorter

Outline

  • Dynamic Memory Allocation

Dynamic Memory Allocation

malloc and free

From the user’s perspective:

  • malloc requests some memory.
    • Returns a pointer to the start of a block that’s big enough to hold the requested number of bytes.
    • May return NULL if there’s not enough memory available.
    • Memory is reserved for us indefinitely.
  • free gives back allocated memory.
    • Specify the block using the pointer malloc gave you.
    • Afterwards, the memory may immediately be overwritten and used by someone else (or not).

malloc and free

From the system’s perspective:

  • malloc requests some memory.
    • We need to find some unallocated memory to give out.
    • We need to mark it as allocated.
  • free gives back allocated memory.
    • We need to mark the block as free again so it can be used by a future malloc call
    • We need to merge free blocks to avoid fragmentation.

Tracking and Alignment

  • We allocate memory in “blocks.” At minimum, each block needs to know:
    1. Am I allocated, or free?
    2. How big am I?
  • Certain instructions like movaps require alignment:
    • Move Aligned Packed Single-precision floating-point values
    • “When [using memory], the operand must be aligned [on a 16-byte boundary] or a general-protection exception will be generated.”
    • It’s simplest (for users) to just guarantee that all pointers returned by malloc are 16-byte aligned.

Heap example

  • Each row is 8 bytes
  • Headers show size &
    status bits (prev-free/this-free)
    • 0 = free
    • 1 = allocated
  • Footer holds size (free blocks only)
(unused) ← heap origin (16-byte aligned)
80 | 0b10 ← block header (off-by-8 from aligned)

← start of block data (16-byte aligned)
  … ← 48 bytes (6 slots) not shown

80 ← block footer
0 | 0b01 ← heap footer

(Alignment means last 4 bits are always 0; don’t need extra room for flags)

A = malloc(5)

(unused) ← heap origin
16 | 0b11 ← block header

← A (aligned; 8 ≥ 5 bytes)
64 | 0b10 ← block header






64 ← block footer
0 | 0b01 ← heap footer

A = malloc(5); B = malloc(15)

(unused) ← heap origin
16 | 0b11 ← block header

← A
32 | 0b11 ← block header

← B (24 ≥ 15 bytes)


32 | 0b10 ← block header


32 ← block footer
0 | 0b01 ← heap footer

A = malloc(5); B = malloc(15); free(A);

(unused) ← heap origin
16 | 0b10 ← block header
16
32 | 0b01 ← block header

← B (24 ≥ 15 bytes)


32 | 0b10 ← block header


32 ← block footer
0 | 0b01 ← heap footer

A = malloc(5); B = malloc(15); free(A); free(B);

(unused) ← heap origin
16 | 0b10 ← block header
16
32 | 0b00 ← block header (fragmented)


32
32 | 0b00 ← block header


32 ← block footer
0 | 0b01 ← heap footer

A = malloc(5); B = malloc(15); free(A); free(B);

(unused) ← heap origin
80 | 0b10 ← block header (consolidated)








80 ← block footer
0 | 0b01 ← heap footer 

A = malloc(5);
B = malloc(15);
C = malloc(8);
free(B);
D = malloc(8);
(unused) ← heap origin
16 | 0b11 ← block header

← A
16 | 0b11 ← block header

← D
16 | 0b10 ← block header
16
16 | 0b01 ← block header

← C
16 | 0b10 ← block header
16 ← block footer
0 | 0b01 ← heap footer 

A = malloc(1);
B = malloc(1);
C = malloc(1);
free(B);
D = malloc(24);
(unused) ← heap origin
16 | 0b11 ← block header

← A
16 | 0b10 ← block header
16
16 | 0b01 ← block header

← C
32 | 0b10 ← block header

← D


0 | 0b11 ← heap footer 

A = malloc(1);
B = malloc(9);
C = malloc(1);
free(B);
D = malloc(25);

We’ve only allocated 2/80 bytes, but we cannot allocate the requested 25 bytes :(

(unused) ← heap origin
16 | 0b11 ← block header

← A
32 | 0b10 ← block header


32 ← block footer
16 | 0b01 ← block header

← C
16 | 0b10 ← block header
16 ← block footer
0 | 0b01 ← heap footer

Malloc Launch

Group yourself:

  • Group A: My malloc partner and I are in this lab.
  • Group B: My malloc partner is not in this lab.
  • Group C: I want to find a partner.
  • Group D: I’d be open to working with a partner, or alone.
  • Group E: I definitely want to work alone.

Get Started

  • Open the “Preparatory Exercises” part of the malloc assignment page
  • Open the Malloc Checkpoint assignment on Gradescope, which is how you will submit your answers.
    • Work through this assignment for this lab (to be turned in before next week’s lab if you don’t finish today).
    • For Q3 and Q4, use the board to make heap drawings so that you can answer the Gradescope questions.
    • There will be additional heap drawings graded in lab next week.

Extra malloc Reference

Extra malloc explanations

(Prof. Herbst’s slides from a previous semester)