[NETFILTER]: nf_conntrack: use hashtable for expectations
[deliverable/linux.git] / net / netfilter / nf_conntrack_expect.c
index 4130ea662c48f33415ffe57bde5bb900848458e6..0696f87aaef12c8987c0825d4685434265b4ada2 100644 (file)
@@ -19,6 +19,7 @@
 #include <linux/err.h>
 #include <linux/percpu.h>
 #include <linux/kernel.h>
+#include <linux/jhash.h>
 
 #include <net/netfilter/nf_conntrack.h>
 #include <net/netfilter/nf_conntrack_core.h>
 LIST_HEAD(nf_ct_expect_list);
 EXPORT_SYMBOL_GPL(nf_ct_expect_list);
 
-struct kmem_cache *nf_ct_expect_cachep __read_mostly;
+struct hlist_head *nf_ct_expect_hash __read_mostly;
+EXPORT_SYMBOL_GPL(nf_ct_expect_hash);
+
+unsigned int nf_ct_expect_hsize __read_mostly;
+EXPORT_SYMBOL_GPL(nf_ct_expect_hsize);
+
+static unsigned int nf_ct_expect_hash_rnd __read_mostly;
+static unsigned int nf_ct_expect_count;
+static int nf_ct_expect_hash_rnd_initted __read_mostly;
+static int nf_ct_expect_vmalloc;
+
+static struct kmem_cache *nf_ct_expect_cachep __read_mostly;
 static unsigned int nf_ct_expect_next_id;
 
 /* nf_conntrack_expect helper functions */
@@ -41,6 +53,9 @@ void nf_ct_unlink_expect(struct nf_conntrack_expect *exp)
        NF_CT_ASSERT(!timer_pending(&exp->timeout));
 
        list_del(&exp->list);
+       hlist_del(&exp->hnode);
+       nf_ct_expect_count--;
+
        NF_CT_STAT_INC(expect_delete);
        master_help->expecting--;
        nf_ct_expect_put(exp);
@@ -57,12 +72,31 @@ static void nf_ct_expectation_timed_out(unsigned long ul_expect)
        nf_ct_expect_put(exp);
 }
 
+static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple)
+{
+       if (unlikely(!nf_ct_expect_hash_rnd_initted)) {
+               get_random_bytes(&nf_ct_expect_hash_rnd, 4);
+               nf_ct_expect_hash_rnd_initted = 1;
+       }
+
+       return jhash2(tuple->dst.u3.all, ARRAY_SIZE(tuple->dst.u3.all),
+                     (((tuple->dst.protonum ^ tuple->src.l3num) << 16) |
+                      tuple->dst.u.all) ^ nf_ct_expect_hash_rnd) %
+              nf_ct_expect_hsize;
+}
+
 struct nf_conntrack_expect *
 __nf_ct_expect_find(const struct nf_conntrack_tuple *tuple)
 {
        struct nf_conntrack_expect *i;
+       struct hlist_node *n;
+       unsigned int h;
+
+       if (!nf_ct_expect_count)
+               return NULL;
 
-       list_for_each_entry(i, &nf_ct_expect_list, list) {
+       h = nf_ct_expect_dst_hash(tuple);
+       hlist_for_each_entry(i, n, &nf_ct_expect_hash[h], hnode) {
                if (nf_ct_tuple_mask_cmp(tuple, &i->tuple, &i->mask))
                        return i;
        }
@@ -141,25 +175,16 @@ static inline int expect_clash(const struct nf_conntrack_expect *a,
 {
        /* Part covered by intersection of masks must be unequal,
           otherwise they clash */
-       struct nf_conntrack_tuple intersect_mask;
+       struct nf_conntrack_tuple_mask intersect_mask;
        int count;
 
-       intersect_mask.src.l3num = a->mask.src.l3num & b->mask.src.l3num;
        intersect_mask.src.u.all = a->mask.src.u.all & b->mask.src.u.all;
-       intersect_mask.dst.u.all = a->mask.dst.u.all & b->mask.dst.u.all;
-       intersect_mask.dst.protonum = a->mask.dst.protonum
-                                       & b->mask.dst.protonum;
 
        for (count = 0; count < NF_CT_TUPLE_L3SIZE; count++){
                intersect_mask.src.u3.all[count] =
                        a->mask.src.u3.all[count] & b->mask.src.u3.all[count];
        }
 
-       for (count = 0; count < NF_CT_TUPLE_L3SIZE; count++){
-               intersect_mask.dst.u3.all[count] =
-                       a->mask.dst.u3.all[count] & b->mask.dst.u3.all[count];
-       }
-
        return nf_ct_tuple_mask_cmp(&a->tuple, &b->tuple, &intersect_mask);
 }
 
@@ -168,23 +193,16 @@ static inline int expect_matches(const struct nf_conntrack_expect *a,
 {
        return a->master == b->master
                && nf_ct_tuple_equal(&a->tuple, &b->tuple)
-               && nf_ct_tuple_equal(&a->mask, &b->mask);
+               && nf_ct_tuple_mask_equal(&a->mask, &b->mask);
 }
 
 /* Generally a bad idea to call this: could have matched already. */
 void nf_ct_unexpect_related(struct nf_conntrack_expect *exp)
 {
-       struct nf_conntrack_expect *i;
-
        write_lock_bh(&nf_conntrack_lock);
-       /* choose the oldest expectation to evict */
-       list_for_each_entry_reverse(i, &nf_ct_expect_list, list) {
-               if (expect_matches(i, exp) && del_timer(&i->timeout)) {
-                       nf_ct_unlink_expect(i);
-                       write_unlock_bh(&nf_conntrack_lock);
-                       nf_ct_expect_put(i);
-                       return;
-               }
+       if (del_timer(&exp->timeout)) {
+               nf_ct_unlink_expect(exp);
+               nf_ct_expect_put(exp);
        }
        write_unlock_bh(&nf_conntrack_lock);
 }
@@ -224,8 +242,6 @@ void nf_ct_expect_init(struct nf_conntrack_expect *exp, int family,
        exp->helper = NULL;
        exp->tuple.src.l3num = family;
        exp->tuple.dst.protonum = proto;
-       exp->mask.src.l3num = 0xFFFF;
-       exp->mask.dst.protonum = 0xFF;
 
        if (saddr) {
                memcpy(&exp->tuple.src.u3, saddr, len);
@@ -242,21 +258,6 @@ void nf_ct_expect_init(struct nf_conntrack_expect *exp, int family,
                memset(&exp->mask.src.u3, 0x00, sizeof(exp->mask.src.u3));
        }
 
-       if (daddr) {
-               memcpy(&exp->tuple.dst.u3, daddr, len);
-               if (sizeof(exp->tuple.dst.u3) > len)
-                       /* address needs to be cleared for nf_ct_tuple_equal */
-                       memset((void *)&exp->tuple.dst.u3 + len, 0x00,
-                              sizeof(exp->tuple.dst.u3) - len);
-               memset(&exp->mask.dst.u3, 0xFF, len);
-               if (sizeof(exp->mask.dst.u3) > len)
-                       memset((void *)&exp->mask.dst.u3 + len, 0x00,
-                              sizeof(exp->mask.dst.u3) - len);
-       } else {
-               memset(&exp->tuple.dst.u3, 0x00, sizeof(exp->tuple.dst.u3));
-               memset(&exp->mask.dst.u3, 0x00, sizeof(exp->mask.dst.u3));
-       }
-
        if (src) {
                exp->tuple.src.u.all = (__force u16)*src;
                exp->mask.src.u.all = 0xFFFF;
@@ -265,13 +266,13 @@ void nf_ct_expect_init(struct nf_conntrack_expect *exp, int family,
                exp->mask.src.u.all = 0;
        }
 
-       if (dst) {
-               exp->tuple.dst.u.all = (__force u16)*dst;
-               exp->mask.dst.u.all = 0xFFFF;
-       } else {
-               exp->tuple.dst.u.all = 0;
-               exp->mask.dst.u.all = 0;
-       }
+       memcpy(&exp->tuple.dst.u3, daddr, len);
+       if (sizeof(exp->tuple.dst.u3) > len)
+               /* address needs to be cleared for nf_ct_tuple_equal */
+               memset((void *)&exp->tuple.dst.u3 + len, 0x00,
+                      sizeof(exp->tuple.dst.u3) - len);
+
+       exp->tuple.dst.u.all = (__force u16)*dst;
 }
 EXPORT_SYMBOL_GPL(nf_ct_expect_init);
 
@@ -285,10 +286,14 @@ EXPORT_SYMBOL_GPL(nf_ct_expect_put);
 static void nf_ct_expect_insert(struct nf_conntrack_expect *exp)
 {
        struct nf_conn_help *master_help = nfct_help(exp->master);
+       unsigned int h = nf_ct_expect_dst_hash(&exp->tuple);
 
        atomic_inc(&exp->use);
        master_help->expecting++;
+
        list_add(&exp->list, &nf_ct_expect_list);
+       hlist_add_head(&exp->hnode, &nf_ct_expect_hash[h]);
+       nf_ct_expect_count++;
 
        setup_timer(&exp->timeout, nf_ct_expectation_timed_out,
                    (unsigned long)exp);
@@ -333,6 +338,8 @@ int nf_ct_expect_related(struct nf_conntrack_expect *expect)
        struct nf_conntrack_expect *i;
        struct nf_conn *master = expect->master;
        struct nf_conn_help *master_help = nfct_help(master);
+       struct hlist_node *n;
+       unsigned int h;
        int ret;
 
        NF_CT_ASSERT(master_help);
@@ -342,7 +349,8 @@ int nf_ct_expect_related(struct nf_conntrack_expect *expect)
                ret = -ESHUTDOWN;
                goto out;
        }
-       list_for_each_entry(i, &nf_ct_expect_list, list) {
+       h = nf_ct_expect_dst_hash(&expect->tuple);
+       hlist_for_each_entry(i, n, &nf_ct_expect_hash[h], hnode) {
                if (expect_matches(i, expect)) {
                        /* Refresh timer: if it's dying, ignore.. */
                        if (refresh_timer(i)) {
@@ -446,3 +454,68 @@ const struct file_operations exp_file_ops = {
        .release = seq_release
 };
 #endif /* CONFIG_PROC_FS */
+
+static int __init exp_proc_init(void)
+{
+#ifdef CONFIG_PROC_FS
+       struct proc_dir_entry *proc;
+
+       proc = proc_net_fops_create("nf_conntrack_expect", 0440, &exp_file_ops);
+       if (!proc)
+               return -ENOMEM;
+#endif /* CONFIG_PROC_FS */
+       return 0;
+}
+
+static void exp_proc_remove(void)
+{
+#ifdef CONFIG_PROC_FS
+       proc_net_remove("nf_conntrack_expect");
+#endif /* CONFIG_PROC_FS */
+}
+
+module_param_named(expect_hashsize, nf_ct_expect_hsize, uint, 0600);
+
+int __init nf_conntrack_expect_init(void)
+{
+       int err = -ENOMEM;
+
+       if (!nf_ct_expect_hsize) {
+               nf_ct_expect_hsize = nf_conntrack_htable_size / 256;
+               if (!nf_ct_expect_hsize)
+                       nf_ct_expect_hsize = 1;
+       }
+
+       nf_ct_expect_hash = nf_ct_alloc_hashtable(&nf_ct_expect_hsize,
+                                                 &nf_ct_expect_vmalloc);
+       if (nf_ct_expect_hash == NULL)
+               goto err1;
+
+       nf_ct_expect_cachep = kmem_cache_create("nf_conntrack_expect",
+                                       sizeof(struct nf_conntrack_expect),
+                                       0, 0, NULL, NULL);
+       if (!nf_ct_expect_cachep)
+               goto err2;
+
+       err = exp_proc_init();
+       if (err < 0)
+               goto err3;
+
+       return 0;
+
+err3:
+       nf_ct_free_hashtable(nf_ct_expect_hash, nf_ct_expect_vmalloc,
+                            nf_ct_expect_hsize);
+err2:
+       kmem_cache_destroy(nf_ct_expect_cachep);
+err1:
+       return err;
+}
+
+void nf_conntrack_expect_fini(void)
+{
+       exp_proc_remove();
+       kmem_cache_destroy(nf_ct_expect_cachep);
+       nf_ct_free_hashtable(nf_ct_expect_hash, nf_ct_expect_vmalloc,
+                            nf_ct_expect_hsize);
+}
This page took 0.029283 seconds and 5 git commands to generate.