kernel/bpf/stackmap.c

   1 /* Copyright (c) 2016 Facebook
   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 #include <linux/bpf.h>
   8 #include <linux/jhash.h>
   9 #include <linux/filter.h>
  10 #include <linux/stacktrace.h>
  11 #include <linux/perf_event.h>
  12 #include "percpu_freelist.h"
  13
  14 #define STACK_CREATE_FLAG_MASK \
  15         (BPF_F_NUMA_NODE | BPF_F_RDONLY | BPF_F_WRONLY)
  16
  17 struct stack_map_bucket {
  18         struct pcpu_freelist_node fnode;
  19         u32 hash;
  20         u32 nr;
  21         u64 ip[];
  22 };
  23
  24 struct bpf_stack_map {
  25         struct bpf_map map;
  26         void *elems;
  27         struct pcpu_freelist freelist;
  28         u32 n_buckets;
  29         struct stack_map_bucket *buckets[];
  30 };
  31
  32 static int prealloc_elems_and_freelist(struct bpf_stack_map *smap)
  33 {
  34         u32 elem_size = sizeof(struct stack_map_bucket) + smap->map.value_size;
  35         int err;
  36
  37         smap->elems = bpf_map_area_alloc(elem_size * smap->map.max_entries,
  38                                          smap->map.numa_node);
  39         if (!smap->elems)
  40                 return -ENOMEM;
  41
  42         err = pcpu_freelist_init(&smap->freelist);
  43         if (err)
  44                 goto free_elems;
  45
  46         pcpu_freelist_populate(&smap->freelist, smap->elems, elem_size,
  47                                smap->map.max_entries);
  48         return 0;
  49
  50 free_elems:
  51         bpf_map_area_free(smap->elems);
  52         return err;
  53 }
  54
  55 /* Called from syscall */
  56 static struct bpf_map *stack_map_alloc(union bpf_attr *attr)
  57 {
  58         u32 value_size = attr->value_size;
  59         struct bpf_stack_map *smap;
  60         u64 cost, n_buckets;
  61         int err;
  62
  63         if (!capable(CAP_SYS_ADMIN))
  64                 return ERR_PTR(-EPERM);
  65
  66         if (attr->map_flags & ~STACK_CREATE_FLAG_MASK)
  67                 return ERR_PTR(-EINVAL);
  68
  69         /* check sanity of attributes */
  70         if (attr->max_entries == 0 || attr->key_size != 4 ||
  71             value_size < 8 || value_size % 8 ||
  72             value_size / 8 > sysctl_perf_event_max_stack)
  73                 return ERR_PTR(-EINVAL);
  74
  75         /* hash table size must be power of 2 */
  76         n_buckets = roundup_pow_of_two(attr->max_entries);
  77
  78         cost = n_buckets * sizeof(struct stack_map_bucket *) + sizeof(*smap);
  79         if (cost >= U32_MAX - PAGE_SIZE)
  80                 return ERR_PTR(-E2BIG);
  81
  82         smap = bpf_map_area_alloc(cost, bpf_map_attr_numa_node(attr));
  83         if (!smap)
  84                 return ERR_PTR(-ENOMEM);
  85
  86         err = -E2BIG;
  87         cost += n_buckets * (value_size + sizeof(struct stack_map_bucket));
  88         if (cost >= U32_MAX - PAGE_SIZE)
  89                 goto free_smap;
  90
  91         bpf_map_init_from_attr(&smap->map, attr);
  92         smap->map.value_size = value_size;
  93         smap->n_buckets = n_buckets;
  94         smap->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;
  95
  96         err = bpf_map_precharge_memlock(smap->map.pages);
  97         if (err)
  98                 goto free_smap;
  99
 100         err = get_callchain_buffers(sysctl_perf_event_max_stack);
 101         if (err)
 102                 goto free_smap;
 103
 104         err = prealloc_elems_and_freelist(smap);
 105         if (err)
 106                 goto put_buffers;
 107
 108         return &smap->map;
 109
 110 put_buffers:
 111         put_callchain_buffers();
 112 free_smap:
 113         bpf_map_area_free(smap);
 114         return ERR_PTR(err);
 115 }
 116
 117 BPF_CALL_3(bpf_get_stackid, struct pt_regs *, regs, struct bpf_map *, map,
 118            u64, flags)
 119 {
 120         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
 121         struct perf_callchain_entry *trace;
 122         struct stack_map_bucket *bucket, *new_bucket, *old_bucket;
 123         u32 max_depth = map->value_size / 8;
 124         /* stack_map_alloc() checks that max_depth <= sysctl_perf_event_max_stack */
 125         u32 init_nr = sysctl_perf_event_max_stack - max_depth;
 126         u32 skip = flags & BPF_F_SKIP_FIELD_MASK;
 127         u32 hash, id, trace_nr, trace_len;
 128         bool user = flags & BPF_F_USER_STACK;
 129         bool kernel = !user;
 130         u64 *ips;
 131
 132         if (unlikely(flags & ~(BPF_F_SKIP_FIELD_MASK | BPF_F_USER_STACK |
 133                                BPF_F_FAST_STACK_CMP | BPF_F_REUSE_STACKID)))
 134                 return -EINVAL;
 135
 136         trace = get_perf_callchain(regs, init_nr, kernel, user,
 137                                    sysctl_perf_event_max_stack, false, false);
 138
 139         if (unlikely(!trace))
 140                 /* couldn't fetch the stack trace */
 141                 return -EFAULT;
 142
 143         /* get_perf_callchain() guarantees that trace->nr >= init_nr
 144          * and trace-nr <= sysctl_perf_event_max_stack, so trace_nr <= max_depth
 145          */
 146         trace_nr = trace->nr - init_nr;
 147
 148         if (trace_nr <= skip)
 149                 /* skipping more than usable stack trace */
 150                 return -EFAULT;
 151
 152         trace_nr -= skip;
 153         trace_len = trace_nr * sizeof(u64);
 154         ips = trace->ip + skip + init_nr;
 155         hash = jhash2((u32 *)ips, trace_len / sizeof(u32), 0);
 156         id = hash & (smap->n_buckets - 1);
 157         bucket = READ_ONCE(smap->buckets[id]);
 158
 159         if (bucket && bucket->hash == hash) {
 160                 if (flags & BPF_F_FAST_STACK_CMP)
 161                         return id;
 162                 if (bucket->nr == trace_nr &&
 163                     memcmp(bucket->ip, ips, trace_len) == 0)
 164                         return id;
 165         }
 166
 167         /* this call stack is not in the map, try to add it */
 168         if (bucket && !(flags & BPF_F_REUSE_STACKID))
 169                 return -EEXIST;
 170
 171         new_bucket = (struct stack_map_bucket *)
 172                 pcpu_freelist_pop(&smap->freelist);
 173         if (unlikely(!new_bucket))
 174                 return -ENOMEM;
 175
 176         memcpy(new_bucket->ip, ips, trace_len);
 177         new_bucket->hash = hash;
 178         new_bucket->nr = trace_nr;
 179
 180         old_bucket = xchg(&smap->buckets[id], new_bucket);
 181         if (old_bucket)
 182                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
 183         return id;
 184 }
 185
 186 const struct bpf_func_proto bpf_get_stackid_proto = {
 187         .func           = bpf_get_stackid,
 188         .gpl_only       = true,
 189         .ret_type       = RET_INTEGER,
 190         .arg1_type      = ARG_PTR_TO_CTX,
 191         .arg2_type      = ARG_CONST_MAP_PTR,
 192         .arg3_type      = ARG_ANYTHING,
 193 };
 194
 195 /* Called from eBPF program */
 196 static void *stack_map_lookup_elem(struct bpf_map *map, void *key)
 197 {
 198         return NULL;
 199 }
 200
 201 /* Called from syscall */
 202 int bpf_stackmap_copy(struct bpf_map *map, void *key, void *value)
 203 {
 204         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
 205         struct stack_map_bucket *bucket, *old_bucket;
 206         u32 id = *(u32 *)key, trace_len;
 207
 208         if (unlikely(id >= smap->n_buckets))
 209                 return -ENOENT;
 210
 211         bucket = xchg(&smap->buckets[id], NULL);
 212         if (!bucket)
 213                 return -ENOENT;
 214
 215         trace_len = bucket->nr * sizeof(u64);
 216         memcpy(value, bucket->ip, trace_len);
 217         memset(value + trace_len, 0, map->value_size - trace_len);
 218
 219         old_bucket = xchg(&smap->buckets[id], bucket);
 220         if (old_bucket)
 221                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
 222         return 0;
 223 }
 224
 225 static int stack_map_get_next_key(struct bpf_map *map, void *key,
 226                                   void *next_key)
 227 {
 228         struct bpf_stack_map *smap = container_of(map,
 229                                                   struct bpf_stack_map, map);
 230         u32 id;
 231
 232         WARN_ON_ONCE(!rcu_read_lock_held());
 233
 234         if (!key) {
 235                 id = 0;
 236         } else {
 237                 id = *(u32 *)key;
 238                 if (id >= smap->n_buckets || !smap->buckets[id])
 239                         id = 0;
 240                 else
 241                         id++;
 242         }
 243
 244         while (id < smap->n_buckets && !smap->buckets[id])
 245                 id++;
 246
 247         if (id >= smap->n_buckets)
 248                 return -ENOENT;
 249
 250         *(u32 *)next_key = id;
 251         return 0;
 252 }
 253
 254 static int stack_map_update_elem(struct bpf_map *map, void *key, void *value,
 255                                  u64 map_flags)
 256 {
 257         return -EINVAL;
 258 }
 259
 260 /* Called from syscall or from eBPF program */
 261 static int stack_map_delete_elem(struct bpf_map *map, void *key)
 262 {
 263         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
 264         struct stack_map_bucket *old_bucket;
 265         u32 id = *(u32 *)key;
 266
 267         if (unlikely(id >= smap->n_buckets))
 268                 return -E2BIG;
 269
 270         old_bucket = xchg(&smap->buckets[id], NULL);
 271         if (old_bucket) {
 272                 pcpu_freelist_push(&smap->freelist, &old_bucket->fnode);
 273                 return 0;
 274         } else {
 275                 return -ENOENT;
 276         }
 277 }
 278
 279 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
 280 static void stack_map_free(struct bpf_map *map)
 281 {
 282         struct bpf_stack_map *smap = container_of(map, struct bpf_stack_map, map);
 283
 284         /* wait for bpf programs to complete before freeing stack map */
 285         synchronize_rcu();
 286
 287         bpf_map_area_free(smap->elems);
 288         pcpu_freelist_destroy(&smap->freelist);
 289         bpf_map_area_free(smap);
 290         put_callchain_buffers();
 291 }
 292
 293 const struct bpf_map_ops stack_map_ops = {
 294         .map_alloc = stack_map_alloc,
 295         .map_free = stack_map_free,
 296         .map_get_next_key = stack_map_get_next_key,
 297         .map_lookup_elem = stack_map_lookup_elem,
 298         .map_update_elem = stack_map_update_elem,
 299         .map_delete_elem = stack_map_delete_elem,
 300 };