[Click] Bug in QuickNoteQueue

[Eddie Kohler]

Hi Ashish,

Thanks for these patches.  I've checked in a somewhat different version -- let 
me know if it works for you.

Eddie


Ashish Sharma wrote:
> Hi Eddie,
> 
> Here is a revised patch that should be thread safe.
> Thanks Cliff for pointing this out.
> 
> diff --git a/elements/standard/quicknotequeue.cc
> b/elements/standard/quicknotequeue.cc
> index 88d8b3a..c590925 100644
> --- a/elements/standard/quicknotequeue.cc
> +++ b/elements/standard/quicknotequeue.cc
> @@ -46,7 +46,17 @@ QuickNoteQueue::pull(int)
>      if (h != t)
>         return pull_success(h, t, nh);
>      else
> +    {
> +       _empty_note.sleep();
> +#if HAVE_MULTITHREAD
> +       // Work around race condition between push() and pull().
> +       // We might have just undone push()'s Notifier::wake() call.
> +       // Easiest lock-free solution: check whether we should wake again!
> +       if (size())
> +           _empty_note.wake();
> +#endif
>         return 0;
> +    }
>  }
> 
>  CLICK_ENDDECLS
> 
> 
> 
> Thanks.
> 
> Ashish
> 
> On Sun, Jun 28, 2009 at 8:01 PM, Ashish Sharma<ashishs.sharma at gmail.com> wrote:
>> Hi Eddie,
>>
>> Thanks for your effort in checking in this new element. I got a chance
>> to test it out only now. There is however one bug in this, the
>> empty_note.sleep is only called when the queue becomes empty, but if
>> the queue is empty to begin with, this goes into a constant polling
>> mode, calling pull in a loop. Here is a possible patch that fixes it.
>> Please consider applying the following patch. Also the suggestion of
>> making the SLEEPINESS_TRIGGER value configurable seems like a good
>> idea. I can write a patch if you think it should be done.
>>
>> diff --git a/elements/standard/quicknotequeue.cc
>> b/elements/standard/quicknotequeue.cc
>> index 88d8b3a..4350346 100644
>> --- a/elements/standard/quicknotequeue.cc
>> +++ b/elements/standard/quicknotequeue.cc
>> @@ -46,7 +46,10 @@ QuickNoteQueue::pull(int)
>>     if (h != t)
>>        return pull_success(h, t, nh);
>>     else
>> +    {
>> +       _empty_note.sleep();
>>        return 0;
>> +    }
>>  }
>>
>>  CLICK_ENDDECLS
>>
>>
>> Thanks
>> Ashish
>>
>>
>> SUB: Notifier::upstream_empty_signal is always active
>>
>> On Sun, Jun 14, 2009 at 9:47 AM, Eddie Kohler<kohler at cs.ucla.edu> wrote:
>>>>  If you want not even one failed pull(), that will take some
>>>> reorganization of the code to clear the notifier in a different place (this
>>>> would be easy to do).
>>>
>>> You may be interested in QuickNoteQueue, just checked in.
>>>
>>> Eddie
>>>
>>>
>>>
>>>>> Since the valid/invalid test is an expensive
>>>>> one, what I would like is for the Notifier signal to act like a test
>>>>> function, so I only perform the valid/invalid operation if a queue is
>>>>> non-empty. Further, in case the queue is not empty but belongs to the set
>>>>> of
>>>>> "invalid" queues, I do not want to put the packet back at the head of the
>>>>> queue (of which I cannot think of a simple way of doing from within the
>>>>> scheduler element).
>>>> More generally, it seems like you should make your valid/invalid check
>>>> cheaper.  There are many possible ways to do this, including caching old
>>>> values of the check and only updating the cache when necessary.
>>>>
>>>> Eddie
>>>>
>>>>
>>>>> One solution is that I extend the Queue element to include a test
>>>>> function
>>>>> and along with the signal check the test function.
>>>>>
>>>>> Is there a clean way to make the Notifier signal active only when the
>>>>> input
>>>>> queue is really non-empty and not a false alarm?
>>>>>
>>>>> Thank you for your time. I would really appreciate any suggestions or
>>>>> thoughts.
>>>>>
>>>>> Thanks
>>>>> Ashish
>>>>> _______________________________________________
>>>>> click mailing list
>>>>> click at amsterdam.lcs.mit.edu
>>>>> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
>>>> _______________________________________________
>>>> click mailing list
>>>> click at amsterdam.lcs.mit.edu
>>>> https://amsterdam.lcs.mit.edu/mailman/listinfo/click