Thread: [Sablevm-developer] adventures in not understanding the java stack
Brought to you by:
egagnon
Menu
▾
▴
sablevm-developer
|
From: Chris P. <chr...@ma...> - 2004-01-17 05:20:04
|
Hello, In order for speculation to work, I require the following to be true for INVOKE<X> instructions: 1) the method has fully exited and the instruction after the INVOKE<X> is the next instruction to be executed when the height of stack.current_frame returns to the height before the INVOKE<X> (this handles the problem of recursion) 2) the stack after the INVOKE<X> is identical to the stack before the INVOKE<X>, except for possibly popped parameters (including a possible objectref) and a possibly pushed return value. I've found that the following can invalidate this: 1) An exception being thrown in the callee (or one of the callee's callees), or some other exception-related irregular control flow -- currently flagged at exception_handler: in interpreter.c, at ATHROW, and at INTERNAL_CALL_END 2) GC being called in the callee (or one of the callee's callees) -- flagged inside _svmf_stop_the_world() 3) The callee (or one of the callee's callees) being a native method. I can understand (1) -- irregular control flow means that the stack returns to the same height without the instruction after the INVOKE<X> being next I can understand (2) -- GC being called would change references on the stack, thus making requirement 2 fail but ... I don't understand (3). So ... can somebody explain (3) for me? Can native code affect stack values or control flow without going through the exception_handler: in interpreter.c or going through _svmf_stop_the_world? If so, where does it do it? Also, is there anything else you can think of that might break requirements 1 and 2? Cheers, and thanks for any suggestions, Chris |
|
From: David <db...@cs...> - 2004-01-17 08:46:37
|
> 1) An exception being thrown in the callee (or one of the callee's=20 > callees), or some other exception-related irregular control flow --=20 > currently flagged at exception_handler: in interpreter.c, at ATHROW, an= d=20 > at INTERNAL_CALL_END > 2) GC being called in the callee (or one of the callee's callees) --=20 > flagged inside _svmf_stop_the_world() > 3) The callee (or one of the callee's callees) being a native method. >=20 > but ... I don't understand (3). >=20 Hi Chris, Native methods can throw exceptions and/or trigger garbage collection. David --- David B=E9langer Graduate Student School of Computer Science McGill University Office: MC226 Web page: http://www.cs.mcgill.ca/~dbelan2/ Public key: http://www.cs.mcgill.ca/~dbelan2/public_key.txt |
|
From: David <db...@cs...> - 2004-01-17 08:57:59
|
On Sat, Jan 17, 2004 at 12:21:30AM -0500, Chris Pickett wrote: > So ... can somebody explain (3) for me? Can native code affect stack=20 > values or control flow without going through the exception_handler: in=20 > interpreter.c or going through _svmf_stop_the_world? If so, where does= =20 > it do it? Look at NATIVE_STATIC_METHOD and NATIVE_NONSTATIC_METHOD. All the code to unwind the stack is in _svmf_interpreter. Though the exception object is built by the native method or one of the method/function it calls. GC is usually trigger by creating new instance and not enough memory. There is also a native method that forces gc. Java_java_lang_Runtime_gc. There is a single gc entry point that will stop all threads (except the current one) before doing the actual gc. Look in gc_copying.c. David --- David B=E9langer Graduate Student School of Computer Science McGill University Office: MC226 Web page: http://www.cs.mcgill.ca/~dbelan2/ Public key: http://www.cs.mcgill.ca/~dbelan2/public_key.txt |
|
From: Chris P. <chr...@ma...> - 2004-01-17 17:05:20
|
David B=E9langer wrote:
>On Sat, Jan 17, 2004 at 12:21:30AM -0500, Chris Pickett wrote:
> =20
>
>>So ... can somebody explain (3) for me? Can native code affect stack=20
>>values or control flow without going through the exception_handler: in =
>>interpreter.c or going through _svmf_stop_the_world? If so, where does=
=20
>>it do it?
>> =20
>>
>
>Look at NATIVE_STATIC_METHOD and NATIVE_NONSTATIC_METHOD.
>
>All the code to unwind the stack is in _svmf_interpreter. Though the
>exception object is built by the native method or one of the
>method/function it calls.
>
> =20
>
that's what i thought. i had changed _svmf_interpreter() to:
athrow_handler:
...
abstractmethoderror_handler:
exception_handler:
=20
<my code to flag exceptions / kill speculative children is here>
<normal exception handler stuff>
and i don't understand how an exception can be thrown natively or=20
non-natively without passing by "exception_handler:" in=20
_svmf_interpreter ...
>GC is usually trigger by creating new instance and not enough memory.
>There is also a native method that forces gc.
>Java_java_lang_Runtime_gc. There is a single gc entry point that will
>stop all threads (except the current one) before doing the actual gc.
>Look in gc_copying.c.
>
> =20
>
okay, i had assumed that _svmf_stop_the_world was always called and=20
always visited all threads for each gc, whether gc is called natively or =
not. I had changed _svmf_stop_the_world() in thread.c to:
/* visit all threads */
for (...)
{
jboolean succeeded;
=20
<my code to flag gc is here>
if (current =3D=3D env)
...
}
and I still don't understand how GC could be called without passing=20
through this code for each thread. after looking at=20
Java_java_lang_Runtime_gc, i see that it calls=20
_svmf_copy_gc_no_exception(), which in turn calls _svmf_stop_the_world ..=
=2E
anyway, i think there might be some other control flow issue related to=20
exceptions that i don't understand. i put abortion code in=20
INTERNAL_CALL_END as well, in the event that a new speculative thread=20
gets started in the middle of the exception handler and the=20
non-speculative parent hits this instruction without hitting the=20
"exception_handler:" handler label in _svmf_interpreter() .....
so -- apart from calling gc and throwing exceptions, is there anything=20
that a native or non-native method could be doing to invalidate the=20
requirements i have (original email)? note that speculation is never=20
started in a preparation sequence.
i'm sorry, i just really don't understand how i'm not catching this if i =
make the above changes. anyway, if it sounds like i'm doing everything=20
right i'll go back over my changes again, but i keep thinking there's=20
some piece that i'm missing.
cheers,
chris
|
|
From: Chris P. <chr...@ma...> - 2004-01-19 19:39:47
|
Hi Etienne,
I looked into bootstrapping and class loading (tracing execution with=20
M-. and M-* in etags) and realized that the problems I'm having are due=20
to my assumption that when the env->stack.current_frame offset reaches=20
the same height again, the method has returned, when in fact that method =
may have called _svmf_interpreter() somewhere along the line, and=20
although the height of the current_frame in the Java stack may be=20
correct, the height in the C stack is incorrect.
So ... my questions are ...
1) Does the indented stuff below (sorry Greg for the "AOL-style" email)=20
make sense w.r.t. exceptions and GC? In other words, have I identified=20
the unique entry points for exceptions and GC correctly, and am I=20
correct to assume that GC or exceptions as caused by native code will=20
pass through these points?
2) Do all calls to _svmf_interpreter() end in INTERNAL_CALL_END (it=20
appears this way from invoke_interface.c)?
3) If I keep track of _svmf_interpreter() call depth and Java call=20
depth, abort speculative children on GC or exceptions in the parent=20
non-speculative thread, and abort speculative children on global=20
memory-writing (Java heap or not) instructions in the speculative child, =
am I correct to assume that the "speculative" stack obtained after=20
jumping over a method call will not differ from the actual stack when=20
that point is reached non-speculatively?
4) Can I furthermore assert that the next instruction to be executed=20
after a method call has completed, in the absence of an exception being=20
thrown in the call, is the next instruction in the code array?
5) Do calls to _svmf_interpreter() enter and exit cleanly? In other=20
words, am I right to assume that there is nothing like a Java exception=20
that can occur to screw up control flow, and that when the height of the =
call stack returns you are back where you started?
6) Do you see any reason, if I take care of things like described above, =
that I would need to worry about non-speculatively executing native=20
methods, class initializers, or finalizers, possibly with speculative=20
children before starting or possibly forking new speculative children in =
each of these (native methods might call JNI functions that start=20
speculative threads)?
If the answer to any of these is "no" or "maybe", I don't need a long=20
explanation as much as pointers to the relevant code (I can ask=20
questions later if I don't understand it).
Cheers,
Chris
Chris Pickett wrote:
>
>
> David B=E9langer wrote:
>
>>On Sat, Jan 17, 2004 at 12:21:30AM -0500, Chris Pickett wrote:
>> =20
>>
>>>So ... can somebody explain (3) for me? Can native code affect stack =
>>>values or control flow without going through the exception_handler: in=
=20
>>>interpreter.c or going through _svmf_stop_the_world? If so, where doe=
s=20
>>>it do it?
>>> =20
>>>
>>
>>Look at NATIVE_STATIC_METHOD and NATIVE_NONSTATIC_METHOD.
>>
>>All the code to unwind the stack is in _svmf_interpreter. Though the
>>exception object is built by the native method or one of the
>>method/function it calls.
>>
>> =20
>>
> that's what i thought. i had changed _svmf_interpreter() to:
>
> athrow_handler:
> ...
> abstractmethoderror_handler:
> exception_handler:
> =20
> <my code to flag exceptions / kill speculative children is here>
>
> <normal exception handler stuff>
>
> and i don't understand how an exception can be thrown natively or=20
> non-natively without passing by "exception_handler:" in=20
> _svmf_interpreter ...
>
>>GC is usually trigger by creating new instance and not enough memory.
>>There is also a native method that forces gc.
>>Java_java_lang_Runtime_gc. There is a single gc entry point that will
>>stop all threads (except the current one) before doing the actual gc.
>>Look in gc_copying.c.
>>
>> =20
>>
>
> okay, i had assumed that _svmf_stop_the_world was always called and=20
> always visited all threads for each gc, whether gc is called natively=20
> or not. I had changed _svmf_stop_the_world() in thread.c to:
>
> /* visit all threads */
> for (...)
> {
> jboolean succeeded;
> =20
> <my code to flag gc is here>
>
> if (current =3D=3D env)
> ...
> }
>
> and I still don't understand how GC could be called without passing=20
> through this code for each thread. after looking at=20
> Java_java_lang_Runtime_gc, i see that it calls=20
> _svmf_copy_gc_no_exception(), which in turn calls _svmf_stop_the_world =
=2E..
|
|
From: Etienne G. <gag...@uq...> - 2004-01-19 20:55:03
|
Chris,
Your messages are too long. I'm sincerely sorry, but I have to ask to su=
mmarize.
I'll try to answer the summary as well as I can.
Etienne
Chris Pickett wrote:
> Hi Etienne,
>=20
> I looked into bootstrapping and class loading (tracing execution with=20
> M-. and M-* in etags) and realized that the problems I'm having are due=
=20
> to my assumption that when the env->stack.current_frame offset reaches =
> the same height again, the method has returned, when in fact that metho=
d=20
> may have called _svmf_interpreter() somewhere along the line, and=20
> although the height of the current_frame in the Java stack may be=20
> correct, the height in the C stack is incorrect.
>=20
> So ... my questions are ...
>=20
> 1) Does the indented stuff below (sorry Greg for the "AOL-style" email)=
=20
> make sense w.r.t. exceptions and GC? In other words, have I identified=
=20
> the unique entry points for exceptions and GC correctly, and am I=20
> correct to assume that GC or exceptions as caused by native code will=20
> pass through these points?
>=20
> 2) Do all calls to _svmf_interpreter() end in INTERNAL_CALL_END (it=20
> appears this way from invoke_interface.c)?
>=20
> 3) If I keep track of _svmf_interpreter() call depth and Java call=20
> depth, abort speculative children on GC or exceptions in the parent=20
> non-speculative thread, and abort speculative children on global=20
> memory-writing (Java heap or not) instructions in the speculative child=
,=20
> am I correct to assume that the "speculative" stack obtained after=20
> jumping over a method call will not differ from the actual stack when=20
> that point is reached non-speculatively?
>=20
> 4) Can I furthermore assert that the next instruction to be executed=20
> after a method call has completed, in the absence of an exception being=
=20
> thrown in the call, is the next instruction in the code array?
>=20
> 5) Do calls to _svmf_interpreter() enter and exit cleanly? In other=20
> words, am I right to assume that there is nothing like a Java exception=
=20
> that can occur to screw up control flow, and that when the height of th=
e=20
> call stack returns you are back where you started?
>=20
> 6) Do you see any reason, if I take care of things like described above=
,=20
> that I would need to worry about non-speculatively executing native=20
> methods, class initializers, or finalizers, possibly with speculative=20
> children before starting or possibly forking new speculative children i=
n=20
> each of these (native methods might call JNI functions that start=20
> speculative threads)?
>=20
> If the answer to any of these is "no" or "maybe", I don't need a long=20
> explanation as much as pointers to the relevant code (I can ask=20
> questions later if I don't understand it).
>=20
> Cheers,
> Chris
>=20
>=20
>=20
> Chris Pickett wrote:
>=20
>>
>>
>> David B=E9langer wrote:
>>
>>> On Sat, Jan 17, 2004 at 12:21:30AM -0500, Chris Pickett wrote:
>>> =20
>>>
>>>> So ... can somebody explain (3) for me? Can native code affect=20
>>>> stack values or control flow without going through the=20
>>>> exception_handler: in interpreter.c or going through=20
>>>> _svmf_stop_the_world? If so, where does it do it?
>>>> =20
>>>
>>>
>>> Look at NATIVE_STATIC_METHOD and NATIVE_NONSTATIC_METHOD.
>>>
>>> All the code to unwind the stack is in _svmf_interpreter. Though the=
>>> exception object is built by the native method or one of the
>>> method/function it calls.
>>>
>>> =20
>>>
>> that's what i thought. i had changed _svmf_interpreter() to:
>>
>> athrow_handler:
>> ...
>> abstractmethoderror_handler:
>> exception_handler:
>> <my code to flag exceptions / kill speculative children is here=
>
>>
>> <normal exception handler stuff>
>>
>> and i don't understand how an exception can be thrown natively or=20
>> non-natively without passing by "exception_handler:" in=20
>> _svmf_interpreter ...
>>
>>> GC is usually trigger by creating new instance and not enough memory.=
>>> There is also a native method that forces gc.
>>> Java_java_lang_Runtime_gc. There is a single gc entry point that wil=
l
>>> stop all threads (except the current one) before doing the actual gc.=
>>> Look in gc_copying.c.
>>>
>>> =20
>>>
>>
>> okay, i had assumed that _svmf_stop_the_world was always called and=20
>> always visited all threads for each gc, whether gc is called natively =
>> or not. I had changed _svmf_stop_the_world() in thread.c to:
>>
>> /* visit all threads */
>> for (...)
>> {
>> jboolean succeeded;
>> <my code to flag gc is here>
>>
>> if (current =3D=3D env)
>> ...
>> }
>>
>> and I still don't understand how GC could be called without passing=20
>> through this code for each thread. after looking at=20
>> Java_java_lang_Runtime_gc, i see that it calls=20
>> _svmf_copy_gc_no_exception(), which in turn calls _svmf_stop_the_world=
=20
>> ...
>=20
>=20
>=20
>=20
>=20
--=20
Etienne M. Gagnon, Ph.D. http://www.info.uqam.ca/~egagnon/
SableVM: http://www.sablevm.org/
SableCC: http://www.sablecc.org/
|
|
From: Etienne G. <gag...@uq...> - 2004-01-19 21:49:53
|
Chris, some answers below. Chris Pickett wrote: > 2) Do all calls to _svmf_interpreter() end in INTERNAL_CALL_END (it > appears this way from invoke_interface.c)? No. They can also end: - at line 636 of interpreter.c: initializing the interpreter. - at line 400 of interpreter.c: exception path. > 3) If I keep track of _svmf_interpreter() call depth and Java call > depth, abort speculative children on GC or exceptions in the parent > non-speculative thread, and abort speculative children on global > memory-writing (Java heap or not) instructions in the speculative child, > am I correct to assume that the "speculative" stack obtained after > jumping over a method call will not differ from the actual stack when > that point is reached non-speculatively? Which stack? The operand stack, or the Java stack? Do not forget about _svmf_ensure_stack_capacity() which can actually change the "absolute" location of the Java stack (and thus the absolute location of the operand stack). > 4) Can I furthermore assert that the next instruction to be executed > after a method call has completed, in the absence of an exception being > thrown in the call, is the next instruction in the code array? Yes. > 5) Do calls to _svmf_interpreter() enter and exit cleanly? In other > words, am I right to assume that there is nothing like a Java exception > that can occur to screw up control flow, and that when the height of the > call stack returns you are back where you started? _svmf_interpreter sets a longjump handler, so it never exits other than through "return" (at one of 3 identified locations: 2 above + INTERNAL_CALL_END) as far as I remember. -- Etienne M. Gagnon, Ph.D. http://www.info.uqam.ca/~egagnon/ SableVM: http://www.sablevm.org/ SableCC: http://www.sablecc.org/ |
|
From: Chris P. <chr...@ma...> - 2004-01-19 23:00:05
|
Hi Etienne, Thanks kindly for your response. I've compressed the unanswered bits for you at the end, and tried to cut out as much as possible. >> 3) Am I correct to assume that the "speculative" stack obtained after >> jumping over a method call will not differ from the actual stack when >> that point is reached non-speculatively? > > > Which stack? The operand stack, or the Java stack? > The entire Java stack, which includes the operand stack. I am getting errors where portions of the Java stack differ if I compare a saved Java stack (that was generated by skipping over a void method and popping parameters) with the actual stack. My plan is to keep track of a) _svmf_interpreter() depth b) height of the current frame on the Java stack c) whether an exception is thrown in the skipped method d) whether GC is called in the skipped method to determine when I have actually returned (and can thus join the speculative thread). Ignore the bit about safety of speculative instructions in the original question -- it doesn't apply to the problem of determining join points. > Do not forget about _svmf_ensure_stack_capacity() which can actually > change the "absolute" location of the Java stack (and thus the absolute > location of the operand stack). Right, I'm sure that this is not the problem, the comparison is value-by-value between saved and actual stacks. ========== Now, summarized: 1a) If I mark relevant threads for GC being called at line 418 in thread.c, will this catch them all? 1b) If I put the code to abort speculative children because the non-speculative parent threw an exception, natively or not, at line 364 in interpreter.c, will this catch everything? 6) Can you think of anything to do with class initialization, object finalization, or native method calls that would cause problems with what I'm describing? As in, problems that I won't detect safely? I'm asking about non-speculative parent threads, with or without children, executing these sections, possibly forking children. Speculative instructions are themselves safe with respect to global memory, exception handling, GC, native methods, and code preparation. Thank-you very very much. I apologize if any of this seems exceedingly obvious to you, but I made some incorrect assumptions in the past and I want to prevent that this time around (I've disabled almost everything and am turning features on one at a time). Cheers, Chris P.S. In the future, I would like to help design and possibly implement some kind of high-level CFG for the VM, which is (partially) built from directives in the source. Discussions like this and the GC one make me think about stuff like that. |
|
From: Etienne G. <gag...@uq...> - 2004-01-19 23:54:23
|
Chris Pickett wrote:
> Now, summarized:
>
> 1a) If I mark relevant threads for GC being called at line 418 in
> thread.c, will this catch them all?
It does visit all "live" threads. SableVM was designed so that dead
thread data structures can be recycled for new threads, lowering the
pressure on the memory manager [malloc/free in this case].
>
> 1b) If I put the code to abort speculative children because the
> non-speculative parent threw an exception, natively or not, at line 364
> in interpreter.c, will this catch everything?
Yes (I think).
> 6) Can you think of anything to do with class initialization, object
> finalization, or native method calls that would cause problems with what
> I'm describing? As in, problems that I won't detect safely? I'm asking
> about non-speculative parent threads, with or without children,
> executing these sections, possibly forking children. Speculative
> instructions are themselves safe with respect to global memory,
> exception handling, GC, native methods, and code preparation.
Let's be nasty... What if the parent thread creates a Thread instance and
calls Thread.start()? I guess this implies a native call and is thus covered
in your approach, right?
I guess you have to worry about native methods. A native method should
probably invalidate speculative children.
That's all that comes to my mind.
> Thank-you very very much. I apologize if any of this seems exceedingly
> obvious to you, but I made some incorrect assumptions in the past and I
> want to prevent that this time around (I've disabled almost everything
> and am turning features on one at a time).
No, it's not obvious at all, even to me. It's just that you face two
competing yet important goals, when you write to me and want an answer:
1- You must explain things very clearly (and unambiguously) and provide
enough information so that I can actually answer.
2- You must write a short ( < 10 lines ) message so that, if I have a 2-5 minutes
hole in my schedule, I will be tempted to read it and answer. Otherwise, it
ends up on the stack of hundreds of messages I hope to have time some day
to answer. [You might notice that I do sometime answer such emails, but after
a few months...] Unless, of course, you don't need the answer any time soon. :-)
> P.S. In the future, I would like to help design and possibly implement
> some kind of high-level CFG for the VM, which is (partially) built from
> directives in the source. Discussions like this and the GC one make me
> think about stuff like that.
Let's finish the speculative stuff first! And if you have time to spare, you
could help with the general infrastructure (e.g. getting Eclipse to run on
SableVM, etc.) :-)))
Etienne
--
Etienne M. Gagnon, Ph.D. http://www.info.uqam.ca/~egagnon/
SableVM: http://www.sablevm.org/
SableCC: http://www.sablecc.org/
|
|
From: Chris P. <chr...@ma...> - 2004-01-20 01:17:36
|
>> 6) Can you think of anything to do with class initialization, object >> finalization, or native method calls that would cause problems with >> what I'm describing? As in, problems that I won't detect safely? >> I'm asking about non-speculative parent threads, with or without >> children, executing these sections, possibly forking children. >> Speculative instructions are themselves safe with respect to global >> memory, exception handling, GC, native methods, and code preparation. > > > Let's be nasty... What if the parent thread creates a Thread instance and > calls Thread.start()? I guess this implies a native call and is thus > covered > in your approach, right? > > I guess you have to worry about native methods. A native method should > probably invalidate speculative children. > > That's all that comes to my mind. I don't think the Thread.start() example is a problem. If a speculative thread tries to start a new thread, it will hit a native method call and abort. If a non-speculative thread without spmt children tries to start a new thread, it can do so. Then we have two non-speculative threads, each of which can start speculative children of their own. If a non-speculative thread with spmt children tries to start a new thread, then if that thread violates some dependences the children will be aborted. In any case, the call to the method that started the thread should return normally, and thus reach the join point before the abortion occurs. Basically ... I am worried about having: FORK (jump over invoke and execute past join speculatively) INVOKE (executed non-speculatively in parallel) JOIN and the INVOKE not returning to the JOIN point (e.g. by throwing an exception) or the initial "speculative" stack at the JOIN being incorrect (e.g. because of GC). Additionally, if the INVOKE can somehow affect the data specific to the speculative thread (not global data), that would be something I need to know about. Note that I am not currently planning for speculative threads to run in their own Java Thread, but rather be clones of the non-speculative parent (and thus be invisible to other non-speculative threads and their children), running in a pthread that I manage explicitly. (it's not necessary to get sidetracked into the multithreading details at this point). Anyway, let me know if a problem in my reasoning occurs to you at some point (Clark too!), and meanwhile I'm just going to go ahead and implement this, based off of your previous answers and the latest description I gave. Thanks again, Chris |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X