Subject: [clisp-list] Solution to TerminateThread bug.

From: [email-masked] (Thaddeus L. Olczyk)
Date: Wed Jan 30 07:20:28 2002

Attached is a diff file which shows what needs to be done to fix the
TerminateThread problem.
Applying the patch might be a problem ( at least I don't have patch
on my Windows box ). 
Here is how I successfully did it.
I copied the file to a linux box.
I then opened it with emacs and did M-x set-buffer-file-coding-system
to unix and saved.
You can try any other ways to change the CRLF thing.
Apply the patch via:
patch -n win32aux.d -l term.patch
Do the emacs thing again. This time change the coding system
to dos, and copy back.

Here is a description of the code around the bug, what it does, what
the problem is and how I fixed it. ( If anyone really cares.)
------------------------------------------------------------------------------
The problem sits in the DoInterruptible routine.
DoInterruptible is supposed to let you call a C function passed
as an argument, and accept a signal generated by C-c ( or BREAK )
to abort the function.

It does it this way:
interruptible_active is a flag that indicates it is running the passed
function.

The basic routine (DoInterruptible)looks like this:

CreateThread to execute C-function
interruptible_active=false
Set signal handler to temp_interrupt_handler
interruptible_active=true
WaitForSingleObject // waits for thread to die.
interruptible_active=false
clear signal handler
return

the  signal handler routine looks like
if(interrupitible_active)
{
   do_stuff
   TerminateThread
}

The problem is that the following scenario takes placeL
the thread starts to die, context-switch, interruptible_active
gets tested, context-switch, thread finishes dieing,
WaitForSingleObject returns, interrupptible_active gets set to
false, context-switch, TerminateThread tries to kill dead thread.

There is plenty of room for the first ( fatal) context switch. It can
happen anytime in the range of thread_dies, WaitForSingleObject
returns, interruptible_active is set to false. 

The solution is to first narrow the room for the context switch and
then eliminate it.

First rewrite the if routine

if(interrupitible_active)
{
   do_stuff
    if(interuptible_active)	
      TerminateThread
}

This way a context switch has to happen between the second if and
TerminateThread, and the thread has to die.

This does not completely solve the problem because
a context switch between thread_dies and WaitForSingleObject or
setting interruptible_active can still crash the process.

The next step is to reduce the time between the exit of the thread
and the time that interruptible_active is set false. So in the
function spawned in the thread ( there are five of them ) set
Interruptible_active to false.

There is still a deadly switch but a very small one. Between the last
line of the thread, and it's return coupled to the one between
interruptible_active and TerminateThread.
So put three Sleep(0) ( the Windows version of yield) in before the
thread dies. That seems to be enough context-switches before the
thread dies to ensure that if the interruptible_active is true at the
test TerminateThread is called before the thread dies ( even though  
it might already be dieing ).
-------------------------------------------------------------
Problem with the solution:
1) It is easier to wrap the fn in DoInterruptible with a special
keep=thread alieve routine:
void ExecuteThread(vois *data)
{
extract fn 
extract fn data
fn( fn data)
interruptible_active=false;
Sleep(0);
Sleep(0);
Sleep(0);
}

DoInterruptible(fn,fn data)
{
vptr=mingle fn and fn data.
CreateThread(ExecuteThread,vptr);
,,,
}

I don't have the time to look into the corners now.

2) The behaviour of clisp wrt C-c with the fix is the
ame as the behaviour of clisp without the fix on my dual machines.
However it's backward from the behaviour on Lisp machines.
In Lisp machines, it takes it up a level, on Windows it takes it down.
However this is a different bug.

---

From: Sam Steingold <[email-masked]>
Date: Wed Jan 30 09:46:05 2002

> * In message <[email-masked]>
> * On the subject of "[clisp-list] Solution to TerminateThread bug."
> * Sent on Wed, 30 Jan 2002 15:20:04 GMT
> * Honorable [email-masked] (Thaddeus L. Olczyk) writes:
>

thanks.
next time, please use context (or unified) diffs - more reliable.

> Applying the patch might be a problem ( at least I don't have patch

cygwin comes with diff, patch &c - no problems.

> the problem is and how I fixed it. ( If anyone really cares.)

Interesting analysis.

It boils down to the fact that TerminateThread() tries to kill a dead
thread and there is no way to check whether the thread is dead or alive.
Right?

Your solution basically tries to wait for the thread to die - instead
of just killing it outright, and you said it does not always work.

Is there a solution that would always work?

Maybe you could follow the direction outlined by Todd and eliminate the
need for TerminateThread() altogether?

Thanks.

-- 
Sam Steingold (http://www.podval.org/~sds)
Keep Jerusalem united! <http://www.onejerusalem.org/Petition.asp>
Read, think and remember! <http://www.iris.org.il> <http://www.memri.org/>
C combines the power of assembler with the portability of assembler.

---

From: [email-masked] (Thaddeus L. Olczyk)
Date: Wed Jan 30 10:57:08 2002

>next time, please use context (or unified) diffs - more reliable.
Sorry. I'm new to patch, and my bibble on UNIX--Kernigan and Pike
don't mention it ( at least not in their index).

>cygwin comes with diff, patch &c - no problems.
I must have missed patch.

>thread and there is no way to check whether the thread is dead or alive.
Not quite. The problem is that you test for whether the thread is
alive or not ( by the interruptible_active flag ), to soon. By the
time you get  around to calling the thread, it may have already died.
The problem is also the interweaving of contexts which means that
the thread has a chance to die before TerminateThread is called.

Understand this is a funcamental problem in your approach. Even
if you could find out whether the thread is alive or dead (via an API
call), you have the problem of the thread dieing before you could call
TerminateThread.

The way around this is to use some kind of synchronization, ie a
critical section or a mutex. However since TerminateThread does not
clean up afterwards you risk a deadlock.

A typical situation might be that the conditional surrounding
TerminateThread acquires a critical section. The child thread
is near exit and tries to acquire the same critical section to
set the interruptible_active flag. Since it can't it blocks.
The TerminateThread conditional then actually calls TerminateThread.
It then releases the the critical section. The child thread is now
dead by the attempt to acquire the critical section will now go
forward. The child thread now has the critical section, but it can't
kill it because the thread is dead. Next time around whatever tries
to acquire the critcal section will block. Deadlock.

The problem  (as Todd pointed out ) is that TerminateThread
doesn't clean up after itself.

>of just killing it outright, and you said it does not always work.
It should work all the time ( a little but here their might be a need
for tweaking, let me first explain this ).  The solution does not wait
for the thread to die. Here is what the solution does:

new_thread_function()
{
....
   interruptible_active=false; //1
} //2 thread dies

if(interruptible_thread) //3
   TerminateThread(new_thread()); //4

On a single processor machine the system is constantly switching
between threads. Call that context switch  CS. One order of execution
is

3,CS,1,2,CS,4
In this case the parent tests to see if the thread is alive. It gets a
yes. Then a context switch sets the same variable to false. The child
thread is dieing, but the parent thread thinks it's not. The child
then dies and the parent then tries to terminate it.

An alternate order of execution could be 
1,CS,3,CS,2
In this case the variable is set to zero, when 3 tests
interruptible_thread it discovers that it is false, the child is
dieing on it's own, and does not call TerminateThread.
Another order of execution could be
3,CS,1,CS,4
in which case
the parent thread tests interruptible_active and thinks the child
is not dieing. The child announces that it is going to die, but before
it actually dies the parent calls terminate thread and kills it.

This is a bit simplistic as the compiler/operating system are doing
things in between  the statement and for that reason a statement
may encounter several context switches before dieing. 

what my solution does is force context switches to make sure that
4 is executed before 2. ( 4 before 2 is good, 2 before 4 is bad. )
So add:

   interruptible_active=false; //1
   Sleep(0); // 1.1	
   Sleep(0); // 1.2
   Sleep(0); // 1.3	
} //2 thread dies

Sleep(0) tells the system to go to sleep for 0 milliseconds.
It also tells it ( as Sleep always does ) to do a context switch.
Essentially it is the same as yield.
So look at the first sequence
3,CS,1,2,CS,4
This becomes:
3,CS,1,1.1,CS,4
So 4 gets executed before 2 because 1.1forces a context switch.

Now back to the tweaking. As I said sometimes multiple context
switches can happen per statement.
so the modified first sequence might look like.
3,CS,1,1.1,CS, first part of 4,CS,1.2,CS,second part of four.
The trick is to force enough context switches to make sure that
four is complete ( or at least that the actual kill thread process
has been put in place ). I'm fairly sure that 2 is enough, but I threw
in the third just to make sure.
-------------------------------------------------------
I just realised that I wasn't addressing the original code, but a
quick look will suggest that it's even worse there.

new_thread_function()
{
....
} //1 thread dies

if(interruptible_thread) //3
   TerminateThread(new_thread()); //4

main_thread:
     WaitForSingleObject(new_thread) //2
     interruptible_active=false; //5

now the deadly sequence is 1 before 4.
The order 1,2,4 always has to happen ( 2 is waiting for 1).
So you can have something as bad as
1,2,CS,3,4,CS,5 
way too late for 5.
or something well behaved
like
1,2,5,CS,3 4 never gets executed.
or
3,first part of 4,CS,first part of 1,CS  second part of 4, which is OK
because 4 finishes before 1.
Or something like
1,first part of 2,CS,3,4,CS,second part of 2,5

>Is there a solution that would always work?
This should always work, just put in enough Sleep(0); s.

>need for TerminateThread() altogether?
I think you need another mechanism to signal the function to end, but
what it should be I'm not sure. This solution should work fine for
now.

---

From: Sam Steingold <[email-masked]>
Date: Wed Jan 30 12:48:03 2002

> 98,99c98,101
> <           if (!TerminateThread(interruptible_thread,1+CtrlType)) {
> <             OS_error();
> ---
> >           if(interruptible_active){         
> >             if (!TerminateThread(interruptible_thread,1+CtrlType)) {
> >                   OS_error();
> >            }

since 3 lines above of this we set interruptible_active to false,
this change just disables TerminateThread().

please use "diff -c" next time.

thanks for your explanations.

-- 
Sam Steingold (http://www.podval.org/~sds)
Keep Jerusalem united! <http://www.onejerusalem.org/Petition.asp>
Read, think and remember! <http://www.iris.org.il> <http://www.memri.org/>
Press any key to continue or any other key to quit.

---

From: [email-masked] (Thaddeus L. Olczyk)
Date: Wed Jan 30 13:47:03 2002

>this change just disables TerminateThread().
Your right. I saw it and then promply forgot about it.
It complicates things because whoever wrote this decided
to use the interruptible_active to denote two things:
1) To describe the state of the interuptible thread ( is it or is it
not active?)
2) To act as a state machine to tell itself that it has already been
interupted once and not to do it again.

It should not call TerminateThread, but One of the tests I ran was to
break into an infinite loop. Strange.
The solutions I see are to move the assignment downward or to break 
the variable into two parts, one for the active state, one for
describing the handler state.
I'll check on both tonight.