第3回 — C言語の連結リストとlldbによる検証

前回は、動的に確保した領域の有効期間と構造体の配置を説明した。本稿では両者を使って単方向連結リストを実装する。最後に、lldbでノードのメモリ内容を確認する。

実測例の環境はmacOSとApple clang、int は4バイト、ポインタは8バイト。アドレスの具体的な値は環境や実行ごとに異なる。

出発点: 配列では困ること

要素の列を配列で作ると、次の性質に縛られる。

連結リストでは、各ノードを別々に確保できる。ここで扱う単方向連結リストは、各ノードに次のノードへのポインタを保持する。ノードの移動を行わずに挿入・削除できるが、目的の位置を探すには走査が必要である。動的配列でも再確保による要素数の変更は可能であり、連結リストだけが選択肢ではない。

Q1. 散らばって置かれた要素たちが「列」として辿れるために、各要素が最低限持つべきものは何か。

1. ノードをつなぐ

リストの各要素をノードと呼ぶ。ノードの型を次のように定義する。

struct node { int value; struct node *next; };   /* 自分と同じ型へのポインタをメンバーに持つ */

この環境では、intのサイズとアラインメントは4、ポインタは8である。valueはオフセット0〜3に配置される。nextの先頭を8の倍数にするため、オフセット4〜7に4バイトのパディングが入る。nextはオフセット8〜15であり、構造体のサイズは16バイトとなる。

byte 0〜3 : value (int)
byte 4〜7 : パディング
byte 8〜15: next (ポインタ)
計 16バイト

Q2.

struct node { int value; struct node *next; } の sizeof はいくつか(この環境)。

まずスタック上のノードで、つなぎ方そのものを見る(まだ malloc は使わない)。

struct node c = {3, NULL};   /* 末尾: 次はない */
struct node b = {2, &c};
struct node a = {1, &b};     /* 先頭 */

実測すると:

sizeof(struct node) = 16

a = 0x16f43e450  value=1  next=0x16f43e460   ← b のアドレス
b = 0x16f43e460  value=2  next=0x16f43e470   ← c のアドレス
c = 0x16f43e470  value=3  next=0x0           ← NULL(次はない)

a.next の中に b のアドレスが入っている。ノードを連結するとは、nextに次のノードへのポインタを格納することに他ならない。

2. 走査: 列を辿る

列を先頭から末尾まで辿る(走査する)ループは、初期化・条件判定・更新の3つの処理でできている。

for (struct node *p = &a;  p != NULL;  p = p->next)
//     ①先頭から始める      ②NULLで止まる  ③nextで1つ進む

③の p = p->next は、pが指すノードのnextを読み、pへ代入する操作である。ノードの内容は変わらない。末尾のnextがNULLなので、次の条件判定でループが終了する。

通過: value=1 → value=2 → value=3

Q3.

a→b→c(valueはそれぞれ1, 2, 3)とつないだ列で、p = &a; の後 p = p->next; を2回実行した。p->value はいくつか。

Q4. p が末尾の c を指している状態で

p = p->next; を実行すると、p はどうなるか。

3. malloc版: ノードは散らばる

実用のリストは malloc で作る。関数にすると:

struct node *make_node(int value) {
    struct node *n = malloc(sizeof(struct node));
    if (n == NULL) return NULL;
    n->value = value;
    n->next = NULL;
    return n;
}

3つのノードを続けて確保したところ、この実行では偶然16バイト刻みで並んだ。そこでノードの間に無関係な malloc(96) を挟んでみる:

a = 0x1017dd8b0
b = 0x1017dd920      ← a から112バイト離れている
c = 0x1017dd990      ← b から112バイト離れている

通過: value=1 → value=2 → value=3   ← それでも正しい順で辿れる

ノードは散らばり、間には無関係なデータが挟まっているのに、走査は正しい順で回る。走査する順序は、各ノードのnextで決まる。 配列の要素は連続して配置されるが、連結リストのノードは連続している必要がない。

Q5. ノードのアドレスが散らばっていても、走査が a→b→c の順になるのはなぜか。

4. lldbでノードのメモリ内容を確認する

ここでは、printfによる表示ではなく、デバッガで停止中のプロセスのメモリ内容を直接確認する。実行ファイルはデバッグ情報つきでビルドする。

$ clang -Wall -g -O0 -o list_lldb list_lldb.c
$ lldb list_lldb
(lldb) b list_lldb.c:17     # 17行目にブレークポイント
(lldb) run                  # そこまで実行して停止

停止中に変数を見るには frame variable(略 v)、式を評価するには expr:

(lldb) p *a            # a が指すノードを構造体として表示
(value = 1, next = 0x0000000100651a30)

そして本題 — メモリのバイト列を読む。memory read に式の結果を渡すと、そのアドレスからダンプできる(expr a の結果は $0 に入る):

(lldb) expr a
$0 = 0x00000001006506a0
(lldb) memory read -c 4 -s 4 -f x $0     # 4バイト×4個、16進で
0x1006506a0: 0x00000001 0x00000000 0x00651a30 0x00000001

(lldb) memory read -c 2 -s 8 -f x $0     # 8バイト×2個
0x1006506a0: 0x0000000000000001 0x0000000100651a30

このバイト列は、第1節 で計算したレイアウトと1バイトの狂いもなく一致している:

• byte 0〜3 = 01 00 00 00 — value(1)
• byte 4〜7 = 00 00 00 00 — パディング。ソースコードに一切現れないのにメモリには実在する
• byte 8〜15 = 0x0000000100651a30 — b のアドレスそのもの。4バイト刻みの表示では 0x00651a30 と 0x00000001 に分けて見える(8バイトの値がリトルエンディアンで下位から並ぶ)

メモリダンプから、整数やポインタを含む構造体の配置を推定できる。ただし、この並びだけでstruct nodeと断定することはできない。命令のアクセス幅、参照するオフセット、ポインタの参照先も調べて仮説を検証する必要がある。パディングの値はゼロとは限らない。

この実測では、lldbで起動したときのコードのアドレスが同じであった。ASLRの扱いはデバッガの設定やOSに依存する。lldbでは settings show target.disable-aslr で設定を確認できる。動的に確保した領域のアドレスまで一定になる保証はない。

Q6. メモリダンプの byte 8〜15 にあった

0x0000000100651a30 は何か。

Q7. メモリダンプの byte 4〜7 が

0x00000000 だったのはなぜか。

5. 挿入: 2本の付け替え

a → b → c の a と b の間に新しいノード x(値99)を挿入する。配列なら後ろを全部ずらすが、リストで変えるのは 2つのnextである。

x->next = a->next;    // ① X の次を b へ(先に!)
a->next = x;          // ② a の次を X へ

順番が重要である。②を先に書くと a->next はすでに X を指しているので、その後の x->next = a->next は x->next = x — 自分自身を指すループになり、b以降へのリンクが失われる。ほかに有効なポインタがなければ、その領域を解放できなくなる。先にx->nextへ後続ノードへのポインタを保存し、その後でa->nextを更新する。

Q8. 挿入の2行はどの順で書くのが正しいか。

6. 削除: 「前のノード」を付け替える

削除も付け替えだが、落とし穴がある。a(1) → x(99) → b(2) → c(3) という列から b を消す場合、付け替えるべきは b の前のノード(x)の next である。

x->next = b->next;    // ① x の次を c へ(b を迂回させる)
free(b);              // ② bを解放する

うっかり「先頭の next」を付け替えるコードを書くと何が起きるか。a->next = b->next; としてみると:

初期:            1 2 3
99を挿入:        1 99 2 3
2を削除:         1 3        ← 99 が消えた!

挿入後の列では b の前は a ではなく x だった。a->next = b->next は「a の次」を c へ直接つなぎ替えるので、間のx(99)がリストの走査対象から外れる — ほかに有効なポインタがなく、領域を解放しなければメモリリークになる。削除対象の直前にあるノードは、宣言順ではなく現在のリストのリンクで決まる。

もう1つの順序の規則: free が先にならないこと。free(b) を先にすると b->next は解放後読み取り(UAF)になる。解放後の領域へのアクセスは未定義動作である。

Q9. 削除で付け替える next はどこか。

Q10.

free(b); の後に b->next を読むと何が起きているか。

7. 全ノードの解放

次のループは、各ノードを先頭から順に解放する。次のノードへのポインタの保存、現在のノードの解放、次のノードへの移動の順に処理する。

struct node *p = head;
while (p != NULL) {
    struct node *nx = p->next;   /* ① 次のノードへのポインタを保存してから */
    free(p);                     /* ② このノードを解放する */
    p = nx;                      /* ③ 保存した次へ進む */
}

①がないと、②の後の p->next は解放後読み取りになる。この実装では、次のノードへのポインタをfreeより前に保存することで、解放済み領域の読み取りを避ける。

もうひとつの定番の罠はループ条件にある:

while (p->next != NULL) { ... }   /* ← この条件だと最後のノードが解放されない */

この条件は、末尾のノードを指した時点で偽になる。つまり末尾の1個だけ free されずに残る — ごく小さなリークだが、この関数を何百万回も呼ぶプログラムでは積み重なる。このループでは、p != NULLを条件にする。pがNULLになるまで、現在のノードを解放する。空のリストでp->nextを評価すると、NULLポインタの参照になる点にも注意する。

Q11. 全解放ループで「次を保存してから free する」のはなぜか。

Q12. 空でないリストで

while (p->next != NULL) を全解放の条件にすると何が起きるか。

まとめ

連結リストは、次のノードへのポインタを持つ構造体から構成される。mallocでノードを確保し、nextを更新して挿入・削除を行う。次回は、p = p->nextに対応する機械語とレジスタの動作を確認する。

練習問題

1. 走査を for ではなく while で書き直す(両方書けるようにする)
2. 先頭への挿入 — new->next = head; head = new; を含む関数を書き、head がなぜ付け替わるのか言葉で説明する
3. 走査しながら value の合計を返す list_sum を書く
4. clang -g でビルドした自分のリストを lldb にかけ、先頭ノードのnextを読み、そのアドレスを使って2番目のノードを memory read で確認する。別々に確保したノード間の距離はsizeofから求められない
5. (挑戦) リストをその場で逆順にする(ポインタ3つ prev/cur/nx を使う古典パターン)

次回

p = p->next は機械語ではどうなるか — アセンブリ読解、レジスタ(register read)。その先はページテーブル(OS)と仮想→物理変換へ進む。