NetBSDのuuidgenコマンドの実装を読んでみる

遅ればせながら、[NetBSD Advent Calendar 2017](https://qiita.com/advent-calendar/2017/netbsd)、22日目の記事です。
今日はNetBSDの[uuidgen](http://netbsd.gw.com/cgi-bin/man-cgi?uuidgen++NetBSD-current)コマンドについて書こうと思います。

## UUIDって何？

[UUID(Wikipedia)](https://ja.wikipedia.org/wiki/UUID)は「ソフトウェア上でオブジェクトを一意に識別するための識別子である。」(Wikipediaの[UUID](https://ja.wikipedia.org/wiki/UUID)の記事より引用)と解説されています。この一意な識別子(ユニークな値)を生成するのが、[uuidgen](http://netbsd.gw.com/cgi-bin/man-cgi?uuidgen++NetBSD-current)コマンドになります。

uuidgenコマンドはLinuxにも存在していますが、NetBSDでの実行例は以下のようになります。

```sh
$ uuidgen 
8515c55e-e889-11e7-a5dc-080027b65d7f
```

## uuidgenコマンドのソースコードを追いかけてみる

それでは `/usr/src` 以下にNetBSDのソースコードが展開されている状態でuuidgenコマンドを読んでみます。
ソースコードの展開方法は[カーネルソースコードの取得](https://qiita.com/furandon_pig/items/35164d2ccc4e1dda160e#%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E3%82%BD%E3%83%BC%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89%E3%81%AE%E5%8F%96%E5%BE%97)の記事をご参照ください。

whichで確認すると、uuidgenコマンドは `/usr/bin` に置かれていることが分かります。

```sh
$ which uuidgen
/usr/bin/uuidgen
```

ソースコード的には `/usr/src/usr.bin` の下に `/usr/bin` に対応するコマンドのソースコードが置かれていますので、今回のケースでは `/usr/src/usr.bin/uuidgen` にお目当てのソースコードがあります。

```sh
$ cd /usr/src/usr.bin/uuidgen/
$ ls
CVS/        Makefile    uuidgen.1   uuidgen.c
```

### ユーザランド側のコードはシンプル

`uuidgen.c` を読んでみます。行数的には180行ちょいなので、何かライブラリを呼ぶだけの処理なのかもしれません。

```sh
$ wc -l uuidgen.c 
     185 uuidgen.c
```

`main()` を読み進めてみると、 `uuidgen()` という関数を読んでいるようです。

```c:/usr/src/usr.bin/uuidgen/uuidgen.c
 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()` という関数が定義されているか調べてみます。

```sh
$ cd /usr/src/sys
$ global sys_uuidgen
kern/kern_uuid.c
```

首尾よく関数が定義されている `kern/kern_uuid.c` を見つけることができました。

```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()` を呼び出しています。

```c:kern/kern_uuid.c:
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生成の主処理になっていますね。

```c:kern/kern_uuid.c:
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](https://tools.ietf.org/html/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()` でクリティカルセクション内の処理としていることから、この処理は常に一人しか実行できない(＝順番が守られる)実装となっています。

```c:kern/kern_uuid.c:
 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の生成が完結させられそうな気がしていましたが、仕様と照らし合わせることで、ユーザランド/カーネルのどちらで実装するべきかが見えてくるという、実装の勘どころをつかむのに良い題材のようにも思えます。

## 参考URL

 * [A Universally Unique IDentifier (UUID) URN Namespace](https://tools.ietf.org/html/rfc4122)
 * [UUID(Wikipedia)](https://ja.wikipedia.org/wiki/UUID)