You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Jacob Lewallen <jl...@cs.ucr.edu> on 2003/02/09 22:28:13 UTC
[PATCH] apr_queue race condition
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
jlewalle@cs.ucr.edu
Re: [PATCH] apr_queue race condition
Posted by Ian Holsman <li...@holsman.net>.
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
> jlewalle@cs.ucr.edu
> Index: apr_queue.c
>
Re: [PATCH] apr_queue race condition
Posted by Ian Holsman <li...@holsman.net>.
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
>><jl...@cs.ucr.edu> 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
Posted by Aaron Bannert <aa...@clove.org>.
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
Posted by David Reid <dr...@jetnet.co.uk>.
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
> <jl...@cs.ucr.edu> 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
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
--On Monday, February 10, 2003 2:10 PM -0800 Jacob Lewallen
<jl...@cs.ucr.edu> 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
Posted by Jacob Lewallen <jl...@cs.ucr.edu>.
>
> 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
jlewalle@cs.ucr.edu
Re: [PATCH] apr_queue race condition
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
--On Sunday, February 9, 2003 1:28 PM -0800 Jacob Lewallen
<jl...@cs.ucr.edu> 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
Posted by Jacob Lewallen <jl...@cs.ucr.edu>.
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
jlewalle@cs.ucr.edu