llvm dev - May 2014 - [LLVMdev] Finding safe thread suspension points while JIT-ing (was: Add pass run listeners to the pass manager.)

On May 9, 2014, at 7:36 PM, Andrew Trick <atrick at apple.com> wrote:
> 
> On May 9, 2014, at 6:33 PM, Chandler Carruth <chandlerc at
google.com> wrote:
> 
>> So, I'm bringing a discussion that has thus far been on
llvm-commits to llvmdev because I finally (and thanks for helping me understand
this Andy) understand what is *really* going on, and I think lots of others need
to be aware of this and involved to figure out the right path forward.
>> 
>> You can find the full review thread and more context under the subject
"[PATCH][PM] Add pass run listeners to the pass manager.", but here is
the important bit from Juergen's initial email:
>> 
>> this patch provides the necessary C/C++ APIs and infastructure to
enable fine-
>> grain progress report and safe suspension points after each pass in the
pass
>> manager. 
>>  
>> Clients can provide a callback function to the pass manager to call
after each
>> pass. This can be used in a variety of ways (progress report, dumping
of IR
>> between passes, safe suspension of threads, etc).
>> 
>> I had wrongly (perhaps because of the implementation, but still,
wrongly) focused on the progress report and IR dumping use cases. It sounds
(from talking to Andy offline, sorry for that confusion) like the real use case
is safe suspension of threads. The idea is that we would have a callback from
the pass manager into the LLVMContext which would be used to recognize safe
points at which the entire LLVMContext could be suspended, and to expose these
callbacks through C API to JIT users.
> 
> Good. Let’s table the discussion of how to report passes and just focus on
the thread suspension API. It never occurred to me that a client using the new
API for thread scheduling would not *already* be making an assumption about one
thread per context. I believe anything else will break these clients regardless
of the API. So I didn’t see this API as imposing a new restriction. The more
explicit we can be about this, the better.
They not only have to make the assumption of one thread per context, but they
actually have to enforce it. According to the comments in LLVMContext there is
no locking guarantee and the user/client has to be careful to use one context
per thread. This is the current C API and that is how clients are using it right
now.

Any future extension to the LLVMContext and to the pass manager that change this
requirement - namely running in parallel - should be backwards compatible.
Although I don’t see how this could or should be an issue to begin with as long
we default to the current single-threaded execution model per LLVMContext.
Anything that changes this behavior should and have to be explicitly requested
by the client. That means there has to be a new C API call to communicate this
information. For now all the threads are created by the client and I think this
should also stay so in the future.
>> Increasingly, I can't fathom a way to get a good design for safe
suspension of JIT-ing threads using callbacks tied to when passes run today. I
think it is a huge mistake to bake this into the C API at this point. If you
need this functionality in the C API, with a design we can use going forward,
I'd like to see a *really* careful write up of exactly what the suspension
point requirements are and a design for achieving them. I think it should be
completely independent from any infrastructure for reporting or dumping IR in
pass managers.
> 
> Yes, there absolutely needs to be a way to expose functionality within LLVM
in its current form through the C API. We can say that the API works under some
explicit set of rules. If some future LLVM can be configured in a way that
breaks the rules, you don’t get the callback in that case.
It is already a conscious choice of the client if and how to use threads. This
choice already affects how callbacks that we already have are implemented by the
client. The same would apply for the proposed callback. The client knows exactly
the conditions, because it is in full control of setting up the environment.
> 
>> I think something much simpler than this might work outside of the C
API, where we can essentially change how it works when we start designing how
multiple threads will actually work within an LLVMContext. Would that work? Is
there a way to make progress more rapidly there?
>> 
>> Ultimately, this is opening a huge can of worms if we put it into the C
API, as I think it is going to fundamentally impact what options we actually
have for parallelizing parts of LLVM in the future. If we want to go there, we
need be *incredibly* explicit about what assumptions are being made here.
Yes, this will definitely impact the design, but only in a positive way :D There
is only one big requirement and that is a given: The thread cannot hold a global
mutex when making this call. This would deadlock everything - even other
concurrent running contexts in todays implementation.

When a thread group is running concurrently in the future pass manager then it
clear that the suspension of any thread in this thread group might deadlock the
remaining threads in the thread group and that is perfectly fine. Also having
this callback being fired concurrently is fine too. The client created a
parallel pass manager and has to write the callback thread-safe.

The important thing here is that LLVM is holding the thread hostage and we need
the control back to safely suspend it. It is possible suspend the thread from
outside, but then it might be inside a system call or library call that holds a
mutex. This could deadlock the whole application. By giving the control back to
the client via the call back we know that this cannot happen. We know that LLVM
might hold some mutex local to the context, but that is fine and won’t deadlock
the whole application.

-Juergen
> 
> Let’s be explicit then.
> 
> We will always need to be able to configure LLVM with one thread per
context. Always. So it’s not like we’re adding something that could become
unusable in the future. Does anyone disagree?
> 
> Incidentally, I have no idea why the callback would not work with parallel
context. If you suspend a thread within a thread group, it is totally expected
that the other threads will also eventually block.
> 
> Tangentially, how many other places do we assume that an LLVMContext
corresponds to a thread?
> 
> -Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140510/d1ef94df/attachment.html>

I don't have a strong opinion on this topic at the moment, but given 
that it is potentially GC related, I figured I'd speak up.

I see two unspoken assumptions in the thread so far:
- The runtime needs a means to bring all threads to a stop to perform 
some action.  In particular, no thread can be excepted.
- A single LLVM library call takes longer to complete than the runtime 
is willing to wait for the thread stoppage to occur.

Both are entirely reasonable; I'm just spelling them out since they 
might not be obvious to everyone.  The second is particularly noteworthy 
since it's entirely new in LLVM.

I largely agree with Andy at the moment that the existing interface 
assumes one thread per context.  I don't see the issue with continuing 
with this assumption, particular since no one t.m.k. has put forward any 
serious plans to change this.  If this does happen, having it occur in 
an opt-in manner will be a matter of practical necessity.

I find myself somewhat uncertain of the choice to leverage the pass 
manager for this purpose though.  It's the entirely logical place to 
start, but is it enough?  What if a single pass takes too long to 
complete?  Do we start scattering these call backs throughout large 
parts of LLVM?  Also, how does this interact with something like the 
hoped for parallel LTO?

Like Chandler, I believe there needs to be a fully thought out proposal 
and discussion on this list.  I would weakly oppose the change in it's 
current form solely on this basis.

Andy, Juergen - Can you start by providing a bit more background 
information?  What do you need the thread yield call back for? Garbage 
collection?  Other VM tasks?  User mode scheduling of threads?  
Something else entirely?

Yours,
Philip



On 05/10/2014 11:11 AM, Juergen Ributzka wrote:
>
> On May 9, 2014, at 7:36 PM, Andrew Trick <atrick at apple.com 
> <mailto:atrick at apple.com>> wrote:
>
>>
>> On May 9, 2014, at 6:33 PM, Chandler Carruth <chandlerc at
google.com
>> <mailto:chandlerc at google.com>> wrote:
>>
>>> So, I'm bringing a discussion that has thus far been on
llvm-commits
>>> to llvmdev because I finally (and thanks for helping me understand 
>>> this Andy) understand what is *really* going on, and I think lots
of
>>> others need to be aware of this and involved to figure out the
right
>>> path forward.
>>>
>>> You can find the full review thread and more context under the 
>>> subject "[PATCH][PM] Add pass run listeners to the pass
manager.",
>>> but here is the important bit from Juergen's initial email:
>>>
>>>     this patch provides the necessary C/C++ APIs and infastructure
>>>     to enable fine-
>>>     grain progress report and safe suspension points after each
>>>     pass in the pass
>>>     manager. 
>>>
>>>     Clients can provide a callback function to the pass manager to
>>>     call after each
>>>     pass. This can be used in a variety of ways (progress report,
>>>     dumping of IR
>>>     between passes, safe suspension of threads, etc).
>>>
>>>
>>> I had wrongly (perhaps because of the implementation, but still, 
>>> wrongly) focused on the progress report and IR dumping use cases.
It
>>> sounds (from talking to Andy offline, sorry for that confusion)
like
>>> the real use case is safe suspension of threads. The idea is that
we
>>> would have a callback from the pass manager into the LLVMContext 
>>> which would be used to recognize safe points at which the entire 
>>> LLVMContext could be suspended, and to expose these callbacks 
>>> through C API to JIT users.
>>
>> Good. Let's table the discussion of how to report passes and just 
>> focus on the thread suspension API. It never occurred to me that a 
>> client using the new API for thread scheduling would not *already* be 
>> making an assumption about one thread per context. I believe anything 
>> else will break these clients regardless of the API. So I didn't
see
>> this API as imposing a new restriction. The more explicit we can be 
>> about this, the better.
>
> They not only have to make the assumption of one thread per context, 
> but they actually have to enforce it. According to the comments in 
> LLVMContext there is no locking guarantee and the user/client has to 
> be careful to use one context per thread. This is the current C API 
> and that is how clients are using it right now.
>
> Any future extension to the LLVMContext and to the pass manager that 
> change this requirement - namely running in parallel - should be 
> backwards compatible. Although I don't see how this could or should be 
> an issue to begin with as long we default to the current 
> single-threaded execution model per LLVMContext. Anything that changes 
> this behavior should and have to be explicitly requested by the 
> client. That means there has to be a new C API call to communicate 
> this information. For now all the threads are created by the client 
> and I think this should also stay so in the future.
>
>>> Increasingly, I can't fathom a way to get a good design for
safe
>>> suspension of JIT-ing threads using callbacks tied to when passes 
>>> run today. I think it is a huge mistake to bake this into the C API
>>> at this point. If you need this functionality in the C API, with a 
>>> design we can use going forward, I'd like to see a *really*
careful
>>> write up of exactly what the suspension point requirements are and
a
>>> design for achieving them. I think it should be completely 
>>> independent from any infrastructure for reporting or dumping IR in 
>>> pass managers.
>>
>> Yes, there absolutely needs to be a way to expose functionality 
>> within LLVM in its current form through the C API. We can say that 
>> the API works under some explicit set of rules. If some future LLVM 
>> can be configured in a way that breaks the rules, you don't get the
>> callback in that case.
>
> It is already a conscious choice of the client if and how to use 
> threads. This choice already affects how callbacks that we already 
> have are implemented by the client. The same would apply for the 
> proposed callback. The client knows exactly the conditions, because it 
> is in full control of setting up the environment.
>
>>
>>> I think something much simpler than this might work outside of the
C
>>> API, where we can essentially change how it works when we start 
>>> designing how multiple threads will actually work within an 
>>> LLVMContext. Would that work? Is there a way to make progress more 
>>> rapidly there?
>>>
>>> Ultimately, this is opening a huge can of worms if we put it into 
>>> the C API, as I think it is going to fundamentally impact what 
>>> options we actually have for parallelizing parts of LLVM in the 
>>> future. If we want to go there, we need be *incredibly* explicit 
>>> about what assumptions are being made here.
>
> Yes, this will definitely impact the design, but only in a positive 
> way :D There is only one big requirement and that is a given: The 
> thread cannot hold a global mutex when making this call. This would 
> deadlock everything - even other concurrent running contexts in todays 
> implementation.
>
> When a thread group is running concurrently in the future pass manager 
> then it clear that the suspension of any thread in this thread group 
> might deadlock the remaining threads in the thread group and that is 
> perfectly fine. Also having this callback being fired concurrently is 
> fine too. The client created a parallel pass manager and has to write 
> the callback thread-safe.
>
> The important thing here is that LLVM is holding the thread hostage 
> and we need the control back to safely suspend it. It is possible 
> suspend the thread from outside, but then it might be inside a system 
> call or library call that holds a mutex. This could deadlock the whole 
> application. By giving the control back to the client via the call 
> back we know that this cannot happen. We know that LLVM might hold 
> some mutex local to the context, but that is fine and won't deadlock 
> the whole application.
>
> -Juergen
>
>>
>> Let's be explicit then.
>>
>> We will always need to be able to configure LLVM with one thread per 
>> context. Always. So it's not like we're adding something that
could
>> become unusable in the future. Does anyone disagree?
>>
>> Incidentally, I have no idea why the callback would not work with 
>> parallel context. If you suspend a thread within a thread group, it 
>> is totally expected that the other threads will also eventually block.
>>
>> Tangentially, how many other places do we assume that an LLVMContext 
>> corresponds to a thread?
>>
>> -Andy
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140512/bac9976e/attachment.html>

On Mon, May 12, 2014 at 4:52 PM, Philip Reames <listmail at
philipreames.com>wrote:
> I largely agree with Andy at the moment that the existing interface
> assumes one thread per context.  I don't see the issue with continuing
with
> this assumption, particular since no one t.m.k. has put forward any serious
> plans to change this.

FWIW, I have specific, concrete, and serious plans here. =D The new pass
manager is in part motivated by these plans. I expect parallelism to be the
next major infrastructure thing I work on after the pass manager.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140512/64b6d335/attachment.html>

On May 12, 2014, at 3:52 PM, Philip Reames <listmail at philipreames.com>
wrote:
> I don't have a strong opinion on this topic at the moment, but given
that it is potentially GC related, I figured I'd speak up.
> 
> I see two unspoken assumptions in the thread so far:
> - The runtime needs a means to bring all threads to a stop to perform some
action.  In particular, no thread can be excepted.
The *only* assumption that we want client to make of this API is that a compiler
thread can be suspended at this point without blocking other non-compiler
threads in the same process, or blocking other compiler threads associated with
a *different* LLVM context.

There will be no assumption about the state of the suspended thread’s LLVM
context and no assumption that other threads in the same context will continue
executing (if there were such a thing).
> - A single LLVM library call takes longer to complete than the runtime is
willing to wait for the thread stoppage to occur.
I’m not sure what you mean by this.
> Both are entirely reasonable; I'm just spelling them out since they
might not be obvious to everyone.  The second is particularly noteworthy since
it's entirely new in LLVM.
> 
> I largely agree with Andy at the moment that the existing interface assumes
one thread per context.  I don't see the issue with continuing with this
assumption, particular since no one t.m.k. has put forward any serious plans to
change this.  If this does happen, having it occur in an opt-in manner will be a
matter of practical necessity.
I don’t think this API makes any assumption about LLVM’s threading model. I
don’t even see how this API assumes one thread per context. However, I will
concede that it does if it helps focus this discussion. Either way, the JIT
should determine the threading model and be given a C API that allows
configuring and scheduling those threads. As you correctly said, if we
hypothetically implement a parallel pass manager mode that breaks some JITs,
then clients will need to opt-in. We are not beholden to implement this callback
in that mode. We just need to make that clear.
> I find myself somewhat uncertain of the choice to leverage the pass manager
for this purpose though.  It's the entirely logical place to start, but is
it enough?  What if a single pass takes too long to complete?  Do we start
scattering these call backs throughout large parts of LLVM?  Also, how does this
interact with something like the hoped for parallel LTO?
> 
> Like Chandler, I believe there needs to be a fully thought out proposal and
discussion on this list.  I would weakly oppose the change in it's current
form solely on this basis.
Would you (or anyone) oppose a simple maySuspendContext() callback API? It would
mean nothing more than the thread(s) for a given LLVM context can be suspended
independent from other contexts.
> Andy, Juergen - Can you start by providing a bit more background
information?  What do you need the thread yield call back for?  Garbage
collection?  Other VM tasks?  User mode scheduling of threads?  Something else
entirely?
The thread yield API is primarily for user mode scheduling of threads. 

A JIT could certainly use it for GC and other VM tasks. That isn’t necessary for
us because those tasks can run concurrent with the LLVM thread until it
completes. It would only be a problem if there are resource constraints.

-Andy
> 
> Yours,
> Philip
> 
> 
> 
> On 05/10/2014 11:11 AM, Juergen Ributzka wrote:
>> 
>> On May 9, 2014, at 7:36 PM, Andrew Trick <atrick at apple.com>
wrote:
>> 
>>> 
>>> On May 9, 2014, at 6:33 PM, Chandler Carruth <chandlerc at
google.com> wrote:
>>> 
>>>> So, I'm bringing a discussion that has thus far been on
llvm-commits to llvmdev because I finally (and thanks for helping me understand
this Andy) understand what is *really* going on, and I think lots of others need
to be aware of this and involved to figure out the right path forward.
>>>> 
>>>> You can find the full review thread and more context under the
subject "[PATCH][PM] Add pass run listeners to the pass manager.", but
here is the important bit from Juergen's initial email:
>>>> 
>>>> this patch provides the necessary C/C++ APIs and infastructure
to enable fine-
>>>> grain progress report and safe suspension points after each
pass in the pass
>>>> manager. 
>>>>  
>>>> Clients can provide a callback function to the pass manager to
call after each
>>>> pass. This can be used in a variety of ways (progress report,
dumping of IR
>>>> between passes, safe suspension of threads, etc).
>>>> 
>>>> I had wrongly (perhaps because of the implementation, but
still, wrongly) focused on the progress report and IR dumping use cases. It
sounds (from talking to Andy offline, sorry for that confusion) like the real
use case is safe suspension of threads. The idea is that we would have a
callback from the pass manager into the LLVMContext which would be used to
recognize safe points at which the entire LLVMContext could be suspended, and to
expose these callbacks through C API to JIT users.
>>> 
>>> Good. Let’s table the discussion of how to report passes and just
focus on the thread suspension API. It never occurred to me that a client using
the new API for thread scheduling would not *already* be making an assumption
about one thread per context. I believe anything else will break these clients
regardless of the API. So I didn’t see this API as imposing a new restriction.
The more explicit we can be about this, the better.
>> 
>> They not only have to make the assumption of one thread per context,
but they actually have to enforce it. According to the comments in LLVMContext
there is no locking guarantee and the user/client has to be careful to use one
context per thread. This is the current C API and that is how clients are using
it right now.
>> 
>> Any future extension to the LLVMContext and to the pass manager that
change this requirement - namely running in parallel - should be backwards
compatible. Although I don’t see how this could or should be an issue to begin
with as long we default to the current single-threaded execution model per
LLVMContext. Anything that changes this behavior should and have to be
explicitly requested by the client. That means there has to be a new C API call
to communicate this information. For now all the threads are created by the
client and I think this should also stay so in the future.
>> 
>>>> Increasingly, I can't fathom a way to get a good design for
safe suspension of JIT-ing threads using callbacks tied to when passes run
today. I think it is a huge mistake to bake this into the C API at this point.
If you need this functionality in the C API, with a design we can use going
forward, I'd like to see a *really* careful write up of exactly what the
suspension point requirements are and a design for achieving them. I think it
should be completely independent from any infrastructure for reporting or
dumping IR in pass managers.
>>> 
>>> Yes, there absolutely needs to be a way to expose functionality
within LLVM in its current form through the C API. We can say that the API works
under some explicit set of rules. If some future LLVM can be configured in a way
that breaks the rules, you don’t get the callback in that case.
>> 
>> It is already a conscious choice of the client if and how to use
threads. This choice already affects how callbacks that we already have are
implemented by the client. The same would apply for the proposed callback. The
client knows exactly the conditions, because it is in full control of setting up
the environment.
>> 
>>> 
>>>> I think something much simpler than this might work outside of
the C API, where we can essentially change how it works when we start designing
how multiple threads will actually work within an LLVMContext. Would that work?
Is there a way to make progress more rapidly there?
>>>> 
>>>> Ultimately, this is opening a huge can of worms if we put it
into the C API, as I think it is going to fundamentally impact what options we
actually have for                   parallelizing parts of LLVM in the future.
If we want to go there, we need be *incredibly* explicit about what assumptions
are being made here.
>> 
>> Yes, this will definitely impact the design, but only in a positive way
:D There is only one big requirement and that is a given: The thread cannot hold
a global mutex when making this call. This would deadlock everything - even
other concurrent running contexts in todays implementation.
>> 
>> When a thread group is running concurrently in the future pass manager
then it clear that the suspension of any thread in this thread group might
deadlock the remaining threads in the thread group and that is perfectly fine.
Also having this callback being fired concurrently is fine too. The client
created a parallel pass manager and has to write the callback thread-safe.
>> 
>> The important thing here is that LLVM is holding the thread hostage and
we need the control back to safely suspend it. It is possible suspend the thread
from outside, but then it might be inside a system call or library call that
holds a mutex. This could deadlock the whole application. By giving the control
back to the client via the call back we know that this cannot happen. We know
that LLVM might hold some mutex local to the context, but that is fine and won’t
deadlock the whole application.
>> 
>> -Juergen
>> 
>>> 
>>> Let’s be explicit then.
>>> 
>>> We will always need to be able to configure LLVM with one thread
per context. Always. So it’s not like we’re adding something that could become
unusable in the future. Does anyone disagree?
>>> 
>>> Incidentally, I have no idea why the callback would not work with
parallel context. If you suspend a thread within a thread group, it is totally
expected that the other threads will also eventually block.
>>> 
>>> Tangentially, how many other places do we assume that an
LLVMContext corresponds to a thread?
>>> 
>>> -Andy
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140512/7d8d9c69/attachment.html>