sched: Optimize return value of qdisc_restart

Optimize return value of qdisc_restart so that it is not called an extra time if there are no more packets on the queue to be sent out. It is also not required to check for gso_skb (though the lock is dropped) since another cpu which added this would have done a netif_schedule.

Patch against net-2.6.22.git

Signed-off-by Krishna Kumar <[email protected]>

From: Krishna Kumar <[email protected]>
Date: Tue, 08 May 2007 13:01:32 +0530

Quoted 9 lines

Optimize return value of qdisc_restart so that it is not called an extra time if there are no more packets on the queue to be sent out. It is also not required to check for gso_skb (though the lock is dropped) since another cpu which added this would have done a netif_schedule.

Patch against net-2.6.22.git

Signed-off-by Krishna Kumar <[email protected]>

<0 return value here means that the queue is not empty, and the device is throttled. If you want to do this, just branch down to the end of the function which asserts that q->q.qlen is not negative, and returns it.

That will achieve the right effect.

But I'm not so sure about this idea, I have this strange feeling that we do things this way for a reason... Hmmm...

This change will not change existing behavior in case there are packets in the queue, it will return -1 each time as does the original code. But when there are no packets, the original qdisc_restart returns -1 and the caller will unnecessarily call qdisc_restart which branches to the bottom and returns 0 (qlen). This call can be avoided if we had returned 0 in the previous iteration. Branching to the bottom cannot be done since it breaks the "packets present" case, as it will return a positive number and the caller will assume that the queue is throttled.

But this only makes sense for the second hunk you changed.

The first hunk is a bug case, an improper looping device decapsulation condition, and we do want to always return -1 in that case in order to break out of the loop.

Your change will make the kernel essentially hang instead when this bug check is triggered.

David Miller <[email protected]> wrote on 05/09/2007 12:06:30 PM:

Quoted 2 lines

Your change will make the kernel essentially hang instead when this bug check is triggered.

By returning -1, we end up freeing all the skbs one by one, or until the condition : "transient error caused by hard_start_xmit recursing" is over. Essentially, that behavior is also not changed in my patch (only run time change is to return 0 if there are no more skbs).

Something this evening is obviously making it impossible for my brain to understand this function and your patch, so I'm going to sleep on it and try again tomorrow :-)

Quoted 4 lines

Something this evening is obviously making it impossible for my brain to understand this function and your patch, so I'm going to sleep on it and try again tomorrow :-)

It is one of those areas that are hard to size-up in a blink;->
Gut-feeling: It doesnt sit right with me as well.

With (2.6.18-rxX++) QDISC_RUNNING changes that mean only one of N CPUs will be dequeueing while the N-1 maybe enqueueing concurently. All N

CPUs contend for the queue lock; and theres a possible window between releasing the queue lock by the dequeuer-CPU and enqueuer-CPU for a race. The dequeuer-CPU entering one last time helps.

Krishna, you probably saw this "wasted entry into qdisc" under low traffic conditions with more than likely only one CPU sending, am i correct? Under heavier traffic when we have multiple CPUs funneling to

the same device, that entry is not really a "waste" because we endup only go in once per X number of packets enqueued on the qdisc and that check is absolutely necessary because a different CPU may have enqueued while you were not looking. In the case of low traffic, X=1 - so it is a waste there albeit a necessary one.

cheers,
jamal

Concurrently is not possible, since everyone needs the queue_lock to add/delete. Did I misunderstand your comment ?

The dev->queue_lock is held by both enqueue'r and dequeue'r (though the dequeue'r drops it before calling xmit). But once the dequeue'r re-gets the lock, it is guaranteed that no one else has the lock Other CPU's trying to add will block on the lock, or if they have already added by getting the lock for a short time while my CPU was

doing the xmit, then their qdisc_run returns doing nothing as RUNNING is true.

Since I am holding a lock in these two changed areas till I return back to __qdisc_run (which clears the RUNNING bit) and then drop the lock, there is no way packets can be on the queue while I falsely return 0, or no packets on the queue while I falsely return -1.

I hope my explanation was not confusing.

Quoted 4 lines

Since I am holding a lock in these two changed areas till I return back to __qdisc_run (which clears the RUNNING bit) and then drop the lock, there is no way packets can be on the queue while I falsely return 0, or no packets on the queue while I falsely return -1.

If you relinquish yourself from being a dequeuer by letting go of RUNNING then it is possible during that short window one of the other N-1 CPUs could have been enqueueing; that packet will never be dequeued unless a new packet shows up some X amount of time later.

I hope what i described above helps. Off for about a day. CCing Herbert who last made changes to that area incase i missed something ..

cheers,
jamal

PS:- Please dont use my temporary gmail account to respond; a reply-to will pick the right address (@cyberus.ca).

But RUNNING is never relinquished till all the way back out to __qdisc_run. Only the lock is dropped before calling xmit and re-got after xmit is finished (all the while holding RUNNING). After xmit both queue_lock and RUNNING are held. If some other cpu enqueue'd during this release window (and they would have returned after dropping the lock as they are pure enqueuer's), qdisc_restart will find those skbs. Similarly if no skbs were added, qdisc_restart will return 0.

Quoted 9 lines

But RUNNING is never relinquished till all the way back out to __qdisc_run. Only the lock is dropped before calling xmit and re-got after xmit is finished (all the while holding RUNNING). After xmit both queue_lock and RUNNING are held. If some other cpu enqueue'd during this release window (and they would have returned after dropping the lock as they are pure enqueuer's), qdisc_restart will find those skbs. Similarly if no skbs were added, qdisc_restart will return 0.

Yes I agree with Krishna completely. In fact this whole section is so 20th-century :) Let's fix up the comments too while we're at it.

[NET_SCHED]: Rationalise return value of qdisc_restart

The current return value scheme and associated comment was invented back in the 20th century when we still had that tbusy flag. Things have changed quite a bit since then (even Tony Blair is moving on now, not to mention the new French president).

All we need to indicate now is whether the caller should continue processing the queue. Therefore it's sufficient if we return 0 if we want to stop and non-zero otherwise.

This is based on a patch by Krishna Kumar.

Signed-off-by <[email protected]>

Quoted 2 lines

[NET_SCHED]: Rationalise return value of qdisc_restart

Fair enough, patch applied :-)

Quoted 4 lines

Quoted 2 lines

[NET_SCHED]: Rationalise return value of qdisc_restart

Fair enough, patch applied :-)

Sorry, reading Thomas's patch made me realise that I've just added that bug all over again.

[NET_SCHED]: Reread dev->qdisc for NETDEV_TX_OK

Now that we return the queue length after NETDEV_TX_OK we better make sure that we have the right queue. Otherwise we can cause a stall after a really quick dev_deactive/dev_activate.

Signed-off-by Herbert Xu <[email protected]>

From: Herbert Xu <[email protected]>
Date: Thu, 10 May 2007 21:50:39 +1000

T_SCHED]: Rationalise return value of qdisc_restart

Quoted 10 lines

The current return value scheme and associated comment was invented back in the 20th century when we still had that tbusy flag. Things have changed quite a bit since then (even Tony Blair is moving on now, not to mention the new French president).

All we need to indicate now is whether the caller should continue processing the queue. Therefore it's sufficient if we return 0 if we want to stop and non-zero otherwise.

Quoted 3 lines

This is based on a patch by Krishna Kumar.

Signed-off-by <[email protected]>

Fair enough, patch applied :-)

Quoted 15 lines · David Miller

From: Herbert Xu <[email protected]>
Date: Thu, 10 May 2007 21:50:39 +1000

T_SCHED]: Rationalise return value of qdisc_restart

Quoted 10 lines

The current return value scheme and associated comment was invented back in the 20th century when we still had that tbusy flag. Things have changed quite a bit since then (even Tony Blair is moving on now, not to mention the new French president).

All we need to indicate now is whether the caller should continue processing the queue. Therefore it's sufficient if we return 0 if we want to stop and non-zero otherwise.

Quoted 5 lines

Quoted 3 lines

This is based on a patch by Krishna Kumar.

Signed-off-by <[email protected]>

Fair enough, patch applied :-)

Ok, see if this makes sense:

CPU0 CPU1 (holding qdisc running)

  .                    |
  .                    |
  .                    + grab qlock
  .                    |
  .                    | deq pkt
  .                    + release qlock
  .                    + grab txlock
  .                    |  send pkt
  .                    + release txlock
  .                    + grab qlock
   has pktX            | (NEW: qlen = 0); return 0 instead of -1
   waiting for qlock   + release qlock
  + grab qlock         |
  |                    + find that return code is 0
  | enq pkt X          + release qdisc running
  |                    |
  + release qlock      | ==> outta here

pkt X is stuck unless some event happens such as a new pkt arrival. In other words it sits there for an indeterminate period.

cheers,
jamal

Ok, see if this makes sense:

CPU0 CPU1 (holding qdisc running)

 .                    |
 .                    |
 .                    + grab qlock
 .                    |
 .                    | deq pkt
 .                    + release qlock
 .                    + grab txlock
 .                    |  send pkt
 .                    + release txlock
 .                    + grab qlock
  has pktX            | (NEW: qlen = 0); return 0 instead of -1
  waiting for qlock   + release qlock

 + grab qlock         |
 |                    + find that return code is 0
 | enq pkt X          + release qdisc running
 |                    |
 + release qlock      | ==> outta here

pkt X is stuck unless some event happens such as a new pkt arrival. In other words it sits there for an indeterminate period.

jamal <[email protected]> wrote:

This release qlock isn't in our source code :)

I wonder how much performance improvement this give now that the extra incursion into qdisc_restart is avoided.

Quoted 3 lines · jamal

I wonder how much performance improvement this give now that the extra incursion into qdisc_restart is avoided.

Probably very little since the only way it can make a difference is if there is lots of contention. But if there is lots of contention we should stay in the function anyway.

Quoted 3 lines · jamal

Quoted 2 lines

I wonder how much performance improvement this give now that the

Quoted 5 lines

Quoted 1 line

incursion into qdisc_restart is avoided.

Probably very little since the only way it can make a difference is if there is lots of contention. But if there is lots of contention we should stay in the function anyway.

Less to do with CPU contention and more with Krishna's change which avoids entering that region all together which is useful even in the absence of contention. In the past (based on some measurement i did) upto 50% of the executions of qdisc restart were on an empty queue depending on traffic rates.

BTW, given that i couldnt recall the layout of the locks on qdisc restart; I think i will come back with the old patch i had to clean up the readability of qdisc restart so it is easy to tell just by quick inspection.

Since Canada seems to be comfortably taking revenge on the Swiss (my condolonces to Thomas and Ratz) - i think it is time for me to head out ;-> ttl.

cheers,
jamal

Herbert,

(quoted diff) +4 -2

-            while (qdisc_restart(dev) < 0 && !netif_queue_stopped(dev))
-                        /* NOTHING */;
+            do {
+                        if (!qdisc_restart(dev))
+                                    break;
+            } while (!netif_queue_stopped(dev));

This could be changed to old format, if required :