遅ればせながら、NetBSD Advent Calendar 2017、22日目の記事です。
今日はNetBSDのuuidgenコマンドについて書こうと思います。
UUIDって何？
UUID(Wikipedia)は「ソフトウェア上でオブジェクトを一意に識別するための識別子である。」(WikipediaのUUIDの記事より引用)と解説されています。この一意な識別子(ユニークな値)を生成するのが、uuidgenコマンドになります。
uuidgenコマンドはLinuxにも存在していますが、NetBSDでの実行例は以下のようになります。
$ uuidgen
8515c55e-e889-11e7-a5dc-080027b65d7f
uuidgenコマンドのソースコードを追いかけてみる
それでは /usr/src 以下にNetBSDのソースコードが展開されている状態でuuidgenコマンドを読んでみます。
ソースコードの展開方法はカーネルソースコードの取得の記事をご参照ください。
whichで確認すると、uuidgenコマンドは /usr/bin に置かれていることが分かります。
$ which uuidgen
/usr/bin/uuidgen
ソースコード的には /usr/src/usr.bin の下に /usr/bin に対応するコマンドのソースコードが置かれていますので、今回のケースでは /usr/src/usr.bin/uuidgen にお目当てのソースコードがあります。
$ cd /usr/src/usr.bin/uuidgen/
$ ls
CVS/ Makefile uuidgen.1 uuidgen.c
ユーザランド側のコードはシンプル
uuidgen.c を読んでみます。行数的には180行ちょいなので、何かライブラリを呼ぶだけの処理なのかもしれません。
$ wc -l uuidgen.c
185 uuidgen.c
main() を読み進めてみると、 uuidgen() という関数を読んでいるようです。
76 int
77 main(int argc, char *argv[])
78 {
79 FILE *fp;
80 uuid_t *store, *uuid;
...
124 store = (uuid_t*)malloc(sizeof(uuid_t) * count);
...
128 if (!iterate) {
129 /* Get them all in a single batch */
130 if (uuidgen(store, count) != 0)
man uuidgen で調べてみると、どうやらシステムコールのようです。コードの構成としては、ユーザランド側では単に uuidgen() システムコールを呼ぶだけのようですね。
UUIDGEN(2) System Calls Manual UUIDGEN(2)
NAME
uuidgen -- generate universally unique identifiers
LIBRARY
Standard C Library (libc, -lc)
SYNOPSIS
#include <sys/types.h>
#include <sys/uuid.h>
int
uuidgen(struct uuid *store, int count);
DESCRIPTION
The uuidgen() system call generates count universally unique identifiers
(UUIDs) and writes them to the buffer pointed to by store. ...
その後、 uuid_to_string() 関数を読んでいますが、こちらはユーザランド側の lib/libc/uuid/uuid_to_string.c で定義されているライブラリ関数となっています。 uuid_to_string() の実体は取得したデータを文字列の形に整形しなおす文字列処理関となっています。
uuidgenシステムコールを追いかけてみる
それでは、uuidgenシステムコールを追いかけてみましょう。NetBSDのシステムコールは sys_*() という形で定義されるので、えいやで sys_uuidgen() という関数が定義されているか調べてみます。
$ cd /usr/src/sys
$ global sys_uuidgen
kern/kern_uuid.c
首尾よく関数が定義されている kern/kern_uuid.c を見つけることができました。
213 int
214 sys_uuidgen(struct lwp *l, const struct sys_uuidgen_args *uap, register_t *retval)
215 {
216 /*
217 * Limit the number of UUIDs that can be created at the same time
218 * to some arbitrary number. This isn't really necessary, but I
219 * like to have some sort of upper-bound that's less than 2G :-)
220 * XXX needs to be tunable.
221 */
222 if (SCARG(uap,count) < 1 || SCARG(uap,count) > 2048)
223 return (EINVAL);
224
225 return kern_uuidgen(SCARG(uap, store), SCARG(uap,count), true);
226 }
sys_uuidgen() から同ファイルにある kern_uuidgen() を呼び出しています。
181 static int
182 kern_uuidgen(struct uuid *store, int count, bool to_user)
183 {
184 struct uuid_private uuid;
185 uint64_t xtime;
...
190 /* Generate the base UUID. */
191 uuid_generate(&uuid, &xtime, count);
...
210 return error;
211 }
kern_uuidgen() から呼ばれる uuid_generate() がUUID生成の主処理になっていますね。
152 /*
153 * Internal routine to actually generate the UUID.
154 */
155 static void
156 uuid_generate(struct uuid_private *uuid, uint64_t *timep, int count)
157 {
158 uint64_t xtime;
159
160 mutex_enter(&uuid_mutex);
161
162 uuid_node(uuid->node);
163 xtime = uuid_time();
164 *timep = xtime;
165
166 if (uuid_last.time.ll == 0LL || uuid_last.node[0] != uuid->node[0] ||
167 uuid_last.node[1] != uuid->node[1] ||
168 uuid_last.node[2] != uuid->node[2])
169 uuid->seq = (uint16_t)cprng_fast32() & 0x3fff;
170 else if (uuid_last.time.ll >= xtime)
171 uuid->seq = (uuid_last.seq + 1) & 0x3fff;
172 else
173 uuid->seq = uuid_last.seq;
174
175 uuid_last = *uuid;
176 uuid_last.time.ll = (xtime + count - 1) & ((1LL << 60) - 1LL);
177
178 mutex_exit(&uuid_mutex);
179 }
でも何でシステムコールなのだろう？
ざっとソースコードを読んでみて、UUIDはカーネルの中で生成していることが分かりました。
とはいえ、何でシステムコールをわざわざ呼び出すのでしょうか？ ユーザランドでUUIDを生成すれば、カーネルに切り替えるオーバーヘッドを減らせるはずなのに...。
手がかりとして、UUIDの仕様であるRFC4122を参照してみましょう。
その中の"Declaration of syntactic structure:"で、ABNFによるUUIDの構造が定義されています。
UUID = time-low "-" time-mid "-"
time-high-and-version "-"
clock-seq-and-reserved
clock-seq-low "-" node
time-low = 4hexOctet
time-mid = 2hexOctet
time-high-and-version = 2hexOctet
clock-seq-and-reserved = hexOctet
clock-seq-low = hexOctet
node = 6hexOctet
hexOctet = hexDigit hexDigit
hexDigit =
"0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" /
"a" / "b" / "c" / "d" / "e" / "f" /
"A" / "B" / "C" / "D" / "E" / "F"
clock-seq-... という定義から、何か時間に関連するシーケンス番号が必要となることが分かります。
カーネルソースを読み返してみると、 uuid_private という変数でシーケンス番号を一意に扱っているようです。 uuid_generate() の中でシーケンス番号を更新しており、かつ mutex_enter() でクリティカルセクション内の処理としていることから、この処理は常に一人しか実行できない(＝順番が守られる)実装となっています。
80 static struct uuid_private uuid_last;
...
155 static void
156 uuid_generate(struct uuid_private *uuid, uint64_t *timep, int count)
157 {
158 uint64_t xtime;
159
160 mutex_enter(&uuid_mutex);
161
162 uuid_node(uuid->node);
163 xtime = uuid_time();
164 *timep = xtime;
165
166 if (uuid_last.time.ll == 0LL || uuid_last.node[0] != uuid->node[0] ||
167 uuid_last.node[1] != uuid->node[1] ||
168 uuid_last.node[2] != uuid->node[2])
169 uuid->seq = (uint16_t)cprng_fast32() & 0x3fff;
170 else if (uuid_last.time.ll >= xtime)
171 uuid->seq = (uuid_last.seq + 1) & 0x3fff;
172 else
173 uuid->seq = uuid_last.seq;
174
175 uuid_last = *uuid;
176 uuid_last.time.ll = (xtime + count - 1) & ((1LL << 60) - 1LL);
つまり、UUIDの生成をカーネル内で行っているのは、生成するUUIDをホスト内で一意にするためにシーケンス番号が必要であり、その処理はカーネル内でないと行えないから、ということですね。
まとめ
NetBSDの uuidgen コマンドの実装をざっと読み進めてみました。何となくユーザランド側だけでUUIDの生成が完結させられそうな気がしていましたが、仕様と照らし合わせることで、ユーザランド/カーネルのどちらで実装するべきかが見えてくるという、実装の勘どころをつかむのに良い題材のようにも思えます。