From bf9ae5386bca8836c16e69ab8fdbe46767d7452a Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:50:59 +0000 Subject: llc: use dev_hard_header Using dev_hard_header allows us to use LLC with VLANs and potentially other Ethernet/TokernRing specific encapsulations. It also removes code duplication between LLC and Ethernet/TokenRing core code. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/llc_output.c | 45 ++++++++------------------------------------- 1 file changed, 8 insertions(+), 37 deletions(-) (limited to 'net/llc') diff --git a/net/llc/llc_output.c b/net/llc/llc_output.c index 754f4fedc85..b38a1079a98 100644 --- a/net/llc/llc_output.c +++ b/net/llc/llc_output.c @@ -33,48 +33,19 @@ int llc_mac_hdr_init(struct sk_buff *skb, const unsigned char *sa, const unsigned char *da) { - int rc = 0; + int rc = -EINVAL; switch (skb->dev->type) { -#ifdef CONFIG_TR - case ARPHRD_IEEE802_TR: { - struct net_device *dev = skb->dev; - struct trh_hdr *trh; - - skb_push(skb, sizeof(*trh)); - skb_reset_mac_header(skb); - trh = tr_hdr(skb); - trh->ac = AC; - trh->fc = LLC_FRAME; - if (sa) - memcpy(trh->saddr, sa, dev->addr_len); - else - memset(trh->saddr, 0, dev->addr_len); - if (da) { - memcpy(trh->daddr, da, dev->addr_len); - tr_source_route(skb, trh, dev); - skb_reset_mac_header(skb); - } - break; - } -#endif + case ARPHRD_IEEE802_TR: case ARPHRD_ETHER: - case ARPHRD_LOOPBACK: { - unsigned short len = skb->len; - struct ethhdr *eth; - - skb_push(skb, sizeof(*eth)); - skb_reset_mac_header(skb); - eth = eth_hdr(skb); - eth->h_proto = htons(len); - memcpy(eth->h_dest, da, ETH_ALEN); - memcpy(eth->h_source, sa, ETH_ALEN); + case ARPHRD_LOOPBACK: + rc = dev_hard_header(skb, skb->dev, ETH_P_802_2, da, sa, + skb->len); + if (rc > 0) + rc = 0; break; - } default: - printk(KERN_WARNING "device type not supported: %d\n", - skb->dev->type); - rc = -EINVAL; + WARN(1, "device type not supported: %d\n", skb->dev->type); } return rc; } -- cgit v1.2.3-18-g5258 From e5cd6fe391aa8c93560bb7ffdfe334cf4d0a02e4 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:00 +0000 Subject: llc: add support for LLC_OPT_PKTINFO Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/af_llc.c | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'net/llc') diff --git a/net/llc/af_llc.c b/net/llc/af_llc.c index 3a66546cad0..ac691fe0807 100644 --- a/net/llc/af_llc.c +++ b/net/llc/af_llc.c @@ -47,6 +47,10 @@ static int llc_ui_wait_for_busy_core(struct sock *sk, long timeout); #define dprintk(args...) #endif +/* Maybe we'll add some more in the future. */ +#define LLC_CMSG_PKTINFO 1 + + /** * llc_ui_next_link_no - return the next unused link number for a sap * @sap: Address of sap to get link number from. @@ -591,6 +595,20 @@ static int llc_wait_data(struct sock *sk, long timeo) return rc; } +static void llc_cmsg_rcv(struct msghdr *msg, struct sk_buff *skb) +{ + struct llc_sock *llc = llc_sk(skb->sk); + + if (llc->cmsg_flags & LLC_CMSG_PKTINFO) { + struct llc_pktinfo info; + + info.lpi_ifindex = llc_sk(skb->sk)->dev->ifindex; + llc_pdu_decode_dsap(skb, &info.lpi_sap); + llc_pdu_decode_da(skb, info.lpi_mac); + put_cmsg(msg, SOL_LLC, LLC_OPT_PKTINFO, sizeof(info), &info); + } +} + /** * llc_ui_accept - accept a new incoming connection. * @sock: Socket which connections arrive on. @@ -812,6 +830,8 @@ copy_uaddr: memcpy(uaddr, llc_ui_skb_cb(skb), sizeof(*uaddr)); msg->msg_namelen = sizeof(*uaddr); } + if (llc_sk(sk)->cmsg_flags) + llc_cmsg_rcv(msg, skb); goto out; } @@ -1030,6 +1050,12 @@ static int llc_ui_setsockopt(struct socket *sock, int level, int optname, goto out; llc->rw = opt; break; + case LLC_OPT_PKTINFO: + if (opt) + llc->cmsg_flags |= LLC_CMSG_PKTINFO; + else + llc->cmsg_flags &= ~LLC_CMSG_PKTINFO; + break; default: rc = -ENOPROTOOPT; goto out; @@ -1083,6 +1109,9 @@ static int llc_ui_getsockopt(struct socket *sock, int level, int optname, val = llc->k; break; case LLC_OPT_RX_WIN: val = llc->rw; break; + case LLC_OPT_PKTINFO: + val = (llc->cmsg_flags & LLC_CMSG_PKTINFO) != 0; + break; default: rc = -ENOPROTOOPT; goto out; -- cgit v1.2.3-18-g5258 From abf9d537fea225af60762640361af7fb233b3103 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:01 +0000 Subject: llc: add support for SO_BINDTODEVICE Using bind(MAC address) with LLC sockets has O(n) complexity, where n is the number of interfaces. To overcome this, we add support for SO_BINDTODEVICE which drops the complexity to O(1). Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/af_llc.c | 29 +++++++++++++++++++++++++++-- 1 file changed, 27 insertions(+), 2 deletions(-) (limited to 'net/llc') diff --git a/net/llc/af_llc.c b/net/llc/af_llc.c index ac691fe0807..c4d1a1da813 100644 --- a/net/llc/af_llc.c +++ b/net/llc/af_llc.c @@ -259,7 +259,14 @@ static int llc_ui_autobind(struct socket *sock, struct sockaddr_llc *addr) if (!sock_flag(sk, SOCK_ZAPPED)) goto out; rc = -ENODEV; - llc->dev = dev_getfirstbyhwtype(&init_net, addr->sllc_arphrd); + if (sk->sk_bound_dev_if) { + llc->dev = dev_get_by_index(&init_net, sk->sk_bound_dev_if); + if (llc->dev && addr->sllc_arphrd != llc->dev->type) { + dev_put(llc->dev); + llc->dev = NULL; + } + } else + llc->dev = dev_getfirstbyhwtype(&init_net, addr->sllc_arphrd); if (!llc->dev) goto out; rc = -EUSERS; @@ -310,7 +317,25 @@ static int llc_ui_bind(struct socket *sock, struct sockaddr *uaddr, int addrlen) goto out; rc = -ENODEV; rtnl_lock(); - llc->dev = dev_getbyhwaddr(&init_net, addr->sllc_arphrd, addr->sllc_mac); + if (sk->sk_bound_dev_if) { + llc->dev = dev_get_by_index(&init_net, sk->sk_bound_dev_if); + if (llc->dev) { + if (!addr->sllc_arphrd) + addr->sllc_arphrd = llc->dev->type; + if (llc_mac_null(addr->sllc_mac)) + memcpy(addr->sllc_mac, llc->dev->dev_addr, + IFHWADDRLEN); + if (addr->sllc_arphrd != llc->dev->type || + !llc_mac_match(addr->sllc_mac, + llc->dev->dev_addr)) { + rc = -EINVAL; + dev_put(llc->dev); + llc->dev = NULL; + } + } + } else + llc->dev = dev_getbyhwaddr(&init_net, addr->sllc_arphrd, + addr->sllc_mac); rtnl_unlock(); if (!llc->dev) goto out; -- cgit v1.2.3-18-g5258 From b76f5a8427ac2928c07fa4ff2144bb8db072c240 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:02 +0000 Subject: llc: convert the socket list to RCU locking For the reclamation phase we use the SLAB_DESTROY_BY_RCU mechanism, which require some extra checks in the lookup code: a) If the current socket was released, reallocated & inserted in another list it will short circuit the iteration for the current list, thus we need to restart the lookup. b) If the current socket was released, reallocated & inserted in the same list we just need to recheck it matches the look-up criteria and if not we can skip to the next element. In this case there is no need to restart the lookup, since sockets are inserted at the start of the list and the worst that will happen is that we will iterate throught some of the list elements more then once. Note that the /proc and multicast delivery was not yet converted to RCU, it still uses spinlocks for protection. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/af_llc.c | 1 + net/llc/llc_conn.c | 93 ++++++++++++++++++++++++++++++++++++------------------ net/llc/llc_core.c | 5 +-- net/llc/llc_proc.c | 22 ++++++------- net/llc/llc_sap.c | 66 ++++++++++++++++++++++++-------------- 5 files changed, 120 insertions(+), 67 deletions(-) (limited to 'net/llc') diff --git a/net/llc/af_llc.c b/net/llc/af_llc.c index c4d1a1da813..f49f3dd6fbd 100644 --- a/net/llc/af_llc.c +++ b/net/llc/af_llc.c @@ -140,6 +140,7 @@ static struct proto llc_proto = { .name = "LLC", .owner = THIS_MODULE, .obj_size = sizeof(struct llc_sock), + .slab_flags = SLAB_DESTROY_BY_RCU, }; /** diff --git a/net/llc/llc_conn.c b/net/llc/llc_conn.c index c6bab39b018..77bb3816655 100644 --- a/net/llc/llc_conn.c +++ b/net/llc/llc_conn.c @@ -468,6 +468,19 @@ static int llc_exec_conn_trans_actions(struct sock *sk, return rc; } +static inline bool llc_estab_match(const struct llc_sap *sap, + const struct llc_addr *daddr, + const struct llc_addr *laddr, + const struct sock *sk) +{ + struct llc_sock *llc = llc_sk(sk); + + return llc->laddr.lsap == laddr->lsap && + llc->daddr.lsap == daddr->lsap && + llc_mac_match(llc->laddr.mac, laddr->mac) && + llc_mac_match(llc->daddr.mac, daddr->mac); +} + /** * __llc_lookup_established - Finds connection for the remote/local sap/mac * @sap: SAP @@ -484,23 +497,26 @@ static struct sock *__llc_lookup_established(struct llc_sap *sap, struct llc_addr *laddr) { struct sock *rc; - struct hlist_node *node; - - read_lock(&sap->sk_list.lock); - sk_for_each(rc, node, &sap->sk_list.list) { - struct llc_sock *llc = llc_sk(rc); - - if (llc->laddr.lsap == laddr->lsap && - llc->daddr.lsap == daddr->lsap && - llc_mac_match(llc->laddr.mac, laddr->mac) && - llc_mac_match(llc->daddr.mac, daddr->mac)) { - sock_hold(rc); + struct hlist_nulls_node *node; + + rcu_read_lock(); +again: + sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + if (llc_estab_match(sap, daddr, laddr, rc)) { + /* Extra checks required by SLAB_DESTROY_BY_RCU */ + if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) + goto again; + if (unlikely(llc_sk(rc)->sap != sap || + !llc_estab_match(sap, daddr, laddr, rc))) { + sock_put(rc); + continue; + } goto found; } } rc = NULL; found: - read_unlock(&sap->sk_list.lock); + rcu_read_unlock(); return rc; } @@ -516,6 +532,18 @@ struct sock *llc_lookup_established(struct llc_sap *sap, return sk; } +static inline bool llc_listener_match(const struct llc_sap *sap, + const struct llc_addr *laddr, + const struct sock *sk) +{ + struct llc_sock *llc = llc_sk(sk); + + return sk->sk_type == SOCK_STREAM && sk->sk_state == TCP_LISTEN && + llc->laddr.lsap == laddr->lsap && + (llc_mac_match(llc->laddr.mac, laddr->mac) || + llc_mac_null(llc->laddr.mac)); +} + /** * llc_lookup_listener - Finds listener for local MAC + SAP * @sap: SAP @@ -530,23 +558,26 @@ static struct sock *llc_lookup_listener(struct llc_sap *sap, struct llc_addr *laddr) { struct sock *rc; - struct hlist_node *node; - - read_lock(&sap->sk_list.lock); - sk_for_each(rc, node, &sap->sk_list.list) { - struct llc_sock *llc = llc_sk(rc); - - if (rc->sk_type == SOCK_STREAM && rc->sk_state == TCP_LISTEN && - llc->laddr.lsap == laddr->lsap && - (llc_mac_match(llc->laddr.mac, laddr->mac) || - llc_mac_null(llc->laddr.mac))) { - sock_hold(rc); + struct hlist_nulls_node *node; + + rcu_read_lock(); +again: + sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + if (llc_listener_match(sap, laddr, rc)) { + /* Extra checks required by SLAB_DESTROY_BY_RCU */ + if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) + goto again; + if (unlikely(llc_sk(rc)->sap != sap || + !llc_listener_match(sap, laddr, rc))) { + sock_put(rc); + continue; + } goto found; } } rc = NULL; found: - read_unlock(&sap->sk_list.lock); + rcu_read_unlock(); return rc; } @@ -652,10 +683,10 @@ static int llc_find_offset(int state, int ev_type) void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) { llc_sap_hold(sap); - write_lock_bh(&sap->sk_list.lock); + spin_lock_bh(&sap->sk_lock); llc_sk(sk)->sap = sap; - sk_add_node(sk, &sap->sk_list.list); - write_unlock_bh(&sap->sk_list.lock); + sk_nulls_add_node_rcu(sk, &sap->sk_list); + spin_unlock_bh(&sap->sk_lock); } /** @@ -663,14 +694,14 @@ void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) * @sap: SAP * @sk: socket * - * This function removes a connection from sk_list.list of a SAP if + * This function removes a connection from sk_list of a SAP if * the connection was in this list. */ void llc_sap_remove_socket(struct llc_sap *sap, struct sock *sk) { - write_lock_bh(&sap->sk_list.lock); - sk_del_node_init(sk); - write_unlock_bh(&sap->sk_list.lock); + spin_lock_bh(&sap->sk_lock); + sk_nulls_del_node_init_rcu(sk); + spin_unlock_bh(&sap->sk_lock); llc_sap_put(sap); } diff --git a/net/llc/llc_core.c b/net/llc/llc_core.c index ff4c0ab96a6..5276b972207 100644 --- a/net/llc/llc_core.c +++ b/net/llc/llc_core.c @@ -37,7 +37,8 @@ static struct llc_sap *llc_sap_alloc(void) if (sap) { /* sap->laddr.mac - leave as a null, it's filled by bind */ sap->state = LLC_SAP_STATE_ACTIVE; - rwlock_init(&sap->sk_list.lock); + spin_lock_init(&sap->sk_lock); + INIT_HLIST_NULLS_HEAD(&sap->sk_list, 0); atomic_set(&sap->refcnt, 1); } return sap; @@ -142,7 +143,7 @@ out: */ void llc_sap_close(struct llc_sap *sap) { - WARN_ON(!hlist_empty(&sap->sk_list.list)); + WARN_ON(!hlist_nulls_empty(&sap->sk_list)); llc_del_sap(sap); kfree(sap); } diff --git a/net/llc/llc_proc.c b/net/llc/llc_proc.c index be47ac427f6..6b3d033b323 100644 --- a/net/llc/llc_proc.c +++ b/net/llc/llc_proc.c @@ -34,19 +34,19 @@ static struct sock *llc_get_sk_idx(loff_t pos) { struct list_head *sap_entry; struct llc_sap *sap; - struct hlist_node *node; + struct hlist_nulls_node *node; struct sock *sk = NULL; list_for_each(sap_entry, &llc_sap_list) { sap = list_entry(sap_entry, struct llc_sap, node); - read_lock_bh(&sap->sk_list.lock); - sk_for_each(sk, node, &sap->sk_list.list) { + spin_lock_bh(&sap->sk_lock); + sk_nulls_for_each(sk, node, &sap->sk_list) { if (!pos) goto found; --pos; } - read_unlock_bh(&sap->sk_list.lock); + spin_unlock_bh(&sap->sk_lock); } sk = NULL; found: @@ -73,25 +73,25 @@ static void *llc_seq_next(struct seq_file *seq, void *v, loff_t *pos) goto out; } sk = v; - next = sk_next(sk); + next = sk_nulls_next(sk); if (next) { sk = next; goto out; } llc = llc_sk(sk); sap = llc->sap; - read_unlock_bh(&sap->sk_list.lock); + spin_unlock_bh(&sap->sk_lock); sk = NULL; for (;;) { if (sap->node.next == &llc_sap_list) break; sap = list_entry(sap->node.next, struct llc_sap, node); - read_lock_bh(&sap->sk_list.lock); - if (!hlist_empty(&sap->sk_list.list)) { - sk = sk_head(&sap->sk_list.list); + spin_lock_bh(&sap->sk_lock); + if (!hlist_nulls_empty(&sap->sk_list)) { + sk = sk_nulls_head(&sap->sk_list); break; } - read_unlock_bh(&sap->sk_list.lock); + spin_unlock_bh(&sap->sk_lock); } out: return sk; @@ -104,7 +104,7 @@ static void llc_seq_stop(struct seq_file *seq, void *v) struct llc_sock *llc = llc_sk(sk); struct llc_sap *sap = llc->sap; - read_unlock_bh(&sap->sk_list.lock); + spin_unlock_bh(&sap->sk_lock); } read_unlock_bh(&llc_sap_list_lock); } diff --git a/net/llc/llc_sap.c b/net/llc/llc_sap.c index 008de1fc42c..39760d013ce 100644 --- a/net/llc/llc_sap.c +++ b/net/llc/llc_sap.c @@ -297,6 +297,17 @@ static void llc_sap_rcv(struct llc_sap *sap, struct sk_buff *skb, llc_sap_state_process(sap, skb); } +static inline bool llc_dgram_match(const struct llc_sap *sap, + const struct llc_addr *laddr, + const struct sock *sk) +{ + struct llc_sock *llc = llc_sk(sk); + + return sk->sk_type == SOCK_DGRAM && + llc->laddr.lsap == laddr->lsap && + llc_mac_match(llc->laddr.mac, laddr->mac); +} + /** * llc_lookup_dgram - Finds dgram socket for the local sap/mac * @sap: SAP @@ -309,25 +320,41 @@ static struct sock *llc_lookup_dgram(struct llc_sap *sap, const struct llc_addr *laddr) { struct sock *rc; - struct hlist_node *node; - - read_lock_bh(&sap->sk_list.lock); - sk_for_each(rc, node, &sap->sk_list.list) { - struct llc_sock *llc = llc_sk(rc); - - if (rc->sk_type == SOCK_DGRAM && - llc->laddr.lsap == laddr->lsap && - llc_mac_match(llc->laddr.mac, laddr->mac)) { - sock_hold(rc); + struct hlist_nulls_node *node; + + rcu_read_lock_bh(); +again: + sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + if (llc_dgram_match(sap, laddr, rc)) { + /* Extra checks required by SLAB_DESTROY_BY_RCU */ + if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) + goto again; + if (unlikely(llc_sk(rc)->sap != sap || + !llc_dgram_match(sap, laddr, rc))) { + sock_put(rc); + continue; + } goto found; } } rc = NULL; found: - read_unlock_bh(&sap->sk_list.lock); + rcu_read_unlock_bh(); return rc; } +static inline bool llc_mcast_match(const struct llc_sap *sap, + const struct llc_addr *laddr, + const struct sk_buff *skb, + const struct sock *sk) +{ + struct llc_sock *llc = llc_sk(sk); + + return sk->sk_type == SOCK_DGRAM && + llc->laddr.lsap == laddr->lsap && + llc->dev == skb->dev; +} + /** * llc_sap_mcast - Deliver multicast PDU's to all matching datagram sockets. * @sap: SAP @@ -341,20 +368,13 @@ static void llc_sap_mcast(struct llc_sap *sap, struct sk_buff *skb) { struct sock *sk; - struct hlist_node *node; + struct hlist_nulls_node *node; - read_lock_bh(&sap->sk_list.lock); - sk_for_each(sk, node, &sap->sk_list.list) { - struct llc_sock *llc = llc_sk(sk); + spin_lock_bh(&sap->sk_lock); + sk_nulls_for_each_rcu(sk, node, &sap->sk_list) { struct sk_buff *skb1; - if (sk->sk_type != SOCK_DGRAM) - continue; - - if (llc->laddr.lsap != laddr->lsap) - continue; - - if (llc->dev != skb->dev) + if (!llc_mcast_match(sap, laddr, skb, sk)) continue; skb1 = skb_clone(skb, GFP_ATOMIC); @@ -365,7 +385,7 @@ static void llc_sap_mcast(struct llc_sap *sap, llc_sap_rcv(sap, skb1, sk); sock_put(sk); } - read_unlock_bh(&sap->sk_list.lock); + spin_unlock_bh(&sap->sk_lock); } -- cgit v1.2.3-18-g5258 From 0f7b67dd9e1192976f5e5a78934c7a339ff7c45f Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:03 +0000 Subject: llc: optimize multicast delivery Optimize multicast delivery by doing the actual delivery without holding the lock. Based on the same approach used in UDP code. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/llc_sap.c | 36 ++++++++++++++++++++++++++++-------- 1 file changed, 28 insertions(+), 8 deletions(-) (limited to 'net/llc') diff --git a/net/llc/llc_sap.c b/net/llc/llc_sap.c index 39760d013ce..94790e60d07 100644 --- a/net/llc/llc_sap.c +++ b/net/llc/llc_sap.c @@ -355,6 +355,24 @@ static inline bool llc_mcast_match(const struct llc_sap *sap, llc->dev == skb->dev; } +static void llc_do_mcast(struct llc_sap *sap, struct sk_buff *skb, + struct sock **stack, int count) +{ + struct sk_buff *skb1; + int i; + + for (i = 0; i < count; i++) { + skb1 = skb_clone(skb, GFP_ATOMIC); + if (!skb1) { + sock_put(stack[i]); + continue; + } + + llc_sap_rcv(sap, skb1, stack[i]); + sock_put(stack[i]); + } +} + /** * llc_sap_mcast - Deliver multicast PDU's to all matching datagram sockets. * @sap: SAP @@ -367,25 +385,27 @@ static void llc_sap_mcast(struct llc_sap *sap, const struct llc_addr *laddr, struct sk_buff *skb) { - struct sock *sk; + int i = 0, count = 256 / sizeof(struct sock *); + struct sock *sk, *stack[count]; struct hlist_nulls_node *node; spin_lock_bh(&sap->sk_lock); sk_nulls_for_each_rcu(sk, node, &sap->sk_list) { - struct sk_buff *skb1; if (!llc_mcast_match(sap, laddr, skb, sk)) continue; - skb1 = skb_clone(skb, GFP_ATOMIC); - if (!skb1) - break; - sock_hold(sk); - llc_sap_rcv(sap, skb1, sk); - sock_put(sk); + if (i < count) + stack[i++] = sk; + else { + llc_do_mcast(sap, skb, stack, i); + i = 0; + } } spin_unlock_bh(&sap->sk_lock); + + llc_do_mcast(sap, skb, stack, i); } -- cgit v1.2.3-18-g5258 From 6d2e3ea284463d5ab34e9cf2a41d0b8627b95d02 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:04 +0000 Subject: llc: use a device based hash table to speed up multicast delivery This patch adds a per SAP device based hash table to solve the multicast delivery scalability issue when we have large number of interfaces and a large number of sockets bound to the same SAP. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/llc_conn.c | 10 +++++++++- net/llc/llc_sap.c | 8 ++++++-- 2 files changed, 15 insertions(+), 3 deletions(-) (limited to 'net/llc') diff --git a/net/llc/llc_conn.c b/net/llc/llc_conn.c index 77bb3816655..10cdfe2db83 100644 --- a/net/llc/llc_conn.c +++ b/net/llc/llc_conn.c @@ -682,10 +682,15 @@ static int llc_find_offset(int state, int ev_type) */ void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) { + struct llc_sock *llc = llc_sk(sk); + struct hlist_head *dev_hb = llc_sk_dev_hash(sap, llc->dev->ifindex); + llc_sap_hold(sap); - spin_lock_bh(&sap->sk_lock); llc_sk(sk)->sap = sap; + + spin_lock_bh(&sap->sk_lock); sk_nulls_add_node_rcu(sk, &sap->sk_list); + hlist_add_head(&llc->dev_hash_node, dev_hb); spin_unlock_bh(&sap->sk_lock); } @@ -699,8 +704,11 @@ void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) */ void llc_sap_remove_socket(struct llc_sap *sap, struct sock *sk) { + struct llc_sock *llc = llc_sk(sk); + spin_lock_bh(&sap->sk_lock); sk_nulls_del_node_init_rcu(sk); + hlist_del(&llc->dev_hash_node); spin_unlock_bh(&sap->sk_lock); llc_sap_put(sap); } diff --git a/net/llc/llc_sap.c b/net/llc/llc_sap.c index 94790e60d07..94cb706f6cc 100644 --- a/net/llc/llc_sap.c +++ b/net/llc/llc_sap.c @@ -387,10 +387,14 @@ static void llc_sap_mcast(struct llc_sap *sap, { int i = 0, count = 256 / sizeof(struct sock *); struct sock *sk, *stack[count]; - struct hlist_nulls_node *node; + struct hlist_node *node; + struct llc_sock *llc; + struct hlist_head *dev_hb = llc_sk_dev_hash(sap, skb->dev->ifindex); spin_lock_bh(&sap->sk_lock); - sk_nulls_for_each_rcu(sk, node, &sap->sk_list) { + hlist_for_each_entry(llc, node, dev_hb, dev_hash_node) { + + sk = &llc->sk; if (!llc_mcast_match(sap, laddr, skb, sk)) continue; -- cgit v1.2.3-18-g5258 From 52d58aef5ee460fedd7f250f05e79081019f2c79 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:05 +0000 Subject: llc: replace the socket list with a local address based hash For the cases where a lot of interfaces are used in conjunction with a lot of LLC sockets bound to the same SAP, the iteration of the socket list becomes prohibitively expensive. Replacing the list with a a local address based hash significantly improves the bind and listener lookup operations as well as the datagram delivery. Connected sockets delivery is also improved, but this patch does not address the case where we have lots of sockets with the same local address connected to different remote addresses. In order to keep the socket sanity checks alive and fast a socket counter was added to the SAP structure. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/llc_conn.c | 70 +++++++++++++++++++++++++++++++++++++++--------------- net/llc/llc_core.c | 6 +++-- net/llc/llc_proc.c | 44 +++++++++++++++++++++++----------- net/llc/llc_sap.c | 11 ++++++++- 4 files changed, 95 insertions(+), 36 deletions(-) (limited to 'net/llc') diff --git a/net/llc/llc_conn.c b/net/llc/llc_conn.c index 10cdfe2db83..a8dde9b010d 100644 --- a/net/llc/llc_conn.c +++ b/net/llc/llc_conn.c @@ -498,10 +498,12 @@ static struct sock *__llc_lookup_established(struct llc_sap *sap, { struct sock *rc; struct hlist_nulls_node *node; + int slot = llc_sk_laddr_hashfn(sap, laddr); + struct hlist_nulls_head *laddr_hb = &sap->sk_laddr_hash[slot]; rcu_read_lock(); again: - sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + sk_nulls_for_each_rcu(rc, node, laddr_hb) { if (llc_estab_match(sap, daddr, laddr, rc)) { /* Extra checks required by SLAB_DESTROY_BY_RCU */ if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) @@ -515,6 +517,13 @@ again: } } rc = NULL; + /* + * if the nulls value we got at the end of this lookup is + * not the expected one, we must restart lookup. + * We probably met an item that was moved to another chain. + */ + if (unlikely(get_nulls_value(node) != slot)) + goto again; found: rcu_read_unlock(); return rc; @@ -540,29 +549,20 @@ static inline bool llc_listener_match(const struct llc_sap *sap, return sk->sk_type == SOCK_STREAM && sk->sk_state == TCP_LISTEN && llc->laddr.lsap == laddr->lsap && - (llc_mac_match(llc->laddr.mac, laddr->mac) || - llc_mac_null(llc->laddr.mac)); + llc_mac_match(llc->laddr.mac, laddr->mac); } -/** - * llc_lookup_listener - Finds listener for local MAC + SAP - * @sap: SAP - * @laddr: address of local LLC (MAC + SAP) - * - * Search connection list of the SAP and finds connection listening on - * local mac, and local sap. Returns pointer for parent socket found, - * %NULL otherwise. - * Caller has to make sure local_bh is disabled. - */ -static struct sock *llc_lookup_listener(struct llc_sap *sap, - struct llc_addr *laddr) +static struct sock *__llc_lookup_listener(struct llc_sap *sap, + struct llc_addr *laddr) { struct sock *rc; struct hlist_nulls_node *node; + int slot = llc_sk_laddr_hashfn(sap, laddr); + struct hlist_nulls_head *laddr_hb = &sap->sk_laddr_hash[slot]; rcu_read_lock(); again: - sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + sk_nulls_for_each_rcu(rc, node, laddr_hb) { if (llc_listener_match(sap, laddr, rc)) { /* Extra checks required by SLAB_DESTROY_BY_RCU */ if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) @@ -576,11 +576,40 @@ again: } } rc = NULL; + /* + * if the nulls value we got at the end of this lookup is + * not the expected one, we must restart lookup. + * We probably met an item that was moved to another chain. + */ + if (unlikely(get_nulls_value(node) != slot)) + goto again; found: rcu_read_unlock(); return rc; } +/** + * llc_lookup_listener - Finds listener for local MAC + SAP + * @sap: SAP + * @laddr: address of local LLC (MAC + SAP) + * + * Search connection list of the SAP and finds connection listening on + * local mac, and local sap. Returns pointer for parent socket found, + * %NULL otherwise. + * Caller has to make sure local_bh is disabled. + */ +static struct sock *llc_lookup_listener(struct llc_sap *sap, + struct llc_addr *laddr) +{ + static struct llc_addr null_addr; + struct sock *rc = __llc_lookup_listener(sap, laddr); + + if (!rc) + rc = __llc_lookup_listener(sap, &null_addr); + + return rc; +} + static struct sock *__llc_lookup(struct llc_sap *sap, struct llc_addr *daddr, struct llc_addr *laddr) @@ -678,18 +707,20 @@ static int llc_find_offset(int state, int ev_type) * @sap: SAP * @sk: socket * - * This function adds a socket to sk_list of a SAP. + * This function adds a socket to the hash tables of a SAP. */ void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) { struct llc_sock *llc = llc_sk(sk); struct hlist_head *dev_hb = llc_sk_dev_hash(sap, llc->dev->ifindex); + struct hlist_nulls_head *laddr_hb = llc_sk_laddr_hash(sap, &llc->laddr); llc_sap_hold(sap); llc_sk(sk)->sap = sap; spin_lock_bh(&sap->sk_lock); - sk_nulls_add_node_rcu(sk, &sap->sk_list); + sap->sk_count++; + sk_nulls_add_node_rcu(sk, laddr_hb); hlist_add_head(&llc->dev_hash_node, dev_hb); spin_unlock_bh(&sap->sk_lock); } @@ -699,7 +730,7 @@ void llc_sap_add_socket(struct llc_sap *sap, struct sock *sk) * @sap: SAP * @sk: socket * - * This function removes a connection from sk_list of a SAP if + * This function removes a connection from the hash tables of a SAP if * the connection was in this list. */ void llc_sap_remove_socket(struct llc_sap *sap, struct sock *sk) @@ -709,6 +740,7 @@ void llc_sap_remove_socket(struct llc_sap *sap, struct sock *sk) spin_lock_bh(&sap->sk_lock); sk_nulls_del_node_init_rcu(sk); hlist_del(&llc->dev_hash_node); + sap->sk_count--; spin_unlock_bh(&sap->sk_lock); llc_sap_put(sap); } diff --git a/net/llc/llc_core.c b/net/llc/llc_core.c index 5276b972207..0c9ef8bc765 100644 --- a/net/llc/llc_core.c +++ b/net/llc/llc_core.c @@ -33,12 +33,14 @@ DEFINE_RWLOCK(llc_sap_list_lock); static struct llc_sap *llc_sap_alloc(void) { struct llc_sap *sap = kzalloc(sizeof(*sap), GFP_ATOMIC); + int i; if (sap) { /* sap->laddr.mac - leave as a null, it's filled by bind */ sap->state = LLC_SAP_STATE_ACTIVE; spin_lock_init(&sap->sk_lock); - INIT_HLIST_NULLS_HEAD(&sap->sk_list, 0); + for (i = 0; i < LLC_SK_LADDR_HASH_ENTRIES; i++) + INIT_HLIST_NULLS_HEAD(&sap->sk_laddr_hash[i], i); atomic_set(&sap->refcnt, 1); } return sap; @@ -143,7 +145,7 @@ out: */ void llc_sap_close(struct llc_sap *sap) { - WARN_ON(!hlist_nulls_empty(&sap->sk_list)); + WARN_ON(sap->sk_count); llc_del_sap(sap); kfree(sap); } diff --git a/net/llc/llc_proc.c b/net/llc/llc_proc.c index 6b3d033b323..09dec630720 100644 --- a/net/llc/llc_proc.c +++ b/net/llc/llc_proc.c @@ -34,17 +34,22 @@ static struct sock *llc_get_sk_idx(loff_t pos) { struct list_head *sap_entry; struct llc_sap *sap; - struct hlist_nulls_node *node; struct sock *sk = NULL; + int i; list_for_each(sap_entry, &llc_sap_list) { sap = list_entry(sap_entry, struct llc_sap, node); spin_lock_bh(&sap->sk_lock); - sk_nulls_for_each(sk, node, &sap->sk_list) { - if (!pos) - goto found; - --pos; + for (i = 0; i < LLC_SK_LADDR_HASH_ENTRIES; i++) { + struct hlist_nulls_head *head = &sap->sk_laddr_hash[i]; + struct hlist_nulls_node *node; + + sk_nulls_for_each(sk, node, head) { + if (!pos) + goto found; /* keep the lock */ + --pos; + } } spin_unlock_bh(&sap->sk_lock); } @@ -61,6 +66,19 @@ static void *llc_seq_start(struct seq_file *seq, loff_t *pos) return l ? llc_get_sk_idx(--l) : SEQ_START_TOKEN; } +static struct sock *laddr_hash_next(struct llc_sap *sap, int bucket) +{ + struct hlist_nulls_node *node; + struct sock *sk = NULL; + + while (++bucket < LLC_SK_LADDR_HASH_ENTRIES) + sk_nulls_for_each(sk, node, &sap->sk_laddr_hash[bucket]) + goto out; + +out: + return sk; +} + static void *llc_seq_next(struct seq_file *seq, void *v, loff_t *pos) { struct sock* sk, *next; @@ -80,17 +98,15 @@ static void *llc_seq_next(struct seq_file *seq, void *v, loff_t *pos) } llc = llc_sk(sk); sap = llc->sap; + sk = laddr_hash_next(sap, llc_sk_laddr_hashfn(sap, &llc->laddr)); + if (sk) + goto out; spin_unlock_bh(&sap->sk_lock); - sk = NULL; - for (;;) { - if (sap->node.next == &llc_sap_list) - break; - sap = list_entry(sap->node.next, struct llc_sap, node); + list_for_each_entry_continue(sap, &llc_sap_list, node) { spin_lock_bh(&sap->sk_lock); - if (!hlist_nulls_empty(&sap->sk_list)) { - sk = sk_nulls_head(&sap->sk_list); - break; - } + sk = laddr_hash_next(sap, -1); + if (sk) + break; /* keep the lock */ spin_unlock_bh(&sap->sk_lock); } out: diff --git a/net/llc/llc_sap.c b/net/llc/llc_sap.c index 94cb706f6cc..ad6e6e1cf22 100644 --- a/net/llc/llc_sap.c +++ b/net/llc/llc_sap.c @@ -321,10 +321,12 @@ static struct sock *llc_lookup_dgram(struct llc_sap *sap, { struct sock *rc; struct hlist_nulls_node *node; + int slot = llc_sk_laddr_hashfn(sap, laddr); + struct hlist_nulls_head *laddr_hb = &sap->sk_laddr_hash[slot]; rcu_read_lock_bh(); again: - sk_nulls_for_each_rcu(rc, node, &sap->sk_list) { + sk_nulls_for_each_rcu(rc, node, laddr_hb) { if (llc_dgram_match(sap, laddr, rc)) { /* Extra checks required by SLAB_DESTROY_BY_RCU */ if (unlikely(!atomic_inc_not_zero(&rc->sk_refcnt))) @@ -338,6 +340,13 @@ again: } } rc = NULL; + /* + * if the nulls value we got at the end of this lookup is + * not the expected one, we must restart lookup. + * We probably met an item that was moved to another chain. + */ + if (unlikely(get_nulls_value(node) != slot)) + goto again; found: rcu_read_unlock_bh(); return rc; -- cgit v1.2.3-18-g5258 From 8beb9ab6c2df203e8d68cb1f48cf42604a6bed86 Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:06 +0000 Subject: llc: convert llc_sap_list to RCU Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/llc_core.c | 46 ++++++++++++++-------------------------------- net/llc/llc_proc.c | 11 ++++------- 2 files changed, 18 insertions(+), 39 deletions(-) (limited to 'net/llc') diff --git a/net/llc/llc_core.c b/net/llc/llc_core.c index 0c9ef8bc765..78167e81dfe 100644 --- a/net/llc/llc_core.c +++ b/net/llc/llc_core.c @@ -23,7 +23,7 @@ #include LIST_HEAD(llc_sap_list); -DEFINE_RWLOCK(llc_sap_list_lock); +DEFINE_SPINLOCK(llc_sap_list_lock); /** * llc_sap_alloc - allocates and initializes sap. @@ -46,30 +46,6 @@ static struct llc_sap *llc_sap_alloc(void) return sap; } -/** - * llc_add_sap - add sap to station list - * @sap: Address of the sap - * - * Adds a sap to the LLC's station sap list. - */ -static void llc_add_sap(struct llc_sap *sap) -{ - list_add_tail(&sap->node, &llc_sap_list); -} - -/** - * llc_del_sap - del sap from station list - * @sap: Address of the sap - * - * Removes a sap to the LLC's station sap list. - */ -static void llc_del_sap(struct llc_sap *sap) -{ - write_lock_bh(&llc_sap_list_lock); - list_del(&sap->node); - write_unlock_bh(&llc_sap_list_lock); -} - static struct llc_sap *__llc_sap_find(unsigned char sap_value) { struct llc_sap* sap; @@ -93,13 +69,13 @@ out: */ struct llc_sap *llc_sap_find(unsigned char sap_value) { - struct llc_sap* sap; + struct llc_sap *sap; - read_lock_bh(&llc_sap_list_lock); + rcu_read_lock_bh(); sap = __llc_sap_find(sap_value); if (sap) llc_sap_hold(sap); - read_unlock_bh(&llc_sap_list_lock); + rcu_read_unlock_bh(); return sap; } @@ -120,7 +96,7 @@ struct llc_sap *llc_sap_open(unsigned char lsap, { struct llc_sap *sap = NULL; - write_lock_bh(&llc_sap_list_lock); + spin_lock_bh(&llc_sap_list_lock); if (__llc_sap_find(lsap)) /* SAP already exists */ goto out; sap = llc_sap_alloc(); @@ -128,9 +104,9 @@ struct llc_sap *llc_sap_open(unsigned char lsap, goto out; sap->laddr.lsap = lsap; sap->rcv_func = func; - llc_add_sap(sap); + list_add_tail_rcu(&sap->node, &llc_sap_list); out: - write_unlock_bh(&llc_sap_list_lock); + spin_unlock_bh(&llc_sap_list_lock); return sap; } @@ -146,7 +122,13 @@ out: void llc_sap_close(struct llc_sap *sap) { WARN_ON(sap->sk_count); - llc_del_sap(sap); + + spin_lock_bh(&llc_sap_list_lock); + list_del_rcu(&sap->node); + spin_unlock_bh(&llc_sap_list_lock); + + synchronize_rcu(); + kfree(sap); } diff --git a/net/llc/llc_proc.c b/net/llc/llc_proc.c index 09dec630720..7af1ff2d1f1 100644 --- a/net/llc/llc_proc.c +++ b/net/llc/llc_proc.c @@ -32,14 +32,11 @@ static void llc_ui_format_mac(struct seq_file *seq, u8 *addr) static struct sock *llc_get_sk_idx(loff_t pos) { - struct list_head *sap_entry; struct llc_sap *sap; struct sock *sk = NULL; int i; - list_for_each(sap_entry, &llc_sap_list) { - sap = list_entry(sap_entry, struct llc_sap, node); - + list_for_each_entry_rcu(sap, &llc_sap_list, node) { spin_lock_bh(&sap->sk_lock); for (i = 0; i < LLC_SK_LADDR_HASH_ENTRIES; i++) { struct hlist_nulls_head *head = &sap->sk_laddr_hash[i]; @@ -62,7 +59,7 @@ static void *llc_seq_start(struct seq_file *seq, loff_t *pos) { loff_t l = *pos; - read_lock_bh(&llc_sap_list_lock); + rcu_read_lock_bh(); return l ? llc_get_sk_idx(--l) : SEQ_START_TOKEN; } @@ -102,7 +99,7 @@ static void *llc_seq_next(struct seq_file *seq, void *v, loff_t *pos) if (sk) goto out; spin_unlock_bh(&sap->sk_lock); - list_for_each_entry_continue(sap, &llc_sap_list, node) { + list_for_each_entry_continue_rcu(sap, &llc_sap_list, node) { spin_lock_bh(&sap->sk_lock); sk = laddr_hash_next(sap, -1); if (sk) @@ -122,7 +119,7 @@ static void llc_seq_stop(struct seq_file *seq, void *v) spin_unlock_bh(&sap->sk_lock); } - read_unlock_bh(&llc_sap_list_lock); + rcu_read_unlock_bh(); } static int llc_seq_socket_show(struct seq_file *seq, void *v) -- cgit v1.2.3-18-g5258 From 3100aa9d74db9c6d8d9a3b6421721fc1aef4728f Mon Sep 17 00:00:00 2001 From: Octavian Purdila Date: Sat, 26 Dec 2009 11:51:08 +0000 Subject: llc: fix SAP reference counting w.r.t. socket handling The SAP ref counter gets decremented twice when deleting a socket, although for all but the first socket of a SAP the SAP ref counter was incremented only once. Signed-off-by: Octavian Purdila Signed-off-by: David S. Miller --- net/llc/af_llc.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'net/llc') diff --git a/net/llc/af_llc.c b/net/llc/af_llc.c index f49f3dd6fbd..e35d907fba2 100644 --- a/net/llc/af_llc.c +++ b/net/llc/af_llc.c @@ -197,10 +197,8 @@ static int llc_ui_release(struct socket *sock) llc->laddr.lsap, llc->daddr.lsap); if (!llc_send_disc(sk)) llc_ui_wait_for_disc(sk, sk->sk_rcvtimeo); - if (!sock_flag(sk, SOCK_ZAPPED)) { - llc_sap_put(llc->sap); + if (!sock_flag(sk, SOCK_ZAPPED)) llc_sap_remove_socket(llc->sap, sk); - } release_sock(sk); if (llc->dev) dev_put(llc->dev); @@ -352,7 +350,6 @@ static int llc_ui_bind(struct socket *sock, struct sockaddr *uaddr, int addrlen) rc = -EBUSY; /* some other network layer is using the sap */ if (!sap) goto out; - llc_sap_hold(sap); } else { struct llc_addr laddr, daddr; struct sock *ask; -- cgit v1.2.3-18-g5258