Thread safety tracker

[ViralBShah]

One of the first things we need to do is make the runtime thread safe. This work is on the threads branch, and this tracker predates the new GC. I thought it is worth capturing a tracker that @StefanKarpinski prepared earlier in an issue to ease the thread safety work.

This list is organized as Variable; Approach

builtins.c

• extern size_t jl_page_size; constant
• extern int jl_in_inference; lock
• extern int jl_boot_file_loaded; constant
• int in_jl_ = 0; thread-local

ccall.cpp

• static std::mapstd::stringstd::string sonameMap; lock
• static bool got_sonames = false; lock, write-once
• static std::mapstd::stringuv_lib_t* libMap; lock
• static std::mapstd::stringGlobalVariable* libMapGV; lock
• static std::mapstd::stringGlobalVariable* symMapGV; lock
• static char *temp_arg_area; thread-local (will be deleted very soon)
• static const uint32_t arg_area_sz = 4196; constant (will be deleted very soon)
• static uint32_t arg_area_loc; thread-local (will be deleted very soon)
• static void *temp_arg_blocks[N_TEMP_ARG_BLOCKS]; thread-local (will be deleted very soon)
• static uint32_t arg_block_n = 0; thread-local (will be deleted very soon)
• static Function *save_arg_area_loc_func; constant (will be deleted very soon)
• static Function *restore_arg_area_loc_func; constant (will be deleted very soon)

cgutils.cpp

• static std::map<const std::stringGlobalVariable*> stringConstants; lock
• static std::map<void*jl_value_llvm> jl_value_to_llvm; lock
• static std::map<Value void> llvm_to_jl_value; lock
• static std::vector<Constant*> jl_sysimg_gvars; lock
• static std::map<intjl_value_t*> typeIdToType; lock
• jl_array_t *typeToTypeId; lock
• static int cur_type_id = 1; lock

codegen.cpp

• void *__stack_chk_guard = NULL; thread-local (jwn: why is this on the list? it's a constant and not thread local)

debuginfo.cpp

• extern "C" volatile int jl_in_stackwalk;
• JuliaJITEventListener *jl_jit_events;
• static obfiletype objfilemap;
• extern char *jl_sysimage_name; constant
• static logdata_t coverageData;
• static logdata_t mallocData;

dump.c

• static jl_array_t *tree_literal_values=NULL; thread-local
• static jl_value_t *jl_idtable_type=NULL; constant
• static jl_array_t *datatype_list=NULL; thread 0 only
• jl_value_t ***sysimg_gvars = NULL; thread 0 only
• extern int globalUnique; thread 0 only
• static size_t delayed_fptrs_n = 0; thread 0 only
• static size_t delayed_fptrs_max = 0; thread 0 only

gc.c

• static volatile size_t allocd_bytes = 0; thread-local
• static volatile int64_t total_allocd_bytes = 0; thread-local
• static int64_t last_gc_total_bytes = 0; thread-local
• static size_t freed_bytes = 0; barrier
• static uint64_t total_gc_time=0; barrier
• int jl_in_gc=0; * referenced from switchto task.c barrier
• static htable_t obj_counts; barrier
• static size_t total_freed_bytes=0; barrier
• static arraylist_t to_finalize; barrier
• static jl_value_t **mark_stack = NULL; barrier
• static size_t mark_stack_size = 0; barrier
• static size_t mark_sp = 0; barrier
• extern jl_module_t *jl_old_base_module; constant
• extern jl_array_t *typeToTypeId; barrier
• extern jl_array_t *jl_module_init_order; barrier
• static int is_gc_enabled = 1; atomic
• static double process_t0; constant

init.c

• char *jl_stack_lo; thread-local
• char *jl_stack_hi; thread-local
• volatile sig_atomic_t jl_signal_pending = 0; thread-local
• volatile sig_atomic_t jl_defer_signal = 0; thread-local
• uv_loop_t *jl_io_loop; I/O thread ?
• static void *signal_stack; thread-local (see Random CI failures rather intense right now #9763 (comment))
• static mach_port_t segv_port = 0; constant
• extern void * __stack_chk_guard; thread-local (duplicate of above)

jltypes.c

• int inside_typedef = 0; thread-local
• static int match_intersection_mode = 0; thread-local
• static int has_ntuple_intersect_tuple = 0; thread-local
• static int t_uid_ctr = 1; lock

llvm-simdloop.cpp

• static unsigned simd_loop_mdkind = 0; constant
• static MDNode* simd_loop_md = NULL; constant
• char LowerSIMDLoop::ID = 0; lock

module.c

• jl_module_t *jl_main_module=NULL; constant
• jl_module_t *jl_core_module=NULL; constant
• jl_module_t *jl_base_module=NULL; constant
• jl_module_t *jl_current_module=NULL; thread-local
• jl_array_t *jl_module_init_order = NULL; lock (this code is bady broken anyways: module init order is wrong and can cause segfaults #9799)

profile.c

• static volatile ptrint_t* bt_data_prof = NULL;
• static volatile size_t bt_size_max = 0;
• static volatile size_t bt_size_cur = 0;
• static volatile u_int64_t nsecprof = 0;
• static volatile int running = 0;
• volatile HANDLE hBtThread = 0;
• static pthread_t profiler_thread;
• static mach_port_t main_thread;
• clock_serv_t clk;
• static int profile_started = 0;
• static mach_port_t profile_port = 0;
• volatile static int forceDwarf = -2;
• volatile mach_port_t mach_profiler_thread = 0;
• static unw_context_t profiler_uc;
• mach_timespec_t timerprof;
• struct itimerval timerprof;
• static timer_t timerprof;
• static struct itimerspec itsprof;

sys.c

• JL_STREAM *JL_STDIN=0; constant
• JL_STREAM *JL_STDOUT=0; constant
• JL_STREAM *JL_STDERR=0; constant

task.c

• volatile int jl_in_stackwalk = 0; thread-local
• static size_t _frame_offset; constant
• DLLEXPORT jl_task_t * volatile jl_current_task; thread-local
• jl_task_t *jl_root_task; constant
• jl_value_t * volatile jl_task_arg_in_transit; thread-local
• jl_value_t *jl_exception_in_transit; thread-local
• __JL_THREAD jl_gcframe_t *jl_pgcstack = NULL; thread-local
• jl_jmp_buf * volatile jl_jmp_target; thread-local
• extern int jl_in_gc; barrier
• static jl_function_t *task__hook_func=NULL; constant
• ptrint_t bt_data[MAX_BT_SIZE+1]; thread-local
• size_t bt_size = 0; thread-local
• int needsSymRefreshModuleList; lock
• jl_function_t *jl_unprotect_stack_func; constant

toplevel.c

• int jl_lineno = 0; thread-local
• jl_module_t *jl_old_base_module = NULL; constant
• jl_module_t *jl_internal_main_module = NULL; constant
• extern int jl_in_inference; lock

[StefanKarpinski]

Don't we have a spreadsheet of this somewhere? Maybe make it public?

[ViralBShah]

https://docs.google.com/a/mayin.org/spreadsheets/d/1FLrB90u0ORvBDmJZtxUfXhSt8HVdKMM0rqYjoOeMvGo/edit#gid=0

Don't know if it is public - but I thought it would be easier to track the work here in the issue.

[StefanKarpinski]

I fancied up the spreadsheet a bit so that it's easier to organize and sort.

[vtjnash]

i've tried to help knock a few off the list based off existing issues and upcoming changes

[JeffBezanson]

That's true, #9986 helps with this.

[ViralBShah]

It would be nice to get basic printing to work:

julia> using Base.Threading
julia> @threads all for i=1:100; println(i) ; end

signal (11): Segmentation fault
Segmentation fault (core dumped)

[ArchRobison]

Are these changes being made in the master, or a branch? I see items checked off for llvm-simdloop.cpp, but don't see them in the master branch.

[StefanKarpinski]

I think this is for the threading branch, right, @JeffBezanson?

[tknopp]

would also be interesting which is the current threading branch, "threading" or "threads"

[StefanKarpinski]

"threading" is newer than "threads"; not sure why we changed branches.

[tknopp]

that why I asked :-) I have seen changes being made to both branches at a time and thus was not sure about it.

Would be also interesting to have an issue what the blockers are for merging into master. IIUC at some point llvm svn was required but this might be solved if we switch to llvm3.6? Further there is still the pthreads dependency.

[ArchRobison]

Moving to C11/C++11 threads would remove the pthreads dependency. Using C11/C++11 would also give us portable atomic ops with good memory consistency controls. LLVM is moving aggressively to depend on C++11 anyway.

[tknopp]

I am not 100% sure why the pthread dependency was added but it seems to be required to set thread affinity. Is this possible with C++11? For atomic ops we have written some macros that use the compiler dependent intrinsics.

[ViralBShah]

@kpamnany had suggested that I use the threads branch and not threading as one of the macros was not quite working. If that is now fixed, I'd rather delete the threads branch and just have everything on threading.

[ArchRobison]

As far as I know, C++11 has no notion of thread affinity. So we still have to write platform-specific code for that. There is a hook in C++11 for getting at the platform-specific thread handle, so I think it's possible to write most of the threading in C++11/C11 and interface to platform-specific stuff for affinity.

[tknopp]

Not sure what exactly we gain when using C++11 threads. The Julia code is currently largely C based and only uses C++ where necessary (i.e. when interfacing with LLVM). This is a design decision. One could simplify quite some code when using C++ and could e.g. use STL containers instead of the self-written ones in libsupport. But the C vs C++ topic can be quite subjective. Its up to Jeff to give a direction here.

[ArchRobison]

C11 threading would work too. It's supposed to interoperate with C++ threads, i.e. in principle it's just difference spellings of the key operations. Though we'd need to check on Windows. Microsoft has been good about implementing the latest versions of C++, but has shown indifference to implementing even C99.

[ArchRobison]

Another route is to figure out the threading model first, and then write platform specific implementations of the core operations. That's the way the Intel Cilk Plus run-time is written, since it requires stack-switching capabilities beyond PThreads.

[eschnett]

To handle thread affinity I recommend using the hwloc library, already nicely wrapped in https://github.com/JuliaParallel/hwloc.jl. hwloc provides a platform-independent API to query number of cores, sockets, caches, etc., and to define the threads' affinity to them.

I find that C++11 threading implementations are based on pthreads, and thus slow. It would e.g. not be efficient to run each Julia task on a new C++11 thread. This makes C++11 threading facilities (the thread class, async method, future objects) rather useless if one is interested in more fine-grained threading. Most languages that are serious about threading define their own thread abstraction and do not rely on pthreads.

@ArchRobison: What stack-switching capabilities does Cilk Plus have? I had the impression that there are certain limitations. I'm currently using Qthreads https://github.com/Qthreads/qthreads, since there each thread has its own stack, and threads can switch arbitrarily.

[ArchRobison]

Yes, direct use of C11/C++11 threading for tasks would be rather useless, but it at least provides portable access to OS-level threads. I would imagine the Julia run-time would have several layers for threading:

1. Platform specific services. E.g. create a thread.
2. Unsafe abstractions implemented directly on top of (1), and hence an implementation per platform.
3. Portable unsafe abstractions built on top of (2)
4. Safe services for mere mortals, built on top of (2) and (3).

Cilk implementations (including Cilk Plus) implement a cactus stack. This paper gives a good overview of different ways to implement cactus stacks. The limitation to cactus stacks and the "busy leaves" property (each leaf has a thread running on it) is essential to Cilk's strong space and time guarantees, which may or may not be worth the limitations depending on perspective.

For level 2 above, the internals of the Intel implementation use an abstraction similar to Windows fibers, essentially arbitrary stack switching. The file runtime/cilk_fiber-unix.cpp has the Linux version -- about 144 lines of code.

@eschnett How does QThreads deal with stack overflow? I recall that Rust gave up on segmented stacks. Go copies the entire stack, which requires some care with code generation and stack maps, and takes on a little overhead in function prologs. Though overall I like its design since users don't have to worry about stack overflow and are not tied to cactus stacks.

[eschnett]

@ArchRobison QThread stack overflows are handled via good, old signal 11, if you enable stack overflow detection. Otherwise they remain unhandled.

[eschnett]

@ArchRobison: Regarding Cilk Plus: I have the impression -- please correct me if I am wrong -- that Cilk offers only a limited kind of parallelism: A routine can spawn children, but all children need to exit before the routine itself exits. This is less powerful than e.g. C++11, where the spawned thread's state is typically captured in a future that can be returned, stored, and passed around. Thread execution in C++11 thus doesn't form a tree structure, and cactus stacks (as described in the paper you mention) are not relevant. Is this what you meant by "busy leaves property"?

[eschnett]

@ArchRobison: You said "I recall that Rust gave up on segmented stacks." Do you have a pointer to what Rust tried, or how they failed?

[kpamnany]

To clarify on the threads vs. threading branches: there are no macro issues. The latter branch is newer and we should throw away the former, but #10527.

[kpamnany]

The threading code uses pthreads to start threads, set thread affinities, and for a mutex and condition variable pair to let threads sleep rather than spin when they aren't working. The other platform dependency is atomics, which would also be used in the runtime for spin locks and other synchronization constructs.

I've begun looking at C11 for threads and atomics, but if platform-dependent code is required anyways (for thread affinitization), and moving to C11 doesn't give us Windows, then I'm not sure it's worth the effort. hwloc looks cool but very elaborate for just thread affinity control.

To maximize parallel performance, at least on HSW-EP and KNL (i.e. 72 to >250 threads), plenty of platform-specific code will be needed anyway (e.g. the "best" barrier algorithm itself is different).

[vtjnash]

libuv also provides threading primitives: https://github.com/joyent/node/blob/a995a6a776f1b2d01946702190c6ff837c338577/deps/uv/include/uv.h#L1331-L1378

[tknopp]

@vtjnash this is what is used but libuv misses the thread affinity code. I would say extending libuv would be a Good appoach

[ArchRobison]

@eschnett: Here is a link to Rust giving up on segmented stacks.

"Busy leaves" property says that all leaves in the cactus stack have a thread actively running. E.g., on a P-thread system there will be no more than P leaves, and each leaf will have a thread running it. Each path from a leaf to the root corresponds to a stack that would have occurred in the sequential version of the program, hence the total space is bounded by P*(space for sequential execution). An example of a system without the busy leave property is TBB, where a leaf can stall because of the way TBB maps tasks to threads internally. (Alas a trade off we made for easy of portability.)

It looks like libuv's threading support is essentially the same as pthreads. Atomic operations and user-level scheduling are missing. So libuv seems like a good way to break dependence on pthreads, but we'll still need at least macros for atomics and something for decoupling stack<-->thread bindings.

[JeffBezanson]

I'll start a checklist of steps needed before we can turn threading on by default:

• CI setup and tests pass
• Improve stability (e.g. Segfault in threading: complex numbers #13380)
• Make Base thread safe (some functions use global or let-bound temp buffers, should be stack allocated instead)
• Stop-the-world GC

Bonus items:

• Integrate task system (and remove yieldto)
• Implement some approach to I/O

[StefanKarpinski]

That's a good list for things that need to be done before threading can be used but I think far less needs to be done before it can be enabled but not used. In fact I think that none of those are necessary for threading support to be enambled by default.

[tkelman]

@yuyichao's opinion was that at least the GC item should be done before enabling it by default. Does the current setup when threads are enabled result in worse performance in the single threaded case?

[ViralBShah]

I do agree that some performance testing would be great to have and we turn on threading by default carefully.

@jrevels Is this something that your perf testing setup you are planning, be used to track?

[JeffBezanson]

Ok, I agree not all of those are necessary. I lowered the priority of some.

I don't think there should be an intermediate state where threading is enabled by default, but shouldn't be used. To me, enabling it by default sends a signal that everybody should feel free to use it.

[StefanKarpinski]

Why does the GC need to be changed before compiling thread support by default? My understanding of the GC situation is that it can only cause problems in cases where threading is actually used. The main issue with turning threading support on currently is that on LLVM 3.7 there's a massive regression in compile time, but @Keno's hard work on LLVM 3.7.1 should fix that once we switch LLVM versions.

[StefanKarpinski]

The point of enabling it by default as a strictly experimental features is so that we can make sure it actually compiles everywhere and can start getting bug reports on crashes from people trying it out but not relying on it as a stable feature. We are not going fix all the potentially crashes in a vacuum.

[yuyichao]

Does the current setup when threads are enabled result in worse performance in the single threaded case?

The only performance regression now is probably the tls access for every GC frame. One main challenge for #14190 is to make sure I don't insert too many GC safepoint / transitions so a performance benchmark would be good.

My understanding of the GC situation is that it can only cause problems in cases where threading is actually used.

If this is what we want, I'm fine with enabling threading for now. I just don't want to encourage people to use threading yet.

The main issue with turning threading support on currently is that on LLVM 3.7 there's a massive regression in compile time,

Threading works fine on LLVM 3.3 now.

[ViralBShah]

I thought threading worked on LLVM 3.3 as well as 3.7 now with @yuyichao's work

[JeffBezanson]

start getting bug reports on crashes

No shortage of those! As it is, it crashes almost constantly. We should at least get to a state where we can say "seems to work ok".

[yuyichao]

Also the stop-the-world is also not the only thing that needs to be fixed in the GC. Many GC internal datastructures are still not thread safe (mostly importantly the remset (for write barrier) and the allocation counter).

[ViralBShah]

@yuyichao The point is to enable threading so that we detect various stability issues in the rest of the codebase, and not necessarily encourage people to use threading. In fact @ArchRobison's PR helps discourage some of the current thread APIs.

[ViralBShah]

Yes - at least all sequential tests need to pass and CI needs to be set up before we can enable threading by default. Ideally, also no performance regressions, but as long as those are identified, I guess it would be ok.

[StefanKarpinski]

We should at least get to a state where we can say "seems to work ok".

I vehemently disagree. We can fix compilation issues and other problems concurrently with making it more stable. I do agree that our test suite needs to pass with threading enabled, but AFAIK, that's already true. If there are platforms where that's not the case, we want to know about them so we can fix them.

[ViralBShah]

@yuyichao Now that things work with LLVM 3.3, I guess we don't need to worry about requiring any updates to the CI system (which was the case before), and threading can get tested. Is that correct? If so, we can at least have a PR with threading enabled, and see if we can get a green.

[yuyichao]

If so, we can at least have a PR with threading enabled, and see if we can get a green.

Yep. As long as we make it clear that it will almost certainly crash for non-trival interaction with the runtime, I'm totally fine with enabling it by default. And we can certainly start by seeing how does Travis and Appveyor like it.

[JeffBezanson]

I don't see the point of shipping something that crashes so much, and where we know we have simple library functions like modf using global buffers. If you want to try something this early-stage, you can set JULIA_THREADS=1. That seems perfectly appropriate to me. Of course we could flip the switch and simply warn people not to use it, but I think the switch-flip sends a stronger signal than anything we post (which not everybody will necessarily read).

[JeffBezanson]

Perhaps a good intermediate state is to enable everything else that JULIA_THREADS=1 enables, but fix nthreads==1 by default. I would be fine with that.

[StefanKarpinski]

People want to try out experimental features without having to compile a special version of Julia. That said, I would be fine with JULIA_THREADS=1 and nthreads == 1, but I still think having it be an experimental feature is better. What are you worried about if we enable it?

[JeffBezanson]

Ok, then this will be fine. All you'll need to do is set an environment variable. What I'm worried about is the appearance of "shipping crap". We need to balance releasing new features ASAP with maintaining rigorous quality standards.

[tkelman]

It's dev master, we're already telling people not to use it for real work. It isn't shipping until it's a stable release branch, and we're still a ways away from that on array and other stdlib work.

[JeffBezanson]

True, but this is a different level of brokenness. Let's at least see if we can fix some of the more flagrant crashes over the next few days.

[jrevels]

@jrevels Is this something that your perf testing setup you are planning, be used to track?

The "testable unit" of the perf tracking framework is just a function call, so as long as a benchmark can be coerced into that form, then the framework should be able to measure its execution.

I'd have to explicitly test out a multithreaded function call to be sure that it doesn't induce any weird breakage, but I can't think of any reason why it shouldn't work in theory.

[ViralBShah]

Should we close this issue for now, or update it for 0.5.0? I am tagging 0.5.0 to make sure this gets reviewed for release, but perhaps 0.5.x is the more suitable tag.

[vtjnash]

this issue doesn't really list anything