bpf: Propose some new instructions for -mcpu=v4
Over the past, there are some discussions to extend bpf instruction ISA to accommodate some new use cases or fix some potential issues. These new instructions will be included in new cpu flavor -mcpu=v4.
The following are the proposal
to add new instructions in 6 different categories.
The proposal is a little bit rough. You can find bpf insn background information in Documentation/bpf/instruction-set.rst. You comments or suggestions are welcome!
SDIV/SMOD (signed div and mod)
==============================
bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)
DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0
The current 'code' field only has two value left, 0xe and 0xf. gcc used these two values (0xe and 0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.
Here, I propose to encode SDIV/SMOD like below:
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)
DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1
Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
Sign extend load
================
Currently llvm generated normal load instructions are encoded like below.
mode(3 bits) size(2 bits) instruction class(3 bits) BPF_MEM (0x3) 8/16/32/64 BPF_LDX
For mode, existing used values are 0x0, 0x1, 0x2, 0x3, 0x6. The proposal is to use mod value 0x4 to encode sign extend loads.
alu32_mode mode(3 bits) size(2 bits) instruction class(3 bits) yes BPF_SMEM (0x4) 8/16 BPF_LDX no BPF_SMEM (0x4) 8/16/32 BPF_LDX
Sign extend register mov
========================
Current BPF_MOV insn is encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)
MOV 0xb 0/1 BPF_ALU/BPF_ALU64 0
Let us support sign extended move insn as defined below:
alu32_mode insn code(4 bits) source(1 bit) instruction
class(3 bit) off(16 bits)
yes MOVS 0xb 0/1 BPF_ALU
8/16
no MOVS 0xb 0/1 BPF_ALU64
8/16/32In the above sign extended mov instruction, 'off' represents the 'size'. For example, if alu32 mode is enabled, and 'off' is 8, which means sign extend a 8-bit value (imm or register) to a 32-bit value. If alu32 mode is not enabled, the same 8-bit value will sign extend to a 64-bit value.
32-bit JA
=========
Currently, the whole range of operations with BPF_JMP32/BPF_JMP insn are implemented like below
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += off BPF_JMP only BPF_JEQ 0x10 PC += off if dst == src BPF_JGT 0x20 PC += off if dst > src unsigned BPF_JGE 0x30 PC += off if dst >= src unsigned BPF_JSET 0x40 PC += off if dst & src BPF_JNE 0x50 PC += off if dst != src BPF_JSGT 0x60 PC += off if dst > src signed BPF_JSGE 0x70 PC += off if dst >= src signed BPF_CALL 0x80 function call BPF_EXIT 0x90 function / program return BPF_JMP only BPF_JLT 0xa0 PC += off if dst < src unsigned BPF_JLE 0xb0 PC += off if dst <= src unsigned BPF_JSLT 0xc0 PC += off if dst < src signed BPF_JSLE 0xd0 PC += off if dst <= src signed ======== ===== ========================= ============
Here the 'off' is 16 bit so the range of jump is [-32768, 32767]. In rare cases, people may have large programs or have loops fully unrolled. This may cause some jump offset beyond the above range. In current llvm implementation, wrong code (after truncation) will be generated.
To fix this issue, the following new insn is proposed
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += imm BPF_JMP32 only, src = 1
The way, the jump offset range become [-2^31, 2^31 - 1].
For other jump instructions, e.g., BPF_JEQ, with a jmp offset beyond [-32768, 32767]. It can be simulated with a 'BPF_JA (PC += imm)' followed by the originalBPF_JEQ with the range 'off', or BPF_JEQ with a short range followed by a BPF_JA.
bswap16/32/64
=============
Currently, llvm does not generate bswap16/32/64 properly. Rather it generates be16/32/64 and le16/32/64 instructions based on endianness of the current bpf target in compilation.
The existing encode looks below:
bpf target insn code(4 bits) source(1 bit)
instruction class(3 bit) imm(32 bits)
big endian LE 0xd LE(0)
BPF_ALU 16/32/64
little endian BE 0xd BE(1)
BPF_ALU 16/32/64LE insn will do swap if the running target is big endian. BE insn will do swap if the running target is little endian. See kernel/bpf/core.c for details.
The new bswap instruction will have the following encoding:
insn code(4 bits) source(1 bit) instruction class(3 bit) imm(32 bits) BSWAP 0xd 0 BPF_ALU64 16/32/64
The BSWAP insn will be swap unconditionally.
ST
==
The kernel has already supported BPF_ST insn like below,
mode(3 bits) size(2 bits) instruction class(3 bits) BPF_MEM (0x3) 8/16/32/64 BPF_ST
The semantics is:
*(size *) (dst_reg + off) = imm32
LLVM just needs to implement this instruction under -mcpu=v4. looks like gcc can already generate this instruction.
Hi Yonghong.
Thanks for the proposal!
Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32
- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32
Of these, code', regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.
On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness. The opcode for signed-operation will be 0x1 in big-endian BPF, but 0x8000 in little-endian bpf.
2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
code:8 regs:8 code2:16 imm:32
Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)
Thoughts?
Quoted 4 lines
1) In effect you have "moving" opcodes that depend on the endianness. The opcode for signed-operation will be
0x1in big-endian BPF, but0x8000in little-endian bpf.
s/0x8000/0x0100/.
(Yeah I'm bad with such things :'D)
Quoted 74 lines
Hi Yonghong.
Thanks for the proposal!Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32Of these,
code',regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness. The opcode for signed-operation will be
0x1in big-endian BPF, but0x8000in little-endian bpf.2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
Quoted 8 lines
code:8 regs:8 code2:16 imm:32Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)
Actually this would be just for DIV/MOD instructions, so the new format should only apply to them. The new format would be something like:
- 64-bit ALU/ALU64 div/mod instructions (code=3,9):
code:8 regs:8 unused:15 signed:1 imm:32
And for the rest of the ALU and ALU64 instructions (code=0,1,2,4,5,6,7,8,a,b,c,d):
- 64-bit ALU/ALU64 instructions:
code:8 regs:8 unused:16 imm:32
Quoted 88 lines
Quoted 74 lines
Hi Yonghong.
Thanks for the proposal!Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32Of these,
code',regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness. The opcode for signed-operation will be
0x1in big-endian BPF, but0x8000in little-endian bpf.2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
Quoted 8 lines
code:8 regs:8 code2:16 imm:32Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)Actually this would be just for DIV/MOD instructions, so the new format should only apply to them. The new format would be something like:
- 64-bit ALU/ALU64 div/mod instructions (code=3,9):
Quoted 8 lines
code:8 regs:8 unused:15 signed:1 imm:32And for the rest of the ALU and ALU64 instructions (code=0,1,2,4,5,6,7,8,a,b,c,d):
- 64-bit ALU/ALU64 instructions:
code:8 regs:8 unused:16 imm:32
Re-reading what I wrote above I realize that it is messy and uses confusing terms that are not used in instruction-set.rst, and it also has mistakes. Sorry about that, 3:30AM posting.
After sleeping over it I figured I better start over and this time I keep it short and stick to instruction-set.rst terminology :)
What I am proposing is, instead of using the `offset' multi-byte field to encode an opcode:
============= ======= ======= ======= ============ 32 bits (MSB) 16 bits 4 bits 4 bits 8 bits (LSB) ============= ======= ======= ======= ============ imm offset src_reg dst_reg opcode ============= ======= ======= ======= ============
To introduce a new opcode2 field for ALU32/ALU instructions like this:
============= ======= ======= ======= ======= ============ 32 bits (MSB) 8 bits 8 bits 4 bits 4 bits 8 bits (LSB) ============= ======= ======= ======= ======= ============ imm opcode2 unused src_reg dst_reg opcode ============= ======= ======= ======= ======= ============
This way:
1) The opcode2 field's stored value will be the same regardless of endianness.
2) The remaining 8 bits stay free for future extensions.
That is from a purely ISA perspective. But then this morning I thought about the kernel and its uapi. This is in uapi/linux/bpf.h:
struct bpf_insn {
__u8 code; /* opcode */
__u8 dst_reg:4; /* dest register */
__u8 src_reg:4; /* source register */
__s16 off; /* signed offset */
__s32 imm; /* signed immediate constant */
};If the bpf_insn struct is supposed to reflect the encoding of stored BPF instructions, and since it is part of the uapi, does this mean we are stuck with that instruction format (and only that format) forever?
Because if changing the internal structure of the bpf_insn struct is a no-no, then there is no way to expand the existing opcode space without using unused multi-byte fields like `off' as such :/
Quoted 140 lines · Jose E. Marchesi
Quoted 89 lines
Quoted 75 lines
Hi Yonghong.
Thanks for the proposal!Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit)
off(16 bits)DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32Of these,
code',regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness. The opcode for signed-operation will be
0x1in big-endian BPF, but0x8000in little-endian bpf.2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
Quoted 8 lines
code:8 regs:8 code2:16 imm:32Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)Actually this would be just for DIV/MOD instructions, so the new format should only apply to them. The new format would be something like:
- 64-bit ALU/ALU64 div/mod instructions (code=3,9):
Quoted 8 lines
code:8 regs:8 unused:15 signed:1 imm:32And for the rest of the ALU and ALU64 instructions (code=0,1,2,4,5,6,7,8,a,b,c,d):
- 64-bit ALU/ALU64 instructions:
code:8 regs:8 unused:16 imm:32Re-reading what I wrote above I realize that it is messy and uses confusing terms that are not used in
instruction-set.rst, and it also has mistakes. Sorry about that, 3:30AM posting.After sleeping over it I figured I better start over and this time I keep it short and stick to
instruction-set.rstterminology :)What I am proposing is, instead of using the `offset' multi-byte field to encode an opcode:
============= ======= ======= ======= ============ 32 bits (MSB) 16 bits 4 bits 4 bits 8 bits (LSB) ============= ======= ======= ======= ============ imm offset src_reg dst_reg opcode ============= ======= ======= ======= ============To introduce a new opcode2 field for ALU32/ALU instructions like this:
============= ======= ======= ======= ======= ============ 32 bits (MSB) 8 bits 8 bits 4 bits 4 bits 8 bits (LSB) ============= ======= ======= ======= ======= ============ imm opcode2 unused src_reg dst_reg opcode ============= ======= ======= ======= ======= ============This way:
1) The opcode2 field's stored value will be the same regardless of endianness.
2) The remaining 8 bits stay free for future extensions.
That is from a purely ISA perspective. But then this morning I thought about the kernel and its uapi. This is in
uapi/linux/bpf.h:struct bpf_insn { __u8 code; /* opcode */ __u8 dst_reg:4; /* dest register */ __u8 src_reg:4; /* source register */ __s16 off; /* signed offset */ __s32 imm; /* signed immediate constant */ };
Quoted 7 lines
If the
bpf_insnstruct is supposed to reflect the encoding of stored BPF instructions, and since it is part of the uapi, does this mean we are stuck with that instruction format (and only that format) forever?Because if changing the internal structure of the
bpf_insnstruct is a no-no, then there is no way to expand the existing opcode space without using unused multi-byte fields like `off' as such :/
Yes. It's an uapi and we're stuck with it.
If I understand correctly you want to extend 8-bit opcode field with another endian independent 8 or 1 bit field.
It's possible on paper, but very challenging and ugly in the code. llvm backend does this for 'off' field:
OSE.write<uint16_t>((Value >> 32) & 0xffff);
where OSE is endian dependent writer.
It does it unconditionally for all insns when it emits them into elf. While in BPFInstrInfo.td we set this 16 bits as:
let Inst{47-32} = offset;
so to make it 'endian independent' from ISA point of view the llvm backend would need to undo the endianness OSE.write and become endian dependent when it sets Inst{47-32} which is possible, but quite ugly.
Another alternative is to teach binary emitter to different opcodes and do OSE.write<uint16_t> one way for one set of opcode and differently for another. Which is equally ugly.
The same ugliness will be on the kernel side.
Instead of doing if (bpf_insn->off == 1) in the interpreter and all JITs in all architectures (both little and big)
the kernel would need to do this pseudo-endian-independent dance and little end arch would do if (bpf_insn->off == 1) while big-endian arch would do if (bpf_insn->off == 255)
which is double ugly.
imo Yonghong's proposal to encode off=1 for signed div/mod is cleaner. It fits well to what we have already for other insns.
Quoted 88 lines · Jose E. Marchesi
Quoted 74 lines
Hi Yonghong.
Thanks for the proposal!Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit) off(16 bits) DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit) off(16 bits) DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32Of these,
code',regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness.
The opcode for signed-operation will be 0x1 in big-endian BPF, but 0x8000 in little-endian bpf.2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
Quoted 8 lines
code:8 regs:8 code2:16 imm:32Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)Actually this would be just for DIV/MOD instructions, so the new format should only apply to them. The new format would be something like:
- 64-bit ALU/ALU64 div/mod instructions (code=3,9):
Quoted 8 lines
code:8 regs:8 unused:15 signed:1 imm:32And for the rest of the ALU and ALU64 instructions (code=0,1,2,4,5,6,7,8,a,b,c,d):
- 64-bit ALU/ALU64 instructions:
code:8 regs:8 unused:16 imm:32
That is correct. My design can be interpreted this way.
Quoted 76 lines · Jose E. Marchesi
Hi Yonghong.
Thanks for the proposal!Quoted 17 lines
SDIV/SMOD (signed div and mod)
==============================bpf already has unsigned DIV and MOD. They are encoded as
insn code(4 bits) source(1 bit) instruction class(3 bit) off(16 bits) DIV 0x3 0/1 BPF_ALU/BPF_ALU64 0 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 0The current 'code' field only has two value left,
0xeand0xf. gcc used these two values (0xeand0xf) for SDIV and SMOD. But using these two values takes up all 'code' space and makes future extension hard.Here, I propose to encode SDIV/SMOD like below:
Quoted 7 lines
insn code(4 bits) source(1 bit) instruction class(3 bit) off(16 bits) DIV 0x3 0/1 BPF_ALU/BPF_ALU64 1 MOD 0x9 0/1 BPF_ALU/BPF_ALU64 1Basically, we reuse the same 'code' value but changing 'off' from 0 to 1 to indicate signed div/mod.
I have a general concern about using instruction operands to encode opcodes (in this case, 'off').
At the moment we have two BPF instruction formats:
- The 64-bit instructions:
code:8 regs:8 offset:16 imm:32- The 128-bit instructions:
code:8 regs:8 offset:16 imm:32 unused:32 imm:32Of these,
code',regs' and `unused' are what is commonly known as instruction fields. These are typically used for register numbers, flags, and opcodes.On the other hand, offset, imm32 and imm:32:::imm:32 are instruction operands (the later is non-contiguous and conforms the 64-bit operand in the 128-bit instruction).
The main difference between these is that the bytes conforming instruction operands are themselves impacted by endianness, on top on the endianness effect on the whole instruction. (The weird endian-flip in the two nibbles of `regs' is unfortunate, but I guess there is nothing we can do about it at this point and I count them as non-operands.)
If you use an instruction operand (such as `offset') in order to act as an opcode, you incur in two inconveniences:
1) In effect you have "moving" opcodes that depend on the endianness.
The opcode for signed-operation will be 0x1 in big-endian BPF, but 0x8000 in little-endian bpf.2) You lose the ability of easily adding more complementary opcodes in these 16 bits in the future, in case you ever need them.
As far as I have seen in other architectures, the usual way of doing this is to add an additional instruction format, in this case for the class of arithmetic instructions, where the bits dedicated to the unused operand (offset) becomes a new opcodes field:
- 32-bit arithmetic instructions:
code:8 regs:8 code2:16 imm:32
Quoted 8 lines
Where code2 is now an additional field (not an operand) that provides extra additional opcode space for this particular class of instructions. This can be divided in a 1-bit field to signify "signed" and the rest reserved for future use:
opcode2 ::= unused(15) signed(1)Thoughts?
If I understand correctly, you proposed something like
insn code(4 bits) source(1 bit) instruction class(3 bit) EXT 0xe 0/1 BPF_ALU/BPF_ALU64
The insn BPF_EXT means the actual 'code' is in 'off' (16 bits), right? I think this could work.
But we already have precedence to use off/imm fields for insn encoding, e.g., newer atomic insns like XCHG using imm for the 'code' and we use the BPF_ATOMIC to indicate a 'class' of atomic operations. In this specific case, we use MOD/DIV as the 'code' which implies a class of mod/div variants and the 'off' is the way to differentiate.
There are pro's and con's for each approach for the above EXT vs. my proposal. But maybe we could reserve EXT for future use?
Quoted 6 lines · Yonghong Song
Over the past, there are some discussions to extend bpf instruction ISA to accommodate some new use cases or fix some potential issues. These new instructions will be included in new cpu flavor -mcpu=v4.
Quoted 6 lines
The following are the proposal
to add new instructions in 6 different categories.
The proposal is a little bit rough. You can find bpf insn background information inDocumentation/bpf/instruction-set.rst. You comments or suggestions are welcome!
Great that we are trying to fix and complete the instruction set! Just one comment/question below for condition jumps.
[...]
Quoted 38 lines
32-bit JA
=========Currently, the whole range of operations with BPF_JMP32/BPF_JMP insn are implemented like below
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += off BPF_JMP only BPF_JEQ 0x10 PC += off if dst == src BPF_JGT 0x20 PC += off if dst > src unsigned BPF_JGE 0x30 PC += off if dst >= src unsigned BPF_JSET 0x40 PC += off if dst & src BPF_JNE 0x50 PC += off if dst != src BPF_JSGT 0x60 PC += off if dst > src signed BPF_JSGE 0x70 PC += off if dst >= src signed BPF_CALL 0x80 function call BPF_EXIT 0x90 function / program return BPF_JMP only BPF_JLT 0xa0 PC += off if dst < src unsigned BPF_JLE 0xb0 PC += off if dst <= src unsigned BPF_JSLT 0xc0 PC += off if dst < src signed BPF_JSLE 0xd0 PC += off if dst <= src signed ======== ===== ========================= ============Here the 'off' is 16 bit so the range of jump is [-32768, 32767]. In rare cases, people may have large programs or have loops fully unrolled. This may cause some jump offset beyond the above range. In current llvm implementation, wrong code (after truncation) will be generated.
To fix this issue, the following new insn is proposed
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += imm BPF_JMP32 only, src = 1
Quoted 7 lines
The way, the jump offset range become [-2^31, 2^31 - 1].
For other jump instructions, e.g.,
BPF_JEQ, with a jmp offset beyond [-32768, 32767]. It can be simulated with a 'BPF_JA(PC += imm)' followed by the originalBPF_JEQwith the range 'off', orBPF_JEQwith a short range followed by aBPF_JA.
Why not implement the same approach (using imm if src = 1) for all the conditional jumps? Just too much JIT work or some other reasons?
[...]
Quoted 59 lines · Andrii Nakryiko
Quoted 6 lines · Yonghong Song
Over the past, there are some discussions to extend bpf instruction ISA to accommodate some new use cases or fix some potential issues. These new instructions will be included in new cpu flavor -mcpu=v4.
Quoted 6 lines
The following are the proposal
to add new instructions in 6 different categories.
The proposal is a little bit rough. You can find bpf insn background information inDocumentation/bpf/instruction-set.rst. You comments or suggestions are welcome!Great that we are trying to fix and complete the instruction set! Just one comment/question below for condition jumps.
[...]
Quoted 40 lines
32-bit JA
=========Currently, the whole range of operations with BPF_JMP32/BPF_JMP insn are implemented like below
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += off BPF_JMP only BPF_JEQ 0x10 PC += off if dst == src BPF_JGT 0x20 PC += off if dst > src unsigned BPF_JGE 0x30 PC += off if dst >= src unsigned BPF_JSET 0x40 PC += off if dst & src BPF_JNE 0x50 PC += off if dst != src BPF_JSGT 0x60 PC += off if dst > src signed BPF_JSGE 0x70 PC += off if dst >= src signed BPF_CALL 0x80 function call BPF_EXIT 0x90 function / program return BPF_JMP only BPF_JLT 0xa0 PC += off if dst < src unsigned BPF_JLE 0xb0 PC += off if dst <= src unsigned BPF_JSLT 0xc0 PC += off if dst < src signed BPF_JSLE 0xd0 PC += off if dst <= src signed ======== ===== ========================= ============Here the 'off' is 16 bit so the range of jump is [-32768, 32767]. In rare cases, people may have large programs or have loops fully unrolled. This may cause some jump offset beyond the above range. In current llvm implementation, wrong code (after truncation) will be generated.
To fix this issue, the following new insn is proposed
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += imm BPF_JMP32 only, src = 1The way, the jump offset range become [-2^31, 2^31 - 1].
Quoted 8 lines
Quoted 5 lines
For other jump instructions, e.g.,
BPF_JEQ, with a jmp offset beyond [-32768, 32767]. It can be simulated with a 'BPF_JA(PC += imm)' followed by the originalBPF_JEQwith the range 'off', orBPF_JEQwith a short range followed by aBPF_JA.Why not implement the same approach (using imm if src = 1) for all the conditional jumps? Just too much JIT work or some other reasons?
We cannot use 'src' since 'src' is used in conditional jump, e.g.,
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JEQ 0x10 PC += off if dst == src
In this particular case, there is no good way to extend the insn with range [-2^31, 2^31 - 1] as 'off/dst/src' all used by the above insn. The sample extension to original BPF_JEQ seems not working so I came up with the above BPF_JA (32bit range) + BPF_JEQ(16 bit range) approach. It is ugly and increase implementation complexity, but considering this is a corner case. It may not be worthwhile to design a whole range of 32bit range of BPF_JEQ/JGT/... instructions.
Quoted 2 lines
[...]
Quoted 69 lines · Yonghong Song
Quoted 65 lines · Andrii Nakryiko
Quoted 6 lines · Yonghong Song
Over the past, there are some discussions to extend bpf instruction ISA to accommodate some new use cases or fix some potential issues. These new instructions will be included in new cpu flavor -mcpu=v4.
Quoted 6 lines
The following are the proposal
to add new instructions in 6 different categories.
The proposal is a little bit rough. You can find bpf insn background information inDocumentation/bpf/instruction-set.rst. You comments or suggestions are welcome!Great that we are trying to fix and complete the instruction set! Just one comment/question below for condition jumps.
[...]
Quoted 45 lines
32-bit JA
=========Currently, the whole range of operations with BPF_JMP32/BPF_JMP insn are implemented like below
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += off BPF_JMP only BPF_JEQ 0x10 PC += off if dst == src BPF_JGT 0x20 PC += off if dst > src unsigned BPF_JGE 0x30 PC += off if dst >= src unsigned BPF_JSET 0x40 PC += off if dst & src BPF_JNE 0x50 PC += off if dst != src BPF_JSGT 0x60 PC += off if dst > src signed BPF_JSGE 0x70 PC += off if dst >= src signed BPF_CALL 0x80 function call BPF_EXIT 0x90 function / program return BPF_JMP only BPF_JLT 0xa0 PC += off if dst < src unsigned BPF_JLE 0xb0 PC += off if dst <= src unsigned BPF_JSLT 0xc0 PC += off if dst < src signed BPF_JSLE 0xd0 PC += off if dst <= src signed ======== ===== ========================= ============Here the 'off' is 16 bit so the range of jump is [-32768, 32767]. In rare cases, people may have large programs or have loops fully unrolled. This may cause some jump offset beyond the above range. In current llvm implementation, wrong code (after truncation) will be generated.
To fix this issue, the following new insn is proposed
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JA 0x00 PC += imm BPF_JMP32 only, src = 1The way, the jump offset range become [-2^31, 2^31 - 1].
For other jump instructions, e.g.,
BPF_JEQ, with a jmp offset beyond [-32768, 32767]. It can be simulated with a 'BPF_JA(PC += imm)' followed by the originalBPF_JEQwith the range 'off', orBPF_JEQwith a short range followed by aBPF_JA.
Quoted 4 lines
Quoted 2 lines
Why not implement the same approach (using imm if src = 1) for all the conditional jumps? Just too much JIT work or some other reasons?
We cannot use 'src' since 'src' is used in conditional jump, e.g.,
Right, I missed this part, thanks.
Quoted 18 lines
======== ===== ========================= ============ code value description notes ======== ===== ========================= ============ BPF_JEQ 0x10 PC += off if dst == srcIn this particular case, there is no good way to extend the insn with range [-2^31, 2^31 - 1] as 'off/dst/src' all used by the above insn. The sample extension to original
BPF_JEQseems not working so I came up with the aboveBPF_JA(32bit range) +BPF_JEQ(16 bit range)approach. It is ugly and increase implementation complexity, but considering this is a corner case. It may not be worthwhile to design a whole range of 32bit range of BPF_JEQ/JGT/... instructions.Quoted 2 lines
[...]