2 * INET An implementation of the TCP/IP protocol suite for the LINUX
3 * operating system. INET is implemented using the BSD Socket
4 * interface as the means of communication with the user level.
6 * Authors: Lotsa people, from code originally in tcp
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
14 #ifndef _INET_HASHTABLES_H
15 #define _INET_HASHTABLES_H
17 #include <linux/interrupt.h>
19 #include <linux/list.h>
20 #include <linux/slab.h>
21 #include <linux/spinlock.h>
22 #include <linux/types.h>
23 #include <linux/wait.h>
26 #include <net/tcp_states.h>
28 #include <asm/atomic.h>
30 /* This is for all connections with a full identity, no wildcards.
31 * New scheme, half the table is for TIME_WAIT, the other half is
32 * for the rest. I'll experiment with dynamic table growth later.
34 struct inet_ehash_bucket
{
36 struct hlist_head chain
;
37 } __attribute__((__aligned__(8)));
39 /* There are a few simple rules, which allow for local port reuse by
40 * an application. In essence:
42 * 1) Sockets bound to different interfaces may share a local port.
43 * Failing that, goto test 2.
44 * 2) If all sockets have sk->sk_reuse set, and none of them are in
45 * TCP_LISTEN state, the port may be shared.
46 * Failing that, goto test 3.
47 * 3) If all sockets are bound to a specific inet_sk(sk)->rcv_saddr local
48 * address, and none of them are the same, the port may be
50 * Failing this, the port cannot be shared.
52 * The interesting point, is test #2. This is what an FTP server does
53 * all day. To optimize this case we use a specific flag bit defined
54 * below. As we add sockets to a bind bucket list, we perform a
55 * check of: (newsk->sk_reuse && (newsk->sk_state != TCP_LISTEN))
56 * As long as all sockets added to a bind bucket pass this test,
57 * the flag bit will be set.
58 * The resulting situation is that tcp_v[46]_verify_bind() can just check
59 * for this flag bit, if it is set and the socket trying to bind has
60 * sk->sk_reuse set, we don't even have to walk the owners list at all,
61 * we return that it is ok to bind this socket to the requested local port.
63 * Sounds like a lot of work, but it is worth it. In a more naive
64 * implementation (ie. current FreeBSD etc.) the entire list of ports
65 * must be walked for each data port opened by an ftp server. Needless
66 * to say, this does not scale at all. With a couple thousand FTP
67 * users logged onto your box, isn't it nice to know that new data
68 * ports are created in O(1) time? I thought so. ;-) -DaveM
70 struct inet_bind_bucket
{
72 signed short fastreuse
;
73 struct hlist_node node
;
74 struct hlist_head owners
;
77 #define inet_bind_bucket_for_each(tb, node, head) \
78 hlist_for_each_entry(tb, node, head, node)
80 struct inet_bind_hashbucket
{
82 struct hlist_head chain
;
85 /* This is for listening sockets, thus all sockets which possess wildcards. */
86 #define INET_LHTABLE_SIZE 32 /* Yes, really, this is all you need. */
88 struct inet_hashinfo
{
89 /* This is for sockets with full identity only. Sockets here will
90 * always be without wildcards and will have the following invariant:
92 * TCP_ESTABLISHED <= sk->sk_state < TCP_CLOSE
94 * First half of the table is for sockets not in TIME_WAIT, second half
95 * is for TIME_WAIT sockets only.
97 struct inet_ehash_bucket
*ehash
;
99 /* Ok, let's try this, I give up, we do need a local binding
100 * TCP hash as well as the others for fast bind/connect.
102 struct inet_bind_hashbucket
*bhash
;
107 /* All sockets in TCP_LISTEN state will be in here. This is the only
108 * table where wildcard'd TCP sockets can exist. Hash function here
109 * is just local port number.
111 struct hlist_head listening_hash
[INET_LHTABLE_SIZE
];
113 /* All the above members are written once at bootup and
114 * never written again _or_ are predominantly read-access.
116 * Now align to a new cache line as all the following members
119 rwlock_t lhash_lock ____cacheline_aligned
;
120 atomic_t lhash_users
;
121 wait_queue_head_t lhash_wait
;
122 spinlock_t portalloc_lock
;
123 kmem_cache_t
*bind_bucket_cachep
;
127 static inline int inet_ehashfn(const __u32 laddr
, const __u16 lport
,
128 const __u32 faddr
, const __u16 fport
,
129 const int ehash_size
)
131 int h
= (laddr
^ lport
) ^ (faddr
^ fport
);
134 return h
& (ehash_size
- 1);
137 static inline int inet_sk_ehashfn(const struct sock
*sk
, const int ehash_size
)
139 const struct inet_sock
*inet
= inet_sk(sk
);
140 const __u32 laddr
= inet
->rcv_saddr
;
141 const __u16 lport
= inet
->num
;
142 const __u32 faddr
= inet
->daddr
;
143 const __u16 fport
= inet
->dport
;
145 return inet_ehashfn(laddr
, lport
, faddr
, fport
, ehash_size
);
148 extern struct inet_bind_bucket
*
149 inet_bind_bucket_create(kmem_cache_t
*cachep
,
150 struct inet_bind_hashbucket
*head
,
151 const unsigned short snum
);
152 extern void inet_bind_bucket_destroy(kmem_cache_t
*cachep
,
153 struct inet_bind_bucket
*tb
);
155 static inline int inet_bhashfn(const __u16 lport
, const int bhash_size
)
157 return lport
& (bhash_size
- 1);
160 extern void inet_bind_hash(struct sock
*sk
, struct inet_bind_bucket
*tb
,
161 const unsigned short snum
);
163 /* These can have wildcards, don't try too hard. */
164 static inline int inet_lhashfn(const unsigned short num
)
166 return num
& (INET_LHTABLE_SIZE
- 1);
169 static inline int inet_sk_listen_hashfn(const struct sock
*sk
)
171 return inet_lhashfn(inet_sk(sk
)->num
);
174 /* Caller must disable local BH processing. */
175 static inline void __inet_inherit_port(struct inet_hashinfo
*table
,
176 struct sock
*sk
, struct sock
*child
)
178 const int bhash
= inet_bhashfn(inet_sk(child
)->num
, table
->bhash_size
);
179 struct inet_bind_hashbucket
*head
= &table
->bhash
[bhash
];
180 struct inet_bind_bucket
*tb
;
182 spin_lock(&head
->lock
);
183 tb
= inet_sk(sk
)->bind_hash
;
184 sk_add_bind_node(child
, &tb
->owners
);
185 inet_sk(child
)->bind_hash
= tb
;
186 spin_unlock(&head
->lock
);
189 static inline void inet_inherit_port(struct inet_hashinfo
*table
,
190 struct sock
*sk
, struct sock
*child
)
193 __inet_inherit_port(table
, sk
, child
);
197 extern void inet_put_port(struct inet_hashinfo
*table
, struct sock
*sk
);
199 extern void inet_listen_wlock(struct inet_hashinfo
*hashinfo
);
202 * - We may sleep inside this lock.
203 * - If sleeping is not required (or called from BH),
204 * use plain read_(un)lock(&inet_hashinfo.lhash_lock).
206 static inline void inet_listen_lock(struct inet_hashinfo
*hashinfo
)
208 /* read_lock synchronizes to candidates to writers */
209 read_lock(&hashinfo
->lhash_lock
);
210 atomic_inc(&hashinfo
->lhash_users
);
211 read_unlock(&hashinfo
->lhash_lock
);
214 static inline void inet_listen_unlock(struct inet_hashinfo
*hashinfo
)
216 if (atomic_dec_and_test(&hashinfo
->lhash_users
))
217 wake_up(&hashinfo
->lhash_wait
);
220 static inline void __inet_hash(struct inet_hashinfo
*hashinfo
,
221 struct sock
*sk
, const int listen_possible
)
223 struct hlist_head
*list
;
226 BUG_TRAP(sk_unhashed(sk
));
227 if (listen_possible
&& sk
->sk_state
== TCP_LISTEN
) {
228 list
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)];
229 lock
= &hashinfo
->lhash_lock
;
230 inet_listen_wlock(hashinfo
);
232 sk
->sk_hashent
= inet_sk_ehashfn(sk
, hashinfo
->ehash_size
);
233 list
= &hashinfo
->ehash
[sk
->sk_hashent
].chain
;
234 lock
= &hashinfo
->ehash
[sk
->sk_hashent
].lock
;
237 __sk_add_node(sk
, list
);
238 sock_prot_inc_use(sk
->sk_prot
);
240 if (listen_possible
&& sk
->sk_state
== TCP_LISTEN
)
241 wake_up(&hashinfo
->lhash_wait
);
243 #endif /* _INET_HASHTABLES_H */