bpf: add queue and stack maps

Queue/stack maps implement a FIFO/LIFO data storage for ebpf programs.
These maps support peek, pop and push operations that are exposed to eBPF
programs through the new bpf_map[peek/pop/push] helpers.  Those operations
are exposed to userspace applications through the already existing
syscalls in the following way:

BPF_MAP_LOOKUP_ELEM            -> peek
BPF_MAP_LOOKUP_AND_DELETE_ELEM -> pop
BPF_MAP_UPDATE_ELEM            -> push

Queue/stack maps are implemented using a buffer, tail and head indexes,
hence BPF_F_NO_PREALLOC is not supported.

As opposite to other maps, queue and stack do not use RCU for protecting
maps values, the bpf_map[peek/pop] have a ARG_PTR_TO_UNINIT_MAP_VALUE
argument that is a pointer to a memory zone where to save the value of a
map.  Basically the same as ARG_PTR_TO_UNINIT_MEM, but the size has not
be passed as an extra argument.

Our main motivation for implementing queue/stack maps was to keep track
of a pool of elements, like network ports in a SNAT, however we forsee
other use cases, like for exampling saving last N kernel events in a map
and then analysing from userspace.

Signed-off-by: Mauricio Vasquez B <mauricio.vasquez@polito.it>
Acked-by: Song Liu <songliubraving@fb.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

1 files changed, 6 insertions, 0 deletions

diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 78d9dd95e25f..1617407f9ee5 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -727,6 +727,9 @@ static int map_lookup_elem(union bpf_attr *attr)
                 err = bpf_fd_htab_map_lookup_elem(map, key, value);
         } else if (map->map_type == BPF_MAP_TYPE_REUSEPORT_SOCKARRAY) {
                 err = bpf_fd_reuseport_array_lookup_elem(map, key, value);
+        } else if (map->map_type == BPF_MAP_TYPE_QUEUE ||
+                   map->map_type == BPF_MAP_TYPE_STACK) {
+                err = map->ops->map_peek_elem(map, value);
         } else {
                 rcu_read_lock();
                 ptr = map->ops->map_lookup_elem(map, key);
@@ -857,6 +860,9 @@ static int map_update_elem(union bpf_attr *attr)
                 /* rcu_read_lock() is not needed */
                 err = bpf_fd_reuseport_array_update_elem(map, key, value,
                                                          attr->flags);
+        } else if (map->map_type == BPF_MAP_TYPE_QUEUE ||
+                   map->map_type == BPF_MAP_TYPE_STACK) {
+                err = map->ops->map_push_elem(map, value, attr->flags);
         } else {
                 rcu_read_lock();
                 err = map->ops->map_update_elem(map, key, value, attr->flags);