#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>
#include <net/netfilter/nf_conntrack_helper.h>
#include <net/netfilter/nf_conntrack_tuple.h>
-LIST_HEAD(nf_ct_expect_list);
-EXPORT_SYMBOL_GPL(nf_ct_expect_list);
+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;
+unsigned int nf_ct_expect_max __read_mostly;
+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_CT_ASSERT(master_help);
NF_CT_ASSERT(!timer_pending(&exp->timeout));
- list_del(&exp->list);
- NF_CT_STAT_INC(expect_delete);
+ hlist_del(&exp->hnode);
+ nf_ct_expect_count--;
+
+ hlist_del(&exp->lnode);
master_help->expecting--;
nf_ct_expect_put(exp);
+
+ NF_CT_STAT_INC(expect_delete);
}
EXPORT_SYMBOL_GPL(nf_ct_unlink_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;
- list_for_each_entry(i, &nf_ct_expect_list, list) {
+ if (!nf_ct_expect_count)
+ return NULL;
+
+ 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;
}
/* delete all expectations for this conntrack */
void nf_ct_remove_expectations(struct nf_conn *ct)
{
- struct nf_conntrack_expect *i, *tmp;
struct nf_conn_help *help = nfct_help(ct);
+ struct nf_conntrack_expect *exp;
+ struct hlist_node *n, *next;
/* Optimization: most connection never expect any others. */
if (!help || help->expecting == 0)
return;
- list_for_each_entry_safe(i, tmp, &nf_ct_expect_list, list) {
- if (i->master == ct && del_timer(&i->timeout)) {
- nf_ct_unlink_expect(i);
- nf_ct_expect_put(i);
+ hlist_for_each_entry_safe(exp, n, next, &help->expectations, lnode) {
+ if (del_timer(&exp->timeout)) {
+ nf_ct_unlink_expect(exp);
+ nf_ct_expect_put(exp);
}
}
}
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);
+
+ hlist_add_head(&exp->lnode, &master_help->expectations);
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);
/* Race with expectations being used means we could have none to find; OK. */
static void evict_oldest_expect(struct nf_conn *master)
{
- struct nf_conntrack_expect *i;
+ struct nf_conn_help *master_help = nfct_help(master);
+ struct nf_conntrack_expect *exp = NULL;
+ struct hlist_node *n;
- list_for_each_entry_reverse(i, &nf_ct_expect_list, list) {
- if (i->master == master) {
- if (del_timer(&i->timeout)) {
- nf_ct_unlink_expect(i);
- nf_ct_expect_put(i);
- }
- break;
- }
+ hlist_for_each_entry(exp, n, &master_help->expectations, lnode)
+ ; /* nothing */
+
+ if (exp && del_timer(&exp->timeout)) {
+ nf_ct_unlink_expect(exp);
+ nf_ct_expect_put(exp);
}
}
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);
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)) {
master_help->expecting >= master_help->helper->max_expected)
evict_oldest_expect(master);
+ if (nf_ct_expect_count >= nf_ct_expect_max) {
+ if (net_ratelimit())
+ printk(KERN_WARNING
+ "nf_conntrack: expectation table full");
+ ret = -EMFILE;
+ goto out;
+ }
+
nf_ct_expect_insert(expect);
nf_ct_expect_event(IPEXP_NEW, expect);
ret = 0;
EXPORT_SYMBOL_GPL(nf_ct_expect_related);
#ifdef CONFIG_PROC_FS
-static void *exp_seq_start(struct seq_file *s, loff_t *pos)
+struct ct_expect_iter_state {
+ unsigned int bucket;
+};
+
+static struct hlist_node *ct_expect_get_first(struct seq_file *seq)
{
- struct list_head *e = &nf_ct_expect_list;
- loff_t i;
+ struct ct_expect_iter_state *st = seq->private;
- /* strange seq_file api calls stop even if we fail,
- * thus we need to grab lock since stop unlocks */
- read_lock_bh(&nf_conntrack_lock);
+ for (st->bucket = 0; st->bucket < nf_ct_expect_hsize; st->bucket++) {
+ if (!hlist_empty(&nf_ct_expect_hash[st->bucket]))
+ return nf_ct_expect_hash[st->bucket].first;
+ }
+ return NULL;
+}
- if (list_empty(e))
- return NULL;
+static struct hlist_node *ct_expect_get_next(struct seq_file *seq,
+ struct hlist_node *head)
+{
+ struct ct_expect_iter_state *st = seq->private;
- for (i = 0; i <= *pos; i++) {
- e = e->next;
- if (e == &nf_ct_expect_list)
+ head = head->next;
+ while (head == NULL) {
+ if (++st->bucket >= nf_ct_expect_hsize)
return NULL;
+ head = nf_ct_expect_hash[st->bucket].first;
}
- return e;
+ return head;
}
-static void *exp_seq_next(struct seq_file *s, void *v, loff_t *pos)
+static struct hlist_node *ct_expect_get_idx(struct seq_file *seq, loff_t pos)
{
- struct list_head *e = v;
+ struct hlist_node *head = ct_expect_get_first(seq);
- ++*pos;
- e = e->next;
+ if (head)
+ while (pos && (head = ct_expect_get_next(seq, head)))
+ pos--;
+ return pos ? NULL : head;
+}
- if (e == &nf_ct_expect_list)
- return NULL;
+static void *exp_seq_start(struct seq_file *seq, loff_t *pos)
+{
+ read_lock_bh(&nf_conntrack_lock);
+ return ct_expect_get_idx(seq, *pos);
+}
- return e;
+static void *exp_seq_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+ (*pos)++;
+ return ct_expect_get_next(seq, v);
}
-static void exp_seq_stop(struct seq_file *s, void *v)
+static void exp_seq_stop(struct seq_file *seq, void *v)
{
read_unlock_bh(&nf_conntrack_lock);
}
static int exp_seq_show(struct seq_file *s, void *v)
{
- struct nf_conntrack_expect *expect = v;
+ struct nf_conntrack_expect *expect;
+ struct hlist_node *n = v;
+
+ expect = hlist_entry(n, struct nf_conntrack_expect, hnode);
if (expect->timeout.function)
seq_printf(s, "%ld ", timer_pending(&expect->timeout)
return seq_putc(s, '\n');
}
-static struct seq_operations exp_seq_ops = {
+static const struct seq_operations exp_seq_ops = {
.start = exp_seq_start,
.next = exp_seq_next,
.stop = exp_seq_stop,
static int exp_open(struct inode *inode, struct file *file)
{
- return seq_open(file, &exp_seq_ops);
+ struct seq_file *seq;
+ struct ct_expect_iter_state *st;
+ int ret;
+
+ st = kmalloc(sizeof(struct ct_expect_iter_state), GFP_KERNEL);
+ if (st == NULL)
+ return -ENOMEM;
+ ret = seq_open(file, &exp_seq_ops);
+ if (ret)
+ goto out_free;
+ seq = file->private_data;
+ seq->private = st;
+ memset(st, 0, sizeof(struct ct_expect_iter_state));
+ return ret;
+out_free:
+ kfree(st);
+ return ret;
}
-const struct file_operations exp_file_ops = {
+static const struct file_operations exp_file_ops = {
.owner = THIS_MODULE,
.open = exp_open,
.read = seq_read,
.llseek = seq_lseek,
- .release = seq_release
+ .release = seq_release_private,
};
#endif /* CONFIG_PROC_FS */
#endif /* CONFIG_PROC_FS */
}
+module_param_named(expect_hashsize, nf_ct_expect_hsize, uint, 0600);
+
int __init nf_conntrack_expect_init(void)
{
- int err;
+ 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_max = nf_ct_expect_hsize * 4;
+
+ 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);
+ 0, 0, NULL);
if (!nf_ct_expect_cachep)
- return -ENOMEM;
+ goto err2;
err = exp_proc_init();
if (err < 0)
- goto err1;
+ goto err3;
return 0;
-err1:
+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;
}
{
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);
}