15 213 Introduction to Computer Systems Memory Management III Perils and pitfalls Oct 15 1998 Topics class16 ppt Review of C pointer references Memory related bugs Debugging versions of malloc Binary translation Garbage collection C operators Operators Associativity left to right right to left left to right left to right left to right left to right left to right left to right left to right left to right left to right left to right right to left right to left left to right type sizeof Note Unary and have higher precedence than binary forms class16 ppt 2 CS 213 F 98 C pointer declarations int p p is a pointer to int int p 13 p is an array 13 of pointer to int int p 13 p is an array 13 of pointer to int int p p is a pointer to a pointer to an int int p 13 p is a pointer to an array 13 of int int f f is a function returning a pointer to int int f f is a pointer to a function returning int int f 13 f is a function returning ptr to an array 13 of pointers to functions returning int int x 3 5 x is an array 3 of pointers to functions returning pointers to array 5 of ints class16 ppt 3 CS 213 F 98 Memory related bugs Dereferencing bad pointers Reading uninitialized memory Overwriting memory Referencing nonexistent variables Freeing blocks multiple times Referencing freed blocks Failing to free blocks class16 ppt 4 CS 213 F 98 Dereferencing bad pointers The classic scanf bug scanf d val class16 ppt 5 CS 213 F 98 Reading uninitialized memory Assuming that heap data is initialized to zero return y Ax int matvec int A int x int y malloc N sizeof int int i j for i 0 i N i for j 0 j N j y i A i j x j return y class16 ppt 6 CS 213 F 98 Overwriting memory Allocating the wrong sized object int p p malloc N sizeof int for i 0 i N i p i malloc M sizeof int class16 ppt 7 CS 213 F 98 Overwriting memory Off by one int p p malloc N sizeof int for i 0 i N i p i malloc M sizeof int class16 ppt 8 CS 213 F 98 Overwriting memory Off by one redux int i done 0 int s 4 while done if i 3 done 1 else s i 10 class16 ppt 9 CS 213 F 98 Overwriting memory Forgetting that strings end with 0 char t 7 char s 8 1234567 strcpy t s class16 ppt 10 CS 213 F 98 Overwriting memory Not checking the max string size char s 8 int i gets s class16 ppt reads 123456789 from stdin 11 CS 213 F 98 Overwriting memory Referencing a pointer instead of the object it points to int BinheapDelete int binheap int size int packet packet binheap 0 binheap 0 binheap size 1 size Heapify binheap size 0 return packet class16 ppt 12 CS 213 F 98 Overwriting memory Misunderstanding pointer arithmetic search int array int val while p p val p sizeof int class16 ppt 13 CS 213 F 98 Referencing nonexistent variables Forgetting that local variables disappear when a function returns int foo int val return val class16 ppt 14 CS 213 F 98 Freeing blocks multiple times Nasty x malloc N sizeof int manipulate x free x y malloc M sizeof int manipulate y free x class16 ppt 15 CS 213 F 98 Referencing freed blocks Evil x malloc N sizeof int manipulate x free x y malloc M sizeof int for i 0 i M i y i x i class16 ppt 16 CS 213 F 98 Failing to free blocks memory leaks slow long term killer foo int x malloc N sizeof int return class16 ppt 17 CS 213 F 98 Failing to free blocks memory leaks Freeing only part of a data structure typedef LISTP int val LISTP val foo LISTP listhead malloc sizeof LISTP LISTP listitem malloc sizeof LISTP listhead next listitem create and manipulate the rest of the list free listhead return class16 ppt 18 CS 213 F 98 Dealing with memory bugs Conventional debugger gdb good for finding bad pointer dereferences hard to detect the other memory bugs Debugging malloc CSRI UToronto malloc wrapper around conventional malloc detects memory bugs at malloc and free boundaries memory overwrites that corrupt heap structures some instances of freeing blocks multiple times memory leaks Cannot detect all memory bugs overwrites into the middle of allocated blocks freeing block twice that has been reallocated in the interim referencing freed blocks class16 ppt 19 CS 213 F 98 Dealing with memory bugs Binary translator Atom cont Purify powerful debugging and analysis technique rewrites text section of executable object file can detect all errors as debugging malloc can also check each individual reference at runtime bad pointers overwriting referencing outside of allocated block Garbage collection Boehm Weiser Conservative GC let the system free blocks instead of the programmer class16 ppt 20 CS 213 F 98 Debugging malloc mymalloc h define malloc size mymalloc size FILE LINE define free p myfree p FILE LINE Application program ifdef DEBUG include mymalloc h endif main p malloc 128 free p q malloc 32 class16 ppt 21 CS 213 F 98 Debugging malloc cont Debugging malloc library void mymalloc int size char file int line prologue code p malloc epilogue code return q void myfree void p char file int line prologue code free p epilogue code class16 ppt 22 CS 213 F 98 Debugging malloc cont block size block ID file name of allocation line number of allocation checksum of previous fields ptr to next allocated block ptr to prev allocated block guard bytes Block requested by application guard bytes class16 ppt 23 header application block footer CS 213 F 98 Debugging malloc cont mymalloc size p malloc size sizeof header sizeof footer add p to list of allocated blocks initialize application block to 0xdeadbeef return pointer to application block myfree p already free line 0xfefefefefefefefe checksum OK guard bytes OK free p sizeof hdr line 0xfefefefefefefefe class16 ppt 24 CS 213 F 98 Binary translator Converts an executable object file to an instrumented executable object file analysis file ptrace anal c original object file hello binary translator e g Atom instrumented object file hello ptrace instrumentation file ptrace inst c class16 ppt 25 CS 213 F 98 Atom example procedure call Instrumentation file ptrace inst c tracing include stdio h include instrument h Instrument Proc proc AddCallProto ProcTrace char for proc GetFirstProc proc NULL proc GetNextProc proc AddCallProc proc ProcBefore ProcTrace ProcName proc Analysis file ptrace anal c include stdio h void ProcTrace char name printf s n name class16 ppt 26 CS 213 F 98 Instrumenting hello world cc Wl r non shared hello c o hello rr atom hello rr ptrace inst c ptrace anal c o hello ptrace hello ptrace start init libc tis init libc locks init calloc malloc sbrk errno getpagesize sbrk tis mutex lock unlocked sbrk tis mutex …
View Full Document
Unlocking...