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)


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 | 0xb10 ← 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 | 0b11 ← 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

(The document does not contain full instructions; just the questions you need to answer. Read the full instructions and then answer the questions in the document.)