net/netfilter/nft_set_bitmap.c

   1 /*
   2  * Copyright (c) 2017 Pablo Neira Ayuso <pablo@netfilter.org>
   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
   9 #include <linux/kernel.h>
  10 #include <linux/init.h>
  11 #include <linux/module.h>
  12 #include <linux/list.h>
  13 #include <linux/netlink.h>
  14 #include <linux/netfilter.h>
  15 #include <linux/netfilter/nf_tables.h>
  16 #include <net/netfilter/nf_tables.h>
  17
  18 /* This bitmap uses two bits to represent one element. These two bits determine
  19  * the element state in the current and the future generation.
  20  *
  21  * An element can be in three states. The generation cursor is represented using
  22  * the ^ character, note that this cursor shifts on every succesful transaction.
  23  * If no transaction is going on, we observe all elements are in the following
  24  * state:
  25  *
  26  * 11 = this element is active in the current generation. In case of no updates,
  27  * ^    it stays active in the next generation.
  28  * 00 = this element is inactive in the current generation. In case of no
  29  * ^    updates, it stays inactive in the next generation.
  30  *
  31  * On transaction handling, we observe these two temporary states:
  32  *
  33  * 01 = this element is inactive in the current generation and it becomes active
  34  * ^    in the next one. This happens when the element is inserted but commit
  35  *      path has not yet been executed yet, so activation is still pending. On
  36  *      transaction abortion, the element is removed.
  37  * 10 = this element is active in the current generation and it becomes inactive
  38  * ^    in the next one. This happens when the element is deactivated but commit
  39  *      path has not yet been executed yet, so removal is still pending. On
  40  *      transation abortion, the next generation bit is reset to go back to
  41  *      restore its previous state.
  42  */
  43 struct nft_bitmap {
  44         u16     bitmap_size;
  45         u8      bitmap[];
  46 };
  47
  48 static inline void nft_bitmap_location(u32 key, u32 *idx, u32 *off)
  49 {
  50         u32 k = (key << 1);
  51
  52         *idx = k / BITS_PER_BYTE;
  53         *off = k % BITS_PER_BYTE;
  54 }
  55
  56 /* Fetch the two bits that represent the element and check if it is active based
  57  * on the generation mask.
  58  */
  59 static inline bool
  60 nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
  61 {
  62         return (bitmap[idx] & (0x3 << off)) & (genmask << off);
  63 }
  64
  65 static bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
  66                               const u32 *key, const struct nft_set_ext **ext)
  67 {
  68         const struct nft_bitmap *priv = nft_set_priv(set);
  69         u8 genmask = nft_genmask_cur(net);
  70         u32 idx, off;
  71
  72         nft_bitmap_location(*key, &idx, &off);
  73
  74         return nft_bitmap_active(priv->bitmap, idx, off, genmask);
  75 }
  76
  77 static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
  78                              const struct nft_set_elem *elem,
  79                              struct nft_set_ext **_ext)
  80 {
  81         struct nft_bitmap *priv = nft_set_priv(set);
  82         struct nft_set_ext *ext = elem->priv;
  83         u8 genmask = nft_genmask_next(net);
  84         u32 idx, off;
  85
  86         nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
  87         if (nft_bitmap_active(priv->bitmap, idx, off, genmask))
  88                 return -EEXIST;
  89
  90         /* Enter 01 state. */
  91         priv->bitmap[idx] |= (genmask << off);
  92
  93         return 0;
  94 }
  95
  96 static void nft_bitmap_remove(const struct net *net,
  97                               const struct nft_set *set,
  98                               const struct nft_set_elem *elem)
  99 {
 100         struct nft_bitmap *priv = nft_set_priv(set);
 101         struct nft_set_ext *ext = elem->priv;
 102         u8 genmask = nft_genmask_next(net);
 103         u32 idx, off;
 104
 105         nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
 106         /* Enter 00 state. */
 107         priv->bitmap[idx] &= ~(genmask << off);
 108 }
 109
 110 static void nft_bitmap_activate(const struct net *net,
 111                                 const struct nft_set *set,
 112                                 const struct nft_set_elem *elem)
 113 {
 114         struct nft_bitmap *priv = nft_set_priv(set);
 115         struct nft_set_ext *ext = elem->priv;
 116         u8 genmask = nft_genmask_next(net);
 117         u32 idx, off;
 118
 119         nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
 120         /* Enter 11 state. */
 121         priv->bitmap[idx] |= (genmask << off);
 122 }
 123
 124 static bool nft_bitmap_flush(const struct net *net,
 125                              const struct nft_set *set, void *ext)
 126 {
 127         struct nft_bitmap *priv = nft_set_priv(set);
 128         u8 genmask = nft_genmask_next(net);
 129         u32 idx, off;
 130
 131         nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
 132         /* Enter 10 state, similar to deactivation. */
 133         priv->bitmap[idx] &= ~(genmask << off);
 134
 135         return true;
 136 }
 137
 138 static struct nft_set_ext *nft_bitmap_ext_alloc(const struct nft_set *set,
 139                                                 const struct nft_set_elem *elem)
 140 {
 141         struct nft_set_ext_tmpl tmpl;
 142         struct nft_set_ext *ext;
 143
 144         nft_set_ext_prepare(&tmpl);
 145         nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, set->klen);
 146
 147         ext = kzalloc(tmpl.len, GFP_KERNEL);
 148         if (!ext)
 149                 return NULL;
 150
 151         nft_set_ext_init(ext, &tmpl);
 152         memcpy(nft_set_ext_key(ext), elem->key.val.data, set->klen);
 153
 154         return ext;
 155 }
 156
 157 static void *nft_bitmap_deactivate(const struct net *net,
 158                                    const struct nft_set *set,
 159                                    const struct nft_set_elem *elem)
 160 {
 161         struct nft_bitmap *priv = nft_set_priv(set);
 162         u8 genmask = nft_genmask_next(net);
 163         struct nft_set_ext *ext;
 164         u32 idx, off, key = 0;
 165
 166         memcpy(&key, elem->key.val.data, set->klen);
 167         nft_bitmap_location(key, &idx, &off);
 168
 169         if (!nft_bitmap_active(priv->bitmap, idx, off, genmask))
 170                 return NULL;
 171
 172         /* We have no real set extension since this is a bitmap, allocate this
 173          * dummy object that is released from the commit/abort path.
 174          */
 175         ext = nft_bitmap_ext_alloc(set, elem);
 176         if (!ext)
 177                 return NULL;
 178
 179         /* Enter 10 state. */
 180         priv->bitmap[idx] &= ~(genmask << off);
 181
 182         return ext;
 183 }
 184
 185 static void nft_bitmap_walk(const struct nft_ctx *ctx,
 186                             struct nft_set *set,
 187                             struct nft_set_iter *iter)
 188 {
 189         const struct nft_bitmap *priv = nft_set_priv(set);
 190         struct nft_set_ext_tmpl tmpl;
 191         struct nft_set_elem elem;
 192         struct nft_set_ext *ext;
 193         int idx, off;
 194         u16 key;
 195
 196         nft_set_ext_prepare(&tmpl);
 197         nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, set->klen);
 198
 199         for (idx = 0; idx < priv->bitmap_size; idx++) {
 200                 for (off = 0; off < BITS_PER_BYTE; off += 2) {
 201                         if (iter->count < iter->skip)
 202                                 goto cont;
 203
 204                         if (!nft_bitmap_active(priv->bitmap, idx, off,
 205                                                iter->genmask))
 206                                 goto cont;
 207
 208                         ext = kzalloc(tmpl.len, GFP_KERNEL);
 209                         if (!ext) {
 210                                 iter->err = -ENOMEM;
 211                                 return;
 212                         }
 213                         nft_set_ext_init(ext, &tmpl);
 214                         key = ((idx * BITS_PER_BYTE) + off) >> 1;
 215                         memcpy(nft_set_ext_key(ext), &key, set->klen);
 216
 217                         elem.priv = ext;
 218                         iter->err = iter->fn(ctx, set, iter, &elem);
 219
 220                         /* On set flush, this dummy extension object is released
 221                          * from the commit/abort path.
 222                          */
 223                         if (!iter->flush)
 224                                 kfree(ext);
 225
 226                         if (iter->err < 0)
 227                                 return;
 228 cont:
 229                         iter->count++;
 230                 }
 231         }
 232 }
 233
 234 /* The bitmap size is pow(2, key length in bits) / bits per byte. This is
 235  * multiplied by two since each element takes two bits. For 8 bit keys, the
 236  * bitmap consumes 66 bytes. For 16 bit keys, 16388 bytes.
 237  */
 238 static inline u32 nft_bitmap_size(u32 klen)
 239 {
 240         return ((2 << ((klen * BITS_PER_BYTE) - 1)) / BITS_PER_BYTE) << 1;
 241 }
 242
 243 static inline u32 nft_bitmap_total_size(u32 klen)
 244 {
 245         return sizeof(struct nft_bitmap) + nft_bitmap_size(klen);
 246 }
 247
 248 static unsigned int nft_bitmap_privsize(const struct nlattr * const nla[])
 249 {
 250         u32 klen = ntohl(nla_get_be32(nla[NFTA_SET_KEY_LEN]));
 251
 252         return nft_bitmap_total_size(klen);
 253 }
 254
 255 static int nft_bitmap_init(const struct nft_set *set,
 256                          const struct nft_set_desc *desc,
 257                          const struct nlattr * const nla[])
 258 {
 259         struct nft_bitmap *priv = nft_set_priv(set);
 260
 261         priv->bitmap_size = nft_bitmap_size(set->klen);
 262
 263         return 0;
 264 }
 265
 266 static void nft_bitmap_destroy(const struct nft_set *set)
 267 {
 268 }
 269
 270 static bool nft_bitmap_estimate(const struct nft_set_desc *desc, u32 features,
 271                                 struct nft_set_estimate *est)
 272 {
 273         /* Make sure bitmaps we don't get bitmaps larger than 16 Kbytes. */
 274         if (desc->klen > 2)
 275                 return false;
 276
 277         est->size   = nft_bitmap_total_size(desc->klen);
 278         est->lookup = NFT_SET_CLASS_O_1;
 279         est->space  = NFT_SET_CLASS_O_1;
 280
 281         return true;
 282 }
 283
 284 static struct nft_set_ops nft_bitmap_ops __read_mostly = {
 285         .privsize       = nft_bitmap_privsize,
 286         .estimate       = nft_bitmap_estimate,
 287         .init           = nft_bitmap_init,
 288         .destroy        = nft_bitmap_destroy,
 289         .insert         = nft_bitmap_insert,
 290         .remove         = nft_bitmap_remove,
 291         .deactivate     = nft_bitmap_deactivate,
 292         .flush          = nft_bitmap_flush,
 293         .activate       = nft_bitmap_activate,
 294         .lookup         = nft_bitmap_lookup,
 295         .walk           = nft_bitmap_walk,
 296         .owner          = THIS_MODULE,
 297 };
 298
 299 static int __init nft_bitmap_module_init(void)
 300 {
 301         return nft_register_set(&nft_bitmap_ops);
 302 }
 303
 304 static void __exit nft_bitmap_module_exit(void)
 305 {
 306         nft_unregister_set(&nft_bitmap_ops);
 307 }
 308
 309 module_init(nft_bitmap_module_init);
 310 module_exit(nft_bitmap_module_exit);
 311
 312 MODULE_LICENSE("GPL");
 313 MODULE_AUTHOR("Pablo Neira Ayuso <pablo@netfilter.org>");
 314 MODULE_ALIAS_NFT_SET();