[CPUFREQ] Fix the p4-clockmod N60 errata workaround.
[linux-2.6/mini2440.git] / include / net / inet_hashtables.h
blob135d80fd658ebf2c8d027440a1e9580f1c2b1ba3
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.
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/config.h>
19 #include <linux/interrupt.h>
20 #include <linux/ipv6.h>
21 #include <linux/list.h>
22 #include <linux/slab.h>
23 #include <linux/socket.h>
24 #include <linux/spinlock.h>
25 #include <linux/types.h>
26 #include <linux/wait.h>
28 #include <net/inet_connection_sock.h>
29 #include <net/inet_sock.h>
30 #include <net/route.h>
31 #include <net/sock.h>
32 #include <net/tcp_states.h>
34 #include <asm/atomic.h>
35 #include <asm/byteorder.h>
37 /* This is for all connections with a full identity, no wildcards.
38 * New scheme, half the table is for TIME_WAIT, the other half is
39 * for the rest. I'll experiment with dynamic table growth later.
41 struct inet_ehash_bucket {
42 rwlock_t lock;
43 struct hlist_head chain;
46 /* There are a few simple rules, which allow for local port reuse by
47 * an application. In essence:
49 * 1) Sockets bound to different interfaces may share a local port.
50 * Failing that, goto test 2.
51 * 2) If all sockets have sk->sk_reuse set, and none of them are in
52 * TCP_LISTEN state, the port may be shared.
53 * Failing that, goto test 3.
54 * 3) If all sockets are bound to a specific inet_sk(sk)->rcv_saddr local
55 * address, and none of them are the same, the port may be
56 * shared.
57 * Failing this, the port cannot be shared.
59 * The interesting point, is test #2. This is what an FTP server does
60 * all day. To optimize this case we use a specific flag bit defined
61 * below. As we add sockets to a bind bucket list, we perform a
62 * check of: (newsk->sk_reuse && (newsk->sk_state != TCP_LISTEN))
63 * As long as all sockets added to a bind bucket pass this test,
64 * the flag bit will be set.
65 * The resulting situation is that tcp_v[46]_verify_bind() can just check
66 * for this flag bit, if it is set and the socket trying to bind has
67 * sk->sk_reuse set, we don't even have to walk the owners list at all,
68 * we return that it is ok to bind this socket to the requested local port.
70 * Sounds like a lot of work, but it is worth it. In a more naive
71 * implementation (ie. current FreeBSD etc.) the entire list of ports
72 * must be walked for each data port opened by an ftp server. Needless
73 * to say, this does not scale at all. With a couple thousand FTP
74 * users logged onto your box, isn't it nice to know that new data
75 * ports are created in O(1) time? I thought so. ;-) -DaveM
77 struct inet_bind_bucket {
78 unsigned short port;
79 signed short fastreuse;
80 struct hlist_node node;
81 struct hlist_head owners;
84 #define inet_bind_bucket_for_each(tb, node, head) \
85 hlist_for_each_entry(tb, node, head, node)
87 struct inet_bind_hashbucket {
88 spinlock_t lock;
89 struct hlist_head chain;
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. */
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:
99 * TCP_ESTABLISHED <= sk->sk_state < TCP_CLOSE
101 * First half of the table is for sockets not in TIME_WAIT, second half
102 * is for TIME_WAIT sockets only.
104 struct inet_ehash_bucket *ehash;
106 /* Ok, let's try this, I give up, we do need a local binding
107 * TCP hash as well as the others for fast bind/connect.
109 struct inet_bind_hashbucket *bhash;
111 int bhash_size;
112 unsigned int ehash_size;
114 /* All sockets in TCP_LISTEN state will be in here. This is the only
115 * table where wildcard'd TCP sockets can exist. Hash function here
116 * is just local port number.
118 struct hlist_head listening_hash[INET_LHTABLE_SIZE];
120 /* All the above members are written once at bootup and
121 * never written again _or_ are predominantly read-access.
123 * Now align to a new cache line as all the following members
124 * are often dirty.
126 rwlock_t lhash_lock ____cacheline_aligned;
127 atomic_t lhash_users;
128 wait_queue_head_t lhash_wait;
129 kmem_cache_t *bind_bucket_cachep;
132 static inline struct inet_ehash_bucket *inet_ehash_bucket(
133 struct inet_hashinfo *hashinfo,
134 unsigned int hash)
136 return &hashinfo->ehash[hash & (hashinfo->ehash_size - 1)];
139 extern struct inet_bind_bucket *
140 inet_bind_bucket_create(kmem_cache_t *cachep,
141 struct inet_bind_hashbucket *head,
142 const unsigned short snum);
143 extern void inet_bind_bucket_destroy(kmem_cache_t *cachep,
144 struct inet_bind_bucket *tb);
146 static inline int inet_bhashfn(const __u16 lport, const int bhash_size)
148 return lport & (bhash_size - 1);
151 extern void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
152 const unsigned short snum);
154 /* These can have wildcards, don't try too hard. */
155 static inline int inet_lhashfn(const unsigned short num)
157 return num & (INET_LHTABLE_SIZE - 1);
160 static inline int inet_sk_listen_hashfn(const struct sock *sk)
162 return inet_lhashfn(inet_sk(sk)->num);
165 /* Caller must disable local BH processing. */
166 static inline void __inet_inherit_port(struct inet_hashinfo *table,
167 struct sock *sk, struct sock *child)
169 const int bhash = inet_bhashfn(inet_sk(child)->num, table->bhash_size);
170 struct inet_bind_hashbucket *head = &table->bhash[bhash];
171 struct inet_bind_bucket *tb;
173 spin_lock(&head->lock);
174 tb = inet_csk(sk)->icsk_bind_hash;
175 sk_add_bind_node(child, &tb->owners);
176 inet_csk(child)->icsk_bind_hash = tb;
177 spin_unlock(&head->lock);
180 static inline void inet_inherit_port(struct inet_hashinfo *table,
181 struct sock *sk, struct sock *child)
183 local_bh_disable();
184 __inet_inherit_port(table, sk, child);
185 local_bh_enable();
188 extern void inet_put_port(struct inet_hashinfo *table, struct sock *sk);
190 extern void inet_listen_wlock(struct inet_hashinfo *hashinfo);
193 * - We may sleep inside this lock.
194 * - If sleeping is not required (or called from BH),
195 * use plain read_(un)lock(&inet_hashinfo.lhash_lock).
197 static inline void inet_listen_lock(struct inet_hashinfo *hashinfo)
199 /* read_lock synchronizes to candidates to writers */
200 read_lock(&hashinfo->lhash_lock);
201 atomic_inc(&hashinfo->lhash_users);
202 read_unlock(&hashinfo->lhash_lock);
205 static inline void inet_listen_unlock(struct inet_hashinfo *hashinfo)
207 if (atomic_dec_and_test(&hashinfo->lhash_users))
208 wake_up(&hashinfo->lhash_wait);
211 static inline void __inet_hash(struct inet_hashinfo *hashinfo,
212 struct sock *sk, const int listen_possible)
214 struct hlist_head *list;
215 rwlock_t *lock;
217 BUG_TRAP(sk_unhashed(sk));
218 if (listen_possible && sk->sk_state == TCP_LISTEN) {
219 list = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
220 lock = &hashinfo->lhash_lock;
221 inet_listen_wlock(hashinfo);
222 } else {
223 struct inet_ehash_bucket *head;
224 sk->sk_hash = inet_sk_ehashfn(sk);
225 head = inet_ehash_bucket(hashinfo, sk->sk_hash);
226 list = &head->chain;
227 lock = &head->lock;
228 write_lock(lock);
230 __sk_add_node(sk, list);
231 sock_prot_inc_use(sk->sk_prot);
232 write_unlock(lock);
233 if (listen_possible && sk->sk_state == TCP_LISTEN)
234 wake_up(&hashinfo->lhash_wait);
237 static inline void inet_hash(struct inet_hashinfo *hashinfo, struct sock *sk)
239 if (sk->sk_state != TCP_CLOSE) {
240 local_bh_disable();
241 __inet_hash(hashinfo, sk, 1);
242 local_bh_enable();
246 static inline void inet_unhash(struct inet_hashinfo *hashinfo, struct sock *sk)
248 rwlock_t *lock;
250 if (sk_unhashed(sk))
251 goto out;
253 if (sk->sk_state == TCP_LISTEN) {
254 local_bh_disable();
255 inet_listen_wlock(hashinfo);
256 lock = &hashinfo->lhash_lock;
257 } else {
258 lock = &inet_ehash_bucket(hashinfo, sk->sk_hash)->lock;
259 write_lock_bh(lock);
262 if (__sk_del_node_init(sk))
263 sock_prot_dec_use(sk->sk_prot);
264 write_unlock_bh(lock);
265 out:
266 if (sk->sk_state == TCP_LISTEN)
267 wake_up(&hashinfo->lhash_wait);
270 static inline int inet_iif(const struct sk_buff *skb)
272 return ((struct rtable *)skb->dst)->rt_iif;
275 extern struct sock *__inet_lookup_listener(const struct hlist_head *head,
276 const u32 daddr,
277 const unsigned short hnum,
278 const int dif);
280 /* Optimize the common listener case. */
281 static inline struct sock *
282 inet_lookup_listener(struct inet_hashinfo *hashinfo,
283 const u32 daddr,
284 const unsigned short hnum, const int dif)
286 struct sock *sk = NULL;
287 const struct hlist_head *head;
289 read_lock(&hashinfo->lhash_lock);
290 head = &hashinfo->listening_hash[inet_lhashfn(hnum)];
291 if (!hlist_empty(head)) {
292 const struct inet_sock *inet = inet_sk((sk = __sk_head(head)));
294 if (inet->num == hnum && !sk->sk_node.next &&
295 (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
296 (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
297 !sk->sk_bound_dev_if)
298 goto sherry_cache;
299 sk = __inet_lookup_listener(head, daddr, hnum, dif);
301 if (sk) {
302 sherry_cache:
303 sock_hold(sk);
305 read_unlock(&hashinfo->lhash_lock);
306 return sk;
309 /* Socket demux engine toys. */
310 #ifdef __BIG_ENDIAN
311 #define INET_COMBINED_PORTS(__sport, __dport) \
312 (((__u32)(__sport) << 16) | (__u32)(__dport))
313 #else /* __LITTLE_ENDIAN */
314 #define INET_COMBINED_PORTS(__sport, __dport) \
315 (((__u32)(__dport) << 16) | (__u32)(__sport))
316 #endif
318 #if (BITS_PER_LONG == 64)
319 #ifdef __BIG_ENDIAN
320 #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
321 const __u64 __name = (((__u64)(__saddr)) << 32) | ((__u64)(__daddr));
322 #else /* __LITTLE_ENDIAN */
323 #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
324 const __u64 __name = (((__u64)(__daddr)) << 32) | ((__u64)(__saddr));
325 #endif /* __BIG_ENDIAN */
326 #define INET_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
327 (((__sk)->sk_hash == (__hash)) && \
328 ((*((__u64 *)&(inet_sk(__sk)->daddr))) == (__cookie)) && \
329 ((*((__u32 *)&(inet_sk(__sk)->dport))) == (__ports)) && \
330 (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
331 #define INET_TW_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
332 (((__sk)->sk_hash == (__hash)) && \
333 ((*((__u64 *)&(inet_twsk(__sk)->tw_daddr))) == (__cookie)) && \
334 ((*((__u32 *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) && \
335 (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
336 #else /* 32-bit arch */
337 #define INET_ADDR_COOKIE(__name, __saddr, __daddr)
338 #define INET_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif) \
339 (((__sk)->sk_hash == (__hash)) && \
340 (inet_sk(__sk)->daddr == (__saddr)) && \
341 (inet_sk(__sk)->rcv_saddr == (__daddr)) && \
342 ((*((__u32 *)&(inet_sk(__sk)->dport))) == (__ports)) && \
343 (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
344 #define INET_TW_MATCH(__sk, __hash,__cookie, __saddr, __daddr, __ports, __dif) \
345 (((__sk)->sk_hash == (__hash)) && \
346 (inet_twsk(__sk)->tw_daddr == (__saddr)) && \
347 (inet_twsk(__sk)->tw_rcv_saddr == (__daddr)) && \
348 ((*((__u32 *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) && \
349 (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
350 #endif /* 64-bit arch */
353 * Sockets in TCP_CLOSE state are _always_ taken out of the hash, so we need
354 * not check it for lookups anymore, thanks Alexey. -DaveM
356 * Local BH must be disabled here.
358 static inline struct sock *
359 __inet_lookup_established(struct inet_hashinfo *hashinfo,
360 const u32 saddr, const u16 sport,
361 const u32 daddr, const u16 hnum,
362 const int dif)
364 INET_ADDR_COOKIE(acookie, saddr, daddr)
365 const __u32 ports = INET_COMBINED_PORTS(sport, hnum);
366 struct sock *sk;
367 const struct hlist_node *node;
368 /* Optimize here for direct hit, only listening connections can
369 * have wildcards anyways.
371 unsigned int hash = inet_ehashfn(daddr, hnum, saddr, sport);
372 struct inet_ehash_bucket *head = inet_ehash_bucket(hashinfo, hash);
374 prefetch(head->chain.first);
375 read_lock(&head->lock);
376 sk_for_each(sk, node, &head->chain) {
377 if (INET_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
378 goto hit; /* You sunk my battleship! */
381 /* Must check for a TIME_WAIT'er before going to listener hash. */
382 sk_for_each(sk, node, &(head + hashinfo->ehash_size)->chain) {
383 if (INET_TW_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
384 goto hit;
386 sk = NULL;
387 out:
388 read_unlock(&head->lock);
389 return sk;
390 hit:
391 sock_hold(sk);
392 goto out;
395 static inline struct sock *__inet_lookup(struct inet_hashinfo *hashinfo,
396 const u32 saddr, const u16 sport,
397 const u32 daddr, const u16 hnum,
398 const int dif)
400 struct sock *sk = __inet_lookup_established(hashinfo, saddr, sport, daddr,
401 hnum, dif);
402 return sk ? : inet_lookup_listener(hashinfo, daddr, hnum, dif);
405 static inline struct sock *inet_lookup(struct inet_hashinfo *hashinfo,
406 const u32 saddr, const u16 sport,
407 const u32 daddr, const u16 dport,
408 const int dif)
410 struct sock *sk;
412 local_bh_disable();
413 sk = __inet_lookup(hashinfo, saddr, sport, daddr, ntohs(dport), dif);
414 local_bh_enable();
416 return sk;
419 extern int inet_hash_connect(struct inet_timewait_death_row *death_row,
420 struct sock *sk);
421 #endif /* _INET_HASHTABLES_H */