2014-10-12

ある値より小さい乱数を得る - arc4random_uniform(3)

1つ前の記事に関連して、OpenBSDのarc4random(3)やarc4random_uniform(3)について調べていたのでメモ。

BSD系のlibcを用いているOS（OpenBSD・FreeBSD・OS X・iOSなど）で提供されている*1arc4random(3)は、[0, UINT_MAX)の範囲でランダムな値を返します。これを用いて、特定の範囲の乱数、ここでは、ある値より小さい乱数を得ることを考えます。

剰余を計算する

たとえば[0, 5)の範囲の整数である乱数を得たい場合に、お手軽に

int random_number = arc4random () % 5;

と剰余を計算する方法があります。しかし、この方法では生成される乱数に偏りができてしまいます。これはarc4random(3)自体の問題ではありません（後述）。

[0, 10)の範囲の整数である乱数を生成する関数rand10 ()があるとします。
この関数を用いて、3より小さい整数である乱数（[0, 3): 0・1・2のいずれか）を生成するとき、上記の方法を用いてみます。

rand10 ()	rand10 () mod 3
0	0
1	1
2	2
3	0
4	1
5	2
6	0
7	1
8	2
9	0

rand10 ()が、0〜9のいずれかの整数をランダムに偏りなく返したとしても、3の剰余を計算すると、0の出現率は4/10、1の出現率は3/10、2の出現率は3/10と、0が1や2よりも多く出現します。つまり、得られた乱数に偏りができてしまいます。

OpenBSDのarc4random(3)のmanpageによると、剰余を用いたときに偏りが出るこの現象を"modulo bias"と呼ぶそうです。

なお、剰余計算では下位のビットしか使われないため、線形合同法のような下位ビットの質が悪い乱数生成器を用いた場合にはさらに偏りができてしまいます。

0以上1未満の範囲にしてn倍する

[0, 5)の範囲の整数である乱数を得たい場合に、

int random_number = ((double) arc4random () / UINT32_MAX+1.0) * 5;

のように、0以上1未満の範囲の実数にした上で5倍する方法があります。

ステップを分解してみます。

uint32_tの範囲の乱数を生成する: [0, UINT32_MAX]
UINT32_MAX+1.0で割る: [0.0, 1.0)
5倍する: [0.0, 5.0)
小数点以下を切り捨てて整数にする

この方法でも、得られる乱数に偏りがあります。

再びrand10 ()を用いて、3より小さい整数である乱数（[0, 3): 0・1・2のいずれか）を生成する場合を考えてみます。

rand10 ()	rand10 () / 10.0	rand10 () / 10.0 * 3	floor (rand10 () / 10.0 * 3)
0	0.0	0.0	0
1	0.1	0.3	0
2	0.2	0.6	0
3	0.3	0.9	0
4	0.4	1.2	1
5	0.5	1.5	1
6	0.6	1.8	1
7	0.7	2.1	2
8	0.8	2.4	2
9	0.9	2.7	2

1・2は3回ですが、0は4回出現しており、偏りができています。
この偏りはrand10 ()が生成する値の範囲を広くすれば相対的に小さくなると考えられますが、それでも一様であるとはいえなくなります。

なお、この方法では上位のビットを使うため、下位ビットの質が悪い乱数生成器を用いた場合でも剰余を用いた方法のような偏りは生じません。

arc4random_uniform(3)を使う

arc4random(3)とともに、ある値より小さい乱数を返すarc4random_uniform(3)という関数も提供されています。

arc4random_uniform(3)は引数として生成される乱数のupper boundを取ります。そして、0以上で指定された値より小さい整数である乱数を返します。

arc4random_uniform(3)も内部ではarc4random(3)を呼び出して乱数を生成し、先に説明した剰余を用いる方法で、指定された値より小さい乱数にしています。しかし、modulo biasの影響がないように、乱数をあらかじめ選別しています。

選別する方法ですが、ソースコードの説明には、[0, 2³² mod upper bound)の範囲から外れる乱数が生成されるまで乱数の生成を繰り返すことで、[2³² mod upper bound, 2³²)の範囲の乱数を得る、とあります。説明だと何のことだかさっぱり分かりませんが、mod upper boundされた状態でUINT_MAXから数えて[0, upper bound）の列がぴったりn回出現するように、範囲を制限しているようです。

イメージとしては、0からUINT_MAXまでの数字が書かれた、厚みのないセロハンテープのような細長い紙を筒に最後まで巻いて、内側の切れ端と外側の切れ端が合わない余った部分を内側から切り落とす感じになると思います。

下からではなく上から切っていく方法でもよいと思いますが、この場合の選別する範囲を算出するには、mod upper boundが0になる最大の値を探す必要があります。これはfloor (2³²/upper bound) * upper boundで計算できます。しかし、2³²というuint32_tに格納できない値が出てきている点がいけてないです。

範囲から外れた値がarc4random(3)から返ってきた場合には再度arc4random(3)を呼び出している*2ため、運が悪いと何度もarc4random(3)を呼び出すことになりそうです。最良の場合の一例（upper bound = 2; 2³² mod 2 = 0）では範囲外となるのは[0, 0)であり範囲から外れる値はありません。最悪の場合（upper bound = 2³¹+1; 2³² mod (2³¹+1) = 2147483647）では範囲外となるのは[0, 2147483647)と約50%の確率ですが、よほど運が悪くない限りは多くの試行を必要としないと思われます。

再びrand10 ()を用いて、3より小さい整数である乱数（[0, 3): 0・1・2のいずれか）を生成することを考えてみます。2³² mod 3 = 1ですので、範囲チェックとして[0, 1)であればその値を不採用とします。

rand10 ()	範囲チェック	rand10 () % 3
0	×	-
1	○	1
2	○	2
3	○	0
4	○	1
5	○	2
6	○	0
7	○	1
8	○	2
9	○	0

このように、0・1・2が均等に分布していることが分かります。

先に述べましたが、arc4random_uniform(3)も、内部ではarc4random(3)を呼び出しています*3。arc4random(3)の返す乱数が良くないというよりも、その結果を加工する方法が良くないということです。

なおこの方法は乱数に対して剰余計算を行っているため、下位ビットの質が悪い乱数生成器と組み合わせることはできません。

*1:Linuxでも、たとえばDebianではlibbsdライブラリとして提供されています

*2:ソースコードでもfor (;;)を用いた無限ループになっています

*3:libc/crypt/arc4random_uniform.c

2014-09-09

時刻同期

ntpdのこまったところ

0.0.0.0:123をbind(2)する

後述のようにACLをかけられるとはいえ、INADDR_ANYは気持ち悪い気がします。また、FreeBSDのJail環境など、見えているNIC全てにbind(2)されると困る場合もあるでしょう。

ACLの書き方が分かりづらい

nomodify/notrap/noquery/nopeerなどキーワードがたくさんで分かりづらいです。うっかりmonlistのようなリクエストに応答するような設定にしてしまいそうです。

他の実装: OpenNTPD

http://www.openntpd.org/

いいところ: 0.0.0.0:123をbindしない

デフォルトでは、NTPサーバーとして指定されたホストとconnect(2)するだけです。このとき発信元UDPポート番号は123固定ではなく、ランダムなポート番号が選択されます。
設定ファイルで明示的に

listen on 192.0.2.123
listen on 2001:db8::beef::123

と指定すると、そのローカルアドレスをbind(2)してNTPリクエストに答えるようになります。ただし細かいACLは記述できないようなので、より細かいアドレス単位で制限するにはOSのパケットフィルタなどを利用することになると思われます。

いいところ: セキュアな実装

OpenSSHと同様に、特権が必要な最小限の操作を行うプロセスと、そのほかの仕事を行う（一般ユーザー権限で動作するchrootされた）プロセスに分離されています。

またclient.cやOpenCon 2004でのプレゼンテーションを読むと分かるのですが、リクエストのTransmit Timestampフィールド（64ビット）に（暗号学的に安全で）ランダムな値をクッキーとして格納してクライアント側でも保存しておき、応答を受信したときに照合して応答が偽装されていないことを確認しています。RFC 958では、リクエストのTransmit TimestampフィールドはレスポンスのOriginate Timestampフィールドにコピーされることになっています。このアイディアは、応答の偽装を防ぐほかに、クライアントの現在時刻が外に漏れないという効果もあります。

こまったところ: ポータブル版がメンテナンスされていない

OpenNTPD 4.4は2008年11月にリリースされましたが、OpenBSD以外でも動作するポータブル版は、2014年9月現在でもOpenNTPD 3.9p1となっています。

公式サイトに「ポータブル版は古くなっており、メンテナーを必要としてる」と記載されている状態です。
DebianやFreeBSDなど、ディストリビューションのメンテナーがメンテナンスしているものを利用するのがよいと思われます。数年前にポータブル版の差分をOpenNTPD 4.4に適用してちょっといじったものを手元でエージング試験（という名の放置）していました*1が、最近のDebianで提供されているパッケージはもう少し最近のものをベースにしているようです。OpenNTPD 3.9p1では存在しなかった機能としてntpd.driftファイルが作成されるようになりました。

ちなみにポータブル版は、他のプラットフォームで提供されていない関数（arc4random(3)、strlcpy(3)など）の実装を追加し、いくつか#ifdefマクロを追加した形となっています。移植性を確保するという点において、（別のチームが開発している）OpenSSLは、各種規格に準拠したプラットフォームをエミュレーションした上で開発するようなイメージ（個人の感想です）ですが、OpenNTPDやOpenSSHはOpenBSDという実在のプラットフォーム上で開発を行い、そこに存在しない・挙動の異なる箇所だけをポータブル版に実装するようなイメージ（個人の感想です）です。

こまったところ: ntpqのようなコマンドがない

ntpdではntpq -pコマンドでピアの一覧と状態を調べることができますが、OpenNTPDにはこのようなコマンドがありません。ピアがvalidになった/invalidになったときにsyslogにメッセージを出力するだけです。SIGINFOシグナルを送ると、各ピアがvalidか否かをsyslogに出力することはできます*2が、ntpq -pコマンドのようにoffsetやjitterなどは得られないようです。monlistリクエストもサポートしていません。

こまったところ: 機能的な制限がある

ブロードキャストNTPには対応していないようです。また、NTP Authentication（共通鍵暗号や公開鍵暗号を用いてNTPメッセージを認証する機能）にも対応していないようです。どちらも使ったことがないのであまり困っていないのですが。
ntp.orgの説明によると、マイクロ秒単位の精度を得られることを設計上のゴールとしていないと書いてあるのですが、adjtimex(2)などを呼び出しているあたりのコードを読めていないので、よくわかりません。

他の実装: Chrony

http://chrony.tuxfamily.org/

インストールして

chronyc sources -v

コマンドを実行して、ntpq -pより見た目が豪華なのを確認した程度であまり触れていません。そのうち書くかも。

まとめ

0.0.0.0:123をntpdがbind(2)する件でお困りの方で、マイクロ秒単位の時刻同期を必要としない方は、OpenNTPDを使うと幸せになれるかもしれません。

*1:ポータブル版やDebianのパッチなどあちこちからコードを拝借したためライセンスが不明確になってしまった、ということもあります

*2:2014/9/19追記: SIGINFOがないので、Debianのパッケージではサポートされていません。SIGUSR1を代わりに使えばよい？

2014-05-23

portsnapで管理しているPorts Collectionにローカルでパッチを当てる

ハンドブックには「ローカルの変更を保持するにはSubversionを使ってね」と書いてあり、検索してもヒットしなかったのでメモ。

files/以下にパッチを置いてもportsnap updateしたときに消されてしまうので、ports-mgmt/portconfとの合わせ技で、

適当なディレクトリにパッチを配置
ports.confで対象のportにEXTRA_PATCHESを指定

EXTRA_PATCHES=/path/to/local-patch

という方法でうまくいきそうです。

2014-05-21

tmuxで、フォーマット変数にロードアベレージを追加するパッチ

tmux 1.9a用。AIXとHP-UXは未対応です。

---
 format.c          |  7 ++++++-
 osdep-aix.c       |  6 ++++++
 osdep-darwin.c    | 11 +++++++++++
 osdep-dragonfly.c | 11 +++++++++++
 osdep-freebsd.c   | 11 +++++++++++
 osdep-hpux.c      |  6 ++++++
 osdep-linux.c     | 17 +++++++++++++++++
 osdep-netbsd.c    | 11 +++++++++++
 osdep-openbsd.c   | 11 +++++++++++
 osdep-sunos.c     | 11 +++++++++++
 osdep-unknown.c   |  6 ++++++
 tmux.1            |  1 +
 tmux.h            |  1 +
 13 files changed, 109 insertions(+), 1 deletion(-)

diff --git a/format.c b/format.c
index 10ac613..396df52 100644
--- a/format.c
+++ b/format.c
@@ -62,7 +62,7 @@ const char *format_upper[] = {
 	"window_index",	/* I */
 	NULL,		/* J */
 	NULL,		/* K */
-	NULL,		/* L */
+	"load_average",	/* L */
 	NULL,		/* M */
 	NULL,		/* N */
 	NULL,		/* O */
@@ -115,6 +115,7 @@ format_create(void)
 {
 	struct format_tree	*ft;
 	char			 host[MAXHOSTNAMELEN], *ptr;
+	double			 la[3];
 
 	ft = xmalloc(sizeof *ft);
 	RB_INIT(ft);
@@ -126,6 +127,10 @@ format_create(void)
 		format_add(ft, "host_short", "%s", host);
 	}
 
+	if (osdep_getloadavg(la) == 0) {
+		format_add(ft, "load_average", "%.2f %.2f %.2f", la[0], la[1], la[2]);
+	}
+
 	return (ft);
 }
 
diff --git a/osdep-aix.c b/osdep-aix.c
index 8d59081..fe1660a 100644
--- a/osdep-aix.c
+++ b/osdep-aix.c
@@ -39,3 +39,9 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	return (1);
+}
diff --git a/osdep-darwin.c b/osdep-darwin.c
index dc60b09..6c01204 100644
--- a/osdep-darwin.c
+++ b/osdep-darwin.c
@@ -27,6 +27,7 @@
 char			*osdep_get_name(int, char *);
 char			*osdep_get_cwd(int);
 struct event_base	*osdep_event_init(void);
+int			 osdep_getloadavg(double [3]);
 
 #define unused __attribute__ ((unused))
 
@@ -78,3 +79,13 @@ osdep_event_init(void)
 	setenv("EVENT_NOPOLL", "1", 1);
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-dragonfly.c b/osdep-dragonfly.c
index ad417d9..f22a001 100644
--- a/osdep-dragonfly.c
+++ b/osdep-dragonfly.c
@@ -33,6 +33,7 @@ struct kinfo_proc	*cmp_procs(struct kinfo_proc *, struct kinfo_proc *);
 char			*osdep_get_name(int, char *);
 char			*osdep_get_cwd(int);
 struct event_base	*osdep_event_init(void);
+int			 osdep_getloadavg(double [3]);
 
 #ifndef nitems
 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
@@ -131,3 +132,13 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-freebsd.c b/osdep-freebsd.c
index d596eab..b44265e 100644
--- a/osdep-freebsd.c
+++ b/osdep-freebsd.c
@@ -35,6 +35,7 @@ struct kinfo_proc	*cmp_procs(struct kinfo_proc *, struct kinfo_proc *);
 char			*osdep_get_name(int, char *);
 char			*osdep_get_cwd(int);
 struct event_base	*osdep_event_init(void);
+int			 osdep_getloadavg(double [3]);
 
 #ifndef nitems
 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
@@ -168,3 +169,13 @@ osdep_event_init(void)
 	setenv("EVENT_NOKQUEUE", "1", 1);
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-hpux.c b/osdep-hpux.c
index 352e375..332b6be 100644
--- a/osdep-hpux.c
+++ b/osdep-hpux.c
@@ -39,3 +39,9 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	return (1);
+}
diff --git a/osdep-linux.c b/osdep-linux.c
index ccac267..ed46e71 100644
--- a/osdep-linux.c
+++ b/osdep-linux.c
@@ -18,6 +18,7 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/sysinfo.h>
 
 #include <event.h>
 #include <stdio.h>
@@ -88,3 +89,19 @@ osdep_event_init(void)
 	setenv("EVENT_NOEPOLL", "1", 1);
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	struct sysinfo sinfo;
+
+	if (sysinfo(&sinfo) != 0) {
+		return (1);
+	}
+
+	la[0] = sinfo.loads[0] / (double) (1 << SI_LOAD_SHIFT);
+	la[1] = sinfo.loads[1] / (double) (1 << SI_LOAD_SHIFT);
+	la[2] = sinfo.loads[2] / (double) (1 << SI_LOAD_SHIFT);
+
+	return (0);
+}
diff --git a/osdep-netbsd.c b/osdep-netbsd.c
index f16d0dc..4e7fa1b 100644
--- a/osdep-netbsd.c
+++ b/osdep-netbsd.c
@@ -36,6 +36,7 @@ struct kinfo_proc2	*cmp_procs(struct kinfo_proc2 *, struct kinfo_proc2 *);
 char			*osdep_get_name(int, char *);
 char			*osdep_get_cwd(int);
 struct event_base	*osdep_event_init(void);
+int			 osdep_getloadavg(double [3]);
 
 struct kinfo_proc2 *
 cmp_procs(struct kinfo_proc2 *p1, struct kinfo_proc2 *p2)
@@ -135,3 +136,13 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-openbsd.c b/osdep-openbsd.c
index 0a4c144..4badcbf 100644
--- a/osdep-openbsd.c
+++ b/osdep-openbsd.c
@@ -40,6 +40,7 @@ struct kinfo_proc	*cmp_procs(struct kinfo_proc *, struct kinfo_proc *);
 char			*osdep_get_name(int, char *);
 char			*osdep_get_cwd(int);
 struct event_base	*osdep_event_init(void);
+int			 osdep_getloadavg(double [3]);
 
 struct kinfo_proc *
 cmp_procs(struct kinfo_proc *p1, struct kinfo_proc *p2)
@@ -154,3 +155,13 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-sunos.c b/osdep-sunos.c
index fd644f5..78716a8 100644
--- a/osdep-sunos.c
+++ b/osdep-sunos.c
@@ -18,6 +18,7 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/loadavg.h>
 
 #include <event.h>
 #include <fcntl.h>
@@ -90,3 +91,13 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	if (getloadavg(la, 3) != 3) {
+		return (1);
+	}
+
+	return (0);
+}
diff --git a/osdep-unknown.c b/osdep-unknown.c
index 41f435b..0d5f9b5 100644
--- a/osdep-unknown.c
+++ b/osdep-unknown.c
@@ -39,3 +39,9 @@ osdep_event_init(void)
 {
 	return (event_init());
 }
+
+int
+osdep_getloadavg(double la[3])
+{
+	return (1);
+}
diff --git a/tmux.1 b/tmux.1
index 51d927a..160a10c 100644
--- a/tmux.1
+++ b/tmux.1
@@ -3117,6 +3117,7 @@ The following variables are available, where appropriate:
 .It Li "keypad_cursor_flag" Ta "" Ta "Pane keypad cursor flag"
 .It Li "keypad_flag" Ta "" Ta "Pane keypad flag"
 .It Li "line" Ta "" Ta "Line number in the list"
+.It Li "load_average" Ta "#L" Ta "System load averages"
 .It Li "mouse_any_flag" Ta "" Ta "Pane mouse any flag"
 .It Li "mouse_button_flag" Ta "" Ta "Pane mouse button flag"
 .It Li "mouse_standard_flag" Ta "" Ta "Pane mouse standard flag"
diff --git a/tmux.h b/tmux.h
index 7d5f230..1a7db34 100644
--- a/tmux.h
+++ b/tmux.h
@@ -2322,6 +2322,7 @@ u_int	utf8_split2(u_int, u_char *);
 char		*osdep_get_name(int, char *);
 char		*osdep_get_cwd(int);
 struct event_base *osdep_event_init(void);
+int		 osdep_getloadavg(double [3]);
 
 /* log.c */
 void		 log_open(int, const char *);
--

2015/7/16追記:

GitHub:kidmin/tmux でぼちぼち。pull requestを送るつもりはないですが、upstreamからは気が向いたら同期してます。

2013-08-05

OS XのNFSクライアントとUnicode正規化

最近身近で困ったので。

Mac OS Xではファイル名はNFDで正規化されているので、NFCでファイル名が正規化されたファイルシステムをそのままNFSでマウントすると、濁音や半濁音などが混じったファイル名を正しく扱うことができません。

mount_nfs(8)を参照すると、nfcというオプションがあります。このオプションを指定してマウントすると、NFSサーバとのやりとりをする際にファイル名をNFCで正規化するため、濁音や半濁音などが混じったファイル名でも正しく扱うことができるようになります。

mount_nfs(8)にも記載がありますが、/etc/nfs.confにマウント時のデフォルトオプションを記述することができます。私の周辺では、ファイル名をNFDで正規化するNFSサーバは存在しないので、/etc/nfs.confに

nfs.client.mount.options = nfc

と書きました。これにより、FinderからNFSサーバを指定してマウントした場合でも上記オプションが指定されます。

2011-03-12

生きてます

自宅も無事でした。

4時間半ほどかけて会社から歩いて帰ってみました。古い建物で外壁がはがれていたのを見た以外は、都内は建物に大きな被害はないように見えました。昨夜の段階では電車はほとんど動いていなかったのですが、バスの復旧は早かったようです。自宅周辺に向かう終バスに途中で追い越された時は、力が抜けそうになりました・・・。

エレベーターの復旧はいつになるんだろう。

2010-11-21

たぶん葛飾区

ねこ

そろそろデジカメが欲しい、かも。

rand10 ()	rand10 () / 10.0	rand10 () / 10.0 * 3	floor (rand10 () / 10.0 * 3)
0	0.0	0.0	0
1	0.1	0.3	0
2	0.2	0.6	0
3	0.3	0.9	0
4	0.4	1.2	1
5	0.5	1.5	1
6	0.6	1.8	1
7	0.7	2.1	2
8	0.8	2.4	2
9	0.9	2.7	2

rand10 ()	rand10 () / 10.0	rand10 () / 10.0 * 3	floor (rand10 () / 10.0 * 3)
0	0.0	0.0	0
1	0.1	0.3	0
2	0.2	0.6	0
3	0.3	0.9	0
4	0.4	1.2	1
5	0.5	1.5	1
6	0.6	1.8	1
7	0.7	2.1	2
8	0.8	2.4	2
9	0.9	2.7	2

rand10 ()	rand10 () / 10.0	rand10 () / 10.0 * 3	floor (rand10 () / 10.0 * 3)
0	0.0	0.0	0
1	0.1	0.3	0
2	0.2	0.6	0
3	0.3	0.9	0
4	0.4	1.2	1
5	0.5	1.5	1
6	0.6	1.8	1
7	0.7	2.1	2
8	0.8	2.4	2
9	0.9	2.7	2