Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

18 views
Skip to first unread message

olcott

unread,
Apr 17, 2021, 10:17:59 AM4/17/21
to
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

olcott

unread,
Apr 17, 2021, 8:18:56 PM4/17/21
to
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.


olcott

unread,
Apr 17, 2021, 8:50:03 PM4/17/21
to
On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <No...@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.


Kaz Kylheku

unread,
Apr 17, 2021, 10:02:30 PM4/17/21
to
["Followup-To:" header set to comp.theory.]
On 2021-04-18, olcott <No...@NoWhere.com> wrote:
> 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);
^^^^

This necessariy has a shitload of conditional execution in it.

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

Wrong:

(3) a) With no conditional branch or indirect jump instructions
anywhere in the recursive loop, including the bodies of Y,
X, or any subroutine they call, or any child thereof.

b) There be no extensions to the Intel x86 instruction set.
which perpetrate conditional behavior inside the simulator
which subsequently affects the control flow.

The criterion that only Y has an basic block of instructions being
executed repeatedly are ridiculously insufficient for establishing that
there is a runaway recursion.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Chris M. Thomasson

unread,
Apr 17, 2021, 10:05:55 PM4/17/21
to
On 4/17/2021 5:18 PM, olcott wrote:
> 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.
>
>

Does your simulator handle the CMPXCHG instruction?

olcott

unread,
Apr 17, 2021, 10:12:14 PM4/17/21
to
The actual x86 emulator handles all of the x86 32-bit instructions.
If this screws up my criteria then I simply screen it out.

I may end up creating a machine much closer to a Turing machine except
that it will have 32-bit signed relative addressing at the very least.

Chris M. Thomasson

unread,
Apr 17, 2021, 10:18:41 PM4/17/21
to
Ahh, okay. So it can handle the LOCK prefix as well, right? CMPXCHG is a
32-bit instruction and, well, you know about the LOCK prefix so, thanks
for answering my question.

https://www.felixcloutier.com/x86/cmpxchg

https://www.felixcloutier.com/x86/lock

Does your simulator lock the bus, and/or the cache line in its emulation
of these instructions? Think of trying, and failing to lock the cache
line a bunch of times in a row, then finally resorting to the bus lock.
How do you do it in your simulator?


> If this screws up my criteria then I simply screen it out.

I do not know what you mean. CMPXCHG, XADD, XCHG, all of the x86 32-bit
instructions must be in your simulator right?


> I may end up creating a machine much closer to a Turing machine except
> that it will have 32-bit signed relative addressing at the very least.

Did you emulator x86 or not?

Bonita Montero

unread,
Apr 18, 2021, 12:12:42 PM4/18/21
to
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!

olcott

unread,
Apr 18, 2021, 12:16:49 PM4/18/21
to
On 4/18/2021 11:12 AM, Bonita Montero wrote:
> STOP POSTING IN comp.lang.c/c++ !!!

Since this <is> relevant to C/C++ you can simply STFU !

Real Troll

unread,
Apr 18, 2021, 12:26:18 PM4/18/21
to
Did you use for loop to print all that crap?

Bonita Montero

unread,
Apr 18, 2021, 1:33:16 PM4/18/21
to
> Since this <is> relevant to C/C++ you can simply STFU !

It isn't relvant specifically to C/C++, it is relevant to any
language. So stop posting here.

olcott

unread,
Apr 18, 2021, 1:35:16 PM4/18/21
to
KNOW !

olcott

unread,
Apr 18, 2021, 2:21:31 PM4/18/21
to
On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <No...@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.

olcott

unread,
Apr 18, 2021, 2:24:19 PM4/18/21
to
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:
>>> 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.


>
0 new messages