next up previous
Next: Requeue Up: Queuing Disciplines Previous: Enqueue

Dequeue

The dequeue function dequeues a packet for sending. It returns the next packet that needs to be sent out on the output interface. This packet is determined by the scheduler in the queuing discipline. The scheduler can be very complicated for complex queuing disciplines like the CBQ. At the same time, it can be very simple too, as in the case of a FIFO queue. The dequeue function for a simple FIFO queuing discipline (in net/sched/sch_fifo.c) is shown below:

static struct sk_buff *
pfifo_dequeue(struct Qdisc* sch)
{
    return __skb_dequeue(&sch->q);
}

As shown in this example, the next packet in the queue is dequeued and returned, which is desired behavior from a simple FIFO.

The dequeue function for a priority FIFO is shown next.

static struct sk_buff *
prio_dequeue(struct Qdisc* sch)
{
 .
 .
 .
 for (prio = 0; prio < q->bands;prio++) {
 qdisc = q->queues[prio];
 skb = qdisc->dequeue(qdisc);
 if (skb) {
  sch->q.qlen--;
  return skb;
   }
 }
 .
 .
 .
}

As shown in this example, whenever the prio_dequeue function is called, packets from the highest priority queue are sent first. After all the packets in the highest priority level are sent, packets from the next priority level are dequeued. This required behavior is provided by the portion of the code given above.

Having discussed the dequeue function of the queuing disciplines, let us now see the places where the dequeue function is invoked. Whenever a packet is enqueued in dev_queue_xmit, the qdisc_wakeup function (in include/net/pkt_sched.h) is invoked in an attempt to send the packet that was just enqueued. qdisc_wakeup invokes the qdisc_restart function (in net/sched/sch_generic.c), which invokes the dequeue function of the queuing discipline attached to the device. The dequeue function returns the next packet that needs to be sent out on the interface. qdisc_restart then invokes hard_start_xmit of the device to send the packet down to the device. If hard_start_xmit fails for some reason, the packet is requeued in the queuing discipline. The requeue function is discussed in a later section.

qdisc_wakeup can also be invoked from the watchdog timer handlers in the CBQ, TBF and CSZ schedulers. In the dequeue function of these queuing disciplines, when a packet is dequeued to be sent on the output interface, a watchdog timer is initiated. If for some reason, qdisc_restart does not send the packet out in time, the watchdog timer will go off and qdisc_restart is called. For example, the setting of the TBF watchdog timer in tbf_dequeue (in net/sched/sch_tbf.c) is shown below:

static struct sk_buff *
tbf_dequeue(struct Qdisc* sch)
{
.
.
.

if (!sch->dev->tbusy) {
.
.
    del_timer(&q->wd_timer);
    q->wd_timer.expires = jiffies + delay;
    add_timer(&q->wd_timer);
}
.
.
.

This example shows the way the watchdog timer is set. Yet another way of calling the dequeue function on a device is via qdisc_run_queues (in net/sched/sch_generic.c) from net_bh (in net/core/dev.c). net_bh is the bottom half handler of the networking stack in linux and is executed whenever packets are queued up for processing. In qdisc_run_queues, qdisc_restart is invoked and the rest of the actions are similar to those explained already.

Having discussed the dequeue function of a queuing discipline, let us now discuss the requeue function.


next up previous
Next: Requeue Up: Queuing Disciplines Previous: Enqueue
Saravanan Radhakrishnan
1999-09-30