Bugzilla – Bug 418
Want JIT support for threaded programs
Last modified: 2005-07-12 12:05:08
You need to log in before you can comment on or make changes to this bug.
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.
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.
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
Created an attachment (id=211) [details] First attempt at adding locks to the JIT
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.
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
Created an attachment (id=214) [details] Trivial fixes from the thread patch I've split out the trival changes from my previous patch, while I resolve the other comments that were made about it.
Created an attachment (id=215) [details] ThreadSupport-PThreads.h: Use recursive mutexes I've added a patch that correctly initializes the mutexes as a recursive mutex for the pthreads implementation. The patch also adds assertions to verify that each pthread function call succeeded.
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
Created an attachment (id=220) [details] Updated JIT thread support patch
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.
(From update of attachment 220 [details]) 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
Created an attachment (id=234) [details] Makes the JIT thread-safe I've attached the latest version of my thread patch. This is against the latest CVS, as of today. The differences from the previous version are as follows: 1. Fixes a bug that I found while using LLVM, by adding locks to the JITResolver class. 2. Adds a "holds" method to the MutexLocker class that can be used to verify that the correct Mutex is being held. I ran the regression tests on Linux and it did not break anything on my machine.
Let's review this again after 1.5 is released.
Mine
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?
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.
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.
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.
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
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
Created an attachment (id=257) [details] Parallel JIT test Great work! Thanks for committing this. I apologize: I'm not working with LLVM at the moment, and I don't really have time to go update my installation in order to be able to make a clean patch against llvm-test. I'm going to do the lazy thing and take you up on your offer: I've attached my test to this bug. This test doesn't use LLVM's indentation style, and is a little bit of a hack of a couple of the LLVM examples. Here is the description from the top of the file: This test program creates two LLVM functions then calls them from three separate threads. It requires the pthreads library. The three threads are created and then block waiting on a condition variable. Once all threads are blocked on the conditional variable, the main thread wakes them up. This complicated work is performed so that all three threads call into the JIT at the same time (or the best possible approximation of the same time). This test had assertion errors until I got the locking right. This code can be licenced under whatever licence you choose. Technically, it is a derivative of the examples in llvm/examples directory.