Like Tree2Likes

Can it be detected if stack space is about to expire?

This is a discussion on Can it be detected if stack space is about to expire? within the C++ Programming forums, part of the General Programming Boards category; I have some code where it is up to the user how many times a function will be called recursively. ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    Can it be detected if stack space is about to expire?

    I have some code where it is up to the user how many times a function will be called recursively.
    Can it be detected when the system limit for it is reached ? (It gives seg faults now...but, I'd like to throw exceptions when it happens.)
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,337
    Any technique to do that would be system specific.

    Generally, it would be better to either code your function non-recursively, or write it more carefully so it does not recurse so deeply.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by grumpy View Post
    Any technique to do that would be system specific.

    Generally, it would be better to either code your function non-recursively, or write it more carefully so it does not recurse so deeply.
    Well it is a lisp(sort of !) interpreter I wrote.. and I can't stop the user from defining stupid functions like:
    Code:
    (defun foo(n)(foo (* n n)))
    I'm considering putting a constant limit....but it seems like taking the easy way out.

    Here is a 'transcript':
    [minlisp](defun foo(n)(foo (* n n)))
    foo
    [minlisp](foo 68778)
    Segmentation fault (core dumped)
    [manasij7479@manasijn minlisp]$
    It took about 2 mins for the error.
    Last edited by manasij7479; 12-02-2011 at 04:37 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,337
    A smart way would be to change the interpreter so it detects infinitely recursive functions, rather than executing them and going into the nether-nether.
    Right 98% of the time, and don't care about the other 3%.

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by grumpy View Post
    A smart way would be to change the interpreter so it detects infinitely recursive functions, rather than executing them and going into the nether-nether.
    In that case.. does the absence of a conditional clause in a recursive function surely denote that the function is not going to return ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,714
    I would say yes, since recursion is defined by the base case. Anything that evaluates to if (true), always, being the implicit base case for infinite recursion.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    This is an issue for all runtime interpreters, I think. IMO it is better to handle at runtime than compile time and I'm sure that is the most common method. Ie, rather than assessing the code, allow it to run, but set an arbitrary limit (maybe: configurable) to the depth of the recursion and when this is exceeded throw an error. It doesn't guarantee avoiding a seg fault, but it will catch more cases and be less prone to mistake. I'd rather risk a seg fault due to my own foolishness or ignorance (most programmers learn about this fairly early, don't they? You only have to get hamstrung once to get it.) than be told incorrectly there is a problem with my code.
    Last edited by MK27; 12-02-2011 at 07:03 AM.
    cyberfish likes this.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    - Use libsigsegv
    - Check that it's supported in your platform
    - Install a stack overflow handler

    You can handle the stack overflow in several ways. Typically, you would longjmp back to the fault point and either inform of the stack overflow, or handle the recursion differently.
    MK27 likes this.
    Stick close to your desks and never program a thing,
    And you all may sit in the standards commitee!

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    There is nothing wrong with a recursive function that potentially uses infinite stack space... You should assume the stack can grow arbitrarily. Running out of stack is the same as running out of memory -- your program simply ran out of memory, no program can be expected to function properly without enough memory.

    The problem is grace when running out of memory. Most suggestions how to fix this are probably going to involve rearchitecting your code to some degree. For instance you can have a stack that you control directly rather than using the processor stack, but this stops you from representing recursive processing by actually recursing, which is nothing to sneeze at. The only way to avoid major changes to the code is with machine-specific hacks, like querying the stack pointer or catching the memory exception and processing it a special way if it's a stack exception.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Oct 2006
    Posts
    2,456
    you have an interpreter - essentially a virtual machine - why not implement your own managed stack? you manage objects allocated by the interpreted code, why not also manage its stack in software?

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by Elkvis View Post
    you have an interpreter - essentially a virtual machine - why not implement your own managed stack? you manage objects allocated by the interpreted code, why not also manage its stack in software?
    I think the problem might be that a call in the interpreted code is implemented by a call in the VM, this deeply entwines the program stack with the machine stack. This is the same problem Python has and why "Stackless Python" is an ongoing wish-I-had sort of dream. Tying the interpreter stack to the machine stack is a recipe for all kinds of awful problems, not just oppressive stack use to store interpreter variables. In fact I doubt that's what the stack is being used for, this sounds like a problem with recursion.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,337
    Quote Originally Posted by brewbuck View Post
    There is nothing wrong with a recursive function that potentially uses infinite stack space...
    I disagree brewbuck.

    A function that actually attempts to use more resources than are available to it is fundamentally flawed.

    This flaw needs to be addressed as early as possible in the development process. In requirements, always. In architecture and design if possible, so the problem is prevented completely. At run time if necessary, with mitigation of the effects that occur (if that mitigation is less expensive to achieve than an architectural change) but that should not be the default treatment. If the problem can be anticipated at all, and can be reasonably addressed, leaving it unaddressed is incompetence and laziness by a software developer.

    The only cases that are forgivable are when a problem is not actually identified (for example, insufficient time is available to identify edge cases, and developers are not super-human), or if the cost to address it is excessive compared with the benefit (which then makes it a management decision, and the risks should be borne by management).
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,046
    In a functional language it might be a good idea to implement recursion on your own stack. They tend to use the stack more than imperative languages, and use the heap a lot less. Otherwise you would need a large pre-allocated stack, and you wouldn't be able to resize it, because it would invalidate pointers in the stack.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by grumpy View Post
    I disagree brewbuck.

    A function that actually attempts to use more resources than are available to it is fundamentally flawed.
    But that's not the same thing as one which potentially does so, which is why I said it's a bad idea to make a decision based on the code at compile time.

    Vis, implementing a stack, I know the perl does this -- it's a global heap structure.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #15
    Registered User
    Join Date
    Jun 2005
    Posts
    6,337
    Quote Originally Posted by MK27 View Post
    But that's not the same thing as one which potentially does so, which is why I said it's a bad idea to make a decision based on the code at compile time.
    That depends on the compile-time analysis.

    There are plenty of cases where the compiler or interpreter can unambiguously assess that a function is infinitely recursive (for example, a function calling itself with the same data it received, directly or indirectly, or a function unconditionally calling itself). In those cases, it is reasonable to make a decision at compile time.

    There are also plenty of cases where the compiler can assess a likelihood of infinite recursion. Those should be reported (for example, a compiler warning) but I agree it would be inappropriate to flatly refuse to compile.
    Right 98% of the time, and don't care about the other 3%.

Page 1 of 4 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack Smashing Detected
    By halexh in forum C Programming
    Replies: 13
    Last Post: 05-19-2010, 02:10 AM
  2. *** stack smashing detected ***
    By chakra in forum C Programming
    Replies: 2
    Last Post: 06-09-2009, 09:12 PM
  3. *** stack smashing detected ***
    By Martin_HS in forum C Programming
    Replies: 9
    Last Post: 05-29-2009, 04:01 AM
  4. help on *** stack smashing detected ***
    By jodelson in forum C Programming
    Replies: 8
    Last Post: 08-16-2007, 06:25 PM
  5. Managing Stack space?
    By Aidman in forum C++ Programming
    Replies: 4
    Last Post: 09-07-2003, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21