kernel/bpf/arraymap.c

   1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
   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 #include <linux/bpf.h>
  13 #include <linux/err.h>
  14 #include <linux/slab.h>
  15 #include <linux/mm.h>
  16 #include <linux/filter.h>
  17 #include <linux/perf_event.h>
  18
  19 static void bpf_array_free_percpu(struct bpf_array *array)
  20 {
  21         int i;
  22
  23         for (i = 0; i < array->map.max_entries; i++) {
  24                 free_percpu(array->pptrs[i]);
  25                 cond_resched();
  26         }
  27 }
  28
  29 static int bpf_array_alloc_percpu(struct bpf_array *array)
  30 {
  31         void __percpu *ptr;
  32         int i;
  33
  34         for (i = 0; i < array->map.max_entries; i++) {
  35                 ptr = __alloc_percpu_gfp(array->elem_size, 8,
  36                                          GFP_USER | __GFP_NOWARN);
  37                 if (!ptr) {
  38                         bpf_array_free_percpu(array);
  39                         return -ENOMEM;
  40                 }
  41                 array->pptrs[i] = ptr;
  42                 cond_resched();
  43         }
  44
  45         return 0;
  46 }
  47
  48 /* Called from syscall */
  49 static struct bpf_map *array_map_alloc(union bpf_attr *attr)
  50 {
  51         bool percpu = attr->map_type == BPF_MAP_TYPE_PERCPU_ARRAY;
  52         u32 elem_size, index_mask, max_entries;
  53         bool unpriv = !capable(CAP_SYS_ADMIN);
  54         u64 cost, array_size, mask64;
  55         struct bpf_array *array;
  56         int ret;
  57
  58         /* check sanity of attributes */
  59         if (attr->max_entries == 0 || attr->key_size != 4 ||
  60             attr->value_size == 0 || attr->map_flags)
  61                 return ERR_PTR(-EINVAL);
  62
  63         if (attr->value_size >= 1 << (KMALLOC_SHIFT_MAX - 1))
  64                 /* if value_size is bigger, the user space won't be able to
  65                  * access the elements.
  66                  */
  67                 return ERR_PTR(-E2BIG);
  68
  69         elem_size = round_up(attr->value_size, 8);
  70
  71         max_entries = attr->max_entries;
  72
  73         /* On 32 bit archs roundup_pow_of_two() with max_entries that has
  74          * upper most bit set in u32 space is undefined behavior due to
  75          * resulting 1U << 32, so do it manually here in u64 space.
  76          */
  77         mask64 = fls_long(max_entries - 1);
  78         mask64 = 1ULL << mask64;
  79         mask64 -= 1;
  80
  81         index_mask = mask64;
  82         if (unpriv) {
  83                 /* round up array size to nearest power of 2,
  84                  * since cpu will speculate within index_mask limits
  85                  */
  86                 max_entries = index_mask + 1;
  87                 /* Check for overflows. */
  88                 if (max_entries < attr->max_entries)
  89                         return ERR_PTR(-E2BIG);
  90         }
  91
  92         array_size = sizeof(*array);
  93         if (percpu)
  94                 array_size += (u64) max_entries * sizeof(void *);
  95         else
  96                 array_size += (u64) max_entries * elem_size;
  97
  98         /* make sure there is no u32 overflow later in round_up() */
  99         cost = array_size;
 100         if (cost >= U32_MAX - PAGE_SIZE)
 101                 return ERR_PTR(-ENOMEM);
 102         if (percpu) {
 103                 cost += (u64)attr->max_entries * elem_size * num_possible_cpus();
 104                 if (cost >= U32_MAX - PAGE_SIZE)
 105                         return ERR_PTR(-ENOMEM);
 106         }
 107         cost = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;
 108
 109         ret = bpf_map_precharge_memlock(cost);
 110         if (ret < 0)
 111                 return ERR_PTR(ret);
 112
 113         /* allocate all map elements and zero-initialize them */
 114         array = bpf_map_area_alloc(array_size);
 115         if (!array)
 116                 return ERR_PTR(-ENOMEM);
 117         array->index_mask = index_mask;
 118         array->map.unpriv_array = unpriv;
 119
 120         /* copy mandatory map attributes */
 121         array->map.map_type = attr->map_type;
 122         array->map.key_size = attr->key_size;
 123         array->map.value_size = attr->value_size;
 124         array->map.max_entries = attr->max_entries;
 125         array->map.map_flags = attr->map_flags;
 126         array->map.pages = cost;
 127         array->elem_size = elem_size;
 128
 129         if (percpu &&
 130             (elem_size > PCPU_MIN_UNIT_SIZE ||
 131              bpf_array_alloc_percpu(array))) {
 132                 bpf_map_area_free(array);
 133                 return ERR_PTR(-ENOMEM);
 134         }
 135
 136         return &array->map;
 137 }
 138
 139 /* Called from syscall or from eBPF program */
 140 static void *array_map_lookup_elem(struct bpf_map *map, void *key)
 141 {
 142         struct bpf_array *array = container_of(map, struct bpf_array, map);
 143         u32 index = *(u32 *)key;
 144
 145         if (unlikely(index >= array->map.max_entries))
 146                 return NULL;
 147
 148         return array->value + array->elem_size * (index & array->index_mask);
 149 }
 150
 151 /* Called from eBPF program */
 152 static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
 153 {
 154         struct bpf_array *array = container_of(map, struct bpf_array, map);
 155         u32 index = *(u32 *)key;
 156
 157         if (unlikely(index >= array->map.max_entries))
 158                 return NULL;
 159
 160         return this_cpu_ptr(array->pptrs[index & array->index_mask]);
 161 }
 162
 163 int bpf_percpu_array_copy(struct bpf_map *map, void *key, void *value)
 164 {
 165         struct bpf_array *array = container_of(map, struct bpf_array, map);
 166         u32 index = *(u32 *)key;
 167         void __percpu *pptr;
 168         int cpu, off = 0;
 169         u32 size;
 170
 171         if (unlikely(index >= array->map.max_entries))
 172                 return -ENOENT;
 173
 174         /* per_cpu areas are zero-filled and bpf programs can only
 175          * access 'value_size' of them, so copying rounded areas
 176          * will not leak any kernel data
 177          */
 178         size = round_up(map->value_size, 8);
 179         rcu_read_lock();
 180         pptr = array->pptrs[index & array->index_mask];
 181         for_each_possible_cpu(cpu) {
 182                 bpf_long_memcpy(value + off, per_cpu_ptr(pptr, cpu), size);
 183                 off += size;
 184         }
 185         rcu_read_unlock();
 186         return 0;
 187 }
 188
 189 /* Called from syscall */
 190 static int array_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 191 {
 192         struct bpf_array *array = container_of(map, struct bpf_array, map);
 193         u32 index = key ? *(u32 *)key : U32_MAX;
 194         u32 *next = (u32 *)next_key;
 195
 196         if (index >= array->map.max_entries) {
 197                 *next = 0;
 198                 return 0;
 199         }
 200
 201         if (index == array->map.max_entries - 1)
 202                 return -ENOENT;
 203
 204         *next = index + 1;
 205         return 0;
 206 }
 207
 208 /* Called from syscall or from eBPF program */
 209 static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 210                                  u64 map_flags)
 211 {
 212         struct bpf_array *array = container_of(map, struct bpf_array, map);
 213         u32 index = *(u32 *)key;
 214
 215         if (unlikely(map_flags > BPF_EXIST))
 216                 /* unknown flags */
 217                 return -EINVAL;
 218
 219         if (unlikely(index >= array->map.max_entries))
 220                 /* all elements were pre-allocated, cannot insert a new one */
 221                 return -E2BIG;
 222
 223         if (unlikely(map_flags == BPF_NOEXIST))
 224                 /* all elements already exist */
 225                 return -EEXIST;
 226
 227         if (array->map.map_type == BPF_MAP_TYPE_PERCPU_ARRAY)
 228                 memcpy(this_cpu_ptr(array->pptrs[index & array->index_mask]),
 229                        value, map->value_size);
 230         else
 231                 memcpy(array->value +
 232                        array->elem_size * (index & array->index_mask),
 233                        value, map->value_size);
 234         return 0;
 235 }
 236
 237 int bpf_percpu_array_update(struct bpf_map *map, void *key, void *value,
 238                             u64 map_flags)
 239 {
 240         struct bpf_array *array = container_of(map, struct bpf_array, map);
 241         u32 index = *(u32 *)key;
 242         void __percpu *pptr;
 243         int cpu, off = 0;
 244         u32 size;
 245
 246         if (unlikely(map_flags > BPF_EXIST))
 247                 /* unknown flags */
 248                 return -EINVAL;
 249
 250         if (unlikely(index >= array->map.max_entries))
 251                 /* all elements were pre-allocated, cannot insert a new one */
 252                 return -E2BIG;
 253
 254         if (unlikely(map_flags == BPF_NOEXIST))
 255                 /* all elements already exist */
 256                 return -EEXIST;
 257
 258         /* the user space will provide round_up(value_size, 8) bytes that
 259          * will be copied into per-cpu area. bpf programs can only access
 260          * value_size of it. During lookup the same extra bytes will be
 261          * returned or zeros which were zero-filled by percpu_alloc,
 262          * so no kernel data leaks possible
 263          */
 264         size = round_up(map->value_size, 8);
 265         rcu_read_lock();
 266         pptr = array->pptrs[index & array->index_mask];
 267         for_each_possible_cpu(cpu) {
 268                 bpf_long_memcpy(per_cpu_ptr(pptr, cpu), value + off, size);
 269                 off += size;
 270         }
 271         rcu_read_unlock();
 272         return 0;
 273 }
 274
 275 /* Called from syscall or from eBPF program */
 276 static int array_map_delete_elem(struct bpf_map *map, void *key)
 277 {
 278         return -EINVAL;
 279 }
 280
 281 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
 282 static void array_map_free(struct bpf_map *map)
 283 {
 284         struct bpf_array *array = container_of(map, struct bpf_array, map);
 285
 286         /* at this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0,
 287          * so the programs (can be more than one that used this map) were
 288          * disconnected from events. Wait for outstanding programs to complete
 289          * and free the array
 290          */
 291         synchronize_rcu();
 292
 293         if (array->map.map_type == BPF_MAP_TYPE_PERCPU_ARRAY)
 294                 bpf_array_free_percpu(array);
 295
 296         bpf_map_area_free(array);
 297 }
 298
 299 static const struct bpf_map_ops array_ops = {
 300         .map_alloc = array_map_alloc,
 301         .map_free = array_map_free,
 302         .map_get_next_key = array_map_get_next_key,
 303         .map_lookup_elem = array_map_lookup_elem,
 304         .map_update_elem = array_map_update_elem,
 305         .map_delete_elem = array_map_delete_elem,
 306 };
 307
 308 static struct bpf_map_type_list array_type __read_mostly = {
 309         .ops = &array_ops,
 310         .type = BPF_MAP_TYPE_ARRAY,
 311 };
 312
 313 static const struct bpf_map_ops percpu_array_ops = {
 314         .map_alloc = array_map_alloc,
 315         .map_free = array_map_free,
 316         .map_get_next_key = array_map_get_next_key,
 317         .map_lookup_elem = percpu_array_map_lookup_elem,
 318         .map_update_elem = array_map_update_elem,
 319         .map_delete_elem = array_map_delete_elem,
 320 };
 321
 322 static struct bpf_map_type_list percpu_array_type __read_mostly = {
 323         .ops = &percpu_array_ops,
 324         .type = BPF_MAP_TYPE_PERCPU_ARRAY,
 325 };
 326
 327 static int __init register_array_map(void)
 328 {
 329         bpf_register_map_type(&array_type);
 330         bpf_register_map_type(&percpu_array_type);
 331         return 0;
 332 }
 333 late_initcall(register_array_map);
 334
 335 static struct bpf_map *fd_array_map_alloc(union bpf_attr *attr)
 336 {
 337         /* only file descriptors can be stored in this type of map */
 338         if (attr->value_size != sizeof(u32))
 339                 return ERR_PTR(-EINVAL);
 340         return array_map_alloc(attr);
 341 }
 342
 343 static void fd_array_map_free(struct bpf_map *map)
 344 {
 345         struct bpf_array *array = container_of(map, struct bpf_array, map);
 346         int i;
 347
 348         synchronize_rcu();
 349
 350         /* make sure it's empty */
 351         for (i = 0; i < array->map.max_entries; i++)
 352                 BUG_ON(array->ptrs[i] != NULL);
 353
 354         bpf_map_area_free(array);
 355 }
 356
 357 static void *fd_array_map_lookup_elem(struct bpf_map *map, void *key)
 358 {
 359         return NULL;
 360 }
 361
 362 /* only called from syscall */
 363 int bpf_fd_array_map_update_elem(struct bpf_map *map, struct file *map_file,
 364                                  void *key, void *value, u64 map_flags)
 365 {
 366         struct bpf_array *array = container_of(map, struct bpf_array, map);
 367         void *new_ptr, *old_ptr;
 368         u32 index = *(u32 *)key, ufd;
 369
 370         if (map_flags != BPF_ANY)
 371                 return -EINVAL;
 372
 373         if (index >= array->map.max_entries)
 374                 return -E2BIG;
 375
 376         ufd = *(u32 *)value;
 377         new_ptr = map->ops->map_fd_get_ptr(map, map_file, ufd);
 378         if (IS_ERR(new_ptr))
 379                 return PTR_ERR(new_ptr);
 380
 381         old_ptr = xchg(array->ptrs + index, new_ptr);
 382         if (old_ptr)
 383                 map->ops->map_fd_put_ptr(old_ptr);
 384
 385         return 0;
 386 }
 387
 388 static int fd_array_map_delete_elem(struct bpf_map *map, void *key)
 389 {
 390         struct bpf_array *array = container_of(map, struct bpf_array, map);
 391         void *old_ptr;
 392         u32 index = *(u32 *)key;
 393
 394         if (index >= array->map.max_entries)
 395                 return -E2BIG;
 396
 397         old_ptr = xchg(array->ptrs + index, NULL);
 398         if (old_ptr) {
 399                 map->ops->map_fd_put_ptr(old_ptr);
 400                 return 0;
 401         } else {
 402                 return -ENOENT;
 403         }
 404 }
 405
 406 static void *prog_fd_array_get_ptr(struct bpf_map *map,
 407                                    struct file *map_file, int fd)
 408 {
 409         struct bpf_array *array = container_of(map, struct bpf_array, map);
 410         struct bpf_prog *prog = bpf_prog_get(fd);
 411
 412         if (IS_ERR(prog))
 413                 return prog;
 414
 415         if (!bpf_prog_array_compatible(array, prog)) {
 416                 bpf_prog_put(prog);
 417                 return ERR_PTR(-EINVAL);
 418         }
 419
 420         return prog;
 421 }
 422
 423 static void prog_fd_array_put_ptr(void *ptr)
 424 {
 425         bpf_prog_put(ptr);
 426 }
 427
 428 /* decrement refcnt of all bpf_progs that are stored in this map */
 429 void bpf_fd_array_map_clear(struct bpf_map *map)
 430 {
 431         struct bpf_array *array = container_of(map, struct bpf_array, map);
 432         int i;
 433
 434         for (i = 0; i < array->map.max_entries; i++)
 435                 fd_array_map_delete_elem(map, &i);
 436 }
 437
 438 static const struct bpf_map_ops prog_array_ops = {
 439         .map_alloc = fd_array_map_alloc,
 440         .map_free = fd_array_map_free,
 441         .map_get_next_key = array_map_get_next_key,
 442         .map_lookup_elem = fd_array_map_lookup_elem,
 443         .map_delete_elem = fd_array_map_delete_elem,
 444         .map_fd_get_ptr = prog_fd_array_get_ptr,
 445         .map_fd_put_ptr = prog_fd_array_put_ptr,
 446 };
 447
 448 static struct bpf_map_type_list prog_array_type __read_mostly = {
 449         .ops = &prog_array_ops,
 450         .type = BPF_MAP_TYPE_PROG_ARRAY,
 451 };
 452
 453 static int __init register_prog_array_map(void)
 454 {
 455         bpf_register_map_type(&prog_array_type);
 456         return 0;
 457 }
 458 late_initcall(register_prog_array_map);
 459
 460 static struct bpf_event_entry *bpf_event_entry_gen(struct file *perf_file,
 461                                                    struct file *map_file)
 462 {
 463         struct bpf_event_entry *ee;
 464
 465         ee = kzalloc(sizeof(*ee), GFP_ATOMIC);
 466         if (ee) {
 467                 ee->event = perf_file->private_data;
 468                 ee->perf_file = perf_file;
 469                 ee->map_file = map_file;
 470         }
 471
 472         return ee;
 473 }
 474
 475 static void __bpf_event_entry_free(struct rcu_head *rcu)
 476 {
 477         struct bpf_event_entry *ee;
 478
 479         ee = container_of(rcu, struct bpf_event_entry, rcu);
 480         fput(ee->perf_file);
 481         kfree(ee);
 482 }
 483
 484 static void bpf_event_entry_free_rcu(struct bpf_event_entry *ee)
 485 {
 486         call_rcu(&ee->rcu, __bpf_event_entry_free);
 487 }
 488
 489 static void *perf_event_fd_array_get_ptr(struct bpf_map *map,
 490                                          struct file *map_file, int fd)
 491 {
 492         const struct perf_event_attr *attr;
 493         struct bpf_event_entry *ee;
 494         struct perf_event *event;
 495         struct file *perf_file;
 496
 497         perf_file = perf_event_get(fd);
 498         if (IS_ERR(perf_file))
 499                 return perf_file;
 500
 501         event = perf_file->private_data;
 502         ee = ERR_PTR(-EINVAL);
 503
 504         attr = perf_event_attrs(event);
 505         if (IS_ERR(attr) || attr->inherit)
 506                 goto err_out;
 507
 508         switch (attr->type) {
 509         case PERF_TYPE_SOFTWARE:
 510                 if (attr->config != PERF_COUNT_SW_BPF_OUTPUT)
 511                         goto err_out;
 512                 /* fall-through */
 513         case PERF_TYPE_RAW:
 514         case PERF_TYPE_HARDWARE:
 515                 ee = bpf_event_entry_gen(perf_file, map_file);
 516                 if (ee)
 517                         return ee;
 518                 ee = ERR_PTR(-ENOMEM);
 519                 /* fall-through */
 520         default:
 521                 break;
 522         }
 523
 524 err_out:
 525         fput(perf_file);
 526         return ee;
 527 }
 528
 529 static void perf_event_fd_array_put_ptr(void *ptr)
 530 {
 531         bpf_event_entry_free_rcu(ptr);
 532 }
 533
 534 static void perf_event_fd_array_release(struct bpf_map *map,
 535                                         struct file *map_file)
 536 {
 537         struct bpf_array *array = container_of(map, struct bpf_array, map);
 538         struct bpf_event_entry *ee;
 539         int i;
 540
 541         rcu_read_lock();
 542         for (i = 0; i < array->map.max_entries; i++) {
 543                 ee = READ_ONCE(array->ptrs[i]);
 544                 if (ee && ee->map_file == map_file)
 545                         fd_array_map_delete_elem(map, &i);
 546         }
 547         rcu_read_unlock();
 548 }
 549
 550 static const struct bpf_map_ops perf_event_array_ops = {
 551         .map_alloc = fd_array_map_alloc,
 552         .map_free = fd_array_map_free,
 553         .map_get_next_key = array_map_get_next_key,
 554         .map_lookup_elem = fd_array_map_lookup_elem,
 555         .map_delete_elem = fd_array_map_delete_elem,
 556         .map_fd_get_ptr = perf_event_fd_array_get_ptr,
 557         .map_fd_put_ptr = perf_event_fd_array_put_ptr,
 558         .map_release = perf_event_fd_array_release,
 559 };
 560
 561 static struct bpf_map_type_list perf_event_array_type __read_mostly = {
 562         .ops = &perf_event_array_ops,
 563         .type = BPF_MAP_TYPE_PERF_EVENT_ARRAY,
 564 };
 565
 566 static int __init register_perf_event_array_map(void)
 567 {
 568         bpf_register_map_type(&perf_event_array_type);
 569         return 0;
 570 }
 571 late_initcall(register_perf_event_array_map);
 572
 573 #ifdef CONFIG_CGROUPS
 574 static void *cgroup_fd_array_get_ptr(struct bpf_map *map,
 575                                      struct file *map_file /* not used */,
 576                                      int fd)
 577 {
 578         return cgroup_get_from_fd(fd);
 579 }
 580
 581 static void cgroup_fd_array_put_ptr(void *ptr)
 582 {
 583         /* cgroup_put free cgrp after a rcu grace period */
 584         cgroup_put(ptr);
 585 }
 586
 587 static void cgroup_fd_array_free(struct bpf_map *map)
 588 {
 589         bpf_fd_array_map_clear(map);
 590         fd_array_map_free(map);
 591 }
 592
 593 static const struct bpf_map_ops cgroup_array_ops = {
 594         .map_alloc = fd_array_map_alloc,
 595         .map_free = cgroup_fd_array_free,
 596         .map_get_next_key = array_map_get_next_key,
 597         .map_lookup_elem = fd_array_map_lookup_elem,
 598         .map_delete_elem = fd_array_map_delete_elem,
 599         .map_fd_get_ptr = cgroup_fd_array_get_ptr,
 600         .map_fd_put_ptr = cgroup_fd_array_put_ptr,
 601 };
 602
 603 static struct bpf_map_type_list cgroup_array_type __read_mostly = {
 604         .ops = &cgroup_array_ops,
 605         .type = BPF_MAP_TYPE_CGROUP_ARRAY,
 606 };
 607
 608 static int __init register_cgroup_array_map(void)
 609 {
 610         bpf_register_map_type(&cgroup_array_type);
 611         return 0;
 612 }
 613 late_initcall(register_cgroup_array_map);
 614 #endif