This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "MPICH primary repository". The branch, master has been updated via 0eeed17df88f41285e43c61a4f6863c0c0b85fb3 (commit) from 2e46f3a6b660dba9c1ac8ffd4c1767ef548df077 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- http://git.mpich.org/mpich.git/commitdiff/0eeed17df88f41285e43c61a4f6863c0c0... commit 0eeed17df88f41285e43c61a4f6863c0c0b85fb3 Author: Huiwei Lu <[email protected]> Date: Tue Jul 15 17:34:26 2014 -0500 Fixes deadlock in multi-threaded MPI_Comm_idup This patch implements the "eager" protocol used in MPI_Comm_idup. Without this patch, test/mpi/threads/comm/comm_idup will crash due to segmentation fault caused by livelock. It uses the same algorithm as multi-threaded MPIR_Get_contextid_sparse_group to avoid deadlock in multi-threaded context_id allocation, but in a nonblocking way. The nonblocking mechanism is explained in the comment of function sched_get_cid_nonblock. Fixes #2069 Signed-off-by: Pavan Balaji <[email protected]> diff --git a/src/mpi/comm/commutil.c b/src/mpi/comm/commutil.c index 8713a2f..60db478 100644 --- a/src/mpi/comm/commutil.c +++ b/src/mpi/comm/commutil.c @@ -833,7 +833,17 @@ fn_fail: } -/* In multi-threaded case, mask_in_used is used to maintain thread safety. In +/* EAGER CONTEXT ID ALLOCATION: Attempt to allocate the context ID during the + * initial synchronization step. If eager protocol fails, threads fall back to + * the base algorithm. + * + * They are used to avoid deadlock in multi-threaded case. In single-threaded + * case, they are not used. + */ +static volatile int eager_nelem = -1; +static volatile int eager_in_use = 0; + +/* In multi-threaded case, mask_in_use is used to maintain thread safety. In * single-threaded case, it is always 0. */ static volatile int mask_in_use = 0; @@ -938,13 +948,6 @@ fn_fail: #else /* MPICH_IS_THREADED is set and true */ -/* EAGER CONTEXT ID ALLOCATION: Attempt to allocate the context ID during the - * initial synchronization step. If eager protocol fails, threads fall back to - * the base algorithm. - */ -static volatile int eager_nelem = -1; -static volatile int eager_in_use = 0; - #undef FUNCNAME #define FUNCNAME MPIR_Get_contextid_sparse #undef FCNAME @@ -1230,6 +1233,8 @@ struct gcn_state { MPIR_Context_id_t *ctx0; MPIR_Context_id_t *ctx1; int own_mask; + int own_eager_mask; + int first_iter; MPID_Comm *comm_ptr; MPID_Comm *comm_ptr_inter; MPID_Sched_t s; @@ -1283,21 +1288,48 @@ static int sched_cb_gcn_allocate_cid(MPID_Comm *comm, int tag, void *state) MPIR_Context_id_t newctxid; MPIU_THREAD_CS_ENTER(CONTEXTID,); - if (st->own_mask) { + if (st->own_eager_mask) { + newctxid = MPIR_Find_and_allocate_context_id(st->local_mask); + if (st->ctx0) + *st->ctx0 = newctxid; + if (st->ctx1) + *st->ctx1 = newctxid; + + st->own_eager_mask = 0; + eager_in_use = 0; + + if (newctxid <= 0) { + /* else we did not find a context id. Give up the mask in case + * there is another thread (with a lower input context id) + * waiting for it. We need to ensure that any other threads + * have the opportunity to run, hence yielding */ + MPIU_THREAD_CS_YIELD(CONTEXTID,); + } + } else if (st->own_mask) { newctxid = MPIR_Find_and_allocate_context_id(st->local_mask); if (st->ctx0) *st->ctx0 = newctxid; if (st->ctx1) *st->ctx1 = newctxid; + + /* reset flags for the next try */ mask_in_use = 0; if (newctxid > 0) { if (lowestContextId == st->comm_ptr->context_id) lowestContextId = MPIR_MAXID; + } else { + /* else we did not find a context id. Give up the mask in case + * there is another thread (with a lower input context id) + * waiting for it. We need to ensure that any other threads + * have the opportunity to run, hence yielding */ + MPIU_THREAD_CS_YIELD(CONTEXTID,); } + } else { + /* As above, force this thread to yield */ + MPIU_THREAD_CS_YIELD(CONTEXTID,); } - MPIU_THREAD_CS_EXIT(CONTEXTID,); if (*st->ctx0 == 0) { /* do not own mask, try again */ @@ -1311,6 +1343,8 @@ static int sched_cb_gcn_allocate_cid(MPID_Comm *comm, int tag, void *state) MPID_SCHED_BARRIER(st->s); } + MPIU_THREAD_CS_EXIT(CONTEXTID,); + /* --BEGIN ERROR HANDLING-- */ /* --END ERROR HANDLING-- */ fn_fail: @@ -1327,18 +1361,40 @@ static int sched_cb_gcn_copy_mask(MPID_Comm *comm, int tag, void *state) struct gcn_state *st = state; MPIU_THREAD_CS_ENTER(CONTEXTID,); - if (st->comm_ptr->context_id < lowestContextId) { - lowestContextId = st->comm_ptr->context_id; - } - if (mask_in_use || (st->comm_ptr->context_id != lowestContextId)) { + if (st->first_iter) { memset(st->local_mask, 0, MPIR_MAX_CONTEXT_MASK * sizeof(int)); - st->own_mask = 0; + st->own_eager_mask = 0; + + /* Attempt to reserve the eager mask segment */ + if (!eager_in_use && eager_nelem > 0) { + int i; + for (i = 0; i < eager_nelem; i++) + st->local_mask[i] = context_mask[i]; + + eager_in_use = 1; + st->own_eager_mask = 1; + } + st->first_iter = 0; } else { - MPIU_Memcpy(st->local_mask, context_mask, MPIR_MAX_CONTEXT_MASK * sizeof(uint32_t)); - mask_in_use = 1; - st->own_mask = 1; + if (st->comm_ptr->context_id < lowestContextId) { + lowestContextId = st->comm_ptr->context_id; + } + if (mask_in_use || (st->comm_ptr->context_id != lowestContextId)) { + memset(st->local_mask, 0, MPIR_MAX_CONTEXT_MASK * sizeof(int)); + st->own_mask = 0; + } else { + /* Copy safe mask segment to local_mask */ + int i; + for (i = 0; i < eager_nelem; i++) + st->local_mask[i] = 0; + for (i = eager_nelem; i < MPIR_MAX_CONTEXT_MASK; i++) + st->local_mask[i] = context_mask[i]; + + mask_in_use = 1; + st->own_mask = 1; + } } - MPIU_THREAD_CS_ENTER(CONTEXTID,); + MPIU_THREAD_CS_EXIT(CONTEXTID,); mpi_errno = st->comm_ptr->coll_fns->Iallreduce_sched(MPI_IN_PLACE, st->local_mask, MPIR_MAX_CONTEXT_MASK, MPI_UINT32_T, MPI_BAND, st->comm_ptr, st->s); @@ -1354,28 +1410,41 @@ fn_fail: } -/** The multi-threaded nonblocking algorithm of getting a context id +/** Allocating a new context ID collectively over the given communicator in a + * nonblocking way. + * + * The nonblocking mechanism is implemented by inserting MPIDU_Sched_entry to + * the nonblocking collective progress, which is a part of the progress engine. + * It uses a two-level linked list 'all_schedules' to manager all nonblocking + * collective calls: the first level is a linked list of struct MPIDU_Sched; + * and each struct MPIDU_Sched is an array of struct MPIDU_Sched_entry. The + * following four functions are used together to implement the algorithm: + * sched_cb_gcn_copy_mask, sched_cb_gcn_allocate_cid, sched_cb_gcn_bcast and + * sched_get_cid_nonblock. * - * 1. It shares the same global flag 'mask_in_use' with other communicator - * functions to protect access to context_mask. And use CONTEXTID lock to - * protext critical sections. + * The above four functions use the same algorithm as + * MPIR_Get_contextid_sparse_group (multi-threaded version) to allocate a + * context id. The algorithm needs to retry the allocation process in the case + * of conflicts. In MPIR_Get_contextid_sparse_group, it is a while loop. In + * the nonblocking algorithm, 1) new entries are inserted to the end of + * schedule to replace the 'while' loop in MPI_Comm_dup algorithm; 2) all + * arguments passed to sched_get_cid_nonblock are saved to gcn_state in order + * to be called in the future; 3) in sched_cb_gcn_allocate_cid, if the first + * try failed, it will insert sched_cb_gcn_copy_mask to the schedule again. * - * 2. It uses the same algorithm as multithreaded MPI_Comm_dup (multi-threaded - * vertion of MPIR_Get_contextid_sparse_group) to allocate a context id, but in - * a nonblocking way. In the case of conflicts, the algorithm needs to retry - * the allocation process again. In the nonblocking algorithm, 1) new entries - * are inserted to the end of schedule to replace the 'while' loop in - * MPI_Comm_dup algorithm; 2) all arguments passed to sched_get_cid_nonblock - * are saved to gcn_state in order to be called in the future; 3) in - * sched_cb_gcn_allocate_cid, if the first try failed, it will insert - * sched_cb_gcn_copy_mask to the schedule again. + * To ensure thread-safety, it shares the same global flag 'mask_in_use' with + * other communicator functions to protect access to context_mask. And use + * CONTEXTID lock to protect critical sections. * - * 3. There is a subtle difference between INTRACOMM and INTERCOMM when + * There is a subtle difference between INTRACOMM and INTERCOMM when * duplicating a communicator. They needed to be treated differently in * current algorithm. Specifically, 1) when calling sched_get_cid_nonblock, the * parameters are different; 2) updating newcommp->recvcontext_id in * MPIR_Get_intercomm_contextid_nonblock has been moved to sched_cb_gcn_bcast * because this should happen after sched_cb_gcn_allocate_cid has succeed. + * + * To avoid deadlock or livelock, it uses the same eager protocol as + * multi-threaded MPIR_Get_contextid_sparse_group. */ #undef FUNCNAME #define FUNCNAME sched_get_cid_nonblock @@ -1406,6 +1475,14 @@ static int sched_get_cid_nonblock(MPID_Comm *comm_ptr, MPIR_Context_id_t *ctx0, st->s = s; st->gcn_cid_kind = gcn_cid_kind; *(st->ctx0) = 0; + st->own_eager_mask = 0; + st->first_iter = 1; + if (eager_nelem < 0) { + /* Ensure that at least one word of deadlock-free context IDs is + always set aside for the base protocol */ + MPIU_Assert( MPIR_CVAR_CTXID_EAGER_SIZE >= 0 && MPIR_CVAR_CTXID_EAGER_SIZE < MPIR_MAX_CONTEXT_MASK-1 ); + eager_nelem = MPIR_CVAR_CTXID_EAGER_SIZE; + } MPIU_THREAD_CS_EXIT(CONTEXTID,); mpi_errno = MPID_Sched_cb(&sched_cb_gcn_copy_mask, st, s); diff --git a/test/mpi/threads/comm/testlist b/test/mpi/threads/comm/testlist index 6d94573..2dfc780 100644 --- a/test/mpi/threads/comm/testlist +++ b/test/mpi/threads/comm/testlist @@ -3,5 +3,5 @@ dup_leak_test 2 comm_dup_deadlock 4 comm_create_threads 4 comm_create_group_threads 4 -comm_idup 4 mpiversion=3.0 xfail=ticket2069 +comm_idup 4 mpiversion=3.0 ctxidup 4 ----------------------------------------------------------------------- Summary of changes: src/mpi/comm/commutil.c | 143 ++++++++++++++++++++++++++++++--------- test/mpi/threads/comm/testlist | 2 +- 2 files changed, 111 insertions(+), 34 deletions(-) hooks/post-receive -- MPICH primary repository