net/netfilter/nft_rbtree.c

   1 /*
   2  * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net>
   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/rbtree.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_rbtree {
  22         struct rb_root          root;
  23 };
  24
  25 struct nft_rbtree_elem {
  26         struct rb_node          node;
  27         u16                     flags;
  28         struct nft_data         key;
  29         struct nft_data         data[];
  30 };
  31
  32 static bool nft_rbtree_lookup(const struct nft_set *set,
  33                               const struct nft_data *key,
  34                               struct nft_data *data)
  35 {
  36         const struct nft_rbtree *priv = nft_set_priv(set);
  37         const struct nft_rbtree_elem *rbe, *interval = NULL;
  38         const struct rb_node *parent = priv->root.rb_node;
  39         int d;
  40
  41         while (parent != NULL) {
  42                 rbe = rb_entry(parent, struct nft_rbtree_elem, node);
  43
  44                 d = nft_data_cmp(&rbe->key, key, set->klen);
  45                 if (d < 0) {
  46                         parent = parent->rb_left;
  47                         interval = rbe;
  48                 } else if (d > 0)
  49                         parent = parent->rb_right;
  50                 else {
  51 found:
  52                         if (rbe->flags & NFT_SET_ELEM_INTERVAL_END)
  53                                 goto out;
  54                         if (set->flags & NFT_SET_MAP)
  55                                 nft_data_copy(data, rbe->data);
  56                         return true;
  57                 }
  58         }
  59
  60         if (set->flags & NFT_SET_INTERVAL && interval != NULL) {
  61                 rbe = interval;
  62                 goto found;
  63         }
  64 out:
  65         return false;
  66 }
  67
  68 static void nft_rbtree_elem_destroy(const struct nft_set *set,
  69                                     struct nft_rbtree_elem *rbe)
  70 {
  71         nft_data_uninit(&rbe->key, NFT_DATA_VALUE);
  72         if (set->flags & NFT_SET_MAP &&
  73             !(rbe->flags & NFT_SET_ELEM_INTERVAL_END))
  74                 nft_data_uninit(rbe->data, set->dtype);
  75
  76         kfree(rbe);
  77 }
  78
  79 static int __nft_rbtree_insert(const struct nft_set *set,
  80                                struct nft_rbtree_elem *new)
  81 {
  82         struct nft_rbtree *priv = nft_set_priv(set);
  83         struct nft_rbtree_elem *rbe;
  84         struct rb_node *parent, **p;
  85         int d;
  86
  87         parent = NULL;
  88         p = &priv->root.rb_node;
  89         while (*p != NULL) {
  90                 parent = *p;
  91                 rbe = rb_entry(parent, struct nft_rbtree_elem, node);
  92                 d = nft_data_cmp(&rbe->key, &new->key, set->klen);
  93                 if (d < 0)
  94                         p = &parent->rb_left;
  95                 else if (d > 0)
  96                         p = &parent->rb_right;
  97                 else
  98                         return -EEXIST;
  99         }
 100         rb_link_node(&new->node, parent, p);
 101         rb_insert_color(&new->node, &priv->root);
 102         return 0;
 103 }
 104
 105 static int nft_rbtree_insert(const struct nft_set *set,
 106                              const struct nft_set_elem *elem)
 107 {
 108         struct nft_rbtree_elem *rbe;
 109         unsigned int size;
 110         int err;
 111
 112         size = sizeof(*rbe);
 113         if (set->flags & NFT_SET_MAP &&
 114             !(elem->flags & NFT_SET_ELEM_INTERVAL_END))
 115                 size += sizeof(rbe->data[0]);
 116
 117         rbe = kzalloc(size, GFP_KERNEL);
 118         if (rbe == NULL)
 119                 return -ENOMEM;
 120
 121         rbe->flags = elem->flags;
 122         nft_data_copy(&rbe->key, &elem->key);
 123         if (set->flags & NFT_SET_MAP &&
 124             !(rbe->flags & NFT_SET_ELEM_INTERVAL_END))
 125                 nft_data_copy(rbe->data, &elem->data);
 126
 127         err = __nft_rbtree_insert(set, rbe);
 128         if (err < 0)
 129                 kfree(rbe);
 130         return err;
 131 }
 132
 133 static void nft_rbtree_remove(const struct nft_set *set,
 134                               const struct nft_set_elem *elem)
 135 {
 136         struct nft_rbtree *priv = nft_set_priv(set);
 137         struct nft_rbtree_elem *rbe = elem->cookie;
 138
 139         rb_erase(&rbe->node, &priv->root);
 140         kfree(rbe);
 141 }
 142
 143 static int nft_rbtree_get(const struct nft_set *set, struct nft_set_elem *elem)
 144 {
 145         const struct nft_rbtree *priv = nft_set_priv(set);
 146         const struct rb_node *parent = priv->root.rb_node;
 147         struct nft_rbtree_elem *rbe;
 148         int d;
 149
 150         while (parent != NULL) {
 151                 rbe = rb_entry(parent, struct nft_rbtree_elem, node);
 152
 153                 d = nft_data_cmp(&rbe->key, &elem->key, set->klen);
 154                 if (d < 0)
 155                         parent = parent->rb_left;
 156                 else if (d > 0)
 157                         parent = parent->rb_right;
 158                 else {
 159                         elem->cookie = rbe;
 160                         if (set->flags & NFT_SET_MAP &&
 161                             !(rbe->flags & NFT_SET_ELEM_INTERVAL_END))
 162                                 nft_data_copy(&elem->data, rbe->data);
 163                         elem->flags = rbe->flags;
 164                         return 0;
 165                 }
 166         }
 167         return -ENOENT;
 168 }
 169
 170 static void nft_rbtree_walk(const struct nft_ctx *ctx,
 171                             const struct nft_set *set,
 172                             struct nft_set_iter *iter)
 173 {
 174         const struct nft_rbtree *priv = nft_set_priv(set);
 175         const struct nft_rbtree_elem *rbe;
 176         struct nft_set_elem elem;
 177         struct rb_node *node;
 178
 179         for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) {
 180                 if (iter->count < iter->skip)
 181                         goto cont;
 182
 183                 rbe = rb_entry(node, struct nft_rbtree_elem, node);
 184                 nft_data_copy(&elem.key, &rbe->key);
 185                 if (set->flags & NFT_SET_MAP &&
 186                     !(rbe->flags & NFT_SET_ELEM_INTERVAL_END))
 187                         nft_data_copy(&elem.data, rbe->data);
 188                 elem.flags = rbe->flags;
 189
 190                 iter->err = iter->fn(ctx, set, iter, &elem);
 191                 if (iter->err < 0)
 192                         return;
 193 cont:
 194                 iter->count++;
 195         }
 196 }
 197
 198 static unsigned int nft_rbtree_privsize(const struct nlattr * const nla[])
 199 {
 200         return sizeof(struct nft_rbtree);
 201 }
 202
 203 static int nft_rbtree_init(const struct nft_set *set,
 204                            const struct nft_set_desc *desc,
 205                            const struct nlattr * const nla[])
 206 {
 207         struct nft_rbtree *priv = nft_set_priv(set);
 208
 209         priv->root = RB_ROOT;
 210         return 0;
 211 }
 212
 213 static void nft_rbtree_destroy(const struct nft_set *set)
 214 {
 215         struct nft_rbtree *priv = nft_set_priv(set);
 216         struct nft_rbtree_elem *rbe;
 217         struct rb_node *node;
 218
 219         while ((node = priv->root.rb_node) != NULL) {
 220                 rb_erase(node, &priv->root);
 221                 rbe = rb_entry(node, struct nft_rbtree_elem, node);
 222                 nft_rbtree_elem_destroy(set, rbe);
 223         }
 224 }
 225
 226 static bool nft_rbtree_estimate(const struct nft_set_desc *desc, u32 features,
 227                                 struct nft_set_estimate *est)
 228 {
 229         unsigned int nsize;
 230
 231         nsize = sizeof(struct nft_rbtree_elem);
 232         if (features & NFT_SET_MAP)
 233                 nsize += FIELD_SIZEOF(struct nft_rbtree_elem, data[0]);
 234
 235         if (desc->size)
 236                 est->size = sizeof(struct nft_rbtree) + desc->size * nsize;
 237         else
 238                 est->size = nsize;
 239
 240         est->class = NFT_SET_CLASS_O_LOG_N;
 241
 242         return true;
 243 }
 244
 245 static struct nft_set_ops nft_rbtree_ops __read_mostly = {
 246         .privsize       = nft_rbtree_privsize,
 247         .estimate       = nft_rbtree_estimate,
 248         .init           = nft_rbtree_init,
 249         .destroy        = nft_rbtree_destroy,
 250         .insert         = nft_rbtree_insert,
 251         .remove         = nft_rbtree_remove,
 252         .get            = nft_rbtree_get,
 253         .lookup         = nft_rbtree_lookup,
 254         .walk           = nft_rbtree_walk,
 255         .features       = NFT_SET_INTERVAL | NFT_SET_MAP,
 256         .owner          = THIS_MODULE,
 257 };
 258
 259 static int __init nft_rbtree_module_init(void)
 260 {
 261         return nft_register_set(&nft_rbtree_ops);
 262 }
 263
 264 static void __exit nft_rbtree_module_exit(void)
 265 {
 266         nft_unregister_set(&nft_rbtree_ops);
 267 }
 268
 269 module_init(nft_rbtree_module_init);
 270 module_exit(nft_rbtree_module_exit);
 271
 272 MODULE_LICENSE("GPL");
 273 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 274 MODULE_ALIAS_NFT_SET();