Skip to content

Commit 8fb472c

Browse files
Nikolay Aleksandrovdavem330
Nikolay Aleksandrov
authored and
davem330
committed
ipmr: improve hash scalability
Recently we started using ipmr with thousands of entries and easily hit soft lockups on smaller devices. The reason is that the hash function uses the high order bits from the src and dst, but those don't change in many common cases, also the hash table is only 64 elements so with thousands it doesn't scale at all. This patch migrates the hash table to rhashtable, and in particular the rhl interface which allows for duplicate elements to be chained because of the MFC_PROXY support (*,G; *,*,oif cases) which allows for multiple duplicate entries to be added with different interfaces (IMO wrong, but it's been in for a long time). And here are some results from tests I've run in a VM: mr_table size (default, allocated for all namespaces): Before After 49304 bytes 2400 bytes Add 65000 routes (the diff is much larger on smaller devices): Before After 1m42s 58s Forwarding 256 byte packets with 65000 routes (test done in a VM): Before After 3 Mbps / ~1465 pps 122 Mbps / ~59000 pps As a bonus we no longer see the soft lockups on smaller devices which showed up even with 2000 entries before. Signed-off-by: Nikolay Aleksandrov <nikolay@cumulusnetworks.com> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent c1ce156 commit 8fb472c

File tree

2 files changed

+182
-130
lines changed

2 files changed

+182
-130
lines changed

‎include/linux/mroute.h

Lines changed: 42 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33

44
#include <linux/in.h>
55
#include <linux/pim.h>
6+
#include <linux/rhashtable.h>
67
#include <net/sock.h>
78
#include <uapi/linux/mroute.h>
89

@@ -60,7 +61,6 @@ struct vif_device {
6061
#define VIFF_STATIC 0x8000
6162

6263
#define VIF_EXISTS(_mrt, _idx) ((_mrt)->vif_table[_idx].dev != NULL)
63-
#define MFC_LINES 64
6464

6565
struct mr_table {
6666
struct list_head list;
@@ -69,8 +69,9 @@ struct mr_table {
6969
struct sock __rcu *mroute_sk;
7070
struct timer_list ipmr_expire_timer;
7171
struct list_head mfc_unres_queue;
72-
struct list_head mfc_cache_array[MFC_LINES];
7372
struct vif_device vif_table[MAXVIFS];
73+
struct rhltable mfc_hash;
74+
struct list_head mfc_cache_list;
7475
int maxvif;
7576
atomic_t cache_resolve_queue_len;
7677
bool mroute_do_assert;
@@ -85,17 +86,48 @@ enum {
8586
MFC_STATIC = BIT(0),
8687
};
8788

89+
struct mfc_cache_cmp_arg {
90+
__be32 mfc_mcastgrp;
91+
__be32 mfc_origin;
92+
};
93+
94+
/**
95+
* struct mfc_cache - multicast routing entries
96+
* @mnode: rhashtable list
97+
* @mfc_mcastgrp: destination multicast group address
98+
* @mfc_origin: source address
99+
* @cmparg: used for rhashtable comparisons
100+
* @mfc_parent: source interface (iif)
101+
* @mfc_flags: entry flags
102+
* @expires: unresolved entry expire time
103+
* @unresolved: unresolved cached skbs
104+
* @last_assert: time of last assert
105+
* @minvif: minimum VIF id
106+
* @maxvif: maximum VIF id
107+
* @bytes: bytes that have passed for this entry
108+
* @pkt: packets that have passed for this entry
109+
* @wrong_if: number of wrong source interface hits
110+
* @lastuse: time of last use of the group (traffic or update)
111+
* @ttls: OIF TTL threshold array
112+
* @list: global entry list
113+
* @rcu: used for entry destruction
114+
*/
88115
struct mfc_cache {
89-
struct list_head list;
90-
__be32 mfc_mcastgrp; /* Group the entry belongs to */
91-
__be32 mfc_origin; /* Source of packet */
92-
vifi_t mfc_parent; /* Source interface */
93-
int mfc_flags; /* Flags on line */
116+
struct rhlist_head mnode;
117+
union {
118+
struct {
119+
__be32 mfc_mcastgrp;
120+
__be32 mfc_origin;
121+
};
122+
struct mfc_cache_cmp_arg cmparg;
123+
};
124+
vifi_t mfc_parent;
125+
int mfc_flags;
94126

95127
union {
96128
struct {
97129
unsigned long expires;
98-
struct sk_buff_head unresolved; /* Unresolved buffers */
130+
struct sk_buff_head unresolved;
99131
} unres;
100132
struct {
101133
unsigned long last_assert;
@@ -105,18 +137,13 @@ struct mfc_cache {
105137
unsigned long pkt;
106138
unsigned long wrong_if;
107139
unsigned long lastuse;
108-
unsigned char ttls[MAXVIFS]; /* TTL thresholds */
140+
unsigned char ttls[MAXVIFS];
109141
} res;
110142
} mfc_un;
143+
struct list_head list;
111144
struct rcu_head rcu;
112145
};
113146

114-
#ifdef __BIG_ENDIAN
115-
#define MFC_HASH(a,b) (((((__force u32)(__be32)a)>>24)^(((__force u32)(__be32)b)>>26))&(MFC_LINES-1))
116-
#else
117-
#define MFC_HASH(a,b) ((((__force u32)(__be32)a)^(((__force u32)(__be32)b)>>2))&(MFC_LINES-1))
118-
#endif
119-
120147
struct rtmsg;
121148
int ipmr_get_route(struct net *net, struct sk_buff *skb,
122149
__be32 saddr, __be32 daddr,

0 commit comments

Comments
 (0)