1 1 Dynamic Memory Management!2 Goals of this Lecture!• Help you learn about:"• Dynamic memory management techniques"• Design decisions for the “K&R” heap manager implementation"2 3 Part 1:!What do malloc() and free() do?"4 Memory Layout: Heap!char* string = "hello"; int iSize; char* f() { char* p; scanf("%d", &iSize); p = malloc(iSize); return p; } Text BSS Stack Heap Needed when required memory size is not known before the program runs"RoData Data3 5 Allocating & Deallocating Memory!• Dynamically allocating memory"• Programmer explicitly requests space in memory"• Space is allocated dynamically on the heap"• E.g., using “malloc” in C, and “new” in Java"• Dynamically deallocating memory"• Must reclaim or recycle memory that is never used again"• To avoid (eventually) running out of memory"• “Garbage”"• Allocated block in heap that will not be accessed again "• Can be reclaimed for later use by the program"6 Option #1: Garbage Collection!• Run-time system does garbage collection (Java)"• Automatically determines objects that canʼt be accessed"• And then reclaims the resources used by these objects"Object 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!4 7 Challenges of Garbage Collection!• Detecting the garbage is not always easy"• “if (complex_function(y)) x = new Quux();”"• Run-time system cannot collect all of the garbage"• Detecting the garbage introduces overhead"• Keeping track of references to objects (e.g., counter)"• Scanning through accessible objects to identify garbage"• Sometimes walking through a large amount of memory"• Cleaning the garbage leads to bursty delays"• E.g., periodic scans of the objects to hunt for garbage"• Leading to unpredictable “freeze” of the running program"• Very problematic for real-time applications"• … though good run-time systems avoid long freezes"8 Option #2: Manual Deallocation!• Programmer deallocates the memory (C and C++)"• Manually determines which objects canʼt be accessed"• And then explicitly returns the resources to the heap"• E.g., using “free” in C or “delete” in C++"• Advantages"• Lower overhead"• No unexpected “pauses” "• More efficient use of memory"• Disadvantages"• More complex for the programmer"• Subtle memory-related bugs"• Security vulnerabilities in the (buggy) code"5 9 Manual Deallocation Can Lead to Bugs!• Dangling pointers"• Programmer frees a region of memory "• … but still has a pointer to it"• Dereferencing pointer reads or writes nonsense values"int main(void) { char *p; p = malloc(10); … free(p); … putchar(*p); } May print nonsense character. 10 Manual Deallocation Can Lead to Bugs!• Memory leak"• Programmer neglects to free unused region of memory"• So, the space can never be allocated again"• Eventually may consume all of the available memory"void f(void) { char *s; s = malloc(50); return; } int main(void) { while (1) f(); return 0; } Eventually, malloc() returns NULL6 11 Manual Deallocation Can Lead to Bugs!• Double free"• Programmer mistakenly frees a region more than once"• Leading to corruption of the heap data structure"• … or premature destruction of a different object"int main(void) { char *p, *q; p = malloc(10); … free(p); q = malloc(10); free(p); … } Might free the space allocated to q! 12 malloc() and free() Challenges!• malloc() may ask for arbitrary number of bytes"• Memory may be allocated & freed in different order"• Cannot reorder requests to improve performance"char *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);7 13 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 14 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p28 15 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p2 p3 16 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p2 p39 17 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p2 p3 p4 18 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p2 p3 p410 19 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p5, p2 p3 p4 20 Heap: Dynamic Memory! #include <stdlib.h> void *malloc(size_t size); void free(void *ptr); 0 0xffffffff Stack }Heap Heap char *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); p1 p5, p2 p3 p411 21 Heap: Dynamic Memory! #include <stdlib.h>
View Full Document
Unlocking...