アジョブジ星通信

進捗が出た頃に更新されるブログ。

バタフライ図も行列も見たくない人のための高速フーリエ変換

高速フーリエ変換FFT)を実装しようと思って、まず理論を知らねばと調べたところ、まったくチンプンカンプンだったのですが、とりあえず、なんとか証明を追うことができました。というわけで、バタフライ演算の図を見てもなんもわからん人が FFT を実装するための資料として、この記事を書き残したいと思います。

参考にした資料は、富永氏による GNU Scientific Library に関するドキュメントの翻訳の「FFT アルゴリズム」の「基数2の時間空間法」です。周波数空間については追っていません(どっちでやっても計算量は同じなので)。

続きを読む

いまさら使う TPL Dataflow

みなさん、並列処理、書いてますか? つらい、つらいよね、わかるよ。

ある部分は高速化のために並列で実行し、ある部分は整合性を取るために直列で実行し、入力ジョブのキューが膨大にならないように流量を調節しながらジョブを入力して……。こんなプログラムをバグなく書くなんて、それはもう大変で、コーナーケースからぼろが出てくる出てくるって感じになります。

さて、そんな面倒な並列プログラミングを支えてくれるライブラリが、結構前(2014 年の NuGet パッケージが存在している。概念自体は 2011 年からある?)から提供されています。名前だけはご存知(個人的な感想) System.Threading.Tasks.Dataflow、通称 TPL Dataflow です。 .NET Core では標準で含まれていますし、そうでない環境では NuGet からダウンロードできます。強いですね。

公式ドキュメントも比較的しっかり書かれています。日本語翻訳がまともかというと何とも言えないですが、翻訳が崩壊しているページよりはまともです。

今まで、イマイチ使いどころがわからない & 複雑で学習コストが高そうだと感じ、避けてきたのですが、触ってみたらかなり便利ということがわかったので、各種オプションによってどのような挙動をするのかをまとめて、今後使うときのメモとしておこうというのが、この記事の目的です。前半では、この目的通り、使い方を説明します。後半では、同じく TPL(Task Parallel Library) という枠で提供されている Parallel クラスや、似たような概念を提供する Reactive Extensions、System.Threading.Channels との比較を行います。

環境は、 .NET Core 2.2 を想定しています。 System.Threading.Tasks.Dataflow の古いバージョンでは、存在しない機能があるかもしれません。

  • TPL Dataflow の使い方
    • インターフェイスの紹介
    • 最初の例: 入力データに対して処理を直列に行う
    • データを変換する TransformBlock とリンク
    • 完了、キャンセル、例外の伝搬
    • ブロック中の SynchronizationContext
    • 並列化
    • 出力データの順番
    • バッファー上限と SendAsync
    • 複数のブロックに同じデータを送信する
    • 入力データをまとめて配列にする BatchBlock
    • 最短一致モード、最長一致モード
  • ちょっと大規模なサンプル: マネージドキューサービスからジョブを取り出し、実行するワーカー
    • 経緯
    • マネージドキューサービスのモデル
    • データフローブロックを組んでいく
    • 完成形
  • 類似品との比較
    • Parallel, PLINQ
    • Reactive Extensions
    • System.Threading.Channels
  • まとめ
続きを読む

Kubernetesで隔離Mastodonネットワークを作った

はじめに

前回、 k3s の紹介をしましたが、もともと Kubernetes に興味を持ったのは Docker のネットワークが、簡単だけれど細かい設定ができないという問題を抱えていたからです。細かく設定したネットワーク環境を使って何がやりたかったかというと、 Mastodon をはじめとする、 ActivityPub サーバーを隔離環境で動かし、他人のサーバーに迷惑をかけずに通信を眺めたかったのです。さらに、それを使って ActivityPub サーバーを自作するところまで行きたいのですが、正直もう体力と時間がないので、他に作っている方の動向だけ眺めていることにします……。

というわけで、要件はこんな感じです。

  • Mastodon サーバーを 2 つ立ち上げ、相互に通信できるようにする
    • 実環境に近くするため HTTPS で通信する
    • サーバー名として「mastodon1.fediverse.local.azyobuzi.net」、「mastodon2.fediverse.local.azyobuzi.net」を割り当て、解決できるようにする
  • 隔離ネットワーク外のサーバーにアクセスできないようにする
  • Mastodon サーバー間の通信内容を簡単に覗き見ることができるようにする

KubernetesMastodon を構築した!といった記事は星の数ほどあると思いますので、この記事のポイントを挙げると、ローカル限定の隔離ネットワークであるところと、サーバー間の通信を監視できる UI を用意したところです。

先に完成品をお見せしておきます。トゥートしたりふぁぼったりすると、相手サーバーにリクエストが飛んでいることが確認できます。

ここまでできて、とりあえずやりきった感が強く、飽きたので、あとはこれを読んだみなさんが、より強いシステムを作って、 ActivityPub サーバーの開発に役立てていただけると幸いです。

このブログ記事では、構成要素や、 k3s での構築について書き残しておきたいと思います。 k3s に限らない構築方法については、 GitHub に置いておきます。

続きを読む

k3s の中身とメモリ使用量の調査

コンテナに対するあらゆる需要に応えるソリューションこと Kubernetes が流行りですね(雑なはじめかた)。僕も何度かこのビッグウェーブに乗ろうとしましたが、新しい概念の多さと、ズボラ運用には厳しいメモリ使用量で断念してきました。動かしたい環境というのが、メモリ 1GB の VPS だったり、メモリ 1GB の ARM シングルボードコンピュータなわけで……。

そんなところに颯爽と登場したのが k3s です。公式の謳い文句から解説しているページは「k3s kubernetes」で検索すれば無限に出てくると思うので、そちらにおまかせして、じゃあ実際どうやってあの馬鹿でかい Kubernetes をコンパクトにパッケージングしたのかについて見ていきたいと思います。

シングルバイナリ?ホンマか?

シングルバイナリと聞くと、ぱっと思いつくのは BusyBox のように、すべてのプログラムをまとめてコンパイルして、起動時のコマンド名で実行するプログラムを切り替えるスタイルですが、 k3s ではどうでしょうか? 答えは、半分そうで、半分違います。

続きを読む

僕のラブコメ史

21歳になって半年弱経ちました。段々アニメを見る体力はなくなり、今期のアニメなんてひとつもわからないような状況ですが、逆に、大学生になって得た財力によって、ライトノベルを読むことが増えたと思います。とはいえ、ラノベにかける予算は、月2000円程度にしているはずですし、ひどく遅読ですから、ガチ勢からしたら、そんなの読んでるうちに入らないというレベルだと思います。

さて、なんで今日この記事を書こうと思ったかというと、「幼なじみ萌え ラブコメ恋愛文化史」を読み終え、読書メーターにレビューを書いたけれど、文字数的に物足りないなぁ、自分の感想も含めて書きたいなぁと思ったからです。最近は幼なじみ属性がマイブームなので、その背景をアウトプットしておきたいと思います。はい、ただの自分語りです。

(本当は、こういう恥ずかしい話は自作 CMS を完成させて、検索エンジンクローラーに見つからない場所に書き残しておこうと思っていたのですが、完成しそうにないし、書きたいと思っている間に書かないと、何もアウトプットできない人間になってしまいそうなので、書くことにしました。)

続きを読む

主人公の好感度問題 完結編

遡ること 2017 年 4 月、「主人公の好感度問題」と題された、あの一大プロジェクトが、今日完結する……。

「主人公の好感度問題」とは

生まれて初めて買ったエロゲ―こと、ワガママハイスペック(以下ワガハイ)をプレイしていたときのこと。このゲームは、共通ルートでの選択肢の選び方によって、各キャラの好感度パラメータが変化していき、最終的に好感度の高いキャラと恋人になって、あとは一本道のストーリーを見るだけの、ほぼほぼ完全に紙芝居なのですが、その選択肢の選び方について、多くのパターンが未尋ルートに向かうように感じられました。そこで、選択肢の選び方全パターンを実際に試してみて、本当に未尋ばかりなのか、つまり未尋はちょろいのかについて検証してみようというプロジェクトが始動しました。

f:id:azyobuzin:20181028175910p:plain

TL;DR

選択肢の積み重ねでエンディングが分岐するタイプのゲームにおいて各エンディングの出現率を調べるために、Docker上にWineで動かしたゲームを C# からX Window Systemプロトコルで操作して、選択肢を全探索させた話。

https://mstdn.maud.io/@unarist/100976963847747421

続きを読む

カーネルモードドライバーをそこそこデバッグできるようにした話

はじめての仮想HID」では、デバッグ手段が手に入れられなかったという終わり方をしてしまいましたが、それなりにデバッグできるようになったので、その方法をまとめておきます。

1. KdPrintEx でログを出力する

KdPrintEx マクロを使うと、デバッグビルド時(DBG 定数があるとき)に雑に Windows にログを残すことができます。 Microsoft から出ているサンプルでもよく使われているので、これで出力したログを見れる環境を作っていきます。

これを読んで理解できれば終わりですが……。

KdPrintEx の使い方

KdPrintEx はこのように使います。

KdPrintEx((ComponentId, Level, Format, フォーマットのための可変長引数));

マクロの都合上、括弧が二重になっています。

ComponentId には、どこで発生したログかを表す値を入れますが、サードパーティーのドライバーの場合は「DPFLTR_IHVDRIVER_ID」を指定しておくのが無難そうです。

Level はいろいろな指定の仕方がありますが、基本的には次の中から選べば良いと思います。

  • DPFLTR_ERROR_LEVEL
  • DPFLTR_WARNING_LEVEL
  • DPFLTR_TRACE_LEVEL
  • DPFLTR_INFO_LEVEL

Format および、その後に続く可変長引数には、 printf 形式でログの内容を指定することができます。最後に改行を入れておかないと、出力されるログも改行されないので、前後の出力がまとまってしまうことに注意してください。

以上を踏まえて、私はこのようなヘッダーファイルを作っておき、利用することにしました。カーネルモードでのログは「カーネルからのログ」という情報しかないので、ログの文字列の最初にプロジェクト名を入れておくことで、あとでフィルターをかけることができるようにしておきます。

#define TraceEnterFunc() KdPrintEx((DPFLTR_IHVDRIVER_ID, DPFLTR_INFO_LEVEL, "ProjectName: Enter %s, IRQL: %d\n", __FUNCTION__, KeGetCurrentIrql()))
#define TraceErrorStatus(funcName, status) KdPrintEx((DPFLTR_IHVDRIVER_ID, DPFLTR_ERROR_LEVEL, "ProjectName: %s returned 0x%x in %s\n", funcName, status, __FUNCTION__))

#if DBG

#define TraceInfo(msg, ...) DbgPrintEx(DPFLTR_IHVDRIVER_ID, DPFLTR_INFO_LEVEL, "ProjectName: " msg "\n", __VA_ARGS__)
#define TraceError(msg, ...) DbgPrintEx(DPFLTR_IHVDRIVER_ID, DPFLTR_ERROR_LEVEL, "ProjectName: " msg "\n", __VA_ARGS__)

#else

#define TraceInfo(msg, ...)
#define TraceError(msg, ...)

#endif

DebugView でログを見る

ログを見るのには、 Sysinternals の DebugView を使用すると便利です。

オプション次第(/v)ですべてのログを見ることができますが、それをやるとログの収集が追い付かず、ものすごく遅延が発生していくので、先に表示するログの設定をしておきます。

  1. レジストリHKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Debug Print Filter キーを(なければ)作成します。
  2. ログの ComponentId に対応する DWORD 値を作成します。例えば DPFLTR_IHVDRIVER_ID なら「IHVDRIVER」という名前にします。
  3. その値を、表示させたいレベルのビットマスクにします。例えば、 INFO だけを表示(実際には値が 0 である ERROR も表示される)したいならば、 1 << DPFLTR_INFO_LEVEL(3) = 0x8 を値とします。 ERROR から INFO まですべてを表示させる場合は、すべてのビットを立てるので 0xF にします。(この範囲外の Level を指定した場合はまた話が変わってくるけれど割愛)

f:id:azyobuzin:20180809013052p:plain

準備ができたら、管理者権限で DebugView を起動し、 Capture Kernel を有効にするとログが見れるようになります。 Visual Studio から配置する場合は、 WDKRemoteUser 上で起動しておけば良いと思います。

f:id:azyobuzin:20180809014549p:plain

バグなのかと思いますが、一度 Capture Kernel を有効にして、 DebugView を終了させた後、再度 DebugView を起動すると、アクセス拒否エラーが出ます。再起動しないと直らなくてつらい。。

DebugView はリモートでも使用することができます。デバッグターゲットのマシンでは、管理者権限で「Dbgview /a /k」を起動します。 /a がエージェントモード、 /k がカーネルログの有効化です。ログを見る側のマシンでは、普通に DebugView を起動し、 Computer → Connect を選択して、 IP アドレスを入れると接続できます。こちら側でも Capture Kernel を有効にする操作が必要です。

2. KDNET でリモートカーネルデバッグ環境を構築する

以前の記事(はじめての仮想HID)では、 Visual Studio からプロビジョニングを行いましたが、そのときプロビジョニングは失敗していたはずです。しかし、次へをクリックすると「Status: Configured for driver testing」と表示されていたので成功したものだと思っていましたが、実際にはドライバーの配置のみが行える状態で、デバッグが出来ない状況でした。そこで、さらに調査を続けたところ、 Windows 10 では Visual Studio からのカーネルデバッグができなくなったようです。

This feature is not available in Windows 10, version 1507 and later versions of the WDK.

Setting Up Kernel-Mode Debugging over a Network Cable in Visual Studio | Microsoft Docs

そこで、とりあえず WinDbg 経由でリモートアクセスできる程度には環境を整えてみようということでやってみました。これを行うと Visual Studio からデバッグ実行を行ったとき、 Visual Studio 上から WinDbg を操作することができるようになりますが、 Visual Studio のエディタ上で設定したブレークポイントが反映されるようなことはありません。残念。

参考情報

これを読めば、この記事を読む必要がないリストです。

NIC の確認

リモートカーネルデバッグを行うには、対応している NIC を使用しなければいけません。つまり無線では無理ということっぽいです。

対応している NIC リストは次のページにあります。

今、テスト環境として使用しているマシンの、有線の NIC のプロパティはこのようになっています。

f:id:azyobuzin:20180809021138p:plain

赤丸がベンダーID、青丸がデバイスIDです。ベンダーID 1969、デバイスID 1091 はリストにあるので使えそうです。よかった。

次に、 NIC の場所をメモしておきます。

f:id:azyobuzin:20180809021411p:plain

この場合は、左から順に「3.0.0」と記録しておきます。これが後で使う Bus Parameter になります。

Visual Studio でプロビジョニング

せっかくなので、作業の半分くらいを Visual Studio にやってもらいます。どうせ Visual Studio から配置するわけですし。

Visual Studio で Configure Devices を開き、 Add New Device すると、勝手にポートやキーが設定されていると思います。ここで、 Bus Parameter の欄に先程調べた値を入力してプロビジョニングを行うと、この後の設定が完了した後から、 Visual Studio 上で WinDbg の操作を行うことができるようになります(その必要がないなら KDNET だけ設定しても良いです)。

f:id:azyobuzin:20180809021817p:plain

プロビジョニングには失敗しますが、デバイス一覧で「Status: Configured for driver testing」となっていれば完了です。

有線での設定を行いましたが、追加で、 WinDbg にアクセスできなくていいから、デプロイだけ無線でやりたいという場合は、さらに Add New Device して、プロビジョニングを行わず、無線 NIC 側の IP アドレスだけ指定して保存すれば、無線でデプロイできるようになります。この場合でも DebugView でログを見ながらデバッグできます(私はこの構成でやっています)。

KDNET でリモートカーネルデバッグの設定を行う

  1. C:\Program Files (x86)\Windows Kits\10\Debuggers\x64 から kdnet.exe と VerifiedNICList.xml を取ってきて、ターゲットマシンの C:\KDNET にコピーします。
  2. C:\KDNET 上で管理者としてターミナルを開き、 .\kdnet <ホストマシンのIPアドレス> <プロビジョニングで設定したポート番号> を実行します。
  3. 再起動すれば完了です。

もし、プロビジョニングを行っていない場合は、ポート番号は適当な値を使用し、実行結果として表示されるキーをメモしておいてください(bcdedit /dbgsettings でも確認できます)。

これで設定は完了です。あとは WinDbg でポートとキーを指定すれば、デバッグが開始されます。

f:id:azyobuzin:20180809024545p:plain

ブレークすると本当に Windows が丸ごとフリーズするので面白いです(他に活用できてない……)。ドライバー関連だと、 !devnode 0 1 とやると、デバイスマネージャーみたいな表示が得られます。

まとめ

ひとまず、ログを眺めながらデバッグすることができるようになって一安心です。しかし、 KMDF の内部ログとかを含めて見たい場合は、また別なことをしないといけないっぽく面倒だなぁといったお気持ちです。