11Dynamic Memory ManagementProfessor Jennifer Rexfordhttp://www.cs.princeton.edu/~jrex2Goals of Today’s Lecture• Dynamic memory managemento Garbage collection by the run-time system (Java)o Manual deallocation by the programmer (C, C++)• Challenges of manual deallocationo Arbitrary request sizes in an arbitrary ordero Complex evolution of heap as a program runs• Design decisions for the “K&R” implementationo Circular linked-list of free blocks with a “first fit” allocationo Coalescing of adjacent blocks to create larger blocks23Memory Layout: Heapchar* string = “hello”;int iSize;char* f(){char* p;scanf(“%d”, &iSize);p = malloc(iSize);return p;}TextBSSStackHeapNeeded when required memory size is not known before the program runsRoDataData4Allocating & Deallocating Memory• Dynamically allocating memoryo Programmer explicitly requests space in memoryo Space is allocated dynamically on the heapo E.g., using “malloc” in C, and “new” in Java• Dynamically deallocating memoryo Must reclaim or recycle memory that is never used againo To avoid (eventually) running out of memory• “Garbage”o Allocated block in heap that will not be accessed again o Can be reclaimed for later use by the program35Option #1: Garbage Collection• Run-time system does garbage collection (Java)o Automatically determines objects that can’t be accessedo And then reclaims the resources used by these objectsObject x = new Foo();Object y = new Bar();x = new Quux();if (x.check_something()) {x.do_something(y);}System.exit(0);Object Foo()is never used again!6Challenges of Garbage Collection• Detecting the garbage is not always easyo “if (complex_function(y)) x = Quux();”o Run-time system cannot collect all of the garbage• Detecting the garbage introduces overheado Keeping track of references to objects (e.g., counter)o Scanning through accessible objects to identify garbageo Sometimes walking through a large amount of memory• Cleaning the garbage leads to bursty delayso E.g., periodic scans of the objects to hunt for garbageo Leading to unpredictable “freeze” of the running programo Very problematic for real-time applicationso … though good run-time systems avoid long freezes47Option #2: Manual Deallocation• Programmer deallocates the memory (C and C++)o Manually determines which objects can’t be accessedo And then explicitly returns the resources to the heapo E.g., using “free” in C or “delete” in C++• Advantageso Lower overheado No unexpected “pauses”o More efficient use of memory• Disadvantageso More complex for the programmero Subtle memory-related bugso Security vulnerabilities in the (buggy) code8Manual Deallocation Can Lead to Bugs• Dangling pointerso Programmer frees a region of memory o … but still has a pointer to ito Dereferencing pointer reads or writes nonsense valuesint main(void) {char *p;p = malloc(10);…free(p);…putchar(*p);}May print nonsense character.59Manual Deallocation Can Lead to Bugs• Memory leako Programmer neglects to free unused region of memoryo So, the space can never be allocated againo Eventually may consume all of the available memoryvoid f(void) {char *s;s = malloc(50);return;}int main(void) {while (1) f();return 0;}Eventually, malloc() returns NULL10Manual Deallocation Can Lead to Bugs• Double freeo Programmer mistakenly frees a region more than onceo Leading to corruption of the heap data structureo … or premature destruction of a different objectint main(void) {char *p, *q;p = malloc(10);…free(p);q = malloc(10);free(p);…}Might free the space allocated to q!611Challenges for Malloc and Free• Malloc() may ask for an arbitrary number of bytes• Memory may be allocated & freed in different order• Cannot reorder requests to improve performancechar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);12Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1713Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p214Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p3815Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p316Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p3p4917Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p2p3p418Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p5, p2p3p41019Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p5, p2p3p420Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void *ptr);00xffffffffStack}HeapHeapchar *p1 = malloc(3);char *p2 = malloc(1);char *p3 = malloc(4);free(p2);char *p4 = malloc(6);free(p3);char *p5 = malloc(2);free(p1);free(p4);free(p5);p1p5, p2p3p41121Heap: Dynamic Memory#include <stdlib.h>void *malloc(size_t size);void free(void
View Full Document
Unlocking...