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


Groups > comp.theory > #31239 > unrolled thread

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

Started byolcott <NoOne@NoWhere.com>
First post2021-04-17 09:17 -0500
Last post2021-04-19 13:47 -0400
Articles 17 on this page of 37 — 6 participants

Back to article view | Back to comp.theory


Contents

  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

Page 2 of 2 — ← Prev page 1 [2]


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

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 19:57 -0500
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<nsOdnaUqY4vuSOH9nZ2dnUU7-K-dnZ2d@giganews.com>
In reply to#31409
On 4/18/2021 7:38 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 4/18/2021 7:11 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> It took me more that a few minutes to understand that the AT&T operand
>>>> order is reversed. Then I discovered that the RIP relative addressing
>>>> was used like a jump table when a value was assigned to the RIP
>>>> register.
>>>
>>> RIP is a red-herring.  The code is compiled from standard C.  If I
>>> compile it for the 32-bit architecture, no IP relative addressing is
>>> used, but the pattern of calls remains the same.
>>
>>    0x000055555555517d <main+0>:	endbr64
>>    0x0000555555555181 <main+4>:	push   %rbp
>>    0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>>    0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>
>> The above instruction moves the contents of the edx register into an
>> offset relative to the rip (instruction pointer register). This could
>> easily make self-modifying code.
> 
> However it does not.  RIP is a red-herring.  The code is compiled from
> standard C.  If I compile it for the 32-bit architecture, no IP relative
> addressing is used, but the pattern of calls remains the same.
> 

Simply post the C source.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


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

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-04-18 20:47 -0700
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<s5iug5$15af$1@gioia.aioe.org>
In reply to#31413
On 4/18/2021 5:57 PM, olcott wrote:
> On 4/18/2021 7:38 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/18/2021 7:11 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> It took me more that a few minutes to understand that the AT&T operand
>>>>> order is reversed. Then I discovered that the RIP relative addressing
>>>>> was used like a jump table when a value was assigned to the RIP
>>>>> register.
>>>>
>>>> RIP is a red-herring.  The code is compiled from standard C.  If I
>>>> compile it for the 32-bit architecture, no IP relative addressing is
>>>> used, but the pattern of calls remains the same.
>>>
>>>    0x000055555555517d <main+0>:    endbr64
>>>    0x0000555555555181 <main+4>:    push   %rbp
>>>    0x0000555555555182 <main+5>:    mov    %rsp,%rbp
>>>    0x0000555555555185 <main+8>:    callq  0x555555555129 <Y>
>>>    0x0000555555555129 <Y+0>:    endbr64
>>>    0x000055555555512d <Y+4>:    push   %rbp
>>>    0x000055555555512e <Y+5>:    mov    %rsp,%rbp
>>>    0x0000555555555131 <Y+8>:    mov    0x2f15(%rip),%eax
>>>    0x0000555555555137 <Y+14>:    lea    0x1(%rax),%edx
>>>    0x000055555555513a <Y+17>:    mov    %edx,0x2f0c(%rip)
>>>
>>> The above instruction moves the contents of the edx register into an
>>> offset relative to the rip (instruction pointer register). This could
>>> easily make self-modifying code.
>>
>> However it does not.  RIP is a red-herring.  The code is compiled from
>> standard C.  If I compile it for the 32-bit architecture, no IP relative
>> addressing is used, but the pattern of calls remains the same.
>>
> 
> Simply post the C source.
> 

Iirc, Kaz has already implemented some of your stuff in C.

Btw, have you ever heard of a site called GodBolt?

https://godbolt.org

Its really nice.

[toc] | [prev] | [next] | [standalone]


#31281

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-04-18 01:34 +0100
Message-ID<87y2dg8m7i.fsf@bsb.me.uk>
In reply to#31239
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:

  0x000055555555517d <main+0>:	endbr64 
  0x0000555555555181 <main+4>:	push   %rbp
  0x0000555555555182 <main+5>:	mov    %rsp,%rbp
  0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
  0x0000555555555129 <Y+0>:	endbr64 
  0x000055555555512d <Y+4>:	push   %rbp
  0x000055555555512e <Y+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Y+23>:	cltq   
  0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Y+44>:	callq  *%rax
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
  0x0000555555555129 <Y+0>:	endbr64 
  0x000055555555512d <Y+4>:	push   %rbp
  0x000055555555512e <Y+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Y+23>:	cltq   
  0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Y+44>:	callq  *%rax
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
  0x0000555555555129 <Y+0>:	endbr64 
  0x000055555555512d <Y+4>:	push   %rbp
  0x000055555555512e <Y+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Y+23>:	cltq   
  0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Y+44>:	callq  *%rax
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
  0x0000555555555129 <Y+0>:	endbr64 
  0x000055555555512d <Y+4>:	push   %rbp
  0x000055555555512e <Y+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Y+23>:	cltq   
  0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Y+44>:	callq  *%rax
  0x000055555555515c <X+0>:	endbr64 
  0x0000555555555160 <X+4>:	push   %rbp
  0x0000555555555161 <X+5>:	mov    %rsp,%rbp
  0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
  0x0000555555555129 <Y+0>:	endbr64 
  0x000055555555512d <Y+4>:	push   %rbp
  0x000055555555512e <Y+5>:	mov    %rsp,%rbp
  0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
  0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
  0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
  0x0000555555555140 <Y+23>:	cltq   
  0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
  0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
  0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
  0x0000555555555155 <Y+44>:	callq  *%rax
  0x000055555555516e <Z+0>:	endbr64 
  0x0000555555555172 <Z+4>:	push   %rbp
  0x0000555555555173 <Z+5>:	mov    %rsp,%rbp
  0x0000555555555176 <Z+8>:	mov    $0x1,%eax
  ...

Note how X is called from Y+44 more than once with no branching or
returns.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#31283

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 19:37 -0500
Message-ID<tLKdnTL0L96r4ub9nZ2dnUU7-d-dnZ2d@giganews.com>
In reply to#31281
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 couldn't make that out it is not the syntax that I am familiar with 
does it get past this newly updated criteria?

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.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31287

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-04-18 02:13 +0100
Message-ID<87czus8kdr.fsf@bsb.me.uk>
In reply to#31283
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.

[toc] | [prev] | [next] | [standalone]


#31289

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 20:28 -0500
Message-ID<kvqdnQAdt47ZFub9nZ2dnUU7-efNnZ2d@giganews.com>
In reply to#31287
On 4/17/2021 8:13 PM, Ben Bacarisse wrote:
> 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.

There are no returns in the execution trace.

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

If my system does not work on the x64 architecture than I simply assume 
that I am only using the x86 architecture.

>> (2) With the same parameters to X().
> 
> No parameters are being passed to any of the functions.
> 

I am modeling the case where parameters are passed, so if no parameters 
are passed this is no good.

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

In your x64 example. Can you do the same thing in x86?

>> 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:
I am only working in Intel x86.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31295

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-04-18 02:49 +0100
Message-ID<87k0p07467.fsf@bsb.me.uk>
In reply to#31289
olcott <NoOne@NoWhere.com> writes:

> On 4/17/2021 8:13 PM, Ben Bacarisse wrote:
>> 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.
>
> There are no returns in the execution trace.

Ah, then it's a silly set of criteria.  You can't detect anything other
than by executing indefinitely to see if there is, eventually a return.
Surely the plan is to be able to detect infinite recursion when the
duplicate call is made, based on the there being identical parameters
and no conditional jumps (and maybe some more details as well).

I thought you had this sorted out already.

>
>>> 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).
>
> If my system does not work on the x64 architecture than I simply
> assume that I am only using the x86 architecture.
>
>>> (2) With the same parameters to X().
>>
>> No parameters are being passed to any of the functions.
>>
>
> I am modeling the case where parameters are passed, so if no
> parameters are passed this is no good.

I could pass a few and it would make no difference.  How many would I
need to pass for you to bother paying attention?

>>> (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.
>
> In your x64 example. Can you do the same thing in x86?

I am not going to put in more work when it makes no difference.  Anyone
who know the Intel architecture can see that there is nothing
significant in the bit width here.

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

> I am only working in Intel x86.

You think the code does something magic that won't be the same in 32
bits?  Or are you just looking for a reason not to bother checking your
criteria?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#31298

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 21:01 -0500
Message-ID<QaSdnZSATouWDub9nZ2dnUU7-R2dnZ2d@giganews.com>
In reply to#31295
On 4/17/2021 8:49 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 4/17/2021 8:13 PM, Ben Bacarisse wrote:
>>> 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.
>>
>> There are no returns in the execution trace.
> 
> Ah, then it's a silly set of criteria.  You can't detect anything other
> than by executing indefinitely to see if there is, eventually a return.
> Surely the plan is to be able to detect infinite recursion when the
> duplicate call is made, based on the there being identical parameters
> and no conditional jumps (and maybe some more details as well).
> 
> I thought you had this sorted out already.
> 
>>
>>>> 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).
>>
>> If my system does not work on the x64 architecture than I simply
>> assume that I am only using the x86 architecture.
>>
>>>> (2) With the same parameters to X().
>>>
>>> No parameters are being passed to any of the functions.
>>>
>>
>> I am modeling the case where parameters are passed, so if no
>> parameters are passed this is no good.
> 
> I could pass a few and it would make no difference.  How many would I
> need to pass for you to bother paying attention?
> 
>>>> (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.
>>
>> In your x64 example. Can you do the same thing in x86?
> 
> I am not going to put in more work when it makes no difference.  Anyone
> who know the Intel architecture can see that there is nothing
> significant in the bit width here.
> 
>>>> 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:
> 
>> I am only working in Intel x86.
> 
> You think the code does something magic that won't be the same in 32
> bits?  Or are you just looking for a reason not to bother checking your
> criteria?
> 

I know that the x64 architecture has rip relative addressing and this 
changes key things completely. If you don't want to translate it to x86 
I may look at it some time later.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31286

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 19:49 -0500
Message-ID<saCdnS6GYdexH-b9nZ2dnUU7-NnNnZ2d@giganews.com>
In reply to#31281
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:
> 
>    0x000055555555517d <main+0>:	endbr64
>    0x0000555555555181 <main+4>:	push   %rbp
>    0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>    0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555515c <X+0>:	endbr64
>    0x0000555555555160 <X+4>:	push   %rbp
>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555515c <X+0>:	endbr64
>    0x0000555555555160 <X+4>:	push   %rbp
>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555515c <X+0>:	endbr64
>    0x0000555555555160 <X+4>:	push   %rbp
>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555515c <X+0>:	endbr64
>    0x0000555555555160 <X+4>:	push   %rbp
>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555516e <Z+0>:	endbr64
>    0x0000555555555172 <Z+4>:	push   %rbp
>    0x0000555555555173 <Z+5>:	mov    %rsp,%rbp
>    0x0000555555555176 <Z+8>:	mov    $0x1,%eax
>    ...
> 
> Note how X is called from Y+44 more than once with no branching or
> returns.
> 

Lets simply assume x86 architecture and Intel syntax.

This is my latest revised infinite recursion halt deciding criteria:

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.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31292

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-04-18 02:36 +0100
Message-ID<87pmys74sc.fsf@bsb.me.uk>
In reply to#31286
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:
>>
>>    0x000055555555517d <main+0>:	endbr64
>>    0x0000555555555181 <main+4>:	push   %rbp
>>    0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>>    0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555515c <X+0>:	endbr64
>>    0x0000555555555160 <X+4>:	push   %rbp
>>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555515c <X+0>:	endbr64
>>    0x0000555555555160 <X+4>:	push   %rbp
>>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555515c <X+0>:	endbr64
>>    0x0000555555555160 <X+4>:	push   %rbp
>>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555515c <X+0>:	endbr64
>>    0x0000555555555160 <X+4>:	push   %rbp
>>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555516e <Z+0>:	endbr64
>>    0x0000555555555172 <Z+4>:	push   %rbp
>>    0x0000555555555173 <Z+5>:	mov    %rsp,%rbp
>>    0x0000555555555176 <Z+8>:	mov    $0x1,%eax
>>    ...
>>
>> Note how X is called from Y+44 more than once with no branching or
>> returns.
>>
>
> Lets simply assume x86 architecture and Intel syntax.
>
> This is my latest revised infinite recursion halt deciding criteria:
>
> 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.

And you can't tell is the trace above meets those criteria?  Oh well,
you might be wrong and you'll never know it!  I think a few minutes
study of the trace would be worth it.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#31294

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 20:43 -0500
Message-ID<v-WdnSUnevkhE-b9nZ2dnUU7-XWdnZ2d@giganews.com>
In reply to#31292
On 4/17/2021 8:36 PM, Ben Bacarisse wrote:
> 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:
>>>
>>>     0x000055555555517d <main+0>:	endbr64
>>>     0x0000555555555181 <main+4>:	push   %rbp
>>>     0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>>>     0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>>>     0x0000555555555129 <Y+0>:	endbr64
>>>     0x000055555555512d <Y+4>:	push   %rbp
>>>     0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>>     0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>>     0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>>     0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>>     0x0000555555555140 <Y+23>:	cltq
>>>     0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>>     0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>>     0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>>     0x0000555555555155 <Y+44>:	callq  *%rax
>>>     0x000055555555515c <X+0>:	endbr64
>>>     0x0000555555555160 <X+4>:	push   %rbp
>>>     0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>>     0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>>     0x0000555555555129 <Y+0>:	endbr64
>>>     0x000055555555512d <Y+4>:	push   %rbp
>>>     0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>>     0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>>     0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>>     0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>>     0x0000555555555140 <Y+23>:	cltq
>>>     0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>>     0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>>     0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>>     0x0000555555555155 <Y+44>:	callq  *%rax
>>>     0x000055555555515c <X+0>:	endbr64
>>>     0x0000555555555160 <X+4>:	push   %rbp
>>>     0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>>     0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>>     0x0000555555555129 <Y+0>:	endbr64
>>>     0x000055555555512d <Y+4>:	push   %rbp
>>>     0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>>     0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>>     0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>>     0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>>     0x0000555555555140 <Y+23>:	cltq
>>>     0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>>     0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>>     0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>>     0x0000555555555155 <Y+44>:	callq  *%rax
>>>     0x000055555555515c <X+0>:	endbr64
>>>     0x0000555555555160 <X+4>:	push   %rbp
>>>     0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>>     0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>>     0x0000555555555129 <Y+0>:	endbr64
>>>     0x000055555555512d <Y+4>:	push   %rbp
>>>     0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>>     0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>>     0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>>     0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>>     0x0000555555555140 <Y+23>:	cltq
>>>     0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>>     0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>>     0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>>     0x0000555555555155 <Y+44>:	callq  *%rax
>>>     0x000055555555515c <X+0>:	endbr64
>>>     0x0000555555555160 <X+4>:	push   %rbp
>>>     0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>>     0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>>>     0x0000555555555129 <Y+0>:	endbr64
>>>     0x000055555555512d <Y+4>:	push   %rbp
>>>     0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>>     0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>>     0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>>>     0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>>     0x0000555555555140 <Y+23>:	cltq
>>>     0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>>     0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>>     0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>>     0x0000555555555155 <Y+44>:	callq  *%rax
>>>     0x000055555555516e <Z+0>:	endbr64
>>>     0x0000555555555172 <Z+4>:	push   %rbp
>>>     0x0000555555555173 <Z+5>:	mov    %rsp,%rbp
>>>     0x0000555555555176 <Z+8>:	mov    $0x1,%eax
>>>     ...
>>>
>>> Note how X is called from Y+44 more than once with no branching or
>>> returns.
>>>
>>
>> Lets simply assume x86 architecture and Intel syntax.
>>
>> This is my latest revised infinite recursion halt deciding criteria:
>>
>> 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.
> 
> And you can't tell is the trace above meets those criteria?  Oh well,
> you might be wrong and you'll never know it!  I think a few minutes
> study of the trace would be worth it.
> 

I already did the relative rip addressing of x64 may allow some strange 
things that I can simply ignore by sticking with x86.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31345

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 13:21 -0500
Message-ID<RsGdncgeEM4B5eH9nZ2dnUU7-YPNnZ2d@giganews.com>
In reply to#31281
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:
> 
>    0x000055555555517d <main+0>:	endbr64
>    0x0000555555555181 <main+4>:	push   %rbp
>    0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>    0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>    0x0000555555555129 <Y+0>:	endbr64
>    0x000055555555512d <Y+4>:	push   %rbp
>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx

It is this line-of-code that has the same effect as simulating a 
conditional branch using a jump table:
>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>    0x0000555555555140 <Y+23>:	cltq
>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>    0x0000555555555155 <Y+44>:	callq  *%rax
>    0x000055555555515c <X+0>:	endbr64
>    0x0000555555555160 <X+4>:	push   %rbp
>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>

Simply restricting the model to the x86 architecture gets rid of this 
problem. Since my purpose is to prove that there is at least one case 
where a halt decider can correctly decide that it was called in infinite 
recursion discarding an architectural model is a reasonable choice.

This is the revised infinite recursion detection criteria:

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.

When X() detects that its simulation of Y() meets the above criteria 
then X() can definitely stop simulating Y() to prevent its own infinite 
execution.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31392

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-04-18 23:30 +0100
Message-ID<87sg3n444k.fsf@bsb.me.uk>
In reply to#31345
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:
>>
>>    0x000055555555517d <main+0>:	endbr64
>>    0x0000555555555181 <main+4>:	push   %rbp
>>    0x0000555555555182 <main+5>:	mov    %rsp,%rbp
>>    0x0000555555555185 <main+8>:	callq  0x555555555129 <Y>
>>    0x0000555555555129 <Y+0>:	endbr64
>>    0x000055555555512d <Y+4>:	push   %rbp
>>    0x000055555555512e <Y+5>:	mov    %rsp,%rbp
>>    0x0000555555555131 <Y+8>:	mov    0x2f15(%rip),%eax
>>    0x0000555555555137 <Y+14>:	lea    0x1(%rax),%edx
>
> It is this line-of-code that has the same effect as simulating a
> conditional branch using a jump table:

>>    0x000055555555513a <Y+17>:	mov    %edx,0x2f0c(%rip)
>>    0x0000555555555140 <Y+23>:	cltq
>>    0x0000555555555142 <Y+25>:	lea    0x0(,%rax,8),%rdx
>>    0x000055555555514a <Y+33>:	lea    0x2ecf(%rip),%rax
>>    0x0000555555555151 <Y+40>:	mov    (%rdx,%rax,1),%rax
>>    0x0000555555555155 <Y+44>:	callq  *%rax
>>    0x000055555555515c <X+0>:	endbr64
>>    0x0000555555555160 <X+4>:	push   %rbp
>>    0x0000555555555161 <X+5>:	mov    %rsp,%rbp
>>    0x0000555555555164 <X+8>:	callq  0x555555555129 <Y>
>
> Simply restricting the model to the x86 architecture gets rid of this
> problem.

No.  The fix is to write the correct criterion.

> Since my purpose is to prove that there is at least one case where a
> halt decider can correctly decide that it was called in infinite
> recursion discarding an architectural model is a reasonable choice.

That can't be your purpose because no sane person would doubt that that
can be done.

> This is the revised infinite recursion detection criteria:
>
> 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.

The other trace -- where you wanted another function called Simulate --
meets these criteria because the call through RAX is in another function.

The trouble is not that this can't be done, but simply that you can't
write the correct criteria.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#31346

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 13:24 -0500
Message-ID<RsGdncseEM7e5OH9nZ2dnUU7-YOdnZ2d@giganews.com>
In reply to#31239
On 4/18/2021 1:02 PM, wij wrote:
> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>> On 4/18/2021 9:52 AM, wij wrote:
>>> On Saturday, 17 April 2021 at 22:18:02 UTC+8, 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.
>>>>
>>>> -- 
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>>
>>> I can think of no easy way to detect infinite recursion in C++.
>>>
>> The detection of the infinite recursion occurs at the machine language
>> level.
>>>  From the problem description:
>>>
>>> Y: // no contiditonal branch
>>> read_arg of Y
>>> push_arg for X
>>> call X
>>> pop_arg for X
>>> ret
>>>
>>> X:
>>> ... // no return instruction
>>> push_arg for Y
>>> call Y
>>> pop_arg for Y
>>> ... // no return instruction, probably unreachable
>>>
>>> Obviously, both X() and Y() can never return. Then, what is the point?
>>>
>> The idea is to be able to define X() as a halt decider for functions
>> that call X() in infinite recursion.
> 
> Then, X() "You call it a halt decider", is defined not to return.

When X() uses the following criteria to decide to stop simulating Y() 
then X() has correctly decided that Y() would otherwise cause X() to 
have infinite execution.

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.


> 
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31462

FromMikko <mikko.levanto@outlook.com>
Date2021-04-19 19:43 +0300
Message-ID<mikko.levanto-0211E1.19433119042021@news.eternal-september.org>
In reply to#31239
In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>,
 olcott <NoOne@NoWhere.com> 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.

Those criteria demand more than is needed but also fail to mention some 
necessary criteria (perhaps one could regard them self evident).

The criteria don't apply if there is a possibility of interrupts or
concurrent execution so that executions may interfere. Without such
possibility X cannot stop execution of a subroutine it calls.

If there are no conditional branches then it does not matter whether the
parameters are the same -- the recursion is infinite anyway. If there are
conditional branches the recursion is infinite if the parameters and
global and static variables that affect the branch conditions must be
the same or at least always determine the same branch. The parameters
and variables that do no affect the branches need not be the same.

Mikko

[toc] | [prev] | [next] | [standalone]


#31463

Fromolcott <NoOne@NoWhere.com>
Date2021-04-19 11:53 -0500
Message-ID<_MGdnW9xkusEKOD9nZ2dnUU7-IUAAAAA@giganews.com>
In reply to#31462
On 4/19/2021 11:43 AM, Mikko wrote:
> In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>,
>   olcott <NoOne@NoWhere.com> 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.
> 
> Those criteria demand more than is needed but also fail to mention some
> necessary criteria (perhaps one could regard them self evident).
> 
> The criteria don't apply if there is a possibility of interrupts or
> concurrent execution so that executions may interfere. Without such
> possibility X cannot stop execution of a subroutine it calls.
> 

Infinite recursion detection criteria:
(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().

The following code (including an x86 emulator) is written in "C"

void X(u32 P, u32 I)
{
   Simulate(P, I);
}

void Y(u32 P)
{
   X(P, P);
}

int main()
{
   X((u32)Y, (u32)Y);
}

When X() simulates the x86 machine language of Y() and examines 
resulting execution trace after simulating each machine instruction of 
Y() then X() can apply the criteria provided above to correctly decide 
to stop simulating Y() on the basis that Y() would otherwise cause X() 
have infinite execution.

Whenever the above criteria is met then X() must stop simulating Y()  to 
prevent its own infinite execution.

> If there are no conditional branches then it does not matter whether the
> parameters are the same -- the recursion is infinite anyway. 

No conditional branches in Y(), there are conditional branches in X(), 
they are ignored.

> If there are
> conditional branches the recursion is infinite if the parameters and
> global and static variables that affect the branch conditions must be
> the same or at least always determine the same branch. The parameters
> and variables that do no affect the branches need not be the same.
> 
> Mikko
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#31468

FromRichard Damon <Richard@Damon-Family.org>
Date2021-04-19 13:47 -0400
Message-ID<GmjfI.9091$AU5.7391@fx29.iad>
In reply to#31463
On 4/19/21 12:53 PM, olcott wrote:
> On 4/19/2021 11:43 AM, Mikko wrote:
>> In article <HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>,
>>   olcott <NoOne@NoWhere.com> 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.
>>
>> Those criteria demand more than is needed but also fail to mention some
>> necessary criteria (perhaps one could regard them self evident).
>>
>> The criteria don't apply if there is a possibility of interrupts or
>> concurrent execution so that executions may interfere. Without such
>> possibility X cannot stop execution of a subroutine it calls.
>>
> 
> Infinite recursion detection criteria:
> (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().
> 
> The following code (including an x86 emulator) is written in "C"
> 
> void X(u32 P, u32 I)
> {
>  Simulate(P, I);
> }
> 
> void Y(u32 P)
> {
>  X(P, P);
> }
> 
> int main()
> {
>  X((u32)Y, (u32)Y);
> }
> 
> When X() simulates the x86 machine language of Y() and examines
> resulting execution trace after simulating each machine instruction of
> Y() then X() can apply the criteria provided above to correctly decide
> to stop simulating Y() on the basis that Y() would otherwise cause X()
> have infinite execution.


Except that the defined X() does none of this.

> 
> Whenever the above criteria is met then X() must stop simulating Y()  to
> prevent its own infinite execution.
> 

Which it can't do as written, since X() is JUST a call to the simulator.

>> If there are no conditional branches then it does not matter whether the
>> parameters are the same -- the recursion is infinite anyway. 
> 
> No conditional branches in Y(), there are conditional branches in X(),
> they are ignored.
> 
>> If there are
>> conditional branches the recursion is infinite if the parameters and
>> global and static variables that affect the branch conditions must be
>> the same or at least always determine the same branch. The parameters
>> and variables that do no affect the branches need not be the same.
>>
>> Mikko
>>
> 
> 

[toc] | [prev] | [standalone]


Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.theory


csiph-web