<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 12/17/16 9:55 PM, 杨至轩(Zhixuan Yang)
wrote:<br>
</div>
<blockquote
cite="mid:29aa8c86.14c68.1590fdacb85.Coremail.zxyang@pku.edu.cn"
type="cite">
<meta http-equiv="Context-Type" content="text/html; charset=UTF-8">
Dear Josh,
<blockquote><br>
> If I understand correctly, if you find memory leak, you
want to find the corresponding call(s) to malloc() that
allocated the memory object, correct? Can you more completely
explain what you are trying to accomplish?</blockquote>
<div><br>
</div>
<div>Thanks for your reply. In my task, I use data flow analysis
to locate a program point where a malloc must be leaked (by must
leaked, I mean (a) it must be allocated, (b) must not be free()d
and (c) never used in the future). And I want to fix this leak
by finding a pointer must point to that malloc(). So I want to
perform a must-alias query.</div>
</blockquote>
<br>
When you say "must be allocated," you mean it must have been
allocated via a call to a heap allocator (e.g., malloc(), calloc(),
etc), correct?<br>
<br>
Technically, global variables and stack variables also allocated;
they just don't allocate heap memory.<br>
<br>
Also, are you performing intra-procedural or inter-procedural
data-flow analysis?<br>
<br>
<blockquote
cite="mid:29aa8c86.14c68.1590fdacb85.Coremail.zxyang@pku.edu.cn"
type="cite">
<div><br>
</div>
<blockquote>
<div>>However, DSA is a unification-based analysis, so I
would think that the accuracy of a must-alias feature would be
pretty weak. Also, DSA loses precision as it performs more
inter-procedural analysis (the local analysi>s will be the
most precise but will have many Incomplete DSNodes; the
Bottom-Up and Top-Down propagate information up and down the
call graph but will cause further DSNode merging). </div>
</blockquote>
<div><br>
</div>
Thanks for your clarification. I agree with you. Even if we
implemented a MustAlias interface in DSA, it will be too weak.<br>
<blockquote>
<div><br>
</div>
<div>>It may be that you will need a more accurate points-to
analysis algorithm for your work.</div>
</blockquote>
<br>
<div>In fact, my task can be solved in a simpler (while less
elegant) way. If I want to find pointers must-alias with a
malloc() call, I can create a new variable storing the result
returned by the malloc() when it is called. <br>
</div>
</blockquote>
<br>
This is essentially a fat pointer; you're extending the pointer that
you're checking to contain the base address of the memory object to
which it points as well as the memory address to which it points.
Since you're not adding the base address to the pointer but passing
it around with the pointer, you must transform the code so that the
base address "follows" the pointer value wherever it goes (into
memory, passed to functions as arguments, etc).<br>
<br>
Fat pointers are relatively easy for local variables but are much
more of a pain for pointers that are stored to/read from memory or
passed to functions as arguments. I'm also of the opinion that
every fat pointer approach suffers from some degree of compatibility
problems with third-party library code (the infamous "external code"
problem).<br>
<br>
If you're going to transform the program, I would recommend that you
use SAFECode's new BBAC feature to track the base address. BBAC has
a run-time library which can take a pointer to a memory object and
calculate, in constant time, the first address of the memory object
into which the pointer is pointing. You could use this to find the
base address of the memory object so that you can pass it to the
free() function. As BBAC is a referent object approach, it doesn't
suffer from the compatibility problems that fat pointer approaches
suffer.<br>
<br>
My Google Summer of Code student, Zhengyang Liu, worked on BBAC this
summer and created an updated and robust implementation of it that
you could modify for your project. If you're interested, please
email me so that I can put you in touch with him.<br>
<br>
Regards,<br>
<br>
John Criswell<br>
<br>
<blockquote
cite="mid:29aa8c86.14c68.1590fdacb85.Coremail.zxyang@pku.edu.cn"
type="cite">
<div>Thanks for your help.</div>
<div><br>
</div>
<div>Best regards, Zhixuan Yang</div>
</blockquote>
<br>
<p><br>
</p>
<pre class="moz-signature" cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a class="moz-txt-link-freetext" href="http://www.cs.rochester.edu/u/criswell">http://www.cs.rochester.edu/u/criswell</a></pre>
</body>
</html>