LinuxのBPF : (5) eBPFによるLinux Kernel Tracing
eBPFによるカーネルトレース
一番最初に書いた通り，eBPFはLinuxのトレーサとして利用できます．
カーネルがeBPFプログラムを実行する場合，BPFインタプリタにctxが渡されます（jit化されている場合も同様です）．
https://github.com/torvalds/linux/blob/v4.12/kernel/bpf/core.c#L766
/* Named registers */ ... #define ARG1 regs[BPF_REG_ARG1] // これは BPF_REG_R1 ... static unsigned int __bpf_prog_run(void *ctx, const struct bpf_insn *insn) { ... ARG1 = (u64) (unsigned long) ctx; ... // インタプリタによる処理の実行
このctxはeBPFプログラムをどこにアタッチするかで異なります．
BPFでパケットフィルタリングをする際は，パケットの受信or送信のタイミングでctxとしてskbuffのポインタが渡されてeBPFプログラムが実行されていました．
この構造を応用して，カーネル内の様々なイベントに対して，ユーザが作成したeBPFプログラムを適当なctxの下で実行することでトレースを実現します．
eBPF Program Type
eBPFプログラムの種類は，eBPF Program Typeで区別されます．このProgram TypeはbpfシステムコールでeBPFプログラムをロードする際に指定します．
Linux 4.12時点では以下のようなProgram Typeが存在します．
https://github.com/torvalds/linux/blob/v4.12/include/trace/events/bpf.h#L12
#define __PROG_TYPE_MAP(FN) \ FN(SOCKET_FILTER) \ FN(KPROBE) \ FN(SCHED_CLS) \ FN(SCHED_ACT) \ FN(TRACEPOINT) \ FN(XDP) \ FN(PERF_EVENT) \ FN(CGROUP_SKB) \ FN(CGROUP_SOCK) \ FN(LWT_IN) \ FN(LWT_OUT) \ FN(LWT_XMIT)
今までSOCKET_FILTERとしてのeBPFをずっと見てきた訳ですが，実際にはこれだけの種類があります．
どの用途としてeBPFプログラムを作成するかによって，eBPFプログラムの引数や，eBPFプログラムの戻り値の意味，eBPFプログラムから呼ぶことが可能なカーネル内の関数，さらにはeBPFプログラム作成のために使えるライブラリの種類も変わってきます．
特にカーネルトレース機能としてのeBPFを考える場合，kprobe, tracepoint, perf_event あたりが重要になります． kprobeやperfは元々eBPF以前からカーネルに存在したトレーシング機能ですが，それらの様々なフックポイントに対してeBPFプログラムがアタッチできるようになっています．
ちなみに，カーネルのどのバージョンでBPFのどの機能がサポートされているかというのは，以下のbccの資料がまとまっています． https://github.com/iovisor/bcc/blob/master/docs/kernel-versions.md
bccのトレースツール群
前回簡単に説明したbccには様々なトレーシングツールがデフォルトで含まれています．
これらのツールで何がトレースできるのかというのは，以下のbccの図にまとまっています．
公式のチュートリアルに一部のみですが機能の説明があります． おそらく，今後もツール群は増えていくものと思われます．
bccでkprobeを利用したトレースの例
bccでトレースプログラムを書く際は，以下の資料が参考になります．
実際にトレースプログラムを書く際は，bccのツール群の中で自分の目的にもっとも近いものを参考にするのがいいかと思います．
例えば，uprobeを利用してあるPIDのプロセスを監視し，strlen()を呼び出したときの文字列を表示するプログラムは以下のようになります．
https://github.com/iovisor/bcc/blob/master/examples/tracing/strlen_snoop.py
#!/usr/bin/python # # strlen_snoop Trace strlen() library function for a given PID. # For Linux, uses BCC, eBPF. Embedded C. # # USAGE: strlensnoop PID # # Try running this on a separate bash shell. # # Written as a basic example of BCC and uprobes. # # Copyright 2016 Netflix, Inc. # Licensed under the Apache License, Version 2.0 (the "License") from __future__ import print_function from bcc import BPF from os import getpid import sys if len(sys.argv) < 2: print("USAGE: strlensnoop PID") exit() pid = sys.argv[1] # load BPF program bpf_text = """ #include <uapi/linux/ptrace.h> int printarg(struct pt_regs *ctx) { if (!PT_REGS_PARM1(ctx)) return 0; u32 pid = bpf_get_current_pid_tgid(); if (pid != PID) return 0; char str[80] = {}; bpf_probe_read(&str, sizeof(str), (void *)PT_REGS_PARM1(ctx)); bpf_trace_printk("%s\\n", &str); return 0; }; """ bpf_text = bpf_text.replace('PID', pid) b = BPF(text=bpf_text) b.attach_uprobe(name="c", sym="strlen", fn_name="printarg") # header print("%-18s %-16s %-6s %s" % ("TIME(s)", "COMM", "PID", "STRLEN")) # format output me = getpid() while 1: try: (task, pid, cpu, flags, ts, msg) = b.trace_fields() except ValueError: continue if pid == me or msg == "": continue print("%-18.9f %-16s %-6d %s" % (ts, task, pid, msg))
b.attach_uprobe(name="c", sym="strlen", fn_name="printarg") でstrlen()が呼ばれたときにprintarg()を実行するようになります．uprobeのctxから関数の引数にアクセスすることができます．printarg()の中でbpf_probe_read()を使ってstrlenの引数の文字列をスタックにコピーし，bpf_trace_printk()を使ってそれを/sys/kernel/debug/tracing/trace_pipe出力します．ユーザランドのプログラム側でtrace_fields()をすることによってそれを読み出して出力しています（ここではconcurrentな利用は考えてないです）．簡単ですね．bccで使える関数の詳細はreference guideをみてください．
他にも，kprobeを利用してblock deviceのI/Oのトレースするプログラムは以下のようになっています．
https://github.com/iovisor/bcc/blob/master/examples/tracing/disksnoop.py
b = BPF(text=""" #include <uapi/linux/ptrace.h> #include <linux/blkdev.h> BPF_HASH(start, struct request *); void trace_start(struct pt_regs *ctx, struct request *req) { // stash start timestamp by request ptr u64 ts = bpf_ktime_get_ns(); start.update(&req, &ts); } void trace_completion(struct pt_regs *ctx, struct request *req) { u64 *tsp, delta; tsp = start.lookup(&req); if (tsp != 0) { delta = bpf_ktime_get_ns() - *tsp; bpf_trace_printk("%d %x %d\\n", req->__data_len, req->cmd_flags, delta / 1000); start.delete(&req); } } """) b.attach_kprobe(event="blk_start_request", fn_name="trace_start") b.attach_kprobe(event="blk_mq_start_request", fn_name="trace_start") b.attach_kprobe(event="blk_account_io_completion", fn_name="trace_completion")
ここではeBPF mapを利用して，block deviceの開始したときに開始時刻を保存，終了時にそれを読み出して出力しています．
他にもいろんなことができるので，いろいろと遊んでみると楽しいと思います．
ちなみにbccでプログラムを書く際は
という点を知っておくといろいろと納得しやすいと思います．何故bccのプログラムで正しいeBPFプログラムが出力されるのかを追いかけると深みにはまります．
LinuxのBPF : (4) ClangによるeBPFプログラムの作成と，BPF Compiler Collection (BCC)
Clangを利用したeBPFプログラムの作成
前回はeBPFプログラムをstruct bpf_insnの配列として直接書きましたが，あまりにも面倒です．
cBPFの場合はtcpdump (libpcap)を使うことができました．
llvm3.7よりeBPFのバックエンドが追加されました．したがって，clangを利用してC言語のプログラムをeBPFプログラムにコンパイルすることが可能です．
eBPFへのコンパイル
例えば，以下のようなCプログラムを考えます．
int f(int x){ return x+1; }
-target bpfを指定することでeBPFのプログラムにコンパイルすることが可能です．
llvm IRの出力
clang -c -S -emit-llvm a.c
; ModuleID = 'a.c' source_filename = "a.c" target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128" target triple = "bpf" ; Function Attrs: noinline nounwind define i32 @f(i32) #0 { %2 = alloca i32, align 4 store i32 %0, i32* %2, align 4 %3 = load i32, i32* %2, align 4 %4 = add nsw i32 %3, 1 ret i32 %4 } attributes #0 = { noinline nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } !llvm.ident = !{!0} !0 = !{!"clang version 4.0.1 (tags/RELEASE_401/final)"}
eBPFアセンブリの出力
clang -c -S -target bpf a.c
.text .globl f .p2align 3 f: # @f # BB#0: *(u32 *)(r10 - 4) = r1 r2 = r1 r1 += 1 r0 = r1 *(u64 *)(r10 - 16) = r2 exit
eBPFプログラムの出力
clang -c -target bpf a.c
この場合，ELFバイナリが出力されます．
% objdump -x a.o a.o: file format elf64-little a.o architecture: UNKNOWN!, flags 0x00000010: HAS_SYMS start address 0x0000000000000000 Sections: Idx Name Size VMA LMA File off Algn 0 .text 00000030 0000000000000000 0000000000000000 00000040 2**3 CONTENTS, ALLOC, LOAD, READONLY, CODE SYMBOL TABLE: 0000000000000000 g .text 0000000000000000 f % readelf -x .text a.o Hex dump of section '.text': 0x00000000 631afcff 00000000 bf120000 00000000 c............... 0x00000010 07010000 01000000 bf100000 00000000 ................ 0x00000020 7b2af0ff 00000000 95000000 00000000 {*..............
ELFバイナリからeBPFプログラムだけを抽出したい場合は，以下のようにします．
objcopy -I elf64-little -O binary a.o a.bin
% ./ubpf-disassembler a.bin a.s % cat a.s stxw [r10-4], r1 mov r2, r1 add r1, 0x1 mov r0, r1 stxdw [r10-16], r2 exit
このようにしてeBPFのプログラムが作成できますが，実際にカーネル内で動作できるプログラムを作成するにはいくつか注意が必要になります．
カーネルで動作するeBPFプログラムの例
カーネルのsamples/bpf以下にC言語で書かれたeBPFの例がいくつかあります．IPの上位プロトコロル別に外向きのパケットバイト数をカウントするCのプログラムが，sockex1_kern.c及びsockex1_user.cです．
https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_kern.c (eBPFプログラム)
#include <uapi/linux/bpf.h> #include <uapi/linux/if_ether.h> #include <uapi/linux/if_packet.h> #include <uapi/linux/ip.h> #include "bpf_helpers.h" struct bpf_map_def SEC("maps") my_map = { .type = BPF_MAP_TYPE_ARRAY, .key_size = sizeof(u32), .value_size = sizeof(long), .max_entries = 256, }; SEC("socket1") int bpf_prog1(struct __sk_buff *skb) { int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol)); long *value; if (skb->pkt_type != PACKET_OUTGOING) return 0; value = bpf_map_lookup_elem(&my_map, &index); if (value) __sync_fetch_and_add(value, skb->len); return 0; }
https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_user.c
#include <stdio.h> #include <assert.h> #include <linux/bpf.h> #include "libbpf.h" #include "bpf_load.h" #include "sock_example.h" #include <unistd.h> #include <arpa/inet.h> int main(int ac, char **argv) { char filename[256]; FILE *f; int i, sock; snprintf(filename, sizeof(filename), "%s_kern.o", argv[0]); if (load_bpf_file(filename)) { printf("%s", bpf_log_buf); return 1; } sock = open_raw_sock("lo"); assert(setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, prog_fd, sizeof(prog_fd[0])) == 0); f = popen("ping -c5 localhost", "r"); (void) f; for (i = 0; i < 5; i++) { long long tcp_cnt, udp_cnt, icmp_cnt; int key; key = IPPROTO_TCP; assert(bpf_map_lookup_elem(map_fd[0], &key, &tcp_cnt) == 0); key = IPPROTO_UDP; assert(bpf_map_lookup_elem(map_fd[0], &key, &udp_cnt) == 0); key = IPPROTO_ICMP; assert(bpf_map_lookup_elem(map_fd[0], &key, &icmp_cnt) == 0); printf("TCP %lld UDP %lld ICMP %lld bytes\n", tcp_cnt, udp_cnt, icmp_cnt); sleep(1); } return 0; }
このプログラムはカーネルソースのルートでmake headers_installとしたのち，samples/bpfでmakeすればコンパイルできると思います(要clang/llc)．
load_bpf_file()はelfからeBPFプログラムを呼びだす関数です．
コードを見ればやっていることはなんとなく分かると思いますが，何故このプログラムがちゃんと動作するかは少々複雑です．
前回示したeBPFのプログラムは以下のようになっていました．
BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
BPF_LD_MAP_FD(BPF_REG_1, map_fd),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
BPF_EXIT_INSN(),
特に重要なポイントとしては，
BPF_LD_ABSはskbuffからデータを読み出す特別な命令で，R6レジスタにskbuffのポインタを格納する必要があるBPF_FUNC_map_lookup_elemを呼び出す前に，R1レジスタにeBPF mapのdescriptorを格納する
の2点です．
skbuffからのロード
まず，skbuffからのデータのロードに関して，Cでは以下のようになっています．
int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));
ここで，load_byte()はbpf_helpers.hで定義されています．
/* llvm builtin functions that eBPF C program may use to * emit BPF_LD_ABS and BPF_LD_IND instructions */ struct sk_buff; unsigned long long load_byte(void *skb, unsigned long long off) asm("llvm.bpf.load.byte");
つまり，この関数はllvm IRのintrinsicな命令を出力します．
実際にllcでeBPFプログラムを出力する際に，R6レジスタにskbuffを追加する命令が追加されます．
https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFISelDAGToDAG.cpp#L179
case ISD::INTRINSIC_W_CHAIN: { unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue(); switch (IntNo) { case Intrinsic::bpf_load_byte: case Intrinsic::bpf_load_half: case Intrinsic::bpf_load_word: { SDLoc DL(Node); SDValue Chain = Node->getOperand(0); SDValue N1 = Node->getOperand(1); SDValue Skb = Node->getOperand(2); SDValue N3 = Node->getOperand(3); SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64); Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue()); Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3); break; } }
bpf_load_byte は 最終的にBPF_ABS | <size> | BPF_LD の命令になります．
https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFInstrInfo.td#L544
let Defs = [R0, R1, R2, R3, R4, R5], Uses = [R6], hasSideEffects = 1, hasExtraDefRegAllocReq = 1, hasExtraSrcRegAllocReq = 1, mayLoad = 1 in { class LOAD_ABS<bits<2> SizeOp, string OpcodeStr, Intrinsic OpNode> : InstBPF<(outs), (ins GPR:$skb, i64imm:$imm), "r0 = *("#OpcodeStr#" *)skb[$imm]", [(set R0, (OpNode GPR:$skb, i64immSExt32:$imm))]> { bits<3> mode; bits<2> size; bits<32> imm; let Inst{63-61} = mode; let Inst{60-59} = size; let Inst{31-0} = imm; let mode = 1; // BPF_ABS let size = SizeOp; let BPFClass = 0; // BPF_LD } ... def LD_ABS_B : LOAD_ABS<2, "u8", int_bpf_load_byte>; def LD_ABS_H : LOAD_ABS<1, "u16", int_bpf_load_half>; def LD_ABS_W : LOAD_ABS<0, "u32", int_bpf_load_word>;
eBPF mapの処理
次に，eBPF mapの部分に関してですが，ロードされる前のeBPFプログラムは以下のようなオブジェクトファイルになっています．
% objdump -x sockex1_kern.o sockex1_kern.o: file format elf64-little sockex1_kern.o architecture: UNKNOWN!, flags 0x00000011: HAS_RELOC, HAS_SYMS start address 0x0000000000000000 Sections: Idx Name Size VMA LMA File off Algn 0 .text 00000000 0000000000000000 0000000000000000 00000040 2**2 CONTENTS, ALLOC, LOAD, READONLY, CODE 1 socket1 00000078 0000000000000000 0000000000000000 00000040 2**3 CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE 2 maps 00000018 0000000000000000 0000000000000000 000000b8 2**2 CONTENTS, ALLOC, LOAD, DATA 3 license 00000004 0000000000000000 0000000000000000 000000d0 2**0 CONTENTS, ALLOC, LOAD, DATA SYMBOL TABLE: 0000000000000068 l socket1 0000000000000000 LBB0_3 0000000000000000 g license 0000000000000000 _license 0000000000000000 g socket1 0000000000000000 bpf_prog1 0000000000000000 g maps 0000000000000000 my_map RELOCATION RECORDS FOR [socket1]: OFFSET TYPE VALUE 0000000000000038 UNKNOWN my_map
注目すべきは最後のrelocationに関するところで，my_mapの値はrelocatableなシンボルとなっています．
load_bpf_file()では，bpfプログラムを読み込む際に以下のことをおこなっています．
- mapsセクションからeBPF mapの情報を読み取り，eBPF mapを作成
- ELFのrelocation recordsをチェックし，必要に応じて処理をおこなう
- 最終的にeBPFプログラムをカーネルにロードする
ちなみに，BPF_FUNC_map_lookup_elemの番号はlinux/bpf.hで定義されています．
BPF Compiler Collection (BCC)
上記の例で分かるように，clangでeBPFプログラムがコンパイルできるものの，実際には何かライブラリがなければカーネル内で動作するeBPFプログラムを作成し動作させることは面倒です．また，eBPFにプログラムがコンパイルできたとしても，それがカーネル内で正しく動くかどうかは別問題です．eBPFプログラムをロードする際のverifierで弾かれる可能性も十分あります． カーネルソースのsamples/bpf以下にいくつかヘルパー関数が存在するものの，自分が作成するプログラムで使用するには少々面倒です．
BPF Compiler Collection (BCC)は，簡単にeBPFによるLinux kernel tracingを実現するためのライブラリ/ツール群です．bccは以下のような機能等があります．
- eBPFプログラムを書くために便利なライブラリの提供
- python bindings
- eBPFによる様々なトレーシングツールの提供
bccは巨大なプロジェクトですが，ここでは今までやってきたパケットの統計量の取得に関してみていきたいと思います．
インストール
本題に入る前に，インストール方法について軽くふれておくと，bccのインストール方法はここに書いてありますが，Ubuntuであれば，
sudo apt-get install binutils bcc bcc-tools libbcc-examples python-bcc
で入ると思います．あるいは，自分でコンパイルする場合は
% git clone https://github.com/iovisor/bcc
% cd bcc
% mkdir build
% cd build
% cmake ..
% make
% make install
でできると思います．最新機能を試したい場合は自分でカーネル含めてコンパイルした方がいいと思います．
bccによるプログラムの例
bccを利用してIPの上位プロトコル別に外向きパケットのバイト数をカウントするプログラムは以下のように書けます．
#include <bcc/proto.h> BPF_ARRAY(my_map, long, 256); int bpf_prog(struct __sk_buff *skb) { u8* cursor = 0; struct ethernet_t *ethhdr = cursor_advance(cursor, sizeof(*ethhdr)); if(!(ethhdr->type == 0x0800)){ // not ipv4 return -1; } struct ip_t *iphdr = cursor_advance(cursor, sizeof(*iphdr)); u32 index = iphdr->nextp; if (skb->pkt_type != PACKET_OUTGOING) return -1; long *value = my_map.lookup(&index); if (value) lock_xadd(value, skb->len); return -1; }
import time from bcc import BPF def main(): b = BPF(src_file="./sockex1.c", debug=0) f = b.load_func("bpf_prog", BPF.SOCKET_FILTER) BPF.attach_raw_socket(f, "lo") my_map = b.get_table("my_map") ICMP = 1 TCP = 6 UDP = 17 for i in range(5): print("TCP {} UDP {} ICMP {} bytes".format(my_map[TCP], my_map[UDP], my_map[ICMP])) time.sleep(1) if __name__ == "__main__": main()
BPF(src_file="...")でbpfプログラムのロード & コンパイルBPF.attach_raw_socket()でraw socketにBPFプログラムをアタッチget_table()でmapにアクセス
しています．
bccで読み込んでいるCプログラムは元のものと似ていますが，以下の特徴があります．
- bpf/proto.hを利用
BPF_ARRAYマクロを利用してeBPF mapを定義cursor_advance()関数を利用してskbuffにアクセス
また，eBPFのプログラムでフィルタリングをする場合，戻り値はuserspaceに返すバイトの長さ（の最大）を指定します．普通はパケットをドロップしたい場合は0, そうでない場合は-1にします．といっても今回の例ではユーザプログラム側では特にパケットを受信してないのであまり深い意味は持たないです．（__sk_receive_skb()の中のsk_filter_trim_capからbpfのプログラムが呼ばれ，その戻り値に応じてskbuffの長さが変更 or dropされます）．
BPF.attach_raw_socket(f, "lo")の後にf.sockでeBPFプログラムがアタッチされたsocketのdescriptorが取得できます．
cursor_advance()
cursor_advance()の定義は以下のようになっています．
#define cursor_advance(_cursor, _len) \ ({ void *_tmp = _cursor; _cursor += _len; _tmp; })
ということで，上のcursor_advance()のコードは以下のようになります．
u8* cursor = 0; struct ethernet_t *ethhdr = ({void *_tmp = cursor; cursor += sizeof(*ethhdr); _tmp;});
これをそのまま解釈すると，最初の状態ではethhdrには0が代入されて，cursorはsizeof(*ethhdr)の分だけ加算されることになります．
さて，それではどうしてこれでskbuff内のパケットデータにアクセスできるのかというと，まずethernet_tは以下のように宣言されています．
#define BPF_PACKET_HEADER __attribute__((packed)) __attribute__((deprecated("packet"))) struct ethernet_t { unsigned long long dst:48; unsigned long long src:48; unsigned int type:16; } BPF_PACKET_HEADER;
ethernet_tには"packet"というattributeがつけられています．bccがプログラムをコンパイルする際に，このattirbuteがついている変数へのassignの場合，bpf_dext_pkt()を出力します．
StatusTuple CodegenLLVM::visit_packet_expr_node(PacketExprNode *n) {
auto p = proto_scopes_->top_struct()->lookup(n->id_->name_, true);
VariableDeclStmtNode *offset_decl, *skb_decl;
Value *offset_mem, *skb_mem;
TRY2(lookup_var(n, "skb", scopes_->current_var(), &skb_decl, &skb_mem));
TRY2(lookup_var(n, "$" + n->id_->name_, scopes_->current_var(), &offset_decl, &offset_mem));
if (p) {
auto f = p->field(n->id_->sub_name_);
if (f) {
size_t bit_offset = f->bit_offset_;
size_t bit_width = f->bit_width_;
if(n->bitop_){
...
} else {
emit("bpf_dext_pkt(pkt, %s + %zu, %zu, %zu)", n->id_->c_str(), bit_offset >> 3, bit_offset & 0x7, bit_width);
Function *load_fn = mod_->getFunction("bpf_dext_pkt");
if (!load_fn) return mkstatus_(n, "unable to find function bpf_dext_pkt");
LoadInst *skb_ptr = B.CreateLoad(skb_mem);
Value *skb_ptr8 = B.CreateBitCast(skb_ptr, B.getInt8PtrTy());
LoadInst *offset_ptr = B.CreateLoad(offset_mem);
Value *skb_hdr_offset = B.CreateAdd(offset_ptr, B.getInt64(bit_offset >> 3));
expr_ = B.CreateCall(load_fn, vector<Value *>({skb_ptr8, skb_hdr_offset,
B.getInt64(bit_offset & 0x7), B.getInt64(bit_width)}));
// this generates extra trunc insns whereas the bpf.load fns already
// trunc the values internally in the bpf interpeter
//expr_ = B.CreateTrunc(pop_expr(), B.getIntNTy(bit_width));
}
} else {
emit("pkt->start + pkt->offset + %s", n->id_->c_str());
return mkstatus_(n, "unsupported");
}
}
return StatusTuple(0);
}
bpf_dext_pkt()は以下のようになっています．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L404
u64 bpf_dext_pkt(void *pkt, u64 off, u64 bofs, u64 bsz) { if (bofs == 0 && bsz == 8) { return load_byte(pkt, off); } else if (bofs + bsz <= 8) { return load_byte(pkt, off) >> (8 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 16) { return load_half(pkt, off); } else if (bofs + bsz <= 16) { return load_half(pkt, off) >> (16 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 32) { return load_word(pkt, off); } else if (bofs + bsz <= 32) { return load_word(pkt, off) >> (32 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 64) { return load_dword(pkt, off); } else if (bofs + bsz <= 64) { return load_dword(pkt, off) >> (64 - (bofs + bsz)) & MASK(bsz); } return 0; }
load_byte()から最終的にllvm.bpf.load.byteが出力されます．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287
struct sk_buff; unsigned long long load_byte(void *skb, unsigned long long off) asm("llvm.bpf.load.byte");
…というのが自分の理解ですが，自分のllvmの知識は圧倒的に不足しているので違ったらごめんなさい．
BPF_ARRAY
BPF_ARRAY()マクロは最終的に以下のように展開されます．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287
// Changes to the macro require changes in BFrontendAction classes #define BPF_F_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries, _flags) \ struct _name##_table_t { \ _key_type key; \ _leaf_type leaf; \ _leaf_type * (*lookup) (_key_type *); \ _leaf_type * (*lookup_or_init) (_key_type *, _leaf_type *); \ int (*update) (_key_type *, _leaf_type *); \ int (*insert) (_key_type *, _leaf_type *); \ int (*delete) (_key_type *); \ void (*call) (void *, int index); \ void (*increment) (_key_type); \ int (*get_stackid) (void *, u64); \ u32 max_entries; \ int flags; \ }; \ __attribute__((section("maps/" _table_type))) \ struct _name##_table_t _name = { .flags = (_flags), .max_entries = (_max_entries) }
あまり真面目にコードを追ってないですが，どうやらbccがプログラムをパースする際に，mapの定義があったらそのmapを作成しているようです． https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/frontends/b/codegen_llvm.cc#L1103
StatusTuple CodegenLLVM::visit_table_decl_stmt_node(TableDeclStmtNode *n) {
...
int map_fd = bpf_create_map(map_type, key->bit_width_ / 8, leaf->bit_width_ / 8, n->size_, 0);
...
}
lookup()は最終的にbpf_map_lookup_elem()が呼ばれます．
StatusTuple CodegenLLVM::emit_table_lookup(MethodCallExprNode *n) {
TableDeclStmtNode* table = scopes_->top_table()->lookup(n->id_->name_);
IdentExprNode* arg0 = static_cast<IdentExprNode*>(n->args_.at(0).get());
IdentExprNode* arg1;
StructVariableDeclStmtNode* arg1_type;
auto table_fd_it = table_fds_.find(table);
if (table_fd_it == table_fds_.end())
return mkstatus_(n, "unable to find table %s in table_fds_", n->id_->c_str());
Function *pseudo_fn = mod_->getFunction("llvm.bpf.pseudo");
if (!pseudo_fn) return mkstatus_(n, "pseudo fd loader doesn't exist");
Function *lookup_fn = mod_->getFunction("bpf_map_lookup_elem_");
if (!lookup_fn) return mkstatus_(n, "bpf_map_lookup_elem_ undefined");
CallInst *pseudo_call = B.CreateCall(pseudo_fn, vector<Value *>({B.getInt64(BPF_PSEUDO_MAP_FD),
B.getInt64(table_fd_it->second)}));
Value *pseudo_map_fd = pseudo_call;
TRY2(arg0->accept(this));
Value *key_ptr = B.CreateBitCast(pop_expr(), B.getInt8PtrTy());
expr_ = B.CreateCall(lookup_fn, vector<Value *>({pseudo_map_fd, key_ptr}));
...
}
最初の例ではbpf_map_lookup_elem()の引数のdescriptorはプログラムをコンパイル後に書き換えていましたが，bccの場合は最初にmapを作ってそのdescriptorをそのままllvmのIRに埋め込んでいるのだと思います．多分．
このように，bccはeBPFプログラムが書きやすいようなmodified Cを提供しています．
もう少し具体的なパケットフィルタリングに関する応用例はbccの examples/networking 以下にあります．（例えばhttp_filterなど)
まとめ
clangによるeBPFプログラムの作成方法と，bccを利用したeBPFプログラムの作成方法の基礎について書きました．
次回は今まで説明してこなかったeBPFを利用したkernel tracingについて書こうと思います．
LinuxのBPF : (3) eBPFの基礎
はじめに（注意）
ちょうど一年ぐらい前にLinuxのBPFについて記事を書いていました． 最初の記事は古典的なBPFについて，二番目の記事はseccompについてです． eBPFに関する文章も書いていて，てっきり公開していたと思っていたのですが今下書きのまま保存され一年以上放置されていたことに気づきました.. BPFの開発は非常に活発で，ここに書いてる情報が古い可能性もあるのですが，せっかくなので公開しておきます．
この記事はLinux 4.7時点での情報に基づきます．プログラムはLinux 4.7（Ubuntu Xeniel）で動作確認しています．
extended BPF (eBPF)
前々回と前回のエントリでLinuxにおいてBPFのプログラムを利用してパケットフィルタリングやseccompを利用する例を見ました．BPFを利用する利点は，大きく以下の2つです．
- ユーザがフィルタプログラムを自由に設定できる
- コードはカーネル内安全に実行される (実行前に静的に安全性をチェック）
そんなBPFですが，これを拡張し，カーネル内の様々なイベントに対してユーザが定義した処理を実行できるようにすれば，様々なトレースに使えるのではないかという議論が2011年ごろから*1起こりました． そして，その機能実現のためにBPFのレジスタマシンを拡張したextended BPF (eBPF)が考案されました． 昔からあるBPFをclassic BPF (cBPF)，extended BPFをeBPFあるいはinternal BPFとして区別します*2．
eBPFは以下のような特徴/機能があります．
- 10個のレジスタ (cBPFは2つ)
- R0 : 戻り値格納用
- R1-R5 : 引数
- R6-R9 : BPFプログラムが利用
- R10: スタックへアクセスするためのフレームポインタ (read only)
- レジスタ幅は64bit (cBPFは32bit)
- ジャンプが jt/jf ではなく jt/fall through に
- 負の方向のジャンプを許可
- 他のbpfプログラムへのジャンプを許可 (ただし無限ループできないように遷移回数は制限されている)
bpf_call命令によるカーネル内の関数の呼び出し- eBPF mapによるデータのやりとり
eBPF map
eBPFの中でも特にeBPF mapはダイナミックトレースを実現するのに欠かせない機能です． eBPF mapはbpfで利用可能なデータ構造で，eBPFプログラム間やユーザスペース/カーネルスペースのプログラム間でのデータのやりとりに利用します． 例えばeBPFマップを利用することで任意の型のkey/valueの連想配列を作成することができます． eBPF mapはまず最初にユーザプロセスが作成します．BPFプログラムはそのmapにプログラム中からアクセスすることができます．
eBPFプログラムの例
eBPF mapを作成したり，あるいはeBPFのプログラムをイベントにアタッチするにはLinux 3.18から追加されたbpf(2)システムコールを利用します．
bpf(2)のマニュアルに情報がありますが，とりあえず現在(2016/8/1)においては情報がやや古いです..
カーネルのソースのsamples/bpf以下にeBPFのプログラムの例があるので，それと
合わせてドキュメントを見た方がいいと思います．
ここでは，サンプルの中でお手頃なsock_exasmple.cを見てみましょう．
このプログラムはeBPFを利用して，受信したTCPパケット，IPパケット，ARPパケットの種類をカウントするものです．
/* eBPF example program: * - creates arraymap in kernel with key 4 bytes and value 8 bytes * * - loads eBPF program: * r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)]; * *(u32*)(fp - 4) = r0; * // assuming packet is IPv4, lookup ip->proto in a map * value = bpf_map_lookup_elem(map_fd, fp - 4); * if (value) * (*(u64*)value) += 1; * * - attaches this program to eth0 raw socket * * - every second user space reads map[tcp], map[udp], map[icmp] to see * how many packets of given protocol were seen on eth0 */ #include <stdio.h> #include <unistd.h> #include <assert.h> #include <linux/bpf.h> #include <string.h> #include <stdlib.h> #include <errno.h> #include <sys/socket.h> #include <arpa/inet.h> #include <linux/if_ether.h> #include <linux/ip.h> #include <stddef.h> #include "libbpf.h" static int test_sock(void) { int sock = -1, map_fd, prog_fd, i, key; long long value = 0, tcp_cnt, udp_cnt, icmp_cnt; map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value), 256, 0); if (map_fd < 0) { printf("failed to create map '%s'\n", strerror(errno)); goto cleanup; } struct bpf_insn prog[] = { BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */), BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */ BPF_LD_MAP_FD(BPF_REG_1, map_fd), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */ BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */ BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */ BPF_EXIT_INSN(), }; prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog), "GPL", 0); if (prog_fd < 0) { printf("failed to load prog '%s'\n", strerror(errno)); goto cleanup; } sock = open_raw_sock("lo"); if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)) < 0) { printf("setsockopt %s\n", strerror(errno)); goto cleanup; } for (i = 0; i < 10; i++) { key = IPPROTO_TCP; assert(bpf_lookup_elem(map_fd, &key, &tcp_cnt) == 0); key = IPPROTO_UDP; assert(bpf_lookup_elem(map_fd, &key, &udp_cnt) == 0); key = IPPROTO_ICMP; assert(bpf_lookup_elem(map_fd, &key, &icmp_cnt) == 0); printf("TCP %lld UDP %lld ICMP %lld packets\n", tcp_cnt, udp_cnt, icmp_cnt); sleep(1); } cleanup: /* maps, programs, raw sockets will auto cleanup on process exit */ return 0; } int main(void) { FILE *f; f = popen("ping -c5 localhost", "r"); (void)f; return test_sock(); }
プログラムの主要点について見ていきいます．
eBPFのmapの作成
map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value), 256, 0);
bpf_create_map()によって大きさが256のeBPF mapを作成します．map_fdがこのeBPF mapのdescriptorです．
eBPFプログラムの作成
/* * - loads eBPF program: * r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)]; * *(u32*)(fp - 4) = r0; * // assuming packet is IPv4, lookup ip->proto in a map * value = bpf_map_lookup_elem(map_fd, fp - 4); * if (value) * (*(u64*)value) += 1; */ struct bpf_insn prog[] = { BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */), BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */ BPF_LD_MAP_FD(BPF_REG_1, map_fd), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */ BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */ BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */ BPF_EXIT_INSN(), };
cBPFと同様に，define済みのマクロを利用してeBPFのプログラムを作成することができます．
<linux/bpf.h>にeBPFの命令や，eBPFプログラムから呼び出すことのできる関数が宣言されています．
eBPFについても詳しくはカーネルのドキュメントに書いてあります．
このプログラムが何をしているかというのは，コメントに書いてある通りですが，ポイントとしては
- R1-R5のレジスタが引数として使われる
- R10はフレームポインタ
- 最初R1にはパケットデータを保持する
sk_buffのポインタが格納されている BPF_LD_ABS(正確にはBPF_ABS | <size> | BPF_LD）は特別な命令で，sk_buffからデータを読み出す．このときR6レジスタにsk_buffのポインタを格納する．（注: パケットデータはsk_buff構造体の中のポインタからアクセスするため，単純なeBPFの命令ではアクセスできない．そのため特別扱いしている)BPF_CALLでBPF_FUNC_map_lookup_elem（この関数はカーネル内にあらかじめ存在）を呼び出しているBPF_FUNC_map_lookup_elemの第一引数はeBPF mapのfd，第二引数はキーのアドレス．ここではスタック上にキーを格納し，それを渡している．戻り値はキーに対応するマップが見つかったらそのアドレス
eBPFフィルタプログラムの利用
BPFでパケットフィルタリングする場合は，setsockopt(2)を使ってソケットのfdに対してcBPFのプログラムをアタッチすることができました．
このとき実はcBPFのプログラムは内部でeBPFのプログラムに変換され実行されます．
それでは，eBPFプログラムそのものをソケットにアタッチすることはできるのでしょうか? 答えはもちろんイエスです． アタッチする手順は以下の通りです．
bpfシステムコール（Linux 3.18から追加）を使って，まずカーネル空間にeBPFのプログラムを追加setsockoptの第二引数にSO_ATTACH_BPFを指定してeBPFのプログラムをアタッチする
上のプログラムではbpfシステムコールの代わりに，そのラッパー関数であるbpf_prog_loadを利用しています．
prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog), "GPL", 0); if (prog_fd < 0) { printf("failed to load prog '%s'\n", strerror(errno)); goto cleanup; } sock = open_raw_sock("lo"); if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)) < 0) { printf("setsockopt %s\n", strerror(errno)); goto cleanup; }
eBPFプログラムはカーネル内で実行されるため，カーネルモジュールと同様にライセンスを明示する必要があります．
bpf_prog_loadの第四引数でライセンスとして"GPL"を指定しています．GPL compatibleなライセンスにしておかないとカーネル内の他のGPLの関数が呼べなくなります．
setsockoptの挙動
BPFに関するsetsockoptの挙動を整理しておくと，
- cBPFプログラムのロードは，
SO_ATTACH_FILTER- このとき，
sk_attach_filterが呼ばれる- さらに，
sk_attach_filterから，__get_filter()>bpf_prepare_filter()>bpf_migrate_filter()>bpf_convert_filter()と関数が呼ばれcBPFはeBPFに変換される
- さらに，
- このとき，
- eBPFプログラムのロードは，
SO_ATTAH_BPF- このとき，
sk_attach_bpfが呼ばれる
- このとき，
JIT
Linux 3.16からeBPFに対してもJITが使えるようになりました． ちなみに，BPFをJIT化しようとする議論は2011年ごろからありました（A JIT for packet filters）．
/proc/sys/net/core/bpf_jit_enable を1にするとjitが有効になります．また，2にするとdebugモードとなり，jitの結果がdemsgで確認できます．
デフォルトは無効化（0）されています．
ソース
eBPFの主なソースはkernel/bpfにあります．また，tools/net以下にBPFのアセンブラ/ディスアセンブラがあります． eBPFのインタプリタに興味がある方は，eBPFのユーザランド実装であるubpfを見た方が分かりやすいかもしれません．
まとめ
今回はeBPFの基礎について簡単に説明しました．
eBPFによるトレースの方法や，実際にeBPFプログラムを作成する方法（もちろん，#defineを使わないで作成する方法があります）などは機会があれば別に書こうと思います．
nomによるnumpyデータのパース
nom
nomはrust製のパーサコンビネーターライブラリです．
個人的にはno_stdでの動作をサポートしてる点が嬉しいです．
今回勉強のためにnomでnumpyのファイル（のヘッダ）をパースしてみます．
numpyのフォーマット
今回は以下のようにして作成したデータをパースしてみます．
$ python -c "import numpy as np; a = np.arange(9).reshape(3,3); np.save('a.npy', a)"; $ hexdump -C a.npy 00000000 93 4e 55 4d 50 59 01 00 46 00 7b 27 64 65 73 63 |.NUMPY..F.{'desc| 00000010 72 27 3a 20 27 3c 69 38 27 2c 20 27 66 6f 72 74 |r': '<i8', 'fort| 00000020 72 61 6e 5f 6f 72 64 65 72 27 3a 20 46 61 6c 73 |ran_order': Fals| 00000030 65 2c 20 27 73 68 61 70 65 27 3a 20 28 33 2c 20 |e, 'shape': (3, | 00000040 33 29 2c 20 7d 20 20 20 20 20 20 20 20 20 20 0a |3), } .| 00000050 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................| 00000060 02 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 |................| 00000070 04 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 |................| 00000080 06 00 00 00 00 00 00 00 07 00 00 00 00 00 00 00 |................| 00000090 08 00 00 00 00 00 00 00 |........| 00000098
フォーマットの公式ドキュメント: https://docs.scipy.org/doc/numpy-dev/neps/npy-format.html
以下のようなフォーマットになっているようです．
- 先頭は
\x93NUMPY - 次の1byteがメジャーバージョン
- 次の1byteがマイナーバージョン
- メジャーバージョン1の場合，次の2byteがヘッダ長（この後に続くpythonのdictを表す文字列の長さ（パディング含む））
- メジャーバージョン2の場合，次の4byteがヘッダ長
- 次に文字列でpythonのdictの形式で
descr,fortran_order,shapeが格納されているdescr: numpyのdtype．通常は'<u8'とか'<f8'などの文字列だが，structured arrayの場合は型情報のリストになる．fortran_order:TrueかFalseshape: タプルでarrayの形を表す
- その後，アラインメントを揃えるために適当なスペースがあり，最後に改行(
\x0a) - その後が実際のデータ．データの格納形式は
descrで指定されたdtypeに基づく
完成品1
とりあえず，1. dictの部分はdescr, fortran_order, shapeの順に格納されていると仮定 *1 2. dtypeの部分はstrucured arrayは考えないで，endianとワードサイズのみだけ取り出す として作ってみました．
#[derive(Debug, PartialEq)] pub struct NpyHeader { major_version: u8, minor_version: u8, header_len: u32, little_endian: bool, fortran_order: bool, word_size: u32, shape: Vec<u8>, } named!(pub parse_header<NpyHeader>, do_parse!( tag!(b"\x93NUMPY") >> major_version: le_u8 >> minor_version: le_u8 >> header_len: alt!( cond_reduce!(major_version == 1, map!(le_u16, |x| x as u32)) | cond_reduce!(major_version == 2, le_u32)) >> tag!("{'descr': '") >> little_endian: map!(alt!(tag!("<") | tag!(">")), |x| x == b"<") >> le_u8 >> // skip byte word_size: map_res!(map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str) >> tag!("', 'fortran_order': ") >> fortran_order: map!(alt!(tag!("True") | tag!("False")), |s| s == b"True") >> tag!(", 'shape': ") >> shape: delimited!(char!('('), separated_list!(ws!(char!(',')), map_res!( map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str)), char!(')')) >> tag!(", }") >> take_while!(call!(|c| c == b' ')) >> tag!("\n") >> ( NpyHeader{ major_version, minor_version, header_len, little_endian, fortran_order, word_size, shape, } ) ) );
実行結果
#[cfg(test)] mod test { use super::*; use std::fs::File; use std::io::Read; #[test] fn parse_nom() { let mut buf = vec![]; File::open("./a.npy") .expect("failed to open file") .read_to_end(&mut buf) .unwrap(); let r = parse_header(&buf); println!("{:?}", r); assert_eq!( r.to_result().ok().unwrap(), NpyHeader { major_version: 1, minor_version: 0, header_len: 70, little_endian: true, fortran_order: false, word_size: 8, shape: vec![3, 3], } ); } }
$ cargo test -- --nocapture
...
running 1 test
Done([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], NpyHeader { major_version: 1, minor_version: 0, header_len: 70, little_endian: true, fortran_order: false, word_size: 8, shape: [3, 3] })
test test::parse_nom ... ok
ポイント
named!()マクロで関数を定義する．今回の場合fn parse_header(input: &[u8]) -> nom::IResult<&[u8], NpyHeader>みたいな関数が定義されることになる．nom::IResult<I,O>の型パラメータは，Iがまだパースしていない残りの部分の型，Oがパースした結果の型- 正しくパースされると，
Done(I,O)が返る．エラーだったらError(Err)かIncomplete(Needed)
do_parse!()マクロを使うと，IResultを返す関数を>>で繋げることができる- 具体的には，
do_parse!(I->IResult<I,A> >> I->IResult<I,B> >> ... I->IResult<I,X> , ( O ) ) => I -> IResult<I, O>の形になる - 最後に
()で囲んだものが最終的な戻り値 - 基本的にnomがいろいろな関数とマクロを提供しているので，それを
do_parse!()の中で組み合わせていくことになる do_parse!()の中でxxx: yyyとするとパース処理した結果が後からxxxで参照できる
- 具体的には，
tag!()で指定したバイト列の読み取りle_u8はlittle endianで1byte読み取る関数*2．同様の関数にle_u16とかle_u32などalt!()は複数のパーサを受け取り，先頭から試していって最初に成功した結果を返すalt!(tag!("True") | tag!("False")の部分は最初がtag!("True")（短い方の文字列)でなければならない．これは"False"が先の場合，"False"にマッチするか確認するために5文字読み込むので，次に"True"にマッチするか確認する際は文字長が足らないため必ず失敗する．詳細はドキュメント参照
- パース処理で得られた部分の型を変換したい場合は，
map!()あるいはmap_res!()を使う- スライスを文字列へ変換:
map_res!(xxxx, std::str::from_utf8) - 文字列を数値へ変換:
map_res!(xxxx, std::str::FromStr::from_str)
- スライスを文字列へ変換:
if処理をしたいときはcond!(),if-else処理をしたい時はalt!()とcond_reduce!()を組み合わせるdelimited!(opening, X, closing)でXを取り出すws!()は各トークン間のスペースを自動で取り除くseparated_list!()でセパレータで区切られた値をVecで取得できる．ちなみに，もし末尾にセパレータがある場合そのセパレータは残る (例えば1,2,3,みたいな場合)
完成品2
もう少し真面目にdictをパースしてみたのがこちら．といっても手抜きでdictのvalueとしてboolかstringか数値のタプルかの3つしか考えてないですが．上の例はあえて全部一つのdo_parse!()にまとめましたが実際には分割した方が，可読性もテストしやすさも向上します．本当ならdictをパースしたあと，さらに個別の各要素をチェックしていく必要がありますが，飽きてきたのでこの辺で.. ちなみにもしdict部分に変なデータがあってもそのままパースされることになります．
named!(to_u8<u8>, map_res!( map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str) ); #[derive(Debug, PartialEq)] pub enum DictValue<'a> { Str(&'a str), Bool(bool), Tuple(Vec<u8>), } named!(tuple_value<DictValue>, map!( delimited!( char!('('), separated_list!(ws!(char!(',')), to_u8), pair!(opt!(ws!(char!(','))), char!(')'))), DictValue::Tuple) ); named!(bool_value<DictValue>, map!(alt!(tag!("True") | tag!("False")), |s| DictValue::Bool(s == b"True")) ); named!(quoted_string<&str>, map_res!( delimited!( char!('\''), is_not!("'"), char!('\'')), std::str::from_utf8) ); named!(string_value<DictValue<'a>>, map!( map_res!( delimited!( char!('\''), is_not!("'"), char!('\'')), std::str::from_utf8), DictValue::Str) ); named!(key_value<(&str, DictValue)>, do_parse!( key: quoted_string >> ws!(char!(':')) >> value: alt!(string_value | bool_value | tuple_value) >> (key, value) ) ); named!(pub parse_dict<HashMap<&str,DictValue>>, delimited!( pair!(char!('{'), opt!(multispace)), map!(many0!(terminated!(key_value, opt!(ws!(char!(','))))), |vec: Vec<_>| vec.into_iter().collect()), pair!(opt!(multispace), char!('}'))) ); #[derive(Debug, PartialEq)] pub struct NpyHeader2<'a> { major_version: u8, minor_version: u8, header_len: u32, dict: HashMap<&'a str, DictValue<'a>>, } named!(pub parse_header2<NpyHeader2>, do_parse!( tag!(b"\x93NUMPY") >> major_version: le_u8 >> minor_version: le_u8 >> header_len: alt!( cond_reduce!(major_version == 1, map!(le_u16, |x| x as u32)) | cond_reduce!(major_version == 2, le_u32)) >> dict: parse_dict >> take_while!(call!(|c| c == b' ')) >> tag!("\n") >> ( NpyHeader2{ major_version, minor_version, header_len, dict, } ) ) );
実行結果
#[test] fn parse_nom2() { let mut buf = vec![]; File::open("./a.npy") .expect("failed to open file") .read_to_end(&mut buf) .unwrap(); let r = parse_header2(&buf); let mut dict = HashMap::new(); dict.insert("descr", DictValue::Str("<i8")); dict.insert("fortran_order", DictValue::Bool(false)); dict.insert("shape", DictValue::Tuple(vec![3,3])); println!("{:?}", r); assert_eq!( r.to_result().ok().unwrap(), NpyHeader2 { major_version: 1, minor_version: 0, header_len: 70, dict: dict, } ); }
$ cargo test -- --nocapture
...
Done([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], NpyHeader2 { major_version: 1, minor_version: 0, header_len: 70, dict: {"descr": Str("<i8"), "fortran_order": Bool(false), "shape": Tuple([3, 3])} })
ポイント
alt!()を使う場合，各パーサの戻り値は同じでなければならない．今回はenumを使って対処している
余談
後から気づきましたが，nomを使ってnumpyのstructured arraysをパースしてるnpy-rsというのがあるのでnumpyデータをちゃんとパースしたい人は参考になるかもしれません．dictのパースはValueのenumを作ってパースしてけば綺麗に書ける訳ですね．確かに．
感想
マクロはあまり好きではないので最初とっつきにくい印象がありましたが，書いていくうちにまぁこんなもんかもしれないと思いました．同じ処理をするにもいろいろな書き方ができるので，ライブラリが提供しているマクロ/関数をうまく活用することが簡潔なコードを書く鍵になります．幸いnomで書かれたパーサはいろいろあるのでそれが参考になります．書いていて少し気になったのが，synstasticでの文法チェックが少々遅いこと．体感として明らかにnomでマクロを定義する前と後で遅くなりました．今回の簡単な例でも1s近く遅くなった気がします．これはnom（というかマクロ）の問題なのか，それ以外の問題なのかはわかりませんが..
[rust]ZST/DSTによるflexible array memberの実現
- flexible array memberとは
- ZSTを使う方法
- DSTを使う方法
flexible array memberとは
flexible array memberとはずばり，C言語で以下のようなサイズ定義を持たない構造体メンバのことです（C99から標準）．
struct X{ size_t len; char value[]; }
この構造体は以下のようにして使うことができます．
size_t len = 10; struct X *p = (struct X*)malloc(sizeof(struct X) + len); p->len = len; p->value[0] = 'a'; p->value[1] = 'b'; ...
このように，flexible array memberを使用することで（ヘッダ+可変サイズなデータ）を持つ構造を簡潔に表現できます．普通はvalueは適当なポインタで持てばいいと思いますが，メモリ的にヘッダとデータが連続して欲しい場合，あるいは連続したバッファが与えられてそこにデータ構造を作成する場合などに有用です．
ちなみにsizeof(struct X)の値はflexible array memberを除いたサイズ（上の例だと実質的にsizeof(size_t)）になります．
ZSTを使う方法
rustにおいて，flexible array memberそのものとずばり対応するものはありません． 似たようなことをしたい場合は，Zero Sized Types (ZSTs) あるいは Dynamically Sized Types (DSTs)を使います．
最初に言っておくと，ZSTを使う場合はなんちゃってflexible array memberになります．
ZSTはその名の通りサイズが0の型で，例えば()がそれに相当します．
これはもともと例えばSetを実現するためにSet<Key> = Map<Key, ()>として，Mapの実装を利用しつつ無駄な領域が割り当てられないようにするといった機能のために用意されたもののようです．
ZSTを利用する場合，最初のC言語の例と同じような構造は以下のようにして定義できます．
#[derive(Debug)] #[repr(C)] struct X { len: usize, val: [u8; 0], }
ここではvalがZSTになります．valのサイズは0なので，std::mem::size_of::<X>()は実質的にstd::mem::size_of::usize()と同じ値を返します．
以下のようにしてこのstructを利用することができます．
#![feature(allocator_api)] use std::heap::{Alloc, Heap, Layout}; unsafe fn alloc(len: usize) -> *mut u8 { let layout = Layout::from_size_align(len, std::mem::align_of::<usize>()).unwrap(); Heap.alloc(layout.clone()).unwrap() as *mut u8 } unsafe fn free(p: *mut u8, len: usize) { let layout = Layout::from_size_align(len, std::mem::align_of::<usize>()).unwrap(); Heap.dealloc(p, layout); } fn zst() { unsafe { // メモリの確保 let value_len = 3; let header_len = std::mem::size_of::<X>(); let total_len = header_len + value_len; let p = alloc(total_len); // 確保したバッファ先頭をstruct Xにキャスト let header: &mut X = std::mem::transmute(p); header.len = value_len; // valにアクセスするためのスライスの作成 let val: &mut [u8] = std::slice::from_raw_parts_mut(p.offset(header_len as isize), header.len); val[0] = 1; val[1] = 2; val[2] = 3; // get_unchecked_mutを利用したアクセス *header.val.get_unchecked_mut(0) = 100; // これは index out of bounds error //header.val[0] = 100; println!("header_len = {}", header_len); println!("value_len = {}", value_len); println!("header = {:?}", header); println!("val = {:?}", val); println!( "p = {:?}", std::slice::from_raw_parts(p, total_len) ); free(p, total_len); } }
実行結果は以下のようになります．
header_len: 8 value_len: 3 header: X { len: 3, val: [] } val: [100, 2, 3] p: [3, 0, 0, 0, 0, 0, 0, 0, 100, 2, 3]
やっていることはC言語の場合とほぼ同じで，まず適当な方法（ここではstd::heap::Alloc）でヘッダ（元々のstructの大きさ)+可変長サイズのデータの長さ分のメモリを確保します．メモリ確保方法の詳細は前回のエントリを参照して下さい．
let value_len = 3; let header_len = std::mem::size_of::<X>(); let total_len = header_len + value_len; let p = alloc(total_len);
その後確保したメモリをtransmuteでXへのreferenceにしてヘッダにアクセスします．
let header: &mut X = std::mem::transmute(p); header.len = value_len;
valに関してはfrom_raw_parts_mutでsliceを作成してアクセスします．
let val: &mut [u8] = std::slice::from_raw_parts_mut(p.offset(header_len as isize), header.len); val[0] = 1; val[1] = 2; val[2] = 3;
valはget_unchecked_mutを使えばヘッダからのアクセスも一応可能です．普通にアクセスしようとした場合は境界値エラーになります．
// get_unchecked_mutを利用したアクセス *header.val.get_unchecked_mut(0) = 100; // これは index out of bounds error //header.val[0] = 100;
実のところこの方法は（valへのアクセスに基本的にはスライスを作ることになるので）flexible array memberと呼べるのか微妙なものですが，使うのは楽だと思います．
ちなみに，この方法ではスタック上に変数を確保することはできません．というか，
let x = X{len : 10, val:[]};
とやれば確保できますが，valは必ずemptyでなければならないので実質的に使えません．
DSTを使う方法
DSTを使うことで，本来のflexible array memberに近いものが実現できます． ここでの方法はHacker Newsのコメントから知りました．
DSTはコンパイル時にはサイズが定まらず，実行時にサイズが求まる型のことで，代表的なDSTの一つはスライス[T]です．structは一番最後の要素にDSTを持つことができます．この場合，そのstruct自体がDSTになります．
例えば，以下のようにしてDSTなstructを定義できます．
#[repr(C)] struct Y{ len: usize, value: [u8], }
で，このようなstructが定義できるのは良いですが，実のところをこれを直接構成する方法はないです．
これは扱いにくいので，代わりに以下のような?Sizedなgeneric data typeを利用します．
#[repr(C)] struct Y<T: ?Sized> { len: usize, val: T, }
コンパイル時に大きさが分かっている場合
そもそもflexible array memberを使いたい目的が動的にデータを割り当てたいという目的からなので，コンパイル時に大きさが分かっている状況というのは本末転倒な状況ですが，この場合は以下のようにして上記のstructをスタック上に構成することができます．
fn as_raw_bytes<T: ?Sized>(x: &T) -> &[u8] { unsafe { std::slice::from_raw_parts(x as *const T as *const u8, std::mem::size_of_val(x)) } } fn dst1() { let len = 10; let val: [u8; 10] = [1; 10]; let y = Y { len, val }; println!("y = {:?}", y); println!("y = {:?}", as_raw_bytes(&y)); println!("&y = {:p}", &y); println!("&y.len = {:p}", &y.len); println!("&y.val = {:p}", &y.val); println!("size_of_val(&y) = {}", std::mem::size_of_val(&y)); println!("size_of_val(&y.len) = {}", std::mem::size_of_val(&y.len)); println!("size_of_val(&y.val) = {}", std::mem::size_of_val(&y.val)); println!( "size_of(Y<[u8;10]>) = {}", std::mem::size_of::<Y<[u8; 10]>>() ); // NG //println!("size_of(y) = {}", std::mem::size_of::<Y>()); //println!("size_of(y) = {}", std::mem::size_of::<Y<[u8]>>()); }
実行結果
y = Y { len: 10, val: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] } y = [10, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 134, 2, 1, 0, 0, 0] &y = 0x7fff5d398b68 &y.len = 0x7fff5d398b68 &y.val = 0x7fff5d398b70 size_of_val(&y) = 24 size_of_val(&y.len) = 8 size_of_val(&y.val) = 10 size_of(Y<[u8;10]>) = 24
ここで，y.lenのサイズは8, y.valはサイズは10ですが，メモリは8バイト単位で確保されるようでy自体のサイズは24になっています．
この場合，DST coercionsを利用して，以下のような関数を呼び出すことが可能になります．
fn f<T: std::fmt::Debug>(y: &Y<[T]>) { println!("f: y = {:?}", y); // f: y = Y { len: 10, val: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] } } fn dst1(){ let len = 10; let val: [u8; 10] = [1; 10]; let y = Y { len, val }; f(&y); }
ちなみに，このコード例において，最初のDSTな構造体
#[repr(C)] struct Y{ len: usize, value: [u8], }
を使った場合，以下のようなエラーが発生します．
error[E0308]: mismatched types --> src/main.rs:149:22 | 149 | let y = Y { len, val }; | ^^^ expected slice, found array of 10 elements | = note: expected type `[u8]` found type `[u8; 10]`
ヒープに割り当てたい場合は，例えば以下のようにVecが利用できます．
let len = 10; let mut vec = Vec::<Y<[u8; 10]>>::with_capacity(1); unsafe { vec.set_len(1); } let y = &mut vec[0]; y.len = len; for i in 0..len { y.val[i] = i as u8; }
動的にサイズを割り当てる
さて，それではようやく本題で，実行時にDSTなstructを構成する方法について説明します．
以下で説明する方法は，servoの一部のコードを参考にその処理を簡略化したものです．元のコードに丁寧にコメントが書いてあるので，興味のある方は一読を勧めます．
fn dst2() { let len = 10; // サイズの計算 let fake_slice_ptr: *const u8 = std::mem::align_of::<Y<[u8; 1]>>() as *const u8; let fake_slice: &[u8] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) }; let fake_ptr: *const Y<[u8]> = fake_slice as *const [u8] as *const Y<[u8]>; let fake_ref: &Y<[u8]> = unsafe { &*fake_ptr }; let size = std::mem::size_of_val(fake_ref); println!("size_of(fake_ref) = {}", size); println!( "size_of(fake_slice) = {}", std::mem::size_of_val(fake_slice) ); println!("fake_slice.len = {}", fake_slice.len()); println!("fake_ref.val.len = {}", fake_ref.val.len()); unsafe { let p = alloc(size); let fake_slice: &mut [u8] = std::slice::from_raw_parts_mut(p as *mut u8, len); let ptr = fake_slice as *mut [u8] as *mut Y<[u8]>; let y: &mut Y<[u8]> = &mut *ptr; y.len = len; for i in 0..len { y.val[i] = i as u8; } println!("y.len = {}", y.len); println!("y.val.len = {}", y.val.len()); println!("size_of_val(y) = {}", std::mem::size_of_val(y)); println!("size_of_val(&ptr) = {}", std::mem::size_of_val(&ptr)); println!("ptr = {:?}", as_raw_bytes(&ptr)); free(p, size); } }
実行結果
size_of(fake_ref) = 24 size_of(fake_slice) = 10 fake_slice.len = 10 fake_ref.val.len = 10 y.len = 10 y.val.len = 10 size_of_val(y) = 24 size_of_val(&ptr) = 16 ptr = [32, 0, 66, 15, 1, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0]
まず，このコードの前半部分では確保するメモリの大きさを計算します．
len = 10; let fake_slice_ptr: *const u8 = std::mem::align_of::<Y<[u8; 1]>>() as *const u8; let fake_slice: &[u8] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) }; let fake_ptr: *const Y<[u8]> = fake_slice as *const [u8] as *const Y<[u8]>; let fake_ref: &Y<[u8]> = unsafe { &*fake_ptr }; let size = std::mem::size_of_val(fake_ref);
ここで何をやっているかというと，
- 長さが
lenの[u8]のfat pinterを作成 - それを長さが
lenのY<u8>のポインタにし，さらにそれをreferenceにする size_of_valを使ってサイズを求める．
どうしてこれでサイズが求まるのかというと，DSTな要素は必ずfat pointer経由でアクセスしますが，このときfat pinterは(アドレス，長さ)を持ちます．このとき，この長さというのはDSTなstructの場合は，structの末尾の要素の長さを意味することになります．上のコードはまず最初にfrom_raw_part()を使って長さがlenの[u8]のfat pointerを作成した後，それを*const Y<[u8]>のfat pointerにキャストし，そしてさらにそれをreferenceに変換してサイズを計算している訳です．
上の実行結果のptrを見ると，後半8byteで長さ(10)を保持していることが分かります．
unsafe { let p = alloc(size); let fake_slice: &mut [u8] = std::slice::from_raw_parts_mut(p as *mut u8, len); let ptr = fake_slice as *mut [u8] as *mut Y<[u8]>; let y: &mut Y<[u8]> = &mut *ptr; y.len = len; for i in 0..len { y.val[i] = i as u8; } }
確保すべきメモリサイズが分かったら，メモリを確保して，サイズ計算時と同様にキャストしてY<[u8]>のreferenceを取得し，それを利用してデータ構造を操作します．
確保すべきサイズ計算のところは
let len = 10; let size = std::mem::size_of::<Y<()>>() + len;
でもいいんじゃないかと思いましたが，この場合はsizeは18になります．前述の通りrustはメモリを（この環境では）8byte単位で確保しているようで，今回の場合はsize_of_val()で得られる値と齟齬が生じることになります．といっても確保したメモリ外にはアクセスしないので大丈夫じゃないかなと思いますが..
実際に利用する場合には，以下のようにしてgeneric data typeを利用すると汎用性が上がります．
fn dst3<T>(len: usize) -> (*mut Y<[T]>, usize) { let fake_slice_ptr: *const T = std::mem::align_of::<Y<[T; 1]>>() as *const T; let fake_slice: &[T] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) }; let fake_ptr: *const Y<[T]> = fake_slice as *const [T] as *const Y<[T]>; let fake_ref: &Y<[T]> = unsafe { &*fake_ptr }; let size = std::mem::size_of_val(fake_ref); unsafe { let p = alloc(size); let fake_slice: &mut [T] = std::slice::from_raw_parts_mut(p as *mut T, len); let ptr = fake_slice as *mut [T] as *mut Y<[T]>; (ptr, size) } } fn f<T: std::fmt::Debug>(y: &Y<[T]>) { println!("f: y = {:?}", y); } fn main(){ let len = 10; let (ptr, size) = dst3::<u8>(len); unsafe { let y: &mut Y<[u8]> = &mut *ptr; y.len = len; for i in 0..len { y.val[i] = i as u8; } f(&y); // f: y = Y { len: 10, val: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] } free(ptr as *mut u8, size); } }
未初期化領域への代入の注意点
ここまで例ではprimitive typeしか扱ってないので未初期化の領域にそのまま代入していますが，Drop型を実装している型の場合はservoの例のようにstd::ptr::writeを使って書き込まないと未初期化のデータに対してDropが実行されてしまいます．詳細はnomiconに書いてあります．
まとめ
Cにおけるflexible array memberをrustで実現するための方法として，ZSTとDSTを利用する方法について書きました．実のところ両方ともあまりunsafeなコード量は変わらず，本来のflexible array memberに相当するのはDSTを使う方法ですが，状況によってはZSTの方が使いやすいかなと思いました．
rustで動的にバッファを確保する方法
Boxを使うVecを使うstd::heap::Allocを使う- placement-in を使う
mallocを使う
1. Boxを使う
rustで動的にメモリを確保する方法といってまず思いつくのはBoxを使う方法だと思います．例えば，以下のようにすれば長さ1000のu8のバッファを確保できます．
let buffer : Box<[u8]> = Box::new([0;1000]);
ただし，この方法は以下のような特徴があります．
- 確保した領域は必ず初期化する必要がある．
- 一旦スタック上にデータを確保したあとに，ヒープにそのデータをコピーする
1.に関しては，これは変数は初期化しないと利用できないというrustの原則に則ったものですが，場合によってはこの初期化コストが大きい場合があります．また，2. の方が問題で，あまりにも大きい領域を確保しようとするとスタックオーバフローが発生する可能性があります．コピー分のオーバヘッドも生じます．
2. Vecを使う
Vecを使う場合はVec::new()で可変長配列を作成した後Vec::pushでデータを追加していくのが最も基本的な方法ですが，当然効率はあまり良くありません．
Vec::with_capacityを使うと，指定したサイズ分だけのメモリ領域を確保してくれます．さらに，Vec::set_lenを使うことで，初期化をスキップして確保した領域にアクセスすることができます．ただし，set_lenはunsafeです．
unsafe{ let len = 1000; let mut vec = Vec::<u8>::with_capacity(len); vec.set_len(len); }
また，確保した要素にアクセスする際rustはデフォルトで境界のチェックをしますが，
そのオーバヘッドを減らしたい場合はget_uncheckedあるいはget_unchecked_mutが使えます((get_uncheckedやget_uchecked_mutはsliceの関数で，boxやvecからderef coercionを通じて呼び出せます))．
ffiで利用するなどでraw pointerが欲しい場合は以下のような手法が使えます．
unsafe fn alloc(len: usize) -> *mut u8 { let mut vec = Vec::<u8>::with_capacity(len); vec.set_len(len); Box::into_raw(vec.into_boxed_slice()) as *mut u8 } unsafe fn free(raw: *mut u8, len : usize) { let s = std::slice::from_raw_parts_mut(raw, len); let _ = Box::from_raw(s); }
Vec::with_capacityで指定した長さ分の領域を確保したあと，それをvec::into_boxed_sliceでBoxに変換し，さらにそれをBox::into_rawすることで実際のポインタを得ます．
確保した領域を解放する場合はポインタを再びslice::from_raw_parts_mutでスライスに直し，それをさらにBox::from_rawでBoxに直してBoxのDropが呼ばれるようにします．
上記のコードはservoの一部のコードを参考にしたものです． 実際のservoのコードではアラインメントをワード境界に揃えるため，以下のようなことをしています （簡単化のため実際のコードとちょっと異なります．ここでは実際に確保したバイト数も戻り値として返しています）．
unsafe fn alloc_buffer(len : usize) -> (*mut u8, usize){ let word_size = std::mem::size_of::<usize>(); let num = (len + word_size-1) / word_size; let mut vec = Vec::<usize>::with_capacity(num); vec.set_len(num); (Box::into_raw(vec.into_boxed_slice()) as *mut u8, num*word_size) }
3. std::heap::Allocを使う
rustのメモリアロケータはAllocator traitを実装することになっており，またstd::heap::Heapでデフォルトのアロケータにアクセスできます．コードはliballocにあります．
これを利用すると，以下のようにメモリを確保することができます．
#![feature(allocator_api)] use std::heap::{Alloc, Heap, Layout}; // 第一引数: サイズ, 第二引数: アラインメントサイズ let layout = Layout::from_size_align(10, std::mem::align_of::<u32>()).unwrap(); unsafe { let p = Heap.alloc(layout.clone()).unwrap() as *mut u8; // ... Heap.dealloc(p, layout); }
この関数を利用すれば，アラインメントも指定可能です．raw pionterが欲しい場合，この手法が一番良さそうに見えますが，残念ながらこの機能はunstableなため，nightlyな環境でしかまだ使えません．また，今後インタフェースが変わる可能性も十分あると思います．（詳細: https://github.com/rust-lang/rust/issues/32838）
4. placement-in を使う
こちらも現時点ではunstableな機能ですが，確保したメモリ上に直接データを配置するplacement-in構文があります（詳細: https://github.com/rust-lang/rust/issues/27779）． これを利用すると，boxでも大きなメモリ領域を確保することが可能です．
#![feature(placement_in_syntax, box_heap)] // OK let x: Box<[u8]> = std::boxed::HEAP <- [0;10000000]; // これは自分の環境ではoverflow // let b: Box<[u8]> = Box::new([0; 10000000]);
5. mallocを使う
場合によってはlibc crateを使ってmalloc & freeを直接呼んでしまうのも手かもしれません．こちらも当然unsafeです．
// https://github.com/rust-lang/libc unsafe { let p : *mut c_void = libc::malloc(10); // ... libc::free(p) }
rustをnostdで使う
nostdとは
rustは他の多くの言語と同様，標準ライブラリ(std)が同包されており，通常はそれを使ってプログラミングをおこないます．しかしながら，stdの多くの機能はOSの機能を利用しているため，OSそのものを開発したいとか，あるいはOSが存在しない環境でプログラミングをしたい場合などではstdは利用できません．
stdを利用しない場合は明示的にその旨を宣言する必要がり，そのために利用するのが#![no_std] attributeです．
nostdの概要は(昔の)bookのno stdlibの章に書いてあります． なお，nostdに関わることはunstableな機能が多いので，ここに書いてあることが今後変更される可能性は十分あります
core library
stdが使えなくなるとかなりの機能が制限されてしまいますが，rustはcoreと呼ばれるrust onlyで書かれたライブラリを提供しており，nostd環境でもcoreを利用することができます*1．ただし，core libraryを使用するにあったって，最低限以下の関数は自前で定義する必要があります．
memcpy,memcmp,memsetpanic_fmteh_personality
memcpy, memcmp, memset
これらの関数はrlibc crateにrustでの実装があるので，必要ならばそれを利用できます．
panic_fmt, eh_personality
プログラムがパニックしたとき等に利用される関数です．とりあえず，何もしないなら
#![feature(lang_items)] #[lang = "eh_personality"] extern fn eh_personality() {} #[lang = "panic_fmt"] extern fn panic_fmt() -> ! { loop {} }
みたいな関数を作ればokです．
coreとstdの関係
coreのドキュメントを見ていると，stdで提供されている機能のサブセットが提供されていることに気づくと思います．それもそのはずで，これはstdの中でcoreのライブラリがreexportされているからです．coreのドキュメントを見ているとよくstdの方を参照せよと書いてあるのはこういう理由からです． stdはOSがある用，coreはベアメタル用のライブラリですが，stdでもcoreの機能は使いたいのでこうしてるようです．
target
#![no_std]を指定すればnostdなプログラムが開発できるかというと，実際にはそう単純ではありません．多くの場合，プログラムをビルドするためのtargetを正しく設定する必要があります．
rustはさまざまなプラットフォームでの動作を保証しており，それを設定するのがtarget*2です．rustがサポートしているターゲットは ructc --print target-list としてみるか，あるいは https://forge.rust-lang.org/platform-support.html から確認できます．ターゲット名は基本的に{arch}-{vendor}-{sys}[-{abi}]の形をしていて，例えばx86_64-unknown-linux-gnuやx86_64-apple-darwinのようなターゲットがデフォルトで存在します．
各targetごとに，struct Target及びstruct TargetOptionsで指定されるtargetごとの設定を記述します．
rustがデフォルトでサポートしているtargetの設定はsrc/librustc_back/target/の中に書いてあります．例えば，linuxの場合はx86_64_unknown_linux_gnu.rsです．
このtargetはjsonで記述できるようになっており，例えば以下のように記述します．
{ "llvm-target": "x86_64-unknown-none", "data-layout": "e-m:e-i64:64-f80:128-n8:16:32:64-S128", "linker-flavor": "gcc", "target-endian": "little", "target-pointer-width": "64", "arch": "x86_64", "os": "none", "disable-redzone": true, "features": "-mmx,-sse,+soft-float", }
ベースはx86_64_unknown_linux_gnuですが，ここではosが存在しないので"none"を指定し，その他redzoneやmmx, sseを禁止しています．またfloatのsoftwareサポートを有効にしています．なお，data layoutはLLVMのものです．
こうして作成したtargetのjsonファイルは，例えばx86_64_xxx.jsonという名前で保存したならビルドする際に（Cargo.tomlと同じディレクトリに置いて） cargo build --target=x86_64_xxxのようにすることで指定できます．
sysrootとxargo
さて，targetを無事に指定すればあとはokかというと，残念ながらそうではありません．rustでは実際にプログラムをコンパイルする際に，sysrootと呼ばれるパスからライブラリを検索します．デフォルトのsysrootはrustc --print sysrootで確認できます．このsysrootにcoreのライブラリなどが置かれています．cargo build --target=x86_64_xxx のように指定した場合は x86_64_xxx用のsysrootを探す訳ですが，x86_64_xxxは自分で用意したターゲットなので，sysrootも自分で用意する必要があります．つまり，自分でそのtarget用のcoreをビルドする必要がある訳です．
幸いなことに，自分で用意したtarget用に自動でsysrootを用意してくれる，xargoと呼ばれるプログラムが存在します．cargo install xargoとすればインストールできます．xargoはcargoのラッパーになっており， xargo build --target=x86_64_xxx としたときにtarget x86_64_xxxのsysrootがなければまずそれ用にcoreなどをビルドし，その後プログラムのビルドをおこないます．nostd環境でプログラムを作る際は普通xargoを使うことになると思います．
nostdで使えるcrate
crates.ioのカテゴリ検索で，no-stdを検索すると，stdを利用していないcrateを見つけることができます．といってもCargo.tomlの中でcategoryをちゃんと設定しているcrateがどれだけあるのか分かりませんが..
