Netdev Archive on lore.kernel.org
 help / color / Atom feed
From: Alexei Starovoitov <ast@kernel.org>
To: <davem@davemloft.net>
Cc: <daniel@iogearbox.net>, <peterz@infradead.org>,
	<jannh@google.com>, <netdev@vger.kernel.org>,
	<kernel-team@fb.com>
Subject: [PATCH v7 bpf-next 0/9] introduce bpf_spin_lock
Date: Thu, 31 Jan 2019 15:40:03 -0800
Message-ID: <20190131234012.3712779-1-ast@kernel.org> (raw)

Many algorithms need to read and modify several variables atomically.
Until now it was hard to impossible to implement such algorithms in BPF.
Hence introduce support for bpf_spin_lock.

The api consists of 'struct bpf_spin_lock' that should be placed
inside hash/array/cgroup_local_storage element
and bpf_spin_lock/unlock() helper function.

Example:
struct hash_elem {
    int cnt;
    struct bpf_spin_lock lock;
};
struct hash_elem * val = bpf_map_lookup_elem(&hash_map, &key);
if (val) {
    bpf_spin_lock(&val->lock);
    val->cnt++;
    bpf_spin_unlock(&val->lock);
}

and BPF_F_LOCK flag for lookup/update bpf syscall commands that
allows user space to read/write map elements under lock.

Together these primitives allow race free access to map elements
from bpf programs and from user space.

Key restriction: root only.
Key requirement: maps must be annotated with BTF.

This concept was discussed at Linux Plumbers Conference 2018.
Thank you everyone who participated and helped to iron out details
of api and implementation.

Patch 1: bpf_spin_lock support in the verifier, BTF, hash, array.
Patch 2: bpf_spin_lock in cgroup local storage.
Patches 3,4,5: tests
Patch 6: BPF_F_LOCK flag to lookup/update
Patches 7,8,9: tests

v6->v7:
- fixed this_cpu->__this_cpu per Peter's suggestion and added Ack.
- simplified bpf_spin_lock and load/store overlap check in the verifier
  as suggested by Andrii
- rebase

v5->v6:
- adopted arch_spinlock approach suggested by Peter
- switched to spin_lock_irqsave equivalent as the simplest way
  to avoid deadlocks in rare case of nested networking progs
  (cgroup-bpf prog in preempt_disable vs clsbpf in softirq sharing
  the same map with bpf_spin_lock)
  bpf_spin_lock is only allowed in networking progs that don't
  have arbitrary entry points unlike tracing progs.
- rebase and split test_verifier tests

v4->v5:
- disallow bpf_spin_lock for tracing progs due to insufficient preemption checks
- socket filter progs cannot use bpf_spin_lock due to missing preempt_disable
- fix atomic_set_release. Spotted by Peter.
- fixed hash_of_maps
  
v3->v4:
- fix BPF_EXIST | BPF_NOEXIST check patch 6. Spotted by Jakub. Thanks!
- rebase

v2->v3:
- fixed build on ia64 and archs where qspinlock is not supported
- fixed missing lock init during lookup w/o BPF_F_LOCK. Spotted by Martin

v1->v2:
- addressed several issues spotted by Daniel and Martin in patch 1
- added test11 to patch 4 as suggested by Daniel

Alexei Starovoitov (9):
  bpf: introduce bpf_spin_lock
  bpf: add support for bpf_spin_lock to cgroup local storage
  tools/bpf: sync include/uapi/linux/bpf.h
  selftests/bpf: add bpf_spin_lock verifier tests
  selftests/bpf: add bpf_spin_lock C test
  bpf: introduce BPF_F_LOCK flag
  tools/bpf: sync uapi/bpf.h
  libbpf: introduce bpf_map_lookup_elem_flags()
  selftests/bpf: test for BPF_F_LOCK

 include/linux/bpf.h                           |  39 ++-
 include/linux/bpf_verifier.h                  |   1 +
 include/linux/btf.h                           |   1 +
 include/uapi/linux/bpf.h                      |   8 +-
 kernel/Kconfig.locks                          |   3 +
 kernel/bpf/arraymap.c                         |  23 +-
 kernel/bpf/btf.c                              |  42 +++
 kernel/bpf/core.c                             |   2 +
 kernel/bpf/hashtab.c                          |  63 +++-
 kernel/bpf/helpers.c                          |  96 +++++
 kernel/bpf/local_storage.c                    |  16 +-
 kernel/bpf/map_in_map.c                       |   5 +
 kernel/bpf/syscall.c                          |  45 ++-
 kernel/bpf/verifier.c                         | 171 ++++++++-
 net/core/filter.c                             |  16 +-
 tools/include/uapi/linux/bpf.h                |   8 +-
 tools/lib/bpf/bpf.c                           |  13 +
 tools/lib/bpf/bpf.h                           |   2 +
 tools/lib/bpf/libbpf.map                      |   1 +
 tools/testing/selftests/bpf/Makefile          |   2 +-
 tools/testing/selftests/bpf/bpf_helpers.h     |   4 +
 tools/testing/selftests/bpf/test_map_lock.c   |  66 ++++
 tools/testing/selftests/bpf/test_progs.c      | 117 ++++++-
 tools/testing/selftests/bpf/test_spin_lock.c  | 108 ++++++
 tools/testing/selftests/bpf/test_verifier.c   | 104 +++++-
 .../selftests/bpf/verifier/spin_lock.c        | 331 ++++++++++++++++++
 26 files changed, 1248 insertions(+), 39 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/test_map_lock.c
 create mode 100644 tools/testing/selftests/bpf/test_spin_lock.c
 create mode 100644 tools/testing/selftests/bpf/verifier/spin_lock.c

-- 
2.20.0


             reply index

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-31 23:40 Alexei Starovoitov [this message]
2019-01-31 23:40 ` [PATCH v7 bpf-next 1/9] bpf: " Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 2/9] bpf: add support for bpf_spin_lock to cgroup local storage Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 3/9] tools/bpf: sync include/uapi/linux/bpf.h Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 4/9] selftests/bpf: add bpf_spin_lock verifier tests Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 5/9] selftests/bpf: add bpf_spin_lock C test Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 6/9] bpf: introduce BPF_F_LOCK flag Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 7/9] tools/bpf: sync uapi/bpf.h Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 8/9] libbpf: introduce bpf_map_lookup_elem_flags() Alexei Starovoitov
2019-01-31 23:40 ` [PATCH v7 bpf-next 9/9] selftests/bpf: test for BPF_F_LOCK Alexei Starovoitov
2019-02-01 20:07 ` [PATCH v7 bpf-next 0/9] introduce bpf_spin_lock Daniel Borkmann

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190131234012.3712779-1-ast@kernel.org \
    --to=ast@kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=davem@davemloft.net \
    --cc=jannh@google.com \
    --cc=kernel-team@fb.com \
    --cc=netdev@vger.kernel.org \
    --cc=peterz@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Netdev Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/netdev/0 netdev/git/0.git
	git clone --mirror https://lore.kernel.org/netdev/1 netdev/git/1.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 netdev netdev/ https://lore.kernel.org/netdev \
		netdev@vger.kernel.org
	public-inbox-index netdev

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.netdev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git