• static memory management: Local variables are automatically allocated and deallocated by the compiler
• dynamic memory management: Heap stores the data that lives indefinitely or until explicit deallocation
  • allocation: malloc, new
  • deallocation: free, delete
• malloc implementations
  • buddy allocator
  • bump allocator

Defragmenter

free = starting location of new heap;
for (each object o in heap) {
		if (o is not freed) {
				NewLocation(o) = free;
				free = free + size(o);
		}
}
for (each object o in heap) {
		if (o is not freed) {
				for (each reference o.r in o) {
						o.r = NewLocation(o.r);
				}
				copy o to NewLocation(r);
		}
}

• Problem with this approach: The local and global variables may have references to heap objects. We can not walk all stack addresses and registers and replace old heap addresses with the new ones. We need compiler support for that.
• Compiler can generate the set of all the objects that can be directly reached via local (or stack) and global variables without any pointer dereference is called the root set. At runtime, the defragmenter can look at these locations and update them with the new locations.

// add this to the above implementation
for (each reference r in the root set) {
		r = NewLocation(r);
}
delete NewLocation map.

• restrictions for having a defragmenter for c:
  • To generate the correct stack map, the compiler may use different stack locations for a and b, even though they can be shared. A and b are in if and else respectively.
  • A pointer can also be casted as an unsigned integer, the compiler can't track all pointers
  • We need to disallow potential unsafe typecasts and pointer arithmetic
  • Why disallow pointer arithmetic?
    • Application may create an out-of-bounds pointer
    • To insert bounds check before every memory access, the compiler needs to compute the address of the object header, which may be expensive if pointer arithmetic is allowed

Automatic memory management

• Garbage collection
• Reference counting
• Unique pointers

finding free objects

• mark and sweep gc

  • Mark phase
    • Mark all the objects that are reachable from the roots (local+ global variables)
    • Every object contains a reached-bit that is reserved for the garbage collector
    • the reached-bit of reachable objects are set in the mark phase
  • Sweep phase
    • free all the objects that were not reached during the mark phase
    • reset the reached-bit of reachable objects

• mark and compact

  • Because the GC runs infrequently, a bump allocator can be used for allocation, which is extremely fast.

  • Compact

    Free = starting location of the new heap
    for (each object o in the old heap) {
    		if (o is reached) {
    				NewLocation(o) = free;
    				free = free + sizeof(o);
    		}
    }
    // updating the references
    for (each object o in the old heap) {
    		if (o is reached) {
    				set the reached-bit of o to 0
    				for (each reference o.r in o) {
    						o.r = NewLocation(o.r);
    				}
    				copy o to NewLocation(o);
    		}
    }
    // updating the local or global references
    for (each reference r in the root set) {
    		r = NewLocation(r);
    }
    

• copying collector

  • Walk only reachable objects.
  • unscanned and free pointers
  • Spatial locality may not be preserved

• Concurrent garbage collection

  • Garbage collector runs in a separate thread
  • Garbage collection is done periodically Depending on
    • Memory consumption of the application
    • Last invocation of garbage collection
  • To solve the problem with the concurrent mark, we somehow need to track the writes to scanned objects
    • The GC threads can find out all the pages that are written during the concurrent mark phase using the dirty bit in the page tables
    • However, even if a non-pointer filed in the object is modified, the dirty bit will be set
    • Therefore, this scheme may work but could be expensive when the memory footprint of the application threads during the concurrent phase is high
  • Another option is to track writes to objects in the application threads during the compilation and add additional instrumentation to detect if a scanned object is being written
    • For example, in LLVM, the updates to pointer fields are done via store instructions in which the value operand is of pointer type

• barriers

  • unreached objects into scanned objects
  • Read barriers are expensive because reads are very frequent instead use write barriers
  • The write barrier is inserted when a reference is stored in a heap object from a local/global variable. E.g. write_barrier(&head2->next, tmp2);