BSDのNW処理部分の設計実装
自分用雑記. まだ書きかけです.
FreeBSDの黄色い本を読んで自分なりに要約, またSTCPの設計実装のためのメモ ここで出てくる典型的例とはBSDカーネル内での実装のことである.
ソースは以下から入手した - ftp://ftp.freebsd.org/pub/FreeBSD/releases/
続きを読むBSDのARP実装についてメモ
どこを参照したか
FreeBSDソースの以下のファイル
ファイル名 | 概要 |
---|---|
sys/net/if_arp.h | arphdr構造体とかその辺がある |
sys/net/if_ethersubr.c | Ethernetに関する処理がある |
sys/netinet/if_ether.c | Ether,ARPに関する大事な実装 |
ARP処理部分の流れ
- init
- arpresolve
- arprequest
ARPでの代表的関数
関数名 | 概要 |
---|---|
arprequest | arpリクエストをブロードキャスト |
arpresolve | 名前解決を行う |
arpintr | パケットがarpかを確認前 |
Glossary
- lla(Link Lyer Address)
よく使われる構造体
struct arphdr { u_short ar_hrd; /* format of hardware address */ #define ARPHRD_ETHER 1 /* ethernet hardware format */ #define ARPHRD_IEEE802 6 /* token-ring hardware format */ #define ARPHRD_ARCNET 7 /* arcnet hardware format */ #define ARPHRD_FRELAY 15 /* frame relay hardware format */ #define ARPHRD_IEEE1394 24 /* firewire hardware format */ #define ARPHRD_INFINIBAND 32 /* infiniband hardware format */ u_short ar_pro; /* format of protocol address */ u_char ar_hln; /* length of hardware address */ u_char ar_pln; /* length of protocol address */ u_short ar_op; /* one of: */ #define ARPOP_REQUEST 1 /* request to resolve address */ #define ARPOP_REPLY 2 /* response to previous request */ #define ARPOP_REVREQUEST 3 /* request protocol address given hardware */ #define ARPOP_REVREPLY 4 /* response giving protocol address */ #define ARPOP_INVREQUEST 8 /* request to identify peer */ #define ARPOP_INVREPLY 9 /* response identifying peer */ /* * The remaining fields are variable in size, * according to the sizes above. */ #ifdef COMMENT_ONLY u_char ar_sha[]; /* sender hardware address */ u_char ar_spa[]; /* sender protocol address */ u_char ar_tha[]; /* target hardware address */ u_char ar_tpa[]; /* target protocol address */ #endif };
ダブルロックの有用性について
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でやりたいひとがいる