All of lore.kernel.org
 help / color / mirror / Atom feed
From: Yonghong Song <yhs@fb.com>
To: Brendan Jackman <jackmanb@google.com>, <bpf@vger.kernel.org>
Cc: Alexei Starovoitov <ast@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	KP Singh <kpsingh@chromium.org>,
	Florent Revest <revest@chromium.org>,
	<linux-kernel@vger.kernel.org>, Jann Horn <jannh@google.com>
Subject: Re: [PATCH bpf-next v3 10/14] bpf: Add bitwise atomic instructions
Date: Thu, 3 Dec 2020 22:42:19 -0800	[thread overview]
Message-ID: <86a88eba-83a1-93c0-490d-ceba238e3aad@fb.com> (raw)
In-Reply-To: <20201203160245.1014867-11-jackmanb@google.com>



On 12/3/20 8:02 AM, Brendan Jackman wrote:
> This adds instructions for
> 
> atomic[64]_[fetch_]and
> atomic[64]_[fetch_]or
> atomic[64]_[fetch_]xor
> 
> All these operations are isomorphic enough to implement with the same
> verifier, interpreter, and x86 JIT code, hence being a single commit.
> 
> The main interesting thing here is that x86 doesn't directly support
> the fetch_ version these operations, so we need to generate a CMPXCHG
> loop in the JIT. This requires the use of two temporary registers,
> IIUC it's safe to use BPF_REG_AX and x86's AUX_REG for this purpose.
> 
> Change-Id: I340b10cecebea8cb8a52e3606010cde547a10ed4
> Signed-off-by: Brendan Jackman <jackmanb@google.com>
> ---
>   arch/x86/net/bpf_jit_comp.c  | 50 +++++++++++++++++++++++++++++-
>   include/linux/filter.h       | 60 ++++++++++++++++++++++++++++++++++++
>   kernel/bpf/core.c            |  5 ++-
>   kernel/bpf/disasm.c          | 21 ++++++++++---
>   kernel/bpf/verifier.c        |  6 ++++
>   tools/include/linux/filter.h | 60 ++++++++++++++++++++++++++++++++++++
>   6 files changed, 196 insertions(+), 6 deletions(-)
> 
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index 7d29bc3bb4ff..4ab0f821326c 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -824,6 +824,10 @@ static int emit_atomic(u8 **pprog, u8 atomic_op,
>   	/* emit opcode */
>   	switch (atomic_op) {
>   	case BPF_ADD:
> +	case BPF_SUB:
> +	case BPF_AND:
> +	case BPF_OR:
> +	case BPF_XOR:
>   		/* lock *(u32/u64*)(dst_reg + off) <op>= src_reg */
>   		EMIT1(simple_alu_opcodes[atomic_op]);
>   		break;
> @@ -1306,8 +1310,52 @@ st:			if (is_imm8(insn->off))
>   
>   		case BPF_STX | BPF_ATOMIC | BPF_W:
>   		case BPF_STX | BPF_ATOMIC | BPF_DW:
> +			if (insn->imm == (BPF_AND | BPF_FETCH) ||
> +			    insn->imm == (BPF_OR | BPF_FETCH) ||
> +			    insn->imm == (BPF_XOR | BPF_FETCH)) {
> +				u8 *branch_target;
> +				bool is64 = BPF_SIZE(insn->code) == BPF_DW;
> +
> +				/*
> +				 * Can't be implemented with a single x86 insn.
> +				 * Need to do a CMPXCHG loop.
> +				 */
> +
> +				/* Will need RAX as a CMPXCHG operand so save R0 */
> +				emit_mov_reg(&prog, true, BPF_REG_AX, BPF_REG_0);
> +				branch_target = prog;
> +				/* Load old value */
> +				emit_ldx(&prog, BPF_SIZE(insn->code),
> +					 BPF_REG_0, dst_reg, insn->off);
> +				/*
> +				 * Perform the (commutative) operation locally,
> +				 * put the result in the AUX_REG.
> +				 */
> +				emit_mov_reg(&prog, is64, AUX_REG, BPF_REG_0);
> +				maybe_emit_mod(&prog, AUX_REG, src_reg, is64);
> +				EMIT2(simple_alu_opcodes[BPF_OP(insn->imm)],
> +				      add_2reg(0xC0, AUX_REG, src_reg));
> +				/* Attempt to swap in new value */
> +				err = emit_atomic(&prog, BPF_CMPXCHG,
> +						  dst_reg, AUX_REG, insn->off,
> +						  BPF_SIZE(insn->code));
> +				if (WARN_ON(err))
> +					return err;
> +				/*
> +				 * ZF tells us whether we won the race. If it's
> +				 * cleared we need to try again.
> +				 */
> +				EMIT2(X86_JNE, -(prog - branch_target) - 2);
> +				/* Return the pre-modification value */
> +				emit_mov_reg(&prog, is64, src_reg, BPF_REG_0);
> +				/* Restore R0 after clobbering RAX */
> +				emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
> +				break;
> +
> +			}
> +
>   			err = emit_atomic(&prog, insn->imm, dst_reg, src_reg,
> -					  insn->off, BPF_SIZE(insn->code));
> +						  insn->off, BPF_SIZE(insn->code));
>   			if (err)
>   				return err;
>   			break;
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index 6186280715ed..698f82897b0d 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -280,6 +280,66 @@ static inline bool insn_is_zext(const struct bpf_insn *insn)
>   		.off   = OFF,					\
>   		.imm   = BPF_ADD | BPF_FETCH })
>   
> +/* Atomic memory and, *(uint *)(dst_reg + off16) &= src_reg */
> +
> +#define BPF_ATOMIC_AND(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_AND })
> +
> +/* Atomic memory and with fetch, src_reg = atomic_fetch_and(*(dst_reg + off), src_reg); */

src_reg = atomic_fetch_and(dst_reg + off, src_reg)?

> +
> +#define BPF_ATOMIC_FETCH_AND(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_AND | BPF_FETCH })
> +
> +/* Atomic memory or, *(uint *)(dst_reg + off16) |= src_reg */
> +
> +#define BPF_ATOMIC_OR(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_OR })
> +
> +/* Atomic memory or with fetch, src_reg = atomic_fetch_or(*(dst_reg + off), src_reg); */

src_reg = atomic_fetch_or(dst_reg + off, src_reg)?

> +
> +#define BPF_ATOMIC_FETCH_OR(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_OR | BPF_FETCH })
> +
> +/* Atomic memory xor, *(uint *)(dst_reg + off16) ^= src_reg */
> +
> +#define BPF_ATOMIC_XOR(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_XOR })
> +
> +/* Atomic memory xor with fetch, src_reg = atomic_fetch_xor(*(dst_reg + off), src_reg); */

src_reg = atomic_fetch_xor(dst_reg + off, src_reg)?

> +
> +#define BPF_ATOMIC_FETCH_XOR(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_XOR | BPF_FETCH })
> +
>   /* Atomic exchange, src_reg = atomic_xchg((dst_reg + off), src_reg) */
>   

Looks like BPF_ATOMIC_XOR/OR/AND/... all similar to each other.
The same is for BPF_ATOMIC_FETCH_XOR/OR/AND/...

I am wondering whether it makes sence to have to
BPF_ATOMIC_BOP(BOP, SIZE, DST, SRC, OFF) and
BPF_ATOMIC_FETCH_BOP(BOP, SIZE, DST, SRC, OFF)
can have less number of macros?

>   #define BPF_ATOMIC_XCHG(SIZE, DST, SRC, OFF)			\
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 498d3f067be7..27eac4d5724c 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -1642,7 +1642,10 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)
>   	STX_ATOMIC_W:
>   		switch (IMM) {
>   		ATOMIC(BPF_ADD, add)
> -
> +		ATOMIC(BPF_AND, and)
> +		ATOMIC(BPF_OR, or)
> +		ATOMIC(BPF_XOR, xor)
> +#undef ATOMIC
>   		case BPF_XCHG:
>   			if (BPF_SIZE(insn->code) == BPF_W)
>   				SRC = (u32) atomic_xchg(
> diff --git a/kernel/bpf/disasm.c b/kernel/bpf/disasm.c
> index 18357ea9a17d..0c7c1c31a57b 100644
> --- a/kernel/bpf/disasm.c
> +++ b/kernel/bpf/disasm.c
> @@ -80,6 +80,13 @@ const char *const bpf_alu_string[16] = {
>   	[BPF_END >> 4]  = "endian",
>   };
>   
> +static const char *const bpf_atomic_alu_string[16] = {
> +	[BPF_ADD >> 4]  = "add",
> +	[BPF_AND >> 4]  = "and",
> +	[BPF_OR >> 4]  = "or",
> +	[BPF_XOR >> 4]  = "or",
> +};
> +
>   static const char *const bpf_ldst_string[] = {
>   	[BPF_W >> 3]  = "u32",
>   	[BPF_H >> 3]  = "u16",
> @@ -154,17 +161,23 @@ void print_bpf_insn(const struct bpf_insn_cbs *cbs,
>   				insn->dst_reg,
>   				insn->off, insn->src_reg);
>   		else if (BPF_MODE(insn->code) == BPF_ATOMIC &&
> -			 insn->imm == BPF_ADD) {
> -			verbose(cbs->private_data, "(%02x) lock *(%s *)(r%d %+d) += r%d\n",
> +			 (insn->imm == BPF_ADD || insn->imm == BPF_ADD ||
> +			  insn->imm == BPF_OR || insn->imm == BPF_XOR)) {
> +			verbose(cbs->private_data, "(%02x) lock *(%s *)(r%d %+d) %s r%d\n",
>   				insn->code,
>   				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
>   				insn->dst_reg, insn->off,
> +				bpf_alu_string[BPF_OP(insn->imm) >> 4],
>   				insn->src_reg);
>   		} else if (BPF_MODE(insn->code) == BPF_ATOMIC &&
> -			   insn->imm == (BPF_ADD | BPF_FETCH)) {
> -			verbose(cbs->private_data, "(%02x) r%d = atomic%s_fetch_add(*(%s *)(r%d %+d), r%d)\n",

(%02x) r%d = atomic%s_fetch_add((%s *)(r%d %+d), r%d)?

> +			   (insn->imm == (BPF_ADD | BPF_FETCH) ||
> +			    insn->imm == (BPF_AND | BPF_FETCH) ||
> +			    insn->imm == (BPF_OR | BPF_FETCH) ||
> +			    insn->imm == (BPF_XOR | BPF_FETCH)))  > +			verbose(cbs->private_data, "(%02x) r%d = atomic%s_fetch_%s(*(%s 
*)(r%d %+d), r%d)\n",

(%02x) r%d = atomic%s_fetch_%s((%s *)(r%d %+d), r%d)?

>   				insn->code, insn->src_reg,
>   				BPF_SIZE(insn->code) == BPF_DW ? "64" : "",
> +				bpf_atomic_alu_string[BPF_OP(insn->imm) >> 4],
>   				bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
>   				insn->dst_reg, insn->off, insn->src_reg);
>   		} else if (BPF_MODE(insn->code) == BPF_ATOMIC &&
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ccf4315e54e7..dd30eb9a6c1b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3606,6 +3606,12 @@ static int check_atomic(struct bpf_verifier_env *env, int insn_idx, struct bpf_i
>   	switch (insn->imm) {
>   	case BPF_ADD:
>   	case BPF_ADD | BPF_FETCH:
> +	case BPF_AND:
> +	case BPF_AND | BPF_FETCH:
> +	case BPF_OR:
> +	case BPF_OR | BPF_FETCH:
> +	case BPF_XOR:
> +	case BPF_XOR | BPF_FETCH:
>   	case BPF_XCHG:
>   	case BPF_CMPXCHG:
>   		break;
> diff --git a/tools/include/linux/filter.h b/tools/include/linux/filter.h
> index ea99bd17d003..b74febf83eb1 100644
> --- a/tools/include/linux/filter.h
> +++ b/tools/include/linux/filter.h
> @@ -190,6 +190,66 @@
>   		.off   = OFF,					\
>   		.imm   = BPF_ADD | BPF_FETCH })
>   
> +/* Atomic memory and, *(uint *)(dst_reg + off16) -= src_reg */
> +
> +#define BPF_ATOMIC_AND(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_AND })
> +
> +/* Atomic memory and with fetch, src_reg = atomic_fetch_and(*(dst_reg + off), src_reg); */
> +
> +#define BPF_ATOMIC_FETCH_AND(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_AND | BPF_FETCH })
> +
> +/* Atomic memory or, *(uint *)(dst_reg + off16) -= src_reg */
> +
> +#define BPF_ATOMIC_OR(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_OR })
> +
> +/* Atomic memory or with fetch, src_reg = atomic_fetch_or(*(dst_reg + off), src_reg); */
> +
> +#define BPF_ATOMIC_FETCH_OR(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_OR | BPF_FETCH })
> +
> +/* Atomic memory xor, *(uint *)(dst_reg + off16) -= src_reg */
> +
> +#define BPF_ATOMIC_XOR(SIZE, DST, SRC, OFF)			\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_XOR })
> +
> +/* Atomic memory xor with fetch, src_reg = atomic_fetch_xor(*(dst_reg + off), src_reg); */
> +
> +#define BPF_ATOMIC_FETCH_XOR(SIZE, DST, SRC, OFF)		\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_ATOMIC,	\
> +		.dst_reg = DST,					\
> +		.src_reg = SRC,					\
> +		.off   = OFF,					\
> +		.imm   = BPF_XOR | BPF_FETCH })
> +
>   /* Atomic exchange, src_reg = atomic_xchg((dst_reg + off), src_reg) */
>   
>   #define BPF_ATOMIC_XCHG(SIZE, DST, SRC, OFF)			\
> 

  reply	other threads:[~2020-12-04  6:43 UTC|newest]

Thread overview: 46+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-12-03 16:02 [PATCH bpf-next v3 00/14] Atomics for eBPF Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 01/14] bpf: x86: Factor out emission of ModR/M for *(reg + off) Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 02/14] bpf: x86: Factor out emission of REX byte Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 03/14] bpf: x86: Factor out function to emit NEG Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 04/14] bpf: x86: Factor out a lookup table for some ALU opcodes Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 05/14] bpf: Rename BPF_XADD and prepare to encode other atomics in .imm Brendan Jackman
2020-12-04  4:49   ` Yonghong Song
2020-12-03 16:02 ` [PATCH bpf-next v3 06/14] bpf: Move BPF_STX reserved field check into BPF_STX verifier code Brendan Jackman
2020-12-04  4:51   ` Yonghong Song
2020-12-03 16:02 ` [PATCH bpf-next v3 07/14] bpf: Add BPF_FETCH field / create atomic_fetch_add instruction Brendan Jackman
2020-12-04  5:02   ` Yonghong Song
2020-12-04  5:27   ` Yonghong Song
2020-12-04  9:12     ` Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 08/14] bpf: Add instructions for atomic_[cmp]xchg Brendan Jackman
2020-12-04  5:34   ` Yonghong Song
2020-12-04  9:26     ` Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 09/14] bpf: Pull out a macro for interpreting atomic ALU operations Brendan Jackman
2020-12-04  6:30   ` Yonghong Song
2020-12-04  9:29     ` Brendan Jackman
2020-12-04 15:20       ` Yonghong Song
2020-12-03 16:02 ` [PATCH bpf-next v3 10/14] bpf: Add bitwise atomic instructions Brendan Jackman
2020-12-04  6:42   ` Yonghong Song [this message]
2020-12-04  9:36     ` Brendan Jackman
2020-12-04 15:21       ` Yonghong Song
2020-12-07 11:28         ` Brendan Jackman
2020-12-07 15:58           ` Yonghong Song
2020-12-07 16:14             ` Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 11/14] tools build: Implement feature check for BPF atomics in Clang Brendan Jackman
2020-12-03 21:02   ` Andrii Nakryiko
2020-12-03 16:02 ` [PATCH bpf-next v3 12/14] bpf: Pull tools/build/feature biz into selftests Makefile Brendan Jackman
2020-12-03 21:01   ` Andrii Nakryiko
2020-12-04  9:41     ` Brendan Jackman
2020-12-04 19:00       ` Andrii Nakryiko
2020-12-07 11:00         ` Brendan Jackman
2020-12-08  2:19           ` Andrii Nakryiko
2020-12-08 17:04             ` Brendan Jackman
2020-12-08 18:31               ` Andrii Nakryiko
2020-12-03 16:02 ` [PATCH bpf-next v3 13/14] bpf: Add tests for new BPF atomic operations Brendan Jackman
2020-12-04  7:06   ` Yonghong Song
2020-12-04  9:45     ` Brendan Jackman
2020-12-04 15:28       ` Yonghong Song
2020-12-04 19:49         ` Andrii Nakryiko
2020-12-07 15:48           ` Brendan Jackman
2020-12-03 16:02 ` [PATCH bpf-next v3 14/14] bpf: Document new atomic instructions Brendan Jackman
2020-12-03 16:10 ` [PATCH bpf-next v3 00/14] Atomics for eBPF Brendan Jackman
2020-12-04  4:46 ` Yonghong Song

Reply instructions:

You may reply publicly 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=86a88eba-83a1-93c0-490d-ceba238e3aad@fb.com \
    --to=yhs@fb.com \
    --cc=ast@kernel.org \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=jackmanb@google.com \
    --cc=jannh@google.com \
    --cc=kpsingh@chromium.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=revest@chromium.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
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.