kernel/bpf/devmap.c

   1 /* Copyright (c) 2017 Covalent IO, Inc. http://covalent.io
   2  *
   3  * This program is free software; you can redistribute it and/or
   4  * modify it under the terms of version 2 of the GNU General Public
   5  * License as published by the Free Software Foundation.
   6  *
   7  * This program is distributed in the hope that it will be useful, but
   8  * WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  10  * General Public License for more details.
  11  */
  12
  13 /* Devmaps primary use is as a backend map for XDP BPF helper call
  14  * bpf_redirect_map(). Because XDP is mostly concerned with performance we
  15  * spent some effort to ensure the datapath with redirect maps does not use
  16  * any locking. This is a quick note on the details.
  17  *
  18  * We have three possible paths to get into the devmap control plane bpf
  19  * syscalls, bpf programs, and driver side xmit/flush operations. A bpf syscall
  20  * will invoke an update, delete, or lookup operation. To ensure updates and
  21  * deletes appear atomic from the datapath side xchg() is used to modify the
  22  * netdev_map array. Then because the datapath does a lookup into the netdev_map
  23  * array (read-only) from an RCU critical section we use call_rcu() to wait for
  24  * an rcu grace period before free'ing the old data structures. This ensures the
  25  * datapath always has a valid copy. However, the datapath does a "flush"
  26  * operation that pushes any pending packets in the driver outside the RCU
  27  * critical section. Each bpf_dtab_netdev tracks these pending operations using
  28  * an atomic per-cpu bitmap. The bpf_dtab_netdev object will not be destroyed
  29  * until all bits are cleared indicating outstanding flush operations have
  30  * completed.
  31  *
  32  * BPF syscalls may race with BPF program calls on any of the update, delete
  33  * or lookup operations. As noted above the xchg() operation also keep the
  34  * netdev_map consistent in this case. From the devmap side BPF programs
  35  * calling into these operations are the same as multiple user space threads
  36  * making system calls.
  37  */
  38 #include <linux/bpf.h>
  39 #include <linux/jhash.h>
  40 #include <linux/filter.h>
  41 #include <linux/rculist_nulls.h>
  42 #include "percpu_freelist.h"
  43 #include "bpf_lru_list.h"
  44 #include "map_in_map.h"
  45
  46 struct bpf_dtab_netdev {
  47         struct net_device *dev;
  48         int key;
  49         struct rcu_head rcu;
  50         struct bpf_dtab *dtab;
  51 };
  52
  53 struct bpf_dtab {
  54         struct bpf_map map;
  55         struct bpf_dtab_netdev **netdev_map;
  56 };
  57
  58 static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
  59 {
  60         struct bpf_dtab *dtab;
  61         u64 cost;
  62         int err;
  63
  64         /* check sanity of attributes */
  65         if (attr->max_entries == 0 || attr->key_size != 4 ||
  66             attr->value_size != 4 || attr->map_flags)
  67                 return ERR_PTR(-EINVAL);
  68
  69         /* if value_size is bigger, the user space won't be able to
  70          * access the elements.
  71          */
  72         if (attr->value_size > KMALLOC_MAX_SIZE)
  73                 return ERR_PTR(-E2BIG);
  74
  75         dtab = kzalloc(sizeof(*dtab), GFP_USER);
  76         if (!dtab)
  77                 return ERR_PTR(-ENOMEM);
  78
  79         /* mandatory map attributes */
  80         dtab->map.map_type = attr->map_type;
  81         dtab->map.key_size = attr->key_size;
  82         dtab->map.value_size = attr->value_size;
  83         dtab->map.max_entries = attr->max_entries;
  84         dtab->map.map_flags = attr->map_flags;
  85
  86         err = -ENOMEM;
  87
  88         /* make sure page count doesn't overflow */
  89         cost = (u64) dtab->map.max_entries * sizeof(struct bpf_dtab_netdev *);
  90         if (cost >= U32_MAX - PAGE_SIZE)
  91                 goto free_dtab;
  92
  93         dtab->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;
  94
  95         /* if map size is larger than memlock limit, reject it early */
  96         err = bpf_map_precharge_memlock(dtab->map.pages);
  97         if (err)
  98                 goto free_dtab;
  99
 100         dtab->netdev_map = bpf_map_area_alloc(dtab->map.max_entries *
 101                                               sizeof(struct bpf_dtab_netdev *));
 102         if (!dtab->netdev_map)
 103                 goto free_dtab;
 104
 105         return &dtab->map;
 106
 107 free_dtab:
 108         kfree(dtab);
 109         return ERR_PTR(err);
 110 }
 111
 112 static void dev_map_free(struct bpf_map *map)
 113 {
 114         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 115         int i;
 116
 117         /* At this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0,
 118          * so the programs (can be more than one that used this map) were
 119          * disconnected from events. Wait for outstanding critical sections in
 120          * these programs to complete. The rcu critical section only guarantees
 121          * no further reads against netdev_map. It does __not__ ensure pending
 122          * flush operations (if any) are complete.
 123          */
 124         synchronize_rcu();
 125
 126         for (i = 0; i < dtab->map.max_entries; i++) {
 127                 struct bpf_dtab_netdev *dev;
 128
 129                 dev = dtab->netdev_map[i];
 130                 if (!dev)
 131                         continue;
 132
 133                 dev_put(dev->dev);
 134                 kfree(dev);
 135         }
 136
 137         /* At this point bpf program is detached and all pending operations
 138          * _must_ be complete
 139          */
 140         bpf_map_area_free(dtab->netdev_map);
 141         kfree(dtab);
 142 }
 143
 144 static int dev_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 145 {
 146         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 147         u32 index = key ? *(u32 *)key : U32_MAX;
 148         u32 *next = (u32 *)next_key;
 149
 150         if (index >= dtab->map.max_entries) {
 151                 *next = 0;
 152                 return 0;
 153         }
 154
 155         if (index == dtab->map.max_entries - 1)
 156                 return -ENOENT;
 157
 158         *next = index + 1;
 159         return 0;
 160 }
 161
 162 struct net_device  *__dev_map_lookup_elem(struct bpf_map *map, u32 key)
 163 {
 164         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 165         struct bpf_dtab_netdev *dev;
 166
 167         if (key >= map->max_entries)
 168                 return NULL;
 169
 170         dev = READ_ONCE(dtab->netdev_map[key]);
 171         return dev ? dev->dev : NULL;
 172 }
 173
 174 /* rcu_read_lock (from syscall and BPF contexts) ensures that if a delete and/or
 175  * update happens in parallel here a dev_put wont happen until after reading the
 176  * ifindex.
 177  */
 178 static void *dev_map_lookup_elem(struct bpf_map *map, void *key)
 179 {
 180         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 181         struct bpf_dtab_netdev *dev;
 182         u32 i = *(u32 *)key;
 183
 184         if (i >= map->max_entries)
 185                 return NULL;
 186
 187         dev = READ_ONCE(dtab->netdev_map[i]);
 188         return dev ? &dev->dev->ifindex : NULL;
 189 }
 190
 191 static void __dev_map_entry_free(struct rcu_head *rcu)
 192 {
 193         struct bpf_dtab_netdev *old_dev;
 194
 195         old_dev = container_of(rcu, struct bpf_dtab_netdev, rcu);
 196         dev_put(old_dev->dev);
 197         kfree(old_dev);
 198 }
 199
 200 static int dev_map_delete_elem(struct bpf_map *map, void *key)
 201 {
 202         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 203         struct bpf_dtab_netdev *old_dev;
 204         int k = *(u32 *)key;
 205
 206         if (k >= map->max_entries)
 207                 return -EINVAL;
 208
 209         /* Use synchronize_rcu() here to ensure any rcu critical sections
 210          * have completed, but this does not guarantee a flush has happened
 211          * yet. Because driver side rcu_read_lock/unlock only protects the
 212          * running XDP program. However, for pending flush operations the
 213          * dev and ctx are stored in another per cpu map. And additionally,
 214          * the driver tear down ensures all soft irqs are complete before
 215          * removing the net device in the case of dev_put equals zero.
 216          */
 217         old_dev = xchg(&dtab->netdev_map[k], NULL);
 218         if (old_dev)
 219                 call_rcu(&old_dev->rcu, __dev_map_entry_free);
 220         return 0;
 221 }
 222
 223 static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
 224                                 u64 map_flags)
 225 {
 226         struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 227         struct net *net = current->nsproxy->net_ns;
 228         struct bpf_dtab_netdev *dev, *old_dev;
 229         u32 i = *(u32 *)key;
 230         u32 ifindex = *(u32 *)value;
 231
 232         if (unlikely(map_flags > BPF_EXIST))
 233                 return -EINVAL;
 234
 235         if (unlikely(i >= dtab->map.max_entries))
 236                 return -E2BIG;
 237
 238         if (unlikely(map_flags == BPF_NOEXIST))
 239                 return -EEXIST;
 240
 241         if (!ifindex) {
 242                 dev = NULL;
 243         } else {
 244                 dev = kmalloc(sizeof(*dev), GFP_ATOMIC | __GFP_NOWARN);
 245                 if (!dev)
 246                         return -ENOMEM;
 247
 248                 dev->dev = dev_get_by_index(net, ifindex);
 249                 if (!dev->dev) {
 250                         kfree(dev);
 251                         return -EINVAL;
 252                 }
 253
 254                 dev->key = i;
 255                 dev->dtab = dtab;
 256         }
 257
 258         /* Use call_rcu() here to ensure rcu critical sections have completed
 259          * Remembering the driver side flush operation will happen before the
 260          * net device is removed.
 261          */
 262         old_dev = xchg(&dtab->netdev_map[i], dev);
 263         if (old_dev)
 264                 call_rcu(&old_dev->rcu, __dev_map_entry_free);
 265
 266         return 0;
 267 }
 268
 269 const struct bpf_map_ops dev_map_ops = {
 270         .map_alloc = dev_map_alloc,
 271         .map_free = dev_map_free,
 272         .map_get_next_key = dev_map_get_next_key,
 273         .map_lookup_elem = dev_map_lookup_elem,
 274         .map_update_elem = dev_map_update_elem,
 275         .map_delete_elem = dev_map_delete_elem,
 276 };