目次: Arduino
最近、M5Stamp C3 + Raspberry Piを組み合わせて的あてゲームを作っています。Bluetooth通信クライアント側のLinuxマシンにRaspberry Pi 3 model Bを使っているものの、販売終了につき新品が手に入りません。今は1台あれば良いので困りませんが、後でN増しするとき困りそうです。
Linuxマシン側の要件を挙げると、
まず値段的にx86のノートPCやNUCは購入候補から外れます(中古品でも厳しい)。ARMのSBCですと、FRIENDLY ELECのNanoPi R5系(Rockcihp RK3568B, Cortex-A55 x 4)か、OKDO/Radxa ROCK 3 model C 1GB版(Rockchip RK3566, Cortex-A55 x 4)がちょうど良さそうでした。
NanoPiとROCK 3はどちらでも良かったのですが、RSコンポーネンツで容易に購入できるROCK 3 model C 1GB版に決めました。
ROCK 3 model CはRaspberry Pi 3 model Bを置き換えるにふさわしい製品だと思いますが、私の使い方だと1点だけ問題があって、Javaの画面描画が致命的に遅いです。5秒に1回くらいしか描画されません。このままでは使いたい目的に合いません。
最初にGPUが有効になっているか確認です。GPU使用率を/sys/devices/platform/fed60000.gpu/utilizationを見ると、無負荷のときは0、アプリ起動時で20くらいでGPUは動いています。問題なさそうです。むしろ暇しているというか余裕すらありそうです。Javaのライブラリ系orアプリ実装の問題でしょう。
次にJavaのライブラリ系を確認です。現在、画面描画のダブルバッファリングに使っているのはBufferStrategyで、BufferStrategyが返すVolatileImageのisAccelerated()はTrueを返します。OpenGLによるHW描画が使われているようです。これも問題なさそうです。残るはアプリ実装の問題ですね。
余談ですが下記のようにGraphics2D経由で確認すると、
((Graphics2D)strategy.getDrawGraphics()).getDeviceConfiguration().getImageCapabilities().isAccelerated()
なぜかisAccelerated()がFalseになります。良くわからん動きです。
タイトルの通りですが、アプリ実装が原因でした。コードでいえば下記の部分です。
Graphics2D g2;
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
g2.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_ON);
図形描画とテキスト描画のアンチエイリアスをONにして使っていましたが、このうち図形描画のアンチエイリアスをONにすると著しく描画速度が下がることがわかりました。Raspberry Pi 3 model Bは双方のアンチエイリアスをONにしても特に問題がなかったため、気づくまで結構手間取りました。
図形描画のアンチエイリアスは今のところ見た目にさほど影響がないので、OFFにしました。テキスト描画のアンチエイリアスも描画速度に多少影響ありますが、OFFにすると見た目が悪くなりすぎるので、ONのまま使います。
問題の解決はしていませんが、回避できたのは良かったです。勢いで3つも買ってしまったROCK 3 model Cの不良在庫化を避けられました……。
目次: GCC
過去の日記(2021年3月13日の日記参照)にプログラムがバグっていて未定義動作だ(つまりGCCのせいじゃない)とコメントいただいたので、C11規格を眺めていました。
C11 committee draft(N1570) 6.7.3 Type qualifiersの6に、volatileとnon-volatileを併用したときの未定義動作の記述がありました。
6.7.3 Type qualifiers ... 6 If an attempt is made to modify an object defined with a const-qualified type through use of an lvalue with non-const-qualified type, the behavior is undefined. If an attempt is made to refer to an object defined with a volatile-qualified type through use of an lvalue with non-volatile-qualified type, the behavior is undefined. 133) 133) This applies to those objects that behave as if they were defined with qualified types, even if they are never actually defined as objects in the program (such as an object at a memory-mapped input/output address). (ざっくり訳) const-qualified型で定義したオブジェクトをnon-const-qualified型の左辺値(lvalue)を使用して変更した場合、 動作は未定義です。volatile-qualified型で定義したオブジェクトを、non-volatile-qualified型の左辺値で参照した場合、 動作は未定義です。 133) たとえプログラム内でオブジェクトとして定義されていなくても、これ(注: 上記の6のこと)は修飾された型で定義されたように 振る舞うオブジェクト(メモリマップされたI/Oアドレスにあるオブジェクトなど)に適用されます。
未定義動作ならmemmoveやmemcopyに何が起きても不思議ではないですね。C言語難しいわ……。
目次: Linux
Raspberry Pi 3 Model B (以降RasPi 3B)のHDMI出力の解像度はFull HDがデフォルト設定です。今日日のディスプレイで困ることはほぼありませんが、古いアスペクト比4:3のディスプレイなど、Full HD以外の解像度で出力してほしいときが稀にあります。
RasPi 3Bに限りませんけど、X Window Systemはxrandrコマンドで解像度を手軽に変更できます。しかし解像度の設定は保存されず、セッションを終了したり再起動すると元のFull HD出力に戻ります。まあ、これはこれで誤った設定のまま固定されないというありがたい面もあるものの、普通は再起動後も解像度を維持してほしいです。
調べるとX Window Systemの設定ファイルを変更するか、autorandrコマンドで解像度を維持できるみたいです(autorandrのソースコード)。例として1024x768 60Hzの解像度で維持するやり方を挙げます。
$ apt-get install autorandr $ xrandr -s 1024x768 --rate 60 $ autorandr --save (profile名)
設定は~/.config/autorandr/(profile名)/というディレクトリに保存されます。
起動時に解像度を変更している方法が気になったので調べると、XDG autostart(Desktop Application Autostart Specification)を使って実現していました。
Linuxのデスクトップ環境は実装ごとに自動起動の方法が違いますが、XDG autostartは多数のデスクトップ環境が対応している自動起動の仕組みのようです。私が使っている64bit版Raspberry Pi OSはデスクトップ環境としてLXDE (Lightweight X11 Desktop Environment)を採用していて、LXDEもXDG autostartに対応しています。
XDG autostartはデスクトップ表示の際に/etc/xdg/autostart/ディレクトリの下の設定を全部実行します。autorandrの設定は/etc/xdg/autostart/autorandr.desktopにありました。
[Desktop Entry] Name=Autorandr Comment=Automatically select a display configuration based on connected devices Type=Application Exec=/usr/bin/autorandr -c --default default X-GNOME-Autostart-Phase=Initialization
実行されるコマンドラインのうちオプション-cはchangeの意味で、最初に見つけたprofileの解像度に変更します。オプション--defaultはdefaultという名のprofileを使うように変更する指令らしいのですが、効き目が良くわかりません。
もし複数のprofileが存在していた場合にどれが選ばれるのか気になるので、デバッグオプションを付けて実行してみましょう。
$ autorandr -c --default default --debug fullhd (detected) (1st match) (current) xga (detected) (2nd match) | Differences between the two profiles: | [Output HDMI-1] Option --mode (= `1920x1080') is `1024x768' in the new configuration \- Config already loaded $ autorandr -l xga $ autorandr -c --default default --debug xga (detected) (1st match) (current) fullhd (detected) (2nd match) | Differences between the two profiles: | [Output HDMI-1] Option --mode (= `1024x768') is `1920x1080' in the new configuration \- Config already loaded
こんな動作をしました。最後に利用もしくは保存したprofileが使われるみたいですね。
目次: ベンチマーク
前回(2024年2月27日の日記参照)はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、バイナリサイズを極限まで削るためのアイデアをご紹介しました。
今回はバイナリ実装の説明を紹介したいと思います。
今回使用する100万回のHello, World!を呼ぶ命令列と処理の流れを説明します。エントリアドレスは0x983cb004なので、一番上の行から実行開始します。
983cb004: b9 40 42 0f 00 mov $0xf4240,%ecx 983cb009: 6a 01 push $0x1 983cb00b: 58 pop %rax 983cb00c: 6a 0e push $0xe 983cb00e: 5a pop %rdx 983cb00f: a9 02 00 3e 00 test $0x3e0002,%eax 983cb014: 89 c7 mov %eax,%edi 983cb016: eb 50 jmp 983cb068 <_start+0x68> 983cb028: "Hello, World!\n" 983cb060: 0f 05 syscall 983cb062: 59 pop %rcx 983cb063: e2 a4 loop 983cb009 <_start+0x9> ----- (★1)loop命令の条件に一致せず、983cb065に進んだ時に見える命令列 983cb065: 25 00 00 be 28 and $0x28be0000,%eax 983cb06a: b0 3c mov $0x3c,%al 983cb06c: 98 cwtl 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60> ----- (★2)983cb068に飛んだ時に見える命令列 983cb068: be 28 b0 3c 98 mov $0x983cb028,%esi 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60>
まず0x983cb004〜0x983cb016まで実行して、ジャンプ命令で0x983cb068に飛びます。上の図でいう(★2)の方です。
ループ100万回が終了してrcxレジスタが0になるとloop命令の次のアドレス983cb065に進みます。eaxレジスタに0x3cを入れてsyscall(exitシステムコールに相当する)するので、プログラムが終了します。
この命令列の凄いところはand命令とmov命令の重ね合わせです。アドレス0x983cb065から見たときと、アドレス0x983cb068から見たときで命令列の意味が大きく変わります。図示するとこんな感じです。
and mov cwtl push jmp | | | | | <------------> <---> <> <> <---> : アドレス983cb065から見たときの解釈 25 00 00 be 28 b0 3c 98 51 eb f0 <------------> <> <---> : アドレス983cb068から見たときの解釈 | | | mov push jmp
この工夫によってmovとjmpの合計7バイトを重ね合わせることができていて、結果112バイトにきっちり収まっています。
$ hexdump -C 112byte.out 00000000 7f 45 4c 46 b9 40 42 0f 00 6a 01 58 6a 0e 5a a9 |.ELF.@B..j.Xj.Z.| 00000010 02 00 3e 00 89 c7 eb 50 04 b0 3c 98 00 00 00 00 |..>....P..<.....| 00000020 38 00 00 00 00 00 00 00 48 65 6c 6c 6f 2c 20 57 |8.......Hello, W| 00000030 6f 72 6c 64 21 0a 38 00 01 00 00 00 05 00 00 00 |orld!.8.........| 00000040 00 00 00 00 00 00 00 00 00 b0 3c 98 00 00 00 00 |..........<.....| 00000050 00 b0 3c 98 00 00 00 00 0f 05 59 e2 a4 25 00 00 |..<.......Y..%..| 00000060 0f 05 59 e2 a4 25 00 00 be 28 b0 3c 98 51 eb f0 |..Y..%...(.<.Q..| 00000070 $ ./112byte.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./112byte.out | wc 1000000 2000000 14000000 $ ./112byte.out > /dev/null
最終的なバイナリはこんな感じです。動作もOKです。
ループ終了後exitシステムコールを呼ぶとき、アドレス983cb06aのmov命令にて0x3c(exitシステムコールを表す番号)をalレジスタに入れてsyscall命令を実行します。もしこのmov命令のみだと、writeシステムコールがエラーを返してeaxレジスタが負の値になっていると問題が起きます。alレジスタを0x3cに書き換えても上位ビットが0ではないため、eaxレジスタとして見たとき値が0x3cになりません。よってexitシステムコールが呼ばれず終了しません。
今回の112バイト版は前後のand命令とcwtl命令によってこの問題を解決しています。loop命令を通過した後の命令列を再掲します。
983cb065: 25 00 00 be 28 and $0x28be0000,%eax 983cb06a: b0 3c mov $0x3c,%al 983cb06c: 98 cwtl 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60>
ポイントは先頭の2命令です、簡単に解説します。
もしwriteシステムコールがエラーを返してeaxレジスタが負の値になっていたとしても、and命令がaxレジスタ相当の下位16ビットを0クリアし、cwtlで符号拡張するので必ずeaxレジスタは0x3cになる仕組みです。
この手のコードゴルフではエラー処理まで考えないことが多いですが、きれいに解決されています。ちなみに私はcwtl命令を初めて知りました。こんな命令あるんだ……。
目次: ベンチマーク
前回(2024年2月26日の日記参照)はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対して、バイナリサイズをどこまで削れるかに挑戦しました。結果120バイトのバイナリとなりました。
今回は削減の限界値と思われる値まで達成したので、その内容を紹介したいと思います。空き地の開拓は私ですが、アセンブラの短縮に関しては私ではなくhdkさん(hdkのページ)がほぼやってくれました。結構難しいので、わかるように説明できているか怪しいです……。
正常に動作するELF形式の実行ファイルには、ELFヘッダ(64バイト)とプログラムヘッダ(56バイト)が必要です。120バイト必要に見えますが、2つのヘッダは破綻しない範囲で重ねて良いです。今のところ112バイトが最小サイズだと思われます。
前回紹介した通り、ELFヘッダには適当な値を入れるとエラーになって動かなくなる部分があります。プログラムヘッダも同様に制約があり、先頭のp_typeとp_flags(01 00 00 00 05 00 00 00)は変更できません。そのあとに続くp_offsetも上位バイトは変更できず、p_vaddr = p_paddr、p_filesz = p_memszでなければなりません。結構厳しいです。
これらの条件を満たせるのはe_phnum, e_shentsize, e_shnum, e_shstrndx(計8バイト)とp_type, p_flags(計8バイト)を重ねることだけだと思われます。単純な合計サイズから8バイト減った64 + 56 - 8 = 112バイトが最小サイズのはず。もし間違っていたら教えてください。私が喜びます。
前回は見落としましたが、プログラムヘッダ中に命令列を置ける空き地が1つ残っていました。p_fileszとp_memsz(どちらも8バイト)です。あまりに大きな値にするとエラーで動かなくなりますが、6バイトくらいなら何を書いても大丈夫そうです。
注意点としてはp_fileszとp_memszを同じ値にしないとエラーになることです。両方書き換えますが実行に使うのはどちらか片方だけとなるでしょう。
RISC系のCPUを使う人からすると信じがたい動きですが、x86 CPUは命令のアラインメントがなく「命令の途中」にジャンプしても良いです。例を示しましょう。
0000: be 28 01 b0 3c: mov $0x3cb00128, %esi この命令の4バイト目(アドレス3)にジャンプすると 0003: b0 3c: mov $0x3c, %al という命令に見えるので、継続して実行可能。
もし命令の一部が有効な命令として解釈可能ならそのまま実行を続けられます。x86 CPUの無茶苦茶な仕様には驚きですが、今回はこの動きが役立ちます。
ELFヘッダのe_identの後半(アドレス: 0x04〜0x0f、12バイト)とe_version(アドレス: 0x14〜0x17、4バイト)の間には、e_type, e_machineという書き換えてはいけない4バイトの情報があります。単純に実装するとe_identの最後に4バイトジャンプ(eb 04)を置いて飛ばせば良いです。
しかし上記のようにアドレス0x000fをtest命令(a9)に置き換えますと、後続の4バイトと合わせて1命令(a9 02 00 3e 00: test $0x3e0002, %eax)とみなせます。test命令はフラグレジスタ以外には影響を及ぼさないので、a9 02 00 3e 00は実行されるものの何も効力を発揮しません。
ジャンプ命令2バイトからtest命令の先頭1バイトのみで済みますので、空き地が1バイト増加します。test命令に変更する代償はフラグレジスタの内容が破壊されることです。例えば条件分岐命令の直前などでtest命令を使うと、分岐の結果が変わる可能性があります。
100万回のループを行うときは、ebxレジスタなどcallee-saveレジスタ(関数呼び出しで値が壊れないレジスタ)に1,000,000を入れ、デクリメントし(ff cb: dec %ebx)、条件不一致ならループの先頭にジャンプ(75 xx: jne +-7bit幅ショートジャンプ)する、2命令、合計4バイトで実現するのが普通だと思います。
実はx86_64にはloop命令といってdec %ecxとjne xxを実行する命令があります。サイズは2バイト(e2 xx: loop +-7bit幅ショートループ)です。ただしecxレジスタはcallee-savedではないため、関数呼び出しやsyscallで内容が壊れます。必ずecxレジスタの保存(51: push %rcx)と復帰(59: pop %ecx)を伴うため合計サイズは4バイトで変わりません。
それなら置き換える意味がないのでは?と思うかもしれませんが、同じ4バイトでも2バイト命令2つ(dec, jne)と1バイト命令2つ+2バイト命令1つ(push, pop, loop)を比べると、後者の方が部品が多くてより柔軟に配置できるのです。
もう1つ良い点はdec命令とjne命令は近くに配置しないといけない制約(フラグを壊す算術命令やtest命令を間に入れると動かなくなるから)がありますが、push/pop命令はloop命令から多少離れても問題ありません。これもloopの方が柔軟に配置できる理由です。
続きはまた明日書きます。
目次: ベンチマーク
前回(2024年2月25日の日記参照)はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、アセンブラというかほぼバイナリ直書きのC言語で挑戦しました。その後、バイナリサイズを削って遊んでみたところgccのみで840バイト、stripありで520バイトとなり、バイナリでも1000バイト以下を達成しました。
今回はどこまでバイナリのサイズを切り詰められるか試してみたいと思います。ツール頼みだとこれ以上削れないと思うのでバイナリエディタで削っていきます。
前回の私のバイナリ実装はかなり適当だったので猛者に叩きなおしてもらいました。変化点としては、
といったところです。
const char _start[] __attribute__((section(".text"))) = {
0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
0x6a, 0x01, //push 0x1
0x58, //pop rax
0x89, 0xc7, //mov eax,edi
0x6a, 0x0e, //push 0xe
0x5a, //pop rdx
0xbe, 0x1c, 0x01, 0x40, 0x00, //mov 0x4011c, esi
0x0f, 0x05, //syscall
0xff, 0xcb, //dec ebx
0x75, 0xed, //jne -> push 0x1
0x6a, 0x3c, //push 0x3c
0xeb, 0xeb, //jmp -> pop rax
'H', 'e', 'l', 'l', 'o', ',', ' ',
'W', 'o', 'r', 'l', 'd', '!', '\n',
};
この改良の時点で520→512バイト(8バイト減)に改善します。素晴らしい〜。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c /tmp/cczsMtLk.s: Assembler messages: /tmp/cczsMtLk.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 832 2月 25 13:47 a.out $ strip -s a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 512 2月 25 13:47 a.out ★8バイト改善 $ objdump -DrS a.out (略) 0000000000400100 <.text>: 400100: bb 40 42 0f 00 mov $0xf4240,%ebx 400105: 6a 01 push $0x1 400107: 58 pop %rax 400108: 89 c7 mov %eax,%edi 40010a: 6a 0e push $0xe 40010c: 5a pop %rdx 40010d: be 1c 01 40 00 mov $0x40011c,%esi 400112: 0f 05 syscall 400114: ff cb dec %ebx 400116: 75 ed jne 0x400105 400118: 6a 3c push $0x3c 40011a: eb eb jmp 0x400107 ★ここから下はHello, World!の文字列なので命令列としては無意味 40011c: 48 rex.W 40011d: 65 6c gs insb (%dx),%es:(%rdi) 40011f: 6c insb (%dx),%es:(%rdi) 400120: 6f outsl %ds:(%rsi),(%dx) 400121: 2c 20 sub $0x20,%al 400123: 57 push %rdi 400124: 6f outsl %ds:(%rsi),(%dx) 400125: 72 6c jb 0x400193 400127: 64 21 0a and %ecx,%fs:(%rdx) $ ./a.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./a.out | wc 1000000 2000000 14000000
動作確認もできました。バイナリはこんな感じです。
$ hexdump -C remove_prg_section_org.out 00000000 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 |.ELF............| 00000010 02 00 3e 00 01 00 00 00 00 01 40 00 00 00 00 00 |..>.......@.....| 00000020 40 00 00 00 00 00 00 00 40 01 00 00 00 00 00 00 |@.......@.......| 00000030 00 00 00 00 40 00 38 00 03 00 40 00 03 00 02 00 |....@.8...@.....| 00000040 01 00 00 00 04 00 00 00 00 00 00 00 00 00 00 00 |................| 00000050 00 00 40 00 00 00 00 00 00 f0 3f 00 00 00 00 00 |..@.......?.....| 00000060 e8 00 00 00 00 00 00 00 e8 00 00 00 00 00 00 00 |................| 00000070 00 10 00 00 00 00 00 00 01 00 00 00 05 00 00 00 |................| 00000080 00 01 00 00 00 00 00 00 00 01 40 00 00 00 00 00 |..........@.....| 00000090 00 01 40 00 00 00 00 00 2a 00 00 00 00 00 00 00 |..@.....*.......| 000000a0 2a 00 00 00 00 00 00 00 00 10 00 00 00 00 00 00 |*...............| 000000b0 51 e5 74 64 06 00 00 00 00 00 00 00 00 00 00 00 |Q.td............| 000000c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 000000e0 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 000000f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000100 bb 40 42 0f 00 6a 01 58 89 c7 6a 0e 5a be 1c 01 |.@B..j.X..j.Z...| 00000110 40 00 0f 05 ff cb 75 ed 6a 3c eb eb 48 65 6c 6c |@.....u.j<..Hell| 00000120 6f 2c 20 57 6f 72 6c 64 21 0a 00 2e 73 68 73 74 |o, World!...shst| 00000130 72 74 61 62 00 2e 74 65 78 74 00 00 00 00 00 00 |rtab..text......| 00000140 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00000180 0b 00 00 00 01 00 00 00 06 00 00 00 00 00 00 00 |................| 00000190 00 01 40 00 00 00 00 00 00 01 00 00 00 00 00 00 |..@.............| 000001a0 2a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |*...............| 000001b0 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ...............| 000001c0 01 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 |................| 000001d0 00 00 00 00 00 00 00 00 2a 01 00 00 00 00 00 00 |........*.......| 000001e0 11 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 000001f0 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000200
サイズは小さいですが0データの羅列が目立ちます。削れそうな気がしてきませんか?
大物から削りましょう。プログラムヘッダがなぜか3つありますが2つ不要、セクションヘッダは実行には不要、セクションヘッダ削除に伴って.shstrtabも不要です。
プログラムヘッダ: タイプ オフセット 仮想Addr 物理Addr ファイルサイズ メモリサイズ フラグ 整列 LOAD 0x0000000000000000 0x0000000000400000 0x00000000003ff000 ★いらない 0x00000000000000e8 0x00000000000000e8 R 0x1000 LOAD 0x0000000000000100 0x0000000000400100 0x0000000000400100 0x000000000000002a 0x000000000000002a R E 0x1000 GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000 ★いらない 0x0000000000000000 0x0000000000000000 RW 0x10
削除データの位置は下記の図の通りです。
削除するデータ(プログラムヘッダ、セクションヘッダなど)の位置
単純に削除すると.textセクションの位置とヘッダに記載されているアドレスがズレて動かなくなりますから、
上記の値を調整します。調整後のバイナリが下記です。
$ ls -la remove_prg_section.out -rwxr-xr-x 1 katsuhiro suzuki 162 2月 25 14:05 remove_prg_section.out $ hexdump -C remove_prg_section.out 00000000 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 |.ELF............| ★ELFヘッダ 00000010 02 00 3e 00 01 00 00 00 78 00 40 00 00 00 00 00 |..>.....x.@.....| 00000020 40 00 00 00 00 00 00 00 40 01 00 00 00 00 00 00 |@.......@.......| 00000030 00 00 00 00 40 00 38 00 01 00 40 00 03 00 02 00 |....@.8...@.....| 00000040 01 00 00 00 05 00 00 00 60 00 00 00 00 00 00 00 |........`.......| ★プログラムヘッダ 00000050 60 00 40 00 00 00 00 00 60 00 40 00 00 00 00 00 |`.@.....`.@.....| 00000060 40 00 00 00 00 00 00 00 40 00 00 00 00 00 00 00 |@.......@.......| 00000070 00 10 00 00 00 00 00 00 bb 40 42 0f 00 6a 01 58 |.........@B..j.X| ★0x78〜: 実行する命令列 00000080 89 c7 6a 0e 5a be 94 00 40 00 0f 05 ff cb 75 ed |..j.Z...@.....u.| 00000090 6a 3c eb eb 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 |j<..Hello, World| 000000a0 21 0a |!.| 000000a2
0データの羅列が減ってだいぶスリム化しました。サイズは162バイトです。
ELFヘッダには色々な値が並んでいますが、実行ファイルを実行(execveシステムコール)するときに全ての値をチェックしているわけではありません。これを逆手にとってELFヘッダに実行命令列やデータを詰め込むことができます。図で示した黄色い部分以外は好き勝手に変えて大丈夫です。
最初の空き地はe_identの後半(アドレス: 0x04〜0x0f、12バイト)とe_version(アドレス: 0x14〜0x17、4バイト)です。実行バイナリの先頭4命令、10バイト分、そのあとの2バイト分を入れます。各領域の終端2バイトはジャンプ命令に使います。そうしないと命令列ではないところまで実行してクラッシュするからからです。
★e_identに入れる分 400100: bb 40 42 0f 00 mov $0xf4240,%ebx 400105: 6a 01 push $0x1 400107: 58 pop %rax 400108: 89 c7 mov %eax,%edi ★e_versionに入れる分 40010a: 6a 0e push $0xe
次の空き地はe_shoff, e_flags, e_ehsize(アドレス: 0x28〜0x35、14バイト)です。ちょうど"Hello, World!\n"と同じ長さなので文字列を置きます。
最後の空き地はELFヘッダの終端、e_shentsize, e_shnum, e_shstrndx(アドレス: 0x3a〜0x3f、6バイト)です。ここは命令列を置くよりe_phnumの値とプログラムヘッダの先頭p_typeも値が0x01であることを利用して、プログラムヘッダを8バイト手前にずらした方が良いでしょう。命令列を置くとジャンプ命令分を除いて、4バイトしか改善できないからです。
プログラムヘッダの方は空き地はほぼなく、ヘッダ終端のp_align(8バイト)だけ変更OKでした。ここにも命令列を置きましょう。
最後にアドレスを調整するとこんなバイナリです。120バイトになりました。当然、実行できて100万回のHello, World!を出力します。
$ hexdump -C overwrap_elfh.out 00000000 7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04 |.ELF.@B..j.X....| 00000010 02 00 3e 00 6a 0e eb 50 04 00 40 00 00 00 00 00 |..>.j..P..@.....| 00000020 38 00 00 00 00 00 00 00 48 65 6c 6c 6f 2c 20 57 |8.......Hello, W| 00000030 6f 72 6c 64 21 0a 38 00 01 00 00 00 05 00 00 00 |orld!.8.........| 00000040 60 00 00 00 00 00 00 00 60 00 40 00 00 00 00 00 |`.......`.@.....| 00000050 60 00 40 00 00 00 00 00 30 00 00 00 00 00 00 00 |`.@.....0.......| 00000060 30 00 00 00 00 00 00 00 5a be 28 00 40 00 0f 05 |0.......Z.(.@...| 00000070 ff cb 75 95 6a 3c eb 93 |..u.j<..| 00000078 $ ./overwrap_elfh.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./overwrap_elfh.out | wc 1000000 2000000 14000000
あくまでもこのバイナリは私が使っているLinux kernel 6.1系のチェックを掻い潜って実行できるだけ、です。gdbは実行ファイルとして認識してくれませんし、readelfも大量のエラーを出します。将来のLinuxカーネルでも実行できなくなる可能性があります。
$ gdb ./remove_elf.out GNU gdb (Debian 13.1-3) 13.1 (略) "(略)/./remove_elf.out": not in executable format: file format not recognized (gdb) $ readelf -a remove_elf.out ELF ヘッダ: マジック: 7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04 クラス: <不明: bb> データ: <不明: 40> Version: 66 <unknown> OS/ABI: AROS ABI バージョン: 0 型: EXEC (実行可能ファイル) マシン: Advanced Micro Devices X86-64 バージョン: 0x50eb0e6a エントリポイントアドレス: 0x400004 プログラムヘッダ始点: 0 (バイト) セクションヘッダ始点: 56 (バイト) フラグ: 0x0 Size of this header: 25928 (bytes) Size of program headers: 27756 (bytes) Number of program headers: 11375 Size of section headers: 22304 (bytes) Number of section headers: 29295 Section header string table index: 25708 readelf: 警告: The e_shentsize field in the ELF header is larger than the size of an ELF section header readelf: エラー: Reading 653395680 bytes extends past end of file for セクションヘッダ readelf: エラー: セクションヘッダが利用できません! readelf: エラー: Too many program headers - 0x2c6f - the file is not that big このファイルには動的セクションがありません。 readelf: エラー: Too many program headers - 0x2c6f - the file is not that big
さらにLinuxの裏をかいて削減できるような気もしますけど……、キリがないのでこれくらいにしておきます。
GDBはセクションヘッダを削除した時点でELFファイルとして認識しなくなります。ジャンプ先を間違ったとき、アドレスが間違っていてSEGVするときのデバッグができずしんどいです。
バイナリの種類 | GDB | readelf |
---|---|---|
オリジナル512バイト版 | 認識する | エラーなし |
セクション削除162バイト版 | エラー | セクションヘッダがない、エラー |
ELFヘッダ改変120バイト版 | エラー | 読む場所がずれてる(OS/ABIが間違っているから?) |
目次: ベンチマーク
Twitterで100万回のHello, World!問題を見かけ、面白そうだったのでやってみました。消えてしまった時のためにレギュレーションを書き写しておくと、
Cだとマクロを入れ子にする、setjmp/longjmpやsignalでgotoの代わりにする、辺りが設問意図のようです。C++だとクラスAのコンストラクタでHello, World!を書いておいて、A hoge[100 * 10000]のように配列宣言する方法があるみたいです。なるほどスマート。スクリプト言語だと大抵は繰り返し処理の構文があるので、あまり難しくないみたいです。最近の言語にとっては手ごたえのない問題かもしれません。
ツイートの引用をざっと見た感じだとアセンブラでやっている人がいなかったので、Cのふりしたアセンブラ(というかほぼバイナリ直書き)でチャレンジしました。
const char _start[] __attribute__((section(".text"))) = {
0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
0x66, 0xb8, 0x01, 0x00, //ax
0x89, 0xc7, //edi
0x66, 0xba, 0x0e, 0x00, //dx
0x48, 0x8d, 0x35, 0x0c, 0x00, 0x00, 0x00, //esi
0x0f, 0x05, //syscall
0xff, 0xcb, //dec ebx
0x75, 0xe9, //jne
0x66, 0xb8, 0x3c, 0x00, //ax
0x0f, 0x05, // syscall
'H', 'e', 'l', 'l', 'o', ',', ' ',
'W', 'o', 'r', 'l', 'd', '!', '\n', '\0',
};
これだけです。ソースコードのサイズは433バイトで、コメントなどは削っていませんが余裕で1000バイト以下に収まります。何が書いてあるのかわからんと思うので逆アセンブルした結果も載せます。
0000000000401000 <_start>: 401000: bb 40 42 0f 00 mov $0xf4240,%ebx ★0xf4240 = 100万 401005: 66 b8 01 00 mov $0x1,%ax 401009: 89 c7 mov %eax,%edi 40100b: 66 ba 0e 00 mov $0xe,%dx 40100f: 48 8d 35 0c 00 00 00 lea 0xc(%rip),%rsi # 401022 <_start+0x22> 401016: 0f 05 syscall ★write(1, "Hello, World!\n", 14)に相当する 401018: ff cb dec %ebx 40101a: 75 e9 jne 401005 <_start+0x5> ★goto 2行目 40101c: 66 b8 3c 00 mov $0x3c,%ax 401020: 0f 05 syscall ★exit()に相当、libcを使っていないのでretするとSEGVする ★ここから下はHello, World!の文字列なので命令列としては無意味 401022: 48 rex.W 401023: 65 6c gs insb (%dx),%es:(%rdi) 401025: 6c insb (%dx),%es:(%rdi) 401026: 6f outsl %ds:(%rsi),(%dx) 401027: 2c 20 sub $0x20,%al 401029: 57 push %rdi 40102a: 6f outsl %ds:(%rsi),(%dx) 40102b: 72 6c jb 401099 <_start+0x99> 40102d: 64 21 0a and %ecx,%fs:(%rdx)
次に動作確認しましょう。
$ gcc -static -nostdlib a.c /tmp/ccdifyE1.s: Assembler messages: /tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text $ ./a.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./a.out | wc 1000000 2000000 14000000
Hello, World!が繰り返し出ていること、100万行出ていること、異常事態(SEGVなど)が発生しないことを見ています。これで良さそうですね。
アセンブラでやる人がいないのは、jmp命令がgotoと同等なので当たり前にクリアできて何も面白くないからだと思います。なのでもう少しこだわって「1000バイト以下」のレギュレーションを極めましょう。
レギュレーションを上記のように強化しました。
まずは先ほど動作確認したバイナリのサイズを確認します。
$ gcc -static -nostdlib a.c /tmp/ccdifyE1.s: Assembler messages: /tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4864 2月 25 03:23 a.out $ strip -s a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4544 2月 25 03:25 a.out $ strip -s -R .note.gnu.build-id -R .comment a.out strip: a.out: warning: empty loadable segment detected at vaddr=0x400000, is this intentional? $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4360 2月 25 03:28 a.out
実質の命令列+文字列で50バイトくらいなのにバイナリは4KBを超えています。なんだこれは。stripしても300バイトほどしか減りません。readelfで確認すると.note.gnu.build-idと.commentというセクションがstripされずに残っていたため、排除しましたが500バイトほどしか減りません。
おっと……これは?もしかして意外と難しいのか?
バイナリのセクションヘッダを眺めていると、なぜか.textが0x1000から配置されています。
セクションヘッダ: [番] 名前 タイプ アドレス オフセット サイズ EntSize フラグ Link 情報 整列 [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .text PROGBITS 0000000000401000 00001000 ★この時点でバイナリサイズ4KBが確定 0000000000000031 0000000000000000 AX 0 0 32 [ 2] .shstrtab STRTAB 0000000000000000 00001031 0000000000000011 0000000000000000 0 0 1
デフォルトリンカースクリプト(gccに-Wl,-verboseオプションを渡すと表示できます)を調べると、特に何も指定しない場合.textは0x400000+SIZEOF_HEADERSというアドレスに配置されることがわかります。
SECTIONS
{
PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000));
. = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;
SIZEOF_HEADERSを決定する仕組みがいまいち分からないですが、恐らくSIZEOF_HEADERS = 0x1000でしょう。0x400000のような大きなアドレスの場合はプログラムヘッダのロードアドレスで調整するので、0x400000の0データがバイナリに書かれることはありません。しかし一定サイズ以下(今回のような0x1000など)の場合はバイナリに0データを埋め込んで開始位置を調整するようです。
この仕組みを逆手にとって.textの開始アドレス下位をもっと手前のアドレスにずらすことで、ELFヘッダやプログラムヘッダを避けながら開始位置調整用の無駄な0データを削除できるはずです。
$ gcc -static -nostdlib -Wl,-Ttext=0x400160 a.c $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 1120 2月 25 03:43 a.out セクションヘッダ: [番] 名前 タイプ アドレス オフセット サイズ EntSize フラグ Link 情報 整列 [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .text PROGBITS 0000000000400160 00000160 ★0x1000から0x160に詰められた 0000000000000031 0000000000000000 AX 0 0 32 [ 2] .note.gnu.bu[...] NOTE 00000000004000e8 000000e8 0000000000000024 0000000000000000 A 0 0 4 [ 3] .comment PROGBITS 0000000000000000 00000191 000000000000001f 0000000000000001 MS 0 0 1 [ 4] .symtab SYMTAB 0000000000000000 000001b0 0000000000000090 0000000000000018 5 2 8 [ 5] .strtab STRTAB 0000000000000000 00000240 000000000000001d 0000000000000000 0 0 1 [ 6] .shstrtab STRTAB 0000000000000000 0000025d 000000000000003d 0000000000000000 0 0 1
開始アドレス下位を0x1000から0x160までずらすとバイナリ中の0データ領域が減り、一気に1120バイトまで減りました。劇的な効果です。変更により動作不良を起こしていないかも忘れずにチェックします(動作チェックのログは省略)。
もう一息削れば1000バイトはすぐそこですが、、、
$ gcc -static -nostdlib -Wl,-Ttext=0x400140 a.c /tmp/cc5LlyKi.s: Assembler messages: /tmp/cc5LlyKi.s:4: Warning: ignoring changed section attributes for .text /usr/bin/ld: section .text LMA [0000000000400140,0000000000400170] overlaps section .note.gnu.build-id LMA [0000000000400120,0000000000400143] collect2: error: ld returned 1 exit status
残念ながら.textの開始アドレス下位を0x140にすると「別のセクションと重なってるぞ!」と怒られてリンクエラーになります。.note.gnu.build-idセクションと重なっているとのこと。
とりあえず.note.gnu.build-idセクションは無くても実行できるので、-Wl,--build-id=noneで消し去ります。.note.gnu.build-idセクションがいなくなった分、.textセクションをさらに前の0x100まで詰められます。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none a.c /tmp/cctmYikq.s: Assembler messages: /tmp/cctmYikq.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 936 2月 25 03:52 a.out
やりました。stripに頼らずとも1000バイトを下回ることができました。最初の4KBを見たときはどうなるかと思いましたが、意外と何とかなるものです。
既に目標は達成しましたが、さらに.commentセクションの排除と、stripするとどこまで減るか試しましょう。まずは.commentセクションの排除です。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 840 2月 25 04:55 a.out
次はstripです。.symtabセクションと.strtabセクションが消えます。
$ strip -s ./a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 520 2月 25 04:56 a.out
サイズは520バイトまで減らせました。1000バイトの約半分です。もっと複雑な処理でも詰め込めるでしょう。私はx86_64アセンブラが得意じゃないので、何か書いてやろうという気は起きませんけど……。
昨年8月ころに国立科学博物館が資金難に陥りクラウドファンディングをしていました(地球の宝を守れ - 国立科学博物館500万点のコレクションを次世代へ(国立科学博物館2023/08/07公開) - クラウドファンディング READYFOR)。科博にはこれからも頑張ってほしいなと思い、微力ながら「【体験】【寄付控除あり】乗り物体験<昔の電気自動車など>」コースに寄付しました。
んで、今日は寄付の返礼品のツアーに行ってきました。
残念ながら建物外観も含め写真を撮ってはダメで、写真がありません。車に乗っているところは写真を撮って良かったのですが、公開してはいけませんとのことで、日記に使える写真はありません。
科博の筑波地域の簡単な歴史や説明、注意事項、ツアーの時間を説明したオリエンテーリングのあと、実験植物園の裏口から理工資料棟に向かいました。こんな入り口あったんだ……。資料棟に入る前には靴底を洗い、靴にカバーを付けてから入場します(資料保護のためです)。
車は6台ありました。
Milburn電気自動車(理工電子資料館:Milburn 電気自動車 - 国立科学博物館)は、名前だけ聞くと電気自動車?EVの仲間?と思いますが、なんと100年前(1920年くらい)のアメリカの車です。
リンク先の写真を見てもらうとわかりますが、形がほぼ「馬車」です。御者台のない馬車というのかな。当時はガソリンエンジンが圧倒的シェアを取る前で、蒸気、電気、ガソリンなど様々な動力で走る車がいたそうです。面白い時代です。
マツダの各車、スバル 360は名前は知ってましたが乗ったのは初めてです。スバル 360は屋根が低すぎます。マツダ R360クーペは車内の狭さが尋常じゃないです。後部座席なんかほぼ壁です。4人乗りと名乗るには無茶が過ぎないか……??
車に乗ったり撮ったりするのが一巡したところでおまけツアーが始まりました。今日のツアー担当の方は3人いらっしゃって、車、天文、物理が専門の方々でした。たぶん2回目のツアーは担当の方が違うはずで、ツアーの内容も変わると思いますので参考程度。
最初は望遠鏡のツアーでした。
ちょうど車と同じフロアに天体望遠鏡が置いてあったため、望遠鏡の説明をしていただきました。今はデジタル撮像素子を使いますが、昔は写真乾板を使って撮影していたため数十分レベルの長時間露光が必要でした。単に数十分露光すると星が動いてしまって正しく撮影できないので、望遠鏡には望遠鏡の撮影部分を星の動きに追尾させる機構があります。
当時はモーターなどが精度良いものはなかったそうで、錘と調速機構(=遠心ガバナー)を使って一定速度で望遠鏡を回すという仕組みだそうです。望遠鏡は何台か所蔵されており上野の日本館の屋上で稼働していたニコンの60cm(だったかな?)反射式望遠鏡も置いてありました。反射式望遠鏡はどれもでかいですねえ……。
望遠鏡の次はコンピュータ系のツアーでした。
地球シミュレータが置いてありました。コンピュータはカッコいい系のデザインにされることが多いですが、地球シミュレータのデザインはかわいいですね。愛嬌があって良いと思います。京コンピュータもあったみたいですが、カバーが掛かったままで良く見えませんでした。
あと日立 HITAC5020もありました。前面パネルを開けて配線を見せてもらいましたが、辿ることすら困難なグチャグチャ配線でゾッとしました。良く配線したものだ、メンテも地獄だったのではなかろうか……。気合と根性の日本って感じがします。
< | 2024 | > | ||||
<< | < | 03 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | - | 1 | 2 |
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 | - | - | - | - | - | - |
合計:
本日: