Idea:

• use free list, as in malloc+free, but do free automatically
• mark all reachable objects
• insert all unreachable objects into free list

How to determine reachable objects?

• start from the set of roots (e.g. live local and global variables)
• follow all reference variables in allocated objects
  • compiler generates information that indicates which fields and variables are of reference type
• mark reachable objects using depth-first search

What are roots?

• global reference variables
• reference variables on stack
• registers

Example

• inserting into a functional tree twice
• not using middle tree
• performing mark and sweep