CP2003 Lecture Notes - Dynamic Storage

These lecture notes are based on chapter 3 in ``Programming Language Concepts and Paradigms'' by David Watt.

Heap vs. Stack

• visual depiction of run-time storage
  
• heap
  • freelist - list of free space
  • on allocation - memory manager finds space and marks it as used changing freelist
  • on deallocation - memory manager marks space as free changing freelist
  • memory fragmentation - memory fragments into small blocks over lifetime of program
  • garbage collection - coalesce fragments, possibly moving objects (must be careful of pointers when moving!)
• stack
  • clean and efficient support for nested functions and recursion
  • central concept is stack frame (also called activation record), includes
    • visual depiction of frame
      
    • parameters
    • return address - where to begin execution when function exits
    • dynamic link - pointer to caller's stack frame
    • static link - pointer to lexical parent (for nested functions)
    • return value - where to put the return value
    • local variables
    • local work space - for temporary storage of results
  • function call - push stack frame
  • function exit - pop stack frame
  • visual depiction of stack calls
    
• example

  int x;                 /* static storage */
  
  void main() {
     int y;              /* dynamic stack storage */
     char *str;          /* dynamic stack storage */
    
     str = malloc(100);  /* allocates 100 bytes of dynamic heap storage */
  
     y = foo(23);
     free(str);          /* deallocates 100 bytes of dynamic heap storage */
  }                      /* y and str deallocated as stack frame is popped */
  
  int foo(int z) {       /* z is dynamic stack storage */
     char ch[100];     /* ch is dynamic stack storage */
  
     if (z == 23) foo(7);
     
     return 3;           /* z and ch are deallocated as stack frame is popped,
                            3 put on top of stack  */
  }

• at the start of the program
  
• after the first call to foo
  
• after the second call to foo
  

Dead Objects

• storage objects in stack storage die (are deallocated) when the stack frame is popped.
• storage objects in heap storage must be explicitly killed in C, but in other languages are implicitly killed when they are no longer referenced.

    /* C example */
    char *str;
    str = malloc(100);  /* allocate 100 byte storage object in heap storage 
                           put the pointer to it into str */
    free(str);          /* kill the allocated storage object */

• the freelist is a list of free areas in heap storage. When an object is allocated, the freelist is searched to find a big enough free area, and then the list is updated to mark that space as no longer free. When an object is killed, the space for the object is added to the freelist. Garbage collection coalesces the heap storage areas pointed to by the freelist.
• dangling reference - pointer to a dead object

    /* C example */
    char *str;
    str = malloc(100);  /* allocate 100 byte storage object in heap storage 
                           put the pointer to it into str */
    free(str);          /* kill the allocated storage object */
    *str = 'h';         /* str is now a dangling reference! attempt to put
                           the character 'h' to what is pointed at by str,
                           but str points to a dead object */

Persistent Variables

A persistent varible is a variable that lives beyond the execution of a program.

   { Pascal Example }
   program curt(a_file_name)  { a_file_name is a persistent file variable! }
     ....
   end.

But why should files be different than other types of variables? This is a violation of the type completeness principle. Research is underway to add persistence to programming languages.