Precise Detection of Memory Leaks Jonas Maebe, Michiel Ronsse, Koen De

Precise Detection of Memory Leaks Jonas Maebe, Michiel Ronsse, Koen De Bosschere Dammit, Jim. I’m an Eiffel Tower, not a Star Trek logo 25 May 2004 WODA2004

Memory leaks What – Allocating memory without releasing later Why bad – Reduce performance – May cause crashes How to solve – Find out where exactly memory is leaked

Overview Kinds of memory leaks Existing tools Our solution False positives Evaluation Future Work

Physical Leaks What – Last pointer to a block of memory is destroyed Causes – Pointer overwrite – Free block containing pointer – Stack shrinks

Physical Leaks (2) Important information: – Allocation site of block – Location where last pointer is lost – Assignment location of last pointer

Logical Leaks What – Reachable pointer available, but block never freed Important information – Allocation site of block – Where are these pointers?

Existing Tools Most: where was leaked block allocated – Pro: simple, very fast – Con: may not be enough information Insure : also where last pointer lost – Pro: more information for physical leaks – Con: not more info for logical leaks, source code instrumentation, no description of technique, expensive

Our solution Keep track of allocated blocks Use dynamic instrumentation1 to detect all references to memory blocks (DIOTA) Physical leak: reference count of block becomes zero Logical leak: unfreed blocks which are not physical leaks 1 Principle of “dynamic instrumentation” covered by EU software patent AT&T

DIOTA principle Original program Generated code (clone) To configure: Use “backends” Here: Memory instrumentation Replace calls to memory heap management functions Stack (shared) DIOTA Push target Jmp DIOTA

Overview Leak Detection References Leaks Memory Blocks LeakInfo1 BlockInfo1 BlockInfo4 Tree: Random and sequential access First element (stack) Hashtable: Only random access necessary

Allocations References Memory Blocks Leaks BlockInfo1 void *a malloc(32); Reserved blocks: Intercept memory management functions Have reference count

References References Memory Blocks BlockInfo1 void *a malloc(32); Reference Detection: Results of stores Begin addresses of blocks Leaks

Leaks References Memory Blocks Leaks Blockinfo1 LeakInfo1 void *a malloc(32); a NULL;

Stale References References Two possibilities: Memory Blocks !!! Search all references and destroy them BlockInfo1 Make sure we can detect that block has been freed void *a malloc(32); free(a); a NULL; Leaks

Stale References (2) All BlockInfo’s get a unique ID References get copy of ID When freeing a block, give it a new ID BlockInfo’s come from dedicated pool Can be reused as soon as block is freed Direct pointer to BlockInfo from Reference

False Positives References NeedMemory way to detect Blocksthat leak info is out of date Leaks Blockinfo1 L1 void *a malloc(32); a 2*sizeof(void*); . void *b a-2*sizeof(void*); .

False Positives (2) Every memory block gets a usecount usecount is increased at stores current usecount is copied to leakinfo Delay reporting of leaks: – BlockID’s don’t match: block freed – usecounts don’t match: block still addressed later

Other issues C : pointers to BlockStart sizeof(void*) False negatives (random value ptr) Circular structures

Evaluation Slowdown: 250 - 350 times in real world programs Example bug found using implementation: 1 for(int i 0;i exp 1;i ) { set map . new terms find terms(.); // fix memory leak found by DIOTA value clear(result- arr[i].d); 5 value clear(result- arr[i].x.n); result- arr[i] translate one term(.); }

Future work Report information about logical memory leaks Detect usage of stale pointers Speed up implementation: – “Post-write” memory instrumentation – Stack change interception

Questions?