kernel/bpf/arraymap.c

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