1
2
3
4
5
6#include <linux/kernel.h>
7#include <linux/init.h>
8#include <linux/module.h>
9#include <linux/list.h>
10#include <linux/netlink.h>
11#include <linux/netfilter.h>
12#include <linux/netfilter/nf_tables.h>
13#include <net/netfilter/nf_tables_core.h>
14
15struct nft_bitmap_elem {
16 struct list_head head;
17 struct nft_set_ext ext;
18};
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45struct nft_bitmap {
46 struct list_head list;
47 u16 bitmap_size;
48 u8 bitmap[];
49};
50
51static inline void nft_bitmap_location(const struct nft_set *set,
52 const void *key,
53 u32 *idx, u32 *off)
54{
55 u32 k;
56
57 if (set->klen == 2)
58 k = *(u16 *)key;
59 else
60 k = *(u8 *)key;
61 k <<= 1;
62
63 *idx = k / BITS_PER_BYTE;
64 *off = k % BITS_PER_BYTE;
65}
66
67
68
69
70static inline bool
71nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
72{
73 return (bitmap[idx] & (0x3 << off)) & (genmask << off);
74}
75
76INDIRECT_CALLABLE_SCOPE
77bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
78 const u32 *key, const struct nft_set_ext **ext)
79{
80 const struct nft_bitmap *priv = nft_set_priv(set);
81 u8 genmask = nft_genmask_cur(net);
82 u32 idx, off;
83
84 nft_bitmap_location(set, key, &idx, &off);
85
86 return nft_bitmap_active(priv->bitmap, idx, off, genmask);
87}
88
89static struct nft_bitmap_elem *
90nft_bitmap_elem_find(const struct nft_set *set, struct nft_bitmap_elem *this,
91 u8 genmask)
92{
93 const struct nft_bitmap *priv = nft_set_priv(set);
94 struct nft_bitmap_elem *be;
95
96 list_for_each_entry_rcu(be, &priv->list, head) {
97 if (memcmp(nft_set_ext_key(&be->ext),
98 nft_set_ext_key(&this->ext), set->klen) ||
99 !nft_set_elem_active(&be->ext, genmask))
100 continue;
101
102 return be;
103 }
104 return NULL;
105}
106
107static void *nft_bitmap_get(const struct net *net, const struct nft_set *set,
108 const struct nft_set_elem *elem, unsigned int flags)
109{
110 const struct nft_bitmap *priv = nft_set_priv(set);
111 u8 genmask = nft_genmask_cur(net);
112 struct nft_bitmap_elem *be;
113
114 list_for_each_entry_rcu(be, &priv->list, head) {
115 if (memcmp(nft_set_ext_key(&be->ext), elem->key.val.data, set->klen) ||
116 !nft_set_elem_active(&be->ext, genmask))
117 continue;
118
119 return be;
120 }
121 return ERR_PTR(-ENOENT);
122}
123
124static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
125 const struct nft_set_elem *elem,
126 struct nft_set_ext **ext)
127{
128 struct nft_bitmap *priv = nft_set_priv(set);
129 struct nft_bitmap_elem *new = elem->priv, *be;
130 u8 genmask = nft_genmask_next(net);
131 u32 idx, off;
132
133 be = nft_bitmap_elem_find(set, new, genmask);
134 if (be) {
135 *ext = &be->ext;
136 return -EEXIST;
137 }
138
139 nft_bitmap_location(set, nft_set_ext_key(&new->ext), &idx, &off);
140
141 priv->bitmap[idx] |= (genmask << off);
142 list_add_tail_rcu(&new->head, &priv->list);
143
144 return 0;
145}
146
147static void nft_bitmap_remove(const struct net *net,
148 const struct nft_set *set,
149 const struct nft_set_elem *elem)
150{
151 struct nft_bitmap *priv = nft_set_priv(set);
152 struct nft_bitmap_elem *be = elem->priv;
153 u8 genmask = nft_genmask_next(net);
154 u32 idx, off;
155
156 nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
157
158 priv->bitmap[idx] &= ~(genmask << off);
159 list_del_rcu(&be->head);
160}
161
162static void nft_bitmap_activate(const struct net *net,
163 const struct nft_set *set,
164 const struct nft_set_elem *elem)
165{
166 struct nft_bitmap *priv = nft_set_priv(set);
167 struct nft_bitmap_elem *be = elem->priv;
168 u8 genmask = nft_genmask_next(net);
169 u32 idx, off;
170
171 nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
172
173 priv->bitmap[idx] |= (genmask << off);
174 nft_set_elem_change_active(net, set, &be->ext);
175}
176
177static bool nft_bitmap_flush(const struct net *net,
178 const struct nft_set *set, void *_be)
179{
180 struct nft_bitmap *priv = nft_set_priv(set);
181 u8 genmask = nft_genmask_next(net);
182 struct nft_bitmap_elem *be = _be;
183 u32 idx, off;
184
185 nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
186
187 priv->bitmap[idx] &= ~(genmask << off);
188 nft_set_elem_change_active(net, set, &be->ext);
189
190 return true;
191}
192
193static void *nft_bitmap_deactivate(const struct net *net,
194 const struct nft_set *set,
195 const struct nft_set_elem *elem)
196{
197 struct nft_bitmap *priv = nft_set_priv(set);
198 struct nft_bitmap_elem *this = elem->priv, *be;
199 u8 genmask = nft_genmask_next(net);
200 u32 idx, off;
201
202 nft_bitmap_location(set, elem->key.val.data, &idx, &off);
203
204 be = nft_bitmap_elem_find(set, this, genmask);
205 if (!be)
206 return NULL;
207
208
209 priv->bitmap[idx] &= ~(genmask << off);
210 nft_set_elem_change_active(net, set, &be->ext);
211
212 return be;
213}
214
215static void nft_bitmap_walk(const struct nft_ctx *ctx,
216 struct nft_set *set,
217 struct nft_set_iter *iter)
218{
219 const struct nft_bitmap *priv = nft_set_priv(set);
220 struct nft_bitmap_elem *be;
221 struct nft_set_elem elem;
222
223 list_for_each_entry_rcu(be, &priv->list, head) {
224 if (iter->count < iter->skip)
225 goto cont;
226 if (!nft_set_elem_active(&be->ext, iter->genmask))
227 goto cont;
228
229 elem.priv = be;
230
231 iter->err = iter->fn(ctx, set, iter, &elem);
232
233 if (iter->err < 0)
234 return;
235cont:
236 iter->count++;
237 }
238}
239
240
241
242
243
244static inline u32 nft_bitmap_size(u32 klen)
245{
246 return ((2 << ((klen * BITS_PER_BYTE) - 1)) / BITS_PER_BYTE) << 1;
247}
248
249static inline u64 nft_bitmap_total_size(u32 klen)
250{
251 return sizeof(struct nft_bitmap) + nft_bitmap_size(klen);
252}
253
254static u64 nft_bitmap_privsize(const struct nlattr * const nla[],
255 const struct nft_set_desc *desc)
256{
257 u32 klen = ntohl(nla_get_be32(nla[NFTA_SET_KEY_LEN]));
258
259 return nft_bitmap_total_size(klen);
260}
261
262static int nft_bitmap_init(const struct nft_set *set,
263 const struct nft_set_desc *desc,
264 const struct nlattr * const nla[])
265{
266 struct nft_bitmap *priv = nft_set_priv(set);
267
268 INIT_LIST_HEAD(&priv->list);
269 priv->bitmap_size = nft_bitmap_size(set->klen);
270
271 return 0;
272}
273
274static void nft_bitmap_destroy(const struct nft_set *set)
275{
276 struct nft_bitmap *priv = nft_set_priv(set);
277 struct nft_bitmap_elem *be, *n;
278
279 list_for_each_entry_safe(be, n, &priv->list, head)
280 nft_set_elem_destroy(set, be, true);
281}
282
283static bool nft_bitmap_estimate(const struct nft_set_desc *desc, u32 features,
284 struct nft_set_estimate *est)
285{
286
287 if (desc->klen > 2)
288 return false;
289 else if (desc->expr)
290 return false;
291
292 est->size = nft_bitmap_total_size(desc->klen);
293 est->lookup = NFT_SET_CLASS_O_1;
294 est->space = NFT_SET_CLASS_O_1;
295
296 return true;
297}
298
299const struct nft_set_type nft_set_bitmap_type = {
300 .ops = {
301 .privsize = nft_bitmap_privsize,
302 .elemsize = offsetof(struct nft_bitmap_elem, ext),
303 .estimate = nft_bitmap_estimate,
304 .init = nft_bitmap_init,
305 .destroy = nft_bitmap_destroy,
306 .insert = nft_bitmap_insert,
307 .remove = nft_bitmap_remove,
308 .deactivate = nft_bitmap_deactivate,
309 .flush = nft_bitmap_flush,
310 .activate = nft_bitmap_activate,
311 .lookup = nft_bitmap_lookup,
312 .walk = nft_bitmap_walk,
313 .get = nft_bitmap_get,
314 },
315};
316