| |||||||||||||
Conservative Automatic Stack Size CheckConservative Automatic Stack Size CheckPosted Sep 8, 2005 8:27 UTC (Thu) by pkolloch (subscriber, #21709)In reply to: 4K stacks for everyone? by jwb Parent article: 4K stacks for everyone?
> The current proposal is sheer madness. The developers have NO IDEA what the maximum kernel stack usage is, and no way of determining it.
Then the current state is desperate as well: They don't have a clue if the current stack size limit is sufficient. Your dynamic stack size check would be a step into the right direction, but:
Most stack allocation should be easily statically determinable (with only small conservative overapproximations). Things like alloca (if there is a kernel equivalent) or any other means which change the stack size by a dynamically computed amount are more tricky. However, these should be avoided anyways if stack conservation has such a priority.
At least conceptionally, computing a call graph with conservative stack usage annotations should be fairly easy (using existing code in GCC). In the absense of recursion, one could easily determine the largest stack size in use. And again, if you value the stack size so much, you should not use recursion. (well, there might be valid use cases with a known maximal recursion depth of 3 or so which might be hard to check statically for machines and even if that is the case, you will need something slightly smarter than plain call graphs.)
Without such an automatic check, I pretty much agree with you.
[Disclaimer: I have basically no clue about the kernel source except of what I read occasionally on this page.]
(Log in to post comments)
Conservative Automatic Stack Size Check Posted Sep 8, 2005 9:12 UTC (Thu) by nix (subscriber, #2304) [Link] Most stack allocation should be easily statically determinableSome static determination is possible but not easy and not reliable (nor can it ever be reliable in the general case), and the error bars are large. See Olivier Hainque's paper in the GCC 2005 Summit proceedings for a pile of info on this. TBH I'd expect that kernel developers' own hunches would be as reliable.
Conservative Automatic Stack Size Check Posted Sep 8, 2005 9:53 UTC (Thu) by pkolloch (subscriber, #21709) [Link] After a moderate amount of web searching, I could find the abstract of thepresentation, but not the paper itself. Any pointers? BTW I did not say that it "easy" for the general case, but for the kernel without dynamic stack allocations and recursion. And OK, I was probably naive and will agree that it is probably also difficult for this special case ;) But both feasible and desirable. I hope Olivier Hainque will be successful in his quest and his work will be applied to the kernel. > TBH I'd expect that kernel developers' own hunches would be as reliable. And predict which variables are being stored in registers and which on the stack and considering all call paths? No, I think humans would miss a lot of special cases on that one. Additionally, not anyone would actually endeavor to do this for anything but some core functions. Am I wrong?
Conservative Automatic Stack Size Check Posted Sep 8, 2005 11:42 UTC (Thu) by farnz (guest, #17727) [Link] The paper starts on page 99 of the proceedings PDF. I've not found it split separately, and the PDF file is quite large (around 1.7MB).
Conservative Automatic Stack Size Check Posted Sep 9, 2005 1:58 UTC (Fri) by sethml (subscriber, #8471) [Link] Clever idea, but you missed a case that's hard to deal with: calling through function pointers. The kernel uses function pointers extensively, especially for device drivers. I suspect the case mentioned involving RAID involves calling through quite a few levels of function pointers. Figuring out the maximum possible call stack depth, even very conservatively, is probably pretty difficult, and the conservative answer is probably "infinite" because there are pathways you could construct that would recurse, even if that never happens in practice.
Conservative Automatic Stack Size Check Posted Sep 9, 2005 9:29 UTC (Fri) by pkolloch (subscriber, #21709) [Link] hmmm, you are right, I knew I had been naive, but I couldn't see what I missed.
Since from what I saw about the VFS, it's a shame that it is not expressed in an object oriented fashion. That could at least limit the amount of candidates. Maybe one could provide some annotations?
But I can well imagine that especially concepts as unionfs which wrap other file systems could in principle be wrapped around each other infinitely. You would have too make up some clever notation to tell the stack analyzer that this really isn't possible. (If there is even such a check ;) ) Or is it done in some clever fashion that the wrapped and the wrapper are not called in a nested fashion, but in some kind of chaining way for exactly the purpose of saving stack space?
[Disclaimer: Again, I have no real clue about the kernel source, so I hope my assumptions are not totally off the beat.]
Conservative Automatic Stack Size Check Posted Sep 10, 2005 21:03 UTC (Sat) by joern (subscriber, #22392) [Link] FYI: Function pointers are not that hard to follow. Seehttp://wh.fh-wedel.de/~joern/quality.pdf
|
|||||||||||||