ダブルロックの有用性について
2016.08.01 サイボウズラボユースにて. ずいぶんまえに学んだ内容だが、資料を生理していたらmemoがでてきたので。 ここに吐いておく(間違っていたらすみません)
はじめに通常のロックについて
以下の手順で行われる
lock() if (inited == false) init() inited = true unlock()
このときif文とlock,unlockのレイテンシの重さはだいたい以下のような関係
if() <<<< lock(), unlock()
初期化をする人は以下のように実行する
lock() if (inited == false) init() inited = true unlock()
それ以降の人はこのように実行する
lock() unlock()
このときの初期化をする人、それ以降の人の割合は以下のような関係
初期化者 <<<<< 超えられない壁 <<<<<< それ以外
なので、いちいちlock, unlockを毎回させるのは嫌だ!!
これがダブルロックのモチベーション
ダブルロックとは
以下のような手順で行われる
if (inited == false) lock() if (inited == false) init() inited = true unlock()
初期化者は以下のように実行
if (inited == false) lock() if (inited == false) init() inited = true unlock()
それ以外の人は以下のように実行
if (inited == false)
見てわかるようにlock,unlockを回避できた。だがしかし、2000年くらいに ただのダブルロックがすべてのアーキテクチャで安全ではないことが示された。
Intelのアーキとかだと、大体うまく動くようだが、Javaとかだと様々なアーキで 動かすことになるので、その問題が浮き彫りになったっぽい。 その出来事以降、Intelのプロセッサのマニュアルにもその趣旨に関する文が追加されている。 詳しくは以下の4/21日を参照する。
http://homepage1.nifty.com/herumi/diary/1204.html
C++11以降はスレッドセーフなロック手法を使っている。
C++のスレッドセーフロックの確認
以下のコードをコンパイルしてasmを見る
struct A { int a; A(int b) : a(b) {} }; A& get_instance() { static A a(2); return a; }
$ c++ -std=c++11 -S -Ofast -o out.s main.cc
.section __TEXT,__text,regular,pure_instructions .macosx_version_min 10, 11 .globl __Z12get_instancev .align 4, 0x90 __Z12get_instancev: ## @_Z12get_instancev .cfi_startproc ## BB#0: pushq %rbp Ltmp0: .cfi_def_cfa_offset 16 Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp2: .cfi_def_cfa_register %rbp movb __ZGVZ12get_instancevE1a(%rip), %al testb %al, %al jne LBB0_3 ## BB#1: leaq __ZGVZ12get_instancevE1a(%rip), %rdi callq ___cxa_guard_acquire testl %eax, %eax je LBB0_3 ## BB#2: movl $2, __ZZ12get_instancevE1a(%rip) leaq __ZGVZ12get_instancevE1a(%rip), %rdi callq ___cxa_guard_release LBB0_3: leaq __ZZ12get_instancevE1a(%rip), %rax popq %rbp retq .cfi_endproc .zerofill __DATA,__bss,__ZZ12get_instancevE1a,4,2 ## @_ZZ12get_instancevE1a .zerofill __DATA,__bss,__ZGVZ12get_instancevE1a,8,3 ## @_ZGVZ12get_instancevE1a .subsections_via_symbols
これがスレッドセーフなロックのasm. __cxa_guard_acquire
, __cxa_guard_release
がそれである
こうするとスレッドセーフでない従来型なasmをはいてくれる
$ c++ -std=c++11 -S -Ofast -o out.s main.cc -fno-threadsafe-statics
.section __TEXT,__text,regular,pure_instructions .macosx_version_min 10, 11 .globl __Z12get_instancev .align 4, 0x90 __Z12get_instancev: ## @_Z12get_instancev .cfi_startproc ## BB#0: pushq %rbp Ltmp0: .cfi_def_cfa_offset 16 Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp2: .cfi_def_cfa_register %rbp movb __ZGVZ12get_instancevE1a(%rip), %al testb %al, %al jne LBB0_2 ## BB#1: movl $2, __ZZ12get_instancevE1a(%rip) movb $1, __ZGVZ12get_instancevE1a(%rip) LBB0_2: leaq __ZZ12get_instancevE1a(%rip), %rax popq %rbp retq .cfi_endproc .zerofill __DATA,__bss,__ZZ12get_instancevE1a,4,2 ## @_ZZ12get_instancevE1a .zerofill __DATA,__bss,__ZGVZ12get_instancevE1a,1,0 ## @_ZGVZ12get_instancevE1a .subsections_via_symbols
これが従来型。 以上でした。
BPFに関する情報収集
BPFについてサーベイしたので、それのまとめ. BPF for Dummiesのプロトタイプといえるよういしていけたら最高である。 現状は雑記状態なのでご了承いただきたい.
BPFとは,何をするためのものか
正直, 僕自身もよく分からない。 BPFはin kernelのパケットフィルタに最適な 仮想機械として設計実装されたが、現在はkernel内部のあらゆるデータフローを トレーシングやデバッグするために 用いられている。といった感じか。。。
構成
eBPFがattachできるポイントは現状で以下. ちなみにcBPFはsocketのみをサポートしている
- socket (via setsockopt) (hook skb)
- kprobe (via bcc) (func-call-infos)
- uprobe (via bcc) (func-call-infos)
- trace points (via bcc) (func-call-infos)
- syscall (via seccmomp) (system-call-infos)
- tc (no exploring)
みやすくするとこんな感じ(iovisorのスライド)
cBPF,eBPF
eBPF(Extended BPF)の登場後、伝統的なBPFの区別のために伝統的なBPFをcBPF (Classic BPF)とよぶようになりました。現在では一般的にBPFと呼ぶとeBPFを さしていることがほとんどのようです。
違いを簡単にまとめた.
cBPF | eBPF | |
---|---|---|
Register | 32bit 2 regs | 64bit 10 regs |
Memory | stack | stack |
Instruction | 4B ld/st to stack | 1-8B ld/st to stack |
Instruction | 1-8B ld to packet | 1-8B ld/st fo packet |
Instruction | Cond Jump forward | Cond Jump forward/backward |
Instruction | ALU Instructions | Same + Signed Shift + Bswap |
Else | . | Helper Functions |
Else | . | Helper Data Structure |
引用: https://www.slideshare.net/PLUMgrid/ebpf-and-linux-networking
Linuxではより高度な作業を可能にするためSKBのフィールドをマクロで参照できるよう にしている。kernel docに概要がのせられているので、以下に示す。
len skb->len proto skb->protocol type skb->pkt_type poff Payload start offset ifidx skb->dev->ifindex nla Netlink attribute of type X with offset A nlan Nested Netlink attribute of type X with offset A mark skb->mark queue skb->queue_mapping hatype skb->dev->type rxhash skb->hash cpu raw_smp_processor_id() vlan_tci skb_vlan_tag_get(skb) vlan_avail skb_vlan_tag_present(skb) vlan_tpid skb->vlan_proto rand prandom_u32()
引用: https://www.kernel.org/doc/Documentation/networking/filter.txt
CPUのIDまでとれるらしい。恐ろしい。。
命令セット
ここで書くと長くなってしまうので、別の記事に分割した。 そちらを参照すること。
活用例
- bcc (Generic Tracing Tool)
- seccomp
- socket filter
その他キーワード
cBPF命令セット
ここでは単純に表と図のみでcBPFにどのような命令が含まれて、 どのように動作するのかを示す。Instruction set archの設計論などは まったく触れない。 (ただつかう段階では必要ないため。) 必要があれば、それぞれのBitにどのような意味があるかも説明していく。
Encoding
struct cbpf_insn { uint16_t opcode; uint8_t jt; uint8_t jf; uint32_t k; };
msb lsb +------------------------+--------+--------+----------------+ | k | jf | jt | opcode | +------------------------+--------+--------+----------------+
Instruction Classは以下の3つに分類できる.
- ALU
- Memory Access
- Branch
- Misc
ALU
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x0004 | add k | A+=k |
0x0014 | sub k | A-=k |
0x0024 | mul k | A*=k |
0x0054 | and k | A&=k |
0x0044 | or k | A|=k |
0x0034 | div k | A/=k |
0x0064 | lsh k | A<<=k |
0x0074 | rsh k | A>>=k |
0x000c | add x | A+=X |
0x001c | sub x | A-=X |
0x002c | mul x | A*=X |
0x004c | or x | A|=X |
0x003c | div x | A/=X |
0x005c | and x | A&=X |
0x006c | lsh x | A<<=X |
0x007c | rsh x | A>>=X |
0x0084 | neg | A=-A |
Memory Access
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x0000 | ld k | A = k |
0x0001 | ldx k | X = k |
0x0002 | st M[k] | mem[k] = A |
0x0003 | stx M[k] | mem[k] = X |
0x0020 | ld [k] | A = ntohl((i32)(p+k)) |
0x0028 | ldh [k] | A = short(&p[k]) |
0x0030 | ldb [k] | A = p[k] |
0x0040 | ld [k] | A = ntohl((i32)(p+k)) |
0x0048 | ldh [k] | A = short(&p[k]) |
0x0050 | ldb [k] | A = p[k] |
0x0060 | ld M[k] | A = mem[k] |
0x0061 | ldx M[k] | X = mem[k] |
0x0080 | ld #pktlen | A = wirelen |
0x0081 | (n/a) | X = wirelen |
0x00b1 | ldxb 4*([k]&0xf) | X = (p[k]&0xf)<<2 |
Branch
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x0005 | ja k | pc+=k |
0x0015 | jeq k jt jf | pc+=(A==k)?jt:jf |
0x0025 | jgt k jt jf | pc+=(A>k)?jt:jf |
0x0035 | jge k jt jf | pc+=(A>=k)?jt:jf |
0x0045 | jset k jt jf | pc+=(A&k)?jt:jf |
0x003d | jge x jt jt | pc+=(A>=X)?jt:jf |
0x001d | jeq x jt jt | pc+=(A==X)?jt:jf |
0x002d | jgt x jt jf | pc+=(A>X)?jt:jf |
0x004d | jset x jt jt | pc+=(A&X)?jt:jf |
0x0006 | ret k | return k |
0x0016 | ret | return A |
Misc
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x0087 | txa | A=X |
0x0007 | tax | X=A |
Reference
eBPF命令セット
ここでは単純に表と図のみでeBPFにどのような命令が含まれて、 どのように動作するのかを示す。Instruction set archの設計論などは まったく触れない。 (ただつかう段階では必要ないため。)
必要があれば、それぞれのBitにどのような意味があるかも説明していく。
Encoding
struct ebpf_insn { uint8_t opcode; uint8_t src:4; uint8_t dst:4; uint16_t offset; uint32_t imm; };
msb lsb +------------------------+----------------+----+----+--------+ |immediate |offset |src |dst |opcode | +------------------------+----------------+----+----+--------+
Instruction Classは以下の3つに分類できる.
- ALU
- Byteswap
- Memory Access
- Branch
ALU
64bit ALU命令
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x07 | add dst, imm | dst += imm |
0x0f | add dst, src | dst += src |
0x17 | sub dst, imm | dst -= imm |
0x1f | sub dst, src | dst -= src |
0x27 | mul dst, imm | dst *= imm |
0x2f | mul dst, src | dst *= src |
0x37 | div dst, imm | dst /= imm |
0x3f | div dst, src | dst /= src |
0x47 | or dst, imm | dst |= imm |
0x4f | or dst, src | dst |= src |
0x57 | and dst, imm | dst &= imm |
0x5f | and dst, src | dst &= src |
0x67 | lsh dst, imm | dst <<= imm |
0x6f | lsh dst, src | dst <<= src |
0x77 | rsh dst, imm | dst >>= imm (logical) |
0x7f | rsh dst, src | dst >>= src (logical) |
0x87 | neg dst | dst = -dst |
0x97 | mod dst, imm | dst %= imm |
0x9f | mod dst, src | dst %= src |
0xa7 | xor dst, imm | dst ^= imm |
0xaf | xor dst, src | dst ^= src |
0xb7 | mov dst, imm | dst = imm |
0xbf | mov dst, src | dst = src |
0xc7 | arsh dst, imm | dst >>= imm (arithmetic) |
0xcf | arsh dst, src | dst >>= src (arithmetic) |
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x04 | add32 dst, imm | dst += imm |
0x0c | add32 dst, src | dst += src |
0x14 | sub32 dst, imm | dst -= imm |
0x1c | sub32 dst, src | dst -= src |
0x24 | mul32 dst, imm | dst *= imm |
0x2c | mul32 dst, src | dst *= src |
0x34 | div32 dst, imm | dst /= imm |
0x3c | div32 dst, src | dst /= src |
0x44 | or32 dst, imm | dst |= imm |
0x4c | or32 dst, src | dst |= src |
0x54 | and32 dst, imm | dst &= imm |
0x5c | and32 dst, src | dst &= src |
0x64 | lsh32 dst, imm | dst <<= imm |
0x6c | lsh32 dst, src | dst <<= src |
0x74 | rsh32 dst, imm | dst >>= imm (logical) |
0x7c | rsh32 dst, src | dst >>= src (logical) |
0x84 | neg32 dst | dst = -dst |
0x94 | mod32 dst, imm | dst %= imm |
0x9c | mod32 dst, src | dst %= src |
0xa4 | xor32 dst, imm | dst ^= imm |
0xac | xor32 dst, src | dst ^= src |
0xb4 | mov32 dst, imm | dst = imm |
0xbc | mov32 dst, src | dst = src |
0xc4 | arsh32 dst, imm | dst >>= imm (arithmetic) |
0xcc | arsh32 dst, src | dst >>= src (arithmetic) |
Byteswap
Opcode | Mnemonic | Pseudocode |
---|---|---|
0xd4 (imm == 16) | le16 dst | dst = htole16(dst) |
0xd4 (imm == 32) | le32 dst | dst = htole32(dst) |
0xd4 (imm == 64) | le64 dst | dst = htole64(dst) |
0xdc (imm == 16) | be16 dst | dst = htobe16(dst) |
0xdc (imm == 32) | be32 dst | dst = htobe32(dst) |
0xdc (imm == 64) | be64 dst | dst = htobe64(dst) |
Memory Access
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x18 | lddw dst, imm | dst = imm |
0x20 | ldabsw src, dst, imm | See kernel documentation |
0x28 | ldabsh src, dst, imm | … |
0x30 | ldabsb src, dst, imm | … |
0x38 | ldabsdw src, dst, imm | … |
0x40 | ldindw src, dst, imm | … |
0x48 | ldindh src, dst, imm | … |
0x50 | ldindb src, dst, imm | … |
0x58 | ldinddw src, dst, imm | … |
0x61 | ldxw dst, [src+off] | dst = (uint32_t ) (src + off) |
0x69 | ldxh dst, [src+off] | dst = (uint16_t ) (src + off) |
0x71 | ldxb dst, [src+off] | dst = (uint8_t ) (src + off) |
0x79 | ldxdw dst, [src+off] | dst = (uint64_t ) (src + off) |
0x62 | stw [dst+off], imm | (uint32_t ) (dst + off) = imm |
0x6a | sth [dst+off], imm | (uint16_t ) (dst + off) = imm |
0x72 | stb [dst+off], imm | (uint8_t ) (dst + off) = imm |
0x7a | stdw [dst+off], imm | (uint64_t ) (dst + off) = imm |
0x63 | stxw [dst+off], src | (uint32_t ) (dst + off) = src |
0x6b | stxh [dst+off], src | (uint16_t ) (dst + off) = src |
0x73 | stxb [dst+off], src | (uint8_t ) (dst + off) = src |
0x7b | stxdw [dst+off], src | (uint64_t ) (dst + off) = src |
Branch
Opcode | Mnemonic | Pseudocode |
---|---|---|
0x05 | ja +off | PC += off |
0x15 | jeq dst, imm, +off | PC += off if dst == imm |
0x1d | jeq dst, src, +off | PC += off if dst == src |
0x25 | jgt dst, imm, +off | PC += off if dst > imm |
0x2d | jgt dst, src, +off | PC += off if dst > src |
0x35 | jge dst, imm, +off | PC += off if dst >= imm |
0x3d | jge dst, src, +off | PC += off if dst >= src |
0x45 | jset dst, imm, +off | PC += off if dst & imm |
0x4d | jset dst, src, +off | PC += off if dst & src |
0x55 | jne dst, imm, +off | PC += off if dst != imm |
0x5d | jne dst, src, +off | PC += off if dst != src |
0x65 | jsgt dst, imm, +off | PC += off if dst > imm (signed) |
0x6d | jsgt dst, src, +off | PC += off if dst > src (signed) |
0x75 | jsge dst, imm, +off | PC += off if dst >= imm (signed) |
0x7d | jsge dst, src, +off | PC += off if dst >= src (signed) |
0x85 | call imm | Function call |
0x95 | exit | return r0 |
Reference
The White Paper of Packet Processing 作成のためのMemo
完成はしないが、お勉強は大事である。 なんかしっていたら教えてください。。。涙
Hardware と Softwareでの選択はどのようにしておこなうのか。
下にいくについれて高性能だがフレキシブルでなくなる. とくにASICはできるまでに2年間くらいかかることもある.
- Sofoware
- In Kernel Software (NFV Migrationとか)
- Kernel Bypass (DPDK, Netmap)
- Hybrid
- Reconf hard, FPGA (slow clockなのでAsicには性能が及ばないが、フレキシブル)
- percial offload
- Hardware
- Full IO Offload (Asic Config)
目的(Target)によって選択を変える.
それぞれのポイント
- コスト
- Opex (Operationg)
- Capex (Capital)
- フレキシブルさ
- 性能
具体例
- Software
- BPF
- Hybrid
- Hardware
- Flow Director
- P4 Asic
- Whitebox Switch
- Hardware Switch
組織
- Community
- FD.io
- SONiC (Software for Open Networking in the Cloud)
- Campany
- RedHat (OS以外 よくしらない)
- Cviun (NW処理のチップベンダ, P4のASICもつくっている)
- snaproute
- Mechanism
- SAI (Switch Abstruction Interface)
- Rack-scale Computing (MicroSoft HPC?)
その他
- Open vSwitchをFPGAでやりたいひとがいる
Thread Affinityによる性能実験
雑記状態なので、この記事もとても汚いことを了承してください。
DPDKはpthreadwを用いてスレッド操作を行っている。 内部でset affinityを行い、複数のCPUでスレッドを共有しないように固定している らしいが、実際に複数CPUで共有実行を行った場合と、単一CPUで動作をおこなった場合 どの程度性能に差がでるのかを検証してみた。
比較対象, 評価方法
比較対象
- 単一CPUで固定して動作させるthread
- 固定しないで動作させたthread
評価方法
- thread遅延 (無限loopの一回の遅延[clock])
ソースコード
#include <slankdev/system.h> #include <slankdev/cpuset.h> #include <slankdev/thread.h> uint64_t func(int loop_count, bool setaffinity_1core) { if (setaffinity_1core) { slankdev::cpuset cpuset(0x2); slankdev::thread_self th; th.setaffinity_np(sizeof(cpu_set_t), cpuset.get_native()); } uint64_t before = slankdev::rdtsc(); for (size_t i=0; i<loop_count; i++) ; uint64_t latency = slankdev::rdtsc() - before; return latency; } int main() { for (size_t i=0; i<10; i++) { printf("test%zd\n", i); uint64_t affinity_true = func(1000000000, true); uint64_t affinity_false = func(1000000000, false); printf("+ affinity true : %lu \n", affinity_true ); printf("+ affinity false: %lu \n", affinity_false); } }
実験結果
以下に示す
test0 + affinity true : 4681434790 + affinity false: 4634806268 test1 + affinity true : 4637598020 + affinity false: 4663916764 test2 + affinity true : 4591219566 + affinity false: 4599745108 test3 + affinity true : 4612664322 + affinity false: 4619733254 test4 + affinity true : 4570637696 + affinity false: 4547641394 test5 + affinity true : 4606940932 + affinity false: 4582990918 test6 + affinity true : 4576054526 + affinity false: 4612506292 test7 + affinity true : 4552900718 + affinity false: 4551479516 test8 + affinity true : 4559223794 + affinity false: 4556642934 test9 + affinity true : 4600009958 + affinity false: 4597938462
空のループなので、とくに性能の変化は大きくは見えなかった。 メモリアクセスとかいろいろやったらもしかしたら変わるかもしれないので、 今後少しずつ結果を伸ばしていきたい.