bpf: add hashtable type of eBPF maps
authorAlexei Starovoitov <ast@plumgrid.com>
Fri, 14 Nov 2014 01:36:45 +0000 (17:36 -0800)
committerDavid S. Miller <davem@davemloft.net>
Tue, 18 Nov 2014 18:43:25 +0000 (13:43 -0500)
commit0f8e4bd8a1fc8c4185f1630061d0a1f2d197a475
tree8f78f12dad4d5188019cba0456186ecced42c073
parent3274f52073d88b62f3c5ace82ae9d48546232e72
bpf: add hashtable type of eBPF maps

add new map type BPF_MAP_TYPE_HASH and its implementation

- maps are created/destroyed by userspace. Both userspace and eBPF programs
  can lookup/update/delete elements from the map

- eBPF programs can be called in_irq(), so use spin_lock_irqsave() mechanism
  for concurrent updates

- key/value are opaque range of bytes (aligned to 8 bytes)

- user space provides 3 configuration attributes via BPF syscall:
  key_size, value_size, max_entries

- map takes care of allocating/freeing key/value pairs

- map_update_elem() must fail to insert new element when max_entries
  limit is reached to make sure that eBPF programs cannot exhaust memory

- map_update_elem() replaces elements in an atomic way

- optimized for speed of lookup() which can be called multiple times from
  eBPF program which itself is triggered by high volume of events
  . in the future JIT compiler may recognize lookup() call and optimize it
    further, since key_size is constant for life of eBPF program

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/hashtab.c [new file with mode: 0644]