Marking the graph
Marking begins at known roots, records discovered objects and follows their references. Already processed objects need not be expanded indefinitely, allowing traversal of graphs containing cycles.
A component with no path from any root is not preserved simply because its objects reference each other. Unmarked candidate storage becomes reclaimable only after a safely completed marking phase.
Returning storage to allocation
Sweeping need not be one monolithic pause. Boehm’s collector can postpone some sweep work until allocation finds an appropriate free list empty.
Emacs describes different storage policies for different objects, including free lists for unused cons cells and coalescing free vector areas. Finding free storage still leaves allocation decisions about which holes can satisfy later requests.
Conservative recognition and space
A conservative collector can treat an address-like bit pattern as a possible pointer. This protects real references but may retain objects that the program no longer needs.
Mark and sweep specifies a reclamation method, not immediate return of all freed memory to the operating system or freedom from fragmentation. Implementations can add size-specific free lists, coalescing or object-specific compaction.