Unified socket storage. (with small bench).
Subsystems (8)
PATCH 1/1 Unified socket storage. (with small bench).
Hi.
This is second patch which implements unified cache of sockets for network instead of old hash tables. It stores all types of sockets (although I only implemented af_inet, unix, netlink and raw ones for now) in single object structure called multidimensional trie (which is similar to judy array in some way).
I performed simple performance test with handmade client and httperf. The former is just epoll driven client which issues requested number of requests one-by-one (or with some concurrency, which does not yet proven to work correctly).
With mpm apache on test machine I got sustained 2k/s requests for mdt and about 1200/s for (untuned) hash. With lighttpd and httperf (10k max, 1k rate) I got sustained 1k/s for mdt and 550-1000/s for untuned hash. With tuned hash (thash_entries=1000000) I got both 1k/s, with 30k max, 3k rate httperf I got 1650 for mdt and 1k for tuned hash. Server was with lighttpd 1.4.13. (handmade server as long as 'echo -en "GET / HTTP/1.0\n\n" | nc server 80' does not work due to unknown reason, I did not investigate).
Results are quite small for that machine (amd athlon64 3500+ with 1gb of ram and gigabit r8169 adapter), but I have all debug options turned on (including heavy slab/vm).
Kernel is quite old 2.6.21-rc3.
Some design bits.
Unified storage is a trie which uses several bits to select a node (compared to usual trie where only one bit is used). Current implementation uses 160 bit keys, which include local/remote address/port, protocol, network family and bound interface number. The same tree thus can store all network protocols (including unix, in this case name is hashed, and result node should have a list of entries with the same hash, which is not completed yet).
Due to the nature of the trie, it does not require rebalancing, and thus it is easily possible to implement rcu protection for socket lookup (which was done).
Due to the fact, that several bits are used to select an entry on every given level (8 in this setup), there is quite noticeble overhead comapred to hash table, but socket structure itself does not have quite a few entries too.
So, this is dynamic structure which can host any kind of network sockets (actually any structure pointer which can be addressed with 160 bits). Structure can be extended to support ipv6 (needs to increase key length) with essentially any number of elements in it.
Code is in development stage, but I would like to rise a discussion about needs to continue this development before next steps.
Attached patch against 2.6.21-rc3 tree, due to heavy reusage of insert/remove/lookup methods number of insertions is smaller than number of deleted lines (not counting needed to be removed inet_hashtables.[ch] in future). Code does not support any kind of statistics (yet).
Link to previous (more complete) description:
http://marc.info/?l=linux-netdev&m=117458697411808&w=2
Thank you.
include/linux/netlink.h | 1 - include/net/af_unix.h | 26 -- include/net/inet_connection_sock.h | 6 +- include/net/inet_hashtables.h | 5 - include/net/inet_timewait_sock.h | 24 +-- include/net/lookup.h | 79 +++++ include/net/netlink.h | 33 ++ include/net/raw.h | 1 + include/net/sock.h | 116 +------ include/net/tcp.h | 7 +- include/net/udp.h | 13 +- net/core/skbuff.c | 2 + net/core/sock.c | 1 - net/ipv4/Kconfig | 1 + net/ipv4/Makefile | 4 +- net/ipv4/af_inet.c | 20 +- net/ipv4/icmp.c | 16 +- net/ipv4/inet_connection_sock.c | 134 +-------- net/ipv4/inet_diag.c | 11 +- net/ipv4/inet_timewait_sock.c | 76 +---- net/ipv4/ip_input.c | 10 +- net/ipv4/mdt.c | 650 ++++++++++++++++++++++++++++++++++++ net/ipv4/raw.c | 67 +--- net/ipv4/tcp.c | 60 +---- net/ipv4/tcp_ipv4.c | 71 ++--- net/ipv4/tcp_minisocks.c | 3 +- net/ipv4/udp.c | 262 +-------------- net/ipv4/udplite.c | 14 +- net/netlink/af_netlink.c | 333 ++++--------------- net/packet/af_packet.c | 62 +--- net/unix/af_unix.c | 126 ++------ net/unix/garbage.c | 10 +- 32 files changed, 1010 insertions(+), 1234 deletions(-)
include/linux/netlink.h +0 -1
@@ -151,7 +151,6 @@ struct netlink_skb_parms#define NETLINK_CB (skb) (*(struct netlink_skb_parms*)&((skb)->cb))#define NETLINK_CREDS (skb) (&NETLINK_CB((skb)).creds) -extern struct sock *netlink_kernel_create (int unit,unsigned int groups,void (*input)(struct sock *sk,int len),struct module *module);extern void netlink_ack (struct sk_buff *in_skb,struct nlmsghdr *nlh,int err);extern int netlink_has_listeners (struct sock *sk,unsigned int group);
include/net/af_unix.h +0 -26
@@ -17,32 +17,6 @@ extern spinlock_t unix_table_lock;extern atomic_t unix_tot_inflight; -static inline struct sock *first_unix_socket (int *i) -{ -for (*i =0 ; *i <=UNIX_HASH_SIZE ; (*i)++) { -if (!hlist_empty (&unix_socket_table[*i])) -return __sk_head (&unix_socket_table[*i]); - } -return NULL ; -} - -static inline struct sock *next_unix_socket (int *i,struct sock *s) -{ -struct sock *next =sk_next (s); -/* More in this chain? */ -if (next) -return next; -/* Look for next non-empty chain. */ -for ((*i)++; *i <=UNIX_HASH_SIZE ; (*i)++) { -if (!hlist_empty (&unix_socket_table[*i])) -return __sk_head (&unix_socket_table[*i]); - } -return NULL ; -} - -#define forall_unix_sockets (i, s) \ - for (s = first_unix_socket(&(i)); s; s = next_unix_socket(&(i),(s))) -struct unix_address {atomic_t refcnt;int len;
include/net/inet_connection_sock.h +1 -5
@@ -244,11 +244,7 @@ extern struct request_sock *inet_csk_search_req(const struct sock *sk, const __be32 laddr);extern int inet_csk_bind_conflict (const struct sock *sk,const struct inet_bind_bucket *tb); -extern int inet_csk_get_port (struct inet_hashinfo *hashinfo, -struct sock *sk,unsigned short snum, -int (*bind_conflict)(const struct sock *sk, -const struct inet_bind_bucket *tb)); - +extern int inet_csk_get_port (struct sock *sk,unsigned short snum);extern struct dst_entry *inet_csk_route_req (struct sock *sk,const struct request_sock *req);
include/net/inet_hashtables.h +0 -5
@@ -266,11 +266,6 @@ out:wake_up (&hashinfo->lhash_wait); } -static inline int inet_iif (const struct sk_buff *skb) -{ -return ((struct rtable *)skb->dst)->rt_iif; -} - extern struct sock *__inet_lookup_listener(struct inet_hashinfo *hashinfo, const __be32 daddr, const unsigned short hnum,
include/net/inet_timewait_sock.h +2 -22
@@ -78,7 +78,6 @@ struct inet_timewait_death_row {struct timer_list tw_timer;int slot;struct hlist_head cells[INET_TWDR_TWKILL_SLOTS ]; -struct inet_hashinfo *hashinfo;int sysctl_tw_recycle;int sysctl_max_tw_buckets; };
@@ -110,10 +109,7 @@ struct inet_timewait_sock {#define tw_state __tw_common.skc_state#define tw_reuse __tw_common.skc_reuse#define tw_bound_dev_if __tw_common.skc_bound_dev_if -#define tw_node __tw_common.skc_node -#define tw_bind_node __tw_common.skc_bind_node#define tw_refcnt __tw_common.skc_refcnt -#define tw_hash __tw_common.skc_hash#define tw_prot __tw_common.skc_protvolatile unsigned char tw_substate;/* 3 bits hole, try to pack */
@@ -131,22 +127,9 @@ struct inet_timewait_sock {__u16 tw_ipv6_offset;int tw_timeout;unsigned long tw_ttd; -struct inet_bind_bucket *tw_tb;struct hlist_node tw_death_node; }; -static inline void inet_twsk_add_node (struct inet_timewait_sock *tw, -struct hlist_head *list) -{ -hlist_add_head (&tw->tw_node, list); -} - -static inline void inet_twsk_add_bind_node (struct inet_timewait_sock *tw, -struct hlist_head *list) -{ -hlist_add_head (&tw->tw_bind_node, list); -} -static inline int inet_twsk_dead_hashed (const struct inet_timewait_sock *tw) {return !hlist_unhashed (&tw->tw_death_node);
@@ -209,12 +192,9 @@ static inline void inet_twsk_put(struct inet_timewait_sock *tw)extern struct inet_timewait_sock *inet_twsk_alloc (const struct sock *sk,const int state); -extern void __inet_twsk_kill (struct inet_timewait_sock *tw, -struct inet_hashinfo *hashinfo); - +extern void __inet_twsk_kill (struct inet_timewait_sock *tw);extern void __inet_twsk_hashdance (struct inet_timewait_sock *tw, -struct sock *sk, -struct inet_hashinfo *hashinfo); +struct sock *sk); extern void inet_twsk_schedule(struct inet_timewait_sock *tw, struct inet_timewait_death_row *twdr,
include/net/lookup.h new file +79 -0
79 lines not on this page · raw message
include/net/netlink.h +33 -0
@@ -1016,4 +1016,37 @@ static inline int nla_validate_nested(struct nlattr *start, int maxtype,#define nla_for_each_nested (pos, nla, rem) \ nla_for_each_attr(pos, nla_data(nla), nla_len(nla), rem) +#ifdef __KERNEL__ + +#include <net/sock.h> + +struct netlink_sock { +/* struct sock has to be the first member of netlink_sock */ +struct sock sk; +u32 pid; +u32 dst_pid; +u32 dst_group; +u32 flags; +u32 subscriptions; +u32 ngroups; +unsigned long *groups; +unsigned long state; +wait_queue_head_t wait; +struct netlink_callback *cb; +spinlock_t cb_lock; +void (*data_ready)(struct sock *sk,int bytes); +struct hlist_node nlk_node; +struct module *module; +}; + +#define sk_for_each_bound (sk, node, head) \ + hlist_for_each_entry(sk, node, head, nlk_node) + +static inline struct netlink_sock *nlk_sk (struct sock *sk) +{ +return (struct netlink_sock *)sk; +} + +#endif +#endif
include/net/raw.h +1 -0
@@ -29,6 +29,7 @@ extern int raw_rcv(struct sock *, struct sk_buff *);* hashing mechanism, make sure you update icmp.c as well. */ #define RAWV4_HTABLE_SIZE MAX_INET_PROTOS +extern int raw_in_use;extern struct hlist_head raw_v4_htable[RAWV4_HTABLE_SIZE ];extern rwlock_t raw_v4_lock;
include/net/sock.h +17 -99
176 lines not on this page · raw message
include/net/tcp.h +3 -4
@@ -32,7 +32,7 @@#include <net/inet_connection_sock.h> #include <net/inet_timewait_sock.h> -#include <net/inet_hashtables.h> +#include <net/lookup.h> #include <net/checksum.h> #include <net/request_sock.h> #include <net/sock.h>
@@ -42,8 +42,6 @@#include <linux/seq_file.h> -extern struct inet_hashinfo tcp_hashinfo; -extern atomic_t tcp_orphan_count;extern void tcp_time_wait (struct sock *sk,int state,int timeo);
@@ -408,6 +406,7 @@ extern struct sk_buff * tcp_make_synack(struct sock *sk,extern int tcp_disconnect (struct sock *sk,int flags);extern void tcp_unhash (struct sock *sk); +extern void tcp_v4_hash (struct sock *sk);/* From syncookies.c */ extern struct sock *cookie_v4_check(struct sock *sk, struct sk_buff *skb,
@@ -901,7 +900,7 @@ static inline void tcp_set_state(struct sock *sk, int state) sk->sk_prot->unhash (sk);if (inet_csk (sk)->icsk_bind_hash && !(sk->sk_userlocks &SOCK_BINDPORT_LOCK )) -inet_put_port (&tcp_hashinfo, sk); +proto_put_port (sk);/* fall through */ default :if (oldstate==TCP_ESTABLISHED )
include/net/udp.h +5 -8
@@ -30,6 +30,7 @@#include <linux/ipv6.h> #include <linux/seq_file.h> #include <linux/poll.h> +#include <net/lookup.h> /** * struct udp_skb_cb - UDP(-Lite) private variables
@@ -101,19 +102,15 @@ static inline __wsum udp_csum_outgoing(struct sock *sk, struct sk_buff *skb) }/* hash routines shared between UDPv4/6 and UDP-Litev4/6 */ -static inline void udp_lib_hash (struct sock *sk) +static inline int udp_lib_hash (struct sock *sk) {BUG (); +return 0 ; } -static inline void udp_lib_unhash (struct sock *sk) +static inline int udp_lib_unhash (struct sock *sk) { -write_lock_bh (&udp_hash_lock); -if (sk_del_node_init (sk)) { -inet_sk (sk)->num =0 ; -sock_prot_dec_use (sk->sk_prot); - } -write_unlock_bh (&udp_hash_lock); +return mdt_remove_sock (sk); }static inline void udp_lib_close (struct sock *sk,long timeout)
net/core/skbuff.c +2 -0
@@ -61,6 +61,7 @@#include <net/sock.h> #include <net/checksum.h> #include <net/xfrm.h> +#include <net/lookup.h> #include <asm/uaccess.h> #include <asm/system.h>
@@ -2057,6 +2058,7 @@ void __init skb_init(void)0 ,SLAB_HWCACHE_ALIGN |SLAB_PANIC , NULL, NULL); +mdt_sysinit (); }EXPORT_SYMBOL (___pskb_trim);
net/core/sock.c +0 -1
@@ -901,7 +901,6 @@ struct sock *sk_clone(const struct sock *sk, const gfp_t priority)sock_copy (newsk, sk);/* SANITY */ -sk_node_init (&newsk->sk_node);sock_lock_init (newsk);bh_lock_sock (newsk);
net/ipv4/Kconfig +1 -0
@@ -1,6 +1,7 @@ # # IP configuration # + config IP_MULTICAST bool "IP: multicasting" help
net/ipv4/Makefile +2 -2
@@ -4,13 +4,13 @@ obj-y := route.o inetpeer.o protocol.o \ ip_input.o ip_fragment.o ip_forward.o ip_options.o \ - ip_output.o ip_sockglue.o inet_hashtables.o \ + ip_output.o ip_sockglue.o \ inet_timewait_sock.o inet_connection_sock.o \ tcp.o tcp_input.o tcp_output.o tcp_timer.o tcp_ipv4.o \ tcp_minisocks.o tcp_cong.o \ datagram.o raw.o udp.o udplite.o \ arp.o icmp.o devinet.o af_inet.o igmp.o \ - sysctl_net_ipv4.o fib_frontend.o fib_semantics.o + sysctl_net_ipv4.o fib_frontend.o fib_semantics.o mdt.o obj-$(CONFIG_IP_FIB_HASH) += fib_hash.o obj-$(CONFIG_IP_FIB_TRIE) += fib_trie.o
net/ipv4/af_inet.c +15 -5
@@ -343,7 +343,12 @@ lookup_protocol:*/ inet->sport =htons (inet->num);/* Add to protocol hash chains. */ - sk->sk_prot->hash (sk); + err = sk->sk_prot->hash (sk); +printk ("%s: sk: %p, err: %d.\n" , __func__, sk, err); +if (err) { +sock_put (sk); + goto out; + } }if (sk->sk_prot->init) {
@@ -1036,8 +1041,13 @@ static int inet_sk_reselect_saddr(struct sock *sk)* Besides that, it does not check for connection * uniqueness. Wait for troubles. */ -__sk_prot_rehash (sk); -return 0 ; + + err =mdt_remove_sock (sk); + err =mdt_insert_sock (sk); + +printk ("%s: sk: %p, err: %d.\n" , __func__, sk, err); + +return err; }int inet_sk_rebuild_header (struct sock *sk)
@@ -1359,7 +1369,8 @@ fs_initcall(inet_init);/* ------------------------------------------------------------------------ */ -#ifdef CONFIG_PROC_FS +//#ifdef CONFIG_PROC_FS +#if 0 static int __init ipv4_proc_init (void ) {int rc =0 ;
@@ -1388,7 +1399,6 @@ out_raw: rc = -ENOMEM ; goto out; } -#else /* CONFIG_PROC_FS */ static int __init ipv4_proc_init (void ) {
net/ipv4/icmp.c +6 -10
@@ -698,17 +698,13 @@ static void icmp_unreach(struct sk_buff *skb)/* Note: See raw.c and net/raw.h, RAWV4_HTABLE_SIZE==MAX_INET_PROTOS */ hash = protocol & (MAX_INET_PROTOS -1 ); -read_lock (&raw_v4_lock); -if ((raw_sk =sk_head (&raw_v4_htable[hash])) !=NULL ) { -while ((raw_sk =__raw_v4_lookup (raw_sk, protocol, iph->daddr, - iph->saddr, - skb->dev->ifindex)) !=NULL ) { -raw_err (raw_sk, skb, info); - raw_sk =sk_next (raw_sk); - iph = (struct iphdr *)skb->data; - } + raw_sk =__raw_v4_lookup (NULL , protocol, iph->daddr, + iph->saddr, + skb->dev->ifindex); +if (raw_sk) { +raw_err (raw_sk, skb, info); + iph = (struct iphdr *)skb->data; } -read_unlock (&raw_v4_lock);rcu_read_lock (); ipprot =rcu_dereference (inet_protos[hash]);
net/ipv4/inet_connection_sock.c +1 -133
158 lines not on this page · raw message
net/ipv4/inet_diag.c +8 -3
@@ -24,7 +24,7 @@#include <net/ipv6.h> #include <net/inet_common.h> #include <net/inet_connection_sock.h> -#include <net/inet_hashtables.h> +#include <net/lookup.h> #include <net/inet_timewait_sock.h> #include <net/inet6_hashtables.h>
@@ -238,9 +238,10 @@ static int inet_diag_get_exact(struct sk_buff *in_skb, hashinfo = handler->idiag_hashinfo;if (req->idiag_family ==AF_INET ) { - sk =inet_lookup (hashinfo, req->id.idiag_dst[0 ], + sk =sock_lookup (req->id.idiag_dst[0 ], req->id.idiag_dport, req->id.idiag_src[0 ], - req->id.idiag_sport, req->id.idiag_if); + req->id.idiag_sport, req->id.idiag_if, +IPPROTO_TCP ); }#if defined(CONFIG_IPV6 ) || defined (CONFIG_IPV6_MODULE ) else if (req->idiag_family == AF_INET6) {
@@ -670,6 +671,9 @@ out:static int inet_diag_dump (struct sk_buff *skb,struct netlink_callback *cb) { +#ifdef CONFIG_MDT_LOOKUP +return -1 ; +#else int i, num;int s_i, s_num;struct inet_diag_req *r =NLMSG_DATA (cb->nlh);
@@ -803,6 +807,7 @@ done: cb->args[1 ] = i; cb->args[2 ] = num;return skb->len; +#endif }static inline int inet_diag_rcv_msg (struct sk_buff *skb,struct nlmsghdr *nlh)
net/ipv4/inet_timewait_sock.c +8 -68
120 lines not on this page · raw message
net/ipv4/ip_input.c +4 -6
@@ -209,19 +209,17 @@ static inline int ip_local_deliver_finish(struct sk_buff *skb) {/* Note: See raw.c and net/raw.h, RAWV4_HTABLE_SIZE==MAX_INET_PROTOS */ int protocol = skb->nh.iph->protocol; -int hash; -struct sock *raw_sk; +int hash, raw = raw_in_use;struct net_protocol *ipprot; resubmit: hash = protocol & (MAX_INET_PROTOS -1 ); - raw_sk =sk_head (&raw_v4_htable[hash]);/* If there maybe a raw socket we must check - if not we * don't care less */ -if (raw_sk && !raw_v4_input (skb, skb->nh.iph, hash)) - raw_sk =NULL ; +if (raw_in_use && !raw_v4_input (skb, skb->nh.iph, hash)) + raw =0 ;if ((ipprot =rcu_dereference (inet_protos[hash])) !=NULL ) {int ret;
@@ -240,7 +238,7 @@ static inline int ip_local_deliver_finish(struct sk_buff *skb) }IP_INC_STATS_BH (IPSTATS_MIB_INDELIVERS ); }else { -if (!raw_sk) { +if (!raw) {if (xfrm4_policy_check (NULL ,XFRM_POLICY_IN , skb)) {IP_INC_STATS_BH (IPSTATS_MIB_INUNKNOWNPROTOS ); icmp_send(skb, ICMP_DEST_UNREACH,
net/ipv4/mdt.c new file +650 -0
650 lines not on this page · raw message
net/ipv4/raw.c +15 -52
125 lines not on this page · raw message
net/ipv4/tcp.c +3 -57
85 lines not on this page · raw message
net/ipv4/tcp_ipv4.c +30 -41
159 lines not on this page · raw message
net/ipv4/tcp_minisocks.c +1 -2
@@ -41,7 +41,6 @@ struct inet_timewait_death_row tcp_death_row = { .sysctl_max_tw_buckets = NR_FILE * 2, .period = TCP_TIMEWAIT_LEN / INET_TWDR_TWKILL_SLOTS, .death_lock = __SPIN_LOCK_UNLOCKED(tcp_death_row.death_lock), - .hashinfo = &tcp_hashinfo, .tw_timer =TIMER_INITIALIZER (inet_twdr_hangman,0 , (unsigned long)&tcp_death_row), .twkill_work = __WORK_INITIALIZER(tcp_death_row.twkill_work,
@@ -328,7 +327,7 @@ void tcp_time_wait(struct sock *sk, int state, int timeo)#endif /* Linkage updates. */ -__inet_twsk_hashdance (tw, sk, &tcp_hashinfo); +__inet_twsk_hashdance (tw, sk);/* Get the TIME_WAIT timeout firing. */ if (timeo < rto)
net/ipv4/udp.c +11 -251
324 lines not on this page · raw message
net/ipv4/udplite.c +13 -1
@@ -16,6 +16,7 @@ DEFINE_SNMP_STAT(struct udp_mib, udplite_statistics) __read_mostly;struct hlist_head udplite_hash[UDP_HTABLE_SIZE ]; +#ifdef CONFIG_MDT_LOOKUP static int udplite_port_rover; int udplite_get_port(struct sock *sk, unsigned short p,
@@ -28,7 +29,12 @@ static int udplite_v4_get_port(struct sock *sk, unsigned short snum) {return udplite_get_port (sk, snum, ipv4_rcv_saddr_equal); } - +#else +static int udplite_v4_get_port (struct sock *sk,unsigned short snum) +{ +return mdt_insert_sock_port (sk, snum); +} +#endif static int udplite_rcv (struct sk_buff *skb) {return __udp4_lib_rcv (skb, udplite_hash,1 );
@@ -80,6 +86,7 @@ static struct inet_protosw udplite4_protosw = { .flags = INET_PROTOSW_PERMANENT, }; +#ifdef CONFIG_MDT_LOOKUP #ifdef CONFIG_PROC_FS static struct file_operations udplite4_seq_fops; static struct udp_seq_afinfo udplite4_seq_afinfo = {
@@ -91,6 +98,7 @@ static struct udp_seq_afinfo udplite4_seq_afinfo = { .seq_fops = &udplite4_seq_fops, };#endif +#endif void __init udplite4_register (void ) {
@@ -102,10 +110,12 @@ void __init udplite4_register(void)inet_register_protosw (&udplite4_protosw); +#ifdef CONFIG_MDT_LOOKUP #ifdef CONFIG_PROC_FS if (udp_proc_register (&udplite4_seq_afinfo))/* udplite4_proc_init() */ printk (KERN_ERR "%s: Cannot register /proc!\n" , __FUNCTION__);#endif +#endif return ; out_unregister_proto:
@@ -116,4 +126,6 @@ out_register_err:EXPORT_SYMBOL (udplite_hash);EXPORT_SYMBOL (udplite_prot); +#ifdef CONFIG_MDT_LOOKUP EXPORT_SYMBOL (udplite_get_port); +#endif
net/netlink/af_netlink.c +64 -269
472 lines not on this page · raw message
net/packet/af_packet.c +7 -55
94 lines not on this page · raw message
net/unix/af_unix.c +20 -106
95 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
Evgeniy Polyakov
Part of the diff is not shown here. View the raw message.
David Miller
maintainerFrom: Evgeniy Polyakov <[email protected]>
Date: Tue, 8 May 2007 21:43:32 +0400
Quoted 5 lines
This is second patch which implements unified cache of sockets for network instead of old hash tables. It stores all types of sockets (although I only implemented
af_inet, unix, netlink and raw ones for now) in single object structure called multidimensional trie (which is similar to judy array in some way).
Thanks for doing this work it is very interesting. :)
Quoted 7 lines
So, this is dynamic structure which can host any kind of network sockets (actually any structure pointer which can be addressed with 160 bits). Structure can be extended to support ipv6 (needs to increase key length) with essentially any number of elements in it.
Code is in development stage, but I would like to rise a discussion about needs to continue this development before next steps.
One thing that will need to be adjust for current tree is the UDP hashing mechanism. But as far as I can tell your code should be able to handle the new scheme (we now hash UDP by saddr+port when possible, and this reminds me that IPV6 is broken and needs some repairs).
What exactly does the 'stages' arg mean? Is this a method to handle partially bound sockets?
Quoted 10 lines · David Miller
From: Evgeniy Polyakov <[email protected]>
Date: Tue, 8 May 2007 21:43:32 +0400Quoted 5 lines
This is second patch which implements unified cache of sockets for network instead of old hash tables. It stores all types of sockets (although I only implemented
af_inet, unix, netlink and raw ones for now) in single object structure called multidimensional trie (which is similar to judy array in some way).Thanks for doing this work it is very interesting. :)
:) it is interesting indeed.
Quoted 5 lines
Quoted 5 lines
So, this is dynamic structure which can host any kind of network sockets (actually any structure pointer which can be addressed with 160 bits). Structure can be extended to support ipv6 (needs to increase key length) with essentially any number of elements in it.
Quoted 8 lines
Quoted 2 lines
Code is in development stage, but I would like to rise a discussion about needs to continue this development before next steps.
One thing that will need to be adjust for current tree is the UDP hashing mechanism. But as far as I can tell your code should be able to handle the new scheme (we now hash UDP by saddr+port when possible, and this reminds me that IPV6 is broken and needs some repairs).
Yes, udp with multicast can be a problem, but it can be solved exactly the same way I implemented netlink broadcast (simple solution) - multicast sockets are placed into own list/hash table/trie with special bit in key/whatever and accessed when needed.
Quoted 2 lines
What exactly does the 'stages' arg mean? Is this a method to handle partially bound sockets?
It is a fallback to select a listening socket, which has remote addr/port as zero, so when socket it selected from tree, lookup wants to first get established socket with given remote identity and if this fails, it tries to select a wildcard one.
Signature · 1 line
Evgeniy Polyakov
David Miller
maintainerFrom: Evgeniy Polyakov <[email protected]>
Date: Wed, 9 May 2007 13:34:43 +0400
Quoted 11 lines · David Miller
Quoted 5 lines
One thing that will need to be adjust for current tree is the UDP hashing mechanism. But as far as I can tell your code should be able to handle the new scheme (we now hash UDP by saddr+port when possible, and this reminds me that IPV6 is broken and needs some repairs).
Yes, udp with multicast can be a problem, but it can be solved exactly the same way I implemented netlink broadcast (simple solution) - multicast sockets are placed into own list/hash table/trie with special bit in key/whatever and accessed when needed.
Actually, I am not talking about multicast. :)
In 2.6.22 what happens now in UDP is that if a non-wildcard rcv_saddr is specified, we try to hash using the rcv_saddr and the port. But when binding we have to check first if an existing port+wildcard bind exists.
See __udp_lib_get_port() in Linus's current tree.
Quoted 7 lines
Quoted 2 lines
What exactly does the 'stages' arg mean? Is this a method to handle partially bound sockets?
It is a fallback to select a listening socket, which has remote addr/port as zero, so when socket it selected from tree, lookup wants to first get established socket with given remote identity and if this fails, it tries to select a wildcard one.
This kind of logic also has implications for UDP. :-)
Quoted 15 lines · David Miller
From: Evgeniy Polyakov <[email protected]>
Date: Wed, 9 May 2007 13:34:43 +0400Quoted 11 lines · David Miller
Quoted 5 lines
One thing that will need to be adjust for current tree is the UDP hashing mechanism. But as far as I can tell your code should be able to handle the new scheme (we now hash UDP by saddr+port when possible, and this reminds me that IPV6 is broken and needs some repairs).
Yes, udp with multicast can be a problem, but it can be solved exactly the same way I implemented netlink broadcast (simple solution) - multicast sockets are placed into own list/hash table/trie with special bit in key/whatever and accessed when needed.
Quoted 8 lines
Actually, I am not talking about multicast. :)
In 2.6.22 what happens now in UDP is that if a non-wildcard
rcv_saddris specified, we try to hash using thercv_saddrand the port. But when binding we have to check first if an existing port+wildcard bind exists.See
__udp_lib_get_port()in Linus's current tree.
I saw that discussion in netdev@, it is a good solution, but it could be moved further.
Quoted 9 lines
Quoted 7 lines
Quoted 2 lines
What exactly does the 'stages' arg mean? Is this a method to handle partially bound sockets?
It is a fallback to select a listening socket, which has remote addr/port as zero, so when socket it selected from tree, lookup wants to first get established socket with given remote identity and if this fails, it tries to select a wildcard one.
This kind of logic also has implications for UDP. :-)
That is only because we have very different way of working with udp. In udp hash table we can have multiple sockets bound to different ip addresses, but with the same port, so it will be placed into the same hash chain. With trie each socket will have differnet key, since addresses are different (or bound device number), so it automatically fixes problem with broken hash for udp (which is a bit fixed with extended hashing).
User can also specify remote address for given socket (actually netchannels use this in netfilter implementation), in that case only given set of ids (remote/local addr/port) will be used to select a socket, which can be a some kind of simple netfilter...
Signature · 1 line
Evgeniy Polyakov
David Miller
maintainerFrom: Evgeniy Polyakov <[email protected]>
Date: Wed, 9 May 2007 13:57:40 +0400
Quoted 7 lines
That is only because we have very different way of working with udp. In udp hash table we can have multiple sockets bound to different ip addresses, but with the same port, so it will be placed into the same hash chain. With trie each socket will have differnet key, since addresses are different (or bound device number), so it automatically fixes problem with broken hash for udp (which is a bit fixed with extended hashing).
Yes it is power of trie.
So connection rates are interesting, but what about raw lookup performance? Last time this topic came up you went into some cave when you looked at the trie lookup assembly and compared it to hash. :)
It does make more memory references than hash by definition, and we need to figure out whether that matters enough or not.
Quoted 11 lines · David Miller
From: Evgeniy Polyakov <[email protected]>
Date: Wed, 9 May 2007 13:57:40 +0400Quoted 7 lines
That is only because we have very different way of working with udp. In udp hash table we can have multiple sockets bound to different ip addresses, but with the same port, so it will be placed into the same hash chain. With trie each socket will have differnet key, since addresses are different (or bound device number), so it automatically fixes problem with broken hash for udp (which is a bit fixed with extended hashing).
Quoted 6 lines
Yes it is power of trie.
So connection rates are interesting, but what about raw lookup performance? Last time this topic came up you went into some cave when you looked at the trie lookup assembly and compared it to hash. :)
Sky was bluer and grass was greener that days...
We discussed raw trie with completely different lookup algo (32 bits keys only, 32 checks per lookup), current implementation (and that one in previous patchset) is a serious step further.
Quoted 2 lines
It does make more memory references than hash by definition, and we need to figure out whether that matters enough or not.
Due to algorithm changes, on each new level we get upto 256 nodes which can store a pointer to data, so usual number of lookups should be 3 (max 4) for the current key organization.
One of the worst cases is when the same source and destination address are used, but with different ports (like in shown example), in that case upto 8 lookups can be performed.
We can even tune key organization to put fields known to be different first (admin can setup some kind of a policy on bootup/runtime) or perform non-destructive hashing (exchange bits in the key according to some law, like change first bit and the last one), which will speedup lookup, but that looks more like a ugly mental exercises and should not be considered in tests for now.
Signature · 1 line
Evgeniy Polyakov