Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #31287

Re: Infinite recursion detection criteria (Please correct me if I am wrong)

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinite recursion detection criteria (Please correct me if I am wrong)
Date 2021-04-18 02:13 +0100
Organization A noiseless patient Spider
Message-ID <87czus8kdr.fsf@bsb.me.uk> (permalink)
References <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com> <87y2dg8m7i.fsf@bsb.me.uk> <tLKdnTL0L96r4ub9nZ2dnUU7-d-dnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> If a function X() is called by function Y() twice in sequence from the
>>> same machine address of Y() with the same parameters to X() and the
>>> execution trace shows no conditional branch instructions in Y() or
>>> function call returns in X() then the function call from Y() to X() is
>>> infinitely recursive unless X() stops it.
>>
>> You mean like this:

(I'll post a slight variation in case that clearer)

> I couldn't make that out it is not the syntax that I am familiar with
> does it get past this newly updated criteria?

I was asking you because I don't follow your criteria.  If neither Y not
X return, of course there is infinite recursion.  I thought the criteria
were there to detect if there was infinite recursion without just
waiting to see if X or Y return (which they'd have to do multiple
times).  In other words, I thought you were looking for calls without an
intervening return.

> If the execution trace of function X() called by function Y() shows:
> (1) Function X() is called twice in sequence from the same machine
> address of Y().

The calls are obvious -- look for callq instructions.  Those from Y to X
are all at Y+8 (in the new trace below).

> (2) With the same parameters to X().

No parameters are being passed to any of the functions.

> (3) With no conditional branch or indexed jump instructions in Y().

The only instructions in Y are push, mov and callq.  If X returns
(i.e. the recursion is not infinite) then Y will do pop and retq.

> (4) With no function call returns from X().

X calls Q which calls back to Y so X can be called again.  But if the
recursion is not infinite, X will return to Y.

> then the function call from Y() to X() is infinitely recursive unless
> X() stops it.

I thought the plan was to detect "infinite recursion" from the call
sequence.  I.e. that you can detect it from something like this trace:

  0x0000555555555189 <main+0>:	endbr64 
  0x000055555555518d <main+4>:	push   %rbp
  0x000055555555518e <main+5>:	mov    %rsp,%rbp
  0x0000555555555191 <main+8>:	callq  0x55555555516b <Y>
  0x000055555555516b <Y+0>:	endbr64 
  0x000055555555516f <Y+4>:	push   %rbp
  0x0000555555555170 <Y+5>:	mov    %rsp,%rbp
  0x0000555555555173 <Y+8>:	callq  0x55555555515c <X>
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Q>
  0x0000555555555129 <Q+0>:	endbr64 
  0x000055555555512d <Q+4>:	push   %rbp
  0x000055555555512e <Q+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Q+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Q+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Q+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Q+23>:	cltq   
  0x0000555555555142 <Q+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Q+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Q+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Q+44>:	callq  *%rax
  0x000055555555516b <Y+0>:	endbr64 
  0x000055555555516f <Y+4>:	push   %rbp
  0x0000555555555170 <Y+5>:	mov    %rsp,%rbp
  0x0000555555555173 <Y+8>:	callq  0x55555555515c <X>
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Q>
  0x0000555555555129 <Q+0>:	endbr64 
  0x000055555555512d <Q+4>:	push   %rbp
  0x000055555555512e <Q+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Q+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Q+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Q+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Q+23>:	cltq   
  0x0000555555555142 <Q+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Q+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Q+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Q+44>:	callq  *%rax
  0x000055555555516b <Y+0>:	endbr64 
  0x000055555555516f <Y+4>:	push   %rbp
  0x0000555555555170 <Y+5>:	mov    %rsp,%rbp
  0x0000555555555173 <Y+8>:	callq  0x55555555515c <X>
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Q>
  0x0000555555555129 <Q+0>:	endbr64 
  0x000055555555512d <Q+4>:	push   %rbp
  0x000055555555512e <Q+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Q+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Q+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Q+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Q+23>:	cltq   
  0x0000555555555142 <Q+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Q+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Q+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Q+44>:	callq  *%rax
  0x000055555555516b <Y+0>:	endbr64 
  0x000055555555516f <Y+4>:	push   %rbp
  0x0000555555555170 <Y+5>:	mov    %rsp,%rbp
  0x0000555555555173 <Y+8>:	callq  0x55555555515c <X>
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Q>
  0x0000555555555129 <Q+0>:	endbr64 
  0x000055555555512d <Q+4>:	push   %rbp
  0x000055555555512e <Q+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Q+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Q+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Q+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Q+23>:	cltq   
  0x0000555555555142 <Q+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Q+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Q+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Q+44>:	callq  *%rax
  0x000055555555516b <Y+0>:	endbr64 
  0x000055555555516f <Y+4>:	push   %rbp
  0x0000555555555170 <Y+5>:	mov    %rsp,%rbp
  0x0000555555555173 <Y+8>:	callq  0x55555555515c <X>
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Q>
  0x0000555555555129 <Q+0>:	endbr64 
  0x000055555555512d <Q+4>:	push   %rbp
  0x000055555555512e <Q+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Q+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Q+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Q+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Q+23>:	cltq   
  0x0000555555555142 <Q+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Q+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Q+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Q+44>:	callq  *%rax
  ...

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 09:17 -0500
  Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 19:18 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 02:02 +0000
      Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:04 -0500
        Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 02:19 +0000
          Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:24 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:05 -0700
      Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:12 -0500
        Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:18 -0700
    Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 03:08 +0100
      Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:16 -0500
        Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 21:56 +0100
          Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 16:08 -0500
            Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 14:21 -0700
            Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 14:22 -0700
            Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 01:11 +0100
              Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:32 -0500
                Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 01:38 +0100
                Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:52 -0500
                Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-19 02:10 +0100
                Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-18 19:57 -0500
                Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 20:47 -0700
  Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 01:34 +0100
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 19:37 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:13 +0100
        Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 20:28 -0500
          Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:49 +0100
            Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 21:01 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 19:49 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 02:36 +0100
        Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 20:43 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:21 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-18 23:30 +0100
  Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:24 -0500
  Re: Infinite recursion detection criteria (Please correct me if I am wrong) Mikko <mikko.levanto@outlook.com> - 2021-04-19 19:43 +0300
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-19 11:53 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) Richard Damon <Richard@Damon-Family.org> - 2021-04-19 13:47 -0400

csiph-web