Page MenuHomePhabricator

[WIP][BPF] support exchange/compare-and-exchange instruction
Needs ReviewPublic

Authored by yonghong-song on Jan 3 2020, 2:32 PM.

Details

Reviewers
ast
Summary

Implement exchange/compare-and-exchange instruction for BPF.

The use case:
During Martin's congestion control work, kernel
data structure is accessed and some fields may be
written. In the kernel, compare-and-exchange is
used to handle race. The same should be done
in bpf program, otherwise, we have a race here.

The exchange instruction is implemented for other
cases involving atomic swap operation.

xchg ===:

At C level, the following gcc builtin function is used:

old = __sync_lock_test_and_set(p, new);

The compiler will generate assembly code like:

dest_reg = xchg_u<8,16,32,64>(base_reg + offset, dest_reg);

Encoding:

opcode: class: STX, width: B, H, W, DW, opcode: XMEM
imm bit 0-7 = 1

Example:

-bash-4.4$ cat swap.c
char test1(char *p, char v) { return __sync_lock_test_and_set(p, v); }
int test2(int *p, int v) { return __sync_lock_test_and_set(p, v); }
typedef unsigned long long __u64;
__u64 test3(__u64 *p, __u64 v) { return __sync_lock_test_and_set(p, v); }
-bash-4.4$ clang -target bpf -O2 -S -emit-llvm swap.c
-bash-4.4$ llc -march=bpf -filetype=obj -mattr=+alu32 swap.ll
-bash-4.4$ llvm-objdump -d -mattr=+alu32 swap.o
... 
0000000000000000 test1:
     0:       bc 20 00 00 00 00 00 00 w0 = w2
     1:       d3 01 00 00 01 00 00 00 w0 = xchg32_u8(r1 + 0, w0) 
     2:       64 00 00 00 18 00 00 00 w0 <<= 24
     3:       c4 00 00 00 18 00 00 00 w0 s>>= 24
     4:       95 00 00 00 00 00 00 00 exit

0000000000000028 test2:
     5:       bc 20 00 00 00 00 00 00 w0 = w2
     6:       c3 01 00 00 01 00 00 00 w0 = xchg32_u32(r1 + 0, w0) 
     7:       95 00 00 00 00 00 00 00 exit

0000000000000040 test3:
     8:       bf 20 00 00 00 00 00 00 r0 = r2
     9:       db 01 00 00 01 00 00 00 r0 = xchg_xchg_u64(r1 + 0, r0) 
    10:       95 00 00 00 00 00 00 00 exit

cmpxchg ===:

At C level, the following gcc builtin function is used:

val = __sync_val_compare_and_swap(p, old, new);

The compiler will generate assembly code like:

dest_reg = cmpxchg_u<8,16,32,64>(base_reg + offset, dest_reg, new_reg);

dest_reg is a read/write register, input is the old value, the result
is written to dest_reg.

Encoding of cmpxchg:

opcode: class: STX, width: B, H, W, DW, opcode: XMEM
imm bit 0-7 = 1, 8-11 encodes "new_reg".

An example with +alu32 mode for cmpxchg:

-bash-4.4$ cat xchg.c
char test1(char *p, char a, char b) { return __sync_val_compare_and_swap(p, a, 5); }
int  test2(int *p, int a, int b) { return __sync_val_compare_and_swap(p, a, b); }
typedef unsigned long long __u64;
__u64 test3(__u64 *p, __u64 a, __u64 b) { return __sync_val_compare_and_swap(p, a, b); }

-bash-4.4$ clang -target bpf -O2 -S -emit-llvm xchg.c
-bash-4.4$ llc -march=bpf -filetype=obj xchg.ll
-bash-4.4$ llvm-objdump -d --mattr=+alu32 xchg.o
0000000000000000 test1:
     0:       bf 20 00 00 00 00 00 00 r0 = r2
     1:       b7 02 00 00 05 00 00 00 r2 = 5 
     2:       d3 01 00 00 02 02 00 00 w0 = cmpxchg32_u8(r1 + 0, w0, w2) 
     3:       67 00 00 00 38 00 00 00 r0 <<= 56
     4:       c7 00 00 00 38 00 00 00 r0 s>>= 56
     5:       95 00 00 00 00 00 00 00 exit

0000000000000030 test2:
     6:       bf 20 00 00 00 00 00 00 r0 = r2
     7:       c3 01 00 00 02 03 00 00 w0 = cmpxchg32_u32(r1 + 0, w0, w3) 
     8:       95 00 00 00 00 00 00 00 exit

0000000000000048 test3:
     9:       bf 20 00 00 00 00 00 00 r0 = r2
    10:       db 01 00 00 02 03 00 00 r0 = cmpxchg_u64(r1 + 0, r0, r3) 
    11:       95 00 00 00 00 00 00 00 exit

Diff Detail

Event Timeline

yonghong-song created this revision.Jan 3 2020, 2:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 3 2020, 2:32 PM
yonghong-song retitled this revision from [WIP][BPF] support compare-and-exchange instruction to [WIP][BPF] support exchange/compare-and-exchange instruction.
yonghong-song edited the summary of this revision. (Show Details)

implement exchange instruction

yonghong-song edited the summary of this revision. (Show Details)

use the same XADD opcode for new instructions.