[Click] Queues and notifications

[Eddie Kohler]

I did go ahead and fix this a different way, which will be a little less 
error prone for people programming elements like ToDevice.

Now in a situation like this:

       ... -> q::Queue -> d::DelayShaper(10s) -> x::ToDevice

the Queue will activate d's signal before waking x.  Thus:

       ... -> q::Queue -> d::DelayShaper(10s) -> x::ToDevice;
              INACTIVE         INACTIVE          UNSCHEDULED
                |  |             ^  ^                |   ^
                |  +--activates--+  +-----signal-----+   |
                |                                        |
                +--------------wakes up------------------+

Thus, when x wakes up, it sees that d's signal is active.

This will also have some benefits in situations like this:

   ... -> q::Queue -> d::DelayShaper(10s) -> rr::RoundRobinSched -> ...

Previously, rr would have had to poll d for 10 seconds per packet 
whenever there were packets in q.

Let me know if you see any problems.

Eddie



Eddie Kohler wrote:
> Hi guys,
> 
> Thanks for continuing to report this problem.  I did manage to reproduce 
> it and, hopefully, fix it.  But I wonder whether we could fix it in a 
> better way.
> 
> Mike, RawSocket did use notifiers.  This is all about notifiers.
> 
> Here's the deal.  Consider this configuration containing DelayShaper.
> 
>         ... -> q::Queue -> d::DelayShaper(10s) -> x::ToDevice;
> 
> Say that "q" has a packet in it.  Then q's notifier is active.  Should 
> "x" poll to get that packet?  NO!  Because it will poll for 10 solid 
> seconds before "d" will release the first packet!
> 
> Instead, Click introduces another notifier, in the DelayShaper d.  This 
> notifier turns on **only when d is ready to release a packet**.  In our 
> config above, then, x has d's notifier, not q's notifier.
> 
> Initially we have this status
> 
>         ... -> q::Queue -> d::DelayShaper(10s) -> x::ToDevice;
>                INACTIVE         INACTIVE          UNSCHEDULED
> 
> What happens when q gets a packet??  We want q to wake up x; since d is 
> a shaper, it should be passive, and x is the eventual packet consumer. 
> But x points at d's notifier!!  No problem; the 
> upstream_empty_notifier() process actually searches the graph TWICE, 
> once to develop a signal and once for registering wakeups.  That creates 
> this situation:
> 
>         ... -> q::Queue -> d::DelayShaper(10s) -> x::ToDevice;
>                INACTIVE         INACTIVE          UNSCHEDULED
>                    |               ^                  |   ^
>                    |               +-------signal-----+   |
>                    +-------------wakes up-----------------+
> 
> q will wake up x, which will then poll d.  Right?
> 
> Except that at the time x wakes up, **d's signal is still inactive.**
> 
> Most Click elements, including Discard, handled this case correctly. 
> When the task was rescheduled, they would pull upstream *before* 
> checking the signal.  But some Click elements did NOT handle this case 
> correctly.  They checked the signal *before* pulling upstream, which 
> meant (since d's signal is inactive here) that they never worked with 
> DelayShaper.  The elements: LinkUnqueue, RawSocket, Socket, and 
> userlevel ToDevice.
> 
> A related problem afflicted schedulers; a scheduler element, such as 
> RoundRobinSched, that had DelayUnqueues upstream would NEVER work 
> correctly since it looked at the wrong notifier.
> 
> I've fixed this in one way, namely by changing code like RawSocket to 
> pull before checking notifiers.  But now I think it would be better for 
> q to update d's signal when it wakes up x.  Not completely sure how to 
> implement this.... But Mike, Geoffrey, others using CVS, could you 
> update and see if you are still having scheduling problems?
> 
> Eddie
> 
> 
> 
> 
> 
> 
> 
> Mike Wilson wrote:
>> I've got a large, complex click config where I read from UDP sockets and 
>> write to a raw socket, routing packets from UDP tunnels.  Unfortunately, I 
>> can't seem to get notifications working in the Queues.
>>
>> I've stripped the config down to a fairly simple case that replicates the 
>> problem, at least on my system.  If I use Queue or NotifierQueue 
>> components for the queues, I either get nothing out the interface, or I 
>> get 1-2 packets and then nothing.  If I use a SimpleQueue, everything 
>> works just fine.
>>
>> My limited understanding is that the SimpleQueue doesn't do notifiers, so 
>> the pull components downstream must use polling.  In other words, it's a 
>> massive CPU hog - I get 99% utilization to click with a SimpleQueue.  With 
>> Queue, I don't even see click in my top(1) list.
>>
>> Am I mis-using the queue components somehow, or is this a bug?  Do 
>> RawSockets use notifiers?
>>
>> -Mike Wilson
>>
>> ---replication example---
>>
>> // Warning, this config will send bogus UDP packets to 172.16.46.20.
>> // Unfortunately, the problem doesn't manifest with a Discard at the end.
>>
>> AddressInfo(myip  128.252.160.209,
>>              NetRtr 172.16.46.12,
>>              HostRtr 172.16.46.20,
>>              NetRoute 172.16.46.0/24);
>>
>> PortInfo(NetTun 0xA121,
>>           HostTun 0xA122);
>>
>> out :: RawSocket("UDP");
>> rt :: RangeIPLookup(NetRoute  0, HostRtr 1);
>> sched :: DRRSched();
>>
>> TimedSource -> UDPIPEncap(HostRtr, 5005, HostRtr, 5005) -> 
>> IPPrint("Injecting Packet") -> check :: CheckIPHeader;
>> Idle -> rt;
>>
>> check[1] -> Print("Injected Bad packet") -> Discard;
>> check[0] -> IPPrint("Injected Valid Packet") -> GetIPAddress(16) -> rt;
>>
>> rt[0] -> UDPIPEncap(myip, NetTun, NetRtr, NetTun) -> IPPrint("Net Route") 
>> -> SimpleQueue -> [0]sched;
>> rt[1] -> UDPIPEncap(myip, HostTun, HostRtr, HostTun) -> IPPrint("Host 
>> Route") -> SimpleQueue -> [1]sched;
>>
>> sched -> IPPrint("Sending") -> out;
>>
>> _______________________________________________
>> 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