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                 nft_data_uninit(rbe->data, set->dtype);
  74         kfree(rbe);
  75 }
  76
  77 static int __nft_rbtree_insert(const struct nft_set *set,
  78                                struct nft_rbtree_elem *new)
  79 {
  80         struct nft_rbtree *priv = nft_set_priv(set);
  81         struct nft_rbtree_elem *rbe;
  82         struct rb_node *parent, **p;
  83         int d;
  84
  85         parent = NULL;
  86         p = &priv->root.rb_node;
  87         while (*p != NULL) {
  88                 parent = *p;
  89                 rbe = rb_entry(parent, struct nft_rbtree_elem, node);
  90                 d = nft_data_cmp(&rbe->key, &new->key, set->klen);
  91                 if (d < 0)
  92                         p = &parent->rb_left;
  93                 else if (d > 0)
  94                         p = &parent->rb_right;
  95                 else
  96                         return -EEXIST;
  97         }
  98         rb_link_node(&new->node, parent, p);
  99         rb_insert_color(&new->node, &priv->root);
 100         return 0;
 101 }
 102
 103 static int nft_rbtree_insert(const struct nft_set *set,
 104                              const struct nft_set_elem *elem)
 105 {
 106         struct nft_rbtree_elem *rbe;
 107         unsigned int size;
 108         int err;
 109
 110         size = sizeof(*rbe);
 111         if (set->flags & NFT_SET_MAP)
 112                 size += sizeof(rbe->data[0]);
 113
 114         rbe = kzalloc(size, GFP_KERNEL);
 115         if (rbe == NULL)
 116                 return -ENOMEM;
 117
 118         rbe->flags = elem->flags;
 119         nft_data_copy(&rbe->key, &elem->key);
 120         if (set->flags & NFT_SET_MAP)
 121                 nft_data_copy(rbe->data, &elem->data);
 122
 123         err = __nft_rbtree_insert(set, rbe);
 124         if (err < 0)
 125                 kfree(rbe);
 126         return err;
 127 }
 128
 129 static void nft_rbtree_remove(const struct nft_set *set,
 130                               const struct nft_set_elem *elem)
 131 {
 132         struct nft_rbtree *priv = nft_set_priv(set);
 133         struct nft_rbtree_elem *rbe = elem->cookie;
 134
 135         rb_erase(&rbe->node, &priv->root);
 136         kfree(rbe);
 137 }
 138
 139 static int nft_rbtree_get(const struct nft_set *set, struct nft_set_elem *elem)
 140 {
 141         const struct nft_rbtree *priv = nft_set_priv(set);
 142         const struct rb_node *parent = priv->root.rb_node;
 143         struct nft_rbtree_elem *rbe;
 144         int d;
 145
 146         while (parent != NULL) {
 147                 rbe = rb_entry(parent, struct nft_rbtree_elem, node);
 148
 149                 d = nft_data_cmp(&rbe->key, &elem->key, set->klen);
 150                 if (d < 0)
 151                         parent = parent->rb_left;
 152                 else if (d > 0)
 153                         parent = parent->rb_right;
 154                 else {
 155                         elem->cookie = rbe;
 156                         if (set->flags & NFT_SET_MAP)
 157                                 nft_data_copy(&elem->data, rbe->data);
 158                         elem->flags = rbe->flags;
 159                         return 0;
 160                 }
 161         }
 162         return -ENOENT;
 163 }
 164
 165 static void nft_rbtree_walk(const struct nft_ctx *ctx,
 166                             const struct nft_set *set,
 167                             struct nft_set_iter *iter)
 168 {
 169         const struct nft_rbtree *priv = nft_set_priv(set);
 170         const struct nft_rbtree_elem *rbe;
 171         struct nft_set_elem elem;
 172         struct rb_node *node;
 173
 174         for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) {
 175                 if (iter->count < iter->skip)
 176                         goto cont;
 177
 178                 rbe = rb_entry(node, struct nft_rbtree_elem, node);
 179                 nft_data_copy(&elem.key, &rbe->key);
 180                 if (set->flags & NFT_SET_MAP)
 181                         nft_data_copy(&elem.data, rbe->data);
 182                 elem.flags = rbe->flags;
 183
 184                 iter->err = iter->fn(ctx, set, iter, &elem);
 185                 if (iter->err < 0)
 186                         return;
 187 cont:
 188                 iter->count++;
 189         }
 190 }
 191
 192 static unsigned int nft_rbtree_privsize(const struct nlattr * const nla[])
 193 {
 194         return sizeof(struct nft_rbtree);
 195 }
 196
 197 static int nft_rbtree_init(const struct nft_set *set,
 198                            const struct nlattr * const nla[])
 199 {
 200         struct nft_rbtree *priv = nft_set_priv(set);
 201
 202         priv->root = RB_ROOT;
 203         return 0;
 204 }
 205
 206 static void nft_rbtree_destroy(const struct nft_set *set)
 207 {
 208         struct nft_rbtree *priv = nft_set_priv(set);
 209         struct nft_rbtree_elem *rbe;
 210         struct rb_node *node;
 211
 212         while ((node = priv->root.rb_node) != NULL) {
 213                 rb_erase(node, &priv->root);
 214                 rbe = rb_entry(node, struct nft_rbtree_elem, node);
 215                 nft_rbtree_elem_destroy(set, rbe);
 216         }
 217 }
 218
 219 static struct nft_set_ops nft_rbtree_ops __read_mostly = {
 220         .privsize       = nft_rbtree_privsize,
 221         .init           = nft_rbtree_init,
 222         .destroy        = nft_rbtree_destroy,
 223         .insert         = nft_rbtree_insert,
 224         .remove         = nft_rbtree_remove,
 225         .get            = nft_rbtree_get,
 226         .lookup         = nft_rbtree_lookup,
 227         .walk           = nft_rbtree_walk,
 228         .features       = NFT_SET_INTERVAL | NFT_SET_MAP,
 229         .owner          = THIS_MODULE,
 230 };
 231
 232 static int __init nft_rbtree_module_init(void)
 233 {
 234         return nft_register_set(&nft_rbtree_ops);
 235 }
 236
 237 static void __exit nft_rbtree_module_exit(void)
 238 {
 239         nft_unregister_set(&nft_rbtree_ops);
 240 }
 241
 242 module_init(nft_rbtree_module_init);
 243 module_exit(nft_rbtree_module_exit);
 244
 245 MODULE_LICENSE("GPL");
 246 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 247 MODULE_ALIAS_NFT_SET();