CS 240 Lab 11: Malloc Launch

Peter Mawhorter

Outline

  • Questions (buffers, malloc, etc.)
  • Dynamic Memory Allocation
  • GO

Write your questions on the boards.

  • Buffer overflows
  • Memory allocation on the heap
  • etc.

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/prev-free/this-free
    • ‘f’ = 0 = free
    • ‘a’ = 1 = allocated
  • Footer holds size (free blocks only)
(unused) ← heap origin (16-byte aligned)
80/a/f ← block header (off-by-8 from aligned)

← start of block data (16-byte aligned)


80 ← block footer
0/f/a ← heap footer

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

A = malloc(5)

(unused) ← heap origin
16/a/a ← block header

← A (aligned; 8 ≥ 5 bytes)
64/a/f ← block header






64 ← block footer
0/f/a ← heap footer

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

(unused) ← heap origin
16/a/a ← block header

← A
32/a/a ← block header

← B (24 ≥ 15 bytes)


32/a/f ← block header


32 ← block footer
0/f/a ← heap footer

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

(unused) ← heap origin
16/a/f ← block header
16
32/f/a ← block header

← B (24 ≥ 15 bytes)


32/a/f ← block header


32 ← block footer
0/f/a ← heap footer

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

(unused) ← heap origin
16/a/f ← block header
16
32/f/f ← block header (fragmented)


32
32/f/f ← block header


32 ← block footer
0/f/a ← heap footer

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

(unused) ← heap origin
80/a/f ← block header (consolidated)








80 ← block footer
0/f/a ← heap footer 

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

← A
16/a/a ← block header

← D
16/a/f ← block header
16
16/f/a ← block header

← C
16/a/f ← block header
16 ← block footer
0/f/a ← heap footer 

A = malloc(1);
B = malloc(1);
C = malloc(1);
free(B);
D = malloc(24);
(unused) ← heap origin
16/a/a ← block header

← A
16/a/f ← block header
16
16/f/a ← block header

← C
32/a/a ← block header

← D


0/a/a ← 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/a/a ← block header

← A
32/a/f ← block header


32 ← block footer
16/f/a ← block header

← C
16/a/f ← block header
16 ← block footer
0/f/a ← 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.)