Keyball46組み立て日記 〜間違えてRP2040を買ったそこのあなたに〜

TL; DR

  • Keyball46はいいぞ
  • ProMicroにはAVR版とRP2040版がある
    • ピン配置の互換性はあれど、命令セットは完全に異なるので「ファームウエアを書けとささやくのよ、私のゴーストが」という方以外はAVR版を間違えずに買いましょう
  • まあ最悪間違えても一週間くらいでなんとかなる(当社調べ)
  • みんな自作キーボードをやろう!

はじまり

みなさんは、Keyball46という素晴らしい自作キーボードキットをご存知ですか?

そう、なんと、キーボードにトラックボールがついてるんです!最高ですよね!

ということで、秋葉原にある自作キーボードのお店こと遊舎工房さんから速攻でポチりました。ちょうど安いキーボードを一個水没させたところですし、自作キーボードも本格的にやりたかったし、年末休みで暇を持て余していますからね。

期待に胸を躍らせつつ、はじめての表面実装ダイオードのハンダづけを難なくこなし、

さて、動作チェックとしゃれこみますか、と思ってファームウエアを焼こうとしたところ、自分の犯したミスに気づきます。

はい、パーツを間違えました。ゲームオーバーです。…本当に?

どこで道を踏み外したのか

さて、Keyball46の組み立て説明には、このように書かれていました。

(念の為、これは組み立て説明の落ち度ではなく、私の無知が原因です。私が失敗に至るまでの思考過程をお伝えするために引用しており、責任は私にあります。)

1-2.組立前にお客様自身で準備いただく部品

...

ProMicro 2個 安価なものやUSB Type-C対応のもの等選べます

...

…なるほど!Pro Microっていうマイコン基板を買えばいいのね! 遊舎工房で「Pro Micro」検索、っと…。

f:id:hikalium:20211230144749p:plain
遊舎工房での検索結果(当時)

お、何種類かあるんだ。せっかくだし USB Type-C のがいいなあ、これを買うか!(SparkFun Qwiic Pro Micro - USB-C (ATmega32U4)の商品ページに飛んでカートに入れようとする)

(ここでも念を押しておきますが、すべての落ち度は買うものを間違えた私にあります。みなさんは適当にポチらずにきちんと調べてから買いましょう。)

f:id:hikalium:20211230145141p:plain
売り切れ - SparkFun Qwiic Pro Micro - USB-C (ATmega32U4) - 遊舎工房

あれ、これは売り切れかあ。半導体不足の影響もあるのかなあ。じゃあこっちはどうかな?(もう一個の似た見た目のやつをクリック)

f:id:hikalium:20211230145337p:plain
商品がカートに追加されました! - SparkFun Pro Micro - RP2040 - 遊舎工房

わーい、買えそうだ!これで行こう!楽しみだなあ!!

…おわかりいただけただろうか。(ここが運命の分かれ道だった。)

Pro Microの種類

実はPro Microと名のつくボードには、コネクタの形状や互換品か否かという些細な点を除けば、大きく分けて少なくとも2種類が存在します。

見た目は非常に似ているのですが、何がちがうのかというと、載っているマイコンが根本的に違います。

前者はATmega32U4, つまりAVRマイコンです。 後者は、RP2040…これはRaspberry Piと同じ、ARMマイコンです。

はい、アーキテクチャからして完全に異なりますね。

さて、Keyball46が標準で提供しているファームウエアは…

# MCU name
MCU = atmega32u4
...

github.com

はい、ATmega32U4用ですね。おつかれさまでした。

「ファームウエアを書けとささやくのよ、私のゴーストが」

さて、困りましたね。再度ATmega32u4のPro Microを注文するのも時間がかかるだろうし、たとえそうしても、今手元にあるこのRP2040は無駄になってしまいます。それはマイコンがかわいそうですよね。

「…ファームウエアがないなら、書けばいいじゃない!」

たしかに!そうしよう!(白目)

方針を考える

とりあえず脳内で盛り上がってるマリーアントワネットと草薙素子は放置して、さっさと先に進みましょう。

最初はQMK firmwareをRP2040向けにビルドできないかとか少し調べたのですが、面倒なのでやめました(面倒とは!?)

あとベアメタルな環境でRustを書きたかったんです、はい。

幸い、ファームウエアのソースコードも回路図も公開されています。なんとかなりそうですね。(keyballの作者であるYowkeesさん、ありがとうございます!)

きっとRP2040のサンプルコードはインターネットにたくさん転がっているでしょうし、まずはそれを試してから、Rustでどう書くか考えることにしましょう。

まずは Hello, world だよね

そもそも、プログラムの書き込み方からわからないマイコンを相手にファームウエアを書き始めるのは無謀というものですから、まずは入門からやっていきましょう。

幸い、ネットの海を調べたところ、RaspberryPi公式でサンプルプログラムが公開されていました。

github.com

しかも、いくつかのプログラムはprebuiltのバイナリまで提供されています。便利!(上記リンク中のテーブルの Link to prebuilt UF2 というカラムから飛べます。)

とりあえずhello_usbのプログラムを書き込んでみましょう。

…え、どうやって書き込むの?

BOOTSEL mode, picotool

とりあえずネットの海を探ると、picotoolというCLIツールが見つかり、ボードをBOOTSELモードというのに持っていくと、picotoolを使ってプログラムを書き込める(もしくはストレージがUSBメモリのように認識されるので、そこにファイルをコピーする方法も可)ということがわかりました。

BOOTSELモードの入り方は、ボードの提供元であるSparkfunのページに画像付きで書かれています。

learn.sparkfun.com

基本的に、ボード上にある2つのボタンはRESETボタンとBOOTSELボタンになっているので、BOOTSELを押しながらRESETを押せばBOOTSELモードでボードが起動してプログラムが書き込めます。

というわけで、いずれかの方法でhello_usbのバイナリ(hello_world.uf2)を書き込むと、なんとPro MicroがUSB modemとして振る舞い始めます。

$ ls /dev/tty.usb*
/dev/tty.usbmodem0000000000001

これの出力をscreenコマンドで見てみると、

$ screen /dev/tty.usbmodem0000000000001
Hello, world!
Hello, world!
Hello, world!
...

OK, RP2040の世界にこんにちはできました。

でもね、そのボタン、押せないの…

さて、じゃあこの調子でファームウエアを書いていきましょう…と言いたいところなのですが、一つ困ったことがわかりました。

この画像を見てください。(逆転裁判で証拠品を提示するときの効果音)

f:id:hikalium:20211230153257j:plain
Pro Microの裏表に注目…(ボタンが押せない!)

「この写真には、制作途中のKeyball46にPro Microが挿さっている様子が写っています。」

「いたって普通のプリント基板とPro Microですね。何か問題でも?」

「Pro Microの部分を見てください。何かに気づきませんか?」

「いえ、いたって普通のPro Microだと思いますけど。先ほどあなたがおっしゃっていた通り、RP2040版であるという点は異常ですが、それはファームウエアを書くという話で決着がついたはずですよね。さっさとファームウエアを書き始めたらどうなんですか?」

「ええ、私もそうしたいところです。ファームウエアが書き込めれば、の話ですが。」

「そんなのボタンを押せばいいってさっき…ああああああっ!!!」

「そう、ないんですよ。ボタンがね。」

…おわかりいただけただろうか?なんとこの基板、Pro Microを裏面に装着するように設計されているため、ボタンが押せないのです。

AVR版のPro Microだと、電源投入時にリセットボタンを長押しや連打することで書き込みモードに移行できるため、リセットボタンはタクトスイッチで基板上から操作できるように設計されているのですが、RP2040版の場合は、リセットボタンだけではなくBOOTSELボタンを押す必要があるのです。しかし、それは押すことができない!

ラズパイでラズパイにプログラムを書き込む - SWDって便利だな

ソフトウエア開発において、開発とデバッグの繰り返しを迅速に行うことは、開発効率の面からも非常に重要です。 最悪、Pro Microを毎回外して書き込み、そして基板上に戻す、ということも、コンスルーピンのおかげでできなくはないでしょうが、非常に面倒ですし、そもそもそう何度も抜き差ししていたら接触不良の原因になるでしょう。なにしろやる気がダダ落ちです。

では、どうするか…上の画像を見ると、Pro Microの下側、qwiicと書いてあるところの上に、DとCと書かれたランドが露出しているのが見えます。

これは一体なんでしょうか?

SWD Pins For advanced users, there are two pins (i.e. D for data/SWDIO and C for clock/SWCLK) on the back broken out for SWD programming on the back of the board. You'll need to solder wire to connect to these pins.

Pro Micro RP2040 Hookup Guide - learn.sparkfun.com

ええ、私たちはAdvanced usersなので、これを使いましょう(満面の笑顔)。

CoreSight Architecture | Serial Wire Debug – Arm Developer

ARM社のドキュメントによれば、SWD(Serial Wire Debug)を利用すると、JTAGと同じようなことができる、と書いてあります。

まあ簡潔にいえば、これをよしなにopenocd経由で操作してあげれば、レジスタ読み書きし放題、メモリ書き換え放題、要するになんでもやりたい放題できるということです。

まあファームウエアを開発するんだから、これくらいやってもよいでしょう。

まずはさくっとジャンパワイヤをSWDのランドにはんだ付けして、

f:id:hikalium:20211230171833p:plain
SWD の D, C および GND にジャンパワイヤを接続したようす

もう一台どこのご家庭にも転がっているRaspberry Piを持ってきて、DをGPIO24, CをGPIO25に繋ぎます。(このピンアサインは、openocdに付属しているconfigファイルに定義されています。)

forums.raspberrypi.com

あとは、Raspberry Pi上で、Raspberry Piのフォーラムに書いてあったいい感じのopenocdのコマンドラインを参考に適当にopenocdさんを呼び出すと

openocd -f interface/raspberrypi-swd.cfg -f target/rp2040.cfg -c '"targets rp2040.core0; program ${PATH_TO_ELF} verify reset exit"

${PATH_TO_ELF}に指定したプログラムが書き込まれてターゲットが再起動します。これは便利!(書き込まれたバイナリはちゃんと永続化されているので、次回以降の起動時もこれが使われます。)(先ほど紹介したprebuiltのUF2ファイルはこの方法では読めないので、サンプルを手元でビルドして、UF2に変換される前のELFファイルを指定してあげてください。)

よし、これでPro MicroをKeyball46の基板に挿しっぱなしでも大丈夫になりました。やっとファームウエアを書くステップに行けますね!

RustでRP2040をターゲットにしたプログラムを書く

先程紹介した raspberrypi/pico-examples は、残念ながらC言語で書かれています。

せっかく書くなら、もっと現代的な言語で書きたいですよね?ということで調べてみると、RP2040向けのHALを提供してくれるcrateが見つかりました。

github.com

フルスクラッチで書くのも面白そうですが、動くとわかってからでも遅くはないので、ひとまずはこれを使うことにしましょう。

先ほどと同様に、まずはサンプルを試してみます。

boards/sparkfun-pro-micro-rp2040/examples/sparkfun_pro_micro_rainbow.rs に、Pro Micro (RP2040) 用のサンプルがあるので、これをREADME.mdに書いてある通りにビルドします。

cargo build --release --example sparkfun_pro_micro_rainbow

そうすると、target/thumbv6m-none-eabi/release/examples/pro_micro_rainbowにELFファイルが生成されるので、これを先程の方法で書き込んでみます。すると、LEDが虹色に光り始めます。やったね!(下の画像で緑色のLEDがそれです。)

f:id:hikalium:20211230180209p:plain
RustでRP2040のLチカ!

USB HID として振る舞いたい

さて、私たちはもう終わったクリスマスの電飾を作りたかったわけではなくて、キーボードとマウスとして振る舞う何かを作りたかったのでした。

これを達成するためには、Pro Microさんに USB HID として振る舞ってもらう必要があるのですが、それをゼロからちょっと実装するのは大変です。

そこで、rp-rs/rp-hal内の他のboard向けのサンプルを眺めてみたところ、boards/rp-pico/examples/pico_usb_twitchy_mouse.rs という、まさにこれがほしかった!みたいなサンプルが見つかりました。なので、これをさくっとsparkfun_pro_micro向けに移植してあげればOKです。

実はpico向けにビルドしたバイナリを書き込むと普通に動いてしまうんですが(まあ同じSoCを使ってるからそれはそう)、せっかくHALがボードごとにあるので、ちょっと手直ししてあげるといいと思います。(適当にやった。)

はい、これで「PCに繋ぐとマウスが小刻みに上下するので画面ロックを回避できる邪悪バイス」ができあがりました。意外と簡単だ!

キーボード機能を追加する

ではこの調子でBadUSBキーボード入力もできるようにしましょう。まずは、さっきのサンプルの実装を読んでみます。

    // Create a USB device with a fake VID and PID
    let usb_dev = UsbDeviceBuilder::new(bus_ref, UsbVidPid(0x16c0, 0x27da))
        .manufacturer("Fake company")
        .product("Twitchy Mousey")
        .serial_number("TEST")
        .device_class(0xEF) // misc
        .build();
    unsafe {
        // Note (safety): This is safe as interrupts haven't been started yet
        USB_DEVICE = Some(usb_dev);
    }

ここでデバイスを作って、

    // Move the cursor up and down every 200ms
    loop {
        delay.delay_ms(100);

        let rep_up = MouseReport {
            x: 0,
            y: 4,
            buttons: 0,
            wheel: 0,
            pan: 0,
        };
        push_mouse_movement(rep_up).ok().unwrap_or(0);

        delay.delay_ms(100);

        let rep_down = MouseReport {
            x: 0,
            y: -4,
            buttons: 0,
            wheel: 0,
            pan: 0,
        };
        push_mouse_movement(rep_down).ok().unwrap_or(0);
    }

あとはここでマウスの動きをpushしているようです。push_mouse_movementの実装は、以下のような感じです。

fn push_mouse_movement(report: MouseReport) -> Result<usize, usb_device::UsbError> {
    cortex_m::interrupt::free(|_| unsafe {
        // Now interrupts are disabled, grab the global variable and, if
        // available, send it a HID report
        USB_HID.as_mut().map(|hid| hid.push_input(&report))
    })
    .unwrap()
}

ここで、自作OSでUSB HIDドライバを実装していた際の知識が役に立ってきます。

まず、USB HID では、マウスの移動やキーボードの押し下げなどの情報は、レポートというデータとしてデバイスから送られてきます。

そして、ここが重要なのですが、USBはプロトコル的に、常にホスト側からしかデータの転送を開始できない仕組みになっています。これはどういうことかというと、USBプロトコルのレイヤでは、割り込みという概念が存在せず、ポーリングしかできない、ということです。

ですが、キーボードやマウスが動くのは(CPUさんの時間軸から見たら)稀なので、ポーリングをするのは非効率的な気がしますよね?そこで、USBでは、USBコントローラがUSBデバイスに対して定期的にデータ転送を要求して(ポーリング)、データがあればUSBコントローラからCPUに割り込みを発生させる、という仕組みになっています。

というわけで、上のpush_mouse_movementが呼ばれても、実際にはまだホスト側にはその情報は伝わりません。その代わり、USBコントローラーが定期的に読んでくるとデバイス側で割り込みが発生するので、そのタイミングでデータを送りつけてあげることになります。

#[allow(non_snake_case)]
#[interrupt]
unsafe fn USBCTRL_IRQ() {
    // Handle USB request
    let usb_dev = USB_DEVICE.as_mut().unwrap();
    let usb_hid = USB_HID.as_mut().unwrap();
    usb_dev.poll(&mut [usb_hid]);
}

これが、その「デバイス側の割り込みハンドラ」です。これが呼ばれるタイミングで、デバイスからホストへとデータ転送が走ることになります。

この割り込みの周期については、もっと上の方で

    let usb_hid = HIDClass::new(bus_ref, MouseReport::desc(), 60);

とすることで、HIDClassを初期化する際に、60msに設定されています。詳細は、docs.rsにあるドキュメントを読むとわかりやすいと思います。

ここまでが、大まかなサンプルのデータの流れです。

では、これを改造して、キーボードの情報も送るにはどうすればよいでしょうか?

usbd-hidのドキュメントをさらに読むと、MouseReportの隣にKeyboardReportがあることがわかります。これを使えばなんとかいけそうですね。

見よう見まねで、こんな感じにしてみます。(振り返って書いているので雰囲気だけ掴んでください。)

static mut USB_HID_KEYBOARD: Option<HIDClass<hal::usb::UsbBus>> = None;

fn main() -> ! {
    ...
    let usb_hid_keyboard = HIDClass::new(bus_ref, KeyboardReport::desc(), 10);
    unsafe {                                                                                                                                                           
        USB_HID_KEYBOARD = Some(usb_hid_keyboard); 
    }
    ...
    loop {
      ...
      let rep = KeyboardReport {
          modifier: 0,
          reserved: 0,
          leds: 0,
          keycodes: [0x04 /* A */, 0, 0, 0, 0, 0],
      };
      push_key_event(rep).ok().unwrap_or(0);
      ...
    }
    ....
}

pub fn push_key_event(report: KeyboardReport) -> Result<usize, usb_device::UsbError> {
    cortex_m::interrupt::free(|_| unsafe {
        USB_HID_KEYBOARD.as_mut().map(|hid| hid.push_input(&report))
    })
    .unwrap()
}

...

#[allow(non_snake_case)]
#[interrupt]
unsafe fn USBCTRL_IRQ() {
    // Handle USB request
    let usb_dev = USB_DEVICE.as_mut().unwrap();
    let usb_hid_mouse = USB_HID.as_mut().unwrap();
    let usb_hid_keyboard = USB_HID_KEYBOARD.as_mut().unwrap(); // new
    usb_dev.poll(&mut [usb_hid_mouse, usb_hid_keyboard /* new */]);
}
...

KeyboardReportのkeycodesについては、HID Usage Tables FOR Universal Serial Bus (USB)10: Keyboard/Keypad Page (0x07) に定義があります。また、ここにpdfよりも軽い表があります。

これで、マウスの上下移動とともに、aが入力され続けるはずです。

実際、動きました。…Linuxでは。

しかし、なぜかmacOSではマウスもキーボードも動かなくなってしまいました。一体なぜでしょうか?

Boot keyboard のフォーマットに切り替える

osdev.orgの記事によれば、USBキーボードのReportの形式は、

pub struct KeyboardReport2 {                                                                                                                                                                                                                                                                              
    pub modifier: u8,                                                                                                                                                                                                                                                                                     
    pub reserved: u8,                                                                                                                                                                                                                                                                                     
    pub keycodes: [u8; 6],                                                                                                                                                                                                                                                                                
}

のような形式になっているようです。…あれっ、先ほど利用したusbd-hidのKeyboardReportには存在する、ledsのフィールドがないですね…。

これは完全に想像ですが、macOSではUSBキーボードのレポートディスクリプタをきちんと解釈せず、Boot protocolに沿っていると仮定しているのではないでしょうか。

レポートディスクリプタというのは、Reportがどのような形式になっているのかをUSBデバイスがUSBホスト側に伝えるためのデータで、

    let usb_hid_keyboard = HIDClass::new(bus_ref, KeyboardReport::desc(), 10);

この行の KeyboardReport::desc()がそれにあたります。このdescは、ソースを確認すると

#[gen_hid_descriptor(
    (collection = APPLICATION, usage_page = GENERIC_DESKTOP, usage = KEYBOARD) = {
        (usage_page = KEYBOARD, usage_min = 0xE0, usage_max = 0xE7) = {
            #[packed_bits 8] #[item_settings data,variable,absolute] modifier=input;
        };
        (usage_min = 0x00, usage_max = 0xFF) = {
            #[item_settings constant,variable,absolute] reserved=input;
        };
        (usage_page = LEDS, usage_min = 0x01, usage_max = 0x05) = {
            #[packed_bits 5] #[item_settings data,variable,absolute] leds=output;
        };
        (usage_page = KEYBOARD, usage_min = 0x00, usage_max = 0xDD) = {
            #[item_settings data,array,absolute] keycodes=input;
        };
    }
)]

このようなマクロによって生成されています。

おそらく、Linuxはこれを解釈して正しくReportを読み取れるのですが、macOSは期待しているデータ構造と送られてきたReportが一致しないため、そこであきらめてしまっているのではないかと考えられます。

というわけで、osdev.orgやUSBのドキュメントに記載されている、Boot protocolの形式のほうを利用することにしましょう。これで、macOSでもLinuxでも動きます!

その他のハマりポイント

勢いで書いていたらめっちゃ記事が長くなってきたので、残りはさくっといきます。もし詳しく知りたい方がいらっしゃったら、Twitterなどでhikalium宛にリプライを飛ばすか、低レイヤーガールチャンネルの配信の際にでもコメントで聞いてください。

トラックボール基板がお返事してくれない…

Pro Micro にピンをつけた際、はんだが流れて NCSとMOSIがショートしてた

状況: トラックボール制御基板さんにSPI通信でお話ししても0xFFしか返ってこない。ロジアナで見たらNCSとMOSIが仲良く同じ波形を出してた。

f:id:hikalium:20211230185805p:plain
上から順にNCS, CLK, MOSI, MISOの波形

解決策: 一回該当するピンのハンダを除去してやりなおし。

NCSがトランザクションが終わるよりも前にhighに戻っちゃう

状況: ショートを直してもまだお返事もらえない。波形を見てみると、NCSが一瞬しかlowになってなかった。

原因: rp-rs/rp-halのSpi::writeは、データレジスタに書き込むだけで、送信完了を待ってはくれないのであった。(涙)

解決策:

rp-halをforkしてSpi::deviceをとれるようにし、それを直接使ってステータスレジスタを読み、sendが完了するのをloopで待つようにした。

        loop {
            let sspsr = spi.borrow_mut().device().sspsr.read();
            if sspsr.tfe().bit_is_set() && sspsr.bsy().bit_is_clear() {
                break;
            }
            delay.borrow_mut().delay_us(10);
        }

まとめ

とりあえず動くようになった。

f:id:hikalium:20211231145356p:plain
完成した図。トラックボールもキーボードも動く!(SWDの線がまだ生えてるのはご愛嬌)

まだキーマップが練りきれていないのと、TRRSケーブルを介した接続には対応していないほか、私はこれまでErgo Dox EZを使っていたので、いかにこのキーの少なさで生きていくかなど課題は山積みですが、少しずつ実運用に投入していきたいと思います。(この記事の一部はこれで書きました。)

自作キーボード、たのしい!みんなもやろう!!

謝辞

Keyball46を設計されたYowkeesさん、自作キーボードに必要なパーツを販売している遊舎工房さん、そして数年前のCookpad自作キーボードインターン(?)で自作キーボードの基礎を教えてくれたKOBA789さん、ありがとうございました!

成果物

github.com

Raspberry Pi 4をJTAGデバッグしてみる(FTDI C232HM-DDHSL-0使用)

f:id:hikalium:20210718212859j:plain
JTAGアダプタとシリアルケーブルがつながったRaspberry Pi 4

概要

Raspberry Piでベアメタルプログラミングをするときに、CPUが今実際にどこの命令を実行しているか、メモリ上にどのような値が存在するか…などの情報を確認できると、デバッグが非常に楽になります。それを可能にしてくれるのが、JTAGというインターフェイスです。

今回は、FTDI社製のケーブルを使用して、Raspberry Pi 4のJTAGにアクセスしてみました。前半部分はケーブル固有の話もあるので、他のJTAGケーブルをお持ちの方は、それぞれのマニュアルを参照して適宜読み替えていただく必要があります。一方後半部分は、openocdを使ってJTAG経由でRaspberry Pi 4の情報を取得する一般的な方法について説明しますので、みなさんの環境でも役立つかもしれません。参考にしていただければ幸いです。

主な登場人物

  • Raspberry Pi 4 Model B
    • BCM2711というSoCが載っています。
  • FTDI C232HM-DDHSL-0
    • このケーブルはMPSSE(Multi-Protocol Synchronous Serial Engine) といって、モードを切り替えればJTAG以外にもSPIやI2Cといった通信もできるようです。
    • C232HM-DDHSL-0とC232HM-EDHSL-0の違いは、通信に使う電圧レベルです(3.3Vと5.0V)。Raspberry PiのGPIOは3.3Vなので、間違えないようにしましょう。
  • FTDI TTL-232RG-VREG3V3-WE
    • このケーブルはJTAG通信には関係ないですが、Raspberry PiのUART(シリアルポート)を読むために使っています。ベアメタルプログラミングするなら、基本的にシリアルは生命線になるので、シリアルを読めるケーブルは何らかのものを持っておくとよいと思います。
    • 例によって、これも電圧レベルによって似た品番のものがあるので、他の変換ケーブルやボードを使う際も、3.3Vのものを買うようにしましょう。
    • ちなみにこのケーブルは末端が電線剥き出しでコネクタがついてないので、私はそれをブレッドボードに刺してそこからRasPiに延ばしています。コネクタがついているタイプのものも他の製品だとあるようなので、そっちを買った方が便利かもしれません。

決戦結線の時

というわけで早速ケーブルとRasPiをつないでゆきます。RasPiの電源を落としてから作業しましょう。

落とし穴としては、RasPiのGPIOピンの番号と、物理ピン番号(GPIOヘッダ上の位置)は異なる、というところです。

詳しくはRaspberry Pi 公式のドキュメントに解説があるので、それをチェックしてください。

(以下はあくまでも参考として、鵜呑みにせずに自分で本当に合っているかチェックしながら接続してください!)

JTAG ⇔ C232HM-DDHSL-0

ケーブル自体のデータシートも参考にしてください。

ケーブルの色 GPIOピン番号 物理ピン番号 GPIOヘッダを右上においたときの場所
Brown (TMS) 27 (ARM_TMS) 13 上から7番目の左
Grey (TRST) 22 (ARM_TRST) 15 上から8番目の左
Blue (RTCK) 23 (ARM_RTCK) 16 上から8番目の右
Green (TDO) 24 (ARM_TDO) 18 上から9番目の右
Orange (TCK) 25 (ARM_TCK) 22 上から11番目の右
Yellow (TDI) 26 (ARM_TDI) 37 上から19番目の左=下から2番目の左
Black (GND) GND 39, etc... 一番左下など

RTCKを使わない記事もインターネット上にはありましたが、これをつなぐと通信が格段に安定したのでこのようにしています。

UART ⇔ TTL-232RG-VREG3V3-WE

ケーブル自体のデータシートも参考にしてください。

ケーブルの色 GPIOピン番号 物理ピン番号 GPIOヘッダを右上においたときの場所
Yellow(RXD) 14 8 上から4番目の右
Black(GND) GND 9, etc... 上から5番目の左など
Orange(TXD) 15 10 上から5番目の右

接続イメージ

全部つないでみたときの参考写真を貼っておきました。(写真の向きは、GPIOヘッダを左上にみたときの例なので、上の説明と対応させる場合は、90度首を傾けてみてください。)

シリアル変換ケーブルから伸びている線は、写真上側のブレッドボードでジャンパワイヤに変換されてきているので、上の説明に書かれている色と、写真中の線の色は一致しません。

画面左側、JTAGアダプタから伸びている線の色は、上に書いてある説明と一致します。

f:id:hikalium:20210718213206j:plain
JTAGアダプタとシリアル出力の接続例

ソフトウエアの設定

今回の環境は macOS 11.4ですが、Linuxなどの他の環境でも、似たような設定をすれば動作するはずです。

openocdをインストールする

最新のopenocdをHomebrew経由でインストールします。

brew install openocd --HEAD

私の環境では、以下のようなエラーメッセージが出ました。

$ brew install openocd --HEAD
...
==> Installing open-ocd --HEAD
==> ./bootstrap nosubmodule
==> ./configure --prefix=/usr/local/Cellar/open-ocd/HEAD-cff0e41 --enable-buspir
==> make install
Error: An unexpected error occurred during the `brew link` step
The formula built, but is not symlinked into /usr/local
Cannot link open-ocd
Another version is already linked: /usr/local/Cellar/open-ocd/0.10.0
Error: Cannot link open-ocd
Another version is already linked: /usr/local/Cellar/open-ocd/0.10.0

このエラーは、すでに他のバージョンのopenocdがインストールされている場合に表示されます。この場合、インストールした最新のopenocdにはPATHが通っていない状態になっていますので、パスを直接指定して実行してあげる必要があります。(もちろん、強制的にPATHを通す(link)することも可能ですが、各自の判断にお任せします。)

私の環境では、/usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocdにインストールされていましたので、これを直接実行できることを確認します。

$ /usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd --version
Open On-Chip Debugger 0.11.0+dev-00236-gcff0e417d-dirty (2021-06-28-20:42)
Licensed under GNU GPL v2
For bug reports, read
    http://openocd.org/doc/doxygen/bugs.html

バージョン情報が正しく表示されればOKです。

Raspberry Pi 側でJTAGインターフェイスを有効化する

デフォルトでは、JTAGインターフェイスは無効になっており、該当するピンは通常のGPIOポートとして機能するように設定されています。

JTAGを有効化するには、Raspberry PiのSDカード内にある config.txtというファイルの[all]セクションの配下に、以下のような記述を追加します。

enable_jtag_gpio=1

これにより、起動時にRaspberry Piのファームウエアがこの設定ファイルを読み込んだ際に、JTAGを有効化してくれます。

詳しくは、公式のドキュメントを参照してください。

ついでにシリアルポート出力とかも有効化しておく

enable_uart=1

参考: 私のconfig.txtの末尾はこうなっている

他にもいろいろ設定を入れてこんな感じになっています。参考までに。(この記事で解説したことを試すには、上で説明した2つを設定するだけで大丈夫なはずです。)

...
[all]
#dtoverlay=vc4-fkms-v3d
arm_64bit=1
init_uart_clock=48000000
init_uart_baud=115200
enable_uart=1
enable_jtag_gpio=1

openocdの設定

それでは早速openocdを使っていきたいのですが、使うためにはいくつか設定ファイルを作成する必要があります。

インターフェイスの設定

まず、以下のような内容のファイルを作成しc232hm-edhsl-0.cfgという名前で保存します。

adapter driver ftdi
ftdi_vid_pid 0x0403 0x6014
ftdi_device_desc C232HM-DDHSL-0

# ftdi_layout_init <values> <directions>
# initial value:
# 0078 = 0000 0000 0001 1000
# TRST, TMS=1, all others zero
# initial direction:
# 0111 = GPIOL3=RTCK=input, GPIOL2=dontcare=output, GPOL1=SRST=output, GPIOL0=TRST=output
# 1011 = [1=TMS=output, 0=TDO=input, 1=TDI=output, 1=TCK=output]
ftdi_layout_init 0x0018 0x007b

# GPIOL0 is TRST
ftdi_layout_signal nTRST -data 0x0010

(参考にしたブログ記事 のものに比べると、最新のopenocdに合わせて少し修正してあります。)

このファイルには、使用するJTAGアダプタ(今回の場合はFTDI C232HM-DDHSL-0)に固有の設定が記載されています。そのため、別のJTAGアダプタを使用する際は、それに合ったファイルを作成する必要があります。場合によっては標準で提供されていることもあるので、他のアダプタをお使いの方は各自で調べてみてください。

ターゲットの設定

次に、以下のような内容のファイルを作成しraspi4.cfgという名前で保存します。

set _CHIPNAME bcm2711
set _DAP_TAPID 0x4ba00477

adapter speed 1000

transport select jtag
reset_config trst_and_srst

telnet_port 4444

# create tap
jtag newtap auto0 tap -irlen 4 -expected-id $_DAP_TAPID

# create dap
dap create auto0.dap -chain-position auto0.tap

set CTIBASE {0x80420000 0x80520000 0x80620000 0x80720000}
set DBGBASE {0x80410000 0x80510000 0x80610000 0x80710000}

set _cores 4

set _TARGETNAME $_CHIPNAME.a72
set _CTINAME $_CHIPNAME.cti
set _smp_command ""

for {set _core 0} {$_core < $_cores} { incr _core} {
    cti create $_CTINAME.$_core -dap auto0.dap -ap-num 0 -baseaddr [lindex $CTIBASE $_core]

    set _command "target create ${_TARGETNAME}.$_core aarch64 \
                    -dap auto0.dap  -dbgbase [lindex $DBGBASE $_core] \
                    -coreid $_core -cti $_CTINAME.$_core"
    if {$_core != 0} {
        set _smp_command "$_smp_command $_TARGETNAME.$_core"
    } else {
        set _smp_command "target smp $_TARGETNAME.$_core"
    }

    eval $_command
}

eval $_smp_command
targets $_TARGETNAME.0

(こちらも、参考にした記事をベースに、最新のopenocdに合わせて少し修正を加えたものになります。)

このファイルには、デバッグ対象のデバイス(今回の場合はRaspberry Pi 4 / BCM2711)に固有の設定が記載されています。そのため、もし異なるボードをJTAGデバッグしたい場合には、それぞれに合ったファイルを作成して使用する必要があります。

動かしてみる

では、編集済みのconfig.txtが入ったRaspberry Pi OS入りのSDカードをRaspberry Pi 4に挿入し、JTAGケーブルやシリアル変換ケーブルをPCにさして、最後にRaspberry Pi 4に電源をさして起動してみましょう。その後、以下のコマンドを実行してみてください。

/usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd -f c232hm-edhsl-0.cfg -f raspi4.cfg

(最初のopenocdへのパスは、適宜環境に合わせて読みかえてください。)

すべてが正しく動作していれば、以下のような出力が得られ、サーバーが待受状態になります。

$ /usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd -f c232hm-edhsl-0.cfg -f raspi4.cfg
Open On-Chip Debugger 0.11.0+dev-00236-gcff0e417d-dirty (2021-06-28-20:42)
Licensed under GNU GPL v2
For bug reports, read
    http://openocd.org/doc/doxygen/bugs.html
Info : Listening on port 6666 for tcl connections
Info : Listening on port 4444 for telnet connections
Info : clock speed 1000 kHz
Info : JTAG tap: auto0.tap tap/device found: 0x4ba00477 (mfg: 0x23b (ARM Ltd), part: 0xba00, ver: 0x4)
Info : bcm2711.a72.0: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.1: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.2: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.3: hardware has 6 breakpoints, 4 watchpoints
Info : starting gdb server for bcm2711.a72.0 on 3333
Info : Listening on port 3333 for gdb connections

openocdとのやりとり

参考:

上の出力に書かれている通り、telnetなどで4444番ポートにアクセスすると、openocdとおはなしできます。

$ telnet localhost 4444
Trying ::1...
telnet: connect to address ::1: Connection refused
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
Open On-Chip Debugger
> 

ここにコマンドを打つと、いろいろ見れます。

targets: 各ターゲット(今回の場合CPUコア)を一覧表示できる

> targets
    TargetName         Type       Endian TapName            State       
--  ------------------ ---------- ------ ------------------ ------------
 0* bcm2711.a72.0      aarch64    little auto0.tap          running
 1  bcm2711.a72.1      aarch64    little auto0.tap          running
 2  bcm2711.a72.2      aarch64    little auto0.tap          running
 3  bcm2711.a72.3      aarch64    little auto0.tap          running

targets bcm2711.a72.1のように、TargetNameを指定すれば、現在選択しているtargetを変更できる。

halt: 実行を停止させる。

> halt
bcm2711.a72.1 cluster 0 core 1 multi core
bcm2711.a72.2 cluster 0 core 2 multi core
bcm2711.a72.2 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.3 cluster 0 core 3 multi core
bcm2711.a72.3 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.0 cluster 0 core 0 multi core
bcm2711.a72.0 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x600003c9 pc: 0x813d8
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.1 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
> targets
    TargetName         Type       Endian TapName            State       
--  ------------------ ---------- ------ ------------------ ------------
 0  bcm2711.a72.0      aarch64    little auto0.tap          halted
 1* bcm2711.a72.1      aarch64    little auto0.tap          halted
 2  bcm2711.a72.2      aarch64    little auto0.tap          halted
 3  bcm2711.a72.3      aarch64    little auto0.tap          halted

reg: レジスタを表示する

> reg                  
===== Aarch64 registers
(0) x0 (/64): 0x000000000000006c (dirty)
(1) x1 (/64): 0x00000000ffffffff
(2) x2 (/64)
...

dirtyと書かれているデータは、openocdがキャッシュしているものなので、もし生の値を反映させたかったら、以下のようにすると強制的に読み書きできる。

reg x0 force

キャッシュ情報とかも見れます

> aarch64 cache_info
L1 I-Cache: linelen 64, associativity 3, nsets 256, cachesize 48 KBytes
L1 D-Cache: linelen 64, associativity 2, nsets 256, cachesize 32 KBytes
L2 D-Cache: linelen 64, associativity 16, nsets 1024, cachesize 1024 KBytes

メモリの読み書きもできちゃいます!たとえば0x80000(raspberry pi 4におけるカーネルのロードアドレス)をみると

>  mdw 0x80000
0x00080000: d53800a1

と書いてありますが、今回起動したイメージの先頭を確認してみると

$ hexdump -C kernel8.img | head -n 1
00000000  a1 00 38 d5 21 04 40 92  42 01 00 58 3f 00 02 eb  |..8.!.@.B..X?...|

たしかに一致していますね!

gdbとあわせて使う

参考: GDB and OpenOCD (OpenOCD User’s Guide)

openocdの起動時のメッセージを注意深く読むと、gdbのサーバーも待ち受けていることがわかります。

Info : starting gdb server for bcm2711.a72.0 on 3333
Info : Listening on port 3333 for gdb connections

ということで、さっそくつないでみましょう。今回使ったgdbのバージョンは以下の通り。

$ gdb --version | head -n 1
GNU gdb (GDB) 9.2

まず、gdbを引数なしで起動します。

gdb

そのあと、gdbのプロンプトに、アーキテクチャとターゲット情報を打ち込んで、リモートデバッグをはじめます。

私が試した例では、config.txtにarm_64bit=1と書いた状態でaarch64のバイナリを実行している状態なので、以下のようにaarch64をターゲットとして指定します。

(gdb) set architecture aarch64
The target architecture is assumed to be aarch64
(gdb) target extended-remote localhost:3333
Remote debugging using localhost:3333
warning: No executable has been specified and target does not support
determining executable automatically.  Try using the "file" command.
0x00000000000813d8 in ?? ()

一方、Raspberry Pi OSは記事執筆現在は32bit(armv7l)で動作しているので、もしそのようなターゲットをデバッグしたい場合は、aarch64の代わりにarmv8-aにするとよいでしょう。

set architecture armv8-a
target extended-remote localhost:3333

もし間違ったarchを指定していたら、以下のようなエラーメッセージが出るので、そのときは別のarchを指定してやり直せばOKです。

warning: Selected architecture armv8-a is not compatible with reported target architecture aarch64
warning: Architecture rejected target-supplied description

さて、これでgdbがつながったので、デバッグし放題です。いつものinfo registersとかもばっちり動きます。

(gdb) info registers
x0             0x0                 0
x1             0x8192d             530733
x2             0x2                 2
x3             0x80264             524900
...

もちろん、今実行しているバイナリが手元にあれば、それを読み込んでgdbデバッグすることもできます。

$ file target/aarch64-unknown-none-softfloat/release/kernel
target/aarch64-unknown-none-softfloat/release/kernel: ELF 64-bit LSB executable, ARM aarch64, version 1 (SYSV), statically linked, with debug_info, not stripped

$ gdb target/aarch64-unknown-none-softfloat/release/kernel
GNU gdb (GDB) 9.2
...
(gdb) target extended-remote localhost:3333
Remote debugging using localhost:3333
0x00000000000813d8 in kernel::kernel_main ()
(gdb) disas
Dump of assembler code for function _ZN6kernel11kernel_main17h947565f396a80a38E:
   0x0000000000080fd4 <+0>:   sub sp, sp, #0xc0
   0x0000000000080fd8 <+4>:   stp x30, x27, [sp, #112]
(gdb) c
Continuing.

loadコマンドをつかえば、バイナリを動的にメモリ上にロードすることだってできちゃいます。

(gdb) load
Loading section .text, size 0x1674 lma 0x80000
Loading section .rodata, size 0x4c5 lma 0x81678
Loading section .got, size 0x10 lma 0x81b40
Loading section .data, size 0x20 lma 0x81b50
Start address 0x0000000000080000, load size 7017
Transfer rate: 63 KB/sec, 1754 bytes/write.

raspberry piJTAGインターフェイスにはSRSTピンが生えていないため、gdbmonitor resetコマンドを利用してチップをリセットしてロードしたプログラムを再実行させることはできませんが、プログラムカウンタ(pc)を変更することはできるので、代わりに使うといいかもしれません。

(gdb) set $pc=0x80000
(gdb) c

というわけで、とっても便利なJTAGを活用して、皆様も楽しいRasPiベアメタル開発の時間をお過ごしください!

付録: openocdがうまくいかないとき

Error: no device found
Error: unable to open ftdi device with vid 0403, pid 6014, description 'C232HM-DDHSL-0', serial '*' at bus location '*'

→そもそもJTAGアダプタがPCにつながっていない/認識されていない。

Error: JTAG scan chain interrogation failed: all ones
Error: Check JTAG interface, timings, target power, etc.
Error: Trying to use configured scan chain anyway...
Error: auto0.tap: IR capture error; saw 0x0f not 0x01
Warn : Bypassing JTAG setup events due to errors
Error: Invalid ACK (7) in DAP response
Error: JTAG-DP STICKY ERROR

デバッグ対象のデバイスの電源が入っていない/まだ起動直後でJTAGが有効化されてない/配線が間違っている/enable_jtag_gpio=1の設定変更が正しく反映されていない。

liumOS 2020年の進化を振り返る

この記事は自作OS Advent Calendar 2020の「最初の4つの素数の和」日目の記事として作成されました。

liumOSについて

liumOSは、NVDIMM(Non-volatile DIMM, 不揮発性メインメモリ)をネイティブにサポートしている、珍しいタイプの自作OSです。2018年7月26日に開発を開始して以来、記事執筆時点で682 commitsを数えるほどに成長しました。主要開発者はhikaliumですが、後述する通り、ここ数ヶ月間はd0iasmさんにも手伝っていただいていました。

2018年には、自作OSからNVDIMMを触る方法について自作OS Advent Calendar 2018の記事で紹介しましたので、NVDIMMについて知らないよという方や、興味のある方はそちらもぜひお読みください。

hikalium.hatenablog.jp

今年は、かなり色々なものをliumOS上に実装して遊んでいたので、この記事ではそのうちのいくつかについて紹介してみたいと思います。

Adlibを利用したMIDI再生機能

これはOSの中核的な機能ではありませんが、デバイスドライバの実装の一環として、Adlibという非常に古いサウンドバイスのドライバを書いて、さらにMIDIファイルのパーサを書いて再生できるようにしました。実は中学生の頃に開発していた自作OSでもMIDIファイルの再生を試みていたことはあるのですが、当時はビープ音で無理やりなんとか和音を出そうとして結局失敗した記憶があり、その当時のMIDIパーサを再利用してN年越しの目標を達成したのでした。

デモ動画はこちらです。(音が鳴るので注意。)


liumOS Adlib MIDI再生デモ

virtio-netドライバの追加とICMP, DHCPへの対応

前菜を楽しんでいただけたところで、メインディッシュですが、なんとliumOSにネットワーク通信機能を追加しました。

たとえば、pingに応答するデモはこちらです。


liumOS pingデモ

冒頭でさらっと流されていますが、なんとDHCPIPアドレスその他が自動的に割り当てられている点にも注目です!

f:id:hikalium:20201217022248p:plain
ipコマンドで割り当てられたIPアドレスを確認している図

NICドライバとしては、仮想入出力デバイスvirtioのうちのひとつである、virtio-netを実装しています。また、GPD Micro PCで採用されているRTL8168というRealtek社製のNICについても現在ドライバの実装を進めているところです。

UDP通信への対応、ソケットシステムコールの部分的実装、簡単なブラウザアプリの実装

さて、pingができるなら、もうなんでもできますね!だって、パケットを送受信するだけですから。(本当に?)

ということで、UDPプロトコルと、ソケット関連システムコールをいくつか実装し、d0iasmさんによって書かれた簡易ブラウザアプリケーションが動くように環境を整備しました。

たとえば、このようにliumOS内のクライアントから、Linux上で動くサーバーにリクエストを投げればHTMLが返ってきますし、

f:id:hikalium:20201217025756p:plain
liumOS内からHTTPのやりとりをしている図

これをパースしてMarkdownに整形するという簡易ブラウザまで動いてしまいます!

f:id:hikalium:20201217025918p:plain
同じHTTPのやりとりだが、出力をパースしてMarkdownに整形して出力している簡易ブラウザの図

どうですか?自作OSでも、これくらいなら少し頑張ればできるんです!

Web+DB Press Vol.120の特集「自作OS×自作ブラウザで学ぶ Webページが表示されるまで」をd0iasmさんと執筆した

さて、このようなことをしていましたら、ありがたいことに技術評論社Web+DB Press編集部よりお声がけをいただき、自作OSと自作ブラウザを通して、Webページが表示されるまでの流れを、文字通り上から下まで一通り追ってゆく記事を執筆させていただく機会を得ました。

gihyo.jp

Webページが表示されるまでに、HTTPのリクエストがどのようにしてパケットにまで落とし込まれて、レスポンスとしてのHTMLがどのようなパスを通って運ばれてゆき、最終的に目に見える形になるのか、ということを解説した、合計36ページの特集となっておりますので、面白そう!と思っていただけたなら、ぜひ書店で内容を確認したり、購入して読んでいただけたりしたら大変嬉しく思います。12/24発売です!

この特集の概要の紹介や、デモを交えた動画を近日中にアップロードする予定ですので、そちらもお楽しみに!

www.youtube.com

今後の展望など

やりたいことは無限にあって永遠に楽しめるのが自作OSのよいところですが、ある程度目標を立てておいたほうが物事を進めやすいのは確かです。ということで、いくつかここで私がやりたいと思っていることを書き連ねておくことにします。

GUIサポートを向上させる

現在のところ、liumOSにはほとんどGUIと呼べるものがありません。画面描画を行うAPIはアプリケーションに対して提供されていませんし、入力インターフェイスについても、ほんの少し前にPS/2マウスのサポートがやっと入ったほどです。そのため、先ほど紹介した特集でも、CUIブラウザを実装するのがやっとの状態でした。

せっかくブラウザの下回りができたなら、CSSで文字を大きく表示したり色を変えたり、なんなら文字列を<blink>させたいですよね?(とはいえblinkタグはすでに廃止されていますが…。)

ということで、ある程度の描画がアプリケーション側からできるような仕組みを近いうちに用意し、ついでにブラウザの実装も拡張したいなあと思っています。

RustでOS本体を書き直す

現在のliumOSはC++で書かれています。C++が使えるだけでもC言語に比べれば大きな進歩だったのですが、やはりメモリ安全性という面ではC言語と五十歩百歩と言わざるを得ません。最近応用が広がってきたRustであれば、より安全にプログラムを書くことができます。ということで、Rustでカーネルを書き直すことを現在検討しています。すでに、Rustで書かれたカーネルを従来のliumOSローダーが起動できるところまでは確認しているため、あとは実装するだけという状況なのですが、うまいことインクリメンタルにできないものか、考えつつ現在進めているところです。(まあ、いつか気分が乗った時にえいやっと書き換えることになりそうな気がしますが…。)

ネットワーク機能の拡張

現在のliumOSのネットワークまわりはかなりアドホックに実装されており、複数のNICをうまく扱えない、ソケットの実装がはりぼてすぎる、たまにドライバがこけるなどの問題が発生しています。特に、ドライバを書くというのは自作OSにとって頭の痛い問題ですが、私としてはネットワークドライバほど実装しておいしいものは他にないのではないかと考えています。というのも、基本的な機能としては「パケットを送信する」「パケットを受信する」の2つしかありませんし、ネットワークの先になにがあるかを私たちは意識する必要がないからです。たとえば、自作OSでファイルを保存できるところまで到達しているケースはかなり少ない(liumOSはNVDIMMに対応しているのでなんでも保存できる!…と言い張ることができるかもしれない)ですが、ネットワーク通信さえ対応してしまえば、保存すべきファイルをネットワーク越しに送信するようにすることで、自作OS側でドライバを書かなくて済む可能性が出てきます。(もちろん、各種プロトコルを実装する必要がありますが…。)あと、自作OS同士が独自のプロトコルで通信するのをみてみたい、という気持ちもかなりあります。ということで、おそらくネットワーク周りの機能はそれなりに重点的に進めていくことになるような気がしています。

おわりに

そういうわけで、今年もいろいろな機能がliumOSには生えましたし、今後も生やしていくつもりではいるのですが、ここで大事なことをひとつ。

自分が楽しいと思えることをやっていきましょう!最初から完璧なものを作る必要はありません。なにせ、一番のユーザーは自分自身なのですから。

自分以外のユーザーが出てきたら、そのときはそのときでまた考えましょう!(なおliumOSにはついにアプリ開発者(@d0iasm)が登場したので、大急ぎでテストを書いたりドキュメントの修正をしたりしていました。もちろんこれも楽しいからやってるんですけどね!)

ということで、このご時世で家にいる時間も多くなってきていると思いますので、皆様ぜひ暖かい部屋でゆっくりしながら、のんびりとした自作OSライフをお楽しみください!ではでは!

SECCON 2020 OnlineCTF writeup -- SCSBX:Reversing

概要

f:id:hikalium:20201011204310p:plain

今年も例年のように、チームHarekazeの一員として出ました。チームの結果は2123点で11位/579チーム(何らかのFLAGを提出したチーム数)でした。 そのうち、私はSCSBX:Reversingを解いて129ポイントを稼ぎました。(st98さんが一人で1552ポイントも稼いでおり目を回しています。)

あと、同じSCSBXをテーマにしたSCSBX:Escapeや、脆弱なkernel moduleの秘孔を突くkstackという問題にも挑戦しましたが、時間内に解くまでにはいたりませんでした。

ということで、挑戦した各問題の解法 or 挑戦のようすを書いておきます。

SCSBX:Reversing

f:id:hikalium:20201011194731p:plain

ソースコードの公開された独自のバイトコード処理系と、それ向けに書かれたアプリケーションのバイナリが与えられています。 そのアプリケーションは、入力がフラグであるか否かを教えてくれるものでした。

$ ./scsbx seccon.bin 
FLAG: hogehoge
Wrong!!

ということで、その処理をみてみれば、どのような入力が期待されているのか、つまりフラグがわかりそうです。ということで、読んでいきましょう。

VMソースコードを読んでみる

ファイルとしてはこんな感じ。

$ ls
Makefile          instr_logic.cpp  main.cpp
instr_arith.cpp   instr_mem.cpp    scsbx.cpp
instr_branch.cpp  instr_sys.cpp    scsbx.hpp

C++で書かれているんですねー。たとえば、scsbx.cppの中をみてみると、

void SCSBX::__cpu_exec(u8 instr)
{
  u32 val;

  switch(instr) {
    /* Memory Operation */
  case INS_PUSH:
    val = *(u32*)(&code[pc+1]);
    __stack_push(val);
    pc += 4;
    break;
  case INS_POP:
    __stack_pop();
    break;
  case INS_DUP:
    __stack_dup();
    break;
  case INS_XCHG:
    __stack_xchg();
    break;
  case INS_LOAD32:
    __mem_load32();
    break;
  case INS_LOAD64:
    __mem_load64();
    break;
  case INS_STORE8:
    __mem_store8();

という感じで、非常に素直に書かれています。

また、DOCS.md というファイルも含まれていたのでみてみると、命令形式についての説明やメモリレイアウトについても書かれていました。めっちゃ親切。

### Instruction
Every instruction except for `push` is 1-byte long.
`push` accepts a 4-byte value to push into the stack.
**SCSBX is proudly open-sourced!**
Check the source code for more details.
0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

とりあえず、PUSH命令以外はすべて1バイトのスタックマシンということがわかったので、さくっとディスアセンブラを書きます。というか、VMソースコードを改造して、オプションを渡したらdisasしてくれるようにしました。その出力がこちら。

$ ./scsbx ../seccon.bin -d
00000000: 20 00001000: push
00000005: 20 DEAD0000: push
0000000A: 62: map
0000000B: 20 00000256: push
00000010: 34: call
00000011: 20 0000020A: push
00000016: 34: call
00000017: 20 47414C46: push
0000001C: 20 DEAD0004: push
00000021: 28: store32
00000022: 20 0000203A: push
00000027: 20 DEAD0008: push
0000002C: 27: store16
0000002D: 20 00000006: push
00000032: 20 DEAD0004: push
00000037: 61: write
00000038: 20 00000040: push
0000003D: 20 DEAD000A: push
00000042: 60: read
00000043: 20 00000008: push
00000048: 20 0000010E: push
...

やっぱりスタックマシンだし長いですね。というわけで、じっとこれを見つめてデコンパイラごっこをします。

私なりのやり方としては、大体以下のような手順を踏みました。

  1. 分岐命令を境に、命令列をブロックに分ける。
  2. 上から辿っていって何をやっているかお気持ちを理解する
  3. 複雑な部分では、スタックを書いて追いながらロジックを推定する

たとえばこんな感じに、スタックの使われ方を書いていったり、

<check_loop()>
/*
[0] k
[1] v
*/
00000135: 20 00000000: push
0000013A: 22: dup
0000013B: 20 00000001: push
00000140: 20 00000001: push
00000145: 23: xchg
00000146: 41: sub
/*
[0] k - 1
[0] k
[1] v
*/
00000147: 20 00000008: push
0000014C: 42: mul
/*
[0] (k - 1) * 8
[0] k
[1] v
*/
0000014D: 20 DEAD000A: push
00000152: 40: add
/*
[0] (k - 1) * 8 + 0xDEAD000A
[0] k
[1] v
*/

...(省略)

00000183: 20 00000001: push
00000188: 23: xchg
/*
[2] k
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/
00000189: 20 00000001: push
0000018E: 20 00000001: push
00000193: 23: xchg
00000194: 41: sub
/*
[2] k - 1
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/

これを元にC言語ベースの擬似コードに落とし込んだりしてみました。

int main(int argc, char *argv) {
  // 00000000
  // map [DEAD0000 - DEAD1000)
  InitEncFlag();
  // 0000020A
  *(uint32_t *)&mem[0] = 0x06D35BCD;
  // 00000017
  // read 0x40 bytes into *0xDEAD000A
  strncpy(&mem[0xA], "SECCON{[\x20-\x7e]+}", 0x40);
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  // [] i
  while(i) {
    // 0000004E
    // 000000DD
    // Stack after 00000097
    // []: *((8-i) * 8 + 0xDEAD000E) = v1
    // []: *(8-i) * 8 + 0xDEAD000A) = v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      // []: p
      // []: v1
      // []: v2
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    // []: p
    // []: v1
    // []: v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  };
  // check if flag_buf is same as flag_encrypted
  ...
}

さて、デコンパイラの気持ちを理解したところで、このプログラムは大体以下のような処理を行っていることがわかりました。

  1. 作業用のメモリ領域[0xDEAD0000 - 0xDEAD1000)をmapする
  2. そのメモリ領域に符号化されたフラグを展開する(0xDEAD004A から0x40バイト)
  3. 0xDEAD0000番地に値0x06D35BCDを格納する(おそらく何らかのシード値、後のロジックで使われる)
  4. ユーザーからの入力を受け取る(0x40バイト、これは0xDEAD000A番地から0x40バイトの空間に格納される)
  5. 上の擬似コードに書いたような処理を行って、ユーザーからの入力を符号化する
  6. 符号化した入力(0xDEAD000Aからの0x40バイト)と、展開しておいた符号化済みのフラグ値(0xDEAD004Aからの0x40バイト)を比較する
  7. それらが一致したらCorrect, 一致しなければWrong!!と出力して終了する

さて、肝心のstep5の処理ですが、擬似コードとしてはこんな感じです。(enc()がその処理)

uint32_t random_num(uint32_t v) {
  // 00000216
  uint32_t *dead0000 = (uint32_t *)&mem[0];
  *dead0000 = (*dead0000 * 0x77F - 0x32A) % 0x0x305EB3EA;
  return ~(v ^ *dead0000);
}
void enc() {
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  while(i) {
    // 0000004E
    // 000000DD
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  }
}

要するに、8バイトを1セットとして符号化するのを8回くりかえすことで、8*8 = 64 = 0x40バイトの領域を符号化しているわけです。 また、random_num()と仮においた処理は、0xDEAD0000番地のメモリ内容という状態を持っているため、呼び出しには副作用があります。 とはいえ、基本的にやっていることは、その8バイトの中で前後4バイトずつの部分をxorしているだけで、入力と出力は各桁ごとに独立に変化します。 結局、random_num()の状態に注意しつつ、8バイトずつのセットの各文字を順に確定させてゆけば、フラグがわかりそうです。(これなら最大でも256 * 8 * 8通り調べればいけますね。)

というわけで、このアイディアをかんたんなC言語のプログラムに落とし込みました。

#include <stdint.h>
#include <stdio.h>

uint32_t dead0000 = 0x06D35BCD;

uint32_t random_num(uint32_t v) {
  // 00000216
  dead0000 = (dead0000 * 0x77F - 0x32A) % 0x305EB3EA;
  return ~(v ^ dead0000);
}

uint64_t enc(uint64_t v) {
  uint32_t v1 = v >> 32;
  uint32_t v2 = v;
  uint32_t p = 3;  // pushed at +00000098
  while (p) {
    p--;
    uint32_t c = v2;
    v2 = v1;
    v1 = random_num(v1) ^ c;
  }
  return ((uint64_t)v1 << 32) | v2;
}

uint8_t mem[64];

void InitEncFlag() {
  // 00000256
  *(uint32_t *)&mem[4 * 0x0] = 0x46761223;
  *(uint32_t *)&mem[4 * 0x1] = 0x54BEA5C5;
  *(uint32_t *)&mem[4 * 0x2] = 0x7A22E8F6;
  *(uint32_t *)&mem[4 * 0x3] = 0x5DB493C9;
  *(uint32_t *)&mem[4 * 0x4] = 0x055D175E;
  *(uint32_t *)&mem[4 * 0x5] = 0x022FCD33;
  *(uint32_t *)&mem[4 * 0x6] = 0x42C46BE6;
  *(uint32_t *)&mem[4 * 0x7] = 0x6D10A0E8;
  *(uint32_t *)&mem[4 * 0x8] = 0x53F4C278;
  *(uint32_t *)&mem[4 * 0x9] = 0x7279EC2A;
  *(uint32_t *)&mem[4 * 0xA] = 0x5491FB39;
  *(uint32_t *)&mem[4 * 0xB] = 0x49AC421F;
  *(uint32_t *)&mem[4 * 0xC] = 0x49AB3A37;
  *(uint32_t *)&mem[4 * 0xD] = 0x47855812;
  *(uint32_t *)&mem[4 * 0xE] = 0x5718BB05;
  *(uint32_t *)&mem[4 * 0xF] = 0x0540FB5B;
}

int main(int argc, char *argv[]) {
  InitEncFlag();
  char buf[64 + 1] = "SECCON{........";

  for (int i = 0; i < 8; i++) {
    for (int k = 0; k < 8; k++) {
      for (char c = 0x20; c <= 0x7E; c++) {
        buf[k] = c;
        uint32_t prev_dead0000 = dead0000;
        uint64_t e = enc(*(uint64_t *)buf);
        uint8_t *p = (uint8_t *)&e;
        dead0000 = prev_dead0000;
        if (p[k] == mem[k + i * 8]) {
          break;
        }
      }
    }
    uint64_t e = enc(*(uint64_t *)buf);
    printf("%.8s", buf);
  }

  return 0;
}

気をつけるべき点は、forの中でencを実行する際に、毎回dead0000の内容を戻しているところですね。(少し冗長ですが色々ためしていたせいである。)

というわけで、以下のような出力を得ました。

$ ./solve2 
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}~~

SECCON{の後にはTがきそう(きっと英語のメッセージ的にTheとかがきそうだから)と思っていて、最初の8桁だけ試してTがでてきてわーいと思っていたのですが、全部出してみたら乱数フラグでちょっと意外でした。(ちゃんと通ってほっとした。)

追記

このアルゴリズムはFeistel構造と呼ばれるものらしい。

ja.wikipedia.org

SCSBX:Escape

ところでこのSCSBX(SecCon SandBoX), reversingだけでなくsandboxの問題としても登場していました。

f:id:hikalium:20201011202618p:plain

こちらは、リモートで動いているSCSBXにいい感じのバイナリを送りつけて、思い通りの動きをさせてshellをゲットしような!という問題だったのだと思います。

SCSBXの説明文にこんな一文がありますが、

### Direct Memory Access
SCSBX allows the program to directly access to the host memory.
This may sound dangerous but the program can only use the 32-bit
address space. Since SCSBX runs on a 64-bit machine with PIE enabled,
there's no way the user can read/write the VM memory directly.

明らかにこれはアヤシイ!と思いますよね。というわけで、じっとソースコードを見つめると、

void SCSBX::__sys_unmap()
{
  u64 address = ((u64)__stack_pop()) & ~0xfff;
  __assert_address_valid(address);

  for(auto itr = memmap.begin(); itr != memmap.end(); ++itr) {
    if (address == itr->first) {
      memmap.erase(itr);
      munmap((void*)address, itr->second);
      return;
    }
  }

  throw MEMORY_ERROR;
}

ほう、munmapの戻り値を確認しないとは勇気がありますね?というところを見つけられます。これは何に役立つかと言うと、メモリマップで言う

0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

Guard Pageを除去するのに使えます。というのも、このGuard Pageは、実際にmapされているわけではなく、

SCSBX::SCSBX(u8 *_code, u32 _size)
{
  /* Guard page */
  memmap.push_back(std::make_pair((u64)STACK_BASE + (u64)STACK_SIZE_INIT,
                                  0x100000000 - (u64)STACK_BASE - (u64)STACK_SIZE_INIT));
}

という感じでVMの初期化時に「確保済みのメモリ領域」として予約されているだけなのです。この結果として、VMはこの領域にアクセスするとマップされていないのでSEGVがおきるし、マップしようにもマップ済みなのでmapを実行できない…はずなのですが、先ほどのようにmunmap命令が実行されると、munmapの結果にかかわらずこのmemmapというリストから除去が行われるため、なんとこの領域をmunmapしてから再度mmapすれば、普通にアクセスできるようになってしまうというバグがあったわけです。

で、ここにアクセスできると何がやばいかというと、Stackが伸びていくとやがてこのGuardPageにあたり、さらにそこを超えるとVM instance、つまりクラスSCSBXのインスタンスが確保されている領域を上書きできてしまうのです。

というわけで、たとえばこうすれば

  // unmap guard page
  instr_push(0xffff0000);
  instr_unmap();
  // map again
  instr_push(0x00010000);
  instr_push(0xffff0000);
  instr_map();

あとはstackをばんばん伸ばすだけでやがてこの構造体を上書きできるようになります。

class SCSBX {
private:
  /* fields */
  std::vector<std::pair<u64, u32>> memmap;

  u32 pc;
  int status;

  u8* code;
  u32* stack;
  u32 code_size;
  u32 capacity;
  u32 top;
...
  virtual void __assert_address_valid(u64 address);
  virtual void __assert_range_valid(u64 address, u64 size);
  virtual void __assert_resource_available(u64 address, u32 size);
...
};

しかもこの構造体、virtual関数としてアドレス範囲チェック系の重要な関数のポインタが記録されている場所でもあるので、ここをいい感じにRETを指すポインタように上書きすれば、チェックを全部回避することも、さらに任意のアドレスに実行を飛ばすこともできます。

…というところまでわかって、時間切れでした。ざんねん。

pythonが得意ではないので、hashのチャレンジレスポンスを解きつつ、ペイロードを突っ込むスクリプトを将来また書かなくてもいいようにここに貼っておきます。

from pwn import *
import itertools
import hashlib
import string
import sys

print(sys.argv[1])
f = open(sys.argv[1], "rb")
attack_bytes = f.read()

table = string.ascii_letters + string.digits + "._"

p = remote('pwn-neko.chal.seccon.jp', 19001)
ret = p.recvline().decode("utf-8") 
# ret = 'sha256("????LFx0jSq8mYA4oZC_.Kuw") = ca67aa308662f39b8e294a99120588102a94

hashval = ret.split("=")[-1].strip()
print(hashval)
suffix = ret.split("\"")[1].replace("?", "")
print(suffix)

for v in itertools.product(table, repeat=4):
    if hashlib.sha256((''.join(v) + suffix).encode()).hexdigest() == hashval:
        prefix = ''.join(v)
        break
else:
    print("[-] Solution not found :thinking_face:")

print("[+] Prefix = " + prefix)
p.sendline(prefix)
p.recvuntil('size')
p.sendline(str(len(attack_bytes)))
p.recvuntil('code')
p.sendline(attack_bytes)
p.interactive()

kstack

f:id:hikalium:20201011204833p:plain

なんか/proc/stackというファイルに対するioctlを生やすkernel moduleが入ったマシンにつながるので、そいつのバグを突いて権限昇格しようね、という問題だったようです。 QEMUで実行できるようイメージと引数の書かれたシェルスクリプトが一緒に配られていて、めちゃくちゃ親切でうれしかったです。

ioctlの仕様としては、ioctl(fd, CMD_PUSH, &value)を発行すると、その値がユーザーランドからカーネル空間のスタック(実体は各要素がkmalloc(GFP_KERNEL)で確保されたLinked List)に格納され、ioctl(fd, CMD_POP, &value)を発行すると、そのカーネル空間のスタックからユーザーランドに値がコピーされていく、というものでした。 ちなみに、そのLinked Listの各要素には、格納したタスクのtgidが一緒に記録されていて、あるtgidが記録したデータに対する操作はそのtgidからしかできないようになっていました。

これについては全然進捗がなくて、複数タスクから同時にPOP処理をかけたら、解放された領域を指し続けるLinked Listが構成できそうとか、pidがぐるっと一周したらどうなる?とか色々あったのですが、結局時間も割けなくてとけませんでした。もっとカーネルに詳しくなりたいですね。

作問者による簡易解説ツイート

感想

バイナリおいしい!あとカーネルむずかしい…。

全体的に、問題のクオリティがかなり上がっているという印象を受けました。とてもよいことだと思います。それに、何より問題を解くのが楽しかったです。(可視化とかも面白かった。)

運営のみなさん本当にお疲れ様でした!ありがとうございましたー!

ISUCON10予選 meguryohikaの記録

ISUCON10の予選にmeguryohikaとして @megumish_unsafe, @systemctl_ryoto と共に出たのでその記録です。

結果としては、初期スコア500点台から、900点台の、1000点に届きそうかな?というところまでは行けたものの、最後のベンチマーク前に複数台構成にしようとして失敗した結果スコアがつかずおしまいでした。来年もまたやりたいですね!

ISUCONは参加者だけじゃなくて運営にも降りかかる…

午前10:00から試合開始ということで、前日は人々とイカをやるのも午前1時までにとどめておき、無事健康的な午前起床を達成しました。

ところが、その少しまえに、こんなツイートが運営から…

ということで、私の目覚める前からISUCONは始まっていたようです。私たちの開始は昼ごろまで遅れたけれど。(運営のみなさんお疲れ様でした!)

正午までの暇を持て余して環境が整う

2時間の余裕を得た我々は、「二度寝するなよ!」というネタをやったり、眠気覚ましにご飯を買いにいく人々が出たりと自由な雰囲気が漂っていました。

私も、あまりにも暇だったので、ちょうど横にあるLinuxマシンを、負荷をかけている際のCPU統計などを表示するのに適したようにセットアップしたいなあという気持ちになって、apt updateしたり、NVIDIAGPUドライバを入れたりしていました。(なんとドライバを入れていなかったので、1024*768の解像度になっていた…これでは流石にきついと思ったので急いでセットアップした。)

そんなわけで、少し環境がリッチになったあたりで、試合開始が12:20からになるとの連絡が。やっていきましょう!

試合開始…からのポータルが503 Service Unavailable

我々はGoで実装を進めるつもりだった&初期実装がGoと書いてあったので、早速ベンチマーカーを回そうとしたところ…なんとポータルが503に。ISUCONむずかしいね…。

というわけで、しばらくベンチマーカーの結果は拝めそうになかったので、megumish氏はソースコードやリソースの退避とデプロイスクリプトの作成を、ryotoさんはbotを弾くnginx configをさっと書いてくれたり、ソースを読んでSQL的にヤバそうなところがないかをしらべてくれたりしていました。私はアプリを実際に触ってみて、遅い部分とか面白い部分がないかをしらべてみていました。「なぞって検索」なる、地図上に領域を描いて物件を検索できるページがあったのにはびっくりしました。また、今回は前回までと異なり、サイトへのログインという概念がなかったため、その点でも度肝を抜かれました。(ついつい/adminが存在しないか調べてしまったが、なかった…。)

14:00の定時報

前回までの反省と、チームでこれまで練習してきたことを生かして、今回は1時間ごとにさくっと進捗共有会をすることにしました。そして、進捗共有がおわったら、強制的に5分間休憩タイムをとることにしていました。これは体力を消耗しないという点では非常によい戦略だったと思います。(今までは終盤になると、精神的にもかなり疲れがきていたのですが、今回は最後までゆったりできたので割とおすすめです。)

このあたりで、megumish氏がデプロイスクリプトを完成させていて、次はredisを入れてキャッシュできるものはやっていこうか、という流れになっていました。 ryotoさんはAPIの各エンドポイントをみ終わって、いくつか修正できそうな点がみつかったので直していく、という話になっていました。

私は、やっと初のベンチを走らせてみて、nginxのログをkataribeでフォーマットしてどのエンドポイントを直すのがよさそうか議論する材料を用意しました。

Top 20 Sort By Total
Count   Total    Mean  Stddev    Min  P50.0  P90.0  P95.0  P99.0    Max  2xx  3xx  4xx  5xx  TotalBytes   MinBytes  MeanBytes   MaxBytes  Request
  105  40.860  0.3891  0.4355  0.046  0.178  1.085  1.397  1.698  2.000  103    0    2    0     1700275          0      16193      33967  POST /api/estate/nazotte HTTP/1.1
  411  33.686  0.0820  0.0246  0.031  0.078  0.115  0.123  0.151  0.206  411    0    0    0     4989248      12139      12139      12153  GET /api/chair/low_priced HTTP/1.1
  411  31.674  0.0771  0.0266  0.032  0.072  0.115  0.127  0.155  0.182  411    0    0    0     5500577      13383      13383      13398  GET /api/estate/low_priced HTTP/1.1
   86  14.241  0.1656  0.0457  0.087  0.157  0.234  0.247  0.271  0.271   86    0    0    0     1429937      16627      16627      16642  GET /api/estate/search?page=0&perPage=25&rentRangeId=1 HTTP/1.1
   67  10.303  0.1538  0.0388  0.093  0.138  0.213  0.223  0.259  0.259   67    0    0    0     1124707      16786      16786      16801  GET /api/estate/search?page=0&perPage=25&rentRangeId=2 HTTP/1.1
   72  10.238  0.1422  0.0348  0.094  0.132  0.194  0.205  0.230  0.230   72    0    0    0     1199601      16660      16661      16682  GET /api/estate/search?page=0&perPage=25&rentRangeId=0 HTTP/1.1

トータルでかかった時間としては、やはり「なぞって検索」が重く、次いで物件と椅子の安い順に上位20件をリストアップするlow_pricedが、一回一回は重くないものの、回数が多いためけっこう負荷になっていることがわかりました。あとは、検索部分が重く、今回のサービスの検索では、かなり多種多様な条件を指定できることがわかっていたので、何らかの高速化が必要だろうね、という話になりました。

例えば、searchで指定する条件には、各物件や椅子の属性(features)というのがあって、これはDBにはカンマ区切りの文字列として格納されているのですが、検索時にはそれらのAND条件を指定できる、というもので、当初の実装では全件リードが走っている状態になっており、まあ重いのは致し方ないかな、という感じでした。

改善のアイディアとしては、featuresの各要素は固定で50件であることから、各属性に対応するboolのカラム50列をDBに追加して、ついでにindexも貼ってあげればいい感じになるんじゃないか?と考えて、以後私はそれに取り組むことにしました。

ちなみに、初期状態でのベンチ終了時点では、データが3万件それぞれのテーブル(chair, estate)に入っており、初期データには2万9500件入っている、ということがわかっていました。なので、実行時に動的に増加する分は、最初は500件ということです。(おそらく、負荷レベルが向上すると、ここが増えたのでしょうが、残念ながらそこまで行きつきませんでした…。)

また、単一サーバー(1 core, 2GB RAM)でDB, Webアプリを同時に動かしている状態でベンチマークをかけても、CPU時間は100%に張り付く一方、メモリ消費量は500MBもいかない程度で、swapも全く発生していないという点に気付きました。かなりCPUに集中した負荷がかかっていたようです。当初、私はこれがMySQLのメモリ設定が厳しすぎるせいだと考えて、緩和する設定を入れてみたのですが、残念ながら全く使用量が増えなかったので、ボトルネックは別の部分にあったようです。

15:00の定期報告

このあたりで、megumish氏はGET chair/low_pricedの結果をキャッシュできないか奮闘していました。

ryotoさんは、全く貼られていなかったindexをDBに貼ったところ、100点程度のスコア向上がみられたと報告していました。

また、なぞって検索に関して、矩形で大まかに物件をフィルタしたあと、その各物件に対して、GIS関連の関数を用いて、描かれたポリゴンの内部にその物件が存在するか否かをチェックしているということがわかり、これをDBに毎回投げるのではなく、Goの側でうまく処理できないかということを検討していました。

私は、先ほど言ったMySQL周りのチューニングが効果ゼロだったことを報告して、もしかするとDBやアプリを複数サーバーに分散させる必要があるのかもしれないと言いつつ、とりあえずfeaturesをbooleanでDBの複数カラムに格納するものに着手するという話になっていました。

16:00の定期報告

megumish氏は、キャッシュの大まかな実装はできたけれど、うまくベンチが通らず四苦八苦していました。

ryotoさんは、椅子を購入すると、物件がrecommendされる(椅子が通るような玄関の間口をもつ家がリコメンドされるシステムだった!)機能のぶぶんを、事前にテーブルを作成することで高速化できないか挑戦していました。

私は、chairのfeaturesをカラム化することを引き続き挑戦していました。

17:00

ほぼ同上。だんだんつらくなってくるね。

f:id:hikalium:20200913000124p:plain
縦に長すぎるchairのschemaの図(実際にはf50まで続いたあと、さらに同じ個数のindexが張られている)

18:00

megumish氏は、キャッシュをするのはいいけれど、レースコンディションがおきたらどうなるんだろう?という問題に頭を悩ませていました。

ryotoさんは、椅子に合った不動産をおすすめする部分の改善目処がつきそうという報告をしており、それが終わり次第、なぞって検索に取り掛かるという目標を掲げていました。

私は、featuresをカラムにし終わったものの、なぜかベンチマークが通らない問題で時間をつぶしていました。(サーバーにデプロイしてみるとうまく動いているように見えた。)

糖分が足りなくなってきたので、ここらへんでクレープをたべました。おいしかったです。

f:id:hikalium:20200912233946j:plain

19:00

megumish氏の実装のバグが取れたとの報告。JSONが正しく吐けていなかったみたい。とりあえずうまくいったら、次は複数台構成の検討に入るとのこと。

ryotoさんは、物件おすすめ機能をあきらめました。というのも、冷静に考えると、事前計算をする処理はかなり重く、また椅子や物件を追加するAPIの時間制限はわりと厳しかったため、時間内に事前計算を終わらせられそうにないというのが理由でした。

今思えば、全部を事前計算せずとも、一度計算したものをキャッシュしておく、などの方策がとれたかもしれないなあ、という感想が浮かんできました。(後から振り返るとそういうアイディアが思いつく。)

私は、クレープの糖分をもってしてもバグを解決できず、なんでだーと頭を抱えていました。

さいご

最後ぎりぎりになって、ryotoさんがなぞって検索のジオメトリ計算の部分をgolangに持ってくることに成功し、これで+300程度になりました。

さらに、私もベンチマークが失敗する理由に気付き(デプロイ時に走るDB初期化と、ベンチマーク時に走るinitialize/内でのDB初期化で異なるデータを流し込んでいた)、なんとかマージに成功。

最終的に、これでスコアが900点ちょい出たのですが、複数台構成を試そうとしてぎりぎりまでryotoさんが頑張ったものの、間に合わず終了時刻を迎えました。いやはや、よくがんばりました…。

反省点

  • 複数台構成を練習時にもあまりできておらず、本番でも手間取って間に合わずじまいになってしまった。練習でできないことは本番でもできないよ!
  • 当初リストアップしていた修正できそうな点のうち、ひとつを見過ごしてしまっていた。(終わった後に気づいた。)
    • 報告会を定期的にしていたのは非常によかったが、ToDoの管理が不十分だった。見ないToDoに意味はないよ!
  • 複数台構成の件にもつながるが、本番サーバー以外に実行環境を用意できていれば、もう少し開発を効率的に行えたかもしれない。

まとめ

来年はさらに準備して望みたい…またがんばりましょう!おつかれさまでした!

f:id:hikalium:20200912235608p:plain
14:30頃のつかの間の15位の図

追記: チームメンバーのryotoさんとツイート被りしていたことが判明(終わるまで全く気づかなかった)(みんな考えることは同じである)

C言語から0番地へアクセスする方法についての個人的まとめ

発端はuchan_nos氏によるこのツイートでした。

それに対する私のリプライ:

私はこれで話が終わると思っていたのだが、どうやらそうではなかったらしく、色々な視点からの意見が加わりながら、話は混沌を極めたのでした…。

ということで、ここに私のこのツイートに対しての見解とか、わかったことをまとめておこうと思います。

私のリプライの背景について

uchanさんが求める「0番地にデータを書きたい」という課題設定を、私はこのように解釈しました。

  • C言語において、整数0をポインタに変換すると、それはNULLポインタになる
  • C言語において、NULLポインタへのアクセスは未定義動作である
  • したがって、0番地にデータを書くことはできないのではないだろうか?
  • これをすり抜ける方法はあるか?

これを受けて、私はこのように考えました。

  • NULLポインタへのアクセスが未定義となるのはコンパイル時の話である
  • ではコンパイル時にNULLポインタであるとコンパイラにバレなければ未定義動作にならないのではないだろうか?
  • じゃあアドレス1を代入してポインタをつくり、それを引き算して0番地へのポインタをつくれば、コンパイラは見逃してくれるのではないだろうか?

そして、以下のコード片が生まれたわけです。

uint8_t *p = 1;  p--; *p = v;

ここで、vは何らかのuint8_t型の書き込みたいデータである(と文脈からわかると期待)。

仕様上の問題

しかしその後、有識者の人々がにわかにざわつき始めた。そして、私の提示したコードはやはり動かないということをherumiさんがありがたくも指摘してくださったわけです。

では仕様上、単なる0番地への代入コードや、私の書いたコードがなぜうまく動かないのかをみていきましょう。

0をポインタにキャストするとそれはnull pointerになる (6.3.2.3 - 3)

この仕様によれば、整数定数0となるような定数式をポインタにキャストすると、それはnull pointerになる。 そして、null pointerは、いかなるオブジェクトや関数へのポインタとも等しくならないことが保証されている。

null pointerを用いた間接参照は未定義動作になる (6.5.3.2 - 4)

この仕様によれば、*演算子を用いた間接参照をするときに、その参照が「無効なもの」であるとき、*演算子の挙動は未定義となる。 ここでいう「無効なもの」には、null pointerも含まれると注釈102に書かれている。


したがって、0番地に1を書き込もうとして *(uint8_t *)0 = 1; と書いてもこれは未定義動作になる これは、整数定数0をポインタにキャストしたもの(uint8_t *)0がnull pointerであり(ここまでは定義された動作)、これへの間接参照が「null pointerを用いた間接参照」になるためである。

この、null pointerへの間接参照を回避するための方法として私が編み出したのがuint8_t *p = 1; p--; *p = v;であるが、これも以下の仕様によって「処理系定義」の動作になる。

整数からポインタへの変換は処理系定義である (6.3.2.3 - 5)

この仕様によれば、整数からポインタへの変換を行ってもよいが、その結果は処理系定義になるという。 つまり、たとえアドレス1を表現しようとして(uint8_t *)1と書いても、その内部表現が整数1と等しくなるとは保証されないということである。


したがって、uint8_t *p = 1; p--; *p = v;と書いても、最初のuint8_t *p = 1;の段階でpがどこを指しているかは処理系の動作に完全に依存し、1番地を指しているとは限らないため、私の提案した方法は残念ながら処理系定義の結果になる。

しかも、最適化によって、コンパイラ*p=v;のタイミングでpがnull pointerになることを推測してしまう場合があるらしく、そうするとこれは未定義動作になってしまう。(これがherumiさんにご指摘いただいた部分。)

まじか、最適化の結果未定義動作を踏むこともあるのか、つらいな…。

じゃあどうすればいいのか

これは多くの人がすでに指摘している通りで、かつ私も同意する結果なのですが、

「処理系定義の動作に依存することなくメモリの0番地にC言語から読み書きをすることは不可能である」

が答えです。

これは、そもそもC言語には「メモリの何番地」に該当する概念がなく、ポインタへの整数値の代入も処理系定義であることが原因であるため、どうしようもありません。

なんとかできないの?

いくつかの点に目をつぶれば、まあ結果的に実現することは可能です。

*(uint8_t *)(0) = 1; とその派生

これは、今まで説明してきた理由によれば未定義動作となるため、鼻から悪魔が出てきてもおかしくありません。早速Compiler Explorerでやってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t *)(0) = 1; with -O0 OK OK
*(uint8_t *)(0) = 1; with -O3 NG(ud2) NG(ud2)

残念ながら悪魔は出てきませんでしたが、最適化を有効にするとやはりud2ですね。しかし、最適化を無効にすれば一応期待通りのコードが得られます。

と、ここで気になるWarningがclangから出力されていることに気付きました。

<source>:3:5: warning: indirection of non-volatile null pointer will be deleted, not trap [-Wnull-dereference]

    *(uint8_t *)(0) = 1;

    ^~~~~~~~~~~~~~~

<source>:3:5: note: consider using __builtin_trap() or qualifying pointer with 'volatile'

1 warning generated.

Compiler returned: 0

ほう?volatileをつけると何か変わるんですかね。やってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t * volatile)(0) = 1; with -O0 OK OK
*(uint8_t * volatile)(0) = 1; with -O3 NG(ud2) NG(ud2)

あれ、volatiileをつける場所、こっちじゃないの?

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(volatile uint8_t *)(0) = 1; with -O0 OK OK
*(volatile uint8_t *)(0) = 1; with -O3 NG(ud2) OK

なるほど、こうすれば、clangでは最適化を有効にしていても、volatile 修飾をすることで有効なコードを吐いてくれるようです。gccは規格通りだめみたいですが…。

uint8_t *p = 1; p--; *p = 1; とその派生

この手法は、null pointer dereference が未定義動作になる挙動を回避した(つもりだった)ものです。(もちろん、この挙動は整数からポインタへの変換という処理系定義の動作に依存しています。)

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t *p = 1; p--; *p = 1; with -O0 OK OK
uint8_t *p = 1; p--; *p = 1; with -O3 NG(ud2) NG(ud2)

しかし、最適化によって前半の結果pがnull pointerになることが推測されてしまっており、その結果ud2が生成されていますね。ということで、最適化を無効にするためにvolatile をつけてあげましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t * volatile p = 1; p--; *p = 1; with -O0 OK OK
uint8_t * volatile p = 1; p--; *p = 1; with -O3 OK OK
volatile uint8_t * p = 1; p--; *p = 1; with -O3 NG(ud2) OK

おー、確かに動きはしますね。でもポインタ演算が入ってしまいますが…。

volatile修飾をポインタ変数ではなく、その指す値につけてみると、ポインタ演算に関する最適化は両者とも走るようになり、gccでは想定通りud2になったんですが、なんとclangでは最適化された結果である0番地への代入mov byte ptr [0], 1 が生成されました。 clangはvolatileがついてたらnull pointerのdereferenceも許容してくれるってことみたいですね。

追記: -fno-delete-null-pointer-checks というフラグをコンパイル時につける

clangとgccの両方で期待通り動くようです。gccのドキュメントにおける記載はここにあります。なるほどud2になる挙動は、「絶対に引っかかることがコンパイル時にわかっている(実行時に行われる可能性がある)null pointer checkを、コンパイル時にud2に置き換える」という最適化によるものなんですね。

ところで調べていたら、このコンパイルオプションが追加されたClangへのパッチを見つけました。曰く:

Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers.

More details : https://lkml.org/lkml/2018/4/4/601

なるほど、やはりLinux Kernel開発者からの熱い要望があったんですね。(lkmlのリンクに飛ぶと、Linusの熱い言葉が見れるのでおすすめです。)入ったのが比較的最近(2018年中頃)というのも面白いですね。

(Thanks @herumi, @kazuho !)

追記: __attribute__((address_space(1))) をポインタ変数につける(LLVM/clang限定)

id:uenoku さんのコメント曰く:

id:uenoku

既出でしたら申し訳ないですが、clangならllvm::NullPointerIsDefinedをtrueにすることを考えれば良いので以下のようなコードがかけます https://godbolt.org/z/x5cXf4

Compiler Explorerでの結果 のうち、f1, f2は前述した-fno-delete-null-pointer-checksによるもの、f3がこの手法です。

address_space(n) というattributeは、そのポインタがどのアドレス空間のものかを指定するもので、デフォルトはaddress_space(0)になっています。そしてこのAddress Spaceの値が、null pointerへの参照が定義された動作かを判定するLLVMの関数bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) @ lib/IR/Function.cpp に渡されます。この関数の実装を見てみると:

bool Function::nullPointerIsDefined() const {
  return getFnAttribute("null-pointer-is-valid")
          .getValueAsString()
          .equals("true");
}

bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) {
  if (F && F->nullPointerIsDefined())
    return true;

  if (AS != 0)
    return true;

  return false;
}

AS(address space)が0以外のとき、常にtrueを返すことがわかります。これで、null pointerへの参照が未定義動作ではないよとコンパイラに教えることができるわけです。なるほどー。

(Thanks id:uenoku !)

まとめ

  • C言語はやはり難しい
  • こんな記事を書いて時間をつぶしている場合ではなかった
  • でも仕様書を読むのも楽しいのでおすすめ

参考文献

  • (n1570.pdf)

2019年概観

2019年を時系列に振り返る。Twitter埋め込みが大量にあるので注意。

  • 1月
    • さくらインターネットで委託研究員としてNVDIMMたちと戯れていた(4月まで)
    • liumOS本格始動
    • VR環境が整備された
    • 試される大地に行った




  • 5月
    • プラサミ+自作OSもくもく会

  • 6月
    • 某社の面接を受けた
    • ハッカーズチャンプルー登壇 @ 琉球大学 docs.google.com

  • 7月

  • 8月
    • ドワンゴでバイトを開始した(継続中)
    • 某社からオファーをもらったので承諾
    • セキュキャンでRuiさんとともにCコンパイラゼミの講師を担当
    • ラボユースキャンプに卒業生として参加




まとめ

今年もなんだかんだ活発に活動していた。本当にえらい!

タスクを積みすぎるところは反省点なので、来年はある程度自制することも覚えましょう。(すでに積み上がったタスクを眺めながら。)

来年もよい年になりますように。