Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 1 | /* |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 2 | * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net> |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 3 | * |
| 4 | * This program is free software; you can redistribute it and/or modify |
| 5 | * it under the terms of the GNU General Public License version 2 as |
| 6 | * published by the Free Software Foundation. |
| 7 | * |
| 8 | * Development of this code funded by Astaro AG (http://www.astaro.com/) |
| 9 | */ |
| 10 | |
| 11 | #include <linux/kernel.h> |
| 12 | #include <linux/init.h> |
| 13 | #include <linux/module.h> |
| 14 | #include <linux/list.h> |
| 15 | #include <linux/jhash.h> |
| 16 | #include <linux/netlink.h> |
| 17 | #include <linux/netfilter.h> |
| 18 | #include <linux/netfilter/nf_tables.h> |
| 19 | #include <net/netfilter/nf_tables.h> |
| 20 | |
| 21 | struct nft_hash { |
| 22 | struct hlist_head *hash; |
| 23 | unsigned int hsize; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 24 | }; |
| 25 | |
| 26 | struct nft_hash_elem { |
| 27 | struct hlist_node hnode; |
| 28 | struct nft_data key; |
| 29 | struct nft_data data[]; |
| 30 | }; |
| 31 | |
| 32 | static u32 nft_hash_rnd __read_mostly; |
| 33 | static bool nft_hash_rnd_initted __read_mostly; |
| 34 | |
| 35 | static unsigned int nft_hash_data(const struct nft_data *data, |
| 36 | unsigned int hsize, unsigned int len) |
| 37 | { |
| 38 | unsigned int h; |
| 39 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 40 | h = jhash(data->data, len, nft_hash_rnd); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 41 | return ((u64)h * hsize) >> 32; |
| 42 | } |
| 43 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 44 | static bool nft_hash_lookup(const struct nft_set *set, |
| 45 | const struct nft_data *key, |
| 46 | struct nft_data *data) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 47 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 48 | const struct nft_hash *priv = nft_set_priv(set); |
| 49 | const struct nft_hash_elem *he; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 50 | unsigned int h; |
| 51 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 52 | h = nft_hash_data(key, priv->hsize, set->klen); |
| 53 | hlist_for_each_entry(he, &priv->hash[h], hnode) { |
| 54 | if (nft_data_cmp(&he->key, key, set->klen)) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 55 | continue; |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 56 | if (set->flags & NFT_SET_MAP) |
| 57 | nft_data_copy(data, he->data); |
| 58 | return true; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 59 | } |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 60 | return false; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 61 | } |
| 62 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 63 | static void nft_hash_elem_destroy(const struct nft_set *set, |
| 64 | struct nft_hash_elem *he) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 65 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 66 | nft_data_uninit(&he->key, NFT_DATA_VALUE); |
| 67 | if (set->flags & NFT_SET_MAP) |
| 68 | nft_data_uninit(he->data, set->dtype); |
| 69 | kfree(he); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 70 | } |
| 71 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 72 | static int nft_hash_insert(const struct nft_set *set, |
| 73 | const struct nft_set_elem *elem) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 74 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 75 | struct nft_hash *priv = nft_set_priv(set); |
| 76 | struct nft_hash_elem *he; |
| 77 | unsigned int size, h; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 78 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 79 | if (elem->flags != 0) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 80 | return -EINVAL; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 81 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 82 | size = sizeof(*he); |
| 83 | if (set->flags & NFT_SET_MAP) |
| 84 | size += sizeof(he->data[0]); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 85 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 86 | he = kzalloc(size, GFP_KERNEL); |
| 87 | if (he == NULL) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 88 | return -ENOMEM; |
| 89 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 90 | nft_data_copy(&he->key, &elem->key); |
| 91 | if (set->flags & NFT_SET_MAP) |
| 92 | nft_data_copy(he->data, &elem->data); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 93 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 94 | h = nft_hash_data(&he->key, priv->hsize, set->klen); |
| 95 | hlist_add_head_rcu(&he->hnode, &priv->hash[h]); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 96 | return 0; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 97 | } |
| 98 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 99 | static void nft_hash_remove(const struct nft_set *set, |
| 100 | const struct nft_set_elem *elem) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 101 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 102 | struct nft_hash_elem *he = elem->cookie; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 103 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 104 | hlist_del_rcu(&he->hnode); |
| 105 | kfree(he); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 106 | } |
| 107 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 108 | static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 109 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 110 | const struct nft_hash *priv = nft_set_priv(set); |
| 111 | struct nft_hash_elem *he; |
| 112 | unsigned int h; |
| 113 | |
| 114 | h = nft_hash_data(&elem->key, priv->hsize, set->klen); |
| 115 | hlist_for_each_entry(he, &priv->hash[h], hnode) { |
| 116 | if (nft_data_cmp(&he->key, &elem->key, set->klen)) |
| 117 | continue; |
| 118 | |
| 119 | elem->cookie = he; |
| 120 | elem->flags = 0; |
| 121 | if (set->flags & NFT_SET_MAP) |
| 122 | nft_data_copy(&elem->data, he->data); |
| 123 | return 0; |
| 124 | } |
| 125 | return -ENOENT; |
| 126 | } |
| 127 | |
| 128 | static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, |
| 129 | struct nft_set_iter *iter) |
| 130 | { |
| 131 | const struct nft_hash *priv = nft_set_priv(set); |
| 132 | const struct nft_hash_elem *he; |
| 133 | struct nft_set_elem elem; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 134 | unsigned int i; |
| 135 | |
| 136 | for (i = 0; i < priv->hsize; i++) { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 137 | hlist_for_each_entry(he, &priv->hash[i], hnode) { |
| 138 | if (iter->count < iter->skip) |
| 139 | goto cont; |
| 140 | |
| 141 | memcpy(&elem.key, &he->key, sizeof(elem.key)); |
| 142 | if (set->flags & NFT_SET_MAP) |
| 143 | memcpy(&elem.data, he->data, sizeof(elem.data)); |
| 144 | elem.flags = 0; |
| 145 | |
| 146 | iter->err = iter->fn(ctx, set, iter, &elem); |
| 147 | if (iter->err < 0) |
| 148 | return; |
| 149 | cont: |
| 150 | iter->count++; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 151 | } |
| 152 | } |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 153 | } |
| 154 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 155 | static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) |
| 156 | { |
| 157 | return sizeof(struct nft_hash); |
| 158 | } |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 159 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 160 | static int nft_hash_init(const struct nft_set *set, |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 161 | const struct nlattr * const tb[]) |
| 162 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 163 | struct nft_hash *priv = nft_set_priv(set); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 164 | unsigned int cnt, i; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 165 | |
| 166 | if (unlikely(!nft_hash_rnd_initted)) { |
| 167 | get_random_bytes(&nft_hash_rnd, 4); |
| 168 | nft_hash_rnd_initted = true; |
| 169 | } |
| 170 | |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 171 | /* Aim for a load factor of 0.75 */ |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 172 | // FIXME: temporarily broken until we have set descriptions |
| 173 | cnt = 100; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 174 | cnt = cnt * 4 / 3; |
| 175 | |
| 176 | priv->hash = kcalloc(cnt, sizeof(struct hlist_head), GFP_KERNEL); |
| 177 | if (priv->hash == NULL) |
| 178 | return -ENOMEM; |
| 179 | priv->hsize = cnt; |
| 180 | |
| 181 | for (i = 0; i < cnt; i++) |
| 182 | INIT_HLIST_HEAD(&priv->hash[i]); |
| 183 | |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 184 | return 0; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 185 | } |
| 186 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 187 | static void nft_hash_destroy(const struct nft_set *set) |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 188 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 189 | const struct nft_hash *priv = nft_set_priv(set); |
| 190 | const struct hlist_node *next; |
| 191 | struct nft_hash_elem *elem; |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 192 | unsigned int i; |
| 193 | |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 194 | for (i = 0; i < priv->hsize; i++) { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 195 | hlist_for_each_entry_safe(elem, next, &priv->hash[i], hnode) { |
| 196 | hlist_del(&elem->hnode); |
| 197 | nft_hash_elem_destroy(set, elem); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 198 | } |
| 199 | } |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 200 | kfree(priv->hash); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 201 | } |
| 202 | |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 203 | static struct nft_set_ops nft_hash_ops __read_mostly = { |
| 204 | .privsize = nft_hash_privsize, |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 205 | .init = nft_hash_init, |
| 206 | .destroy = nft_hash_destroy, |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 207 | .get = nft_hash_get, |
| 208 | .insert = nft_hash_insert, |
| 209 | .remove = nft_hash_remove, |
| 210 | .lookup = nft_hash_lookup, |
| 211 | .walk = nft_hash_walk, |
| 212 | .features = NFT_SET_MAP, |
| 213 | .owner = THIS_MODULE, |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 214 | }; |
| 215 | |
| 216 | static int __init nft_hash_module_init(void) |
| 217 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 218 | return nft_register_set(&nft_hash_ops); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 219 | } |
| 220 | |
| 221 | static void __exit nft_hash_module_exit(void) |
| 222 | { |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 223 | nft_unregister_set(&nft_hash_ops); |
Patrick McHardy | 9651851 | 2013-10-14 11:00:02 +0200 | [diff] [blame] | 224 | } |
| 225 | |
| 226 | module_init(nft_hash_module_init); |
| 227 | module_exit(nft_hash_module_exit); |
| 228 | |
| 229 | MODULE_LICENSE("GPL"); |
| 230 | MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>"); |
Patrick McHardy | 20a6934 | 2013-10-11 12:06:22 +0200 | [diff] [blame^] | 231 | MODULE_ALIAS_NFT_SET(); |