Repository navigation
Address potential for stackoverflow in recursive function loops #3473
Description
In embedded systems, stackoverflows can be catastrophic if the processor does not support virtual memory which is true of many(most?) microcontrollers that micropython is meant to support.
I understand that it is not feasible to rewrite micropython to not need recursion, especially if stackoverflows are so infrequent. However, it is possible to at least put in code to catch a stackoverflow.
Using cflow, I've generated the complete call tree of micropython and found there is recursion all over the place.
If I'm interpreting the cflow output correctly, there are 15 distinct "recursion loops" and total of 35 functions that exist in those recursive loops.
I think the macro MP_STACK_CHECK() needs to be added to (at least) one function in each recursive loop.
For example, it should be added to mp_obj_new_exception_msg_varg.
1 +-abort_() <__attribute__ () void () at abort_.i:1659>
2 +-nlr_jump()
3 \-mp_obj_new_exception_msg() <mp_obj_t () at objexcept.i:2328>
4 \-mp_obj_new_exception_msg_varg() <mp_obj_t () at objexcept.i:2332> (R)
5 +-m_malloc_maybe() <void * () at malloc.i:2077>
6 | \-malloc()
7 +-mp_obj_new_tuple() <mp_obj_t () at objtuple.i:1889> (R)
8 | \-m_malloc() <void * () at malloc.i:2063> (R)
9 | +-malloc()
10 | \-m_malloc_fail() <void () at runtime.i:3697> (R)
11 | +-nlr_jump()
12 | \-mp_obj_new_exception_msg_varg() <mp_obj_t () at objexcept.i:2332> (recursive: see 4) [see 4]
13 +-strchr()
Activity
dhylands commentedon Dec 7, 2017
That's probably a bad example. This is what I'd refer to as limited recursion. If the memory allocation fails, then it will raise an MemoryError using a pre-allocated object. This will only recurse once. It won't recurse any deeper than what it is already.
adritium commentedon Dec 7, 2017
Actually it’s the perfect example for the reason you implicitly pointed out:
cflowdoes not look at the logic leading to the recursive calls but only if it’s possible for a given call tree to exist.I fully expect that logically, most of the recursive loops
cflowrevealed cannot happen but are there unit tests to prove that? If it’s possible for those tests to be written, then let’s do that.But even if it is possible to write those tests, given that there are so few functions that exist in the recursive loops and even fewer that would need to be instrumented with
MP_STACK_CHECK(), why not add it?dpgeorge commentedon Dec 7, 2017
@adritium thanks for looking into these issues, but I think this one has already been addressed in a comprehensive way in 96fd80d. There's no longer a call to mp_obj_new_tuple() so I think you are analysing an old version of uPy.
adritium commentedon Dec 7, 2017
@dpgeorge I just used it as an example. My larger point is that all the recursion must be somehow addressed in a systematic method.
From your comment, it seems that you skimmed over what I said above:
I guess if we had tests disproving those recursive loops, we wouldn’t need to also add
MP_STACK_CHECK()to the recursive calls. At least until we have those tests, we should add theMP_STACK_CHECK()checks.dpgeorge commentedon Dec 7, 2017
Ok, I see, but it makes it harder to discuss things when using examples that are no longer relevant.
As you've pointed out, one can use
MP_STACK_CHECK()to guard against stack overflow, and that has been done it as many places as was found to date.In the case of creating new exceptions there was some code snippet that triggered a stack overflow in
mp_obj_new_exception_msg_varg()and so that's why it was fixed. And note that it's not possible to write a test to prove that something never happens. Instead one must use analysis to show it can't happen (if possible). And if analysis can't show that it won't happen then either 1) write a test to trigger the case and then fix it; 2) put a runtime check in (egMP_STACK_CHECK) to allow to tighten up the (static) analysis.If you can find a recursive loop that is not protected by
MP_STACK_CHECKthen please do point it out and try to write a test that triggers a stack overflow. That would be very helpful.adritium commentedon Dec 7, 2017
Even if a test cannot be written to trigger overflow, ALL possible paths exposed by
cflowshould be instrumented with MP_STACK_CHECK() … even if upon examination of the code logic recursion is impossible.Using this approach, you’re guaranteed to catch all overflows during runtime. Also, you don’t have to rely on manual proofs that a certain recursive path is impossible.
This is the safest way to deal with the recursive loops.
dpgeorge commentedon Jun 23, 2022
Closing due to inactivity.