Loading ...
Sorry, an error occurred while loading the content.

Re: Restricting recursion?

Expand Messages
  • ed_davis2
    ... A few thoughts, more to detecting using inordinate amounts of stack space: Each time your stack grows (pushes, allocation of local variables, temporaries,
    Message 1 of 9 , Jan 5, 2004
    View Source
    • 0 Attachment
      --- In QDepartment@yahoogroups.com, "M. Uli Kusterer" wrote:
      > Whenever a user produces an endless recursion of any kind, my
      > application will just happily keep executing, using up
      > resources endlessly and finally just blowing up horribly.
      >
      > I'd like to have my application attempt to prevent this and
      > put up an error message "too much recursion" or something like
      > that. But I have no idea how to detect recursion. Any ideas?

      A few thoughts, more to detecting using inordinate amounts of
      stack space:

      Each time your stack grows (pushes, allocation of local
      variables, temporaries, whatever), you could check to make sure
      you are within an acceptable limit.

      Or, you could only check the stack usage whenever local variables
      are allocated on entry to a function.

      If you have a Pascal/C/C++ compiler that can generates
      stack-checking-code as a compiler option, you could turn that on,
      compile some sample code, and disassemble it and see what that
      compiler does.

      As for detecting recursion, your idea sounds like it might work.
      But as you say, you would have to some how connect the counter to
      the proper script. Does each script have a unique identifier,
      say a handle or perhaps a unique base address? Perhaps you could
      use this to somehow index into an array, if the
      script-identifiers start at 0 and run consecutively.

      Since this is such an interesting question, you might try asking
      it at a couple of other places:

      The Yahoo Group Compilers101

      The usenet group comp.compilers - you can post/read there via
      google-groups.

      I would appreciate hearing about whatever solution you do come up
      with.
    • Steve A.
      Hello Uli, It s very good to hear from you and I can appreciate your questions, having worked at some length of the subject of recursion. ... Yes, this is not
      Message 2 of 9 , Jan 5, 2004
      View Source
      • 0 Attachment
        Hello Uli,

        It's very good to hear from you and I can appreciate your questions,
        having worked at some length of the subject of recursion.

        > Whenever a user produces an endless recursion of any kind, my
        >application will just happily keep executing, using up resources
        >endlessly and finally just blowing up horribly.

        Yes, this is not at all unheard of.
        Some languages or dialects will simply let the program crash.
        Blame the programmer.
        Then again, some languages will halt when the stack space has been
        exhausted.
        On the otherhand, as the language developer, you have the distinct
        opportunuty to determine how you wish the outcome to be resolved.

        > I'd like to have my application attempt to prevent this and put up
        >an error message "too much recursion" or something like that. But I
        >have no idea how to detect recursion. Any ideas?

        As I see it, you can approach this in perhaps one of two ways, or, both
        simultaniously, a check and balance, so to speak:

        1) at the start of the program, you can assign a variable to hold
        the maximum stack address you wish to prevent exceeding. When the
        program enters a function that is prone to recursion, you can take
        a look at the available stack, or current stack address (stack pointer).
        You can then compare the current stack address with the maximum stack
        address and branch based on the result. Either proceed with the recursion,
        or generate an error message, via a message handler routine.
        Not all functions are subject to recursion, in my experience.

        2) On those function that are prone to recursion, yes, you can actually
        keep a count of the number of times it has been looped through.
        I experienced this when writing the "IF/Then/Else" sequence for "Bxb".
        In that situation, I chose to monitor the recursion count. At the time,
        it looked like a lot simpler course to take. I simply declared a *global
        variable*, that would not be subject to the comings and goings of the
        stack, and everytime it entered the "IF/Else" sequence, the counter was
        incremented. Thusly, as it exited the sequence, it decremented the count.

        The net result is that the counter will always stay within a safety zone.
        After experiencing many crashes I stumbled across this solution. After
        running several tests, causing hundreds or thousands of recursions, the
        counter has prevented further crashes.

        By monitoring either the stack-pointer or recursion count, you can safely
        close open files and generate an intellegent error message before the program
        comes to a screeching halt on it's own, or wanders off to *never-neverland*.

        Some people might argue that maintaining any control over recursion is
        taking an element of control away from the programmer. That is something
        you will have to wrestle with.

        >....I thought about maybe giving every function a counter how often it's
        >running right now, but I guess I'd have to attach that to the call
        >stack or something, because otherwise

        As stated above, only certain functions tend to be affected the most.

        >...two simultaneously running copies of the script might be seen as an
        >endless loop as well.

        I'm not sure why that would be the case.
        Each script should be running wihtin it's own 'INSTANCE', in it's own
        memory space, etc. I can't see why there should be a conflict.

        Hope this helps. If you need more information, feel free to ask.

        Steve
      • witness_of_teachtext
        ... Ed, that sounds like a more practicable approach than my original idea. The point when local variables are allocated would actually be a very nice point to
        Message 3 of 9 , Jan 6, 2004
        View Source
        • 0 Attachment
          --- In QDepartment@yahoogroups.com, "ed_davis2" <ed_davis2@y...> wrote:
          > Each time your stack grows (pushes, allocation of local
          > variables, temporaries, whatever), you could check to make sure
          > you are within an acceptable limit.
          >
          > Or, you could only check the stack usage whenever local variables
          > are allocated on entry to a function.

          Ed,

          that sounds like a more practicable approach than my original idea. The point when
          local variables are allocated would actually be a very nice point to hook in at in my
          case. Though then the problem would be: How do I determine what "an acceptable
          limit" is?

          A hard-coded limit would be very inflexible. Depending on what amount of RAM a
          user has, I might want to raise the limit, to reduce the number of valid but complex
          recursions I cut off mistakenly. Trouble is: Most Unixes (I'm running MacOS X) don't
          let you know how much physical RAM there is. Furthermore, they allow swapping out
          memory to hard disk, and I'd want to allow that to a certain degree, but not up to the
          point where the swap file fills the hard disk... hmmm...

          > If you have a Pascal/C/C++ compiler that can generates
          > stack-checking-code as a compiler option, you could turn that on,
          > compile some sample code, and disassemble it and see what that
          > compiler does.

          My stack is actually not _the_ stack. Just a stack data structure (okay, std::deque) on
          the heap.

          > As for detecting recursion, your idea sounds like it might work.
          > But as you say, you would have to some how connect the counter to
          > the proper script. Does each script have a unique identifier,
          > say a handle or perhaps a unique base address? Perhaps you could
          > use this to somehow index into an array, if the
          > script-identifiers start at 0 and run consecutively.

          Nothing of the kind, no. The best I have are memory addresses of my loaded byte-
          code instructions.

          > Since this is such an interesting question, you might try asking
          > it at a couple of other places:
          >
          > The Yahoo Group Compilers101

          Thanks. No idea why I didn't notice that newsgroup before.

          > The usenet group comp.compilers - you can post/read there via
          > google-groups.

          I actually have a real newsfeed. :-)

          > I would appreciate hearing about whatever solution you do come up
          > with.

          I'll try to remember to f'up on this one to let you all know what I eventually decided
          on. If RL doesn't interfere, that is. ;-)

          Cheers,
          -- M. Uli Kusterer
        • witness_of_teachtext
          ... Steve, that s good to hear :-) ... Since I m aiming at beginners, just crashing really isn t what I want. Ideally, any invalid input on the user s side in
          Message 4 of 9 , Jan 6, 2004
          View Source
          • 0 Attachment
            --- In QDepartment@yahoogroups.com, "Steve A." <sarbayo@t...> wrote:
            > It's very good to hear from you and I can appreciate your questions,
            > having worked at some length of the subject of recursion.

            Steve,

            that's good to hear :-)

            > Yes, this is not at all unheard of.
            > Some languages or dialects will simply let the program crash.
            > Blame the programmer.
            > Then again, some languages will halt when the stack space has been
            > exhausted.

            Since I'm aiming at beginners, just crashing really isn't what I want. Ideally, any
            invalid input on the user's side in the form of code should at worst end in abortion of
            script execution and an error message to the user.

            > 1) at the start of the program, you can assign a variable to hold
            > the maximum stack address you wish to prevent exceeding. When the
            > program enters a function that is prone to recursion, you can take
            > a look at the available stack, or current stack address (stack pointer).
            > You can then compare the current stack address with the maximum stack
            > address and branch based on the result. Either proceed with the recursion,
            > or generate an error message, via a message handler routine.

            This sounds basically like what Ed suggested as well. Though I still don't have much
            of a clue how to calculate a limit instead of just hard-coding one and thus screwing
            with legitimate uses (I'd like to avoid a preference forcing the user to specify a stack
            limit -- not newbie-friendly enough).

            > Not all functions are subject to recursion, in my experience.

            Well, I guess those that don't call any subroutines at all could be ruled out. Are there
            any other nice tricks? I'm not sure I'd want to build a huge dependency graph to check
            where possible recursions could arise, though. Especially since I have sort of
            smalltalk-ish messaging, which means there'd be many more possible cases that
            won't be known until runtime...

            > 2) On those function that are prone to recursion, yes, you can actually
            > keep a count of the number of times it has been looped through.
            > I experienced this when writing the "IF/Then/Else" sequence for "Bxb".
            > In that situation, I chose to monitor the recursion count. At the time,
            > it looked like a lot simpler course to take. I simply declared a *global
            > variable*, that would not be subject to the comings and goings of the
            > stack, and everytime it entered the "IF/Else" sequence, the counter was
            > incremented. Thusly, as it exited the sequence, it decremented the count.

            Maybe my implementation is very different from yours, but I can't quite grasp why I
            would want to check for recursion in if/then/else? Or do you mean in one particular
            script that you wrote using your interpreter? I'm sorry if I wasn't clear enough: I'm not
            looking for a particular solultion for a particular script. Rather, I'm looking for a
            general solution I can implement at the language level to protect the scripters using
            my language.

            > Some people might argue that maintaining any control over recursion is
            > taking an element of control away from the programmer. That is something
            > you will have to wrestle with.

            Yes, that is why I am attempting to avoid a hard-coded limit. Basically, I'm just trying
            to do what most modern OSs with protected memory do (shoot down the offending
            program the moment it attempts to overrun the stack) on a higher level (shoot down
            the offending script and display an error message). Eventually, I hope to just throw an
            exception in that case (once I have implemented exceptions, that would be...), which
            can be caught at a point lower down, so a scripter has at least some control over what
            part of the script is shot down.

            > I'm not sure why that would be the case.
            > Each script should be running wihtin it's own 'INSTANCE', in it's own
            > memory space, etc. I can't see why there should be a conflict.

            Neither can I. Guess my train of thought got screwed up somewhere.

            Cheers,
            -- M. Uli Kusterer
            http://www.zathras.de
          • Steve A.
            Hey Uli, ... Right, I understand that. You may need to run a test using increasingly higher limits, to see where your breaking point is. ... Because, of this
            Message 5 of 9 , Jan 7, 2004
            View Source
            • 0 Attachment
              Hey Uli,

              >Though I still don't have much of a clue how to calculate a limit instead
              >of just hard-coding one and thus screwing with legitimate uses (I'd like
              >to avoid a preference forcing the user to specify a stack
              >limit -- not newbie-friendly enough).

              Right, I understand that.
              You may need to run a test using increasingly higher limits, to see where
              your breaking point is.

              > Maybe my implementation is very different from yours, but I can't quite
              >grasp why I would want to check for recursion in if/then/else?

              Because, of this type of syntax:
              ...
              IF (expr) THEN ' first-level 'IF'
              IF (expr) THEN ' recursive 'IF'
              IF (expr) THEN ' 2nd degree recursive
              IF (expr) THEN ' 3rd degree recursive
              [program block] '--->(that may include a call
              ... to this same function)
              ENDIF
              ENDIF
              ENDIF
              ENDIF
              ...
              In other words, *IF* is just another function,...
              except that it is prone to be called recursively,
              before having exited from any given degree of recursion.

              >Or do you mean in one particular script that you wrote using your
              interpreter?

              No, in general principal.

              >Rather, I'm looking for a general solution I can implement at the language
              >level to protect the scripters using my language.

              Correct.
              (as you stated previously), the OS tends to makes little or no distinction
              between *real* and *virtual* memory. You either need a mechanism for
              monitoring your recursions (a counter), or for monitoring a stack usage
              pointer. I'm sure that you can examine the Stack Register at the start
              of the program and build a hook that makes sure it doesn't exceed some
              rediculously high limit.

              I can't think of too many functions that would call themselves recursively,
              in an uncontrolled fashion. Are you sure that is really the problem.
              1) you enter a function,
              2) you execute it and then,
              3) you exit the function.

              Perhaps an example, some code or pseudo-code that would help explain why
              you feel that recursion is really the heart of the problem.
              Are you sure your program isn't just caught in a loop somewhere?
              Have you actually run a recursion test, to see how deeply nested your
              program is, prior to crashing?

              Steve
            • M. Uli Kusterer
              ... So, you mean fork off a copy of the interpreter, and make it recurse until it barfs? ... Well, since in the case of if (at least the way I implemented
              Message 6 of 9 , Jan 8, 2004
              View Source
              • 0 Attachment
                At 16:52 Uhr +0100 07.01.2004, Steve A. wrote:
                >Right, I understand that.
                >You may need to run a test using increasingly higher limits, to see where
                >your breaking point is.

                So, you mean fork off a copy of the interpreter, and make it recurse
                until it barfs?

                >In other words, *IF* is just another function,...
                >except that it is prone to be called recursively,
                >before having exited from any given degree of recursion.

                Well, since in the case of "if" (at least the way I implemented it)
                all stack space needed is already allocated on entry to the function,
                and "if" isn't a function of its own right in my language (that would
                be overkill for such a commonly used construct in my case), I don't
                think that's necessary for me.

                Checking on entry to an actual function should be enough to ensure I
                don't run out of pseudo-stack space.

                >(as you stated previously), the OS tends to makes little or no distinction
                >between *real* and *virtual* memory. You either need a mechanism for
                >monitoring your recursions (a counter), or for monitoring a stack usage
                >pointer. I'm sure that you can examine the Stack Register at the start
                >of the program and build a hook that makes sure it doesn't exceed some
                >rediculously high limit.

                Yes, I understand the basic principle. I'd probably just check the
                stack size against some limit, which can be done easily. The problem
                is finding the right limit for the current computer. E.g. a user with
                2GB of RAM can do a good deal more recursions than one who only has
                256MB. But I guess I'll have to implement that in a platform-specific
                way, and thus this would probably be off-topic on this list. I'll try
                on one of the Mac mailing lists.

                >I can't think of too many functions that would call themselves recursively,
                >in an uncontrolled fashion. Are you sure that is really the problem.

                This language I'm writing will be used by beginners. They will
                constantly write faulty code, and I need the language to take
                anything they dish out and at worse abort the current script. I can't
                have the entire application coming down, taking unsaved files with it
                etc. It's part of the requirements for my language that it be
                forgiving, which means even if there is only one function that can
                cause a crash, I'll have to account for it.

                >Perhaps an example, some code or pseudo-code that would help explain why
                >you feel that recursion is really the heart of the problem.
                >Are you sure your program isn't just caught in a loop somewhere?
                >Have you actually run a recursion test, to see how deeply nested your
                >program is, prior to crashing?

                It's like this: The user enters a script, say:

                on repeatForever
                repeatForever
                end repeatForever

                When I compile and run this code, my app starts eating up resources,
                then shoots down the system. I know that this is useless code, but
                nothing keeps my users of entering such scripts, so I have to cater
                to it. Since the application consists of more than just these
                scripts, I need it to recover gracefully from such faulty scripts.
                --
                Cheers,
                M. Uli Kusterer
                ------------------------------------------------------------
                "The Witnesses of TeachText are everywhere..."
                http://www.zathras.de
              • M. Uli Kusterer
                ... Hi, just to f up on this thread: The folks at comp.compilers pointed me at libiberty in the GCC sources, which lets me detect the physical memory of the
                Message 7 of 9 , Jan 14, 2004
                View Source
                • 0 Attachment
                  At 16:52 Uhr +0100 07.01.2004, Steve A. wrote:
                  >Right, I understand that.
                  >You may need to run a test using increasingly higher limits, to see where
                  >your breaking point is.

                  Hi,

                  just to f'up on this thread: The folks at comp.compilers pointed me
                  at "libiberty" in the GCC sources, which lets me detect the physical
                  memory of the computer. They also pointed me at the Unix system call
                  getrlimit() which gives the various size limits the current
                  application may not exceed.

                  So, right now I'll try to calculate my recursion stack depth limit
                  by getting RLIMIT_RSS (which is the RAM limit in bytes), dividing
                  that by twice the size of my stack entries, and using that as the
                  upper limit.
                  --
                  Cheers,
                  M. Uli Kusterer
                  ------------------------------------------------------------
                  "The Witnesses of TeachText are everywhere..."
                  http://www.zathras.de
                • M. Uli Kusterer
                  ... That was theory, now comes practice: ;-) - getrlimit: This absolutely didn t work. RLIMIT_RSS is an incredibly large 64-bit number, which I can hardly
                  Message 8 of 9 , Jan 17, 2004
                  View Source
                  • 0 Attachment
                    At 10:10 Uhr +0100 14.01.2004, M. Uli Kusterer wrote:
                    > So, right now I'll try to calculate my recursion stack depth limit
                    >by getting RLIMIT_RSS (which is the RAM limit in bytes), dividing
                    >that by twice the size of my stack entries, and using that as the
                    >upper limit.

                    That was theory, now comes practice: ;-)

                    -> getrlimit: This absolutely didn't work. RLIMIT_RSS is an
                    incredibly large 64-bit number, which I can hardly even get close to
                    with my endless recursion.

                    -> libiberty only does physical RAM, which also doesn't seem wise as
                    a limit to recursion.

                    -> Limiting stack size itself (as in 10000 entries on the stack) also
                    doesn't really work, because depending on how many local variables
                    are involved, my limit is either too high, or too low for even simple
                    recursive scripts.

                    The problem isn't really the program crashing, but rather that it
                    starts eating up CPU cycles long before that. So, I'll probably have
                    to monitor the call stack and limit the depth of that. I.e. every
                    time I jump into a subroutine, it'll increase some counter, and if
                    that gets too high, I'll cut it off.

                    ... apart from that, I will probably have to do some heavy profiling
                    on my variable stack... something tells me I went way overboard with
                    virtual functions and templatized auto-released reference-counted
                    objects... ;-)
                    --
                    Cheers,
                    M. Uli Kusterer
                    ------------------------------------------------------------
                    "The Witnesses of TeachText are everywhere..."
                    http://www.zathras.de
                  Your message has been successfully submitted and would be delivered to recipients shortly.