bpf: add array type of eBPF maps
authorAlexei Starovoitov <ast@plumgrid.com>
Fri, 14 Nov 2014 01:36:46 +0000 (17:36 -0800)
committerDavid S. Miller <davem@davemloft.net>
Tue, 18 Nov 2014 18:43:59 +0000 (13:43 -0500)
commit28fbcfa08d8ed7c5a50d41a0433aad222835e8e3
tree1ef9417be1eb51e76456b3f2dbaf080c48883c32
parent0f8e4bd8a1fc8c4185f1630061d0a1f2d197a475
bpf: add array type of eBPF maps

add new map type BPF_MAP_TYPE_ARRAY and its implementation

- optimized for fastest possible lookup()
  . in the future verifier/JIT may recognize lookup() with constant key
    and optimize it into constant pointer. Can optimize non-constant
    key into direct pointer arithmetic as well, since pointers and
    value_size are constant for the life of the eBPF program.
    In other words array_map_lookup_elem() may be 'inlined' by verifier/JIT
    while preserving concurrent access to this map from user space

- two main use cases for array type:
  . 'global' eBPF variables: array of 1 element with key=0 and value is a
    collection of 'global' variables which programs can use to keep the state
    between events
  . aggregation of tracing events into fixed set of buckets

- all array elements pre-allocated and zero initialized at init time

- key as an index in array and can only be 4 byte

- map_delete_elem() returns EINVAL, since elements cannot be deleted

- map_update_elem() replaces elements in an non-atomic way
  (for atomic updates hashtable type should be used instead)

Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/uapi/linux/bpf.h
kernel/bpf/Makefile
kernel/bpf/arraymap.c [new file with mode: 0644]