Want JIT support for threaded programs

[Quuxplusone]

Bugzilla Link	PR418
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Johan Walles (walles@mailblocks.com)
Reported on	2004-08-14 09:21:30 -0700
Last modified on	2010-02-22 12:44:21 -0800
Version	1.3
Hardware	All All
CC	ejones@uwaterloo.ca, jeffc@jolt-lang.org, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	llvm-threadsafe.patch (13172 bytes, text/plain) llvm-thread-fixes.patch (1604 bytes, text/plain) llvm-pthread-support.patch (1497 bytes, text/plain) llvm-pthread-support.patch (10531 bytes, text/plain) thread.patch (16341 bytes, text/plain) ParallelJIT.cpp (8447 bytes, application/octet-stream)
Blocks
Blocked by	PR540
See also

According to the 1.3 release notes at
"http://llvm.cs.uiuc.edu/releases/1.3/docs/ReleaseNotes.html", LLVM is unable to
run threaded programs:

"
The JIT does not use mutexes to protect its internal data structures. As such,
execution of a threaded program could cause these data structures to be
corrupted.
"

It would be nice if it was indeed possible to run threaded programs.

Since this is in the release notes, you're obviously aware of it, but having a
bugzilla for it makes it easier for people to track what's happening with this.

[Quuxplusone]

One of the UIUC researchers was assigned to add threading support to LLVM. I
forget who, but it has been thought about/started. In any event, there's nothing
stopping someone from using a library like pthreads today. Its possible to make
a multi-threaded application with LLVM, we just don't support it natively in
LLVM.

[Quuxplusone]

Adding this to the LLVM JIT would be really trivial, it's just that noone has
started looking into it.  All it would take is putting mutexes (defined in
"Support/ThreadSupport.h", around the critical JIT data structures.

Noone has started looking at this, but if you're interested, it would be a
really easy (and useful) LLVM enhancement.

-Chris

[Quuxplusone]

I've made a first attempt at adding locking to the JIT. Unfortunately, since I
do not really understand the
structure of LLVM, I could have very easily screwed something up. In other
words, this definitely needs
review. I touched two classes, the JIT and the  ExecutionEngine. I need some
help from someone who is
more familiar with the code to make sure that  I have protected the correct
data structures. I'm also
looking for suggestion about how to test this for correctness.

To make sure that I added locks where required, I moved "dangerous" members of
the classes into a
new class, called JITState and ExecutionEngineState, respectively. These
classes only allow access to the
variables if a lock is held. This allows the compiler to verify that locks are
held in the correct places,
although there could still easily be bugs if the locks are released too early.
The data structures that are
protected are:

ExecutionEngine:
std::map<const GlobalValue*, void *> GlobalAddressMap; // R/W data structure
std::map<void *, const GlobalValue*> GlobalAddressReverseMap; // R/W data
structure

JIT:
std::vector<const GlobalVariable*> PendingGlobals;  // R/W data structure
FunctionPassManager PM; // Could call passes which are not thread safe

Both of these classes have additional members which I have not protected. It
looked to my brief
analysis that they were used in a read-only fashion. Can anyone tell me if I am
wrong:

ExecutionEngine:
Module &CurMod;
const TargetData *TD;

JIT:
TargetMachine &TM;
TargetJITInfo &TJI;
MachineCodeEmitter *MCE;

I specifically did not protect the ExecutionEngine::CurMod member because a
reference is returned via
ExecutionEngine::getModule(). If access to it must be serialized, it must be
done very carefully. I tried to
make getModule return a constant reference, but that quickly led me into deep
trouble in the world of
const correctness.

I've attached my patch against the latest CVS. There is one "trivial" fix which
should be committed, even
if this patch is incorrect. In ThreadSupport.h, the include guard macro needs
to have "LLVM_" prefixed
to it. The ThreadSupport-PThread.h and ThreadSupport-NoSupport.h files look for
the macro with this
prefix.

[Quuxplusone]

Overall, the patch looks very good.  Here are a couple of suggestions:

1. Please pull the unrelated bits and pieces (e.g.
s/SUPPORT_THREADSUPPORT_H/LLVM_SUPPORT_THREADSUPPORT_H and the iterator -> const
iterator changes) into a seperate patch.  These changes are "obvious" and can be
applied immediately.

2. I like your use of methods like "getPM" to force the client to demonstrate
that they own the lock.  Very nice idiom.  However, it would be nice to change
the JIT ctor to look something like this:

MutexLocker locked(lock);
PassManager &PM = state.getPM(locked);

instead of using getPM multiple times.

3. I'm not sure that the pthreads implementation of the mutex class is right,
can you take a look?  In particular, the ctor looks like this
(include/llvm/Support/ThreadSupport-PThreads.h):

    Mutex() {
      pthread_mutexattr_t Attr;
      pthread_mutex_init(&mutex, &Attr);
    }

It seems like pthread_mutexattr_init should be used, or
PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP should be used.  Note that we do want a
recursive mutex here.

I think your patch is correct.  To test it, the first thing you want to do is
make sure that no non-threaded programs are broken.  If you use the llvm-test
suite, you can pick a subdirectory (e.g. MultiSource/Benchmarks/Olden) type
'make' and it will test all of the programs in that subdir.

For the threaded case, it's more difficult.  You can try writing programs that
would cause multiple functions to be JIT'd at the same time, for example, but
I'm not sure the best way to ensure the bad behavior would happen...

If you take care of the above and attach both patches (the trivial stuff and
non-trivial stuff patches), I would be happy to apply them for you. :)

Thanks a lot!

-Chris

[Quuxplusone]

Attached llvm-threadsafe.patch (13172 bytes, text/plain): First attempt at adding locks to the JIT

[Quuxplusone]

Attached llvm-thread-fixes.patch (1604 bytes, text/plain): Trivial fixes from the thread patch

[Quuxplusone]

Attached llvm-pthread-support.patch (1497 bytes, text/plain): ThreadSupport-PThreads.h: Use recursive mutexes

[Quuxplusone]

Both patches look great, and are applied:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024322.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024323.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024324.html

Thanks!

-Chris

[Quuxplusone]

I have finally ran the test suite, and created an example that actually calls
into the JIT from multiple
threads. These all seem to work. I've attached the current version of my patch.
Would you also like me
to include my example program somehow? I could attempt to reformat it as a
test, although the only
thing that it could verify is that the program runs and generates the expected
result.

This bug depends on configure and Makefile support to add "-lpthreads" to the
linker command line for
all LLVM based tools. Without this change, the tools will fail to link on
Linux. This bug depends on my
enhancement request for this feature.

[Quuxplusone]

Comment on attachment 220
Updated JIT thread support patch

I found a bug with the original patch, as noted in the following mailing list
post. Thus, the patch is obsolete:

http://mail.cs.uiuc.edu/pipermail/llvmdev/2005-April/003809.html

[Quuxplusone]

Attached llvm-pthread-support.patch (10531 bytes, text/plain): Updated JIT thread support patch

[Quuxplusone]

Attached thread.patch (16341 bytes, text/plain): Makes the JIT thread-safe

[Quuxplusone]

Let's review this again after 1.5 is released.

[Quuxplusone]

Mine

[Quuxplusone]

I have applied Evan's patch in my own tree and determined that it does not, at
least, cause any harm. Whether it actually keeps the JIT thread-safe, I don't
know since there aren't any multi-threaded programs in llvm-test.  However, all
the llvm-test tests pass with the patch applied.

Unfortunately, this patch causes lli to require linking with libpthread.a which
I'm not sure everyone wants. Furthermore, I think this will render lli as a
"unix only" tool because I doubt we want threading done with libpthread on Win32
even if it was available. I don't particularly care so I'm happy to commit the
patch, but others might object.

Anyone want to chime in on this?

[Quuxplusone]

There is no libpthread in VC++.  It won't even compile, much less link.  Win32
sychronization primitives, probably critical sections, must be used.  Suggest
that these be added to lib/System.

[Quuxplusone]

My patch doesn't *directly* depend on libpthread, so it would be very possible
to add Win32 support by
creating a Win32 version of the libSystem lock classes, and hacking the build
system to select the
appropriate macros and linker flags. I would make a Win32 version of this class
myself, except that I
don't have easy access to a Windows machine with Visual Studio, nor do I know
Win32's synchronization
primitives.

As for threaded test programs, I have a couple that I used to test the patch
myself that I could provide.
However, there is a similar issue there: the test program needs a way to spawn
threads and perform
synchronization. I just wrote my tests to be Linux specific, but to be included
as part of LLVM's test
suite they would need to be made cross platform.

[Quuxplusone]

Evan, could you please add your threaded test programs to
llvm-test/SingleSource/UnitTests, please? They need to be public domain or very
lax open source licensed (e.g. BSD like). If you're in doubt, just attach them
to this bug and I'll take care of it.

[Quuxplusone]

Resolved via Evans patch and these patches:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027019.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027020.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027021.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027022.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027023.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027024.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027025.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027026.html

[Quuxplusone]

Don't forget to update the release notes:

1. Mention the new feature
2. Remove the 'known problem' that says the JIT is not thread safe.

Thanks!

-Chris

[Quuxplusone]

Attached ParallelJIT.cpp (8447 bytes, application/octet-stream): Parallel JIT test