* Credits (in time order) for older HTB versions:
* Stef Coene <stef.coene@docum.org>
* HTB support at LARTC mailing list
- * Ondrej Kraus, <krauso@barr.cz>
+ * Ondrej Kraus, <krauso@barr.cz>
* found missing INIT_QDISC(htb)
* Vladimir Smelhaus, Aamer Akhter, Bert Hubert
* helped a lot to locate nasty class stall bug
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
-#include <linux/sched.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/skbuff.h>
#include <linux/list.h>
#include <linux/compiler.h>
+#include <net/netlink.h>
#include <net/sock.h>
#include <net/pkt_sched.h>
#include <linux/rbtree.h>
Author: devik@cdi.cz
========================================================================
HTB is like TBF with multiple classes. It is also similar to CBQ because
- it allows to assign priority to each class in hierarchy.
+ it allows to assign priority to each class in hierarchy.
In fact it is another implementation of Floyd's formal sharing.
Levels:
- Each class is assigned level. Leaf has ALWAYS level 0 and root
+ Each class is assigned level. Leaf has ALWAYS level 0 and root
classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
one less than their parent.
*/
} un;
struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
struct rb_node pq_node; /* node for event queue */
- unsigned long pq_key; /* the same type as jiffies global */
+ psched_time_t pq_key;
int prio_activity; /* for which prios are we active */
enum htb_cmode cmode; /* current mode of the class */
struct rb_root wait_pq[TC_HTB_MAXDEPTH];
/* time of nearest event per level (row) */
- unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
-
- /* cached value of jiffies in dequeue */
- unsigned long jiffies;
+ psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
/* whether we hit non-work conserving class during this dequeue; we use */
int nwc_hit; /* this to disable mindelay complaint in dequeue */
int rate2quantum; /* quant = rate / rate2quantum */
psched_time_t now; /* cached dequeue time */
- struct timer_list timer; /* send delay timer */
+ struct qdisc_watchdog watchdog;
#ifdef HTB_RATECM
struct timer_list rttim; /* rate computer timer */
int recmp_bucket; /* which hash bucket to recompute next */
* We allow direct class selection by classid in priority. The we examine
* filters in qdisc and in inner nodes (if higher filter points to the inner
* node). If we end up with classid MAJOR:0 we enqueue the skb into special
- * internal fifo (direct). These packets then go directly thru. If we still
+ * internal fifo (direct). These packets then go directly thru. If we still
* have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
* then finish and return direct queue.
*/
{
struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
- cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay);
- if (cl->pq_key == q->jiffies)
+ cl->pq_key = q->now + delay;
+ if (cl->pq_key == q->now)
cl->pq_key++;
/* update the nearest event cache */
- if (time_after(q->near_ev_cache[cl->level], cl->pq_key))
+ if (q->near_ev_cache[cl->level] > cl->pq_key)
q->near_ev_cache[cl->level] = cl->pq_key;
while (*p) {
struct htb_class *c;
parent = *p;
c = rb_entry(parent, struct htb_class, pq_node);
- if (time_after_eq(cl->pq_key, c->pq_key))
+ if (cl->pq_key >= c->pq_key)
p = &parent->rb_right;
else
p = &parent->rb_left;
* htb_activate_prios - creates active classe's feed chain
*
* The class is connected to ancestors and/or appropriate rows
- * for priorities it is participating on. cl->cmode must be new
+ * for priorities it is participating on. cl->cmode must be new
* (activated) mode. It does nothing if cl->prio_activity == 0.
*/
static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
/**
* htb_deactivate_prios - remove class from feed chain
*
- * cl->cmode must represent old mode (before deactivation). It does
+ * cl->cmode must represent old mode (before deactivation). It does
* nothing if cl->prio_activity == 0. Class is removed from all feed
* chains and rows.
*/
*
* It computes cl's mode at time cl->t_c+diff and returns it. If mode
* is not HTB_CAN_SEND then cl->pq_key is updated to time difference
- * from now to time when cl will change its state.
+ * from now to time when cl will change its state.
* Also it is worth to note that class mode doesn't change simply
- * at cl->{c,}tokens == 0 but there can rather be hysteresis of
+ * at cl->{c,}tokens == 0 but there can rather be hysteresis of
* 0 .. -cl->{c,}buffer range. It is meant to limit number of
* mode transitions per time unit. The speed gain is about 1/6.
*/
}
/**
- * htb_activate - inserts leaf cl into appropriate active feeds
+ * htb_activate - inserts leaf cl into appropriate active feeds
*
* Routine learns (new) priority of leaf and activates feed chain
* for the prio. It can be called on already active leaf safely.
}
/**
- * htb_deactivate - remove leaf cl from active feeds
+ * htb_deactivate - remove leaf cl from active feeds
*
* Make sure that leaf is active. In the other words it can't be called
* with non-active leaf. It also removes class from the drop list.
return NET_XMIT_SUCCESS;
}
-static void htb_timer(unsigned long arg)
-{
- struct Qdisc *sch = (struct Qdisc *)arg;
- sch->flags &= ~TCQ_F_THROTTLED;
- wmb();
- netif_schedule(sch->dev);
-}
-
#ifdef HTB_RATECM
#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
static void htb_rate_timer(unsigned long arg)
cl->T = toks
while (cl) {
- diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
+ diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
if (cl->level >= level) {
if (cl->level == level)
cl->xstats.lends++;
/**
* htb_do_events - make mode changes to classes at the level
*
- * Scans event queue for pending events and applies them. Returns jiffies to
+ * Scans event queue for pending events and applies them. Returns time of
* next pending event (0 for no event in pq).
- * Note: Aplied are events whose have cl->pq_key <= jiffies.
+ * Note: Applied are events whose have cl->pq_key <= q->now.
*/
-static long htb_do_events(struct htb_sched *q, int level)
+static psched_time_t htb_do_events(struct htb_sched *q, int level)
{
int i;
return 0;
cl = rb_entry(p, struct htb_class, pq_node);
- if (time_after(cl->pq_key, q->jiffies)) {
- return cl->pq_key - q->jiffies;
- }
+ if (cl->pq_key > q->now)
+ return cl->pq_key;
+
htb_safe_rb_erase(p, q->wait_pq + level);
- diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
+ diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
htb_change_class_mode(q, cl, &diff);
if (cl->cmode != HTB_CAN_SEND)
htb_add_to_wait_tree(q, cl, diff);
}
if (net_ratelimit())
printk(KERN_WARNING "htb: too many events !\n");
- return HZ / 10;
+ return q->now + PSCHED_TICKS_PER_SEC / 10;
}
/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
for (i = 0; i < 65535; i++) {
if (!*sp->pptr && *sp->pid) {
- /* ptr was invalidated but id is valid - try to recover
+ /* ptr was invalidated but id is valid - try to recover
the original or next ptr */
*sp->pptr =
htb_id_find_next_upper(prio, sp->root, *sp->pid);
/* class can be empty - it is unlikely but can be true if leaf
qdisc drops packets in enqueue routine or if someone used
- graft operation on the leaf since last dequeue;
+ graft operation on the leaf since last dequeue;
simply deactivate and skip such class */
if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
struct htb_class *next;
return skb;
}
-static void htb_delay_by(struct Qdisc *sch, long delay)
-{
- struct htb_sched *q = qdisc_priv(sch);
- if (delay <= 0)
- delay = 1;
- if (unlikely(delay > 5 * HZ)) {
- if (net_ratelimit())
- printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
- delay = 5 * HZ;
- }
- /* why don't use jiffies here ? because expires can be in past */
- mod_timer(&q->timer, q->jiffies + delay);
- sch->flags |= TCQ_F_THROTTLED;
- sch->qstats.overlimits++;
-}
-
static struct sk_buff *htb_dequeue(struct Qdisc *sch)
{
struct sk_buff *skb = NULL;
struct htb_sched *q = qdisc_priv(sch);
int level;
- long min_delay;
-
- q->jiffies = jiffies;
+ psched_time_t next_event;
/* try to dequeue direct packets as high prio (!) to minimize cpu work */
skb = __skb_dequeue(&q->direct_queue);
if (!sch->q.qlen)
goto fin;
- PSCHED_GET_TIME(q->now);
+ q->now = psched_get_time();
- min_delay = LONG_MAX;
+ next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
q->nwc_hit = 0;
for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
/* common case optimization - skip event handler quickly */
int m;
- long delay;
- if (time_after_eq(q->jiffies, q->near_ev_cache[level])) {
- delay = htb_do_events(q, level);
- q->near_ev_cache[level] =
- q->jiffies + (delay ? delay : HZ);
+ psched_time_t event;
+
+ if (q->now >= q->near_ev_cache[level]) {
+ event = htb_do_events(q, level);
+ q->near_ev_cache[level] = event ? event :
+ PSCHED_TICKS_PER_SEC;
} else
- delay = q->near_ev_cache[level] - q->jiffies;
+ event = q->near_ev_cache[level];
+
+ if (event && next_event > event)
+ next_event = event;
- if (delay && min_delay > delay)
- min_delay = delay;
m = ~q->row_mask[level];
while (m != (int)(-1)) {
int prio = ffz(m);
}
}
}
- htb_delay_by(sch, min_delay > 5 * HZ ? 5 * HZ : min_delay);
+ sch->qstats.overlimits++;
+ qdisc_watchdog_schedule(&q->watchdog, next_event);
fin:
return skb;
}
}
}
- sch->flags &= ~TCQ_F_THROTTLED;
- del_timer(&q->timer);
+ qdisc_watchdog_cancel(&q->watchdog);
__skb_queue_purge(&q->direct_queue);
sch->q.qlen = 0;
memset(q->row, 0, sizeof(q->row));
for (i = 0; i < TC_HTB_NUMPRIO; i++)
INIT_LIST_HEAD(q->drops + i);
- init_timer(&q->timer);
+ qdisc_watchdog_init(&q->watchdog, sch);
skb_queue_head_init(&q->direct_queue);
q->direct_qlen = sch->dev->tx_queue_len;
if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
q->direct_qlen = 2;
- q->timer.function = htb_timer;
- q->timer.data = (unsigned long)sch;
#ifdef HTB_RATECM
init_timer(&q->rttim);
static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
{
struct htb_sched *q = qdisc_priv(sch);
- unsigned char *b = skb->tail;
+ unsigned char *b = skb_tail_pointer(skb);
struct rtattr *rta;
struct tc_htb_glob gopt;
spin_lock_bh(&sch->dev->queue_lock);
rta = (struct rtattr *)b;
RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
- rta->rta_len = skb->tail - b;
+ rta->rta_len = skb_tail_pointer(skb) - b;
spin_unlock_bh(&sch->dev->queue_lock);
return skb->len;
rtattr_failure:
spin_unlock_bh(&sch->dev->queue_lock);
- skb_trim(skb, skb->tail - skb->data);
+ nlmsg_trim(skb, skb_tail_pointer(skb));
return -1;
}
struct sk_buff *skb, struct tcmsg *tcm)
{
struct htb_class *cl = (struct htb_class *)arg;
- unsigned char *b = skb->tail;
+ unsigned char *b = skb_tail_pointer(skb);
struct rtattr *rta;
struct tc_htb_opt opt;
opt.prio = cl->un.leaf.prio;
opt.level = cl->level;
RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
- rta->rta_len = skb->tail - b;
+ rta->rta_len = skb_tail_pointer(skb) - b;
spin_unlock_bh(&sch->dev->queue_lock);
return skb->len;
rtattr_failure:
spin_unlock_bh(&sch->dev->queue_lock);
- skb_trim(skb, b - skb->data);
+ nlmsg_trim(skb, b);
return -1;
}
if (cl && !cl->level) {
if (new == NULL &&
(new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
- cl->classid))
+ cl->classid))
== NULL)
return -ENOBUFS;
sch_tree_lock(sch);
parent->un.leaf.prio = parent->prio;
parent->tokens = parent->buffer;
parent->ctokens = parent->cbuffer;
- PSCHED_GET_TIME(parent->t_c);
+ parent->t_c = psched_get_time();
parent->cmode = HTB_CAN_SEND;
}
{
struct htb_sched *q = qdisc_priv(sch);
- del_timer_sync(&q->timer);
+ qdisc_watchdog_cancel(&q->watchdog);
#ifdef HTB_RATECM
del_timer_sync(&q->rttim);
#endif
/* This line used to be after htb_destroy_class call below
- and surprisingly it worked in 2.4. But it must precede it
+ and surprisingly it worked in 2.4. But it must precede it
because filter need its target class alive to be able to call
unbind_filter on it (without Oops). */
htb_destroy_filters(&q->filter_list);
sch_tree_lock(sch);
- /* delete from hash and active; remainder in destroy_class */
- hlist_del_init(&cl->hlist);
-
if (!cl->level) {
qlen = cl->un.leaf.q->q.qlen;
qdisc_reset(cl->un.leaf.q);
qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
}
+ /* delete from hash and active; remainder in destroy_class */
+ hlist_del_init(&cl->hlist);
+
if (cl->prio_activity)
htb_deactivate(q, cl);
/* set class to be in HTB_CAN_SEND state */
cl->tokens = hopt->buffer;
cl->ctokens = hopt->cbuffer;
- cl->mbuffer = PSCHED_JIFFIE2US(HZ * 60); /* 1min */
- PSCHED_GET_TIME(cl->t_c);
+ cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
+ cl->t_c = psched_get_time();
cl->cmode = HTB_CAN_SEND;
/* attach to the hash list and parent's family */
projects / powerpc.git / blobdiff