bpf: Add percpu LRU list
authorMartin KaFai Lau <kafai@fb.com>
Fri, 11 Nov 2016 18:55:07 +0000 (10:55 -0800)
committerDavid S. Miller <davem@davemloft.net>
Tue, 15 Nov 2016 16:50:20 +0000 (11:50 -0500)
commit961578b63474d13ad0e2f615fcc2901c5197dda6
treeacdc59cde6cd08002b0495e0c862db461b7fb63f
parent3a08c2fd763450a927d1130de078d6f9e74944fb
bpf: Add percpu LRU list

Instead of having a common LRU list, this patch allows a
percpu LRU list which can be selected by specifying a map
attribute.  The map attribute will be added in the later
patch.

While the common use case for LRU is #reads >> #updates,
percpu LRU list allows bpf prog to absorb unusual #updates
under pathological case (e.g. external traffic facing machine which
could be under attack).

Each percpu LRU is isolated from each other.  The LRU nodes (including
free nodes) cannot be moved across different LRU Lists.

Here are the update performance comparison between
common LRU list and percpu LRU list (the test code is
at the last patch):

[root@kerneltest003.31.prn1 ~]# for i in 1 4 8; do echo -n "$i cpus: "; \
./map_perf_test 16 $i | awk '{r += $3}END{print r " updates"}'; done
 1 cpus: 2934082 updates
 4 cpus: 7391434 updates
 8 cpus: 6500576 updates

[root@kerneltest003.31.prn1 ~]# for i in 1 4 8; do echo -n "$i cpus: "; \
./map_perf_test 32 $i | awk '{r += $3}END{printr " updates"}'; done
  1 cpus: 2896553 updates
  4 cpus: 9766395 updates
  8 cpus: 17460553 updates

Signed-off-by: Martin KaFai Lau <kafai@fb.com>
Acked-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: David S. Miller <davem@davemloft.net>
kernel/bpf/bpf_lru_list.c
kernel/bpf/bpf_lru_list.h