Re: [PATCH] apr_queue race condition
David Reid wrote: I share the concern so +1 for the concept. I'm also not familiar enough with the code to commit it but hopefully someone who is can have a look before too long... Aaron? Ian? david I'll commit it soon. --Ian --On Monday, February 10, 2003 2:10 PM -0800 Jacob Lewallen <[EMAIL PROTECTED]> wrote: Can you do us a big favor and please resubmit the patch without any whitespace changes? That is, only diff what you actually changed. We No problem. Here she is. In this case, I'll defer to the people who know this code better than I do. I think even if the queue size is of the correct size, too many consumers could rush in and get stuck waiting on the empty case which may never come. So, yeah. +1 in concept. This is better than doing the broadcast approach which could be expensive. -- justin
Re: [PATCH] apr_queue race condition
Thanks for the patch, and thanks for using APR! Regards Ian On Sun, 09 Feb 2003 13:28:13 -0800, Jacob Lewallen wrote: >Hi there, I've stumbled on a bug in the apr_queue_t code... When > calling apr_queue_pop to retrieve an item from the queue the call may > block indefinately despite items having been pushed in. Same things goes > for calls to apr_queue_push that are blocking until there is room in the > queue (they may stay blocked even though items have been popped from the > queue). The problem lies in the logic that manages the two conditions that > help operate the queue - NOT_EMPTY, and NOT_FULL. In apr_queue_push, the > NOT_EMPTY condition is only signaled if the queue was empty prior to > adding the new item. This can cause problems if there are multiple threads > blocked in calls to apr_queue_pop and then two or more successive calls to > apr_queue_push are handled prior to one of the apr_queue_pop awakening... > for example: > > apr_queue_pop1 [BLOCKED] (nelts = 0) > apr_queue_pop2 [BLOCKED] (nelts = 0) > apr_queue_pop3 [BLOCKED] (nelts = 0) > apr_queue_push1 (nelts = 1) (nelts was 0, so signals) apr_queue_push2 > (nelts = 2) > apr_queue_pop1 [UNBLOCKS] (nelts = 1) (awake from push1's signal) > apr_queue_push3 (nelts = 2) > apr_queue_push4 (nelts = 3) > > pop2, pop3 as well as any others remained blocked. > > Similar logic is used to handle blocked calls to apr_queue_push. My > solution was to add two variables to apr_queue_t to track the number of > threads waiting for a non-full and non-empty state, and choosing to signal > the conditions based on those variables. So far this has worked fine for > me. testqueue doesn't seem to catch this because of the way it's written > (timing delays betwee calls make this harder to catch) > > I've attached a patch. I appreciate any comments, it being my first patch > and all. > > --- > jacob lewallen > [EMAIL PROTECTED] > Index: apr_queue.c >
Re: [PATCH] apr_queue race condition
It looked fine at first glance, but I'll have to take a closer look later today. -aaron On Tuesday, February 11, 2003, at 10:26 AM, David Reid wrote: I share the concern so +1 for the concept. I'm also not familiar enough with the code to commit it but hopefully someone who is can have a look before too long... Aaron? Ian?
Re: [PATCH] apr_queue race condition
I share the concern so +1 for the concept. I'm also not familiar enough with the code to commit it but hopefully someone who is can have a look before too long... Aaron? Ian? david > --On Monday, February 10, 2003 2:10 PM -0800 Jacob Lewallen > <[EMAIL PROTECTED]> wrote: > > >> > >> Can you do us a big favor and please resubmit the patch without > >> any whitespace changes? That is, only diff what you actually > >> changed. We > > > > No problem. Here she is. > > In this case, I'll defer to the people who know this code better than > I do. > > I think even if the queue size is of the correct size, too many > consumers could rush in and get stuck waiting on the empty case which > may never come. So, yeah. +1 in concept. This is better than doing > the broadcast approach which could be expensive. -- justin >
Re: [PATCH] apr_queue race condition
--On Monday, February 10, 2003 2:10 PM -0800 Jacob Lewallen <[EMAIL PROTECTED]> wrote: Can you do us a big favor and please resubmit the patch without any whitespace changes? That is, only diff what you actually changed. We No problem. Here she is. In this case, I'll defer to the people who know this code better than I do. I think even if the queue size is of the correct size, too many consumers could rush in and get stuck waiting on the empty case which may never come. So, yeah. +1 in concept. This is better than doing the broadcast approach which could be expensive. -- justin
Re: [PATCH] apr_queue race condition
Can you do us a big favor and please resubmit the patch without any
whitespace changes? That is, only diff what you actually changed. We
No problem. Here she is.
--
jacob lewallen
[EMAIL PROTECTED]
Index: apr_queue.c
===
RCS file: /home/cvspublic/apr-util/misc/apr_queue.c,v
retrieving revision 1.10
diff -u -u -r1.10 apr_queue.c
--- apr_queue.c 13 Jan 2003 20:15:50 - 1.10
+++ apr_queue.c 10 Feb 2003 22:08:31 -
@@ -85,6 +85,8 @@
unsigned intin;/**< next empty location */
unsigned intout; /**< next filled location */
unsigned intbounds;/**< max size of queue */
+unsigned intfull_waiters;
+unsigned intempty_waiters;
apr_thread_mutex_t *one_big_mutex;
apr_thread_cond_t *not_empty;
apr_thread_cond_t *not_full;
@@ -169,6 +171,8 @@
queue->in = 0;
queue->out = 0;
queue->terminated = 0;
+queue->full_waiters = 0;
+queue->empty_waiters = 0;
apr_pool_cleanup_register(a, queue, queue_destroy, apr_pool_cleanup_null);
@@ -183,7 +187,6 @@
APU_DECLARE(apr_status_t) apr_queue_push(apr_queue_t *queue, void *data)
{
apr_status_t rv;
-int need_signal = 0;
if (queue->terminated) {
return APR_EOF; /* no more elements ever again */
@@ -196,7 +199,9 @@
if (apr_queue_full(queue)) {
if (!queue->terminated) {
+queue->full_waiters++;
rv = apr_thread_cond_wait(queue->not_full, queue->one_big_mutex);
+queue->full_waiters--;
if (rv != APR_SUCCESS) {
apr_thread_mutex_unlock(queue->one_big_mutex);
return rv;
@@ -218,16 +223,11 @@
}
}
-/* if we were empty then signal that we aren't */
-if (apr_queue_empty(queue)) {
-need_signal = 1;
-}
-
queue->data[queue->in] = data;
queue->in = (queue->in + 1) % queue->bounds;
queue->nelts++;
-if (need_signal == 1) {
+if (queue->empty_waiters) {
Q_DBG("sig !empty", queue);
rv = apr_thread_cond_signal(queue->not_empty);
if (rv != APR_SUCCESS) {
@@ -248,7 +248,7 @@
APU_DECLARE(apr_status_t) apr_queue_trypush(apr_queue_t *queue, void *data)
{
apr_status_t rv;
-int need_signal = 0;
+
if (queue->terminated) {
return APR_EOF; /* no more elements ever again */
}
@@ -262,17 +262,12 @@
rv = apr_thread_mutex_unlock(queue->one_big_mutex);
return APR_EAGAIN;
}
-
-/* if we were empty then signal that we aren't */
-if (apr_queue_empty(queue)) {
-need_signal = 1;
-}
queue->data[queue->in] = data;
queue->in = (queue->in + 1) % queue->bounds;
queue->nelts++;
-if (need_signal == 1) {
+if (queue->empty_waiters) {
Q_DBG("sig !empty", queue);
rv = apr_thread_cond_signal(queue->not_empty);
if (rv != APR_SUCCESS) {
@@ -301,7 +296,6 @@
APU_DECLARE(apr_status_t) apr_queue_pop(apr_queue_t *queue, void **data)
{
apr_status_t rv;
-int need_signal = 0;
if (queue->terminated) {
return APR_EOF; /* no more elements ever again */
@@ -315,7 +309,9 @@
/* Keep waiting until we wake up and find that the queue is not empty. */
if (apr_queue_empty(queue)) {
if (!queue->terminated) {
+queue->empty_waiters++;
rv = apr_thread_cond_wait(queue->not_empty, queue->one_big_mutex);
+queue->empty_waiters--;
if (rv != APR_SUCCESS) {
apr_thread_mutex_unlock(queue->one_big_mutex);
return rv;
@@ -336,15 +332,12 @@
}
}
}
-if (apr_queue_full(queue)) {
-need_signal = 1;
-}
*data = &queue->data[queue->out];
queue->nelts--;
queue->out = (queue->out + 1) % queue->bounds;
-if (need_signal == 1) {
+if (queue->full_waiters) {
Q_DBG("signal !full", queue);
rv = apr_thread_cond_signal(queue->not_full);
if (rv != APR_SUCCESS) {
@@ -366,7 +359,6 @@
APU_DECLARE(apr_status_t) apr_queue_trypop(apr_queue_t *queue, void **data)
{
apr_status_t rv;
-int need_signal = 0;
if (queue->terminated) {
return APR_EOF; /* no more elements ever again */
@@ -382,15 +374,12 @@
rv = apr_thread_mutex_unlock(queue->one_big_mutex);
return APR_EAGAIN;
}
-if (apr_queue_full(queue)) {
-need_signal = 1;
-}
*data = &queue->data[queue->out];
queue->nelts--;
queue->out = (queue->out + 1) % queue->bounds;
-if (need_signal == 1) {
+if (queue->full_waiters) {
Q_DBG("signal !full", queue);
rv = apr_thread_cond_signal(queue->not_full);
if (rv != APR_SUCCESS) {
Re: [PATCH] apr_queue race condition
--On Sunday, February 9, 2003 1:28 PM -0800 Jacob Lewallen <[EMAIL PROTECTED]> wrote: I've attached a patch. I appreciate any comments, it being my first patch and all. Sounds about right. Can you do us a big favor and please resubmit the patch without any whitespace changes? That is, only diff what you actually changed. We don't change whitespace with code changes in the same commit/patch. This makes it really hard to review your patch. Thanks! -- justin
Re: [PATCH] apr_queue race condition
Ian Holsman wrote: On Sun, 09 Feb 2003 13:28:13 -0800, Jacob Lewallen wrote: Hi there, I've stumbled on a bug in the apr_queue_t code... When calling apr_queue_pop to retrieve an item from the queue the call may block indefinately despite items having been pushed in. Same things goes for calls to apr_queue_push that are blocking until there is room in the queue (they may stay blocked even though items have been popped from the queue). The problem lies in the logic that manages the two conditions that help operate the queue - NOT_EMPTY, and NOT_FULL. In apr_queue_push, the NOT_EMPTY condition is only signaled if the queue was empty prior to adding the new item. This can cause problems if there are multiple threads blocked in calls to apr_queue_pop and then two or more successive calls to apr_queue_push are handled prior to one of the apr_queue_pop awakening... for example: another approach would be just to send signals every time a pop/push occurs, or to have the pop/push wake every waiting thread and try to get them to re-lock it. Yes, this would absolutely work and was something I did in narrowing down the problem. My intention in the patch was to keep the spirit of the original implementation and only signal when necessary, since that seemed to be a good idea. The solution is really unimportant to me, but I make heavy use of apr_queue in some software of mine so a working apr_queue is my priority. Thanks, -- jacob lewallen [EMAIL PROTECTED]
