Skip to content

Commit 59cc1f6

Browse files
Jiri Kosinadavem330
authored andcommitted
net: sched: convert qdisc linked list to hashtable
Convert the per-device linked list into a hashtable. The primary motivation for this change is that currently, we're not tracking all the qdiscs in hierarchy (e.g. excluding default qdiscs), as the lookup performed over the linked list by qdisc_match_from_root() is rather expensive. The ultimate goal is to get rid of hidden qdiscs completely, which will bring much more determinism in user experience. Reviewed-by: Cong Wang <xiyou.wangcong@gmail.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent e87a8f2 commit 59cc1f6

File tree

8 files changed

+30
-18
lines changed

8 files changed

+30
-18
lines changed

include/linux/netdevice.h

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@
5252
#include <uapi/linux/netdevice.h>
5353
#include <uapi/linux/if_bonding.h>
5454
#include <uapi/linux/pkt_cls.h>
55+
#include <linux/hashtable.h>
5556

5657
struct netpoll_info;
5758
struct device;
@@ -1800,6 +1801,9 @@ struct net_device {
18001801
unsigned int num_tx_queues;
18011802
unsigned int real_num_tx_queues;
18021803
struct Qdisc *qdisc;
1804+
#ifdef CONFIG_NET_SCHED
1805+
DECLARE_HASHTABLE (qdisc_hash, 4);
1806+
#endif
18031807
unsigned long tx_queue_len;
18041808
spinlock_t tx_global_lock;
18051809
int watchdog_timeo;

include/net/pkt_sched.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -90,8 +90,8 @@ int unregister_qdisc(struct Qdisc_ops *qops);
9090
void qdisc_get_default(char *id, size_t len);
9191
int qdisc_set_default(const char *id);
9292

93-
void qdisc_list_add(struct Qdisc *q);
94-
void qdisc_list_del(struct Qdisc *q);
93+
void qdisc_hash_add(struct Qdisc *q);
94+
void qdisc_hash_del(struct Qdisc *q);
9595
struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle);
9696
struct Qdisc *qdisc_lookup_class(struct net_device *dev, u32 handle);
9797
struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r,

include/net/sch_generic.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ struct Qdisc {
6161
u32 limit;
6262
const struct Qdisc_ops *ops;
6363
struct qdisc_size_table __rcu *stab;
64-
struct list_head list;
64+
struct hlist_node hash;
6565
u32 handle;
6666
u32 parent;
6767
void *u32_node;

net/core/dev.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7629,6 +7629,9 @@ struct net_device *alloc_netdev_mqs(int sizeof_priv, const char *name,
76297629
INIT_LIST_HEAD(&dev->all_adj_list.lower);
76307630
INIT_LIST_HEAD(&dev->ptype_all);
76317631
INIT_LIST_HEAD(&dev->ptype_specific);
7632+
#ifdef CONFIG_NET_SCHED
7633+
hash_init(dev->qdisc_hash);
7634+
#endif
76327635
dev->priv_flags = IFF_XMIT_DST_RELEASE | IFF_XMIT_DST_RELEASE_PERM;
76337636
setup(dev);
76347637

net/sched/sch_api.c

Lines changed: 13 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@
2929
#include <linux/hrtimer.h>
3030
#include <linux/lockdep.h>
3131
#include <linux/slab.h>
32+
#include <linux/hashtable.h>
3233

3334
#include <net/net_namespace.h>
3435
#include <net/sock.h>
@@ -263,33 +264,33 @@ static struct Qdisc *qdisc_match_from_root(struct Qdisc *root, u32 handle)
263264
root->handle == handle)
264265
return root;
265266

266-
list_for_each_entry_rcu(q, &root->list, list) {
267+
hash_for_each_possible_rcu(qdisc_dev(root)->qdisc_hash, q, hash, handle) {
267268
if (q->handle == handle)
268269
return q;
269270
}
270271
return NULL;
271272
}
272273

273-
void qdisc_list_add(struct Qdisc *q)
274+
void qdisc_hash_add(struct Qdisc *q)
274275
{
275276
if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
276277
struct Qdisc *root = qdisc_dev(q)->qdisc;
277278

278279
WARN_ON_ONCE(root == &noop_qdisc);
279280
ASSERT_RTNL();
280-
list_add_tail_rcu(&q->list, &root->list);
281+
hash_add_rcu(qdisc_dev(q)->qdisc_hash, &q->hash, q->handle);
281282
}
282283
}
283-
EXPORT_SYMBOL(qdisc_list_add);
284+
EXPORT_SYMBOL(qdisc_hash_add);
284285

285-
void qdisc_list_del(struct Qdisc *q)
286+
void qdisc_hash_del(struct Qdisc *q)
286287
{
287288
if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
288289
ASSERT_RTNL();
289-
list_del_rcu(&q->list);
290+
hash_del_rcu(&q->hash);
290291
}
291292
}
292-
EXPORT_SYMBOL(qdisc_list_del);
293+
EXPORT_SYMBOL(qdisc_hash_del);
293294

294295
struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
295296
{
@@ -998,7 +999,7 @@ qdisc_create(struct net_device *dev, struct netdev_queue *dev_queue,
998999
goto err_out4;
9991000
}
10001001

1001-
qdisc_list_add(sch);
1002+
qdisc_hash_add(sch);
10021003

10031004
return sch;
10041005
}
@@ -1435,6 +1436,7 @@ static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
14351436
{
14361437
int ret = 0, q_idx = *q_idx_p;
14371438
struct Qdisc *q;
1439+
int b;
14381440

14391441
if (!root)
14401442
return 0;
@@ -1449,7 +1451,7 @@ static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
14491451
goto done;
14501452
q_idx++;
14511453
}
1452-
list_for_each_entry(q, &root->list, list) {
1454+
hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
14531455
if (q_idx < s_q_idx) {
14541456
q_idx++;
14551457
continue;
@@ -1765,14 +1767,15 @@ static int tc_dump_tclass_root(struct Qdisc *root, struct sk_buff *skb,
17651767
int *t_p, int s_t)
17661768
{
17671769
struct Qdisc *q;
1770+
int b;
17681771

17691772
if (!root)
17701773
return 0;
17711774

17721775
if (tc_dump_tclass_qdisc(root, skb, tcm, cb, t_p, s_t) < 0)
17731776
return -1;
17741777

1775-
list_for_each_entry(q, &root->list, list) {
1778+
hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
17761779
if (tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
17771780
return -1;
17781781
}

net/sched/sch_generic.c

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -423,7 +423,6 @@ struct Qdisc noop_qdisc = {
423423
.dequeue = noop_dequeue,
424424
.flags = TCQ_F_BUILTIN,
425425
.ops = &noop_qdisc_ops,
426-
.list = LIST_HEAD_INIT(noop_qdisc.list),
427426
.q.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
428427
.dev_queue = &noop_netdev_queue,
429428
.running = SEQCNT_ZERO(noop_qdisc.running),
@@ -613,7 +612,6 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
613612
sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
614613
sch->padded = (char *) sch - (char *) p;
615614
}
616-
INIT_LIST_HEAD(&sch->list);
617615
skb_queue_head_init(&sch->q);
618616

619617
spin_lock_init(&sch->busylock);
@@ -700,7 +698,7 @@ void qdisc_destroy(struct Qdisc *qdisc)
700698
return;
701699

702700
#ifdef CONFIG_NET_SCHED
703-
qdisc_list_del(qdisc);
701+
qdisc_hash_del(qdisc);
704702

705703
qdisc_put_stab(rtnl_dereference(qdisc->stab));
706704
#endif
@@ -788,6 +786,10 @@ static void attach_default_qdiscs(struct net_device *dev)
788786
qdisc->ops->attach(qdisc);
789787
}
790788
}
789+
#ifdef CONFIG_NET_SCHED
790+
if (dev->qdisc)
791+
qdisc_hash_add(dev->qdisc);
792+
#endif
791793
}
792794

793795
static void transition_one_qdisc(struct net_device *dev,

net/sched/sch_mq.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -88,7 +88,7 @@ static void mq_attach(struct Qdisc *sch)
8888
qdisc_destroy(old);
8989
#ifdef CONFIG_NET_SCHED
9090
if (ntx < dev->real_num_tx_queues)
91-
qdisc_list_add(qdisc);
91+
qdisc_hash_add(qdisc);
9292
#endif
9393

9494
}

net/sched/sch_mqprio.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -182,7 +182,7 @@ static void mqprio_attach(struct Qdisc *sch)
182182
if (old)
183183
qdisc_destroy(old);
184184
if (ntx < dev->real_num_tx_queues)
185-
qdisc_list_add(qdisc);
185+
qdisc_hash_add(qdisc);
186186
}
187187
kfree(priv->qdiscs);
188188
priv->qdiscs = NULL;

0 commit comments

Comments
 (0)