| Message ID | 1446484297-837-1-git-send-email-bill.fischofer@linaro.org |
|---|---|
| State | Accepted |
| Commit | efa23a691b1ee37ae7cadcbd22066124b68c34d3 |
| Headers | show |
On Tue, Nov 3, 2015 at 3:21 AM, Nicolas Morey-Chaisemartin <nmorey@kalray.eu > wrote: > > > On 11/02/2015 06:11 PM, Bill Fischofer wrote: > > Enqueueing to ordered queues requires two locks (source and target > > queues). Since any queue can be either source or target, queues do not > > have a natural locking hierarchy. Create one by using the address of > > the qentry as the lock order. > > > > This addresses the aspect of Bug > > https://bugs.linaro.org/show_bug.cgi?id=1879 > > relating to deadlock in unicore systems. > > > > Suggested-by: Nicolas Morey-Chaisemartin <nmorey@kalray.eu> > > Signed-off-by: Bill Fischofer <bill.fischofer@linaro.org> > > --- > > platform/linux-generic/odp_queue.c | 39 > +++++++++++++++++++++++++++++--------- > > 1 file changed, 30 insertions(+), 9 deletions(-) > > > > diff --git a/platform/linux-generic/odp_queue.c > b/platform/linux-generic/odp_queue.c > > index a27af0b..1c15e17 100644 > > --- a/platform/linux-generic/odp_queue.c > > +++ b/platform/linux-generic/odp_queue.c > > @@ -48,6 +48,28 @@ typedef struct queue_table_t { > > static queue_table_t *queue_tbl; > > > > > > +static inline void get_qe_locks(queue_entry_t *qe1, queue_entry_t *qe2) > > +{ > > + /* Special case: enq to self */ > > + if (qe1 == qe2) { > > + LOCK(&qe1->s.lock); > > + return; > > + } > > + > > + /* Since any queue can be either a source or target, queues do > not have > > + * a natural locking hierarchy. Create one by using the qentry > address > > + * as the ordering mechanism. > > + */ > > + > > + if (qe1 < qe2) { > > + LOCK(&qe1->s.lock); > > + LOCK(&qe2->s.lock); > > + } else { > > + LOCK(&qe2->s.lock); > > + LOCK(&qe1->s.lock); > > + } > > +} > > + > > queue_entry_t *get_qentry(uint32_t queue_id) > > { > > return &queue_tbl->queue[queue_id]; > > @@ -370,14 +392,11 @@ int queue_enq(queue_entry_t *queue, > odp_buffer_hdr_t *buf_hdr, int sustain) > > > > /* Need two locks for enq operations from ordered queues */ > > if (origin_qe) { > > - LOCK(&origin_qe->s.lock); > > - while (!LOCK_TRY(&queue->s.lock)) { > > - UNLOCK(&origin_qe->s.lock); > > - LOCK(&origin_qe->s.lock); > > - } > > + get_qe_locks(origin_qe, queue); > > if (odp_unlikely(origin_qe->s.status < > QUEUE_STATUS_READY)) { > > UNLOCK(&queue->s.lock); > > - UNLOCK(&origin_qe->s.lock); > > + if (origin_qe != queue) > This test is unneeded as we are already in a if(origin_qe) branch > We're in that branch, however origin_qe will be equal to queue if a buffer originating from origin_qe is being queued back to origin_qe. In that case queue == origin_qe, so there's only one lock that should be unlocked. > > + UNLOCK(&origin_qe->s.lock); > > ODP_ERR("Bad origin queue status\n"); > > ODP_ERR("queue = %s, origin q = %s, buf = %p\n", > > queue->s.name, origin_qe->s.name, > buf_hdr); > > @@ -389,7 +408,7 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t > *buf_hdr, int sustain) > > > > if (odp_unlikely(queue->s.status < QUEUE_STATUS_READY)) { > > UNLOCK(&queue->s.lock); > > - if (origin_qe) > > + if (origin_qe && origin_qe != queue) > > UNLOCK(&origin_qe->s.lock); > If we are factoring this test in get_qe_locks, it might make sense to add > a release_qe_locks that does the same > That's reasonable, however in other cases we want to release them separately to increase parallelism because we're done with one but still have need for the other, so you'd still have both. > > > ODP_ERR("Bad queue status\n"); > > return -1; > > @@ -405,7 +424,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t > *buf_hdr, int sustain) > > * we're done here. > > */ > > UNLOCK(&queue->s.lock); > > - UNLOCK(&origin_qe->s.lock); > > + if (origin_qe != queue) > > + UNLOCK(&origin_qe->s.lock); > > return 0; > > } > > > > @@ -477,7 +497,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t > *buf_hdr, int sustain) > > /* Now handle any unblocked complete buffers destined for > > * other queues, appending placeholder bufs as needed. > > */ > > - UNLOCK(&queue->s.lock); > > + if (origin_qe != queue) > > + UNLOCK(&queue->s.lock); > > reorder_complete(origin_qe, &reorder_buf, &placeholder_buf, > > 1, 0); > > UNLOCK(&origin_qe->s.lock); > > Regarding the API-NEXT issue, this will be propagated into master as part of v1.4.1.
It's fixing the deadlock issue reported by Carl where A is queueing to B and B is queuing to A. The previous scheme relied on a statistical locking strategy that was prone to stalls, especially on uniprocessor systems. Your suggestion solves this issue and is also simpler and faster. Concurrent with that it also solves the deadlock that would arise if A is queueing to A since that case had not been previously been handled. Given the size of the patch I'm not sure if it makes sense to try to split it further. The larger issue is that we're still not maintaining order in all cases (ordered queues are surprisingly subtle in SW, especially given the ability to insert and delete elements in an ordered flow). I'm close to understanding what's going on with that and will have a separate patch for that issue. On Tue, Nov 3, 2015 at 7:13 AM, Nicolas Morey-Chaisemartin <nmorey@kalray.eu > wrote: > > > On 11/03/2015 10:21 AM, Nicolas Morey-Chaisemartin wrote: > > > > On 11/02/2015 06:11 PM, Bill Fischofer wrote: > >> Enqueueing to ordered queues requires two locks (source and target > >> queues). Since any queue can be either source or target, queues do not > >> have a natural locking hierarchy. Create one by using the address of > >> the qentry as the lock order. > >> > >> This addresses the aspect of Bug > >> https://bugs.linaro.org/show_bug.cgi?id=1879 > >> relating to deadlock in unicore systems. > >> > >> Suggested-by: Nicolas Morey-Chaisemartin <nmorey@kalray.eu> > >> Signed-off-by: Bill Fischofer <bill.fischofer@linaro.org> > >> --- > >> platform/linux-generic/odp_queue.c | 39 > +++++++++++++++++++++++++++++--------- > >> 1 file changed, 30 insertions(+), 9 deletions(-) > >> > >> diff --git a/platform/linux-generic/odp_queue.c > b/platform/linux-generic/odp_queue.c > >> index a27af0b..1c15e17 100644 > >> --- a/platform/linux-generic/odp_queue.c > >> +++ b/platform/linux-generic/odp_queue.c > >> @@ -48,6 +48,28 @@ typedef struct queue_table_t { > >> static queue_table_t *queue_tbl; > >> > >> > >> +static inline void get_qe_locks(queue_entry_t *qe1, queue_entry_t *qe2) > >> +{ > >> + /* Special case: enq to self */ > >> + if (qe1 == qe2) { > >> + LOCK(&qe1->s.lock); > >> + return; > >> + } > >> + > >> + /* Since any queue can be either a source or target, queues do > not have > >> + * a natural locking hierarchy. Create one by using the qentry > address > >> + * as the ordering mechanism. > >> + */ > >> + > >> + if (qe1 < qe2) { > >> + LOCK(&qe1->s.lock); > >> + LOCK(&qe2->s.lock); > >> + } else { > >> + LOCK(&qe2->s.lock); > >> + LOCK(&qe1->s.lock); > >> + } > >> +} > >> + > >> queue_entry_t *get_qentry(uint32_t queue_id) > >> { > >> return &queue_tbl->queue[queue_id]; > >> @@ -370,14 +392,11 @@ int queue_enq(queue_entry_t *queue, > odp_buffer_hdr_t *buf_hdr, int sustain) > >> > >> /* Need two locks for enq operations from ordered queues */ > >> if (origin_qe) { > >> - LOCK(&origin_qe->s.lock); > >> - while (!LOCK_TRY(&queue->s.lock)) { > >> - UNLOCK(&origin_qe->s.lock); > >> - LOCK(&origin_qe->s.lock); > >> - } > >> + get_qe_locks(origin_qe, queue); > >> if (odp_unlikely(origin_qe->s.status < > QUEUE_STATUS_READY)) { > >> UNLOCK(&queue->s.lock); > >> - UNLOCK(&origin_qe->s.lock); > >> + if (origin_qe != queue) > > This test is unneeded as we are already in a if(origin_qe) branch > Agreed. > This patch is actually fixing 2 issues (if I read it right): > * Actual deadlock issues if qe == origin_qe > * Linux scheduling issues > > It would be nice to split the patch or update the log accordingly. > Other than that, it looks good. > > Nicolas >
merged to api-next. On 11/03/2015 12:53, Nicolas Morey-Chaisemartin wrote: > Also, why is this only applied to API-NEXT ? Doesn't master have the same "deadlock" issue? I used api-next as staging branch for patches which do not have anybody else Review-by: Will merge that patches to master shortly. Maxim. > On 11/02/2015 06:11 PM, Bill Fischofer wrote: >> Enqueueing to ordered queues requires two locks (source and target >> queues). Since any queue can be either source or target, queues do not >> have a natural locking hierarchy. Create one by using the address of >> the qentry as the lock order. >> >> This addresses the aspect of Bug >> https://bugs.linaro.org/show_bug.cgi?id=1879 >> relating to deadlock in unicore systems. >> >> Suggested-by: Nicolas Morey-Chaisemartin <nmorey@kalray.eu> >> Signed-off-by: Bill Fischofer <bill.fischofer@linaro.org> >> --- >> platform/linux-generic/odp_queue.c | 39 +++++++++++++++++++++++++++++--------- >> 1 file changed, 30 insertions(+), 9 deletions(-) >> >> diff --git a/platform/linux-generic/odp_queue.c b/platform/linux-generic/odp_queue.c >> index a27af0b..1c15e17 100644 >> --- a/platform/linux-generic/odp_queue.c >> +++ b/platform/linux-generic/odp_queue.c >> @@ -48,6 +48,28 @@ typedef struct queue_table_t { >> static queue_table_t *queue_tbl; >> >> >> +static inline void get_qe_locks(queue_entry_t *qe1, queue_entry_t *qe2) >> +{ >> + /* Special case: enq to self */ >> + if (qe1 == qe2) { >> + LOCK(&qe1->s.lock); >> + return; >> + } >> + >> + /* Since any queue can be either a source or target, queues do not have >> + * a natural locking hierarchy. Create one by using the qentry address >> + * as the ordering mechanism. >> + */ >> + >> + if (qe1 < qe2) { >> + LOCK(&qe1->s.lock); >> + LOCK(&qe2->s.lock); >> + } else { >> + LOCK(&qe2->s.lock); >> + LOCK(&qe1->s.lock); >> + } >> +} >> + >> queue_entry_t *get_qentry(uint32_t queue_id) >> { >> return &queue_tbl->queue[queue_id]; >> @@ -370,14 +392,11 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) >> >> /* Need two locks for enq operations from ordered queues */ >> if (origin_qe) { >> - LOCK(&origin_qe->s.lock); >> - while (!LOCK_TRY(&queue->s.lock)) { >> - UNLOCK(&origin_qe->s.lock); >> - LOCK(&origin_qe->s.lock); >> - } >> + get_qe_locks(origin_qe, queue); >> if (odp_unlikely(origin_qe->s.status < QUEUE_STATUS_READY)) { >> UNLOCK(&queue->s.lock); >> - UNLOCK(&origin_qe->s.lock); >> + if (origin_qe != queue) >> + UNLOCK(&origin_qe->s.lock); >> ODP_ERR("Bad origin queue status\n"); >> ODP_ERR("queue = %s, origin q = %s, buf = %p\n", >> queue->s.name, origin_qe->s.name, buf_hdr); >> @@ -389,7 +408,7 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) >> >> if (odp_unlikely(queue->s.status < QUEUE_STATUS_READY)) { >> UNLOCK(&queue->s.lock); >> - if (origin_qe) >> + if (origin_qe && origin_qe != queue) >> UNLOCK(&origin_qe->s.lock); >> ODP_ERR("Bad queue status\n"); >> return -1; >> @@ -405,7 +424,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) >> * we're done here. >> */ >> UNLOCK(&queue->s.lock); >> - UNLOCK(&origin_qe->s.lock); >> + if (origin_qe != queue) >> + UNLOCK(&origin_qe->s.lock); >> return 0; >> } >> >> @@ -477,7 +497,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) >> /* Now handle any unblocked complete buffers destined for >> * other queues, appending placeholder bufs as needed. >> */ >> - UNLOCK(&queue->s.lock); >> + if (origin_qe != queue) >> + UNLOCK(&queue->s.lock); >> reorder_complete(origin_qe, &reorder_buf, &placeholder_buf, >> 1, 0); >> UNLOCK(&origin_qe->s.lock); > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org > https://lists.linaro.org/mailman/listinfo/lng-odp
diff --git a/platform/linux-generic/odp_queue.c b/platform/linux-generic/odp_queue.c index a27af0b..1c15e17 100644 --- a/platform/linux-generic/odp_queue.c +++ b/platform/linux-generic/odp_queue.c @@ -48,6 +48,28 @@ typedef struct queue_table_t { static queue_table_t *queue_tbl; +static inline void get_qe_locks(queue_entry_t *qe1, queue_entry_t *qe2) +{ + /* Special case: enq to self */ + if (qe1 == qe2) { + LOCK(&qe1->s.lock); + return; + } + + /* Since any queue can be either a source or target, queues do not have + * a natural locking hierarchy. Create one by using the qentry address + * as the ordering mechanism. + */ + + if (qe1 < qe2) { + LOCK(&qe1->s.lock); + LOCK(&qe2->s.lock); + } else { + LOCK(&qe2->s.lock); + LOCK(&qe1->s.lock); + } +} + queue_entry_t *get_qentry(uint32_t queue_id) { return &queue_tbl->queue[queue_id]; @@ -370,14 +392,11 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) /* Need two locks for enq operations from ordered queues */ if (origin_qe) { - LOCK(&origin_qe->s.lock); - while (!LOCK_TRY(&queue->s.lock)) { - UNLOCK(&origin_qe->s.lock); - LOCK(&origin_qe->s.lock); - } + get_qe_locks(origin_qe, queue); if (odp_unlikely(origin_qe->s.status < QUEUE_STATUS_READY)) { UNLOCK(&queue->s.lock); - UNLOCK(&origin_qe->s.lock); + if (origin_qe != queue) + UNLOCK(&origin_qe->s.lock); ODP_ERR("Bad origin queue status\n"); ODP_ERR("queue = %s, origin q = %s, buf = %p\n", queue->s.name, origin_qe->s.name, buf_hdr); @@ -389,7 +408,7 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) if (odp_unlikely(queue->s.status < QUEUE_STATUS_READY)) { UNLOCK(&queue->s.lock); - if (origin_qe) + if (origin_qe && origin_qe != queue) UNLOCK(&origin_qe->s.lock); ODP_ERR("Bad queue status\n"); return -1; @@ -405,7 +424,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) * we're done here. */ UNLOCK(&queue->s.lock); - UNLOCK(&origin_qe->s.lock); + if (origin_qe != queue) + UNLOCK(&origin_qe->s.lock); return 0; } @@ -477,7 +497,8 @@ int queue_enq(queue_entry_t *queue, odp_buffer_hdr_t *buf_hdr, int sustain) /* Now handle any unblocked complete buffers destined for * other queues, appending placeholder bufs as needed. */ - UNLOCK(&queue->s.lock); + if (origin_qe != queue) + UNLOCK(&queue->s.lock); reorder_complete(origin_qe, &reorder_buf, &placeholder_buf, 1, 0); UNLOCK(&origin_qe->s.lock);
Enqueueing to ordered queues requires two locks (source and target queues). Since any queue can be either source or target, queues do not have a natural locking hierarchy. Create one by using the address of the qentry as the lock order. This addresses the aspect of Bug https://bugs.linaro.org/show_bug.cgi?id=1879 relating to deadlock in unicore systems. Suggested-by: Nicolas Morey-Chaisemartin <nmorey@kalray.eu> Signed-off-by: Bill Fischofer <bill.fischofer@linaro.org> --- platform/linux-generic/odp_queue.c | 39 +++++++++++++++++++++++++++++--------- 1 file changed, 30 insertions(+), 9 deletions(-)