仙石浩明の日記

次のようなプログラム test.c について考える:

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>

struct test {
    int32_t len;
    int8_t buf[16];
};

int main(int argc, char *argv[]) {
    struct test *p = malloc(sizeof(struct test));
    int8_t buf[16];
    p->len = sizeof(p->buf);
    bzero(p->buf, p->len);
    printf("0x%lX-0x%lX => 0x%lX\n",
	   (long)p->buf, (long)p->buf+p->len-1, (long)buf);
    bcopy(p->buf, buf, p->len);
    free(p);
    return 0;
}

malloc(3) で確保した領域のうち、 16 byte を bcopy(3) でコピーするだけの極めて単純なプログラムであり、 特に問題はないように見える。

ところが memory debugging tool Valgrind を使って検証してみると、 x86_64 Linux だと次のようなエラーが出てしまう。

sag16:/home/sengoku/tmp % cc -O -Wall test.c
sag16:/home/sengoku/tmp % valgrind ./a.out
==19008== Memcheck, a memory error detector.
==19008== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==19008== Using LibVEX rev 1658, a library for dynamic binary translation.
==19008== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==19008== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation framework.
==19008== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==19008== For more details, rerun with: -v
==19008== 
0x4D5C034-0x4D5C043 => 0x7FF000750
==19008== Invalid read of size 8
==19008==    at 0x4B9326B: (within /lib/libc-2.3.6.so)
==19008==    by 0x4B92C06: bcopy (in /lib/libc-2.3.6.so)
==19008==    by 0x4005BD: main (in /home/sengoku/tmp/a.out)
==19008==  Address 0x4D5C040 is 16 bytes inside a block of size 20 alloc'd
==19008==    at 0x4A1B858: malloc (vg_replace_malloc.c:149)
==19008==    by 0x400574: main (in /home/sengoku/tmp/a.out)
==19008== 
==19008== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 8 from 1)
==19008== malloc/free: in use at exit: 0 bytes in 0 blocks.
==19008== malloc/free: 1 allocs, 1 frees, 20 bytes allocated.
==19008== For counts of detected errors, rerun with: -v
==19008== All heap blocks were freed -- no leaks are possible.

「Invalid read of size 8」、 すなわちアクセスすべきではないメモリを、 64bit (8 byte) 読み込み命令で読んだというエラー。

test.c で読み込みを行なう可能性があるところと言えば、 「bcopy(p->buf, buf, p->len);」の部分だけであり、 その範囲は printf で表示しているように、 0x4D5C034 番地から 0x4D5C043 番地までの 16 byte である。

ところが、Valgrind 曰く:

Address 0x4D5C040 is 16 bytes inside a block of size 20 alloc'd

ちょっと英語の意味が取りにくい (私の英語力が低いだけ? ^^;) が、 つまり「malloc で確保した 20 byte の領域のうち、 先頭から数えて 16 byte 目 (先頭は 0 byte 目と数える) が 0x4D5C040 番地であり、 この番地に対してメモリ読み込みが行なわれた」 という意味である (「16 byte 目」なら 「16 bytes」でなくて「16th byte」のような...?)。

すなわち、 「20 byte の領域のうち 16 byte 目」というのは残り 4 byte であり、 あと 4 byte コピーすればいいのにもかかわらず、 64bit 読み込み命令を使って 8 byte いっぺんに読んでしまっているから、 malloc で確保した領域の外をアクセスしてしまう、というわけ。

結果として 4 byte 無駄に読んでしまっている (実はコピー開始位置も 4 byte 前から行なうので、計 8 byte 余計に読み込んでいる) わけだが、 CPU にとって一番高速にコピーできる単位が (64bit 境界に合わせた) 64bit 読み書きだから、 bcopy の実装がこのようになっているのだろう。

より正確に言えば、 bcopy は 16 byte 以上のコピーを行なう場合は コピー開始位置手前の 64bit 境界 (alignment) の番地から 64bit ずつコピーし、 16 byte 未満の場合は byte 単位でコピーする。 test.c では、 コピー開始位置 p->buf が (直前のメンバが int32_t なので) 64bit 境界に一致しておらず、 しかもコピーする byte 数 p->len が 16 byte (= 64bit の倍数) なので、 16 byte 以上のコピーかつコピー終了位置も 64bit 境界に一致していない、 というのがミソである。

したがって 32bit な x86 Linux の場合であれば 32bit 単位でコピーを行なうので、 test.c ではこのようなエラーは起きない。 もちろん、64bit な x86_64 Linux で Valgrind がエラーを出すからといって、 bcopy の x86_64 における実装に問題がある、というわけではない。 Valgrind は、 あくまでバグの「可能性」を指摘するだけであって、 malloc で確保した領域の外へのアクセスでも、 それが意図的なものであれば (メモリ保護違反などでない限り) 何の問題もない。

分かってみれば単純な話なのであるが、 Valgrind のメッセージ「16 bytes inside a block」の意味が把握できなかった私は、 glibc の bcopy のソースを読んで 64bit 単位でコピーを行なっていることを知り、 4 byte の領域外読み込みが行なわれることを理解して初めて、 Valgrind のメッセージの意味が分かったという、 本末転倒な体験をした (^^;)。

ちなみに、 もちろん最初から上記のようなテストプログラムを Valgrind で チェックしようと思ったわけではなく、 「struct test」構造体は実際には次のような SockAddr 構造体であり、 saDup 関数にて malloc した SockAddr 構造体を doconnect 関数で bcopy する処理になっていて、 元ネタは拙作 stone である。

typedef struct {
    socklen_t len;
    struct sockaddr addr;
} SockAddr;
#define SockAddrBaseSize	((int)&((SockAddr*)NULL)->addr)
...

SockAddr *saDup(struct sockaddr *sa, socklen_t salen) {
    SockAddr *ret = malloc(SockAddrBaseSize + salen);
...

int doconnect(Pair *p1, struct sockaddr *sa, socklen_t salen) {
    struct sockaddr_storage ss;
    struct sockaddr *dst = (struct sockaddr*)&ss;	/* destination */
...
    bcopy(sa, dst, salen);
...

stone ML にて、 Valgrind で検証したらエラーが出た、という報告を頂いて (_O_) 以上のような調査を行なった次第。 bcopy に与えた引数に問題はなく、 どうしてこれが 「Invalid read of size 8」 エラーを引き起こすのか謎だった。 結果的には stone には問題はなく、 修正の必要もないことが判明したわけであるが、 今まで使っていなかった Valgrind を使ってみるいいきっかけになった。 実を言うと 64bit Linux を (プログラミングのレベルで) 使ったのも、 今回が初めてだったりする (^^;)。

FON ソーシャルルータ La Fonera のファームウェアは Linux であり、 RedBoot ブートローダ から起動される。 デフォルト状態の La Fonera では、 以下のように RedBoot がフラッシュメモリから Linux カーネルをロードして 自動起動する設定になっている。

== Executing boot script in 1.000 seconds - enter ^C to abort
RedBoot> fis load -l vmlinux.bin.l7
Image loaded from 0x80041000-0x801ba000
RedBoot> exec
Now booting linux kernel:
 Base address 0x80030000 Entry 0x80041000
 Cmdline : 
(以下略)

fis (Flash Image System) は、 フラッシュメモリの読み書きを行なうためのコマンドである。

「fis load -l vmlinux.bin.l7」を実行することにより、 フラッシュメモリ内の「vmlinux.bin.l7」と名前をつけられた区画の内容を RAM へコピー (つまり load) する。

ところが、 fis load コマンドのマニュアルには、 「-l」オプションの記述がない。

Synopsis
fis load [-b load address] [-c ] [-d ] [name]

にもかかわらず、 La Fonera の RedBoot で fis コマンドのヘルプを表示させると、 「-l」オプションが指定できることが分かる。

RedBoot> fis help
*** invalid 'fis' command: unrecognized command
Usage:
  fis create -b <mem_base> -l <image_length> [-s <data_length>]
      [-f <flash_addr>] [-e <entry_point>] [-r <ram_addr>] [-n] <name>
  fis delete name
  fis erase -f <flash_addr> -l <length>
  fis free
  fis init [-f]
  fis list [-c] [-d]
  fis load [-d] [-l] [-b <memory_load_address>] [-c] name    ← コレ
  fis write -f <flash_addr> -b <mem_base> -l <image_length>

一体この「-l」オプションとは何なのか？

というか、 そもそも「vmlinux.bin.l7」という名前の見慣れない拡張子「L7」とは何なのか？
(L7 というと Layer 7 くらいしか思いつかない... ^^;)

というわけで調べてみた。

「vmlinux.bin.l7」の内容と、 「fis load -l」コマンドによって 0x80041000 番地にロードされた内容を見比べると、 「vmlinux.bin.l7」はデータ圧縮を行なった形式であるように見える。 おそらく「-l」オプションは、 フラッシュメモリ上の圧縮データを展開して RAM へロードするための オプションなのだろう。 圧縮データを展開するオプションとして「fis load」コマンドには、 すでに「-d」(gzip 圧縮データを展開) があるにもかかわらず、 何故わざわざ gzip 以外の圧縮形式を使っているのか謎であるが、 おそらくはより圧縮率の高い圧縮形式を使いたかったのだろう。

gzip より圧縮率が高い圧縮形式で「7」といえば 「7-Zip」、 という (安直な ^^;) 連想をもとに、 とりあえず手元にあった lzma コマンドで展開を試みてみる。

% lzma d vmlinux.bin.l7 vmlinux.bin

LZMA 4.43 Copyright (c) 1999-2006 Igor Pavlov  2006-06-04

ありゃ、あっさり展開できてしまった。 ちょっと拍子抜け。

展開した vmlinux.bin を TFTP サーバに置いて、 La Fonera に読み込ませて起動してみる:

RedBoot> load -r -b 0x80041000 vmlinux.bin
Using default protocol (TFTP)
Raw file loaded 0x80041000-0x8029aa37, assumed entry at 0x80041000
RedBoot> exec
Now booting linux kernel:
 Base address 0x80030000 Entry 0x80041000
 Cmdline :
(以下略)

これで、TFTP サーバに置いた任意のカーネルを La Fonera で起動することが できるようになった。 フラッシュメモリに書込む必要がないので手軽にカーネルの入れ替えができる。

ちなみに、 「vmlinux.bin」は RAM 上にコピーして即実行 (RedBoot の exec コマンド) 可能であることから、 raw binary 形式 (つまりオブジェクトファイルから、 シンボル情報やリロケーション情報を取り除いたもの) であることが分かる。 つまり、「vmlinux.bin」の拡張子「bin」は「raw binary」の意味なのだろう。 vmlinux から raw binary 形式のファイル vmlinux.bin を得るには、 次のように objcopy コマンドを実行すればよい。

% mips-linux-uclibc-objcopy -O binary vmlinux vmlinux.bin