Re: setrecursionlimit
On Wed, 18 May 2016 09:19:25 -0700, Ned Batchelder wrote: > Is there a way to know how large the C stack can grow, Yes. For the main thread, getrlimit(RLIMIT_STACK). For other threads, pthread_attr_getstacksize(). > and how much it will grow for each Python function call? No. Depending upon the interpreter implementation, the stack might not grow at all in the case where a function written in Python calls another function written in Python. Calling out into native code (which may then call back into Python code) is bound to grow the thread by some amount. While the interpreter could keep track of how much space is left on the stack, there's no way of knowing in advance how much any given C function will need. If there isn't enough, there is no robust way to recover from the resulting segfault. -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On 18 May 2016 at 17:11, Steven D'Aprano wrote: > The documentation for setrecursion limit warns against setting the limit too > high: > > [quote] > The highest possible limit is platform-dependent. A user may need to > set the limit higher when they have a program that requires deep > recursion and a platform that supports a higher limit. This should > be done with care, because a too-high limit can lead to a crash. > [end quote] > > https://docs.python.org/3/library/sys.html#sys.setrecursionlimit > > Indeed, if you set the recursion limit too high, you can smash the memory > heap and get a segfault. How exactly does that work? > > Why doesn't setrecursionlimit() raise an exception when you try to set it > too high? For example: > > sys.setrecursionlimit(20) > > succeeds on my system, even though that's a ludicrously high number. (It is > more than half the number of bytes of memory my computer has.) > > > So why can't Python tell if I'm setting the limit too high? > > (I'm assuming that if it could, it would.) It's not altogether impossible to do this but it requires ducking underneath the C level to the machine code level. The C standard doesn't define the exact number of bytes that should be used by a stack frame. The exact number depends on the calling convention used for your OS/hardware/compiler combination and also on the optimisation/debug settings used by the compiler. A good optimiser might be able to completely eliminate your function so that it doesn't touch the stack for example. Also it depends ultimately on the code path that leads to PyEval_EvalFrameEx calling itself recursively. The recursion here is indirect and there are multiple paths for it, depending on whether the function is called with no arguments or whether it is a generator etc. Then after that you need to consider extension modules. For example a numpy array can store Python objects and perform operations on them. If we have an ndarray of Fractions then there's no way at compile time to know how much stack space ndarray.__add__ (implemented with a load of complex C code) will need before calling e.g. Fraction.__add__. Given the extension module case it's clearly impossible to compute the hardware-stack memory requirements of a Python-level frame at compile time. Christian has already explained why this wouldn't really work at runtime either. There isn't even a portable way at the C level to query the current value of the stack pointer. And even if you could you'd have to make hardware-specific assumptions to be able to use that information. My understanding (although I have no direct experience here) is that Stackless Python is an alternative implementation that gets around all of these problems by avoiding the recursion altogether. -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
Rustom Mody wrote: Both the mess in catching numeric overflow as well as stackoverflow looks like its C's fault. I consider it as the fault of currently fashionable stock hardware The sad thing about C is that it doesn't even help you detect integer overflow in *software*. Every machine I've ever seen has a flag that gets set if an integer addition overflows. But C doesn't provide any portable way of testing that flag, even if you wanted to. -- Greg -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
Steven D'Aprano wrote: I don't really understand why the system can't track the current top of the stack and bottom of the heap, and if they're going to collide, halt the process. That effectively *is* what it does. The reason it manifests as a segfault is because of the way it goes about detecting the heap/stack collision. It would be very expensive to explicitly check for this every time something is pushed or popped on the stack, so what OSes typically do instead is reserve a buffer zone of unmapped memory between the stack and the heap. If the stack overflows, you end up trying to reference memory in the unmapped area, and a segfault results. This is not foolproof -- if you allocate a *really* big stack frame, you could leap right over the buffer zone and clobber the heap. But it works well enough most of the time and succeeds in stopping the program before it accidentally launches the nuclear missiles. Hardware support for stack bounds checkinbg would of course make all this easier and more reliable, but the x86 architecture doesn't provide anything like that, unfortunately. -- Greg -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Thursday, May 19, 2016 at 3:13:44 AM UTC+5:30, bream wrote: > On Wednesday, May 18, 2016 at 6:47:42 PM UTC+1, Chris Kaynor wrote: > > On Wed, May 18, 2016 at 10:15 AM, Steven D'Aprano wrote: > > > > > I don't really understand why the system can't track the current top of > > > the > > > stack and bottom of the heap, and if they're going to collide, halt the > > > process. That would still be kinda awful, in a sudden "your application > > > just died" kind of way, but it would be better than "your computer is now > > > owned by some hacker in Hong Kong, who is now renting it by the hour to > > > some spammer in Texas". > > > > > > > Most modern OSs will track it, and kill the app (hence the exception/crash > > that occurs), rather than allow access outside the memory. > > Chris > > Oh so funny, I just had to roar with laughter, unless you (plural) classify > VMS as a "modern OS". Then of course some youngsters think the OS is simply > software, whereas us old gits know that a combination of hardware and > software makes for something that is rather more solid. Hi Mark -- howdy! Much truth in your comment. Dijkstra pointed out (in mid-70s!) the essential tradeoff between hardware and software. He did it for numeric oveflow but it applies equally for stack overflow. In short software costs are variable costs: An instruction that is executed a million times costs million-fold one that is executed only once. For hardware its a fixed cost: Once the investment in silicon is done, once or a billion times is the same. Therefore -- and this is Dijkstra's key insight -- if a test is very skew, ie if the if-part is 99.9% likely to be taken and the else part only 0.1% the programmer will be increasingly tempted to drop the test and hope/pray that the 0.1% does not happen. With a hardware interrupt this temptation would be obviated. Both the mess in catching numeric overflow as well as stackoverflow looks like its C's fault. I consider it as the fault of currently fashionable stock hardware -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
Am 18.05.16 um 19:15 schrieb Steven D'Aprano: Not being a C programmer, I don't really understand this. The idea I have in mind is a model of program memory I learned[1] way back in the 80s. I don't know if it's still valid. Your application has a bunch of memory available, which broadly speaking can be divided into three chunks: globals, the stack, and the heap. The application knows what globals exist, and can allocate a fixed block of memory big enough for them, so that's not very interesting. It just sits there, holding space for the globals, and doesn't grow or shrink. Then there's the stack, which holds local variables whenever a function is called, the return address of the caller, and other stuff. There's a fixed bottom to the stack, but the top can grown and shrink depending on how many functions you call and how many local variables they use. Until here, it is reasonably accurate. On some machines, the stack does grow in the other direction, but that does not matter either. ON x86, it grows from top to bottom Then there's everything else, which is the heap, and it can grown and shrink in both directions (up to some maximum, of course): bottom [ globals | stack -> <- heap -> ] top If the stack grows into the heap, or vice versa, Bad Things happen. At best you get a crash. At worst you get arbitrary code execution. No, you have virtual memory management in effect in the OS which maps the real memory addresses into your address space. On 64 bit, a collision between stack and heap is practically impossible. I don't really understand why the system can't track the current top of the stack and bottom of the heap, and if they're going to collide, halt the process. It does. But in a different way. For the heap, you need to call a function which asks for more memory. It returns an error code, if the memory can't be supplied. The problem is that often in this case, the program needs more memory to handle that, e.g. to format an error message. If you allocate memory in small pieces until it is exhausted, the program will die in unforeseen ways. If you try to alloc 1TB on the heap and it fails, there is enough room for a clean shutdown. Unless the C program is buggy and does not check the error. On the stack, you don't allocate by telling the OS. You simply increase the stack pointer register. This is a single machine instruction, very fast, and unfeasible to trap by the OS and intercept. Instead, the stack is framed by pages which are non-writeable. As soon as the program tries to write there, it segfaults (SIGSEGV or SIGBUS). At this point there is no way to cleanly exit the program, therefore you see the crash/segfault. It might happen that you overrun the stack so much as to reach writeable memory again. But not under normal circumstances, where only a few bytes are pushed/popped. That would still be kinda awful, in a sudden "your application just died" kind of way, but it would be better than "your computer is now owned by some hacker in Hong Kong, who is now renting it by the hour to some spammer in Texas". Stack overflow does not usually lead to security risks. A buffer overflow is different: It means that the program allocates a fixed-size buffer on the stack, which overflows and writes into the return addresses / local variables of functions higher up the callchain. The basic problem here is, that the C programmer was too lazy to get the memory from the heap. Christian -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Wed, May 18, 2016 at 10:15 AM, Steven D'Aprano wrote: > I don't really understand why the system can't track the current top of the > stack and bottom of the heap, and if they're going to collide, halt the > process. That would still be kinda awful, in a sudden "your application > just died" kind of way, but it would be better than "your computer is now > owned by some hacker in Hong Kong, who is now renting it by the hour to > some spammer in Texas". > Most modern OSs will track it, and kill the app (hence the exception/crash that occurs), rather than allow access outside the memory. What generally happens is that, when a thread is created (including the main thread during startup), the OS will allocate enough pages to hold the requested stack, plus one as a buffer. Most of these are virtual pages, with no backing memory allocated (either in RAM or the page file). When the next page is first requested, the OS will actually allocate the RAM needed for that page of the stack. If the final guard page is hit, the OS will throw an exception, which generally kills the app. This means there is a overhead when a previously unused stack page is hit, however, as this generally does not happen often, it is generally acceptable. I cannot quickly find the reference material I learned this from, and naturally it will vary based on the OS, however this is pretty standard for general purpose, modern OSes. Chris -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Wed, May 18, 2016 at 11:15 AM, Steven D'Aprano wrote: > I don't really understand why the system can't track the current top of the > stack and bottom of the heap, and if they're going to collide, halt the > process. That would still be kinda awful, in a sudden "your application > just died" kind of way, but it would be better than "your computer is now > owned by some hacker in Hong Kong, who is now renting it by the hour to > some spammer in Texas". Seems kind of expensive for little benefit to have to make that check on every function call. -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Thu, 19 May 2016 02:29 am, Rob Gaddi wrote: > Ned Batchelder wrote: >> Is there a way to know how large the C stack can grow, and how much it >> will grow for each Python function call? That sounds complicated to get >> right. >> >> --Ned. > > It's probably trivial to look at a number and say "Yeah, no, that's > CLEARLY too high." based on the minimum number of bytes a stack frame > can require. Guaranteeing that some number lower than that is safe is > almost certainly impossible. So you'd get an exception for truly > stupid numbers, but a lack of exception is no guarantee of safety. > Which is worth what it's worth, I guess. Not being a C programmer, I don't really understand this. The idea I have in mind is a model of program memory I learned[1] way back in the 80s. I don't know if it's still valid. Your application has a bunch of memory available, which broadly speaking can be divided into three chunks: globals, the stack, and the heap. The application knows what globals exist, and can allocate a fixed block of memory big enough for them, so that's not very interesting. It just sits there, holding space for the globals, and doesn't grow or shrink. Then there's the stack, which holds local variables whenever a function is called, the return address of the caller, and other stuff. There's a fixed bottom to the stack, but the top can grown and shrink depending on how many functions you call and how many local variables they use. Then there's everything else, which is the heap, and it can grown and shrink in both directions (up to some maximum, of course): bottom [ globals | stack -> <- heap -> ] top If the stack grows into the heap, or vice versa, Bad Things happen. At best you get a crash. At worst you get arbitrary code execution. I don't really understand why the system can't track the current top of the stack and bottom of the heap, and if they're going to collide, halt the process. That would still be kinda awful, in a sudden "your application just died" kind of way, but it would be better than "your computer is now owned by some hacker in Hong Kong, who is now renting it by the hour to some spammer in Texas". [1] I say "learned", but in reality I more sort of absorbed it by osmosis. Nobody ever actually sat down and told me how the stack and heap work, so the model I have might be completely wrong, even for 1980s tech. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Wed, May 18, 2016 at 9:19 AM, Ned Batchelder wrote: > I believe the issue here is that Python recursion results in the C stack > growing. Each Python function call creates a number of C function calls, > which grows the C stack. The crash you see is the C stack overflowing. > > Is there a way to know how large the C stack can grow, and how much it > will grow for each Python function call? That sounds complicated to get > right. > I'm fairly sure that it is, in fact, basically impossible to get right. Some Python calls will use more memory on the C stack than others. They may call more C functions internally, or C functions that require more stack space. In the most extreme example, you could have a single Python call crash (for example, having a super deeply recursive call as a single Python call), or you could theoretically have extremely deep Python recursion without a problem (presuming optimizations that do not exist in CPython for a number of, generally good, reasons). Even in more typical cases, I believe a Python call with keyword arguments requires more stack than one with only positional arguments, which may require more than one with no arguments (depending on which CPython APIs were used). Additionally, even within the standard library, some of the native calls will require more stack (think OS calls) than most of the basic math functions and simple operators (like int add). The root of the issue is that, much of the time, C function arguments are allocated on the stack, if they exceed certain limits based on the calling convention used. 32-bit Windows only allocates the "this" pointer as a register, all other arguments are stack [1]. 64-bit Windows allocates up-to 4 word arguments as registers, and the rest on the stack [2]. I do not know what the Linux conventions are. Naturally, these rules may vary based on the compiler, for any functions the compiler knows is being compiled by the compiler - the rules listed for the OS are only required for OS calls, however most compilers will follow them for ease. Additionally, any local variables that do not fit in registers will be offloaded to the stack, and sometimes they will be offloaded even if they do fit, at the compiler's decision, especially if function calls are made. All of this means that, as Ned mentioned, it is very complicated to figure out a *recursion* depth that will cause a stack overflow. Generally, there will be an OS method to determine the stack size in *bytes*, however (and often, the application can control this when creating threads and in executable meta data for the main thread). There is basically no way to convert that bytes to a recursion level, however - the best you can do is as Rob said, see that a depth is obviously higher than valid, as it is a reasonable (but not guaranteed) guess that each recusion will use some number of bytes of stack. [1] https://msdn.microsoft.com/en-us/library/984x0h58.aspx [2] https://msdn.microsoft.com/en-us/library/zthk2dkh.aspx Chris -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
Ned Batchelder wrote: > On Wednesday, May 18, 2016 at 12:11:25 PM UTC-4, Steven D'Aprano wrote: >> The documentation for setrecursion limit warns against setting the limit too >> high: >> >> [quote] >> The highest possible limit is platform-dependent. A user may need to >> set the limit higher when they have a program that requires deep >> recursion and a platform that supports a higher limit. This should >> be done with care, because a too-high limit can lead to a crash. >> [end quote] >> >> https://docs.python.org/3/library/sys.html#sys.setrecursionlimit >> >> Indeed, if you set the recursion limit too high, you can smash the memory >> heap and get a segfault. How exactly does that work? >> >> Why doesn't setrecursionlimit() raise an exception when you try to set it >> too high? For example: >> >> sys.setrecursionlimit(20) >> >> succeeds on my system, even though that's a ludicrously high number. (It is >> more than half the number of bytes of memory my computer has.) >> >> >> So why can't Python tell if I'm setting the limit too high? >> >> (I'm assuming that if it could, it would.) > > I believe the issue here is that Python recursion results in the C stack > growing. Each Python function call creates a number of C function calls, > which grows the C stack. The crash you see is the C stack overflowing. > > Is there a way to know how large the C stack can grow, and how much it > will grow for each Python function call? That sounds complicated to get > right. > > --Ned. It's probably trivial to look at a number and say "Yeah, no, that's CLEARLY too high." based on the minimum number of bytes a stack frame can require. Guaranteeing that some number lower than that is safe is almost certainly impossible. So you'd get an exception for truly stupid numbers, but a lack of exception is no guarantee of safety. Which is worth what it's worth, I guess. -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix. -- https://mail.python.org/mailman/listinfo/python-list
Re: setrecursionlimit
On Wednesday, May 18, 2016 at 12:11:25 PM UTC-4, Steven D'Aprano wrote: > The documentation for setrecursion limit warns against setting the limit too > high: > > [quote] > The highest possible limit is platform-dependent. A user may need to > set the limit higher when they have a program that requires deep > recursion and a platform that supports a higher limit. This should > be done with care, because a too-high limit can lead to a crash. > [end quote] > > https://docs.python.org/3/library/sys.html#sys.setrecursionlimit > > Indeed, if you set the recursion limit too high, you can smash the memory > heap and get a segfault. How exactly does that work? > > Why doesn't setrecursionlimit() raise an exception when you try to set it > too high? For example: > > sys.setrecursionlimit(20) > > succeeds on my system, even though that's a ludicrously high number. (It is > more than half the number of bytes of memory my computer has.) > > > So why can't Python tell if I'm setting the limit too high? > > (I'm assuming that if it could, it would.) I believe the issue here is that Python recursion results in the C stack growing. Each Python function call creates a number of C function calls, which grows the C stack. The crash you see is the C stack overflowing. Is there a way to know how large the C stack can grow, and how much it will grow for each Python function call? That sounds complicated to get right. --Ned. -- https://mail.python.org/mailman/listinfo/python-list
