d99c1ba2ece0e0ff98488859abc30e8cde549b77
[linux-3.10.git] / include / net / inet_hashtables.h
1 /*
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.
5  *
6  * Authors:     Lotsa people, from code originally in tcp
7  *
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.
12  */
13
14 #ifndef _INET_HASHTABLES_H
15 #define _INET_HASHTABLES_H
16
17
18 #include <linux/interrupt.h>
19 #include <linux/ipv6.h>
20 #include <linux/list.h>
21 #include <linux/slab.h>
22 #include <linux/socket.h>
23 #include <linux/spinlock.h>
24 #include <linux/types.h>
25 #include <linux/wait.h>
26 #include <linux/vmalloc.h>
27
28 #include <net/inet_connection_sock.h>
29 #include <net/inet_sock.h>
30 #include <net/sock.h>
31 #include <net/tcp_states.h>
32
33 #include <asm/atomic.h>
34 #include <asm/byteorder.h>
35
36 /* This is for all connections with a full identity, no wildcards.
37  * One chain is dedicated to TIME_WAIT sockets.
38  * I'll experiment with dynamic table growth later.
39  */
40 struct inet_ehash_bucket {
41         struct hlist_head chain;
42         struct hlist_head twchain;
43 };
44
45 /* There are a few simple rules, which allow for local port reuse by
46  * an application.  In essence:
47  *
48  *      1) Sockets bound to different interfaces may share a local port.
49  *         Failing that, goto test 2.
50  *      2) If all sockets have sk->sk_reuse set, and none of them are in
51  *         TCP_LISTEN state, the port may be shared.
52  *         Failing that, goto test 3.
53  *      3) If all sockets are bound to a specific inet_sk(sk)->rcv_saddr local
54  *         address, and none of them are the same, the port may be
55  *         shared.
56  *         Failing this, the port cannot be shared.
57  *
58  * The interesting point, is test #2.  This is what an FTP server does
59  * all day.  To optimize this case we use a specific flag bit defined
60  * below.  As we add sockets to a bind bucket list, we perform a
61  * check of: (newsk->sk_reuse && (newsk->sk_state != TCP_LISTEN))
62  * As long as all sockets added to a bind bucket pass this test,
63  * the flag bit will be set.
64  * The resulting situation is that tcp_v[46]_verify_bind() can just check
65  * for this flag bit, if it is set and the socket trying to bind has
66  * sk->sk_reuse set, we don't even have to walk the owners list at all,
67  * we return that it is ok to bind this socket to the requested local port.
68  *
69  * Sounds like a lot of work, but it is worth it.  In a more naive
70  * implementation (ie. current FreeBSD etc.) the entire list of ports
71  * must be walked for each data port opened by an ftp server.  Needless
72  * to say, this does not scale at all.  With a couple thousand FTP
73  * users logged onto your box, isn't it nice to know that new data
74  * ports are created in O(1) time?  I thought so. ;-)   -DaveM
75  */
76 struct inet_bind_bucket {
77         struct net              *ib_net;
78         unsigned short          port;
79         signed short            fastreuse;
80         struct hlist_node       node;
81         struct hlist_head       owners;
82 };
83
84 #define inet_bind_bucket_for_each(tb, node, head) \
85         hlist_for_each_entry(tb, node, head, node)
86
87 struct inet_bind_hashbucket {
88         spinlock_t              lock;
89         struct hlist_head       chain;
90 };
91
92 /* This is for listening sockets, thus all sockets which possess wildcards. */
93 #define INET_LHTABLE_SIZE       32      /* Yes, really, this is all you need. */
94
95 struct inet_hashinfo {
96         /* This is for sockets with full identity only.  Sockets here will
97          * always be without wildcards and will have the following invariant:
98          *
99          *          TCP_ESTABLISHED <= sk->sk_state < TCP_CLOSE
100          *
101          * TIME_WAIT sockets use a separate chain (twchain).
102          */
103         struct inet_ehash_bucket        *ehash;
104         rwlock_t                        *ehash_locks;
105         unsigned int                    ehash_size;
106         unsigned int                    ehash_locks_mask;
107
108         /* Ok, let's try this, I give up, we do need a local binding
109          * TCP hash as well as the others for fast bind/connect.
110          */
111         struct inet_bind_hashbucket     *bhash;
112
113         unsigned int                    bhash_size;
114         /* Note : 4 bytes padding on 64 bit arches */
115
116         /* All sockets in TCP_LISTEN state will be in here.  This is the only
117          * table where wildcard'd TCP sockets can exist.  Hash function here
118          * is just local port number.
119          */
120         struct hlist_head               listening_hash[INET_LHTABLE_SIZE];
121
122         /* All the above members are written once at bootup and
123          * never written again _or_ are predominantly read-access.
124          *
125          * Now align to a new cache line as all the following members
126          * are often dirty.
127          */
128         rwlock_t                        lhash_lock ____cacheline_aligned;
129         atomic_t                        lhash_users;
130         wait_queue_head_t               lhash_wait;
131         struct kmem_cache                       *bind_bucket_cachep;
132 };
133
134 static inline struct inet_ehash_bucket *inet_ehash_bucket(
135         struct inet_hashinfo *hashinfo,
136         unsigned int hash)
137 {
138         return &hashinfo->ehash[hash & (hashinfo->ehash_size - 1)];
139 }
140
141 static inline rwlock_t *inet_ehash_lockp(
142         struct inet_hashinfo *hashinfo,
143         unsigned int hash)
144 {
145         return &hashinfo->ehash_locks[hash & hashinfo->ehash_locks_mask];
146 }
147
148 static inline int inet_ehash_locks_alloc(struct inet_hashinfo *hashinfo)
149 {
150         unsigned int i, size = 256;
151 #if defined(CONFIG_PROVE_LOCKING)
152         unsigned int nr_pcpus = 2;
153 #else
154         unsigned int nr_pcpus = num_possible_cpus();
155 #endif
156         if (nr_pcpus >= 4)
157                 size = 512;
158         if (nr_pcpus >= 8)
159                 size = 1024;
160         if (nr_pcpus >= 16)
161                 size = 2048;
162         if (nr_pcpus >= 32)
163                 size = 4096;
164         if (sizeof(rwlock_t) != 0) {
165 #ifdef CONFIG_NUMA
166                 if (size * sizeof(rwlock_t) > PAGE_SIZE)
167                         hashinfo->ehash_locks = vmalloc(size * sizeof(rwlock_t));
168                 else
169 #endif
170                 hashinfo->ehash_locks = kmalloc(size * sizeof(rwlock_t),
171                                                 GFP_KERNEL);
172                 if (!hashinfo->ehash_locks)
173                         return ENOMEM;
174                 for (i = 0; i < size; i++)
175                         rwlock_init(&hashinfo->ehash_locks[i]);
176         }
177         hashinfo->ehash_locks_mask = size - 1;
178         return 0;
179 }
180
181 static inline void inet_ehash_locks_free(struct inet_hashinfo *hashinfo)
182 {
183         if (hashinfo->ehash_locks) {
184 #ifdef CONFIG_NUMA
185                 unsigned int size = (hashinfo->ehash_locks_mask + 1) *
186                                                         sizeof(rwlock_t);
187                 if (size > PAGE_SIZE)
188                         vfree(hashinfo->ehash_locks);
189                 else
190 #endif
191                 kfree(hashinfo->ehash_locks);
192                 hashinfo->ehash_locks = NULL;
193         }
194 }
195
196 extern struct inet_bind_bucket *
197                     inet_bind_bucket_create(struct kmem_cache *cachep,
198                                             struct net *net,
199                                             struct inet_bind_hashbucket *head,
200                                             const unsigned short snum);
201 extern void inet_bind_bucket_destroy(struct kmem_cache *cachep,
202                                      struct inet_bind_bucket *tb);
203
204 static inline int inet_bhashfn(const __u16 lport, const int bhash_size)
205 {
206         return lport & (bhash_size - 1);
207 }
208
209 extern void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
210                            const unsigned short snum);
211
212 /* These can have wildcards, don't try too hard. */
213 static inline int inet_lhashfn(const unsigned short num)
214 {
215         return num & (INET_LHTABLE_SIZE - 1);
216 }
217
218 static inline int inet_sk_listen_hashfn(const struct sock *sk)
219 {
220         return inet_lhashfn(inet_sk(sk)->num);
221 }
222
223 /* Caller must disable local BH processing. */
224 static inline void __inet_inherit_port(struct sock *sk, struct sock *child)
225 {
226         struct inet_hashinfo *table = sk->sk_prot->h.hashinfo;
227         const int bhash = inet_bhashfn(inet_sk(child)->num, table->bhash_size);
228         struct inet_bind_hashbucket *head = &table->bhash[bhash];
229         struct inet_bind_bucket *tb;
230
231         spin_lock(&head->lock);
232         tb = inet_csk(sk)->icsk_bind_hash;
233         sk_add_bind_node(child, &tb->owners);
234         inet_csk(child)->icsk_bind_hash = tb;
235         spin_unlock(&head->lock);
236 }
237
238 static inline void inet_inherit_port(struct sock *sk, struct sock *child)
239 {
240         local_bh_disable();
241         __inet_inherit_port(sk, child);
242         local_bh_enable();
243 }
244
245 extern void inet_put_port(struct sock *sk);
246
247 extern void inet_listen_wlock(struct inet_hashinfo *hashinfo);
248
249 /*
250  * - We may sleep inside this lock.
251  * - If sleeping is not required (or called from BH),
252  *   use plain read_(un)lock(&inet_hashinfo.lhash_lock).
253  */
254 static inline void inet_listen_lock(struct inet_hashinfo *hashinfo)
255 {
256         /* read_lock synchronizes to candidates to writers */
257         read_lock(&hashinfo->lhash_lock);
258         atomic_inc(&hashinfo->lhash_users);
259         read_unlock(&hashinfo->lhash_lock);
260 }
261
262 static inline void inet_listen_unlock(struct inet_hashinfo *hashinfo)
263 {
264         if (atomic_dec_and_test(&hashinfo->lhash_users))
265                 wake_up(&hashinfo->lhash_wait);
266 }
267
268 extern void __inet_hash_nolisten(struct sock *sk);
269 extern void inet_hash(struct sock *sk);
270 extern void inet_unhash(struct sock *sk);
271
272 extern struct sock *__inet_lookup_listener(struct net *net,
273                                            struct inet_hashinfo *hashinfo,
274                                            const __be32 daddr,
275                                            const unsigned short hnum,
276                                            const int dif);
277
278 static inline struct sock *inet_lookup_listener(struct net *net,
279                 struct inet_hashinfo *hashinfo,
280                 __be32 daddr, __be16 dport, int dif)
281 {
282         return __inet_lookup_listener(net, hashinfo, daddr, ntohs(dport), dif);
283 }
284
285 /* Socket demux engine toys. */
286 /* What happens here is ugly; there's a pair of adjacent fields in
287    struct inet_sock; __be16 dport followed by __u16 num.  We want to
288    search by pair, so we combine the keys into a single 32bit value
289    and compare with 32bit value read from &...->dport.  Let's at least
290    make sure that it's not mixed with anything else...
291    On 64bit targets we combine comparisons with pair of adjacent __be32
292    fields in the same way.
293 */
294 typedef __u32 __bitwise __portpair;
295 #ifdef __BIG_ENDIAN
296 #define INET_COMBINED_PORTS(__sport, __dport) \
297         ((__force __portpair)(((__force __u32)(__be16)(__sport) << 16) | (__u32)(__dport)))
298 #else /* __LITTLE_ENDIAN */
299 #define INET_COMBINED_PORTS(__sport, __dport) \
300         ((__force __portpair)(((__u32)(__dport) << 16) | (__force __u32)(__be16)(__sport)))
301 #endif
302
303 #if (BITS_PER_LONG == 64)
304 typedef __u64 __bitwise __addrpair;
305 #ifdef __BIG_ENDIAN
306 #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
307         const __addrpair __name = (__force __addrpair) ( \
308                                    (((__force __u64)(__be32)(__saddr)) << 32) | \
309                                    ((__force __u64)(__be32)(__daddr)));
310 #else /* __LITTLE_ENDIAN */
311 #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
312         const __addrpair __name = (__force __addrpair) ( \
313                                    (((__force __u64)(__be32)(__daddr)) << 32) | \
314                                    ((__force __u64)(__be32)(__saddr)));
315 #endif /* __BIG_ENDIAN */
316 #define INET_MATCH(__sk, __net, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
317         (((__sk)->sk_hash == (__hash)) && ((__sk)->sk_net == (__net))   &&      \
318          ((*((__addrpair *)&(inet_sk(__sk)->daddr))) == (__cookie))     &&      \
319          ((*((__portpair *)&(inet_sk(__sk)->dport))) == (__ports))      &&      \
320          (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
321 #define INET_TW_MATCH(__sk, __net, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
322         (((__sk)->sk_hash == (__hash)) && ((__sk)->sk_net == (__net))   &&      \
323          ((*((__addrpair *)&(inet_twsk(__sk)->tw_daddr))) == (__cookie)) &&     \
324          ((*((__portpair *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) &&      \
325          (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
326 #else /* 32-bit arch */
327 #define INET_ADDR_COOKIE(__name, __saddr, __daddr)
328 #define INET_MATCH(__sk, __net, __hash, __cookie, __saddr, __daddr, __ports, __dif)     \
329         (((__sk)->sk_hash == (__hash)) && ((__sk)->sk_net == (__net))   &&      \
330          (inet_sk(__sk)->daddr          == (__saddr))           &&      \
331          (inet_sk(__sk)->rcv_saddr      == (__daddr))           &&      \
332          ((*((__portpair *)&(inet_sk(__sk)->dport))) == (__ports))      &&      \
333          (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
334 #define INET_TW_MATCH(__sk, __net, __hash,__cookie, __saddr, __daddr, __ports, __dif)   \
335         (((__sk)->sk_hash == (__hash)) && ((__sk)->sk_net == (__net))   &&      \
336          (inet_twsk(__sk)->tw_daddr     == (__saddr))           &&      \
337          (inet_twsk(__sk)->tw_rcv_saddr == (__daddr))           &&      \
338          ((*((__portpair *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) &&      \
339          (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
340 #endif /* 64-bit arch */
341
342 /*
343  * Sockets in TCP_CLOSE state are _always_ taken out of the hash, so we need
344  * not check it for lookups anymore, thanks Alexey. -DaveM
345  *
346  * Local BH must be disabled here.
347  */
348 extern struct sock * __inet_lookup_established(struct net *net,
349                 struct inet_hashinfo *hashinfo,
350                 const __be32 saddr, const __be16 sport,
351                 const __be32 daddr, const u16 hnum, const int dif);
352
353 static inline struct sock *
354         inet_lookup_established(struct net *net, struct inet_hashinfo *hashinfo,
355                                 const __be32 saddr, const __be16 sport,
356                                 const __be32 daddr, const __be16 dport,
357                                 const int dif)
358 {
359         return __inet_lookup_established(net, hashinfo, saddr, sport, daddr,
360                                          ntohs(dport), dif);
361 }
362
363 static inline struct sock *__inet_lookup(struct net *net,
364                                          struct inet_hashinfo *hashinfo,
365                                          const __be32 saddr, const __be16 sport,
366                                          const __be32 daddr, const __be16 dport,
367                                          const int dif)
368 {
369         u16 hnum = ntohs(dport);
370         struct sock *sk = __inet_lookup_established(net, hashinfo,
371                                 saddr, sport, daddr, hnum, dif);
372
373         return sk ? : __inet_lookup_listener(net, hashinfo, daddr, hnum, dif);
374 }
375
376 static inline struct sock *inet_lookup(struct net *net,
377                                        struct inet_hashinfo *hashinfo,
378                                        const __be32 saddr, const __be16 sport,
379                                        const __be32 daddr, const __be16 dport,
380                                        const int dif)
381 {
382         struct sock *sk;
383
384         local_bh_disable();
385         sk = __inet_lookup(net, hashinfo, saddr, sport, daddr, dport, dif);
386         local_bh_enable();
387
388         return sk;
389 }
390
391 extern int __inet_hash_connect(struct inet_timewait_death_row *death_row,
392                 struct sock *sk, u32 port_offset,
393                 int (*check_established)(struct inet_timewait_death_row *,
394                         struct sock *, __u16, struct inet_timewait_sock **),
395                                void (*hash)(struct sock *sk));
396 extern int inet_hash_connect(struct inet_timewait_death_row *death_row,
397                              struct sock *sk);
398 #endif /* _INET_HASHTABLES_H */