Re: Important bug fix in current trunk

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--===============0688649169==
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature";
	boundary="------------enig96C76A49BE0D69E62F08C75D"

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enig96C76A49BE0D69E62F08C75D
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Hi Chris,

First...  The bug fix does nothing to fix SMP support; for that, the
integration of atomic_ops and the implementation of the memory model JSR
is needed.

> ...  Can you detail the unsafe
> interleaving between threads that you discovered?  Can you explain
> exactly how your solution fixes it and what happens if two threads
> compete now?  I see the changes in prepare_code.c but I don't really see
> the difference in execution semantics.

Here's a quick description of the problem and its solution:

SableVM prepares methods lazily.  Now, you know that SableVM does split
local variables in order to allow for precise garbage collection using
very little stack/local map storage.

Here's a figure from doc/stack_layout.txt:

Case 1: Normal Java Method Frame
================================

                      |                    |   *
current_frame         +--------------------+   *
- previous_offset --> |stack_frame_struct  |   *
                      |                    |   *
                      +--------------------+   *
                      |                    |   *
                      |                    |   *
                      |                    |   * previous frame
                      |                    |   *
current_frame -       +--------------------+   *
method->frame_info->  |local 0             | * *
start_offset          |      1             | * *
                      |      2             | * *__ last param
                      |      ...           | *
                      |local n             | *
env->stack.           +--------------------+ *
current_frame   ----> | stack_frame_struct | *  current frame
                      |                    | *
                      |                    | *
                      +--------------------+ *
                      | padding to align   | *
current_frame +       +--------------------+ *
_svmv_stack_offset -> | expression stack   | *
                      |                    | *
                      |                    | *
                      |                    | *
                      |                    | *
current_frame +       +--------------------+ *
end_offset       ---> |                    |



Before method preparation, all that SableVM knows about local variables
is the max_locals value of the code attribute.  SableVM uses that value
to compute the displacement between "last param" (on the right of the
figure) and env->stack.current_frame (on the left).  In other words,
SableVM prepares a frame for the called method, yet it does not know the
"prepared" size of the locals array.

After preparation, sometimes the number of variables increases beyond
max_locals (other times it is reduced, surprisingly, see my thesis for
details).  So, in order to execute the prepared method, SableVM must
rewrite the stack frame, increasing/decreasing the value of
env->stack.current_frame so that the appropriate amount of space is left
for local variables.

The problem was that, sometimes, in multi-threaded applications, two or
more threads competed to execute the same method for the first time.  Of
course, there was synchronization on preparing methods.  But, the
problem happened when the first thread, the winning one (that got the
lock) finished preparation.  That thread changed the stored precomputed
offset (last param to current frame).  Now, sometimes gc happened just
at that point (on small heaps triggering frequent GCs), leading to the
seen assertion.  The problem being that the garbage collector used the
globally stored precomputed offsets to walk the heap, yet, the losing
thread had not yet fixed its stack frame...

Actually, the code was even a little buggier.  The second thread never
fixed its stack frame and simply resumed execution once it got the lock.
   So, from that time on, the second thread could potentially corrupt
its stack.  Sometimes, I guess, it happened, and resulted in late seen
corruption.

Of course, in order for corruption to happen, one had to be "lucky", so
that two threads competed on preparing the same method.  As method
preparation is usually quite fast, the window of opportunity was small,
but relatively likely in programs launching very early a bunch of
threads doing the same thing.

> Also, please note, that if you are depending on an ordering between
> reads/writes in different threads, ...

I know all of this.  Did I ever claim that SableVM was safe to run on
SMP?  Yet, I've heard between branches that you had started implementing
the memory model JSR.  Is there any chance you could contribute this
code within the upcoming months?  [Would be a retribution for me writing
this long and detailed reply to you. ;-P ]

> Finally, it would be good to have a test-case shell script.

Agreed.  You're welcome to help.  Have a look at
$SVN/sablevm-test-suite/trunk.  Could be used a a start point.

> I'm assuming I can test and reproduce the bug with
> sablevm/branches/sablevm-lgpl (I am using x86_64 SMP),
> sablevm-classpath/trunk, and --enable-debugging-features.

x86_64 *SMP*...  Good luck... :-/

Have fun!


Etienne

-- 
Etienne M. Gagnon, Ph.D.            http://www.info2.uqam.ca/~egagnon/
SableVM:                                       http://www.sablevm.org/
SableCC:                                       http://www.sablecc.org/

--------------enig96C76A49BE0D69E62F08C75D
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFEVYBcjyrJi4rH84gRAkIsAJ0fJDeZt9dwaJ4aIUZO6jQ8o6bPmgCfeI6d
9DmOGgYP2MsjU5yByo3rGlg=
=NAXd
-----END PGP SIGNATURE-----

--------------enig96C76A49BE0D69E62F08C75D--


--===============0688649169==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
SableVM-devel mailing list
[email protected]
http://sablevm.org/lists/control/listinfo/sablevm-devel

--===============0688649169==--