<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Roboto;
panose-1:0 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.gmail-hoenzb
{mso-style-name:gmail-hoenzb;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Note that LLVM can already emit per-function stack-size information in the assembler/object file. Offhand I don't remember where it happens but should not
be hard to track down. You should certainly leverage that, however.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">--paulr<o:p></o:p></span></p>
<p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></a></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Andrew Kelley via llvm-dev<br>
<b>Sent:</b> Wednesday, July 11, 2018 4:37 PM<br>
<b>To:</b> Annie Cherkaev<br>
<b>Cc:</b> LLVM Dev<br>
<b>Subject:</b> Re: [llvm-dev] static stack depth analysis tool<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Hi Annie,<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">The Zig frontend is highly interested in this tool.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">One of the big outstanding issues left to solve [1] is statically determining stack upper bound, as you have described.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Currently, recursion is allowed the same as it is in C; however, the plan is:<o:p></o:p></p>
</div>
<p class="MsoNormal"> * Detect cycles in the call graph, and emit compile errors at the cycle entry point.<o:p></o:p></p>
</div>
<p class="MsoNormal"> * Users can break the cycle by using @newStackCall [2] to call a function using a heap-allocated buffer. This works today; however we need to be able to determine how much to allocate on the heap using the tools you describe.<o:p></o:p></p>
</div>
<p class="MsoNormal"> * Inline assembly, interrupts, function pointers, and external functions must be annotated as you have described so that the static analysis can complete the stack depth computation.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"> * The implementation of spawnThread will determine the worst case stack upper bound for the entry point of the thread to know how much memory to allocate for the thread's stack.<o:p></o:p></p>
</div>
<p class="MsoNormal">Let me know if I can help. I will watch this LLVM issue with great interest.<o:p></o:p></p>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><br>
[1]: <a href="https://github.com/ziglang/zig/issues/157">https://github.com/ziglang/zig/issues/157</a><br>
[2]: <a href="https://ziglang.org/documentation/master/#newStackCall">https://ziglang.org/documentation/master/#newStackCall</a><o:p></o:p></p>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Wed, Jul 11, 2018 at 12:32 PM, Annie Cherkaev via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
<div>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Hello llvm-dev!</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">We are currently building a tool using LLVM which statically computes the worst-case stack depth for programs whose call-graphs are statically constrained.
While this task is undecidable for general programs, we specifically plan to use it to analyze all entry points into Zircon’s kernel and the vDSO.
</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Currently, without such a tool, the best option for allocating kernel memory in Zircon is taking a best guess of a conservative overestimate of the memory
required. This is problematic, however, because allocating too much memory wastes valuable, highly limited RAM, and allocating too little memory can result in stack overflows, which lead to catastrophic system failure. This tool will eliminate the guesswork
by reporting the smallest amount of memory that is sufficient for all possible executions within the kernel.
</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">We would appreciate feedback on our approach, and would like to hear if anyone else has use-cases for such a tool. Below are some implementation details,
followed by some Zircon-specific details.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif""> Implementation details:</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Arial","sans-serif"">This tool will perform the stack depth analysis by extracting the call graph and the stack frame sizes from LLVM in two late passes, scheduled just before
codegen. A modulePass will write a dictionary of function names to the list of called functions, and a machineFunctionPass will write a dictionary of function names to their stack sizes. A script can then use these dictionaries to annotate the call graph with
the stack sizes by matching up function names, and use this annotated call graph to find the execution path with the largest stack</span><span style="font-size:11.0pt;font-family:"Roboto","serif"">.
</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Backends: We plan to support the x86-64 and aarch64 architectures; adding other architectures should be straight-forward.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Fancy stacks: We plan to support using SafeStack & ShadowCallStack.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Hand-written assembly: The Zircon codebase contains a nontrivial amount of hand-written assembly which uses stack space. We will manually audit the stack
usage of assembly code, and provide it to the analysis in a lookup table. </span>
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Indirect Function Calls & Recursion: We hope to not run into too many call graph complications in our codebase, refactor those which we do run into, and
add this tool into the build system to enforce that future code is amenable to this analysis. We currently don’t plan on implementing any additional analysis which LLVM does not already have.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Testing: We’ll validate the correctness of the tool through unit testing, end-to-end testing and ideally also fuzz testing. We can set up fuzz testing by
instrumenting the source code to dynamically monitor the stack size-- for instance by inlining assembly to report the stack pointer-- and comparing that result to the value the tool computes statically. While this wouldn’t validate that the tool is reporting
stack sizes precisely, it would give us a way to automatically check that the true stack frame size reported by the dynamic check (which is the stack size for *some* execution path) is no larger than the worst-case stack size reported by the static tool.
</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif""> Zircon-specific details:</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Interrupts:
</span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">An executing thread can be temporarily halted by an interrupt, which will execute code on the stack of the thread it paused. This means to ensure we find
what the true worst-case stack is, we need to model the case where an interrupt occurs while the function is at its deepest stack depth. Some interrupts can interrupt other interrupts, therefore to accurately model worst-case stack depth we need to build a
model of how interrupts may execute in x86-64 and aarch64, and treat them as additional entry points which are called by every leaf function.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Motivation for analyzing stack usage in the vDSO:
</span><o:p></o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">In Zircon, syscalls are exposed through the vDSO (virtual Dynamic Shared Object). The vDSO is an interface which is like a shared library object, except
it is provided by the OS instead of existing as a literal file. If a process has permission to make syscalls then the vDSO is mapped into its memory space, and it can dynamically link against syscalls the same way it would any other shared library object.
The vDSO requires a certain amount of stack space to safely complete any syscall, and that amount is part of the system’s ABI contract with user code. Currently, however, that amount is unknown, undocumented and unenforced; this tool will allow us to analyze
the amount of stack space currently implemented syscalls use, document the amount that will be contractually required by the ABI, and enforce that future syscalls do not exceed that amount.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Please let us know if you have any comments or suggestions about the implementation, and if you have a project that could benefit from such a tool.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif"">Thanks!</span><o:p></o:p></p>
<p class="MsoNormal"><span class="gmail-hoenzb"><span style="color:#888888"><o:p> </o:p></span></span></p>
<p style="margin:0in;margin-bottom:.0001pt"><span style="font-size:11.0pt;font-family:"Roboto","serif";color:#888888">Annie Cherkaev</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>