pthreadの条件変数

今日は決算報告書を 作成して 顧問の税理士さんに作成してもらって確認したあと、銀行、役所、税務署を 徘徊して 廻って国税（法人税、復興特別法人税、消費税）と県税、市税を納付してきた。
今期は若干の設備投資が発生したため、利益は少なかった。　というより、前の期での設備更新を先延ばしにしたためその期は利益が出て、逆に今期に更新分が偏ってしまった。
設備投資は計画的に行わなければ資金の運用にも、生産性にも問題が生じてしまう。　しっかりやらないと。

夕方には帰社できたが取引先は休みに入っているので、自社のプロジェクトに時間を割くことにした。

softies projectとは別に、Unix上で動作する T-Kernelもどき（サブセット）を作ることにする。
T-Kernelを扱う業務では簡単なモックを作ってテストしているが、それとは別にシミュレータも作りたくなった。
既にシミュレータはあるはずなので新たに作るのは時間の無駄になるのだが、今回の目的はシミュレーションというよりも T-Kernelの仕様を理解することにある。

主成功シナリヲ

まず、1st iterationでは、下記の関数に対して主成功シナリヲ（最も基本的な使い方）だけを実装して単体テストしてみると、それなりにうまくいった。

tk_cre_mtx  tk_del_tsk  tk_ext_tsk  tk_ref_mtx tk_slp_tsk
tk_cre_tsk  tk_dly_tsk  tk_get_tid  tk_ref_tsk tk_sta_tsk
tk_del_mtx  tk_exd_tsk  tk_loc_mtx  tk_rel_wai tk_unl_mtx

taskは pthreadに、mutexは pthread_mutexに単純に対応させた。

代替シナリヲ

2st iterationでは、代替シナリヲ（主成功シナリヲではない別の使い方）を実装して単体テストしてみる。

tk_dly_tskを使用しているテストが通らなくなった。たとえば tk_dly_tsk(2000U)としてあるので 2秒経過後に抜けてきて欲しいのだが、10ミリ秒そこそこで抜けてきてしまう。
10ミリ秒というのは単体テストのフレームワークのオーバヘッドも含んでいるので、もう少し短い時間かも知れない。
いづれにしても期待する動作になってない。

tk_dly_tskの主成功シナリヲでは、引数で指定した時間を経過した後関数から復帰するだけだったので、単純な usleep(3C)で遅延を実装していた。

tk_dly_tskの代替シナリヲでは、他タスクから tk_rel_waiを呼ばれると、SUSPEND状態が解除されてエラーコード E_RLWAIを返さなければならない。
SUSPEND状態を抜けるには他にも tk_ter_tskもあるし、tk_slp_tskで SUSPENDして tk_wup_tskで解除というのもある。

このように待ち合わせと解除の方法が多岐にわたるため、何の要因により SUSPENDを解除しようとしているのかを記憶しなければならない。

usleepではシグナルを使うことにより中断させることはできるが、複数のタスクから条件変数の操作を安全に行うことはできない。
そこで、mutexおよび条件変数を使用することにした。

バグの原因

時間待ちを行うために pthread_cond_timedwait(3T)を使用したが、問題はそこにあった。

この関数は時間待ちをするものではなく、時刻を待つものである。
そしてその時刻とは 1970年 1月 1日 0時 0分 0秒 GMTを期限とする相対値である。 多くのマニュアルには、abstimeと書かれている。

これを見落として、2st iterationで最初に書いたコードでは単純に待ち時間を与えたものを引数に使ったものだから、2秒間待つつもりが、1970年 1月 1日 0時 0分 2秒 GMTまで待つことを指定したことになる。
1970年というのは読者の中にはまだ生まれてない方もいることだろう。そのくらい大昔である。
pthread_cont_timedwaitを呼び出しても僅かなオーバヘッドが生ずるだけで、ほとんど直ちに復帰してくるのである。

バグの影響

それでも組み込みの開発でありがちな、時計が設定されていない状態では偶然それっぽい時間になるかもしれなかった。
そんな出鱈目な状態でテストをパスさせてしまうと、市場で不具合になることだろう。
シミュレーションでよかった。

そうなると、過去に開発したものが怪しくなってきた。

幸い、請け負ったものの中には pthread_cond_timedwait(3T)を使ったものが無いことが確認できた。

softies projectでは、lwd_lang_Objectクラスの waitAsMillis関数で使っている。
しかし、ちゃんと現在時刻を取得し、待ち時間を加えて使っている。
エラー処理の違いのため、lwd_lang_Objectをそのまま使用することはできないが、参考にすべきだったかも知れない。

教訓

• ちゃんとマニュアル読め
• 正常に動くコードを参照しろ

参考文献

• ビル・ルイス＋ダニエル・バーグ著『Pスレッドプログラミング』岩本信一訳 プレンティスホール 1999年
• David R.Butenhof著『POSIXスレッドプログラミング』油井 尊訳 アジソン・ウェスレイ 1998年

mallocライブラリ その１ (alternative malloc library 1)

現代のプログラミングに於いてメモリの動的割り当ては欠かせない機能の一つである。
リソースは「要る物を」「要る時に」「要る分だけ」無駄なく割り当てることは重要だと考える。

近代的な言語にはガベージコレクタを標準で備えるようになっているが、言語 Cでのメモリ管理はプログラマに任せられている。
我々は動的メモリ管理のために mallocや free関数を使用するが、どうしても間違いが生じてしまう。

• 未割り当て領域へのアクセス
• 使用中の領域を解放／解放済み領域へのアクセス
• 二重解放
• 解放漏れ（メモリリーク）
• オーバラン／アンダーラン

softiesプロジェクトでは、これらの問題を検出するための LWD mallocライブラリを開発している。
この用途には valgrindというメモリの監視以外にも使える使いやすいツールが既にあるが、Solarisには非対応で、動作も若干鈍調である。
我々はより軽量で Solarisでも使用できることを目標に置いている。

使用法

このライブラリはメモリを大量に消費する。
そのため、専ら小規模な単体テストに使用されることを想定している。

静的ライブラリ libmalloc.aをテスト対象のプログラムにリンクして使用する。
（都合が悪ければライブラリ名称は任意に変更して良い）

libmalloc.aがホームディレクトリの下のlibにあり、Test.cからデバッグ版の Testをビルドする例を以下に示す。

 $ cc -g -o Test -L ~/lib -lmalloc Test.c

Makefileを使用する場合には、下記の定義を含めればよい。

CFLAGS = -g
LFLAGS = -L ~/lib
LDLIBS = -lmalloc

正常な使用例

まず、メモリを割り当て、それを解放した場合の例を見てみよう。

#include <malloc.h>
#include <stdio.h>

int main() {
 char* bytes1 = (char*)malloc(5);
 char* bytes2 = (char*)malloc(8);
 free(bytes1);
 free(bytes2);
 return 0;
}

このプログラムは 5バイトと 8バイトの領域を割り当て、その両方を解放する Test1.cである。

$ ./Test1
HEAP REPORT
  SUMMARY
   total allocated: 13(bytes)  2
   memory leak: 0(bytes)  0

SUMMARYには、total allocatedに 2回の割り当てで合計 13バイト割り当て、memory leakに解放漏れが無いことが示されている。
(bytes)の後ろの値は領域の数を表している。

メモリリークの検出例

つぎは、メモリの解放を忘れた場合の例である。

#include <malloc.h>
#include <stdio.h>

int main() {
 char* bytes1 = (char*)malloc(5);
 char* bytes2 = (char*)malloc(8);
 free(bytes2);
 return 0;
}

先ほどと同じ 5バイトと 8バイトの割り当てを行った後、8バイトの方のみ解放する。

$ ./Test2
HEAP REPORT
  SUMMARY
   total allocated: 13(bytes)  2
   memory leak: 5(bytes)  1

  DETAIL OF MEMORY LEAK
 no.     memory size(byte) created by
   1 0xfae00000          5

SUMMARYには、total allocatedに 2回の割り当てで合計 13バイト割り当て、memory leakに そのうちの 1回分の 5バイトが解放漏れを起こしたことが示されている。
さらに DETAIL OF MEMORY LEAKでは、5バイトの解放漏れ領域のアドレスが 0xfea0000であることを示している。

解放漏れが複数ある場合には、その数分だけ 1行ずつ表示される。

created byの欄が空欄なのは許して欲しい。
libdwarfを使用して割り当てたコードのソースファイルとその行番号を表示するためのものだが、現在機能しない。

未割り当て領域へのアクセス検出例

メモリを割り当てていない領域にアクセスする例を示す。

#include <malloc.h>
#include <stdio.h>

int main() {
 char* bytes = (char*)malloc(5);
 char* p = bytes - 1;
 char c = *p;
 free(bytes);
 return 0;
}

このプログラムは 5バイトの領域を割り当てるが、それよりも前のアドレスから読み出しを行おうとする。

$ ./Test3
not allocated memory access at 0xfadfffff from (0xfeee01bf)

HEAP REPORT
  SUMMARY
   total allocated: 5(bytes)  1
   memory leak: 5(bytes)  1

  DETAIL OF MEMORY LEAK
 no.     memory size(byte) created by
   1 0xfae00000          5
Abort (core dumped)

HEAPレポートよりも前にエラーメッセージとアクセスしたアドレス、およびそのとき実行していたコード付近のアドレスが表示される。

最後は Abortして終了する。コアダンプするかどうかは環境設定による。

この例では、割り当てた 5バイトよりも 1バイト小さいアドレスにアクセスしていてアンダーランが検出できたかのように見えるが、そうではない。
直前に別の用途のために割り当てた領域があれば、エラーは検出できない。

注：コアダンプする設定の場合、ダンプに時間が掛かる分 Abortが表示されてシェルに復帰するまで時間を要する。

二重解放の検出例

既に解放済みの領域をもう一度解放しようとしたらどうなるか。

#include <malloc.h>
#include <stdio.h>

int main() {
 char* bytes = (char*)malloc(5);
 free(bytes);
 free(bytes);
 return 0;
}

このプログラムでは、5バイトの領域を割り当てたあと、2回つづけて解放を行おうとする。

$ ./Test4
bad memory release.(already released.)

HEAP REPORT
  SUMMARY
   total allocated: 5(bytes)  1
   memory leak: 0(bytes)  0
Abort (core dumped)

HEAP REPORTよりも前にエラーメッセージが表示され、Abortする。

制約

下記のような制約がある。

• 現バージョンでは、アンダーラン、オーバランの検出はできない。
• MMUのメモリ保護機構を必要とする。
• メモリ割り当て回数の上限は 256 * 1024回。（変更可）
• ヒープのサイズは 64MB。（変更可）
• 同じヒープサイズでも通常より早くメモリが枯渇する。
• main関数が呼ばれる以前に別スレッドが起動された場合、動作は保証されない。

ライセンス (license)

このライブラリは MITライセンスで公開されている。

GPLとのマルチライセンスが計画されていたが、手続きの都合により保留され、とりあえず MITライセンス単独でのリリースとなった。

ダウンロード (download)(下载)

ライブラリのソースは下記からダウンロードできる。

lwd_malloc_1.0.tgz

Solarisと Linux用の静的ライブラリ（いづれも Intel 32bit版）も含まれている。

bash-completion

softies projectの開発環境は Solarisと Ubuntuを使用しているが、先日、Ubuntuを 10.04→ 12.04に変えたところ、何やらいろいろと拙いことが発生し始めた。

makeが通らない

ちょっとした実験をする Main.cというソースがあったとしよう。たとえば次のようなもの。

#include 

int main() {
 printf("Hello, world.\n");
 return 0;
}

これだけなら、わざわざ makefile（や build.xml, pom.xml)を作らなくとも、

$ make Main
cc     Main.c   -o Main

の様にビルドが通る。これはデフォルトで定義されているサフィックスルールだけで何とかなる場合だからだ。

しかし、Ubuntu 12.04にしたところ、

$ make Main
make: *** ターゲット 'Main' を make するルールがありません．　中止．

と表示されてしまう。

makeコマンドで補完ができない

まだ可笑しい所がある。
シェルでmake Mのあと、Tabキーを押しても補完されない。
make Main.cが出ることを期待していたのだが。
使っているシェルが悪いのかと psしてみたが、bashである。
試しに echoとか、lsとか、catとかのあとに Mに続けて Tabキーを押すとちゃんと補完される。
Tabキーの接触不良でもないようだ。
また誰か余計な機能を発明したようだ。

理由は bash-completion

ネットで調べてみると出てきたのは bash-completionという機能。
makeや gitなど、使用するコマンドによって補完の推測方法を変えているようだ。
makeでは、makefileのターゲットを調べ、あるものしか入力できない。
makefile無しの場合のターゲットの推測までは頭が回ってないようだ。
中途半端なヤツ。
bas-completionが有効になってるかどうかは、次のように complete -pを実行して completeルールがゾロゾロと出てくるかどうかで確かめることができる。

$ complete -p
 :
 :
complete -F _route route
complete -o default -o dirnames -F _mount mount
complete -F _badblocks badblocks
complete -F _filedir_xspec lyx
complete -F _filedir_xspec rgvim
complete -F _filedir_xspec timidity
complete -F _filedir_xspec dvitype
complete -F _filedir_xspec dviselect
complete -F _filedir_xspec xdvi
complete -o default -F _longopt uniq
complete -F _root_command sudo
complete -F _command tsocks
complete -a unalias

bash-completionを無効にする

この機能を無効にするには、

sudo apt-get remove bash-completion

とやってアンインストールすれば良いのだが、それだと他のユーザまで影響してしまうので、つぎのようにしてローカルにアンインストールすれば良い。

$ complete -r

アンインストールがうまく行っていれば、

$ complete -p

でなにも出てこない。

bash-completionを無効にすると、makefileにないターゲットや makefile自体が無い状態での補完ができるようになる。

なお、makeでは無効にしたいが、gitでは有効にしておきたいということもできるようだ。

先輩、暮らす図って何ですか？

入れ子関数 その２ (nested function 2)

前回の入れ子関数 その１では、１つのスコープで同一名称の関数を定義してもエラーにはならないが使えないことが確認されたが、入れ子関数に関してはローカル変数にアクセスできるという便利な機能についても触れておきたい。

ローカル変数へのアクセス

次のプログラムは、入れ子関数 getが、その外側の mainのローカル変数 vの値を参照する例である。

#include 

int main() {
 int v = 5;
 int get() { return v; }
 printf("%d\n", get());
 return 0;
}

実行してみよう。

$ make NestedFunctionExample11
cc     NestedFunctionExample11.c   -o NestedFunctionExample11
$ ./NestedFunctionExample11
5

入れ子関数が、関数の中の単なるブロックであるかのように変数にアクセスできることがわかる。

入れ子関数のポインタ

関数のポインタを渡して、その渡した先で vにアクセスできるだろうか。

#include 

typedef int (*function)();

void sub(function f) {
 printf("%d\n", f());
}

int main() {
 int v = 5;
 int get() { return v; }
 sub(get);
 return 0;
}

$ make NestedFunctionExample12
cc     NestedFunctionExample12.c   -o NestedFunctionExample12
$ ./NestedFunctionExample12
5

subの中から呼び出されている関数 fが mainのローカル変数 vにアクセスできている。

subは mainのスタックフレームにアクセスできるだけなのか、自身のフレームも持っているのだろうか。

#include 

typedef int (*function)();

void sub(function f) {
        printf("%d\n", f());
}

int main() {
        int v = 5;
        int get() {
                int u = 3;
                printf("%d\n", u);
                return v + u;
        }
        sub(get);
        return 0;
}

$ make NestedFunctionExample13
cc     NestedFunctionExample13.c   -o NestedFunctionExample13
$ ./NestedFunctionExample13
3
8

これを見ると、自身のスタックフレームを持った上で、その外側にある関数のスタックフレームにもアクセスできるようだ。

外側の関数から復帰後

入れ子関数を定義した関数から復帰してしまったらどうか。

#include 

typedef int (*function)();

void sub(function f) {
 printf("%d\n", f());
}

function getFunction() {
 int v = 899;
 int get() { return v; }
 return get;
}

int main() {
 function f = getFunction();
 sub(f);
 return 0;
}

多分外側の関数のスタックフレームはもう無いからアクセスできないはず。

$ make NestedFunctionExample14
cc     NestedFunctionExample14.c   -o NestedFunctionExample14
$ ./NestedFunctionExample14
3
902

あれ、うまくアクセスできてしまった。

実はこれ、GCC 4.6.0 on SunOS 5.11 (x86)環境ではうまく行ってしまう。（様に見える）

同じコードを GCC 4.6.3 on Ubuntu 12.04 (x86)でやってみると。

$ make NestedFuctionExample14
cc     NestedFuctionExample14.c   -o NestedFuctionExample14
$ ./NestedFuctionExample14 
134513727

ちゃんと滅茶苦茶な値になった。（うまく行かなかったことを安心しているようで妙な表現だが）

Solarisでうまく行ったように見えたのはスタックフレームの内容が残っていたからで、いつもこう行くとは限らない。

たとえば、関数ポインタを取得してから呼び出すまでの間にスタックを使用するなにか別の関数を呼んでしまうと壊れてるはず。

#include 

typedef int (*function)();

void sub(function f) {
 printf("%d\n", f());
}

function getFunction() {
 int v = 899;
 int get() {
  int u = 3;
  printf("%d\n", u);
  return v + 3;
 }
 return get;
}

int main() {
 function f = getFunction();
 printf("Hello, world.\n");
 sub(f);
 return 0;
}

この様に、printfを入れてみよう。

$ make NestedFunctionExample15
cc     NestedFunctionExample15.c   -o NestedFunctionExample15
$ ./NestedFunctionExample15
Hello, world.
Segmentation Fault (core dumped)

値が可笑しくなるだけでなく、アクセス違反が生じてしまった。

入れ子関数 その１ (nested function 1)

例外機構、例外機構 その２で紹介した言語 Cでの例外処理の機構はマクロと関数を組み合わせて実現しているが、制約が多くまだ実験の初期段階の域を出ない。

制約のうちの幾つかは finally節に関するものである。

• finallyは省略できない。
• 同一スコープの中では finallyが2回以上記述できない。

これは、gccの入れ子関数(nested function)機能の使い方に由来する。

同一スコープの中で複数の入れ子関数を定義した場合になにが起こるか、GCCのオンラインドキュメントNested Functionsで調べてみたが、書かれていない。

そこで、幾つかの実験を行って見た。
使用した環境はつぎの通り。

• GCC 4.4.3 on Ubuntu 4.4.3-4ubuntu5.1 (x86)
• GCC 4.6.0 on SunOS 5.11 (x86)

異なるスコープで同じ名称の関数を定義した場合の振る舞い

まず同一スコープで複数回定義した場合の実験の前に、同じ名称の関数を異なるスコープで定義しそれを呼び出した場合になにが実行されるかを試してみる。

次のコードの関数 subが実験コードである。
外側と内側のスコープでは各々 "f(1)"、"f(2)"を表示する関数 fを定義している。
その後、fという名前の関数を呼び出すと呼び出したスコープに一番違い f(2)が呼び出されると思われる。

#include <stdio.h>

void sub() {
 void f() { printf("f(1)\n"); }
 {
  void f() { printf("f(2)\n"); }
  f();
 }
}

int main() {
 sub();
 return 0;
}

ビルドして、実行してみる。

$ make NestedFunctionExample1
cc     NestedFunctionExample1.c   -o NestedFunctionExample1
$ ./NestedFunctionExample1
f(2)

予想通り、f(2)が表示された。

念のため、関数 subを書き換えて、内部の定義が無くとも外部の定義が呼ばれることを確認しておく。

void sub() {
 void f() { printf("f(1)\n"); }
 {
  f();
 }
}

$ make NestedFunctionExample2
cc     NestedFunctionExample2.c   -o NestedFunctionExample2
$ ./NestedFunctionExample2
f(1)

期待通り、外側のスコープで定義した入れ子関数が呼び出された。

内側のスコープで 関数 fを定義する前に fという名前で呼び出しを行なおうとしたらコンパイルは通るのか、通ったとしたら何が呼ばれるのかを試してみる。

void sub() {
 void f() { printf("f(1)\n"); }
 {
  f();
  void f() { printf("f(2)\n"); }
  f();
 }
}

$ make NestedFunctionExample3
cc     NestedFunctionExample3.c   -o NestedFunctionExample3
$ ./NestedFunctionExample3
f(1)
f(2)

コンパイルはエラーにならなかった。自動変数の場合もスコープが違えば同じ名前でもちゃんと区別されるので期待通りだ。
内側の定義を行う前と後では呼び出される関数が異なることが判明した。
これは自然な感じがする。

前方参照を用いて、外側の関数定義を呼び出しより後に定義したらコンパイル、実行はどうなるだろうか。

void sub() {
 auto void f();
 {
  f();
  void f() { printf("f(2)\n"); }
  f();
 }
 void f() { printf("f(1)\n"); }
}

$ make NestedFunctionExample4
cc     NestedFunctionExample4.c   -o NestedFunctionExample4
$ ./NestedFunctionExample4
f(1)
f(2)

おお、すばらしい。

同一スコープで同じ名称の関数を定義した場合の振る舞い

いよいよ、同じ関数名で定義したらどうなるか。

void sub() {
 void f() { printf("f(1)\n"); }
 f();
 void f() { printf("f(2)\n"); }
 f();
}

$ make NestedFunctionExample5
cc     NestedFunctionExample5.c   -o NestedFunctionExample5
NestedFunctionExample5.c: In function ‘sub’:
NestedFunctionExample5.c:11:7: error: redefinition of ‘f’
NestedFunctionExample5.c:9:7: note: previous definition of ‘f’ was here
make: *** [NestedFunctionExample5] Error 1

関数fの再定義はコンパイルエラーとなる。

でも諦めない。なぜなら例外機構では try～catch～finallyを 2個並べてもコンパイルは通っているのだから。
1個目の定義のあと、宣言を入れてみよう。

void sub() {
 void f() { printf("f(1)\n"); }
 f();
 auto void f();
 void f() { printf("f(2)\n"); }
 f();
}

vi NestedFunctionExample6.c
$ make NestedFunctionExample6
cc     NestedFunctionExample6.c   -o NestedFunctionExample6
$ ./NestedFunctionExample6
f(2)
f(2)

コンパイルは通った。
だが、どちらも2個目の定義が呼ばれていて、1個目の定義は無視されている。
これが、例外機構での制約の原因だ。

最初の呼び出しでは1個目の定義のが呼ばれても良いような気がするのだが。

gccのソースを見ていないので憶測だが、同一スコープで同じ名前の関数を定義しようとすると１つ前の実験でわかるように名前の衝突が起きてエラーになるが、
宣言を書けば衝突は回避されるようだ。
しかし、定義の前でも後でも2個目に定義した関数が呼ばれているところを見れば、単純に関数定義を上書きしているのだろう。

宣言は前方参照できるはずなので、定義を呼び出しを逆にしても結果は同じである。

void sub() {
 void f() { printf("f(1)\n"); }
 f();
 auto void f();
 f();
 void f() { printf("f(2)\n"); }
}

$ make NestedFunctionExample7
cc     NestedFunctionExample7.c   -o NestedFunctionExample7
$ ./NestedFunctionExample7
f(2)
f(2)

当然だけど、次の例も再定義でエラーになる。

void sub() {
 auto void f();
 f();
 void f() { printf("f(1)\n"); }
 f();
 void f() { printf("f(2)\n"); }
}

$ make NestedFunctionExample8
cc     NestedFunctionExample8.c   -o NestedFunctionExample8
NestedFunctionExample8.c: In function ‘sub’:
NestedFunctionExample8.c:13:7: error: redefinition of ‘f’
NestedFunctionExample8.c:11:7: note: previous definition of ‘f’ was here
make: *** [NestedFunctionExample8] Error 1

これまで定義が2個の例を示したが、次のように3個以上でも同じことである。

void sub() {
 auto void f();
 f();
 void f() { printf("f(1)\n"); }

 auto void f();
 f();
 void f() { printf("f(2)\n"); }

 auto void f();
 f();
 void f() { printf("f(3)\n"); }

 auto void f();
 f();
 void f() { printf("f(4)\n"); }
}

$ vi NestedFunctionExample9.c
$ make NestedFunctionExample9
cc     NestedFunctionExample9.c   -o NestedFunctionExample9
$ ./NestedFunctionExample9
f(4)
f(4)
f(4)
f(4)

以上の結果から、定義と宣言を分けると同一スコープに同じ名称の関数定義を記述することはできるが、最後の定義のみが有効となることが判明した。

これでは現在の例外機構の案では実用にはならない。

gccのバージョンが変わったら挙動が変わる可能性もある。