<style>

u {
text-decoration-color: gray;
text-decoration-style: wavy; /* 波線 */
}

</style>

# メッセージキューの概要

# キューの構造
メッセージキューのデータ構造は [ghost_ring](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L505-L517) 構造体で定義される。この構造体のインスタンスは共有メモリを介してユーザー空間に公開される。
　後述する ghost_msg のリングバッファとして実装されていて、以下のような構造になっている。


:::warning
:dart: 実際は ghost_ring のデータ構造は [ghost_queue_header](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L242-L249) 構造体でラップされている。
:::
ghost-userspace ではこのデータ構造を [LocalChannel](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/channel.h#L113-L145) というクラスでラップしている。どのように ghost_ring が使われているのかは、このクラスの実装を眺めてみるといい。

# メッセージの構造
メッセージのデータ構造は [ghost_msg](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/channel.h#L113-L145) 構造体で定義される。この構造体のインスタンスが1つのメッセージに対応し、ghost_ring のバッファを介して伝達される。

データ構造は以下のようになっていて、メッセージの種類・ペイロードの長さ・シーケンス番号・ペイロード、の4つから構成される。

$\tt type$ には、メッセージの種類を示す値が格納される。
メッセージの種類には、タスク関連のものとCPU関連のものがある。タスク関連のものは [$\texttt{MSG_TASK_*}$](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L275-L286) という列挙子で定義され、CPU関連のものは [$\texttt{MSG_CPU_*}$](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L289-L295) という列挙子で定義されている。

$\tt length$ は、payloadフィールドの長さを示す値が置かれる。ghost_msgは可変長の構造体である（ただし8の倍数のサイズで揃えられる）。

$\tt seqnum$ には、メッセージ発行時点でのタスクのバリアが渡される。

$\tt payload$ には、メッセージ固有のデータが格納される。ここのデータ構造は $\texttt{ghost_msg_payload_*}$ という構造体で定義されている。例えば $\texttt{MSG_TASK_NEW}$ のペイロードのデータ構造は [$\texttt{ghost_msg_payload_task_new}$](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L299-L307) 構造体である。

ghost-userspace では [Message](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/channel.h#L21-L73) というクラスでラップされている。

# メッセージキューの関連付けとWAKEUPリスト
メッセージキューには2つの重要な概念がある。それは、
* メッセージを**どのメッセージキューにpushするのか**？
* メッセージキューに新しいメッセージがpushされたときに**どのagentを起こすのか**？

である。

特にPer-CPU型のスケジューラではagentの数とメッセージキューの数は管理するCPUの数だけ存在することになる。そのとき、agentが管理しているghOStスレッドのタスクメッセージが、他のagentに転送されないようにしなければならない。そのため、**これら2つのポイントを理解し、適切に設定できるようにする**必要がある。

## メッセージはどのメッセージキューにpushされるのか？
まず最初に、メッセージがどのキューにpushされるのか、について見ていく。
以降、メッセージがpushされる先のメッセージキューのことを**dstQ**と呼ぶことにする。

dstQは、メッセージの種類によって決められ方が変わる。

タスク関連のメッセージの場合は、**そのタスクの** task_struct にdstQの情報が含まれている。具体的には [task_struct.ghost.dst_q](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/linux/sched.h#L597) が指す先の ghost_queue がdstQとなる。タスクのdstQを設定するには　GHOST_IOC_ASSOC_QUEUE システムコールによって行う。詳しくは「ghOSt FS」を参照。

CPU関連のメッセージの場合は、**そのCPUに紐付いたagentの** task_struct にdstQの情報が含まれている。上と同様に task_struct.ghost.dst_q が指す先の ghost_queue がdstQである。この設定も同様に、GHOST_IOC_ASSOC_QUEUE システムコールによって行う。

## 新しいメッセージがpushされたときに、どのagentを起こすか？
キューに新しいメッセージがpushされたときに起こすagentの情報は [ghost_queue.notifier](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost.c#L2082) に置かれている。この設定は GHOST_IOC_CONFIG_QUEUE_WAKEUP システムコールによって行われる。

# メッセージ発行関数
スケジューラを実装するには、メッセージがどういったタイミングで発行されてくるのかを理解しておく必要がある。ghOStの思想的にカーネル側のソースコードを深く理解しておく必要はないはずだが、一応カーネル側でのメッセージ発行処理を見てみることにする。

まず、カーネルがメッセージを発行するときに必ず呼び出す関数が $\texttt{task_deliver_msg_*}$ という関数である。例えば MSG_TASK_NEW メッセージを発行するときには [$\texttt{task_deliver_msg_task_new}$](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost.c#L4581-L4610) という関数を必ず呼び出す。

つまり **MSG_\* タスクがどういうときに発行されているのかを知りたいときは、task_deliver_msg_\* という関数がどのように呼ばれているのか**を探ればいい。

# タスク関連のメッセージ
このメッセージはタスクの状態が変化するたびに発行される。
ghOStではタスクの状態を以下のようにモデル化している。

**Per-CPU型**の場合

**Centralized型**の場合

いくつかのポイントをまとめる。

* ghOStスレッドは他のスケジューリングポリシーのスレッドから移動してくることになっていて、直接的にghOStスレッドを作成することはできない（後述）。
* 各状態の名前はスケジューラの実装によって好きに定義されている（例えばrunnableをqueuedと名付けたりrunningをoncpuと名付けたり）。
* スケジューラの実装によっては**paused状態**など特殊な状態も定義されていたりする。
* Cenralized型では、runnable状態で MSG_TASK_PREEMPT や MSG_TASK_YIELD が送られてくることもあるらしい（詳しくは[ここのコメント](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/edf/edf_scheduler.cc#L306-L310)）。
* Cenralized型では、blocked状態で TASK_BLOCKED が送られてくることがある（詳しくは[ここのコメント](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/edf/edf_scheduler.cc#L279-L282)）。
* MSG_TASK_SWITCHTO という現在の実装ではまったく送られてくることのないメッセージもある、、、

以下ではタスク関連のメッセージについてそれぞれまとめる。メッセージ固有のデータ構造については重要な部分のみまとめている。

## MSG_TASK_NEW
スレッドがghOStスレッドとなったときに発行されるメッセージ。
**他のいかなるタスクのメッセージよりも先行して発行される**ことが保証されている。

このメッセージが発行されるタイミングとしては、以下のようなものがある。
* 別のスケジューリングクラスからghOStクラスへ移動してきた場合
* ghOStスレッドが新しくスレッドを生成した場合（ghOStポリシーが引き継がれる）

payloadのデータ構造（[ghost_msg_payload_task_departed](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L299-L307) 構造体）は以下のようになっている。
| 型 | フィールド名 | 意味 |
|-|-|-|
| uint64_t | gtid | 新しいスレッドのgtid
| uint64_t | parent_gtid | このスレッドの親スレッドのgtid
| uint64_t | runtime | このスレッドの実行時間
| uint16_t | runnable | このスレッドが実行可能状態か（そうでない場合はblocked状態として解釈される）
| int | nice | nice値
| ghost_sw_info | sw_info | このスレッドに対応するステータスワードの位置
| uint64_t | agent_data | BPF用

## MSG_TASK_WAKEUP

スレッドが起床したときに発行されるメッセージ。sched_class.task_woken の中でこのメッセージは発行されている。

以下の情報が一緒に送られてくる。どのタスクが起こされたかやCPUの情報などが渡される。

| 型 | フィールド名 | 意味 |
|-|-|-|
| uint64_t |gtid | 該当タスクの識別子
| int | last_ran_cpu | タスクが最後に実行していたCPUの番号。必ずしもタスクが最後に スケジュールされたCPUとは一致しないことに注意。
| int | wake_up_cpu | タスクが起床したCPUの番号。基本的には last_ran_cpu と一致するが、waker_cpu と一致することもあるらしい。select_task_rq で選ばれたCPUがここに設定される。
| int | waker_cpu | そのタスクを起床させたCPUの番号。

## MSG_TASK_DEAD
スレッドの状態が TASK_DEAD となったときに発行されるメッセージ。

メッセージのペイロードは以下のように簡潔になっている。
| 型 | フィールド名 | 意味 |
|-|-|-|
| uint64_t | gtid | 該当タスクの識別子

## MSG_TASK_DEPARTED

タスクが ghOSt の管理化から外れるときに発行されるメッセージ。例えば、sched_setscheduler システムコールによって、タスクのスケジューリングポリシーが変更されたりすると、このメッセージが発行される。
　agentがこのメッセージを受け取ったら、タスクを管理対象から外すための処理を行う。例えば、ランキューに入っている可能性もあるので、その場合はランキューから取り外したりする。

メッセージのペイロードで渡されるデータ構造は `ghost_msg_payload_task_departed` 構造体で定義されている。
| 型 | フィールド名 | 意味 |
|-|-|-|
| uint64_t | gtid | ghOStの管理対象から出ていったタスクの識別子。
| char | **was_current** | メッセージ送信時点で、そのタスクがRUNキュー上で実行状態だったか、を意味するフィールド

## MSG_TASK_YIELD

タスクがyieldするときに発行されるメッセージ。agentはこのメッセージを受け取ると、そのタスクをrqの最後尾に移動させる、などの処理を行う（ポリシーに応じて変更）。

## MSG_TASK_BLOCKED

タスクが実行可能状態でなくなったときに発行されるメッセージ。agentはこのメッセージを受け取ると、該当タスクをRUNキューから取り外す、などの処理を行う。


## MSG_TASK_PREEMPT

ghOStタスクがプリエンプトされたときに送信されるメッセージ。より優先度の高いタスクが実行可能状態になると、ghOSt タスクはプリエンプトされてこのメッセージが送られてくる。一緒に送られてくるデータ構造には was_latched というものがあり、どのタイミングでプリエンプションが起きたのかを教えてくれる。

was_latched がセットされているときはラッチされたタスクがプリエンプトされたことを意味する。ラッチされたタスクとは、次の PNT で選ばれるタスクのことである。PNT の前にプリエンプトが起きると、このフィールドがセットされる。


# CPU関連のメッセージ
タイマー割り込みが起きる度に発行されるメッセージ MSG_CPU_TICK などがある。**いつでも MSG_CPU_TICK が発行されてくるのではなく、ghOStスレッドが実行状態のときにCPUが割り込みがあったときだけ発行される**ことに注意。

また、このメッセージがプッシュされるキューについても注意が必要。タスク関連メッセージは、そのタスクが関連付けられたキューにメッセージをプッシュすることになっているが、**CPU関連メッセージはそのCPUに紐付いたagentが関連付けられているキューにメッセージがプッシュされる**ことになっている。よくagentとメッセージキューの関連付けを忘れてしまうことがあるので注意。

以下ではCPU関連のメッセージについてそれぞれまとめる。メッセージ固有のデータ構造については重要な部分のみまとめている。

## MSG_CPU_TICK
ghOStスレッドを実行中にタイマー割り込みが発生すると送られてくるメッセージ。

このメッセージは**オプショナル**で、ghOStFS の enclave_\<id>/deliver_ticks の値を1にすると、メッセージが発行されるようになる。**デフォルトでは0**となっていて、メッセージは送られてこないので注意。

payloadのデータ構造（[ghost_msg_payload_cpu_tick](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/include/uapi/linux/ghost.h#L402-L406)）は以下のようになっている。

| 型 | フィールド名 | 意味 |
|-|-|-|
| int | cpu | tickが起きたCPUのid。 |
| int | is_agent | このtickが起きたときに実行していたスレッドがagentスレッドか。 |

このメッセージを発行するカーネル側の関数は [cpu_deliver_msg_tick](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost.c#L4385-L4400) であり、ghost_sched_class の task_tick コールバックの内部から呼び出されている。

## MSG_CPU_AVAILABLE
**cpuがavailableになったとき**（つまり、CFSタスクなどがrqに存在しなくなったとき）**に送信されるメッセージ**。このメッセージは**optional**であり、デフォルトでは発行されないことになっている。

cpuのavailabilityをagentが知る方法としては、ステータスワード内のflagsをポーリングする、というのもある。スケジューラの実装では、cpuのavailabilityの変化を検知するのに、どちらの方法を使っても良い、と説明されている（[コミット](https://github.com/google/ghost-kernel/commit/6bb7e055d3d2bfede75ea6f9416041554d1436f6#diff-0a057b44c774d5794417194559e3274fec17ba44de756bd3ffd138bc631442d0R52)を参照）。このメッセージが追加されたのは比較的新しく、BPFスケジューラ向けの機能となっているみたいである。

## MSG_CPU_BUSY
MSG_CPU_AVAILABLEと対をなすメッセージ。cpuがbusy状態になったとき（availableの逆）に発行されるメッセージになる。

詳しくはMSG_CPU_AVAILABLEの説明を参照。