[Click] Bug in QuickNoteQueue

[Ashish Sharma]

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
>>
>