Gentoo Forums
Gentoo Forums
Gentoo Forums
Quick Search: in
Clarification of "Avoid heap memory allocation"
View unanswered posts
View posts from last 24 hours

Goto page Previous  1, 2  
Reply to topic    Gentoo Forums Forum Index Portage & Programming
View previous topic :: View next topic  
Author Message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Tue Mar 24, 2020 2:43 am    Post subject: Reply with quote

Well if you write you code with no recursion -- never call itself again whether a called function or not -- then it's only the number of calls. The stack depth is indeed limited and cannot grow past a certain value, and this isn't really a big problem anymore unless you allocate a lot of stack space per frame. Using recursion, however, can lead to mathematical proofs of functional correctness - but this would have data dependent stack depth.

So recursion is good or bad? Functional proofs versus unknown maximum stack depth? I still don't think stack depth is really an issue for user mode programs as they can always allocate new stack pages. However for things that use kernel calls, stacks may be limited. Perhaps this is the specific issue that's the problem?
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Tue Mar 24, 2020 4:17 am    Post subject: Reply with quote

User programs cannot always allocate new stack pages. User stacks are not nearly as limited as kernel stacks, but they are still limited. Address space is finite, and especially on embedded processors, memory layout may offer little room for expansion. I think the guidelines care mainly about proving that the program can never encounter an exceptional condition, such as stack exhaustion. Any program for which that cannot be proved, whether because the program is actually unsafe or just because it is too complicated for our existing formal methods to prove it to be safe, is presumed undesirable.
Back to top
View user's profile Send private message
krinn
Watchman
Watchman


Joined: 02 May 2003
Posts: 7362

PostPosted: Tue Mar 24, 2020 5:28 am    Post subject: Reply with quote

I think it should be more simple : as long as your recursion has error handling exit, on stack oom, your program should end recurse and unloop all the nests, leading to a "nice" ending
I don't see any security issue there, only a bad design if not properly implemented ; because if your program crash, the stack will be cleared without your help
and the real issue there is that doing this with heap, would mean you should unroll and unallocated everytime what each recursions would had allocate, something that might not be doable with a crash and poor implementation, which could be worst of the worst with huge memory leak on heap.

of course someone could recurse to fill all the stack, and then freeze its state like that to make other programs out of stack memory, but those are recommandations for people who don't want be an ass or doing a secure program, not for bad ass that want hack a system.
Back to top
View user's profile Send private message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Tue Mar 24, 2020 3:12 pm    Post subject: Reply with quote

Okay this is is another issue I ran across during experimentation.

The kernel, to prevent memory abuse, has a ulimit on stack size which will stop user programs from allocating unusual amounts of stack pages. Currently my machines limits stack to 8MB which is quite a few 4K pages, and as superuser can increase this further if needed.

So, the kernel/compiler instrumentation will kill (apparently with SIGSEGV) when we go past 8MB allocated. So unless this ulimit is raised we can't use stack for large amounts of storage and must resort to heap if more memory is needed.

The whole premise, barring ulimits, is that memory is memory and programs should be free to use either as needed without causing unintended/unproveable behavior... Just that stack use is restrictive as it should only accessible in that frame and lower... (then there's also the problem of statics allocated ...)
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Wed Mar 25, 2020 2:05 am    Post subject: Reply with quote

Most programs don't handle stack exhaustion well, as eccerr0r discovered. Since exhaustion could occur any time the program allocates another stack page, good centralized handling is difficult. Even worse, the usual ways of handling a fault require some free stack space, so unless the program has prearranged for a separate signal stack, the kernel will be forced to kill the program because there is nowhere to put the state required to handle the fault. As a result, the rules go for the simplified approach of trying to prove the program never exhausts its stack, so that there is no need to have a recovery handler. Remember, these are rules for software where failure has such severe consequences that spending additional months of developer time to stamp out every last fault is considered a good trade.

As a curious aside, one place where stack usage is a worse choice involves functions that have large stack frames, but brief lifetimes. If the compiler is aggressive about inlining those functions, it may effectively promote the large stack frame into a much longer lived function, depriving other functions of needed stack space. A corresponding function that used the heap would still free the memory when the programmer intended, so inlining it would not extend the lifetime of the allocation.
Back to top
View user's profile Send private message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Wed Mar 25, 2020 3:01 am    Post subject: Reply with quote

Again I don't see how stack depth can be checked during build time, it can only be done at runtime. What is a specific program that tells exactly how deep stack goes at build time -- formally determining depth -- without requiring profiling which implies runtime as runtime calculations is heuristic as it depends on the dataset. Are there any languages that can do formal verification of depth?

It is indeed strange that GCC behaved very poorly dealing with stack ulimit exhaustion, granted instrumentation to prevent hitting a ulimit (versus a fixed limit) would require calculations during each call, which is additional overhead (there *must* be a gcc option to add these if needed?) However all these problems go away and becomes no different than running out of heap memory when you just set an unlimited stack. Just like being able to check for failed mallocs, if you know you have huge stack frames you can getrusage/getrlimit stack memory before making a call to stave off these errors, albeit this is not atomic like malloc. Then again malloc will always return success on allocate-on-use kernels like Linux so there's a race there too.

Anyway, I don't think using stack as storage is a reasonable solution to not using heap if your software needs a lot of dynamic memory. If you use heap, make sure you keep track of all your pointers...

BTW if anyone wants to play,
Code:
void useless(int depth) {
int stackjunk[1024*512]; /* this would be about 512K*sizeof(int) + sizeof(int) + regular stack frame */
if (depth > 0) useless(depth-1);
}
void main(void) {
useless(2); /* change the 2 to play with this */
}

When compiling, don't optimize with -O2, gcc will optimize all the code away...
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Wed Mar 25, 2020 4:47 am    Post subject: Reply with quote

As I said previously, for a subset of programs, determining stack depth without running them is easy. Construct a call graph representing which functions can call which other functions. This can be done statically, even for data-dependent branching, because you construct a pessimistic graph assuming that the program will exercise every branch. For each individual function, you know its stack requirement. Find the path through the graph that causes the greatest sum, and you know the maximum depth required.

This technique fails for programs where recursion prevents building a call graph, and for programs where a function uses alloca or similar to allocate a dynamically sized stack buffer. Such programs can be rejected as "potentially unsafe" without further analysis.

GCC doesn't need to handle ulimit, because ulimit is just the most immediate way to fail a stack allocation. For a sufficiently greedy program, address space exhaustion will eventually force the kernel to deny a stack expansion, even in the absence of ulimit or any kernel policies restricting stack growth. A stack cannot grow forever. Eventually it will encounter some other memory region, and then stack growth must be denied because that region is likely not relocatable, and growing the stack into the region will cause memory corruption. GCC does need to handle probing the stack so the kernel can detect increasing stack depth requirements. However, unless the program was written to anticipate stack exhaustion and do something unusual to cope with it, there is nothing that can be done if the kernel declines to extend the stack. Most programs are not prepared to unwind themselves suddenly.
Back to top
View user's profile Send private message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Wed Mar 25, 2020 8:06 am    Post subject: Reply with quote

See, this is where the conflict belongs: Recursive programs are provable correct, but stack usage cannot be known at compile time using static program analysis. The code sequence above, suppose if I used *argv to change recursion depth, what tool is available to calculate depth, or are you simply saying programs like this should automatically be rejected even though its computation is provably correct by induction? And is there any languages that will tell you this which was the initial query, or will it depend on someone inspecting that this is a recursive program that has potentially unbounded stack growth?

And as long as there are free pages (and not hit ulimit), why can't stack keep growing? If the program hits a page fault when it runs out of the current stack page, why couldn't the kernel map another page at the next virtual address below the previous page. Of course you don't want to start the stack at VA 0x3fff so assume that's not the case, and ASLR may not allow the program to start very high, but it still can provide quite a bit of space. Also for the case of not using any heap, we should have plenty of VA's to grow the stack downwards...

Of course if we actually do run out of VA's the program is dead no matter what, but that's no different than malloc failing because the kernel ran out of address space for the new brk either... Neither case really is a software bug, your computer just doesn't have the resources to give you what you want.
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Thu Mar 26, 2020 3:04 am    Post subject: Reply with quote

eccerr0r wrote:
Recursive programs are provable correct, but stack usage cannot be known at compile time using static program analysis.
I think these statements are in conflict. For any given function, stack usage can be known at compile time (assuming the function does not use alloca or similar). If you can prove that the program does not enter an unbounded recursion, then you can create a control flow graph where every state in the program is a node and every state transition is an edge. Two nodes lead to the same successor node only if the program is in exactly the same state on completion of the respective edges. This may lead to some otherwise seemingly redundant nodes, but is necessary to support the next step. Once you have the graph, annotate the node representing program initialization with the stack used by the entrypoint function. For every state directly reachable from that node, annotate it with the sum of its predecessor node and the usage new to that state. By definition each node will deserve exactly one annotated value. If it deserves more than one, that is an indication the graph was not split correctly. Iteratively annotate the graph until every node has a usage amount. When finished, find the node with the largest amount. That is your proven worst case stack usage.

For the purpose of these guidelines, one of the aspects of correctness is that the analysis will prove that the program cannot run out of resources even for the worst case inputs. If the analysis cannot prove that, whether because the analysis tool is too simplistic or because the program is unbounded, then the program is rejected. These guidelines are meant for use on programs where mistakes have serious real world consequences, so incorrectly rejecting safe programs is preferable to accepting potentially unsafe programs.
eccerr0r wrote:
The code sequence above, suppose if I used *argv to change recursion depth, what tool is available to calculate depth, or are you simply saying programs like this should automatically be rejected even though its computation is provably correct by induction?
The program has variable behavior depending on the input, but it is still bounded. We can prove the maximum value you could pass (based on the maximum representable in the data type you used to store the count of steps remaining), trace the stack usage for that worst case scenario, and judge whether that usage is too expensive for the program to be safe.
eccerr0r wrote:
And is there any languages that will tell you this which was the initial query, or will it depend on someone inspecting that this is a recursive program that has potentially unbounded stack growth?
I expect such languages exist, or could be created with modifications to existing tools. gcc already has the ability to warn about stack frames that exceed a certain size, and linkers have long had the ability to construct control graphs as a side effect of symbol resolution. A good solver tool would be more precise than the linker's algorithm, since it should trace branching to avoid warning about impossible errors. (For example, suppose that the program checks that your input is less than 10. If it is, it recurses that number of times. If the input is not less than 10, the program prints an error and quits. A good solver would recognize that an input of 1 million does not cause a recursion of 1 million because the input test would prevent even starting recursion on that input.)
eccerr0r wrote:
And as long as there are free pages (and not hit ulimit), why can't stack keep growing?
You can keep growing, until you run out of memory or contiguous unused virtual address space.
eccerr0r wrote:
Also for the case of not using any heap, we should have plenty of VA's to grow the stack downwards...
Maybe. Omitting the heap helps, except that the rules didn't exactly say "no heap." They said "Do not use dynamic memory allocation after initialization." From that, heap allocations during program startup, before the program declares "initialization complete; ready for duty" are allowed, and could use up quite a bit of heap. Even if there is no appreciable heap usage, there is still the virtual address space lost to dynamic shared objects. If ASLR is in use, then almost by definition, these objects will not be efficiently packed together, but scattered throughout the address space. If the program is meant to run on an embedded system, address space may be 2**32, or even smaller. Someone might even do something crazy and try to run this hypothetical program in the same address space as the system kernel, in which case part of the address space is consumed by memory-mapped hardware, by DMA reservations, etc.
eccerr0r wrote:
Of course if we actually do run out of VA's the program is dead no matter what, but that's no different than malloc failing because the kernel ran out of address space for the new brk either... Neither case really is a software bug, your computer just doesn't have the resources to give you what you want.
True, but if the analysis program could examine the program and definitively state "Your program will, in the worst case, require X GB of memory," and your hardware team commits that the standard production hardware will have at least X GB of memory, then you have guaranteed that the program cannot run out of resources. If your analysis program cannot establish the worst case memory usage (or the solver is so simplistic that its reported worst case is actually far worse than the true worst case), then your production hardware may not have enough resources to guarantee that the program never runs out. These guidelines contemplate a program where "program crashed due to insufficient free resources" has catastrophic consequences (say, a self-driving car that goes braindead while driving down the highway), so the definition of bug covers every reasonably preventable crash.
Back to top
View user's profile Send private message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Thu Mar 26, 2020 9:43 am    Post subject: Reply with quote

So what I'm getting now is:

- you can get individual stack frame sizes at compile time (trivial, usually; this should be reported in the assembler output)
- and my main point: there is no such language/program today that actually checks your maximum theoretical stack depth (total of all call depths and their frame sizes per call) statically at build time and won't error out at build time due to a possible stack exhaustion error.

If you have to depend on knowing your program by manual analysis and/or runtime profiling with random or predicted worst case inputs, this isn't what I was wondering about. Skipping the manual analysis to guarantee nobody in the project wrote a deep recursive function was the intent of the query.

There is no question running out of resources is bad, but that's a different, more general issue. It's even worse if you're running on a PIC microcontroller (stack stored on processor limited to like 8 calls) and IIRC the 6502 (stack limited to 256 bytes), and thus call depth is limited by processor resources rather than memory - unlike the 8080 and onwards cpus that you can completely fill your RAM with stack frames if you wanted to...

Incidentally, I think that recursive programs usually are slow and resource hogs if you can't do tail recursion or something like that where the compiler can convert to a faster, more efficient iterative solution -- do recursion during theoretical design, convert to iterative for production!
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Fri Mar 27, 2020 1:11 am    Post subject: Reply with quote

I am not aware of a tool which can statically tell you the worst case stack usage. That does not mean one does not exist. Depending on the accuracy desired with regard to branch pruning, a simplistic version of such a tool might not be hard to write. A simplistic version could be one that does not do detailed flow analysis, and instead believes that any call into a function will necessarily exercise every call in that function. Flow analysis and value propagation are more work.
Back to top
View user's profile Send private message
szatox
Veteran
Veteran


Joined: 27 Aug 2013
Posts: 1846

PostPosted: Fri Mar 27, 2020 10:22 am    Post subject: Reply with quote

Quote:
A simplistic version could be one that does not do detailed flow analysis, and instead believes that any call into a function will necessarily exercise every call in that function
How would that _not_ report an overflow for _any_ recursive function?
Back to top
View user's profile Send private message
eccerr0r
Watchman
Watchman


Joined: 01 Jul 2004
Posts: 7414
Location: almost Mile High in the USA

PostPosted: Sat Mar 28, 2020 12:21 am    Post subject: Reply with quote

I think the recursive functions I've written in the past I believe cannot be tail recursed (directed and double link graph DFS/BFS routines) depend on the dataset to determine stack depth. I did make sure the routines check for dataset loops, and IMHO this is the key piece of code that needs to be present to prevent infinite recursion. I don't know how one could write code to determine the correctness of the loop detection hence thinking this may be a subset of the halting problem mentioned earlier.

However these are still dependent on the data to determine ultimate and maximum stack depth even if the data does not contain loops - suppose the dataset contained a linear directed graph of arbitrary length, which would generate the worst case scenario...

Luckily it was written in perl and the perl call stack is probably mostly stored in heap memory anyway :)
_________________
Intel Core i7 2700K@ 4.1GHz/HD3000 graphics/8GB DDR3/180GB SSD
What am I supposed watching?
Back to top
View user's profile Send private message
Hu
Moderator
Moderator


Joined: 06 Mar 2007
Posts: 14921

PostPosted: Sat Mar 28, 2020 12:32 am    Post subject: Reply with quote

It would. If you want to use recursive functions, you need a smarter solver. If you don't need to use recursive functions, a fairly simplistic solver may be sufficient.
Back to top
View user's profile Send private message
Display posts from previous:   
Reply to topic    Gentoo Forums Forum Index Portage & Programming All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum