home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 2006 November (DVD) / PCWELT_11_2006.ISO / casper / filesystem.squashfs / usr / src / linux-headers-2.6.17-6 / include / net / inet_hashtables.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-08-11  |  13.2 KB  |  421 lines
  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.  
  27. #include <net/inet_connection_sock.h>
  28. #include <net/inet_sock.h>
  29. #include <net/route.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.  * New scheme, half the table is for TIME_WAIT, the other half is
  38.  * for the rest.  I'll experiment with dynamic table growth later.
  39.  */
  40. struct inet_ehash_bucket {
  41.     rwlock_t      lock;
  42.     struct hlist_head chain;
  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.     unsigned short        port;
  78.     signed short        fastreuse;
  79.     struct hlist_node    node;
  80.     struct hlist_head    owners;
  81. };
  82.  
  83. #define inet_bind_bucket_for_each(tb, node, head) \
  84.     hlist_for_each_entry(tb, node, head, node)
  85.  
  86. struct inet_bind_hashbucket {
  87.     spinlock_t        lock;
  88.     struct hlist_head    chain;
  89. };
  90.  
  91. /* This is for listening sockets, thus all sockets which possess wildcards. */
  92. #define INET_LHTABLE_SIZE    32    /* Yes, really, this is all you need. */
  93.  
  94. struct inet_hashinfo {
  95.     /* This is for sockets with full identity only.  Sockets here will
  96.      * always be without wildcards and will have the following invariant:
  97.      *
  98.      *          TCP_ESTABLISHED <= sk->sk_state < TCP_CLOSE
  99.      *
  100.      * First half of the table is for sockets not in TIME_WAIT, second half
  101.      * is for TIME_WAIT sockets only.
  102.      */
  103.     struct inet_ehash_bucket    *ehash;
  104.  
  105.     /* Ok, let's try this, I give up, we do need a local binding
  106.      * TCP hash as well as the others for fast bind/connect.
  107.      */
  108.     struct inet_bind_hashbucket    *bhash;
  109.  
  110.     int                bhash_size;
  111.     unsigned int            ehash_size;
  112.  
  113.     /* All sockets in TCP_LISTEN state will be in here.  This is the only
  114.      * table where wildcard'd TCP sockets can exist.  Hash function here
  115.      * is just local port number.
  116.      */
  117.     struct hlist_head        listening_hash[INET_LHTABLE_SIZE];
  118.  
  119.     /* All the above members are written once at bootup and
  120.      * never written again _or_ are predominantly read-access.
  121.      *
  122.      * Now align to a new cache line as all the following members
  123.      * are often dirty.
  124.      */
  125.     rwlock_t            lhash_lock ____cacheline_aligned;
  126.     atomic_t            lhash_users;
  127.     wait_queue_head_t        lhash_wait;
  128.     kmem_cache_t            *bind_bucket_cachep;
  129. };
  130.  
  131. static inline struct inet_ehash_bucket *inet_ehash_bucket(
  132.     struct inet_hashinfo *hashinfo,
  133.     unsigned int hash)
  134. {
  135.     return &hashinfo->ehash[hash & (hashinfo->ehash_size - 1)];
  136. }
  137.  
  138. extern struct inet_bind_bucket *
  139.             inet_bind_bucket_create(kmem_cache_t *cachep,
  140.                         struct inet_bind_hashbucket *head,
  141.                         const unsigned short snum);
  142. extern void inet_bind_bucket_destroy(kmem_cache_t *cachep,
  143.                      struct inet_bind_bucket *tb);
  144.  
  145. static inline int inet_bhashfn(const __u16 lport, const int bhash_size)
  146. {
  147.     return lport & (bhash_size - 1);
  148. }
  149.  
  150. extern void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
  151.                const unsigned short snum);
  152.  
  153. /* These can have wildcards, don't try too hard. */
  154. static inline int inet_lhashfn(const unsigned short num)
  155. {
  156.     return num & (INET_LHTABLE_SIZE - 1);
  157. }
  158.  
  159. static inline int inet_sk_listen_hashfn(const struct sock *sk)
  160. {
  161.     return inet_lhashfn(inet_sk(sk)->num);
  162. }
  163.  
  164. /* Caller must disable local BH processing. */
  165. static inline void __inet_inherit_port(struct inet_hashinfo *table,
  166.                        struct sock *sk, struct sock *child)
  167. {
  168.     const int bhash = inet_bhashfn(inet_sk(child)->num, table->bhash_size);
  169.     struct inet_bind_hashbucket *head = &table->bhash[bhash];
  170.     struct inet_bind_bucket *tb;
  171.  
  172.     spin_lock(&head->lock);
  173.     tb = inet_csk(sk)->icsk_bind_hash;
  174.     sk_add_bind_node(child, &tb->owners);
  175.     inet_csk(child)->icsk_bind_hash = tb;
  176.     spin_unlock(&head->lock);
  177. }
  178.  
  179. static inline void inet_inherit_port(struct inet_hashinfo *table,
  180.                      struct sock *sk, struct sock *child)
  181. {
  182.     local_bh_disable();
  183.     __inet_inherit_port(table, sk, child);
  184.     local_bh_enable();
  185. }
  186.  
  187. extern void inet_put_port(struct inet_hashinfo *table, struct sock *sk);
  188.  
  189. extern void inet_listen_wlock(struct inet_hashinfo *hashinfo);
  190.  
  191. /*
  192.  * - We may sleep inside this lock.
  193.  * - If sleeping is not required (or called from BH),
  194.  *   use plain read_(un)lock(&inet_hashinfo.lhash_lock).
  195.  */
  196. static inline void inet_listen_lock(struct inet_hashinfo *hashinfo)
  197. {
  198.     /* read_lock synchronizes to candidates to writers */
  199.     read_lock(&hashinfo->lhash_lock);
  200.     atomic_inc(&hashinfo->lhash_users);
  201.     read_unlock(&hashinfo->lhash_lock);
  202. }
  203.  
  204. static inline void inet_listen_unlock(struct inet_hashinfo *hashinfo)
  205. {
  206.     if (atomic_dec_and_test(&hashinfo->lhash_users))
  207.         wake_up(&hashinfo->lhash_wait);
  208. }
  209.  
  210. static inline void __inet_hash(struct inet_hashinfo *hashinfo,
  211.                    struct sock *sk, const int listen_possible)
  212. {
  213.     struct hlist_head *list;
  214.     rwlock_t *lock;
  215.  
  216.     BUG_TRAP(sk_unhashed(sk));
  217.     if (listen_possible && sk->sk_state == TCP_LISTEN) {
  218.         list = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
  219.         lock = &hashinfo->lhash_lock;
  220.         inet_listen_wlock(hashinfo);
  221.     } else {
  222.         struct inet_ehash_bucket *head;
  223.         sk->sk_hash = inet_sk_ehashfn(sk);
  224.         head = inet_ehash_bucket(hashinfo, sk->sk_hash);
  225.         list = &head->chain;
  226.         lock = &head->lock;
  227.         write_lock(lock);
  228.     }
  229.     __sk_add_node(sk, list);
  230.     sock_prot_inc_use(sk->sk_prot);
  231.     write_unlock(lock);
  232.     if (listen_possible && sk->sk_state == TCP_LISTEN)
  233.         wake_up(&hashinfo->lhash_wait);
  234. }
  235.  
  236. static inline void inet_hash(struct inet_hashinfo *hashinfo, struct sock *sk)
  237. {
  238.     if (sk->sk_state != TCP_CLOSE) {
  239.         local_bh_disable();
  240.         __inet_hash(hashinfo, sk, 1);
  241.         local_bh_enable();
  242.     }
  243. }
  244.  
  245. static inline void inet_unhash(struct inet_hashinfo *hashinfo, struct sock *sk)
  246. {
  247.     rwlock_t *lock;
  248.  
  249.     if (sk_unhashed(sk))
  250.         goto out;
  251.  
  252.     if (sk->sk_state == TCP_LISTEN) {
  253.         local_bh_disable();
  254.         inet_listen_wlock(hashinfo);
  255.         lock = &hashinfo->lhash_lock;
  256.     } else {
  257.         lock = &inet_ehash_bucket(hashinfo, sk->sk_hash)->lock;
  258.         write_lock_bh(lock);
  259.     }
  260.  
  261.     if (__sk_del_node_init(sk))
  262.         sock_prot_dec_use(sk->sk_prot);
  263.     write_unlock_bh(lock);
  264. out:
  265.     if (sk->sk_state == TCP_LISTEN)
  266.         wake_up(&hashinfo->lhash_wait);
  267. }
  268.  
  269. static inline int inet_iif(const struct sk_buff *skb)
  270. {
  271.     return ((struct rtable *)skb->dst)->rt_iif;
  272. }
  273.  
  274. extern struct sock *__inet_lookup_listener(const struct hlist_head *head,
  275.                        const u32 daddr,
  276.                        const unsigned short hnum,
  277.                        const int dif);
  278.  
  279. /* Optimize the common listener case. */
  280. static inline struct sock *
  281.         inet_lookup_listener(struct inet_hashinfo *hashinfo,
  282.                      const u32 daddr,
  283.                      const unsigned short hnum, const int dif)
  284. {
  285.     struct sock *sk = NULL;
  286.     const struct hlist_head *head;
  287.  
  288.     read_lock(&hashinfo->lhash_lock);
  289.     head = &hashinfo->listening_hash[inet_lhashfn(hnum)];
  290.     if (!hlist_empty(head)) {
  291.         const struct inet_sock *inet = inet_sk((sk = __sk_head(head)));
  292.  
  293.         if (inet->num == hnum && !sk->sk_node.next &&
  294.             (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
  295.             (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
  296.             !sk->sk_bound_dev_if)
  297.             goto sherry_cache;
  298.         sk = __inet_lookup_listener(head, daddr, hnum, dif);
  299.     }
  300.     if (sk) {
  301. sherry_cache:
  302.         sock_hold(sk);
  303.     }
  304.     read_unlock(&hashinfo->lhash_lock);
  305.     return sk;
  306. }
  307.  
  308. /* Socket demux engine toys. */
  309. #ifdef __BIG_ENDIAN
  310. #define INET_COMBINED_PORTS(__sport, __dport) \
  311.     (((__u32)(__sport) << 16) | (__u32)(__dport))
  312. #else /* __LITTLE_ENDIAN */
  313. #define INET_COMBINED_PORTS(__sport, __dport) \
  314.     (((__u32)(__dport) << 16) | (__u32)(__sport))
  315. #endif
  316.  
  317. #if (BITS_PER_LONG == 64)
  318. #ifdef __BIG_ENDIAN
  319. #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
  320.     const __u64 __name = (((__u64)(__saddr)) << 32) | ((__u64)(__daddr));
  321. #else /* __LITTLE_ENDIAN */
  322. #define INET_ADDR_COOKIE(__name, __saddr, __daddr) \
  323.     const __u64 __name = (((__u64)(__daddr)) << 32) | ((__u64)(__saddr));
  324. #endif /* __BIG_ENDIAN */
  325. #define INET_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
  326.     (((__sk)->sk_hash == (__hash))                &&    \
  327.      ((*((__u64 *)&(inet_sk(__sk)->daddr))) == (__cookie))    &&    \
  328.      ((*((__u32 *)&(inet_sk(__sk)->dport))) == (__ports))    &&    \
  329.      (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
  330. #define INET_TW_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif)\
  331.     (((__sk)->sk_hash == (__hash))                &&    \
  332.      ((*((__u64 *)&(inet_twsk(__sk)->tw_daddr))) == (__cookie)) &&    \
  333.      ((*((__u32 *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) &&    \
  334.      (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
  335. #else /* 32-bit arch */
  336. #define INET_ADDR_COOKIE(__name, __saddr, __daddr)
  337. #define INET_MATCH(__sk, __hash, __cookie, __saddr, __daddr, __ports, __dif)    \
  338.     (((__sk)->sk_hash == (__hash))                &&    \
  339.      (inet_sk(__sk)->daddr        == (__saddr))        &&    \
  340.      (inet_sk(__sk)->rcv_saddr    == (__daddr))        &&    \
  341.      ((*((__u32 *)&(inet_sk(__sk)->dport))) == (__ports))    &&    \
  342.      (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
  343. #define INET_TW_MATCH(__sk, __hash,__cookie, __saddr, __daddr, __ports, __dif)    \
  344.     (((__sk)->sk_hash == (__hash))                &&    \
  345.      (inet_twsk(__sk)->tw_daddr    == (__saddr))        &&    \
  346.      (inet_twsk(__sk)->tw_rcv_saddr    == (__daddr))        &&    \
  347.      ((*((__u32 *)&(inet_twsk(__sk)->tw_dport))) == (__ports)) &&    \
  348.      (!((__sk)->sk_bound_dev_if) || ((__sk)->sk_bound_dev_if == (__dif))))
  349. #endif /* 64-bit arch */
  350.  
  351. /*
  352.  * Sockets in TCP_CLOSE state are _always_ taken out of the hash, so we need
  353.  * not check it for lookups anymore, thanks Alexey. -DaveM
  354.  *
  355.  * Local BH must be disabled here.
  356.  */
  357. static inline struct sock *
  358.     __inet_lookup_established(struct inet_hashinfo *hashinfo,
  359.                   const u32 saddr, const u16 sport,
  360.                   const u32 daddr, const u16 hnum,
  361.                   const int dif)
  362. {
  363.     INET_ADDR_COOKIE(acookie, saddr, daddr)
  364.     const __u32 ports = INET_COMBINED_PORTS(sport, hnum);
  365.     struct sock *sk;
  366.     const struct hlist_node *node;
  367.     /* Optimize here for direct hit, only listening connections can
  368.      * have wildcards anyways.
  369.      */
  370.     unsigned int hash = inet_ehashfn(daddr, hnum, saddr, sport);
  371.     struct inet_ehash_bucket *head = inet_ehash_bucket(hashinfo, hash);
  372.  
  373.     prefetch(head->chain.first);
  374.     read_lock(&head->lock);
  375.     sk_for_each(sk, node, &head->chain) {
  376.         if (INET_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
  377.             goto hit; /* You sunk my battleship! */
  378.     }
  379.  
  380.     /* Must check for a TIME_WAIT'er before going to listener hash. */
  381.     sk_for_each(sk, node, &(head + hashinfo->ehash_size)->chain) {
  382.         if (INET_TW_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
  383.             goto hit;
  384.     }
  385.     sk = NULL;
  386. out:
  387.     read_unlock(&head->lock);
  388.     return sk;
  389. hit:
  390.     sock_hold(sk);
  391.     goto out;
  392. }
  393.  
  394. static inline struct sock *__inet_lookup(struct inet_hashinfo *hashinfo,
  395.                      const u32 saddr, const u16 sport,
  396.                      const u32 daddr, const u16 hnum,
  397.                      const int dif)
  398. {
  399.     struct sock *sk = __inet_lookup_established(hashinfo, saddr, sport, daddr,
  400.                             hnum, dif);
  401.     return sk ? : inet_lookup_listener(hashinfo, daddr, hnum, dif);
  402. }
  403.  
  404. static inline struct sock *inet_lookup(struct inet_hashinfo *hashinfo,
  405.                        const u32 saddr, const u16 sport,
  406.                        const u32 daddr, const u16 dport,
  407.                        const int dif)
  408. {
  409.     struct sock *sk;
  410.  
  411.     local_bh_disable();
  412.     sk = __inet_lookup(hashinfo, saddr, sport, daddr, ntohs(dport), dif);
  413.     local_bh_enable();
  414.  
  415.     return sk;
  416. }
  417.  
  418. extern int inet_hash_connect(struct inet_timewait_death_row *death_row,
  419.                  struct sock *sk);
  420. #endif /* _INET_HASHTABLES_H */
  421.