読者です 読者をやめる 読者になる 読者になる

Linuxシステムプログラミング8章

memo zatsu linux

Linuxシステムプログラミングの8章メモリ管理の雑なメモ。 下に行くほど雑になってそう。この本。

Linuxシステムプログラミング

Linuxシステムプログラミング

プロセスアドレス空間

  • 物理メモリを仮想化しているため、プロセスは物理メモリを参照するのではない。
  • カーネルがプロセスそれぞれに仮想アドレス空間を与える
  • 仮想アドレス空間は0から始まるリニアアドレス

ページとページイン/アウト

  • 仮想アドレス空間はページで構成される
  • サイズはマシンによる 32だと4KB、64ビットマシンだと8KB
  • ページには有効と無効という概念がある
    • 有効なページは実際に対応する物理メモリ、またはディスク上のファイルがが存在する
    • 無向なページはアクセスするとセグフォになる
  • プログラムが物理メモリに存在せず二次記憶装置に存在するページにアクセスしようとすると、ページフォルトMMUが発生させる
    • カーネルページフォルトに対応し、二次記憶装置から物理メモリにページインする
    • 物理メモリ上にあって、直近で最もアクセスされていないデータはページアウトされる

ページ共有とcopy-on-write

  • (異なるプロセスの)異なる仮想アドレスから物理メモリ内のデータを共有できる
    • 読み書き専用、読み取り専用どちらでも良い
  • 書き込む処理は二種類ある
    • 一つは単純に共有しているページにプロセスが書き込み変更された同じデータを参照
    • もう一つはMMUが書き込みを検知し例外をなげる、カーネルがその例外を検知して透過的にそのうろセス専用のページを新たに作り、そこに書き込むようにする(Copy on write)

メモリ領域

  • カーネルはページを複数のブロックに分けアクセスパーミッションなどの属性を管理している
    • このブロックをメモリ領域、セグメント、マッピングという
  • すべてのプロセスには決まったメモリ領域が存在する
    • テキストセグメント - プロセスの実行コード、文字列、定数、その他専用のデータを格納。読み取り専用、オブジェクトファイルにマッピングされる
    • スタック - 実行時に動的に拡張、縮小するデータ。ローカル変数や関数の戻り値などに使う
    • データセグメント(ヒープ領域) - プロセスの動的メモリを格納する。書き込み可能(malloc)
    • bss - 未初期化のグローバル変数を格納。

動的メモリ割り当て

  • 動的メモリは、コンパイル時ではなく実行時に割り当てるもの
    • 実行時になるまで、実際のサイズなどはわからない
  • cだとmalloc で動的メモリ割り当て出来る
    • 成功すると、割り当てたメモリ領域の先頭アドレスを返す

配列割当

  • 配列の割当にはcallocをつかう
    • mallocと違って0で初期化する

メモリ領域のサイズ変更

  • realloc でメモリ領域のサイズを変更できる

動的メモリの解放

  • 動的に割り当てたメモリは明示的に解放するまでプロセスアドレスの一部として存在し続ける
    • free を使う
    • 開放しないとメモリリークする
    • 解放後のメモリにアクセスしてはいけない(ダングリングポインタ)

アラインメント

  • ハードウェアからみたメモリ領域とアドレスの関係
  • データサイズの定数倍のメモリアドレスへ配置された変数を自然なアライメントという
    • 32ビットの変数がメモリ上で4の倍数のアドレスに配置されているとき

アラインメントされたメモリの割当

  • コンパイラとCライブラリがよしなに解決してくれる
  • 32ビットシステムでは8バイト,64ビットだと16バイト境界にアライメントされる
  • posix_memalign を使用すると、任意の倍数でアライメントされたsizeバイトの動的メモリを割り当てられる

他のアライメント問題

  • 非標準の型
    • 構造体のアライメントはメンバの最大サイズに合わせる
      • 最大サイズを持つメンバが4バイト境界でアライメントされる32ビット整数なら、その構造体は4バイト以上のアライメント
    • パディング(padding)が必要。
      • char(1バイト)のあとにintのメンバ(4バイトでアライメントされる)がある場合、charの後ろに3倍とのパディングが必要
    • 共用体のアライメントはメンバの最大サイズに合わす
    • 配列アラインメントは要素に合わせる
  • ポインタ
    • 以下の例では、unsigned longは4 or 8バイト境界に割り当てられるのに、charはほぼ確実に1バイト
    • そこで c をロードするとアラインメント違反
    • 違反の結果はアーキテクチャ依存でクラッシュすることもある
char greeting[] = "Ahoy Matey";
char *c = greeting[1];
unsigned long badnews = *(unsigned long *) c;

データセグメントの管理(ヒープ領域)

  • でたーセグメントを直接操作する関数はあるが、malloc などが使いやすく機能も豊富であるためほぼ使われていない
  • brk はデータセグメントの末尾(break point)を渡された場所を変更する

無名メモリマッピング

  • 典型的な malloc はデータセグメントを2の累乗のサイズの領域が並んだ状態に分割し,要求されたサイズに最も近い領域を貸す
    • 直前の領域がフリーの場合はつなげて,一つの大きなフリー領域にする
    • 戦闘だった場合は領域を縮めてカーネルに返す
    • バディメモリ割り当てシステムという
  • 内部フラグメンテーション - 要求されたメモリより大きなメモリ領域を返す問題
  • 外部フラグメンテーション - サイズ分のメモリ領域があるにも関わらず,複数のメモリ領域に分断されている
  • 領域Bと領域Aが隣接しており,領域Aがbreakpointに隣接している場合,Bを開放してもAが終わらない限り開放されない

  • 巨大なメモリ割り当てをするとglibcはヒープを使用せす無名メモリマッピングをする

    • ファイルを使わない
    • 巨大で,0に初期化された領域を使用できる
    • 本来のヒープの外にあるのでフラグメンテーションが発生しない
    • メモリ領域はサイズ,アクセスパー密書の変更が可能
    • 短所
      • メモリのサイズがページングサイズの整数倍になる,要求サイズがページサイズより小さいと無駄な領域が発生する
      • カーネルからのヒープ割当に比べてオーバヘッドが大きい

無名メモリマッピングの作成

/dev/zero のマッピング

高度なメモリ割り当て

  • mallopt を使用してカーネルパラメータを変更できる。

メモリ割り当てのデバッグ

メモリ割り当て統計情報

  • mallinfo でメモリ割り当ての統計情報を得る

スタック上のメモリ割り当て

  • スタックはプログラムのオート変数(automatic variable)を格納する場所
  • allocaを使ってスタック上で動的にメモリ割り当てをする
    • メモリ領域はスタック上に取られる
    • つまり、alloca を実行した関数がリターンしたら解放/破棄される -> freeしなくていいのでコードが簡潔に
    • alloca を関数コールのパラメータ内で使用すると、関数パラメータの用のスタック領域にメモリを割り当ててしまうため使用を避ける

スタック上へ文字列をコピー

  • 文字列の一時的なコピー等に使える

メモリ割り当て方法の選択

  • malloc
    • 単純だが割り当てられたメモリがゼロクリアされていない
  • calloc
    • 配列の割当が容易でゼロクリアされてる、配列以外には使いづらい
  • realloc
    • メモリサイズを変更できる、ソレ以外使えない
  • brk and sbrk
  • 無名メモリマッピング
    • 共有可能、アクセスパーミッションもできる。サイズが大きいときにも使える。メモリが小さいと効率が落ちる
  • posix_memalign
    • 任意サイズの境界に従うメモリを割り当てる。移植性に難がある
  • memalign and valloc
    • unixシステムで使えるかも、posix標準ではない
  • alloca
    • 高速なメモリ割り当て、解放不要、サイズの大きな割当には不向き。
  • 可変サイズ配列
    • allocaとほぼ同じ、スコープを抜けたときに解放される。配列に限り有効

メモリ操作

バイト設定

  • memset(void *s,int c,size_t n) sのメモリ領域へcをnバイト分設定

バイト比較

  • memcmp(s1,s2,n) s1の先頭からnバイトs2と比較
    • 構造体は持つ内部にパディングを含むため正しく比較できない(パディングは不定値だから)

バイト移動

  • memmove(dst,src,n) srcの先頭nバイトをdstへこぴー
    • メモリ領域が重なっていない場合も正しく動く
    • もともと重ならないとわかっている場合にはmemcpyを使用する

バイト検索

  • memchrはメモリ領域内の指定されたバイトを検索する

メモリのロック

  • linuxカーネルは不要なページはスワップアウトして、必要に応じてスワップインするデマンドページングを使用している
    • この操作は透過的に行われるのでアプリケーションは気にしなくて良い
    • しかし意識したい場合もある
      • 決定論
        • 時間的な制約を持つアプリケーションではページフォルトしてディスクIOが発生して時間的制約を超過してしまう
      • セキュリティ
        • 機密情報がページアウトされてしまうと、暗号化されずディスクへ保存されてしまう
    • 当然全体のパフォーマンスが落ちる可能性があるので気をつける

アドレス空間の一部をロック

  • mlock(addr, len)でアドレスの範囲を指定して物理メモリ上にロックする

アドレス空間全体をロック

  • mlockallで(カレントプロセスの)メモリ全体を物理メモリ上にロックする

メモリのアンロック

  • munlock, munlockall

メモリの遅延割当

  • カーネルへメモリの追加を要求すると,カーネルは実際には物理メモリを割り当てずに成功を返す(commit)
  • 書き込んだ時点で初めて割り当てる(CoW)
    • 遅延できる
    • 実際に使用する分(割当要求分ではない)のみ物理メモリを使用する(ページ単位にする)
    • コミットしたメモリサイズをシステムの持っているメモリよりも大きくすることが出来る。(overcommit)

オーバコミットとOOM

  • 2GBのファイルのCoWをマッピングするのは2GBのメモリが必要
    • オーバコミットを使用すると、実際に書き込んだ部分だけで良い
  • 実装メモリサイズおよび、スワップ領域より大きなメモリ領域を要求したとき
    • カーネルは要求したしシステムコールに対して成功を返す
    • コミットしてるからどこからからメモリを取ってこないといけない
    • そこでkillするプロセスを見つけ出しOOM killerで殺す
  • OOM killer は sysctlパラメータの vm.overcommit_memoryに値を設定してOOMを逃れる
    • 0がデフォルトで、ヒューリスティックオーバーコミットする
    • 1はメモリを非常に多く使用するアプリだとこれがいいか
    • 2はオーバコミットを禁止する。

golang で Future を実現する

Go

ここで言う Future オブジェクトとは、clojureFuture を使用して作成できるオブジェクトのようなものことをいう(結果をキャッシュしてないとかはあるけど、その辺は割愛している)。 つまり、何か処理を受け取りその処理を別 thread で実行するオブジェクトのことで、それを golang で作る。

シンプルな Future

とにかくブロックせずに、後から値を取り出せるようなオブジェクトを作成する場合は以下のようにする。 ジェネリクスがないので int に対する Future を書いた。NewFuture の引数の f がブロックするような重い処理をする。 クロージャ f の戻り値を future (chan int) にいれて、Get() を使ってあとからその値を取っている。

type Future chan int

func (f *Future) Get() int {
    return <-*f
}

func NewFuture(f func() int) *Future {
    c := make(Future)
    go func() {
        c <- f()
    }()
    return &c
}

使い方は以下のようになる。

f := NewFuture(func() int {
    // a time-consuming code
    return 10
})

f.Get() // 10

Get()のブロックを回避

上の実装だと、Get() したタイミングで NewFuture に渡した処理が終わっていなかった場合そこでブロックしてしまう。 そこで、処理中 (pendding) か終了 (filfilled) かをブロックせずにわかるようなメソッドを持った Future オブジェクトは以下のようになる。

const (
    Pending   = iota
    Fulfilled = iota
)

type Future struct {
    State int
    ch    chan int
}

func (f *Future) Get() int {
    return <-f.ch
}

func NewFuture(fn func() int) *Future {
    f := Future{
        State: Pending,
        ch:    make(chan int),
    }

    go func() {
        ret := fn()
        f.State = Fulfilled
        f.ch <- ret
    }()

    return &f
}

State を使用すると渡され処理が完了しているかわかるので例えば、以下のように終了したか(fulfilled)かどうかによって処理を変えられる。

f := NewFuture(func() int {
    // a time-consuming code
    return 10
})

if f.State == Fulfilled {
    f.Get() // 10
} else {
    // something code

    f.Get() // 10
}

感想

以上のように golang を使うと Future はシンプルに書けるので、無理に Future ライブラリを使うのではなくてその都度かんたんなものを作れば良さそうな気がした。

Go版retriable作った

Go

Rubyretirable の Go版を書いた。

github.com

使い方

一番シンプルな使い方。引数として渡されたクロージャが成功するまでリトライし続ける。 リトライ回数のデフォルトは3で、リトライ間隔は randomized exponential backoff アルゴリズムを使っている。簡単に言うと、CSMA/CD みたいにコリジョン(失敗)すると次に実行するまでの時間が徐々に長くなっていくアルゴリズム(をちょっと変形させたやつで、元ネタはここらしい google-http-java-client )。

retriable.Retry(func() error {
    // your code
    return nil
})

リトライ回数を変更したい場合は Options を使う。 リトライ回数を5、最初のリトライ間隔を1秒に設定した例。

opt := retriable.Options{
  retries:  5,
  interval: 1 * time.Second,
}

retriable.RetryWithOptions(func() error {
  // your code
  return nil
}, opt)

処理全体にタイムアウトを設定することも出来る。 RetryWithOptionsに渡されたクロージャが5秒以上かかった場合にリトライするのをやめて、処理を返えす。

opt := retriable.Options{
    timeout: 5 * time.Second,
}

retriable.RetryWithOptions(func() error {
    // your code
    return nil
}, opt)

リトライ間隔がexponentialに増加するのではなく、一定にしたい場合はbackoffをConstantBackoffに変更する。

opt := retriable.Options{
    backoff: backoff.NewConstantBackOff(1 * time.Second),
}

retriable.RetryWithOptions(func() error {
    // your code
    return nil
}, opt)

まとめ

ご意見があればぜひ

Rust で LLVM やってみる

Rust LLVM

Rust と LLVM やってみたくなってやってる. llvm-sys という LLVM の Rust バインディングのライブラリを使って LLVM 動かしてみた話と自分用メモ.

きつねさんでもわかるLLVMを読んでからやるかと思ったが,5章以降はちょっと自分には合わなかったのでブログ探して、それをやりながら参照程度に狐さんを見るという作戦でいった.

環境設定

何とかして Rust を入れる. これを真似すればだいたい行ける.

気付いたらRustの環境構築がかなり楽になってた | κeenのHappy Hacκing Blog

後は LLVM を入れてpathを通す.

brew install llvm
export PATH="`brew --prefix llvm`/bin:$PATH"

やったこと

  • LLVM IR の雰囲気を知りたかったので幾つかサンプル書いてみた.

playground/rust/llvm-example at master · ganmacs/playground · GitHub

llvm*.rsは上の方に動かしたい擬似コードを書いてある. codegen*.rs は AST ができてる体でそれを LLVM IR に変換するコードをかいた.

  • Rust で作った言語(中途半端なlisp) のバックエンドを LLVMにしてみた.

ほとんど Rust かいた経験がないため,色々おかしいところがありそう. マクロかけるようにするかってところで気持ちが終わり,LLVMバックエンドにリプレイスとかやってる.

GitHub - ganmacs/rlisp

参考になったブログとコード

llvm の公式のサイト.実際 LLVM IR 書いてる(実際に書いてるのはRustのラッパーだけど)と使い方がわからず,ググると大抵これしかヒットしないので一生懸命これを読む.

Rust で llvm-sys.rs を使って 数字を出すところから phi 関数(というのがある) を使って if 式を作ることまでやってる.

Go 言語用のバインディングもあるようでそれを使って,加算するところまでやってる.序盤の説明が分かりやすかった.

LLVM の外観をつかむのには良かった. ただ,読み進めてるといきなり Pass の話をしだすので,LLVM IR について知りたい場合は序盤だけ読んで,後半は後で読むと良さそう.

LLVMチュートリアルを Rust でやってる. この作者が作った iron-llvm という llvm-sys.rs をラップしたライブラリを使って LLVM を触っているのでいきなりこれを見ること混乱するかもしれない. 最初はむしろ iron-llvm のコードを読んで llvm-sys.rs の使い方の雰囲気をつかむのが良い.

きつねさんでもわかる LLVM のサンプルコードのリポジトリ.割りと大きめのコードなので実際に真似しやすい. 構文の定義( https://github.com/Kmotiko/DummyCCompiler/blob/master/dummyC_ebnf.txt )を読めばどんな言語かわかるので本の方は読まなくてもだいたい分かると思う.

emacsでコード読んでるときに「現在いる行が含まれたプルリク」に飛びたいを見れるようにした

emacs

hisaichi5518.hatenablog.jp

これ見て hub browse -- commit/<commit-id> でcommitに飛べることを知ったので、それを使って emacsでコード読んでるときに「現在いる行が含まれたプルリク」に飛びたいを見れるようにした。 このスクリプトも元ブログと一緒でプルリクのページではなくコミットページを開くところで終わってますが。

(defun open-github-commit ()
  (interactive)
  (let* ((cmd1 "git blame -l -L %s,+1  %s | cut -d ' ' -f 1")
         (cmd2 "hub browse -- commit/%s")
         (zero "0000000000000000000000000000000000000000")
         (commit-id (shell-command-to-string (format cmd1 (line-number-at-pos) buffer-file-name))))
    (if (string= zero commit-id)
        (message "This line is not commited")
      (shell-command (format cmd2 commit-id)))))

(global-set-key (kbd "M-g o") 'open-github-commit)

さよならgheに対応してないelispGitHub - ganmacs/emacs-github-open: Open a commit url in github.com

Treasure Data インターンで最高の夏過ごしてきた #td_intern

intern

8月1日から9月30日の間,Treasure Data Summer Intern 2016に参加していました. 他のインターン生2人からの強烈なプレッシャー (強烈なプレッシャー1強烈なプレッシャー2)に負けたので僕もインターンブログを書きます.

tl;dr

すごいメンターの元 Fluentd の開発してると何故かめっちゃお金がもらえるインターンでとにかく最高

なにやってたの?

f:id:ganmacs:20161007102854p:plain キュートなロゴ

Fluentd というソフトウェアの v0.14 向けの機能を,メンターの @tagomoris さんの元,開発しました.具体的に行ったことは以下のようになります(スライドからそのまま持ってきただけですが).

  • 6 features
    • Counter API (Not merged yet)
    • Data compression in buffer plugins and forward plugins
    • New out_file plugin only for section
    • A CLI tool to read dumped event data
    • Log rotation
    • filter_with_time method in filter plugins
  • 2 enhancements
    • Optimizing multiple filter calls
    • Add event size to options in a forward protocol
  • Some small tasks

インターン期間は2ヶ月あったので,最初の1ヶ月は Fluentd の開発スタイルに慣れようということで小さめの機能(Counter API以外のタスク)をいくつかをやって,最後の1ヶ月で大きい機能(Counter API)を1つ をやりました.

一応雑に機能を紹介すると,

Counter API
マルチプロセスでfluentd動かしたとき,メトリクスとるのに使えるやつ

Data compression in buffer plugins and forward plugins
データを圧縮して操作できるようになり何かとリソースを節約できるやつ

New out_file plugin only for section
secondary セクションのみで使えるシンプルな out_file プラグイン

A CLI tool to read dumped event data
送信に失敗してダンプされた MessagePack形式のデータを読めるようなるやつ

Log rotation
Fluentd で log rotation できるようになるやつ

filter_with_time method in filter plugins
filter pluginで time をいじれるようにするやつ

Optimizing multiple filter calls
複数filter使用したときに高速化するやつ

Add event size to options in a forward protocol
eventのサイズつかって,内部の無駄な処理最適化するやつ

それぞれの説明を詳しく書いてもいいんですが長くなりすぎて誰も読まなくなると思うので,興味のある人は僕に会ったときにでも聞いてください(スライドを読んでもいいですが説明がアレ).

以下が最終発表スライドです.発表は英語でするはずだったんですが,僕のときだけUSの人たちがいなくて日本語で発表OKだったので,日本語が使えることに感謝しながら日本語で発表しました.

感想は?

まずは,Fluentd がいろいろ大変でした(語彙力).そもそも1回くらいしか Fluentd 使ったことなかったのでどうやって使われているか調べるところからはじまり,「あれ,これやばくない???」とか思いながらインターン初日を過ごしていました. @tagmorisさんのスライドにも書いてありますが,Rubyの黒魔術をふんだんに使って書かれていたので非常に読み応えがありました. コードを読む上で,Fluentd ソースコード完全解説 は参考になりました.結構古いので変わってしまったところもありますが,全体の流れを見るにはちょうどよかったです. キッっと睨んでるとわかってきたので大変なのは慣れることだなって感想になりました.

あとは,一番大きい機能の Counter API を merge まで持っていけなかったことが心残りです. 設計をしてレビューのフェーズで大量に時間を使ってしまったのがよくなかったなって感じです. 今の自分ができることと,できないことがはっきりしたのでそういう意味では良かったかなとおもっています.

前々から興味のあったミドルウェア開発を経験できたことは(しかもFluentdで,しかもTDで)とても幸運で,最高の経験だったと思っています. 開催されるかしらないですが,もし来年も開催されならとりあえず出してみると意外とインターン行けるかもしれないので,来年も学生の皆様はぜひ.

まとめ

特にまとめることもないですが,とても刺激的なインターンだったということが伝われば幸いです. 周りは全員超すごい人ばかりだったので,「(業務中自分の力の無さに)おちこんだりもしたけれど、私はげんきです。」という感じです. 社員のみなさん,同期の2人にはとてもお世話になりました.ありがとうございました.

付録1(愉快な仲間たち)

僕の他に2人,インターン同期がいました. 彼らが先に書いたブログがあって僕のより数倍いいのでそちらもぜひ.

@amay382 iPhone7とiOSのことをめちゃくちゃ煽る人(年下なのに優秀でつらい)

トレジャーデータでインターンしてた話 #td_intern - 水底

@takuti オタクかヤンキーかで言えばオタクの人(英語が引くほどうまい)

Treasure Dataインターンにみる機械学習のリアル #td_intern | takuti.me

2人とも機械学習(系?っていうの?あってる?)をやってたので,「インターンでは何やるの?」って聞いたんですけど,丁寧に教えてもらった割に何言ってるよくわからず「すごそう」くらいしか感想がなかったのできっとすごいんだろうなって思ってました.

付録2(食)

牡蠣が苦手だった僕も牡蠣が食べられるようになりました。

以下、 ログの重要性について真面目にディスカッションしていたときの図です!!!! f:id:ganmacs:20160930214523j:plain f:id:ganmacs:20160930194731j:plain f:id:ganmacs:20160930200710j:plain f:id:ganmacs:20160930214021j:plain

高速にメモをとるためのOrg Capture

emacs

Org Capture とはOrg-Modeのメモ取りツール(わかりやすく書いてある -> 色々 Org Capture する | Amrta )

以下のように書いておくと(キーバインドはなんだっていい)

(setq org-capture-templates
   '(("t" "Task" entry (file (expand-file-name (concat org-directory "/task.org")))
      "* TODO %?\n    %i\n   %a\n    %T")
     ("n" "note" entry (file (expand-file-name (concat org-directory "/notes.org")))
      "* %?\n   %a\n    %T")
     ("r" "reading" entry (file (expand-file-name (concat org-directory "/reading.org")))
      "* %?\n   %a\n    %T")))

(global-set-key (kbd "C-c C-q") 'org-capture)

C-c C-qと押した時に以下のようなバッファが現れどれかを選択するとメモが簡単に書ける

Select a capture template
=========================

[t]     Task
[n]     note
[r]     reading
-------------------------------------------------------------------------------
[C]     Customize org-capture-templates
[q]     Abort

ただ問題があって,たかがメモをとるためにC-c C-q nとおさないとメモを取れないのはだるすぎる(C-c C-qの部分は好きに設定できるが最小でも2回必要.しかも画面が勝手に開いて視点がコロコロ変わり本当にだるい) そこで以下のような関数を作った.これでC-M-=を一度押せばいきなりメモをかけるようになった. org-captureの第二引数を上記で記述したorg-capture-templatest(Task)かn(note)かr(reading)にすることで指定のテンプレートを使用できる.

(defun org/note-right-now (content)
  (interactive "sContent: ")
  (org-capture nil "n")
  (insert content)
  (org-capture-finalize))
(global-set-key (kbd "C-M-=") 'org/note-right-now)