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


Groups > comp.theory > #31303

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

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Date 2021-04-18 03:08 +0100
Organization A noiseless patient Spider
Message-ID <87eef873a2.fsf@bsb.me.uk> (permalink)
References <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com> <ZPKdnSyBUrN_5-b9nZ2dnUU7-efNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 4/17/2021 9:17 AM, olcott wrote:
>> 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.
>>
>> The referenced execution trace is on x86 machine language, disassembled for human consumption.
>>
>
> void X(u32 P, i32 I)
> {
>   Simulate(P, I);
> }
>
> void Y(u32 P)
> {
>   X(P, P);
> }
>
> int main()
> {
>   X((u32)Y, (u32)Y);
> }
>
>
> 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().
> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().
> then the function call from Y() to X() is infinitely recursive unless
> X() stops it.

Can you tell if this is or is not infinite recursion:

  0x00005555555551de <main+0>:	endbr64 
  0x00005555555551e2 <main+4>:	push   %rbp
  0x00005555555551e3 <main+5>:	mov    %rsp,%rbp
  0x00005555555551e6 <main+8>:	lea    -0x4a(%rip),%rdx
  0x00005555555551ed <main+15>:	lea    -0x51(%rip),%rax
  0x00005555555551f4 <main+22>:	lea    (%rdx),%rsi
  0x00005555555551f7 <main+25>:	lea    (%rax),%rdi
  0x00005555555551fa <main+28>:	callq  0x555555555174 <X>
  0x0000555555555174 <X+0>:	endbr64 
  0x0000555555555178 <X+4>:	push   %rbp
  0x0000555555555179 <X+5>:	lea    (%rsp),%rbp
  0x000055555555517d <X+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555182 <X+14>:	mov    %rdi,-0x8(%rbp)
  0x0000555555555186 <X+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555518a <X+22>:	mov    -0x10(%rbp),%rdx
  0x000055555555518e <X+26>:	mov    -0x8(%rbp),%rax
  0x0000555555555192 <X+30>:	mov    %rdx,%rsi
  0x0000555555555195 <X+33>:	mov    %rax,%rdi
  0x0000555555555198 <X+36>:	callq  0x555555555129 <Simulate>
  0x0000555555555129 <Simulate+0>:	endbr64 
  0x000055555555512d <Simulate+4>:	push   %rbp
  0x000055555555512e <Simulate+5>:	lea    (%rsp),%rbp
  0x0000555555555132 <Simulate+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555137 <Simulate+14>:	mov    %rdi,-0x8(%rbp)
  0x000055555555513b <Simulate+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555513f <Simulate+22>:	mov    0x2f07(%rip),%eax
  0x0000555555555145 <Simulate+28>:	mov    %eax,%edx
  0x0000555555555147 <Simulate+30>:	add    $0x1,%edx
  0x000055555555514a <Simulate+33>:	mov    %edx,0x2efc(%rip)
  0x0000555555555150 <Simulate+39>:	cltq   
  0x0000555555555152 <Simulate+41>:	lea    0x0(,%rax,8),%rdx
  0x000055555555515a <Simulate+49>:	lea    0x2ebf(%rip),%rax
  0x0000555555555161 <Simulate+56>:	mov    (%rdx,%rax,1),%rdx
  0x0000555555555165 <Simulate+60>:	mov    -0x10(%rbp),%rax
  0x0000555555555169 <Simulate+64>:	mov    %rax,%rdi
  0x000055555555516c <Simulate+67>:	callq  *%rdx
  0x00005555555551a3 <Y+0>:	endbr64 
  0x00005555555551a7 <Y+4>:	push   %rbp
  0x00005555555551a8 <Y+5>:	lea    (%rsp),%rbp
  0x00005555555551ac <Y+9>:	lea    -0x10(%rsp),%rsp
  0x00005555555551b1 <Y+14>:	mov    %rdi,-0x8(%rbp)
  0x00005555555551b5 <Y+18>:	mov    -0x8(%rbp),%rdx
  0x00005555555551b9 <Y+22>:	mov    -0x8(%rbp),%rax
  0x00005555555551bd <Y+26>:	mov    %rdx,%rsi
  0x00005555555551c0 <Y+29>:	mov    %rax,%rdi
  0x00005555555551c3 <Y+32>:	callq  0x555555555174 <X>
  0x0000555555555174 <X+0>:	endbr64 
  0x0000555555555178 <X+4>:	push   %rbp
  0x0000555555555179 <X+5>:	lea    (%rsp),%rbp
  0x000055555555517d <X+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555182 <X+14>:	mov    %rdi,-0x8(%rbp)
  0x0000555555555186 <X+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555518a <X+22>:	mov    -0x10(%rbp),%rdx
  0x000055555555518e <X+26>:	mov    -0x8(%rbp),%rax
  0x0000555555555192 <X+30>:	mov    %rdx,%rsi
  0x0000555555555195 <X+33>:	mov    %rax,%rdi
  0x0000555555555198 <X+36>:	callq  0x555555555129 <Simulate>
  0x0000555555555129 <Simulate+0>:	endbr64 
  0x000055555555512d <Simulate+4>:	push   %rbp
  0x000055555555512e <Simulate+5>:	lea    (%rsp),%rbp
  0x0000555555555132 <Simulate+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555137 <Simulate+14>:	mov    %rdi,-0x8(%rbp)
  0x000055555555513b <Simulate+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555513f <Simulate+22>:	mov    0x2f07(%rip),%eax
  0x0000555555555145 <Simulate+28>:	mov    %eax,%edx
  0x0000555555555147 <Simulate+30>:	add    $0x1,%edx
  0x000055555555514a <Simulate+33>:	mov    %edx,0x2efc(%rip)
  0x0000555555555150 <Simulate+39>:	cltq   
  0x0000555555555152 <Simulate+41>:	lea    0x0(,%rax,8),%rdx
  0x000055555555515a <Simulate+49>:	lea    0x2ebf(%rip),%rax
  0x0000555555555161 <Simulate+56>:	mov    (%rdx,%rax,1),%rdx
  0x0000555555555165 <Simulate+60>:	mov    -0x10(%rbp),%rax
  0x0000555555555169 <Simulate+64>:	mov    %rax,%rdi
  0x000055555555516c <Simulate+67>:	callq  *%rdx
  0x00005555555551a3 <Y+0>:	endbr64 
  0x00005555555551a7 <Y+4>:	push   %rbp
  0x00005555555551a8 <Y+5>:	lea    (%rsp),%rbp
  0x00005555555551ac <Y+9>:	lea    -0x10(%rsp),%rsp
  0x00005555555551b1 <Y+14>:	mov    %rdi,-0x8(%rbp)
  0x00005555555551b5 <Y+18>:	mov    -0x8(%rbp),%rdx
  0x00005555555551b9 <Y+22>:	mov    -0x8(%rbp),%rax
  0x00005555555551bd <Y+26>:	mov    %rdx,%rsi
  0x00005555555551c0 <Y+29>:	mov    %rax,%rdi
  0x00005555555551c3 <Y+32>:	callq  0x555555555174 <X>
  0x0000555555555174 <X+0>:	endbr64 
  0x0000555555555178 <X+4>:	push   %rbp
  0x0000555555555179 <X+5>:	lea    (%rsp),%rbp
  0x000055555555517d <X+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555182 <X+14>:	mov    %rdi,-0x8(%rbp)
  0x0000555555555186 <X+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555518a <X+22>:	mov    -0x10(%rbp),%rdx
  0x000055555555518e <X+26>:	mov    -0x8(%rbp),%rax
  0x0000555555555192 <X+30>:	mov    %rdx,%rsi
  0x0000555555555195 <X+33>:	mov    %rax,%rdi
  0x0000555555555198 <X+36>:	callq  0x555555555129 <Simulate>
  0x0000555555555129 <Simulate+0>:	endbr64 
  0x000055555555512d <Simulate+4>:	push   %rbp
  0x000055555555512e <Simulate+5>:	lea    (%rsp),%rbp
  0x0000555555555132 <Simulate+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555137 <Simulate+14>:	mov    %rdi,-0x8(%rbp)
  0x000055555555513b <Simulate+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555513f <Simulate+22>:	mov    0x2f07(%rip),%eax
  0x0000555555555145 <Simulate+28>:	mov    %eax,%edx
  0x0000555555555147 <Simulate+30>:	add    $0x1,%edx
  0x000055555555514a <Simulate+33>:	mov    %edx,0x2efc(%rip)
  0x0000555555555150 <Simulate+39>:	cltq   
  0x0000555555555152 <Simulate+41>:	lea    0x0(,%rax,8),%rdx
  0x000055555555515a <Simulate+49>:	lea    0x2ebf(%rip),%rax
  0x0000555555555161 <Simulate+56>:	mov    (%rdx,%rax,1),%rdx
  0x0000555555555165 <Simulate+60>:	mov    -0x10(%rbp),%rax
  0x0000555555555169 <Simulate+64>:	mov    %rax,%rdi
  0x000055555555516c <Simulate+67>:	callq  *%rdx
  0x00005555555551a3 <Y+0>:	endbr64 
  0x00005555555551a7 <Y+4>:	push   %rbp
  0x00005555555551a8 <Y+5>:	lea    (%rsp),%rbp
  0x00005555555551ac <Y+9>:	lea    -0x10(%rsp),%rsp
  0x00005555555551b1 <Y+14>:	mov    %rdi,-0x8(%rbp)
  0x00005555555551b5 <Y+18>:	mov    -0x8(%rbp),%rdx
  0x00005555555551b9 <Y+22>:	mov    -0x8(%rbp),%rax
  0x00005555555551bd <Y+26>:	mov    %rdx,%rsi
  0x00005555555551c0 <Y+29>:	mov    %rax,%rdi
  0x00005555555551c3 <Y+32>:	callq  0x555555555174 <X>
  0x0000555555555174 <X+0>:	endbr64 
  0x0000555555555178 <X+4>:	push   %rbp
  0x0000555555555179 <X+5>:	lea    (%rsp),%rbp
  0x000055555555517d <X+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555182 <X+14>:	mov    %rdi,-0x8(%rbp)
  0x0000555555555186 <X+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555518a <X+22>:	mov    -0x10(%rbp),%rdx
  0x000055555555518e <X+26>:	mov    -0x8(%rbp),%rax
  0x0000555555555192 <X+30>:	mov    %rdx,%rsi
  0x0000555555555195 <X+33>:	mov    %rax,%rdi
  0x0000555555555198 <X+36>:	callq  0x555555555129 <Simulate>
  0x0000555555555129 <Simulate+0>:	endbr64 
  0x000055555555512d <Simulate+4>:	push   %rbp
  0x000055555555512e <Simulate+5>:	lea    (%rsp),%rbp
  0x0000555555555132 <Simulate+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555137 <Simulate+14>:	mov    %rdi,-0x8(%rbp)
  0x000055555555513b <Simulate+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555513f <Simulate+22>:	mov    0x2f07(%rip),%eax
  0x0000555555555145 <Simulate+28>:	mov    %eax,%edx
  0x0000555555555147 <Simulate+30>:	add    $0x1,%edx
  0x000055555555514a <Simulate+33>:	mov    %edx,0x2efc(%rip)
  0x0000555555555150 <Simulate+39>:	cltq   
  0x0000555555555152 <Simulate+41>:	lea    0x0(,%rax,8),%rdx
  0x000055555555515a <Simulate+49>:	lea    0x2ebf(%rip),%rax
  0x0000555555555161 <Simulate+56>:	mov    (%rdx,%rax,1),%rdx
  0x0000555555555165 <Simulate+60>:	mov    -0x10(%rbp),%rax
  0x0000555555555169 <Simulate+64>:	mov    %rax,%rdi
  0x000055555555516c <Simulate+67>:	callq  *%rdx
  0x00005555555551a3 <Y+0>:	endbr64 
  0x00005555555551a7 <Y+4>:	push   %rbp
  0x00005555555551a8 <Y+5>:	lea    (%rsp),%rbp
  0x00005555555551ac <Y+9>:	lea    -0x10(%rsp),%rsp
  0x00005555555551b1 <Y+14>:	mov    %rdi,-0x8(%rbp)
  0x00005555555551b5 <Y+18>:	mov    -0x8(%rbp),%rdx
  0x00005555555551b9 <Y+22>:	mov    -0x8(%rbp),%rax
  0x00005555555551bd <Y+26>:	mov    %rdx,%rsi
  0x00005555555551c0 <Y+29>:	mov    %rax,%rdi
  0x00005555555551c3 <Y+32>:	callq  0x555555555174 <X>
  0x0000555555555174 <X+0>:	endbr64 
  0x0000555555555178 <X+4>:	push   %rbp
  0x0000555555555179 <X+5>:	lea    (%rsp),%rbp
  0x000055555555517d <X+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555182 <X+14>:	mov    %rdi,-0x8(%rbp)
  0x0000555555555186 <X+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555518a <X+22>:	mov    -0x10(%rbp),%rdx
  0x000055555555518e <X+26>:	mov    -0x8(%rbp),%rax
  0x0000555555555192 <X+30>:	mov    %rdx,%rsi
  0x0000555555555195 <X+33>:	mov    %rax,%rdi
  0x0000555555555198 <X+36>:	callq  0x555555555129 <Simulate>
  0x0000555555555129 <Simulate+0>:	endbr64 
  0x000055555555512d <Simulate+4>:	push   %rbp
  0x000055555555512e <Simulate+5>:	lea    (%rsp),%rbp
  0x0000555555555132 <Simulate+9>:	lea    -0x10(%rsp),%rsp
  0x0000555555555137 <Simulate+14>:	mov    %rdi,-0x8(%rbp)
  0x000055555555513b <Simulate+18>:	mov    %rsi,-0x10(%rbp)
  0x000055555555513f <Simulate+22>:	mov    0x2f07(%rip),%eax
  0x0000555555555145 <Simulate+28>:	mov    %eax,%edx
  0x0000555555555147 <Simulate+30>:	add    $0x1,%edx
  0x000055555555514a <Simulate+33>:	mov    %edx,0x2efc(%rip)
  0x0000555555555150 <Simulate+39>:	cltq   
  0x0000555555555152 <Simulate+41>:	lea    0x0(,%rax,8),%rdx
  0x000055555555515a <Simulate+49>:	lea    0x2ebf(%rip),%rax
  0x0000555555555161 <Simulate+56>:	mov    (%rdx,%rax,1),%rdx
  0x0000555555555165 <Simulate+60>:	mov    -0x10(%rbp),%rax
  0x0000555555555169 <Simulate+64>:	mov    %rax,%rdi
  0x000055555555516c <Simulate+67>:	callq  *%rdx
  ...

-- 
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