Re: [PATCH v5] net: sched: convert qdisc linked list to hashtable

[kbuild test robot]

Hi,

[auto build test ERROR on v4.7-rc7]
[also build test ERROR on next-20160729]
[cannot apply to net/master net-next/master ipsec-next/master]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Jiri-Kosina/net-sched-convert-qdisc-linked-list-to-hashtable/20160729-155412
config: arm-allmodconfig (attached as .config)
compiler: arm-linux-gnueabi-gcc (Debian 5.4.0-6) 5.4.0 20160609
reproduce:
wget 
https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross
 -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=arm 

All errors (new ones prefixed by >>):

>> drivers/net/ethernet/ti/davinci_emac.c:736:57: error: macro "hash_add" 
>> requires 3 arguments, but only 2 given
static int hash_add(struct emac_priv *priv, u8 *mac_addr)
^
>> drivers/net/ethernet/ti/davinci_emac.c:737:1: error: expected '=', ',', ';', 
>> 'asm' or '__attribute__' before '{' token
{
^
>> drivers/net/ethernet/ti/davinci_emac.c:778:12: error: conflicting types for 
>> 'hash_del'
static int hash_del(struct emac_priv *priv, u8 *mac_addr)
   ^
   In file included from include/linux/netdevice.h:55:0,
from drivers/net/ethernet/ti/davinci_emac.c:44:
   include/linux/hashtable.h:104:20: note: previous definition of 'hash_del' 
was here
static inline void hash_del(struct hlist_node *node)
   ^
   drivers/net/ethernet/ti/davinci_emac.c: In function 'emac_add_mcast':
   drivers/net/ethernet/ti/davinci_emac.c:828:35: error: macro "hash_add" 
requires 3 arguments, but only 2 given
  update = hash_add(priv, mac_addr);
  ^
>> drivers/net/ethernet/ti/davinci_emac.c:828:12: error: 'hash_add' undeclared 
>> (first use in this function)
  update = hash_add(priv, mac_addr);
   ^
   drivers/net/ethernet/ti/davinci_emac.c:828:12: note: each undeclared 
identifier is reported only once for each function it appears in

vim +/hash_add +736 drivers/net/ethernet/ti/davinci_emac.c

a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  730   
* @priv: The DaVinci EMAC private adapter structure
49ce9c2c drivers/net/ethernet/ti/davinci_emac.c Ben Hutchings 2012-07-10  731   
* @mac_addr: mac address to delete from hash table
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  732   
*
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  733   
* Adds mac address to the internal hash table
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  734   
*
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  735   
*/
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18 @736  
static int hash_add(struct emac_priv *priv, u8 *mac_addr)
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18 @737  {
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  738   
struct device *emac_dev = >ndev->dev;
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  739   
u32 rc = 0;
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  740   
u32 hash_bit;
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  741   
u32 hash_value = hash_get(mac_addr);
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  742  
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  743   
if (hash_value >= EMAC_NUM_MULTICAST_BITS) {
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  744   
if (netif_msg_drv(priv)) {
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  745   
dev_err(emac_dev, "DaVinci EMAC: hash_add(): Invalid "\
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  746   
"Hash %08x, should not be greater than %08x",
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  747   
hash_value, (EMAC_NUM_MULTICAST_BITS - 1));
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  748   
}
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  749   
return -1;
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  750   
}
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  751  
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  752   
/* set the hash bit only if not previously set */
a6286ee6 drivers/net/davinci_emac.c Anant Gole2009-05-18  753   
if (priv->multicast_hash_cnt[hash_value] == 0) {
a6286ee6 drivers/net/davinci_emac.c Anant Gole

Re: [PATCH v5] net: sched: convert qdisc linked list to hashtable

[kbuild test robot]

Hi,

[auto build test WARNING on v4.7-rc7]
[cannot apply to net/master net-next/master ipsec-next/master]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Jiri-Kosina/net-sched-convert-qdisc-linked-list-to-hashtable/20160729-155412
config: x86_64-randconfig-s1-07292101 (attached as .config)
compiler: gcc-4.4 (Debian 4.4.7-8) 4.4.7
reproduce:
# save the attached .config to linux build tree
make ARCH=x86_64 

All warnings (new ones prefixed by >>):

   In file included from drivers/net/ethernet/dec/tulip/de4x5.c:480:
   drivers/net/ethernet/dec/tulip/de4x5.h:864:1: warning: "HASH_BITS" redefined
   In file included from include/linux/netdevice.h:55,
from drivers/net/ethernet/dec/tulip/de4x5.c:459:
>> include/linux/hashtable.h:27:1: warning: this is the location of the 
>> previous definition
   drivers/net/ethernet/dec/tulip/de4x5.o: warning: objtool: 
dma_free_coherent()+0x4b: function has unreachable instruction

vim +27 include/linux/hashtable.h

d9b482c8 Sasha Levin  2012-10-30  11  #include 
d9b482c8 Sasha Levin  2012-10-30  12  #include 
d9b482c8 Sasha Levin  2012-10-30  13  #include 
d9b482c8 Sasha Levin  2012-10-30  14  
d9b482c8 Sasha Levin  2012-10-30  15  #define DEFINE_HASHTABLE(name, bits)  
\
d9b482c8 Sasha Levin  2012-10-30  16struct hlist_head name[1 << (bits)] =   
\
d9b482c8 Sasha Levin  2012-10-30  17{ [0 ... ((1 << (bits)) 
- 1)] = HLIST_HEAD_INIT }
d9b482c8 Sasha Levin  2012-10-30  18  
6180d9de Eric Dumazet 2015-11-18  19  #define 
DEFINE_READ_MOSTLY_HASHTABLE(name, bits)  \
6180d9de Eric Dumazet 2015-11-18  20struct hlist_head name[1 << (bits)] 
__read_mostly = \
6180d9de Eric Dumazet 2015-11-18  21{ [0 ... ((1 << (bits)) 
- 1)] = HLIST_HEAD_INIT }
6180d9de Eric Dumazet 2015-11-18  22  
d9b482c8 Sasha Levin  2012-10-30  23  #define DECLARE_HASHTABLE(name, bits) 
\
d9b482c8 Sasha Levin  2012-10-30  24struct hlist_head name[1 << (bits)]
d9b482c8 Sasha Levin  2012-10-30  25  
d9b482c8 Sasha Levin  2012-10-30  26  #define HASH_SIZE(name) (ARRAY_SIZE(name))
d9b482c8 Sasha Levin  2012-10-30 @27  #define HASH_BITS(name) 
ilog2(HASH_SIZE(name))
d9b482c8 Sasha Levin  2012-10-30  28  
d9b482c8 Sasha Levin  2012-10-30  29  /* Use hash_32 when possible to allow for 
fast 32bit hashing in 64bit kernels. */
d9b482c8 Sasha Levin  2012-10-30  30  #define hash_min(val, bits)   
\
d9b482c8 Sasha Levin  2012-10-30  31(sizeof(val) <= 4 ? hash_32(val, bits) 
: hash_long(val, bits))
d9b482c8 Sasha Levin  2012-10-30  32  
d9b482c8 Sasha Levin  2012-10-30  33  static inline void __hash_init(struct 
hlist_head *ht, unsigned int sz)
d9b482c8 Sasha Levin  2012-10-30  34  {
d9b482c8 Sasha Levin  2012-10-30  35unsigned int i;

:: The code at line 27 was first introduced by commit
:: d9b482c8ba1973a189f2d4c8175d405b87fbf2d7 hashtable: introduce a small 
and naive hashtable

:: TO: Sasha Levin 
:: CC: Linus Torvalds 

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation


.config.gz
Description: Binary data

[PATCH v5] net: sched: convert qdisc linked list to hashtable

[Jiri Kosina]

From: Jiri Kosina 

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.

As we're adding hashtable.h include into generic netdevice.h, we have to 
make sure HASH_SIZE macro is now non-conflicting with local definitions.

Reviewed-by: Cong Wang 
Signed-off-by: Jiri Kosina 
---

v1 -> v2: fix up RCU hastable usage wrt. rtnl
  fix compilation of .c files which define their own
  HASH_SIZE that now oncflicts with the one from
  hashtable.h (newly included via netdevice.h)

v2 -> v3: resolve HASH_SIZE identifier conflicts in a cleaner way
  fix up the number of hash bucket bits (4 bits for 16 buckets)

v3 -> v4: put the hastable into struct netdevice only if 
  CONFIG_NET_SCHED has been enabled

v4 -> v5: fix !CONFIG_NET_SCHED build (reported by Fengguang Wu)
  add Cong Wang's reviewed-by

 include/linux/netdevice.h |  4 
 include/net/pkt_sched.h   |  4 ++--
 include/net/sch_generic.h |  2 +-
 net/core/dev.c|  3 +++
 net/ipv6/ip6_gre.c| 12 ++--
 net/ipv6/ip6_tunnel.c | 10 +-
 net/ipv6/ip6_vti.c| 10 +-
 net/ipv6/sit.c| 10 +-
 net/sched/sch_api.c   | 23 +--
 net/sched/sch_generic.c   |  8 +---
 net/sched/sch_mq.c|  2 +-
 net/sched/sch_mqprio.c|  2 +-
 12 files changed, 51 insertions(+), 39 deletions(-)

diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index f45929c..17c6499 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -52,6 +52,7 @@
 #include 
 #include 
 #include 
+#include 
 
 struct netpoll_info;
 struct device;
@@ -1778,6 +1779,9 @@ struct net_device {
unsigned intnum_tx_queues;
unsigned intreal_num_tx_queues;
struct Qdisc*qdisc;
+#ifdef CONFIG_NET_SCHED
+   DECLARE_HASHTABLE   (qdisc_hash, 4);
+#endif
unsigned long   tx_queue_len;
spinlock_t  tx_global_lock;
int watchdog_timeo;
diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index fea53f4..8ba11b4 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -90,8 +90,8 @@ int unregister_qdisc(struct Qdisc_ops *qops);
 void qdisc_get_default(char *id, size_t len);
 int qdisc_set_default(const char *id);
 
-void qdisc_list_add(struct Qdisc *q);
-void qdisc_list_del(struct Qdisc *q);
+void qdisc_hash_add(struct Qdisc *q);
+void qdisc_hash_del(struct Qdisc *q);
 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle);
 struct Qdisc *qdisc_lookup_class(struct net_device *dev, u32 handle);
 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r,
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 62d5531..26f5cb3 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -67,7 +67,7 @@ struct Qdisc {
u32 limit;
const struct Qdisc_ops  *ops;
struct qdisc_size_table __rcu *stab;
-   struct list_headlist;
+   struct hlist_node   hash;
u32 handle;
u32 parent;
int (*reshape_fail)(struct sk_buff *skb,
diff --git a/net/core/dev.c b/net/core/dev.c
index 904ff43..d3736d5 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -7511,6 +7511,9 @@ struct net_device *alloc_netdev_mqs(int sizeof_priv, 
const char *name,
INIT_LIST_HEAD(>all_adj_list.lower);
INIT_LIST_HEAD(>ptype_all);
INIT_LIST_HEAD(>ptype_specific);
+#ifdef CONFIG_NET_SCHED
+   hash_init(dev->qdisc_hash);
+#endif
dev->priv_flags = IFF_XMIT_DST_RELEASE | IFF_XMIT_DST_RELEASE_PERM;
setup(dev);
 
diff --git a/net/ipv6/ip6_gre.c b/net/ipv6/ip6_gre.c
index fdc9de2..d3697a4 100644
--- a/net/ipv6/ip6_gre.c
+++ b/net/ipv6/ip6_gre.c
@@ -61,12 +61,12 @@ static bool log_ecn_error = true;
 module_param(log_ecn_error, bool, 0644);
 MODULE_PARM_DESC(log_ecn_error, "Log packets received with corrupted ECN");
 
-#define HASH_SIZE_SHIFT  5
-#define HASH_SIZE (1 << HASH_SIZE_SHIFT)
+#define IP6_GRE_HASH_SIZE_SHIFT  5
+#define IP6_GRE_HASH_SIZE (1 << IP6_GRE_HASH_SIZE_SHIFT)
 
 static int ip6gre_net_id __read_mostly;
 struct ip6gre_net {
-   struct ip6_tnl __rcu *tunnels[4][HASH_SIZE];
+   struct ip6_tnl __rcu *tunnels[4][IP6_GRE_HASH_SIZE];
 
struct net_device *fb_tunnel_dev;
 };
@@ -96,12 +96,12 @@ static void ip6gre_tnl_link_config(struct ip6_tnl *t, int