2017-09-01

BSDのNW処理部分の設計実装

自分用雑記. まだ書きかけです.

FreeBSDの黄色い本を読んで自分なりに要約, またSTCPの設計実装のためのメモここで出てくる典型的例とはBSD カーネル内での実装のことである.

ソースは以下から入手した - ftp://ftp.freebsd.org/pub/FreeBSD/releases/

2017-09-01

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
1. 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
};

2017-09-01

ダブルロックの有用性について

サイボウズ

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

これが従来型。以上でした。

2017-05-06

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のスライド)

f:id:slankdev:20170508005046p:plain

引用: https://www.iovisor.org

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までとれるらしい。恐ろしい。。

命令セット

ここで書くと長くなってしまうので、別の記事に分割した。そちらを参照すること。

slankdev.hatenablog.com

活用例

bcc (Generic Tracing Tool)
seccomp
socket filter

その他キーワード

tc
iptables (xt_bof)
xdp
lwt

2017-05-06

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

FreeBSDのソースコード (どこだったかわすれた。)

2017-05-06

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

2017-05-06

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
- FPGA
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でやりたいひとがいる

高速通信計算研究所

slankdevの報告

BSDのNW処理部分の設計実装

BSDのARP実装についてメモ

どこを参照したか

ARP処理部分の流れ

ARPでの代表的関数

Glossary

よく使われる構造体

ダブルロックの有用性について

はじめに通常のロックについて

ダブルロックとは

C++のスレッドセーフロックの確認

BPFに関する情報収集

BPFとは,何をするためのものか

構成

cBPF,eBPF

命令セット

活用例

その他キーワード

cBPF命令セット

Encoding

ALU

Memory Access

Branch

Misc

Reference

eBPF命令セット

Encoding

ALU

Byteswap

Memory Access

Branch

Reference

The White Paper of Packet Processing 作成のためのMemo

Hardware と Softwareでの選択はどのようにしておこなうのか。

組織

その他