私のひらめき日記

気持ちをめも

ABCIシステムの使い方

ABCIシステムについて

GPUの環境を整えるのに、オンプレorクラウドかを状況に応じて選択する場合、双方メリット、デメリットがある。オンプレの場合は伝聞だと、運用がとても大変らしい。対して大手クラウドサービス(AWS, GCPなどでGPUインスタンス)を用いる場合は、便利だが、変動費とのトレードオフになる。

今回は第3の選択肢として、2018.8に運用開始したABCIシステムを検討の上で使用してみた1ので、概要を述べる。ABCIとは産業技術総合研究所が構築運用しているAI向けクラウド型計算システムであり、上記のクラウドを使う場合に比べて運用費が1/10くらいに(つまり、一桁!)抑えられるのが一番のメリットだ。

もし、中規模~大規模の機械学習の案件が有り、GPU資源が必要な場合は、一度比較検討してみるのも良いだろう。

なお本記事は、一個人として使用した知見であるので、間違った情報を記載しているかもしれない。より正確な情報は下記の公式ドキュメントを見るか、直接問い合わせをしてみてください。

reference

ABCIを使うにあたってのメリット・デメリット

まず、いきなりコマンドやら使い方のコツの説明をされても困ると思うので、使用に適するかどうかのメリット・デメリットを上げたいと思う。ソフトウェアスタックは https://abci.ai/ja/about_abci/software.html にある。

メリット

  • 同性能でコストがAWSGPUインスタンスと比べて1/10に抑えられる。GPUがTesla V100で高性能 https://abci.ai/ja/about_abci/computing_resource.html
  • クラウドなので、運用コスト(人件費含め)がかからない。
  • 現状知名度がそれほど高くないため、ほとんど混雑していない。自身は100+ノード規模を借りて実際に運用基盤を構築しているが、ノードが確保できないことはまったくないといって良い。
  • 国産のため、問い合わせは比較的スムーズに行える。

デメリット

  • すぐに利用できるわけではない。使用手続き等必要です2 https://abci.ai/ja/how_to_use/custom.html
  • AWSインスタンスと異なり、非管理者としての使用に限定されるので、CentOSだが、yumコマンドなどは使用できない。使用コマンドが少々特殊(yumの代わりにmoduleコマンド、Dockerの代わりにHPC向けのコンテナライブラリSingularityなど)。 Dockerは使用できるものの、特にprivate imageは(docker loginが管理者権限を要求されるので、)直接使用できない。(ただし、後述するように回避方法はある) docker-composeとかも使用できないよ。

  • 情報が公式ドキュメントくらいしかない。ABCI自体の利用に関しては日本語で書かれたドキュメントがあるが、Singularityについては、ほぼ英語の公式ドキュメントしかありません。

  • 例えば、Webサービス等の運用の一部として用いるのには不向きかもしれない。

ABCIの概要

前章では、そもそも利用に適しているのかのメリット、デメリットを上げた。本章では、インフラを構築するために知っておくべきor知っておくと捗る点をいくつか述べたいと思う。

f:id:knknkn11626:20190418105341p:plain https://portal.abci.ai/docs/ja/01/ より

ABCIシステムでは、インタラクティブノード上にloginして、計算ノードにjob(scriptの内容)を投げることで、機械学習の計算をさせる。

ログインはsshのトンネリングを経由してインタラクティブノードにログインする3

# ABCI_USER=...
ssh -vvv -L 10022:es:22 -l ${ABCI_USER} as.abci.ai
# on the other terminal
## -XC: インタラクティブノードへX転送を有効に
ssh -XC -p 10022 -l ${ABCI_USER} localhost
# enter interactive node..

インタラクティブノードに入った後は、スクリプトを用意する。自分の場合は、ansibleを利用して各種構成ファイルを自動で準備できるようにした:

# Before starting ansible, prepare the ssh-tunneling.
ssh -vvv -L 10022:es:22 -l ${ABCI_USER} as.abci.ai
# In the other terminal, we initialize and configure the application related scripts within the ABCI system.
ansible-playbook -u ${ABCI_USER} -i ./inventory/abci_hosts abci.yml
.
├── abci.yml
|   ├── inventory
|       ├── abci_hosts
├── abci.yml
├── roles
    ├── abci
        ├── files
        │   └── ...
        └── tasks
            └── main.yml
  • inventory/abci_hosts
[tag_Role_abci]
127.0.0.1
[tag_Role_abci:vars]
ansible_port = 10022
# abci.yml
- hosts: tag_Role_abci
  user: ${ABCI_USER}
  gather_facts: yes

  roles:
    - abci

その後、計算ノードにjobを投げる。

# ABCI_GROUP=..
qsub -g ${ABCI_GROUP} -l rt_F=1 script.sh

qsubというコマンドはHPC用のJob Schedulerのコマンドであり、後述する。

ノード間では、グループ領域4 (/group1/${ABCI_GROUP} or /group2/${ABCI_GROUP})が共有になっているため、出力ファイル等はここに置くようにすると良い。

Note) インタラクティブノードはあくまでqsubなどのjob schedulerを走らせるためのフロントであって、機械学習プログラムなどを動かすノードでないので、注意すること。See https://portal.abci.ai/docs/ja/01/#15


使い方の流れとしてはこれが基本だが、コアのプログラムはSingualrityというHPC用のコンテナライブラリを用いる。また、ノードの状態を自動で監視するためにJob Scheduler command(qsub, qstat, qrstat)を使用する。使用方法にコツが有るため、次章で述べる。

ABCIのツール群

https://abci.ai/ja/about_abci/software.html にある中で

あたりの使い方をみていく。Hadoop, Sparkは使用する機会がなかったので、割愛。

  • module コマンドについては、公式ドキュメントか、ABCI docsにも、 https://portal.abci.ai/docs/ja/05/ に書いてある。基本的にyumの代わりに用いるイメージで、もうちょっと柔軟なことをしたければ、Singularityというコンテナライブラリを利用して、所要の処理をコンテナでラップすれば良い。

Singularity

Singularityとは、HPC向けのコンテナライブラリで、GPU仮想化も--nvオプションを付ければ対応できる(ちょうど、nvidia-dockerの--runtime=nvidiaと対応している)。ここでは、DockerとSingualrityの技術的な差異については述べずに、専ら利用者の立場からの利用のコツについて述べる。

Note) singularityのversionは2019.4現在、2.6.1しか使用できないことに注意:

$ module display singularity
-------------------------------------------------------------------
/apps/modules/modulefiles/runtimes/singularity/2.6.1:

module-whatis    singularity 2.6.1
conflict     singularity
setenv       SSL_CERT_DIR /apps/modules/modulefiles/runtimes/singularity/certs
prepend-path     PATH /apps/singularity/2.6.1/bin
prepend-path     LD_LIBRARY_PATH /apps/singularity/2.6.1/lib
prepend-path     MANPATH /apps/singularity/2.6.1/share/man
-------------------------------------------------------------------

使用する際は、module load singularity/2.6.1とするだけでよい。

なので、本記事ではSingularity 2.6について説明する。(3以降も存在するが、2.6との後方互換性はなかったような気がする。) 詳細は、 https://www.sylabs.io/guides/2.6/user-guide/index.html を確認してほしい。

Singularity imageの作成方法

Singularityのimageを作成、使用する方法はざっくり4つある。3番目の方法が最も学習コストが高いが、確実に動作する。4番目の方法は実務上便利で、コアの機械学習プログラムをこの方法を用いてimageとして作成した:

  1. publicなDocker imageであれば、singularity pull docker://${docker_image_name}:${version}5

  2. Singularity Recipe(これはDockerfileのSingularity版に当たるImage作成するための構成ファイル)によってimageを作成する

  3. SingularityHub(これは、DockerHubと似たようなやつ)に所要のImageがあるかどうか探してみる

  4. Docker2Singularityを用いて、Docker imageからSingularity Imageに変換することで、Singularity Imageを使用できるようにする

もし、publicなDocker imageを使用する場合は、singularity pullコマンドが使用できる:

$ singularity pull docker://centos:latest
WARNING: pull for Docker Hub is not guaranteed to produce the
WARNING: same image on repeated pull. Use Singularity Registry
WARNING: (shub://) to pull exactly equivalent images.
Docker image path: index.docker.io/library/centos:latest
Cache folder set to /home/****/.singularity/docker
[1/1] |===================================| 100.0%
// <skip>
Singularity container built: ./centos-latest.simg
Cleaning up...
Done. Container is at: ./centos-latest.simg

docker imageの種類によっては、singualrity imageと互換性が合わず、使用できない可能性があるので、その場合は2,3を検討する。また、ABCIシステムは非管理者権限での実行となるので、docker loginを使用できず、privateなdocker imageをpullできない(と思われる)。その時は、4を検討する。

2番目は正攻法なのだが、可搬性が乏しい。というのも、もし、Dockerfileを事前に作成してある状況下において、新たにSingularity Recipeという構成ファイルをSingularityという(ABCIでしか使わないであろう)ライブラリを使用するためだけに作成するのは、時間がかかる。さらに良くないことに、DockerfileとこのSingularity Recipeは結構書き方が異なるので、学習コストがやや高いと感じた。

なので、どうしてもSingualrity Recipeを使わなければならない、という時以外は使用を避けたほうが良いかもしれない。自分自身は、後述する方法でMySQLがdocker imageから変換すると、singualrity上で使用できず、(解決方法が調べても情報ないので)仕方なしにMySQLのSingularity Recipeを作成した6

3番目は、一見すると良い解決方法に見えるが、所要のsingularity imageがあるとは限らないのですよね.. この場合は、4番目、それでもだめなら2番目の方法を使うしかない。

4番目のDocker2Singularityを使用する方法は、主に、既存のprivateなdocker imageがある場合、有効な方法である。自分の場合、C++で使用できるようにtensorflowをsourceからbuildしたいがprivate repositoryで閉じた範囲での使用を検討していたため、Dockerfileを作り、image化し、その後、docker2singularityを用いて、singularity imageに変換して、社内のS3に置くようにしていた7

各種コマンド

singularityの使用方法例としては、 https://portal.abci.ai/docs/ja/09/ にある。ここでは、自身が使用しているコマンドについてまとめる。

# 普通の使い方
# similar to docker pull
## `shub://aaaa/sample`はsingularity hubからimageを登録できるようにしておく
singularity pull --name ${APP_NAME} shub://aaaa/sample
# あるいは、ABCIではS3が使用できるので、singularity imageをdownloadする(予め、docker2singularity等でsingularity imageを作成しておく)
# aws s3 cp s3://${BUCKET_NAME}/app.simg ${APP_SIMG_PATH}
# --nv: GPU仮想化 c.f) https://www.sylabs.io/guides/2.6/user-guide/appendix.html#a-gpu-example
singularity exec --nv ${APP_SIMG_PATH} /bin/bash -c "..."

# backgroundでの起動(mysqlなど)
# https://github.com/ISU-HPC/mysql を改良
# docker pull
singularity pull --name $(basename ${MYSQL_SERVER_SIMG_PATH}) shub://bbbb/sample
# background で initialization
## --bindはdockerのvolumeに対応
singularity instance.start --bind ${MYSQL_DATADIR}:/var/lib/mysql --bind ${MYSQL_SOCKDIR}:/run/mysqld ${MYSQL_SERVER_SIMG_PATH} mysqld
# mysql serverをstart(backgroundで)
singularity run instance://mysqld

dockerのcommandとは、厳密には1:1に対応しているわけではないが、似たように扱える。ただし、current directoryはSingularityの場合、${HOME}などで共有されている8。(ちょうどdockerの--volumeと同等の機能)

Job Scheduler

続いて、job schedulerについて述べる。 ABCIのdocumentとしては、 https://portal.abci.ai/docs/ja/03/ が対応しているので、基本的な操作というよりは、使い勝手を向上させるためのtipsについて述べる。

qsub

qsubは計算ノードにjobを走らせるのに必要なコマンドで、ABCIシステム上で機械学習プログラムを動かすのに必須のコマンドである。man pageはhttps://docs.hpc.qmul.ac.uk/using/man/man1/ にある。

自身は以下のようにaliasで定義している:

alias qsubg="qsub -g ${ABCI_GROUP} -j y -cwd -terse -M ${EMAIL_ADDRESS} -m sa -o ${LOG_PATH} -e ${LOG_PATH}"
alias qsub_full="qsubg -l rt_F=1"
alias qsub_gpu1="qsubg -l rt_G.small=1"
alias qsub_gpu4="qsubg -l rt_G.large=1"

-Mはemail addressを指定するが、slackに通知させるには、emailというapplicationを用いると、一意のemail addressが新規に発行されるので、それを利用すれば良い。 -m-Mで指定したemail addressにいつ飛ばすかで、以下のように指定できる:

# man qsubより
-m b|e|a|s|n,...
          `b'     Mail is sent at the beginning of the job.
          `e'     Mail is sent at the end of the job.
          `a'     Mail is sent when the job is aborted or
                  rescheduled.
          `s'     Mail is sent when the job is suspended.
          `n'     No mail is sent.

-terseは標準出力にYour job 218747 ("script.sh") has been submittedと表示される代わりに、job_id(218747)のみが出力されるようになる。 これは、-hold_jidと合わせて、直列でjobを走らせる際に用いると便利:

https://gist.github.com/knknkn1162/2bf87553f586e3d93489dda49197df89

他には、-ar ar_id optionが予約ノードを指定する際に必要だ。予約ノードについては、qrstat commandで詳しく述べるが、事前に予約したノードを使用する際のオプション。

qrsh

qrshはqsubとにているが、qsubとは違い、計算ノード上でコマンド操作を試行するために用いるコマンドである。https://portal.abci.ai/docs/ja/03/#34 に詳しく書かれているので、詳細は省くが、自分自身は以下のような補助関数を定めている:

# ~/.bash_profile
function launch() {
  local TYP=$1
  if [ -z $1 ]; then
    echo "default_type is rt_G.small"
    TYP="rt_G.small=1"
  fi
  qrsh -g ${ABCI_GROUP} -l $TYP -pty yes -display DISPLAY -v xterm /bin/bash
}

function launch_gpu1() {
  launch "rt_G.small=1"
}

function launch_gpu4() {
  launch "rt_G.large=1"
}

function launch_full() {
  launch "rt_F=1"
}

qstat

qstatは計算ノードの状態を表示させるためのコマンド。qstat -xmlxml形式に整形してくれるので、計算ノードの状態を定期的に監視させたい場合などはこのxmlをparseすることになる。自身はxmllintを用いて以下のように用いている:

# cache xml result
QSTAT_XML=`qstat -xml`
FILTER_TAG='s/<[^>]*>//g'
FILTER_ATTR='s/^.*"\(.*\)".*$/\1/'
COUNT=$(echo $QSTAT_XML | xmllint --xpath "count(//queue_info/job_list)" -)

if [ ${COUNT} -eq 0 ]; then
  return 1
fi

# This is an example of the xml-formmated output: When you exec `qsub` command multiple times, the number of job_list element should be more than one.
## $ qstat -xml | xmllint --xpath "//queue_info/job_list" -
## <job_list state="running">
##       <JB_job_number>228168</JB_job_number>
##       <JAT_prio>0.28027</JAT_prio>
##       <JB_name>bash</JB_name>
##       <JB_owner>****</JB_owner>
##       <state>r</state>
##       <JAT_start_time>******</JAT_start_time>
##       <queue_name>gpu@g0002</queue_name>
##       <jclass_name/>
##       <slots>10</slots>
##     </job_list>
for idx in `seq 1 $COUNT`; do
  JOB_XML=$(echo $QSTAT_XML | xmllint --xpath "//queue_info/job_list[$idx]" -)
  STATE=$(echo $JOB_XML | xmllint --xpath "//@state" - | sed -e ${FILTER_ATTR})
  JOB_NUMBER=$(echo $JOB_XML | xmllint --xpath "//JB_job_number" - | sed -e ${FILTER_TAG})
  JOB_NAME=$(echo $JOB_XML | xmllint --xpath "//JB_name" - | sed -e ${FILTER_TAG})
  if [ ${STATE} = "running" ]; then
    STATE="r"
  fi
done
_FILTER_TAG_SPACE='s/<[^>]*>/ /g'

# 現在実行中のinstance名(gpu@g0999など)の一覧表示
function get_running_instances() {
  local QSTAT_XML=$(qstat -xml)
  echo ${QSTAT_XML} | xmllint --xpath "//job_info/queue_info/job_list/queue_name" - | sed -e "${_FILTER_TAG_SPACE}" | xargs -n1 echo
}

qrstat

qsub実行時にノードを取得する場合、72時間しか、連続で使用できない。もし、それ以上連続可動させたい場合は、予約ノードを用いる。予約ノードは前日の21:00まで予約でき、翌日の10:00から30日間連続でノードを専有させることができる9。詳細は、https://portal.abci.ai/docs/ja/03/#36 を参照のこと。

f:id:knknkn11626:20190418134519p:plain

予約ノードはqsubで使用する場合、-ar ${AR_ID}のように指定する10。2019.4現在、一度につき、32台まで同時に予約できる。(その際、一つのAR_IDが得られる。) もし、32台以上使用したい場合は、複数のAR_IDを発行することで対応する。

qrstatは予約ノードについての情報を入手できるコマンドで、こちらも、qrstat -xmlqrstat -ar ${AR_ID} -xmlxml形式で得られる。予約ノードについての詳細は、前小節のqsubの部分と、https://portal.abci.ai/docs/ja/03/#362 を参照のこと。以下のように使用している:

_FILTER_TAG='s/<[^>]*>//g'
_FILTER_TAG_SPACE='s/<[^>]*>/ /g'
_FILTER_ATTR='s/^.*"\(.*\)".*$/\1/'

function get_ar_info() {
  local QRSTAT_XML=`qrstat -xml`
  local AR_ID_XPATH="//qrstat/ar_summary"
  local AR_COUNT=$(echo $QRSTAT_XML | xmllint --xpath "count($AR_ID_XPATH/id)" -)
  for idx in `seq 1 $AR_COUNT`; do
    local AR_ID=$(echo $QRSTAT_XML | xmllint --xpath "$AR_ID_XPATH[$idx]/id" - | sed -e ${_FILTER_TAG})
    local AR_STATE=$(echo $QRSTAT_XML | xmllint --xpath "$AR_ID_XPATH[$idx]/state" - | sed -e ${_FILTER_TAG})
    # check "r": running state or "E": error (effective - running with error) state
    if [ $AR_STATE = "r" ] || [ $AR_STATE = "E" ]; then
      local SLOTS=$(qrstat -ar ${AR_ID} -xml | xmllint --xpath "count(//qrstat//ar_summary/granted_slots_list/granted_slots)" -)
      echo "$AR_ID,$SLOTS"
    fi
  done
  return 0
}

function get_running_instances() {
  local QSTAT_XML=$(qstat -xml)
  echo ${QSTAT_XML} | xmllint --xpath "//job_info/queue_info/job_list/queue_name" - | sed -e "${_FILTER_TAG_SPACE}" | xargs -n1 echo
}

function get_nonreserved_running_instances() {
  local AR_LIST=`get_ar_instances`
  local RUNNING_LIST=`get_running_instances`
  for ins in $RUNNING_LIST; do
    [[ "$AR_LIST" =~ $ins ]] || echo $ins
  done
}

function get_ar_instances() {
  for ar_id in `qrstat -xml | xmllint --xpath "//qrstat/ar_summary/id" - | sed -e "${_FILTER_TAG_SPACE}"`; do
    qrstat -ar $ar_id -xml | xmllint -xpath "//qrstat/ar_summary/granted_slots_list/granted_slots/@queue_instance" - | sed -e 's/queue_instance=//g' | sed -e 's/"//g' | xargs -n1 echo
  done
}

get_nonreserved_running_instancesはqsub時に予約ノードが使用されているかチェックするコマンドで、もし、予約していないノードが使用されている場合、リストアップするようになっている。


ほとんど、使用するにあたっての情報が公式document以外になかったので、かなり詳しめに書きました。AWSなどのクラウドサービスに慣れている方にとっては、多少job schedulerなどが独特だと思うので、最初のメリット、デメリット等勘案しながら、利用するのが良いと思います。


  1. 社内で https://www.globis.co.jp/news/release/20190418_globis.html の件で使用中。

  2. ここは社内のビジネスサイドの方たちに代行していただいたので、詳細は把握してないです

  3. https://portal.abci.ai/docs/ja/02/

  4. ABCIから与えられるgroup名によってgroup1 or group2 が変わる

  5. https://www.sylabs.io/guides/2.6/user-guide/build_a_container.html?highlight=docker#downloading-a-existing-container-from-docker-hub

  6. https://github.com/ISU-HPC/mysql を参考にはした

  7. 勿論、一連の流れを手動でやるのめんどくさかったので、自動化した。

  8. https://www.sylabs.io/guides/2.6/user-guide/bind_paths_and_mounts.html?highlight=bind#system-defined-bind-points

  9. 利用管理者(ABCI利用の代表者)であれば、予約実行や予約取り消しもコマンドで行えるが、自動化するモチベーションがなかったため、利用者ページから指定するようにした。

  10. arとはadvance reservationの略らしい。

linux kernelでのFPU, MMX, SSEについて

linux kernelでのFPU, MMX, SSEについて

本記事では、linux kernel 2.6.11でのFPU(Float Point Unit)やMMX, SSEがどう設定、使用されているのかを確認する。FPU, MMX SSE命令を使用する際は、使用する際に意図的に#NM(Interrupt7: Device not available exception)を出し、各種フラグを切り替え(特にcr0.TS flagをOFFにして)、これらの命令を使えるようにしている。(後述の通り、Kernel Modeでは、kernel_fpu_begin, kernel_fpu_endにてフラグの切り替えをおこなっている1ため、この限りでない。)

プログラミング言語の例外処理はパフォーマンスを落とすものとして一般に嫌われているが、ハードウェア(この場合x86)のレイヤでは、例外をあえて意図的に出すことでパフォーマンス向上を狙っている点で、面白いなと思った2ので、少し詳細に調べて見ようと思った。

reference

  • Understanding the Linux Kernel ch.3とch.8のFPUの部分(本記事ではこの本に従って、version 2.6.11とする)

  • Intel SDM vol.1 ch.8

  • Indel SDM vol.2 fxsave

  • Intel SDM vol.3 cr0の部分、#NM exception

boot時:

arch/i386/boot/setup.S

最初の値がどうなっているのかは気になるので、protected modeに移行した直後の処理をみていく。

pagingとIDTの初期設定が終わった後は、checkCPUtypeに移る:

#define X86     new_cpu_data+CPUINFO_x86
#define X86_VENDOR new_cpu_data+CPUINFO_x86_vendor
#define X86_MODEL  new_cpu_data+CPUINFO_x86_model
#define X86_MASK   new_cpu_data+CPUINFO_x86_mask
#define X86_HARD_MATH  new_cpu_data+CPUINFO_hard_math
#define X86_CPUID  new_cpu_data+CPUINFO_cpuid_level
#define X86_CAPABILITY new_cpu_data+CPUINFO_x86_capability
#define X86_VENDOR_ID  new_cpu_data+CPUINFO_x86_vendor_id

// skip (Enable Paging)

checkCPUtype:
    movl $-1,X86_CPUID       #  -1 for no CPUID initially
    movb $3,X86      # at least 386
    pushfl           # push EFLAGS
    popl %eax     # get EFLAGS
    movl %eax,%ecx     # save original EFLAGS
    xorl $0x240000,%eax  # flip AC and ID bits in EFLAGS
    pushl %eax        # copy to EFLAGS
    popfl            # set EFLAGS
    pushfl           # get new EFLAGS
    popl %eax     # put it in eax
    xorl %ecx,%eax     # change in flags
    pushl %ecx        # restore original EFLAGS
    popfl
    testl $0x40000,%eax  # check if AC bit changed
    je is386

    movb $4,X86      # at least 486
    testl $0x200000,%eax # check if ID bit changed
    je is486

    /* get vendor info */
    xorl %eax,%eax         # call CPUID with 0 -> return vendor ID
    cpuid
    movl %eax,X86_CPUID        # save CPUID level
    movl %ebx,X86_VENDOR_ID        # lo 4 chars
    movl %edx,X86_VENDOR_ID+4 # next 4 chars
    movl %ecx,X86_VENDOR_ID+8 # last 4 chars

    orl %eax,%eax          # do we have processor info as well?
    je is486

    movl $1,%eax     # Use the CPUID instruction to get CPU type
    cpuid
    movb %al,%cl       # save reg for future use
    andb $0x0f,%ah       # mask processor family
    movb %ah,X86
    andb $0xf0,%al       # mask model
    shrb $4,%al
    movb %al,X86_MODEL
    andb $0x0f,%cl       # mask mask revision
    movb %cl,X86_MASK
    movl %edx,X86_CAPABILITY

is486:   movl $0x50022,%ecx   # set AM, WP, NE and MP
    jmp 2f

is386:   movl $2,%ecx     # set MP
2: movl %cr0,%eax
    andl $0x80000011,%eax    # Save PG,PE,ET
  # append MP: Monitor Coprocessor[1]
    orl %ecx,%eax
    movl %eax,%cr0
    call check_x87
# skip (After that load IDT, GDT and call start_kernel)
check_x87:
    movb $0,X86_HARD_MATH
    clts # clear task switch flag
    fninit # initialize FPU
    fstsw %ax # store x87 FPU status register to %ax
    cmpb $0,%al
    je 1f
    movl %cr0,%eax     /* no coprocessor: have to set bits */
    xorl $4,%eax     /* set EM */
    movl %eax,%cr0
    ret
    ALIGN
1: movb $1,X86_HARD_MATH
    .byte 0xDB,0xE4     /* fsetpm for 287, ignored by 387 */
    ret

ここでは、まず、cr0のフラグについてとcheck_x87の動作について説明する。

checkCPUtype ~ i386まで

je is386やらje is486はすべてjumpせず、cpuid命令3の実行により、new_cpu_dataに値が入り、%cr0 registerに各種flagが設定される:(FPUに関係のあるのだけ4)

  • ET(Extension Type[4])=1 : Reserved in the Pentium 4, Intel Xeon, P6 family, and Pentium processors. In the Pentium 4, Intel Xeon, and P6 family processors, this flag is hardcoded to 1.
  • TS(Task Switched[3])=0
  • EM(Emulation[2])=0 : indicates an x87 FPU is present when clear.
  • MP(Monitor Coprocessor[1]) =1 : If the MP flag is set, a WAIT instruction generates a device-not-available exception (#NM) if the TS flag is also set.

ET, EM, MPは常にこの値で、TSが特定のタイミングで切り替わる。TS flagについて、役割の概要を述べる。(実際のコードは後述とする)

cr0.TSはIntel SDM ch.2.5によれば、以下のような仕様である。

  • If the TS flag is set and the EM flag (bit 2 of CR0) is clear, a device-not-available exception (#NM) is raised prior to the execution of any x87 FPU/MMX/SSE/SSE2/SSE3/SSSE3/SSE4 instruction; with the exception of PAUSE, PREFETCHh, SFENCE, LFENCE, MFENCE, MOVNTI, CLFLUSH, CRC32, and POPCNT. See the paragraph below for the special case of the WAIT/FWAIT instructions.

  • If the TS flag is set and the MP flag (bit 1 of CR0) and EM flag are clear, an #NM exception is not raised prior to the execution of an x87 FPU WAIT/FWAIT instruction.

また、FPU, MMX, SSEにおける各種flagのtableを見ると、次のようになっている:

FPU: 3,4行目 f:id:knknkn11626:20190414132914p:plain

MMX: f:id:knknkn11626:20190414132806p:plain

SSE: Intel SDM vol.3 Table 13.1 [4, 6行目](Xはdon't care) f:id:knknkn11626:20190414132619p:plain cr4.OSFXSR(bit 9), cr4.OSXMMEXCPT(bit 10)

MXCSRはSSE命令に付随するregister5

CPUIDの項目はsse系がハードウェアでサポートされているか?

SSEのcr4.OSFXSRとcr4.OSXMMEXCPTはstart_kernel -> check_bugs -> check_fpuにて、ハードウェアがサポートされている限りONになる。

これら3つの表を見ると、

  • TS=0の時、FPU, MMX, SSEの命令時にExceptionを送出せずに実行する
  • TS=1の時、FPU, MMX, SSEの命令時にException(#NM)を送出する

となる。これを利用して、

context switchとdo_forkの際に6unlazy_fpu(または、__unlazy_fpu)にてTS=1`と設定して、使われる段になったら、#NMのException handler(device_not_available_emulate -> math_state_restore)内にてTS=0として、2回目以降はこれらの命令を使えるようにしている。

FPUやMMXに関連するregisterは大きいため、context switchのたびにこれらのregisterをsave and storeするのはパフォーマンスが良くない。また、user側での使用頻度は多くないため、必要になったら、registerをsave, storeするような方式7をとっている。「必要になったよ」というトリガーがException handlerというわけだ。

なお、TSのON, OFFは以下のマクロor命令で表現されている:

// include/asm-i386/system.h
#define clts() __asm__ __volatile__ ("clts")
#define write_cr0(x) \
   __asm__("movl %0,%%cr0": :"r" (x));
#define stts() write_cr0(8 | read_cr0()) // 8=0b1000

check_x87

check_x87 labelでは、je 1f1にjumpして、movb $1,X86_HARD_MATHとして、終了する。fstswx87 FPU status registerをmemoryにstoreする命令で、下位8bitがすべて0であるかをチェックする(勿論、真なので8jumpする)

f:id:knknkn11626:20190413140800p:plain Intel SDM vol.1より

Note) X86_HARD_MATHはmathemetical coprocessor(IRQ 13)と関連する。結果的にはIRQ13はdisableのままである。FPU以前のlegacyな計算機の外部deviceとして備え付けられていたものらしい9。その設定については、細かい(&かなりややこしい)ので補足に回す。

cpu_init

head.Sではcr0.TSを0にしていなかったので、どこかで1にしているはずだ。この設定は、start_kernel -> trap_init -> cpu_initにておこなっているので、実際に見てみよう:

// cpu_init
current_thread_info()->status = 0; // disable TS_USEDFPU
// { current->flags &= ~PF_USED_MATH; }
clear_used_math();
// sttsマクロ
mxcsr_feature_mask_init();

一番目の行は、TS_USEDFPU(0x0001) flagをOFFにする狙いがある。2番目の行は、PF_USED_MATHをOFFにしている。3番目は、sttsマクロ(前述のとおり)を用いて、cr0.TS flagをONにしている。

TS_USEDFPUは、stack(struct thread_info)に結びついており、PF_USED_MATHについてはprocess(struct task_struct)に結びついている。両者は意味は同じだが、Kernel ModeにてFPUを使用する際に、(process単位でなく)thread単位でcr0.TSの管理をしたいという動機でTS_USEDFPUが使用される。


TS.flagとその周辺の前提知識がわかったところで、forkの部分とcontext switchの部分をみてみる。

do_fork

do_forkはfork, clone, kernel_threadのコアの部分の関数である。:

when sys_fork .. do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
when sys_clone .. do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr);
when kernel_thread .. do_fork(flags | CLONE_VM | CLONE_UNTRACED, 0, &regs, 0, NULL, NULL);

FPUに関連するところは、do_fork -> copy_process -> prepare_to_copy -> unlazy_fpuの部分:

// prempt_disable: thread_infoのpreempt_countを1プラスする
// preempt_enable:     preempt_enable_no_resched(); preempt_check_resched();

#define unlazy_fpu( tsk ) do {   \
   preempt_disable();  \
   __unlazy_fpu(tsk);  \
   preempt_enable();   \
} while (0)

#define __unlazy_fpu( tsk ) do { \
   if ((tsk)->thread_info->status & TS_USEDFPU) \
       save_init_fpu( tsk ); \
} while (0)

static inline void save_init_fpu( struct task_struct *tsk )
{
    preempt_disable();
    __save_init_fpu(tsk);
    stts(); // #define stts() write_cr0(8 | read_cr0())
    preempt_enable();
}

static inline void __save_init_fpu( struct task_struct *tsk )
{
    if ( cpu_has_fxsr ) {
        asm volatile( "fxsave %0 ; fnclex"
                  : "=m" (tsk->thread.i387.fxsave) ); // thread_struct.i387(i387_union) 
    } else {
        asm volatile( "fnsave %0 ; fwait"
                  : "=m" (tsk->thread.i387.fsave) );
    }
    tsk->thread_info->status &= ~TS_USEDFPU;
}

TS_USEDFPUはFPU命令がすでに使用されていることを表すフラグ。もし、使用されていれば、__save_init_fpuを実行する。cpu_has_fxsr#define cpu_has_fxsr boot_cpu_has(X86_FEATURE_FXSR)で真なので、fxsave命令が実行され、FPUやSSE関連のregisterが全てtsk->thread.i387.fxsaveに保存される。fxsaveの型はunion i387_unionで、以下のようになっている:

union i387_union {
    struct i387_fsave_struct   fsave;
    struct i387_fxsave_struct  fxsave; // SSE and SSE2 extensions.
    struct i387_soft_struct soft;
};

struct i387_fxsave_struct {
    unsigned short    cwd;
    unsigned short    swd;
    unsigned short    twd;
    unsigned short    fop;
    long   fip;
    long   fcs;
    long   foo;
    long   fos;
    long   mxcsr;
    long   mxcsr_mask;
    long   st_space[32];  /* 8*16 bytes for each FP-reg = 128 bytes */
    long   xmm_space[32]; /* 8*16 bytes for each XMM-reg = 128 bytes */
    long   padding[56];
} __attribute__ ((aligned (16))); // must be aligned on a 16-byte boundary.

fsaveとfxsaveの違いは、 SSE命令をサポートしているか否かの違い10。これらの(おどろおどろしい)構造体の正体は、Intel SDM vol.2のfxsave命令を見れば、以下のような形でsaveしていると書かれている:

f:id:knknkn11626:20190414161350p:plain
fxsave memory region

また、it must be aligned on a 16-byte boundary.とfxsaveにかかれているため、__attribute__ ((aligned (16)));となっている。これら一つ一つの構造体の意味については、深入りしない(し、linux kernelの範囲では深入りする必要もない)

Note) unlazy_fpuはfork元の(親となる)processに対して実行しているが、dup_task_structではtask_structの内容をcopyするため、子のprocessに対しても同様にTS_USEDFPUが0となっている。

context switch

context switchのentry pointはscheduler関数であったから、scheduler -> context_switch -> switch_toとたどっていき、__switch_to11内の__unlazy_fpuがFPU関連のコードである:

struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    struct thread_struct *prev = &prev_p->thread,
                 *next = &next_p->thread;
    int cpu = smp_processor_id();
    struct tss_struct *tss = &per_cpu(init_tss, cpu);
    __unlazy_fpu(prev_p);
    load_esp0(tss, next);
    load_TLS(next, cpu);
// skip

__unlazy_fpuについては、do_forkの章でやったとおりなので、省略する。

Note) next_p(process P_Bとよぶ)は前の(P_Bがprev_pであった頃の)context switchにて__switch_to(P_B, n_p) -> __unlazy_fpu(P_B)と実行されているので、TS_USEDFPUが0となっていることが保証される。

Exception

ここからは、context switch後に一度も使用されていない(cr0.TS=1)場合に、FPU関連の命令が使用されると、#NM exceptionのhandlerが発生し、cr0.TS=0となり、以降、exceptionが発生せずにFPU関連の命令が使用できる部分のコードをみていきたい。boot時の章のcr0.TSに述べたとおり、

  • TS=0の時、FPU, MMX, SSEの命令時にExceptionを送出せずに実行する
  • TS=1の時、FPU, MMX, SSEの命令時にException(#NM)を送出する

ということを念頭に置く。

handlerの登録

まず、Interrupt 7 Device Not Available Exception (#NM)で、trap_init にて、set_trap_gate(7,&device_not_available);とhandlerが登録される。trap gateなので、device_not_available開始時にはeflags.IFが自動的に0にならない。

device_not_available

linuxにおけるException全般の取扱は、http://cstmize.hatenablog.jp/entry/2019/03/28/linux2_6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8%60int_%240x80%60%28system_call%29%E3%81%AE%E6%8C%99%E5%8B%95 に以前書いた。今回は、device_not_availableに限った話をする。

# arch/i386/kernel/entry.S
ENTRY(device_not_available)
    pushl $-1           # mark this as an int
    SAVE_ALL
    movl %cr0, %eax
    testl $0x4, %eax     # EM (math emulation bit): usually set 0
    jne device_not_available_emulate
     # we take cr0.EM=0
    preempt_stop # cli
    call math_state_restore
    jmp ret_from_exception
device_not_available_emulate:
    pushl $0        # temporary storage for ORIG_EIP
    call math_emulate # force_sig(SIGFPE,current); and schedule()
    addl $4, %esp
    jmp ret_from_exception

cr0.EMは常時0だったから、jne(ZF=0, 結果が0でない場合jumpする)は素通りして、math_state_restoreをcallする:

void init_fpu(struct task_struct *tsk)
{
    if (cpu_has_fxsr) {
        memset(&tsk->thread.i387.fxsave, 0, sizeof(struct i387_fxsave_struct));
        tsk->thread.i387.fxsave.cwd = 0x37f; // 0b0000_0011_0111_1111
        if (cpu_has_xmm)
            tsk->thread.i387.fxsave.mxcsr = 0x1f80;
    } else {
        memset(&tsk->thread.i387.fsave, 0, sizeof(struct i387_fsave_struct));
        tsk->thread.i387.fsave.cwd = 0xffff037fu;
        tsk->thread.i387.fsave.swd = 0xffff0000u;
        tsk->thread.i387.fsave.twd = 0xffffffffu;
        tsk->thread.i387.fsave.fos = 0xffff0000u;
    }
    /* only the device not available exception or ptrace can call init_fpu */
    set_stopped_child_used_math(tsk); // tsk->flags |= PF_USED_MATH;
}


asmlinkage void math_state_restore(struct pt_regs regs)
{
    struct thread_info *thread = current_thread_info();
    struct task_struct *tsk = thread->task;

    clts(); // clear cr0.TS
    if (!tsk_used_math(tsk)) // ((p)->flags & PF_USED_MATH)
        init_fpu(tsk);
    restore_fpu(tsk);
    thread->status |= TS_USEDFPU;    /* So we fnsave on switch_to() */
}

次からFPU, MMX, SSEの命令時にExceptionを送出せずに実行したいので、cr0.TSをoffにする。PF_USED_MATHがOFFなら、init_fpuでcurrent->thread.i387.fxsaveが初期化され12PF_USED_MATHがONになる。この初期化したfxsaveがrestore_fpuによって、registerに反映される(fxrstor: restore命令)

その後、TS_USEDFPUもONする。

ということで、cr0.TSをoffにしていることが確認できた。以降、context switchされるまではFPU関連の命令を使ってもdevice_not_availableで補足されない。

kernel_start_fpu, kernel_end_fpu

上記の話は、user landでFPUが使われたときの挙動だったが、kernel thread(Kernel land)でFPUを使用する場合は、kernel_start_fpukernel_end_fpuの間でFPU, MMX命令を使うようにする。というのも、Exceptionはuser land(か、interrupt handlerの最中)でしか起こらないので、Kernel landでは上のようなことができないからである。

一例として、get_zeroed_pageという関数は、最終的にmmx_clear_pageで4K pageの中身を0埋めしている。get_zeroed_pageは例えば、start_kernel -> pidmap_initにて、pidmap_array->page = (void *)get_zeroed_page(GFP_KERNEL);という形で使われている。

static pidmap_t pidmap_arrayはpidが使用されているか否かを1(used) or 0(free)のbitで表現するための構造体であり、pidmap_array->pageは、pidの最大値32768bit=4KBの大きさのbitmapである。初期値は、process 0(kernel process, swapper processともいう)を除いて13すべて使用可能なので、0である必要がある。ということで、0埋めするというモチベーションが起こる。

get_zeroed_pageをたどっていくと、get_zeroed_page -> alloc_pages(gfp_mask | __GFP_ZERO, 0); -> alloc_pages_node(0, gfp_mask, order=0) -> __alloc_pages(gfp_mask, order=0, node_data[0]->node_zonelists[(gfp_mask & GFP_ZONEMASK)] ) -> buffered_rmqueue -> prep_zero_page(page, order=0, gfp_flags);(__GFP_ZEROのため) -> clear_highpage -> clear_page(kaddr);-> mmx_clear_page -> fast_clear_page(page);という感じでようやく所要の関数にたどり着く。

fast_clear_pageは

// arch/i386/lib/mmx.c
void kernel_fpu_begin(void)
{
    struct thread_info *thread = current_thread_info();

    preempt_disable(); // inc_preempt_count(); barrier();
    if (thread->status & TS_USEDFPU) {
          // fxsave %0 ; fnclex
          // tsk->thread_info->status &= ~TS_USEDFPU;
        __save_init_fpu(thread->task);
        return;
    }
    clts();
}
#define kernel_fpu_end() do { stts(); preempt_enable(); } while(0)


static void fast_clear_page(void *page)
{
    int i;

    kernel_fpu_begin(); 
    __asm__ __volatile__ (
        "  pxor %%mm0, %%mm0\n" : :
    );

    for(i=0;i<4096/64;i++)
    {
        __asm__ __volatile__ (
        "  movntq %%mm0, (%0)\n"
        "  movntq %%mm0, 8(%0)\n"
        "  movntq %%mm0, 16(%0)\n"
        "  movntq %%mm0, 24(%0)\n"
        "  movntq %%mm0, 32(%0)\n"
        "  movntq %%mm0, 40(%0)\n"
        "  movntq %%mm0, 48(%0)\n"
        "  movntq %%mm0, 56(%0)\n"
        : : "r" (page) : "memory");
        page+=64;
    }
    /* since movntq is weakly-ordered, a "sfence" is needed to become
    * ordered again.
    */
    __asm__ __volatile__ (
        "  sfence \n" : :
    );
    kernel_fpu_end();
}

という感じになっており、kernel_fpu_beginでcr0.TS=0が保証され、kernel_fpu_endでcr0.TS=1となる。つまり、両者の内部では、(cr0.TS=0なので)mmx命令がexceptionを送出せず使える。

補足

mathematical coprocessorについて

X86_HARD_MATHの値については、legacyのIRQ13(mathematical coprocessor)の設定のときに用いられているようだ。結果的にdisableになっている。

start_kernel -> init_IRQ

 if (boot_cpu_data.hard_math && !cpu_has_fpu)
        setup_irq(FPU_IRQ, &fpu_irq); // FPU_IRQ=13

にてIRQ13がsetupされるかどうか決まる。

boot_cpu_data.hard_mathについては、movb $1,X86_HARD_MATHの影響で、1になる。#define X86_HARD_MATH new_cpu_data+CPUINFO_hard_mathと定義されていて、start_kernel -> setup_arch -> memcpy(&boot_cpu_data, &new_cpu_data, sizeof(new_cpu_data));boot_cpu_dataに値がコピーされる。なので、boot_cpu_data.hard_math=1で良さそう。

cpu_has_fpuについても1になる。これは、movl %edx,X86_CAPABILITYと関係がある。

// include/asm-i386/cpufeature.h
#define boot_cpu_has(bit) test_bit(bit, boot_cpu_data.x86_capability)
#define cpu_has_fpu boot_cpu_has(X86_FEATURE_FPU) // #define X86_FEATURE_FPU (0*32+ 0)

で、#define X86_CAPABILITY new_cpu_data+CPUINFO_x86_capabilityと合わせてみると、cpuidの結果FPUはサポートされているので、1が入るはずで、boot_cpu_has(X86_FEATURE_FPU)は1となり、cpu_has_fpu=1となる

ということで、IRQ13は使用されない14


  1. Kernel Modeでは、4K-byte pageを0 clearしたり、pageのcopyをする際にmmx命令を使っている。

  2. 勿論、HWのexceptionの機構とsoftwareの分野のそれとは、異なるものであるが、少なくとも言葉としては同じ"exception"なので。

  3. cpuid命令の詳細については、https://www.scss.tcd.ie/Jeremy.Jones/CS4021/processor-identification-cpuid-instruction-note.pdf のch. 5.1.2.4とTable5.6(edx registerの方)を見れば良いとおもう。

  4. この結果は、Intel SDM vol.3のTable 9-3. Recommended Settings of EM and MP Flags on IA-32 Processorsにも合致しているので、大丈夫そう。

  5. Intel SDM vol.1 ch.11.5.1を見ると、Each of the six exception conditions has a corresponding flag (IE, DE, ZE, OE, UE, and PE) and mask bit (IM, DM, ZM, OM, UM, and PM) in the MXCSR registerとある。そこでMXCSRがどう設定されてるのかを確認する。Intel SDM vol.3のTable 9-1を見ると、 Power-upのときに、MXCSRが0x1F80にリセットされる。それと、Intel SDM vol.1 のtable10.3とを合わせると、初期状態はexception flagが全てmaskされていることがわかるので、#UDや#XM Exceptionは発生しないと思われる。(start_kernel -> trap_init -> cpu_init -> mxcsr_feature_mask_initの部分では、MXCSRの初期化はなされてなさそう)

  6. また、do_notify_resume内でもdo_notify_resume -> handle_signal -> setup_frame -> setup_sigcontext -> save_i387 -> save_i387_fxsave -> unlazy_fpu で必要であれば、TS=1と初期化されているようだ。

  7. これは、linux OSが特別にこの性質を利用しているというわけではなく、x86側の機能としてそもそも搭載されているものだ。Intel SDM ch.2.5のThe processor does not automatically save the context of the x87 FPU, XMM, and MXCSR registers on a task switch. Instead, it sets the TS flag, which causes the processor to raise an #NM exception whenever it encounters an x87 FPU/MMX/SSE/SSE2/SSE3/SSSE3/SSE4 instruction in the instruction stream for the new task (with the exception of the instructions listed above).でそう書いてある。

  8. やや細かいが、Intel SDM vol.3のTable 9.1によれば、x87 FPU Status Word(regiterの中身)の初期値は0x0000である。

  9. Understanding the Linux kernel ch.3に、"The name mathematical coprocessor continues to be used in memory of the days when floating-point computations were executed by an expensive special-purpose chip.“とある。

  10. この点をもう少し詳しく述べると、FPU, MMXとSSE系の命令は独立に動作する(Intel SDM vol.1 ch.8.1.The x87 FPU executes instructions from the processor’s normal instruction stream. The state of the x87 FPU is inde- pendent from the state of the basic execution environment and from the state of SSE/SSE2/SSE3 extensions.より) 一方、FPUとMMXは同じregisterを用いる(However, the x87 FPU and Intel MMX technology share state because the MMX registers are aliased to the x87 FPU data registers. Therefore, when writing code that uses x87 FPU and MMX instructions, the programmer must explicitly manage the x87 FPU and MMX state)。ということで、FPU, MMX, SSE, SSE2..と種類があるが、SSE命令をサポートしているか、で区切られているのはこういった背景があるためである。

  11. inline assemblyで難しいですが、 switch_toに関しては、以前、http://cstmize.hatenablog.jp/entry/2019/03/16/%60switch_to%60%E3%82%92%E8%AA%AD%E3%82%93%E3%81%A7%E3%81%BF%E3%82%8B でまとめましたので、参照してください。

  12. init_fpuのcwd = 0x37fの左辺はFPU Control Word(16bitのFPU Control Register)でIntel SDM vol.3 Table 9-1によれば、INITの際、0x37Fに初期化するので、それを踏襲している。mxcsrの0x1F80もPower upの際の設定値と同じ。

  13. swapper processに関しては、set_bit(0, pidmap_array->page);でbit0番に1を埋めてる

  14. commentにも、Careful.. There are problems with IBM-designed IRQ13 behaviour. Don't touch unless you *really* know how it works. とか、IRQ13は危険!みたいな文言がいくつかあるので、disableであってると思う。

slab allocatorの内部実装

slab allocatorの内部実装

page frameは4K単位の管理なので、比較的小さいメモリ領域を確保するときに効率が悪い。そこで、linux2.6では、slab allocatorという仕組みを用いて小さな領域を効率的にreserved/freeするようになっている。cacheという概念自体はfileだけでなく、小さい領域を管理するための一般化された仕組みなので、やや想像しづらい。ということで、詳しめにまとめてみた。

reference

  • Understanding the Linux kernel: ch.8 Memory Management
  • 前回の記事と同様にlinux kernel 2.6.11で確認してる
  • Intel SDM vol.3 ch.11のcacheの部分
  • Computer Organization and DesignのFigure5.12, Figure5.18あたりのcacheの図

概要

  • モチベーションとしては、一定のサイズのkernel内の構造体(inodeならstruct inode, tcpのportのbindの管理ならstruct tcp_bind_bucket)の領域を確保したい。しかしながら、Buddy System Algorithm1では page frame単位(4K-byte)で領域の管理をしているので、それより小さい領域確保の場合、非効率である。
  • まず、cache descriptorを作成する。(tcp_bind_bucketなら、struct kmem_cache_t tcp_bucket_cachep)。ここで、どんなslabを作るのかを決める。cache descriptorはslabを管理してる。 -> kmem_cache_create
  • slab descriptorはobjectという領域を管理している。使用可能な領域なら自由に使える。これでPAGE_SIZEよりもより小さいサイズの領域をalloc/freeできる様になっている。
  • slabはcache descriptorの情報から複数作れるので、slab内のobjectが使用可能かどうかをcache descriptorから一元管理したい。そういう動機があり、local cacheがcache descriptorにある。local cacheでは使用可能なobjectのaddressがいくつか管理されているので、local cacheを経由して使用可能なobjectのaddressを入手できる。 -> kmem_cache_alloc
  • もし、local cacheの使用可能なobjectが枯渇した場合は、objectとslabとを新たに作って(cache_growkmem_getpagesおよびalloc_slabmgmt)、使用可能なobjectをrefillする。 -> cache_alloc_refill

cache

使用可能なobjectを管理するためには、(specific) cacheか(general) cacheを用いる。

前者は、一定のサイズのobjectを管理する場合(e.g. 特定の構造体の領域)の場合で、専用のcache descriptorを作ることでobjectを管理する。

一方後者は、それ以外の場合で、この場合は、boot時に構成したmalloc_sizesを用いる。malloc_sizesでは、32 or 64 or 128 or 256...の大きさのobjectを管理しているcache descriptorのdescriptorで、malloc_sizes内のcache descriptorでobjectを管理している。例えば、確保したい領域が56byteの場合、すっぽり入る最小の箱の大きさ(64)のsizeのobjectを管理しているcache descriptor(malloc_sizesのCACHE(64))を用いる。

なお、malloc_sizesはかなりトリッキーな構造体で、https://gist.github.com/knknkn1162/b063e1890586f35c84d8fb2672c427fe のようになっているので、結構オモシロイと思った。

kmem_cache_t create create from alloc alloc from
cache_cache kmem_cache_init - -
malloc_sizes[i]->cs_(dma)cachep kmem_cache_init - -
(specific) cache kmem_cache_create cache_cache kmem_cache_alloc kmem_cache_createで作成した構造体
(general) cache - - kmalloc malloc_sizes[i]->cs_(dma)cachep

kmallocも内部では、kmem_cache_alloc(kmem_cache_t *cachep, int flags)を使っていて、第一引数は、malloc_sizes[i]->cs_(dma)cachepとなる。(ZONE_DMAの場合cs_dmacachepを使う)

なので、slab allocatorを把握するためには、cache descriptorを構成するためのkmem_cache_createkmem_cache_allocを把握できれば良さげ。

  • kmem_cache_createにて
    • cache descriptor(struct kmem_cache_t)の作成とこの構造体の初期化
    • local cache(cache descriptorのarrayメンバで管理されている)の初期化
  • kmem_cache_alloc (kmem_cache_t *cachep, int flags)にて、
    • local cacheに使用可能なobjectがあれば(array->avail > 0)それを用いる
    • そうでなければ、cache_alloc_refill

一応例があったほうがイメージしやすいかもなので、今回はinode cache(struct kmem_cache_t inode_cachep)を例にしてみる。

Note) ちなみに、struct task_structtask_struct_cachepでkmem_cache_allocされていて、struct thread_info(4Kのstack領域)はkmallocを用いてallocされてる2

kmem_cache_create

(inode) cache(struct kmem_cache_t inode_cachep)は、start_kernel -> inode_init -> kmem_cache_createにて作成する。ざっくりとは下のような感じ。

- inode_cachep = kmem_cache_create("inode_cache", sizeof(struct inode), 0, SLAB_PANIC, init_once, NULL);
  - kmem_cache_t *cachep = NULL;
  - cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
  -  memset(cachep, 0, sizeof(kmem_cache_t));
  -  cachep->num(Number of objects)とcachep->gfporder(usually =1)を決める(`PAGE_SIZE >> cachep->gfporder`にて、各slabの大きさが決まる)
  -  cachepの他のメンバも決める
    - cachep->slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t) + sizeof(struct slab), 4);
    - cachep->objsize = ALIGN(size, 4);
    - cachep->color_off = align = 4
  - local cache(cachep->array)の構成(最初は空)
    - cachep->array[cpu_id]->avail = 0; # 最初local cacheはzero
    - cachep->array[cpu_id] = BOOT_CPUCACHE_ENTRIES; // #define BOOT_CPUCACHE_ENTRIES 1
    - ac_data(cachep)->batchcount = 1;
    - ac_data(cachep)->touched = 0;
  -  list_add(&cachep->next, &cache_chain): register cachep`static struct list_head cache_chain;`
  -  return cachep

大きくポイントは2つ。1つ目は、inode_cachep自体、cache_cacheというcache(struct kmem_cache_t)からallocateされているところ。(cache_cacheはkmem_cache_initにて構成されている)

もう一つは、local cache(cachep->array)の初期化である。

あとは、CFLGS_OFF_SLABも大事かもしれない。構造体のサイズが512[byte]以上なら、CFLGS_OFF_SLABが付けられる。(今回は、sizeof(struct inode)は512byte以上でないので、このフラグはつかない) これは、後々確保されるobjectをslab descriptor(struct slab)の直後に配置してよいか、そうでないかを示すフラグ。確保するサイズが大きすぎると、特定の場所よりも、もうチョット領域の大きい場所にobjectを確保するのが良いという理由から。詳しくは、Understanding the Linux kernelのFigure 8-5. Relationships between slab and object descriptorsを見れば意味がわかると思う。

kmem_cache_alloc

inodeの場合、inode = (struct inode *) kmem_cache_alloc(inode_cachep, SLAB_KERNEL);という風にalloc[^slab_kernel]する。 void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)という形をしていて、戻り値は確保した領域のaddressである。

この関数は確保する領域のsizeが陽に含まれていないので、結構混乱するが、cachep->objsizeにて、確保する領域のsizeがわかる。(cache descriptor自体は特定の大きさの領域(構造体の領域など)を確保するためのものということを思い出す。

この関数のポイントとしては、local cache内に使用可能なobjectがあれば、それを使うことと、なければ、inode_cachep内の既存のslabから調達する。もし、全く使えるobjectがないときは、1~2page分の領域をBuddy System Algorithmを用いて確保し3、その領域をstruct slabとそれに付随する複数のobjectに割り当てることで、使用可能なobjectを作成する。

kmem_cache_alloc->__cache_alloc
  - ac = cachep->array[smp_processor_id()](local cache(`struct へのpointer)とする。
  - objp = ac_entry(ac)[--ac->avail]: local cacheに使用可能なobjectがある時、それを使う
  - objp = cache_alloc_refill(cachep, flags): 上記以外の場合
    - [retry]: まず、以下の三種類の方法でobjectを取得を試し、そのobjectの先頭アドレスをlocal cacheに保存する:
      - shared local cacheから(cachep->lists->shared)
      - cachep->lists->slabs_partialから
      - cachep->lists->slabs_freeから
    - 上記が全くだめだった場合(`ac->avail == 0`)
      - cache_grow(cachep, flags, -1): slabとobject達を作成する。
        - cachep->colour_next++: これは、cacheのindexを意図的にずらすためのもの
        - offset *= cachep->colour_off: slab descriptorのoffset
        - objp = kmem_getpages(cachep, flags, -1): `PAGE_SIZE >> cachep->gfporder(=1)`分の領域確保
          - page = alloc_pages(flags, cachep->gfporder): Buddy System Algorithmを用いて2page分の領域を確保
          - addr = page_address(page): page -> virtual addressに変換
          - SetPageSlab(page): 2page分のpage->flagsに`PG_slab`をセット
        - slabp = alloc_slabmgmt(cachep, objp, offset, local_flags):
          - slabp = objp+colour_off; colour_off += cachep->slab_size;
          - slabp->s_mem = objp+colour_off;(objectの先頭アドレス)
        - set_slab_attr: page->lruの設定(このpageはpage descriptorなので、objpとは別であることに注意)
          - page->lru.next = (struct list_head *)cachep
          - page->lru.prev = (struct list_head *)slabp
        - cache_init_objs(cachep, slabp, ctor_flags):
          - cachep->ctor(objp, cachep, ctor_flags): inodeの場合は、init_once(`struct inode`としてobjectを初期化)
          - `struct slab`の直後の`kmem_bufctl_t`達の中身を埋める
        - list_add_tail(&slabp->list, &(cachep->lists->slabs_free))
      - if (!ac->avail) goto retry: もう一回、cache_alloc_refillの最初の部分に戻る。今度は、`cachep->lists->slabs_free`からobjectを取得できるようになっている。

ややこしいところだけ、ピックアップ:

  • ac_entry(ac)は(void**)(ac+1);で一見難しそうだが、図にすると、void*(objectのaddress)の配列の先頭を表していることがわかる:

f:id:knknkn11626:20190406164915j:plain
ac_entry


  • 次にslabがどのような形をしていくかみていく。これは、cache->object_sizeが小さい場合はslab descriptor(struct slab)とobjectの数のkmem_bufctl_tの後にobjectが配置される(Fig8-6にも似たような図がある):

f:id:knknkn11626:20190406232334j:plain
slab

cachep->colour_next*cachep->colour_offはL1 cacheのindexを意図的にずらすためのもの。もし、ずらさなかったとしたら、作成されたslabはobjectの数も同じだし、sizeも同等なので、(cachepと結びついている)他のslabとobjectの下位アドレスは同じになるが、hardwareのcache構造上少しまずい。(cache missしやすくなる)

以下、cacheの前提知識をある程度必要とするので、少し難しい4

f:id:knknkn11626:20190406232646j:plain
x86: pentium4のcache構造

Intel SDM Table 11-1.のL1 Data Cacheによれば、

Pentium 4 and Intel Xeon processors (Based on Intel NetBurst microarchitecture): 8-KByte, 4-way set associative, 64-byte cache line size.

とあるので5、これをもとに書いたのが上の図になる(多分)。

slabに話を当てはめると、もし、ずらさなかったとしたら、tagの部分は異なるが、[11:4]のindexの部分は同じとなる2つのobjectが生成される。この場合、objectのdataを探す時、同じindexをたどってしまうことになり、cache missのrateが高くなるかもしれない。そこで、indexの部分は同じとならないように、objectの位置を少しだけずらす(最初の数バイト空白cachep->colour_next*cachep->colour_offを入れることにより、indexがズレるので、cache missが減ることが期待できる。


  • struct slabの直後のkmem_bufctl_t達は次のobjectがどこにあるかは indexのかたちで表されている(kmem_bufctl_tの型はunsigned shortになっているのはそういった理由から)。この中身を埋める部分は、以下のようになっている。
// cache_init_objs
slabp->free = 0;
kmem_bufctl_t* obj_idxs = (kmem_bufctl_t *)(slabp+1); // slabp->freeのすぐ直後のaddress
obj_idxs[0] = 1;
obj_idxs[1] = 2;
// .. skip
obj_idxs[cachep->num-1] = BUFCTL_END; // BUFCTL_END: 次のobject
// obj_idxs[cachep->num-1]の直後にobjectがnum個配置されている

これで、slab内のfreeのobjectを順番にたどっていけるというわけだ。cache_alloc_refillのcachep->lists->slabs_(partial|free)にて、slabのobject達を取得するときは、この要領で順番にたどり、objectのaddressを取得し、local cacheに置くようなロジックになっている。

補足

kmem_cache_createとkmem_cache_allocをそれなりに詳しく説明したが、cache, slab, objectの全体の関係の把握は以下の図のようになる。手書きで汚いけど。。

f:id:knknkn11626:20190407121937j:plain
cache slab objectの関係


  1. buddy system algorithmについては、この記事で説明しないが、Understanding the Linux kernel: ch.8に詳しい説明がある。Page frameを理解すればそれほど難しくないと思う(あと、pagingと混同しないこと。kernel領域の0xC000_0000から896MBの領域は4MB-pagingであるが、このpagingの枠組みとは独立にpage frameという概念がある。こちらは4K-byte単位で管理されている。)

  2. dup_task_struct()を見る限り

  3. ただし、小さな領域(< 512 bytes)の場合。大きな領域の場合は、object用の領域とstruct slabの場所が別になるが、詳細は省略。

  4. cacheの概要については、chapter5を見ればよい。特に、Computer Organization and DesignのFigure5.12, Figure5.18あたり。

  5. Pentium 4 古いが、Understanding the Linux Kernel ch.2にThe L1_CACHE_BYTES macro yields the size of a cache line in bytes. On Intel models earlier than the Pentium 4, the macro yields the value 32; on a Pentium 4, it yields the value 128.とあるので、これを上げた。x64の比較的新しい場合はcacheの構成が違うと思うので、いつか調べてみたい。

e820について

linux kernelのsetupの部分を読んでいて、E820という謎の数字?が気になったのと、ここで得られたデータをboot時に後々利用しているので、少し重点的に調べてみる。

reference

E820 とは?

E820とは、BIOSの命令から来ていて、RAMのmemory mapの状態を返す。 real modeの際にBIOSINT 15h, AX=E820hを投げると、physical addressのsizeやら状態(reserveかそうでないか?)やらが結果として返ってくる。

arch/i386/boot/setup.S

実際に最初から関連のコードを追っていく。

# https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/arch/i386/boot/setup.S#311
meme820:
    xorl %ebx, %ebx            # continuation counter
    movw $E820MAP, %di         # point into the whitelist(#define E820MAP 0x2d0)
jmpe820:
    movl $0x0000e820, %eax       # e820, upper word zeroed
    movl $SMAP, %edx           # ascii 'SMAP'
    movl $20, %ecx           # size of the e820rec
    pushw    %ds              # data record.
    popw %es
    int  $0x15              # make the call

http://www.uruk.org/orig-grub/mem64mb.html の通りにレジスタに値を設定して、BIOSにinterruptを投げると、ES:DI Buffer Pointerで指定したaddress(E820MAP: 0x2d0)に20byte分(%ecx)以下のデータが入る:

Offset in Bytes      Name        Description
    0       BaseAddrLow     Low 32 Bits of Base Address
    4       BaseAddrHigh    High 32 Bits of Base Address
    8       LengthLow       Low 32 Bits of Length in Bytes
    12      LengthHigh      High 32 Bits of Length in Bytes
    16      Type        Address type of  this range.

このデータはおおよそ、以下のような雰囲気のデータ1である:

BIOS-e820: [mem 0x0000000000000000-0x000000000009fbff] usable
BIOS-e820: [mem 0x000000000009fc00-0x000000000009ffff] reserved
BIOS-e820: [mem 0x00000000000f0000-0x00000000000fffff] reserved
BIOS-e820: [mem 0x0000000000100000-0x00000000dffeffff] usable
BIOS-e820: [mem 0x00000000dfff0000-0x00000000dfffffff] ACPI data
BIOS-e820: [mem 0x00000000fec00000-0x00000000fec00fff] reserved
BIOS-e820: [mem 0x00000000fee00000-0x00000000fee00fff] reserved
BIOS-e820: [mem 0x00000000fffc0000-0x00000000ffffffff] reserved

typeの取りうる値は、以下の通り:

// include/asm-i386/e820.h
#define E820_RAM   1 // usable
#define E820_RESERVED  2 // reserved
#define E820_ACPI  3 /* usable as RAM once ACPI tables have been read */
#define E820_NVS   4

mapが複数得られているが、setup.Sの方では、以下のようにループを回している:

        # add %di register to loop meme820
    movw %di, %ax
    addw $20, %ax
    movw %ax, %di
again820:
    cmpl $0, %ebx            # check to see if (A return value of zero means that this is the last descriptor.)
    jne  jmpe820              # %ebx is set to EOF, goto next

ES:DI Buffer Pointerで今、20byte分のデータが入ったから、di+=20とincrementしているのが上記の3行。下2行はEBX Continuationとあるので、走査が終了しているかそうでないかの判別値のようだ。0であれば、終了するので、次に進む。0でなければ、jmpe820に戻り再度int $0x15を実行する。

linuxでは、legacy な機種にも対応するために、INT 15h, AX=E820hに引き続いて、INT 15h, AX=E801hINT 15h, AH=88hも実行する。

2つめの命令は、0x1e02に、3つめは、23に格納される(つまり、e820で格納したaddressとは違う場所)。この値は、include/asm-i386/setup.hにて、

// #define PARAM (boot_params)
// unsigned char __initdata boot_params[PARAM_SIZE];  // #define PARAM_SIZE 2048

#define EXT_MEM_K (*(unsigned short *) (PARAM+2))
#define ALT_MEM_K (*(unsigned long *) (PARAM+0x1e0))

のようにaliasが設定されている4

その後、setup.Sは最終的に、

# almost same as `jmpi    0x100000, __BOOT_CS`
code32:  .long 0x1000             # will be set to 0x100000
                        # for big kernels
    .word __BOOT_CS

となり、startup_32関数にjmpする。setup.S自体の全体のフローはUnderstanding the linux kernel Appendix AのMiddle Ages: the setup( ) Functionにある。その後、head.S -> init/main.cのstart_kernel()を実行していく。

init/main.c

machine_specific_memory_setup

E820が関わっている場所は、start_kernel -> setup_arch -> machine_specific_memory_setup の部分:

static char * __init machine_specific_memory_setup(void)
{
    char *who;
    who = "BIOS-e820";
        // E820_MAP .. the address of the data result from `INT 15h, AX=E820h`
        // E820_MAP_NR .. the number of entries
    sanitize_e820_map(E820_MAP, &E820_MAP_NR);

    if (copy_e820_map(E820_MAP, E820_MAP_NR) < 0) {
        unsigned long mem_size;
        if (ALT_MEM_K < EXT_MEM_K) {
            mem_size = EXT_MEM_K;
            who = "BIOS-88";
        } else {
            mem_size = ALT_MEM_K;
            who = "BIOS-e801";
        }

        e820.nr_map = 0;
                // conservative default setup
        add_memory_region(0, LOWMEMSIZE(), E820_RAM);
        add_memory_region(HIGH_MEMORY, mem_size << 10, E820_RAM);
    }
    return who;
}

前章のsetup.Sを踏まえた上でざっくり流れを追うと、

  1. BIOSから得られたmemory mappingが重複している場合があるので、もれなくダブりなく再構成する。[sanitize_e820_map]
  2. struct e820map e820;に1で再構成したデータを移動させる。low memoryに1のデータが有るため、高位のaddressに移動させたいという理由から。[copy_e820_map]
  3. 2でうまく行かなかった場合は、legacyなINT 15h, AX=E801hINT 15h, AH=88hで得られた結果を利用する。(if文の中身) 2が問題なければ文字列"BIOS-e820"を返す。

という感じ。3番は背景だけ知っておけばそれでよいのでは?と思う。

copy_e820_mapは、その中のadd_memory_regionにて、

// static void __init add_memory_region(unsigned long long start, unsigned long long size, int type)
  // struct e820map e820;
  e820.map[x].addr = start;
  e820.map[x].size = size;
  e820.map[x].type = type;
  e820.nr_map++;

のように指定されている。


このstruct e820map e820はこの後のsetup_memoryの内部でpage frameの終端(max_pfn)を決める際に必要で、この変数は色んな場所に登場していくことになる。


  1. これは、start_kernel -> setup_arch -> print_memory_mapでlogに出力されるものをとってきた。実際には、machine_specific_memory_setupにて、得られたデータを整形しているが、後述する。

  2. movl %edx, (0x1e0), addl %ecx, (0x1e0)の部分。

  3. movw %ax, (2) // INT 15h, AH=88h - Get Extended Memory Sizeの部分

  4. __initdata#define __initdata __attribute__ ((__section__ (".init.data")))と設定されており、これは、リンカスクリプト(arch/i386/kernel/vmlinux.lds.S)を覗いてみると、.init.dataのラベルが存在するはずだ!

linux kernelにおけるtimerについて

linux kernelにおけるtimerについて(Timing Measurementsについて)

はじめに

user landで見えるtimerは時刻の取得やsiginfoとか、epollといったselect系など関数でのtimeoutの設定で用いられるが、kernel側でのtimerの利用はこれとは大きく異なる1

本記事ではkernel上でのtimer全般についてまとめている。Linux (User) Programmingの範疇のtimerの扱われ方はTLPI(The Linux Programming Interface)のch.23(TIMERS AND SLEEPING)がかなり詳しい。

timer interruptも含まれるので、interrupt自体を知っている必要があるが、今回はinterruptについて幹の部分だけ追った上で、timerに関係するコードを追いたいとおもう。timer interruptを先取りする理由は、一般論から話すよりも具体例を先に見ていったほうが良さそうという思惑から。

timerの部分は定数が多く出てくるので、用語だけでなく、数値の確認も行う。

reference

  • Understanding Linux Kernel ch.4 & 6 linux2.6.11をベースに扱っているので本記事でもそれに沿う。

Glossary

  • TSC(Timer Stamp Counter): receive the clock ticks from an external oscilator e.g) 2.4GHz rdtscでcounterを取得できる。後発にHPET(High Precision Event Timer)があるが、linux2.6.11ではdefaultで使用しないことになっているので、省略。
  • PIT(Programmable Interval Timer): 8254 CMOS chip timer interrupt(IRQ0)を周期的に(1msごとに)発生させるために用いる。 周波数は、1193182[Hz]。 こちらは、CPUごとにPITがあるわけではなく、I/O APICでredirectするcpuを決める。linux2.6wでは、timer_interruptがISR(Interrupt Service Routine)として呼ばれる。
  • RTC(Real Time Clock) .. IRQ8 interruptを発する(が、interrupt発生装置としては未使用)。linuxでは限られた場所でしか使われてない2
  • CPU local timer: local APIC timerで各cpuに一つづつある。LVT(Local Vector Table)の0x320にLVT Timer Registerがあるので、そちらで設定する(他にもLVT内のentryを設定する必要がある)。linuxでは、bus clock signal*16回ごとにcounterがdecreaseするようになっている。

他に本では、TSCのより良いとされるHPET(High Precision Event Timer)やACPI Power Management Timerも出てくるが、TSCの場合のみに絞る3

interrupt関連の用語については、http://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95 のGlosaryを参考のこと。

Constants

いろいろ定義されているのでみていく4

// include/asm-i386/timex.h
// internal oscillator frequency
// // CONFIG_X86_ELAN is no set in x86
#define CLOCK_TICK_RATE 1193182

// include/asm-i386/param.h
# define HZ        1000       /* Internal kernel timer frequency */
# define USER_HZ   100        /* .. some user interfaces are in "ticks" */
# define CLOCKS_PER_SEC       (USER_HZ)   /* like times() */

// include/linux/jiffies.h
#define LATCH  ((CLOCK_TICK_RATE + HZ/2) / HZ)    /* For divider */ // => 1193

// NOM .. nominator
// DEN .. denominator
// LSH.. shift ( for resolution) (SH_DIV means "div with shift (for accuracy)")
// ((NOM / DEN) << LSH) .. (quotient) << LSH
// ((NOM % DEN) << LSH) / DEN .. [(reminder)/DEN] << LSH. Note that [(reminder)/DEN] is nearly decimal part of (double)(NOM / DEN)
// (((NOM % DEN) << LSH) + DEN / 2) / DEN ..  [(reminder)/DEN with rounding] << LSH
// SH_DIV(NOM,DEN,LSH) is almost same as the value of `(double)(NOM/DEN) << LSH`
#define SH_DIV(NOM,DEN,LSH) (   ((NOM / DEN) << LSH)                    \
                             + (((NOM % DEN) << LSH) + DEN / 2) / DEN)

// ACTHZ(actual HZ)
#define ACTHZ (SH_DIV (CLOCK_TICK_RATE, LATCH, 8)) // 1000<<8 + 39=256039

/* TICK_NSEC is the time between ticks in nsec assuming real ACTHZ */
// also, it's used in `unsigned long tick_nsec` in `kernel/timer.c`
#define TICK_NSEC (SH_DIV (1000000UL * 1000, ACTHZ, 8)) // 3905 << 8 + 168 = 999848

/* TICK_USEC is the time between ticks in usec assuming fake USER_HZ */
// also, it's used in `unsigned long tick_usec` in `kernel/timer.c`
#define TICK_USEC ((1000000UL + USER_HZ/2) / USER_HZ) // 1000050UL/100 = 10000"

/* TICK_USEC_TO_NSEC is the time between ticks in nsec assuming real ACTHZ and */
/* a value TUSEC for TICK_USEC (can be set by adjtimex)        */
#define TICK_USEC_TO_NSEC(TUSEC) (SH_DIV (TUSEC * USER_HZ * 1000, ACTHZ, 8))

各種timerの初期設定

linux2.6では、PIT, TSC, local APIC timerの設定を順に行う。(TSC, local APIC timerは最初に設定されたPITをもとにセットされる)

今回は概要だけ述べてとりあえず、timerに関する全体像を把握したいと考えている。timerのcalibrationの実装はくせがある(けど、結構面白い)ので、またの機会にまとめたい。

PIT

start_kernel -> init_IRQ -> setup_pit_timerでLATCH(=1193)をi8254にセットする。1193182[Hz]だったからinterruptが1[ms]ごとにIRQ0が発生するようにする(というよりそうなるようにLATCHを設定してる)

TSC

time_init:
  - set xtime and wall_to_monotonic global variable (xtime: `struct timespec xtime __attribute__ ((aligned (16)));`)
  - select_timer: find most preferred working timer. Initialize and take it.
    - timers[i]->init(clock_override): use timer_hpet_init or timer_pmtmr_init or `init_tsc`. In x86, `init_tsc` is selected.

time_init -> select_timer -> timers[i]->init( same as init_tsc) -> calibrate_tscTSCの設定(クロック周波数は機種によって異なるため、動的に決める。そこで、PITを利用してTCSの設定を行う)

local APIC Timer

inuxでは、PITを用いて、init5 -> smp_boot_cpus -> setup_boot_APIC_clock -> calibrate_APIC_clockで周波数を算出し、setup_APIC_timer(calibration_result);で1[ms]ごとにlocal APIC timer interruptを発生するようにさせる。

timer interrupt

以下ではPITとlocal APIC timerのinterruptについて述べる。

PITのtimer interrupt

I/O APICを経由するので、Interrupt ReQuest lineとvector numberを結びつける必要がある。また、vector numberとそのcallbackのヒモ付(IDTの設定)も必要となる。

IRQ0の設定

IRQの設定の方は start_kernel -> time_init -> time_init_hook -> setup_irq(0, &irq0);で設定される。 この関数は本質的には、I/O APICのInterrupt Redirection Tableに設定を書き込む。設定方法は、 (仕様書)https://pdos.csail.mit.edu/6.828/2018/readings/ia32/ioapic.pdf3.2.4. IOREDTBL[23:0]を見ればよい。

setup_irq:
  - desc->handler->startup(irq):
    - startup_edge_ioapic(same as startup_edge_ioapic_irq):
    - __unmask_IO_APIC_irq:
      - __modify_IO_APIC_irq: disable Interrupt Mask(bit16) in Redirection Table Entry

IRQ0のInterruptをONにするために、Interrupt Maskをdisableするだけだ。 ちなみに、Interrupt Redirection Tableの初期設定は、init[^init_func] -> smp_prepare_cpus -> smp_boot_cpus -> smpboot_setup_io_apic -> setup_IO_APIC -> setup_IO_APIC_irqsで行っている。この関数一見複雑に見えるが、やってることは単純で、24entryを一つづつ埋めて、最後に

// arch/i386/kernel/io_apic.c
void __init setup_IO_APIC_irqs(void) { 
  // skip
  io_apic_write(apic, 0x11+2*pin, *(((int *)&entry)+1));
  io_apic_write(apic, 0x10+2*pin, *(((int *)&entry)+0));

として、書き込む。

あと、ISR(Interrupt Service Routine)を実行するためのglobal変数irq_desc[idx=0]に必要な情報を詰める。今回の場合、

// arch/i386/mach-default/setup.c
static struct irqaction irq0  = { timer_interrupt, SA_INTERRUPT, CPU_MASK_NONE, "timer", null, null};

が引数として渡ってくる。IRQ0の場合、ISR(Interrupt Service Routine)はtimer_interruptである。SA_INTERRUPTはISRの突入時にeflags.IFがdisableのママであることを要請するflagである。ここあたりは、interruptやpreemptの回で紹介できればと思う。

IDTの設定

こちらもちょっと複雑だ。interrupt全般の設定は、start_kernel -> init_IRQにて、以下のように設定される:

// init_IRQ
    for (i = 0; i < (NR_VECTORS - FIRST_EXTERNAL_VECTOR); i++) {
        // #define FIRST_EXTERNAL_VECTOR   0x20
        int vector = FIRST_EXTERNAL_VECTOR + i;
        if (i >= NR_IRQS)
            break;
        // void set_intr_gate(unsigned int n, void *addr)
        // // _set_gate(idt_table+n,14,0,addr,__KERNEL_CS);
        if (vector != SYSCALL_VECTOR) 
            set_intr_gate(vector, interrupt[i]);
    }

初期設定では、vector32+iとinterrupt handlerのindexiが対応しているが、(Symmetric)MultiProcessorの場合は、更にこの設定が上書きされるようだ。

init[^init_func] -> smp_prepare_cpus -> smp_boot_cpus -> smpboot_setup_io_apic -> setup_IO_APIC -> check_timer -> set_intr_gate(vector, interrupt[0]);で定義されているようだ。vectorvector = assign_irq_vector(0);の処理から、FIRST_DEVICE_VECTOR»0x31になるっぽい。linuxでは、 Vectors 0x20-0x2f are used for ISA(Industry Standard Architecture) interrupts.と有り、古い規格(ISA)で遅いので、使われていないようだ[^timer_isa]。(TODO: ここあまり自信ない..)

interruptの挙動

PITは interruptが1[ms]ごとにIRQ0が発生するように設定しているのだった。

interrupt gateなので、interrupt発生直後ではeflags.IF=OFFになっており、

interrupt->common_interrupt->do_IRQ:
  # eflags.IF=OFFのまま
  - irq_enter
  - __do_IRQ->handle_IRQ_event(irq, regs, desc->action):
    - local_irq_enable(): eflags.IF=ONに if `!(action->flags & SA_INTERRUPT)` [今回は`irq0`から条件を満たす]
    - call ISR(interrupt service routine) [IRQ0の場合、timer_interruptが実行される]
      - jiffies_64++; update_times(): system time(jiffies, `struct timespec xtime`)の更新
      - smp_local_timer_interrupt: 個別のCPUで済む処理(後述)
    - local_irq_disable(): eflags.IF=OFFに
  - irq_exit: 条件を満たせばdo_softirqが実行される

IRQ0のISR(interrupt Service Routine)の役割 : system time(jiffies, struct timespec xtime)の更新。個別のcpuで済むものはsmp_local_timer_interruptに処理を移譲する。

smp_local_timer_interruptについては、 local APIC timerのtimer interruptで出てくるので、次章で述べる。

local APIC timerのtimer interrupt

local APIC timerから発するinterruptはlocal APIC期限なので、IRQ number(I/O APICとexternal deviceを結ぶ線)はない。そのかわり、local APIC側での設定(LVTの設定)は必要である。加えて、IDTでの設定も見る。

LVTの設定

LVT(Local Vector Table)とは、local APICのregisterたちのRead/Writeができるtableのことだった。

init[^init_func] -> smp_boot_cpus -> setup_boot_APIC_clock -> setup_APIC_timer -> __setup_APIC_LVTT -> apic_write_around(APIC_LVTT, APIC_LVT_TIMER_PERIODIC | LOCAL_TIMER_VECTOR)でlocal APICのLVT timer register(320H)にLOCAL_TIMER_VECTOR(0xef=237)を紐付ける。init_IRQで初期化されたもの(vector[LOCAL_TIMER_VECTOR])をそのまま使う。

IDTの設定

こちらは、

start_kernel -> init_IRQ -> intr_init_hook -> apic_intr_init にて、

set_intr_gate(LOCAL_TIMER_VECTOR, apic_timer_interrupt); とセットされる。

interruptの挙動

local APIC timerの役割は個別のCPUのprocess switchingなどを行う役割を担っている。1[ms]ごとにlocal APIC timer interruptを発生するようにさせるのだった。local timerのinterruptが生じた直後から簡単に見ていく。

local timer interruptが生じると、IDTLOCAL_TIMER_VECTOR番のentryのapic_timer_interruptから、smp_apic_timer_interrptをcall6し、以下のように遷移する。主にsmp_local_timer_interruptが呼ばれる:

smp_apic_timer_interrupt:
  - ack_APIC_irq: apic_write_around(APIC_EOI, 0)
  - irq_enter
  - smp_local_timer_interrupt:
    - profile_tick(CPU_PROFILING, regs): Profiling the kernel code
      - timer_notify: if start profiling (echo 1>/dev/oprofile/enable)
        - oprofile_add_sample: add sample for optimizer profile
      - profile_hit: Profiling the kernel code using
    - update_process_times(user_mode(regs)):
      - account_(user|system)_time: update `p->(u|s)time`; how long the current process has been running
      - run_local_timers(): invoke TIMER_SOFTIRQ handler(run_timer_softirq)
        - raise_softirq(TIMER_SOFTIRQ):
          - raise_softirq_irqoff: check pending softirq existed
            - irq_stat[smp_processor_id().__softirq_pending] << 2**nr: __raise_softirq_irqoff(nr);
            - wakeup_softirqd: if necessary(exec `wake_up_process(tsk)`)
      - rcu_check_callbacks if rcu_pending:
      - scheduler_tick: keeps the current->time_slice up-to-date (usually decrease)
  - irq_exit: 条件を満たせばdo_softirqが実行される

processの起動時間を更新したり、processのtime_slice(schedulerのためのprocessの持ち時間)の更新をしている。また、optionalでprofiling(kernelのボトルネックがどこか探すために有効に)してたりする。つまり、各CPUで定期的に確認したいことを実行している。

raise_softirq_irqoffでsoftirqをpendingにする(今回は、TIMER_SOFTIRQのbitをONにする)。

timer softirq

softirqがいつ実行されるかは、irq_exitの際にinvoke_softirq(same as do_softirq)を実行することが多い。

// kernel/softirq.c
// void irq_exit(void)
  // skip
      if (!in_interrupt() && local_softirq_pending())
      invoke_softirq(); // same as do_softirq

にて、irq_stat[smp_processor_id()].__softirq_pendingのbitが立っている場合、softirqのactionが実行される。例えば、TIMER_SOFTIRQのbitが立っている場合は、do_softirq -> __do_softirq -> h->action(h);(run_timer_softirq)が実行される:

// kernel/softirq.c
// __do_softirq
        pending = local_softirq_pending();
        // skip
    h = softirq_vec;
    do {
        if (pending & 1) {
            h->action(h);
            rcu_bh_qsctr_inc(cpu);
        }
        h++;
        pending >>= 1;
    } while (pending);

具体的には、pendingは以下のいずれかで、HI_SOFTIRQのbitが立っていたらaction(tasklet_hi_action)が実行され、次にTIMER_SOFTIRQのbitが立っていたら、action(run_timer_softirq)が実行され,...と続き、最後にTASKLET_SOFTIRQのbitが立っていたら、action(tasklet_action)となる。

// include/linux/interrupt.h
enum { HI_SOFTIRQ=0, TIMER_SOFTIRQ, NET_TX_SOFTIRQ, 
  NET_RX_SOFTIRQ, SCSI_SOFTIRQ, TASKLET_SOFTIRQ};

run_timer_softirqはdynamic timersを管理し、timeoutが来たものに関しては、callbackを実行する関数だ。これに関しては、詳細はUnderstanding Linux Kennel ch.6 Dynamic Timersが詳しいので、そちらに譲る。

感想

timerに関してはだいたい全体像を掴んだが、interruptはeflags.IFのON, OFF, preempt, spinlock, re-schedule(TIF_NEED_RESCHED)が絡み合っているので、これよりも更に考えることがある。それについては、今後一つ一つ的を絞って考察していけば良いかな、と感じた。まずは一本の糸を解きほぐせたかなぁ。

次回は、interruptか各種timerのcalibrationの実装詳細をみていきたい。

補足

Understanding Linux kernel の ch.7に関して、p.232( The Linux Timekeeping Architecture )とp.241(Updating System Statistics)の部分の箇条書きがコードのどの部分に相当するのかをメモ

  • Update the time elapsed since system startup: handle_IRQ_event -> timer_interupt -> jiffies(tick count)
  • Update the time & date .. update_times
  • Determine, for every CPU, how long the current process has been running, and preempts it if it has exceeded the time allocated to it. ..account_(user|system)_time
  • update resource usage statistics
    • Checking the CPU resource limit of the running processes .. update_times -> calc_load
    • Updating statistics about the local CPU workload .. update_process_times
    • Computing the average system load .. set nmi_watchdog parameter (entry point is NMI interrupt, do_nmi)
    • Profiling the kernel code .. profile_tick
  • Checks whether the interval of time has elapsed
    • Software Timers
      • dynamic timers: run_timer_softirq as TIMER_SOFTIRQ action.
      • interval timers(PITとは無関係): setitimer()[system call]
    • Delay Functions: (u|n)delay (intenally, use TSC counter)

  1. 補足にまとめてみた

  2. ch.6 The adjtimex( ) System Callを参照のこと。

  3. 実際には、start_kernel -> time_init -> select_timerで複数あるうちのどれを用いるかを決定する

  4. TICK_NSECはUnderstanding Linux Kernel ch.6 のProgrammable Interval Timer (PIT)にて、On a PC, tick_nsec is initialized to 999,848 nanoseconds (yielding a clock signal frequency of about 1000.15 Hz)と書いてあるので、上記の数字であっていそう。

  5. init 関数自体は、start_kernel -> rest_init -> kernel_thread(init, NULL, CLONE_FS | CLONE_SIGHAND);で駆動する。

  6. ここのコードの追い方がわかりにくいが、include/asm-i386/mach-default/entry_arch.hBUILD_INTERRUPT(apic_timer_interrupt,LOCAL_TIMER_VECTOR)のマクロが効いてる。こちらもinterruptの記事でまとめられたらなとおもう。

linux2.6の場合のExceptionと`int $0x80`(system call)の挙動

linux2.6の場合のExceptionとint $0x80の挙動

前の記事でxv6ではどうなのかを述べた。今回はlinux kernel(2.6.11)の場合のexceptionとint $0x80の挙動についてまとめる。今回も長いので、I/O APIC, local APICがからんだinterruptは後回しにしたい。

referenceは前の記事を参考にしてね。

IDTの初期設定

x86(32-bit)では、arch/i386/kernel/head.Sのstartup_32がprotected modeのentrypointになっており、registerの設定をいろいろした後に、start_kernelに飛ぶ。この関数は、init/main.cにある。

  • 最初にarch/i386/kernel/head.SIDTを初期化して、とりあえずロードまで済ませている。

  • start_kenel -> trap_initのset_**_gateIDTのentryを設定する。sys_call(0x80)とexceptionの設定

  • start_kernel -> trap_init -> cpu_initで再度IDTをロード

  • start_kernel -> init_IRQにて、IDTのentryをinterrupt gateに初期化する。syscall(0x80)の部分はtrap_initで設定されているのでskipしていることに注意。

// init_IRQ in arch/i386/kernel/i8259.c
  // init_IRQ
  // skip
    for (i = 0; i < (NR_VECTORS - FIRST_EXTERNAL_VECTOR); i++) {
        if (i >= NR_IRQS)
            break;
    // void set_intr_gate(unsigned int n, void *addr)
    // // _set_gate(idt_table+n,14,0,addr,__KERNEL_CS);
        if (FIRST_EXTERNAL_VECTOR + i != SYSCALL_VECTOR) 
            set_intr_gate(FIRST_EXTERNAL_VECTOR + i, interrupt[i]);
    }
  // skip

ここで、interruptarch/i386/kernel/entry.Sで定義されているcallbackを要素に持つ配列。次回以降で詳しくみていく。

exception

divide_error exception(#0)を例に取る。 User landから呼ばれるので%csのRPL(CPL)は3である。

hardware側の処理 ~ do_divide_errorまで

前節で、start_kenel -> trap_init -> set_trap_gate(0,&divide_error);と設定した1

hardware側の処理の概要は、http://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95 で書いたが、ここでは、TSSの設定だけ見る。

// start_kernel -> trap_init -> cpu_init(void)
  // skip
  // t->esp0 = current->thread->esp0;
    load_esp0(t, thread);
    // #define set_tss_desc(cpu,addr) __set_tss_desc(cpu, GDT_ENTRY_TSS, addr) GDT_ENTRY_TSS=GDT_ENTRY_KERNEL_BASE + 4
    set_tss_desc(cpu,t);
    load_TR_desc(); // #define load_TR_desc() __asm__ __volatile__("ltr %%ax"::"a" (GDT_ENTRY_TSS*8))

なので、TSSにloadされるesp0はprocのstack(thread_info)内にあることがわかる。

例外が発生した場合、権限周りは大丈夫として、スタックにレジスタが積まれる。後ほどみていくが、struct pt_regsが形成されていく。

hareware側では

struct pt_regs {
    long ebx;
    long ecx;
    long edx;
    long esi;
    long edi;
    long ebp;
    long eax;
    int  xds;
    int  xes; // ES
    long orig_eax; // ORIG_EAX
  // these below register is stored by hardware automatically(the previous values)
    long eip;
    int  xcs;
    long eflags;
    long esp;
    int  xss;
};

でregisterがpushされた結果、long eip;まで自動的にstackがgrow downする。(下に伸びるので、struct pt_regsの要素はxss(stack segment)の方向から構築されていく。ESORIG_EAXはconstantとして指定されているが、すぐ下のコードに出てくる。

その後、arch/i386/kernel/entryにて

ENTRY(divide_error)
    pushl $0 // pt_regs.orig_eax
    pushl $do_divide_error  // pt_regs.xes
    ALIGN
error_code:
    pushl %ds // pt_regs.xds
    pushl %eax // pt_regs.eax
    xorl %eax, %eax // reset %eax = 0
    pushl %ebp // pt_regs.ebp
    pushl %edi // pt_regs.edi
    pushl %esi // pt_regs.esi
    pushl %edx // pt_regs.edx
    decl %eax // %eax = -1
    pushl %ecx // pt_regs.ecx
    pushl %ebx // pt_regs.ebx
    # cld instruction to clear the direction flag eflags.DF
    cld
    # NOW, %esp(current stack pointer) is at &pt_regs, which type is `struct pt_regs`.
    movl %es, %ecx # %ecx <= %es # TODO: why?
    movl ES(%esp), %edi     # get the function address($do_divide_error)
    movl ORIG_EAX(%esp), %edx # set the error code in %edx
    # pt_regs.orig_eax <= -1  to separate from syscall instruction(0x80)
    movl %eax, ORIG_EAX(%esp)
    # %ecx <= 0x20(%esp) # TODO: why?
    movl %ecx, ES(%esp)
    # designate user data segment in %ds, %es
    movl $(__USER_DS), %ecx
    movl %ecx, %ds
    movl %ecx, %es
    movl %esp,%eax # set the stack pointer(&pt_regs) in %edx
    // call do_divide_error
    call *%edi
    jmp ret_from_exception

と処理が走る。個々でやっていることは、struct pt_regsの構築とsegment registerの設定だ。 %ediにはdo_divide_error関数へのpointerが入っているので、call *%edido_divide_errorが動く。 これが終わったら、ret_from_exceptionに移動する。

Note) xv6では、vectors.plの

#   vector0:
#     pushl $0
#     pushl $0
#     jmp alltraps

および、trapasm.Sの https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/trapasm.S#L4-L20 に対応する。struct pt_regsstruct trapframeに対応していることが見て取れる。

do_divide_error

do_divide_errorそのものはコードになくて、arch/i386/kernel/traps.cにてDO_VM86_ERROR_INFO( 0, SIGFPE, "divide error", divide_error, FPE_INTDIV, regs->eip)というマクロで一般化されているので、ばらしてみる:

// #define fastcall __attribute__((regparm(3)))
fastcall void do_divide_error(struct pt_regs * regs, long error_code) {
    siginfo_t info;
    info.si_signo = signr;
    info.si_errno = 0;
    info.si_code = sicode;
    info.si_addr = (void __user *)siaddr;
    if (notify_die(DIE_TRAP, str, regs, error_code, trapnr, signr) == NOTIFY_STOP)
        return;
    do_trap(trapnr, signr, str, 1, regs, error_code, &info);
}

雰囲気的には、do_trap関数を呼ぶようだ。更にこの関数を除くと、regs->xcsは3(exception呼び出し前のCPL=3)なので、trap_signallabelに遷移する...

fastcallとはなんぞや? これは、関数の引数とregisterを直接対応させることができる。regparmはGCC拡張で、

On x86-32 targets, the regparm attribute causes the compiler to pass arguments number one to number if they are of integral type in registers EAX, EDX, and ECX instead of on the stack. Functions that take a variable number of arguments continue to be passed all of their arguments on the stack. https://gcc.gnu.org/onlinedocs/gcc/x86-Function-Attributes.html

とある。通常は、関数呼び出しの前にスタックに積んで置く準備をする必要があるが、今回の場合、

 movl ES(%esp), %edi     # get the function address($do_divide_error)
    movl %esp,%eax # set the stack pointer(&pt_regs) in %edx

の用に、%eax, %ediをセットしているので、これらが、(struct pt_regs * regs, long error_code)に対応する。stack取り出さないで、registerを直接使うという点でfastcallなんだろう。

notify_diekprobe_exceptions_notifyがcallbackとして呼ばれ、notify_dieの第一引数で戻り値が決定するようだ。今回はDIE_TRAPで、NOTIFY_DONEとなるので、条件分岐はfalseとなる。したがって、どのみちdo_trapが呼ばれる。

do_trap

infoはstruct siginfoでmemberが.si_signo: SIGFPE, .si_code: FPE_INTDIVとなる。force_sig_info -> specific_send_sig_info -> send_signalと続くようだ。user processにSIGFPEを投げるのが仕事っぽい。

struct siginfoはuser landでも出てくる構造体で、sigactionでキャッチするSIGNALを設定してstruct siginfoで受け取れるようにできる。ココらへんは The Linux Programming Interfaceのch21.4あたりで詳しく解説されている。

do_trapが終わったので、ret_from_exceptionを見る。

ret_from_exception

ret_from_exceptionについては、Understanding the Linux Kernelのch4.6が圧倒的に詳しいので、2つだけこの記事で触れる。

1つ目が一番最初のところ。

ret_from_exception:
    preempt_stop   # #define preempt_stop       cli

exceptionの場合、trap gateが入口になる事があるため、eflags.IF=ONのママの場合がある。このため、exceptionの部分だけ、cli命令が付加されている。以降、iret命令が呼ばれるまで2はinterrupt disableの状態が続く。

2つ目がexceptionの一番最後のところ。最終的にrestore_allラベルに飛んで、User landに戻る。

restore_all:
    RESTORE_ALL

#define RESTORE_ALL    \
    RESTORE_REGS \
    addl $4, %esp;  \
1: iret;       \
.section .fixup,"ax";   \
2: sti;        \
    movl $(__USER_DS), %edx; \
    movl %edx, %ds; \
    movl %edx, %es; \
    movl $11,%eax;  \
    call do_exit;    \
.previous;       \ # swaps current section (code) with previous section (data)
.section __ex_table,"a";\
    .align 4;   \
    .long 1b,2b; \
.previous # // swaps curent section (data) with previous section (code)

RESTORE_REGSをバラすと、

restore_all:
    popl %ebx;
    popl %ecx;
    popl %edx;
    popl %esi;
    popl %edi;
    popl %ebp;
    popl %eax;
    popl %ds;
    popl %es;
    addl $4, %esp;
    iret;

再びstruct pt_regsを見る:

struct pt_regs {
    long ebx;
    long ecx;
    long edx;
    long esi;
    long edi;
    long ebp;
    long eax;
    int  xds;
    int  xes; // ES
    // pop above value
    long orig_eax; // addl $4, %esp;
    long eip;
    int  xcs;
    long eflags;
    long esp;
    int  xss;
};

irethttp://cstmize.hatenablog.jp/entry/2019/03/20/xv6%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AEException%E3%81%A8Interrupt%E3%81%AE%E6%8C%99%E5%8B%95 の最後で触れているが、hardware側で%eipやら%espやら%ssやらを復元していく。%eipはexceptionが生じた直後のinstruction pointerだったから、exceptionの処理終了後はここに飛んで作業を再開する。(ただ、SIGFPEは"重い"signalなので、このuser processはabortして死ぬことになるだろう)

Note) .section .fixupはよくわかんないので、TODOに回す。

Note) xv6では、 https://github.com/mit-pdos/xv6-public/blob/b818915f793cd20c5d1e24f668534a9d690f3cc8/trapasm.S#L21-L32 に対応する。同様にiret命令があることがポイント。

int 0x80

つづいてsoftware-generated なinterruptが発生した場合どうなっているのかをみていく。まず、set_system_gate(SYSCALL_VECTOR,&system_call);がstart_kernel -> trap_initで設定されていることに注意する。

syscall interruptが発生した時、hardware側で権限周りを確認後、registerをstackにpushする。その後、arch/i386/kernel/entry.S内のENTRY(system_call)からソフトウェア的な処理がスタートする。

%eaxにはsystem callのnumberを保存しているので、call *sys_call_table(,%eax,4)が呼ばれ、所要の関数に飛ぶ。この処理が終われば、syscall_exitラベル、restore_allラベルと進んでいきiretでUser spaceに引き戻される。

ただし、sys_execveの場合は、最終的にuser processに飛んだままになるかもしれない(処理が帰ってこない)ので、違う記事にて処理を追いたい。(xv6では、http://cstmize.hatenablog.jp/entry/2019/03/14/GDT%E3%81%A8IDT%E5%91%A8%E8%BE%BA%E3%81%AE%E7%90%86%E8%A7%A3%28xv6%E3%82%92%E4%BE%8B%E3%81%AB%29 の記事の"forkからinitまで"のフローに簡単にまとめている)

syscallの詳細はUnderstanding Linux kernelのch10にあるみたいだが、まだ読んでないので読んだらまとめたい。

exception中のinterruptの挙動

exception中にinterruptが生じるか否かは実はexceptionの種類によって異なる。interrupt gateの場合はeflags.IFがOFFになるので、手動でONにしない限り、interruptは発生しない。しかし、trap gateの場合はeflags.IFフラグはexceptionの前後でそのまま3。(TSSにあるeflagsエントリはch.7.2.1によれば、EFLAGS register field — State of the EFAGS register prior to the task switch.なので、前の状態を保存するためのもの)

Note) Trap GateとInterrupt Gateの形式的な違いは、Descriptorのtype[43:40]が0b1110だったらinterrupt Gateで、0b1111だったらTrap Gateであるという部分だけである。

divide_errorの場合、したのようにtrap_gate(type: 0b1111とセットされてる)なので、IFはクリアされない。set_system_gateもtypeが0x1111なのでIFはクリアされない。

// arch/i386/kernel/traps.c
// void __init trap_init(void)
    set_trap_gate(0,&divide_error);
    set_intr_gate(1,&debug);
    set_intr_gate(2,&nmi);
    set_system_intr_gate(3, &int3);
    set_system_gate(4,&overflow);
    set_system_gate(5,&bounds);
    set_trap_gate(6,&invalid_op);
    set_trap_gate(7,&device_not_available);
    set_task_gate(8,GDT_ENTRY_DOUBLEFAULT_TSS); 
    set_trap_gate(9,&coprocessor_segment_overrun);
    set_trap_gate(10,&invalid_TSS);
    set_trap_gate(11,&segment_not_present);
    set_trap_gate(12,&stack_segment);
    set_trap_gate(13,&general_protection);
    set_intr_gate(14,&page_fault);
    set_trap_gate(15,&spurious_interrupt_bug);
    set_trap_gate(16,&coprocessor_error);
    set_trap_gate(17,&alignment_check);
  // in x86, yes
#ifdef CONFIG_X86_MCE
    set_trap_gate(18,&machine_check);
#endif
    set_trap_gate(19,&simd_coprocessor_error);

    set_system_gate(SYSCALL_VECTOR,&system_call); // SYSCALL_VECTOR=0x80

なので、例えば、int $0x80が発生中にinterruptが生じる場合ことももちろんある。例えば、

[syscall開始 -> [local APIC timerが0に -> interrupt開始 -> 処理.. -> interrupt終了 ] -> syscall処理の続行 -> syscallの終了]

とか。

local APIC timerが0になるprocessは別プロセスであってもよく、その場合は、interruptを開始するprocessはexceptionが起こったprocessと別になる。

みたいなことが起こりうる。

exception中のschedulingについて

こちらも起こりうる。arch/i386/kernel/entry.Sの中の ret_from_exception -> resume_userspace -> work_pending -> check thread_info.flags & _TIF_NEED_RESCHED -> work_resched -> call schedule() となり、scheduleはprocess switchのentry pointだから、現在exceptionの処理中にもかかわらず、別のprocessに移動することが有りうる。

_TIF_NEED_RESCHEDがいつ付加されるかは、自分がまだ把握しきっていないので、別の機会に。

Note) ちなみに、上2つの例のように、exceptionやinterruptなどKernel Modeにいるときに別のprocessに移動できる状態のことをpreemptというみたい。通常はexceptionがinterruptが起こったときは発生前のprocessと同じprocessで作業する(exceptionの場合は、stack pointerを先頭に持ってくるのだったし、別で触れるが、external deviceによるinterruptは別途違うstack pointerに切り替えて作業する。)のだが、上記のようにそうならないパターンがいくつかある4

exceptionの入れ子について

exceptionの最中にexceptionが起こった場合は、Double Fault Exception (#DF)に分類され、abortとなる。(同じexceptionが重なることはないというところがポイント)

interruptの最中にexceptionは起こるか?

こちらも起こりうるが、これはinterruptについて解説するときにまとめるのが良いだろう。


  1. _set_gate(idt_table+n: GDT's index, 15: Trap Gate Descriptor, 0: dpl, divide_error: offset, __KERNEL_CS: segment selector);となっている。

  2. 厳密に言えば、call命令で呼び出される関数内でeflags.IFがONになることはあるがassembly内では終了処理中はdisableのまま。

  3. ch.6.12.1.2に When accessing an exception- or interrupt-handling procedure through an interrupt gate, the processor clears the IF flag to prevent other interrupts from interfering with the current interrupt handler. A subsequent IRET instruction restores the IF flag to its value in the saved contents of the EFLAGS register on the stack. Accessing a handler procedure through a trap gate does not affect the IF flag.とある。

  4. Understanding Linux Kernel のch.1の"Reentrant Kernels"の4つの箇条書されたやつがそう。

xv6の場合のExceptionとInterruptの挙動

ExceptionとInterruptの挙動

linux2.6.11の場合のExceptionとInterruptの挙動をまとめようと思って、xv6との比較を書いていたが分量が多くなりすぎたので、簡単にxv6ではException、Interruptをどう処理しているのかをまとめる。

Reference

Glosary

ExceptionやInterruptに関係する用語としては以下の通り(ややこしい..):

  • Exception: ゼロ除算やPage Faultなどのvector0~31までに割り当てられている。c.f) Table 6-1または、ch.6.15
  • Interrupt: timerやdiskなど外部I/O deviceが起こす。vector32~255まで割り当てることができる。int命令(software-generated interrupt)もinterruptに分類される。

  • Process switch .. process間の切り替え(linux2.6ではswitch_toで、xv6ではswtchでやったこと)

  • Interrupt switch .. Interruptが生じたときの切り替え(linux2.6の場合、同じプロセス内で完結するが、Interruptの処理のstackが異なる。Interruptの処理中にInterruptが重なるのも許す。)

  • IRQ(Interrupt ReQuests):

    • IRQ line: Hardware deviceがinterruptを発したいときのsignalを発する線(電話線みたいな). PIC(I/O APIC)につながっている
    • interrupt vector(IV): interruptやexceptionを識別するための番号1。xv6やlinuxではdefaultでIRQ+0x20(#define FIRST_EXTERNAL_VECTOR 0x20)。0~31まではreserved(systemのinterrupt)のためなので。
    • IRQ Descriptor: linuxではstruct irq_desc_rで定義されている。interruptが発生した時ISR(Interrupt Service Routine)が呼び出される。xv6にはISR(Interrupt Service Routine)という概念はないので、IRQ Descriptorは存在しない。
    • PIC(Programmable Interrupt Controller): 外部のdeviceから来たInterrupt達をCPUに伝達するためのcontroller。"Programmable"なので、register(memory上のaddressに配置されてる場合2もある。I/O APICやlocal APICはこれに当てはまる)にRead or Write(もしくはRead/Write両方)することでdeviceの設定を変更できる
      • 8259A PIC: [legacy] legacy CPUに搭載されていたInterrupt Controller。8つのinterruptまで受容できる。(slaveとmasterの2つを使い、15つまで対応) c.f) https://pdos.csail.mit.edu/6.828/2018/readings/hardware/8259A.pdf && pp.14 in http://www.cse.iitm.ac.in/~chester/courses/16o_os/slides/6_Interrupts.pdf
      • I/O APIC(Advanced PIC): 8259A PICの後進で、multiprocessorに対応するためのAPIC。こちらはLocal APICと違い、CPUの搭載数に依存しない。(random|特定)のCPUに指定のinterruptの処理をお願いしたりできる。
        • Interrupt Redirection Table(Redirection Tableとも): I/O APICでinterruptがどのCPUに振り分ける(redirect)べきかを決める表。vector numberとdest CPU(+その他オプション)を対応付ける。(24 entryある) xv6では、ioapicenableでtableの中身を設定できる。また、linux2.6ではset_ioapic_affinity(=set_ioapic_affinity_irq)でCPUの振り分けを変更できる。
      • local APIC: I/O APICとセットで使われる。各CPUに存在するAPIC(なので"local")で、HardWare Deviceが発したinterruptがI/O APICを介してlocal APICに振り分けられる。LAPICとも言ったりする。 c.f.) Table10-1にregister一覧がある
        • LVT(Local Vector Table): local APICにてvector number(32~)とLVTのindexを対応させる必要がある(32 ~ 255はuser-definedのinterruptなので)。その対応表。 c.f) Ch10.5.1 & Figure 10-8
        • TPR(task priority register): arbitration priorityが格納されているregister.
        • ICR(Interrupt Command Register): local APICにあるregister。IPI(InterProcessor Interrupt)を別のCPUに伝達する時の設定諸々を格納するregister c.f.) Figure10.12
        • EOI(End Of Interrupt) Register: Interruptの終わりを知らせるレジスタ
        • LINT0, LINT1: local APIC interruptに予約されてるIRQ line.
        • Local APICには他にもregister達があるようだ... c.f.) Table10-1
  • SMP(Symmetric MultiProcessing): 同等な2つ以上ののCPUが一つのmemoryとつながっている構造(CPU達がmaster-slaveの関係になっていない) 外部のI/O deviceから来たInterruptを各CPUに均等に振り分けたりできる。

    • IPI(InterProcessor Interrupt): あるCPUから他のCPU(broadcastも含め)に向かってやり取りするためのInterruptのこと。I/O APICを経由して、該当のCPUのlocal APICに伝達する。
      • SIPI(Startup IPI): 最初のCPUの初期化のときに、他のCPUをbootさせるための合図
  • NMI(NonMaskable Interrupt) .. disableにできないInterrupt. c.f) Interrupt 2—NMI Interrupt in ch. 6.15

    • INTR pin: [legacy] local APICがdisableのときに用いられる。externel interruptの受取先。
    • NMI pin: [legacy] local APICがdisableのときに用いられる。disableにできないexternel interruptの受取先。
  • IDT(Interrupt Descriptor Table) .. Gate Descriptorというentryが格納された配列。Interruptの番号が表のindexに対応してdispatchされる。IDTR命令でIDTのbase addressを登録。

    • gate descriptor: IDTのentryでOffset([63:48], [15:0])にcallbackのaddressを格納している
      • Interrupt gate (DPL:0): used for all interrupt handlers
        • System Interrupt gate .. same as Interrupt gate except DPL=3 (int3instruction)
      • Trap gate (DPL:0) .. used for most Linux exception handlers
        • System gate: same as Trap gate except DPL=3. It's used for int $0x80 instruction
      • Task gate (DPL:0) .. only used for "Double Fault Exception"
  • CPL(Current Priviledge Level): %cs(code segment register)のRPL([1:0]) c.f) Figure3.6

  • DPL(Descriptor Priviledge Level): (Segment|Gate) DescriptorのDPL([46:45])

  • kernel control path: the sequence of instructions executed by the kernel to handle a system call, an exception, or an interrupt.

用語が山のようにあるが、次の節以降で断りなく各種用語を使っていくので、適宜参照してください。

Note) 最初LVTをIDTのEntryのOffset([63:48], [15:0])(callback)の表かと勘違いしていたが、Local APICにあるregisterであって、IDTとは関係がない。LVTについては、Intel SDMのTable 10.1を見れば雰囲気がよく分かると思う。

ExceptionとInterruptの挙動

xv6のExceptionやInterruptの処理を追っていく。

初期化

InterruptやExceptionが起こる時のために、IDTのentryにcallbackが呼ばれるように設定できる。加えて、Interruptの場合は、IRQからvector numberの変換(といってもIRQ+32という単純なもの)並びに振り分けるcpuの設定をI/O APICのRedirection Tableに書き込む。

  • local APICの初期化と設定 (main 関数のlapicinitで。timer(IRQ_TIMER), LINT0, LINT1, End Of Interrupt(EOI) register, Error Status Register(ESR), Task Priority Register(TPR)の設定 etc..)
  • I/O APICの初期化(main関数のioapicinitでioapicwrite(REG_TABLE+2*i, INT_DISABLED | (T_IRQ0 + i)); ioapicwrite(REG_TABLE+2*i+1, 0);)

  • exception, interruptの設定

    • main() 関数の tvinitでIDTの初期化とsyscall(0x40)を呼び出すためのTrap-gate descriptorの設定( SETGATE(idt[T_SYSCALL], 1, SEG_KCODE<<3, vectors[T_SYSCALL], DPL_USER);
  • Interruptの設定(I/O APICの Interrupt Redirection Tableに設定を書き込む)
    • main() 関数の console_initでIRQ_KBD=1の設定(ioapicenable(IRQ_KBD, 0);)。interrupt vectorの#32をcpu#0に送る設定
    • main()関数のuart_initでIRQ_COM=1の設定(ioapicenable(IRQ_COM1, 0);)。interruptの#36をcpu#0に送る設定
    • main()関数の ideinit(DiskのR/W) でIRQ_IDE=14の設定(ioapicenable(IRQ_IDE, ncpu - 1);) interrupt vectorの#46をcpu#1に送る設定
  • idtinitでIDTのロード(lidt)

と設定。xv6の場合、Interruptの処理を任せるCPUは決め打ちにしている。linuxでは、もうちょっと洗練されて設定されてる。

Exception発生直後のhardware(x86)の対応

雑に言うと、Exception, Interruptが発生した時、権限の確認をした上で、各種レジスタをpushする。その後、Exception or Interruptの番号(vector number)から、IDTからそれに対応するentryがわかるので、callbackのアドレスに飛んで実行する。

この流れを詳しめにみていく。 User spaceでException, Interruptが発生することに注意する(linuxではinterruptについては入れ子を許すのでもうちょっと複雑) また、eflag.IFがONである必要がある。

  1. Exceptionが発生した(例えば、Divide Errorは#0) 以下の2~8はhardwareが自動的に行う処理
  2. IDTRからIDTの場所がわかるので、IDTのindexのidxを参照できる。(Base address(callback関数のアドレス)やselectorの場所がわかるよ)
  3. check (CPL=%csのRPL)<=(%csのindex[15:3]の場所のSegment DescriptorのDPL) && (CPL=%csのRPL)<=(IDT[idx](Gate Descriptor)のDPL)をチェック
  4. 3で、もし、(CPL=%csのRPL)!=(%csのSegment DescriptorのDPL) ならば、(%csのSegment DescriptorのDPL) の権限に対応するssとespをロード。TR=>TSS DescriptorのBase Address([63:56], [39:32], [31:16]) => TSSと辿れる。xv6の場合、4は原則当てはまる。右辺=0なので、%ss0(stack segment register)と%esp0となる。
  5. 古いssとespを新しいスタックにpushしておく
  6. eflags, cs, eipをスタックにpush, hardware error codeもあったらそれもスタックにpush
  7. eflagsのIFをOFFに。c.f) ch.6.12.1.
  8. IDT[idx]にSegment Selector[31:16]とOffset([63:48], [15:0])があるので、それぞれ%csと%eipにloadする。
  9. (%eipはinstruction pointerなので、そのアドレスにある命令を順次実行していく)

xv6では、vector numberがiのときはIDTのOffset(callbackのbase address)がvector_##iとなっているので、そちらの関数に飛んでソフトウェア的な(OS側の)処理が開始される。

Interrupt発生直後のhardware(x86)の対応

こちらは外部I/Oがinterruptを発生させるので、最初の部分がプログラム内で発生するExceptionよりもやや複雑。

  1. HardwareがInterruptを発する(Diskが読み終わったとか、Timerが0になったとか)
  2. I/O APICIRQ number(IRQ lineの状態)を受け取る。
  3. I/O APICIRQの番号をvectorの番号に変換して、対象のCPUのlocal APICにsignalを伝達する。(Interrupt Redirection Tableに設定したのだった)
  4. 動的に振り分ける場合、各CPUにarbitration priorityが振り分けられる(task priority register(TRR)に格納されてる) 今回は振り分けるCPUは決め打ちなので、skip

以下、Exceptionの場合と同じ。要するに、外部I/O deviceがInterruptを発生させた時、 I/O APICがどのCPUにInterruptを処理させるのかを決め、該当のCPUにお願いをするところが最初に挟まる。もし、自動で振り分ける場合は、SMPなので、いい感じにInterruptの配分をhardware側で行ってくれる3

Exception発生時

0~31までのexception及び、int $T_SYSCALLのsoftware generated interruptが起こったときが該当。

int $T_SYSCALLが起こった場合は http://cstmize.hatenablog.jp/entry/2019/03/14/GDT%E3%81%A8IDT%E5%91%A8%E8%BE%BA%E3%81%AE%E7%90%86%E8%A7%A3%28xv6%E3%82%92%E4%BE%8B%E3%81%AB%29#switchuvm の"forkretからinitまで"のところでだいたい確認している。ポイントとしては、trap()関数がException, Interruptを振り分けているところ。

// trap.c
void
trap(struct trapframe *tf)
{
  // if `int $T_SYSCALL` occurs..
  if(tf->trapno == T_SYSCALL){
    if(myproc()->killed)
      exit();
    myproc()->tf = tf;
    syscall();
    if(myproc()->killed)
      exit();
    return;
  }

  switch(tf->trapno){
  // skip
  default:
    // If Interrupt or Exception is occured at DPL_KERNEL, something wrong happens..
    if(myproc() == 0 || (tf->cs&3) == 0){
      // skip
      panic("trap");
    }
    // skip
    myproc()->killed = 1;
  }

  // if 0~31 exception occurs..
  if(myproc() && myproc()->killed && (tf->cs&3) == DPL_USER)
    exit();

Interrupt発生時のOS側の対応

vector_##iが呼ばれ、trap()関数で、IRQ_TIMERの場合、IRQ_IDEの場合..とswitch文により振り分けられ、個別のinterruptの処理が走る。これが終わったら、I/O deviceによるinterruptの場合はlapicw(EOI, 0);でEOI registerにInterruptの終わりをLocal APICに伝えて、Interruptが終わる。

コード的には、

// trap.c
trap(struct trapframe *tf)
{
 // skip // trapno means vector number.
  switch(tf->trapno){
  case T_IRQ0 + IRQ_KBD:
    kbdintr();
    lapiceoi();
    break;
  // skip

linux2.6では、Interrupt発生時にvectorに紐付いているcallbackが呼ばれるところまでは同じだが、その後、ISR(Interrupt Service Routine)を呼び出す。この呼び出し方複雑なので、次あたりにまとめたい。

trap関数終了後のOS側の対応

trap関数が終了した後は、trapasm.Sにて、stackをpopして、最後にiret命令を実行する。iret命令はinterrupt or exceptionでhardwareが自動的にやったことの逆を行う。

詳細は、以前 https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#iret%E3%81%A8ret%E3%81%AF%E3%81%A9%E3%81%86%E9%81%95%E3%81%86 でまとめた。または、Understanding the linux kernelのHardware Handling of Interrupts and Exceptionsで詳しめの解説がある。

ポイントとしては、interrupt発生した後は、kernel landで作業していたものが、iretにより、user landに引き戻されるということだ。勿論、%eipやら%ssやら%espは前の状態に戻る。

ちなみに、linux2.6では、ret_from_intrおよび、ret_from_exceptionが同じ役割を担っている。


  1. pp.134に、Each interrupt or exception is identified by a number ranging from 0 to 255; Intel calls this 8-bit unsigned number a vectorとある。

  2. memory-mapped I/Oという。https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#io-port%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6 を参照のこと。

  3. ただしhardwareによっては例外はあるらしく、linux2.6では、kirqd(kernel thread)で配分のバランスを適宜取るようだ。

`switch_to`を読んでみる

reference

概要

linux kernel 2.6.11より

schedule() => context_switch(rq, prev, next); => switch_to(prev, next, prev); とつながる。

scheduleを実行する前段階としては、

  • proc->stateをWAIT状態にする
  • wait_queueのlistにこのproc(正確には、このprocをpointerにもつwait_queue_t型の変数)を登録する。
  • schedule()が実行される +終わったら、wait_queueのlistからこのprocを除く

というのがよくある流れっぽい。

switch_toの直前のプロセスをProcessAとする。 switch_toの実行途中(より正確にはjmp __switch_toが終了する直後)に別プロセス(ProcessB)に移行するので、今までRUNNINGしていたプロセスが眠りについて、別の(wait状態の)processがまたRUNNINGに移行する。

このように、次から次にprocessが移行していく。つまり、

ProcessA -> ProcessB -> ... ->

移行しているとは言っても、stack(%esp)とprogram counter(%eip)が変化するのであって、User landからKernel landに権限昇格しているわけではない。(Kernel領域で作業していることには変わらない。)

当然ProcessAはまだ完了しているわけでないので、しばらくすると、ProcessAに主導権が再び得られることになる。その時は、"jmp __switch_to\n"から処理がスタートしてProcessAで使っていたregisterたちを次々と復元していく。

雰囲気的にはこんな感じだが、実際のコードをみていく。assemblyなので慣れないとなかなかむずい。そこで、ひとつずつコードを紐解いていきたい。

code

// include/asm-i386/system.h
#define switch_to(prev,next,last) do {                   \
   unsigned long esi,edi;                        \
   asm volatile("pushfl\n\t"                    \
            "pushl %%ebp\n\t"                 \
            "movl %%esp,%0\n\t"   /* save ESP */      \
            "movl %5,%%esp\n\t"   /* restore ESP */   \
            "movl $1f,%1\n\t"      /* save EIP */      \
            "pushl %6\n\t"     /* restore EIP */   \
            "jmp __switch_to\n"                \
            "1:\t"                     \
            "popl %%ebp\n\t"                  \
            "popfl"                     \
            :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
             "=a" (last),"=S" (esi),"=D" (edi)            \
            :"m" (next->thread.esp),"m" (next->thread.eip),    \
             "2" (prev), "d" (next));                \
} while (0)

擬似コードはこんな感じかな:

  pushfl # push eflags register in the stack
  pushl %ebp # push ebp(base pointer) register in the stack
  movl %esp, [prev->thread.espのアドレス] # save %esp register to prev process
  movl [next->thread.espの中身],%%esp # restore %esp
  movl $1f, [prev->thread.eipのアドレス] # save %eip to prev process
  pushl [next<-thread.eipの中身] # `jmp __switch_to`が終了したときに`"1:\t"`のラベルのアドレスまで飛びたいので。
  jmp __switch_to # exec __switch_to
1:
  popl %%ebp # % restore %ebp(base pointer register)
  popfl # restore eflags register in the stack

jmp命令がとても重要で、この命令があるので、別プロセスへと移動できる。

jmp命令はret命令と異なり、戻った先のaddressをスタックに積まないのでpushl [next<-thread.eipの中身]にて手動でアドレス値をスタックに積んでいて、これが戻った先のaddressと解釈されて、別プロセスの関数へと移動できるわけだ。(単純にjumpするだけ)

対してret命令はC言語とかの関数の通り、step inして処理が終わればstep outする感じに似ている。詳しくは、 https://qiita.com/knknkn1162/items/9bd54e165c6c9edca49b#ret-instruction%E3%81%AE%E5%BF%9C%E7%94%A8 を参照のこと。

上記をふまえたうえでの流れは以下の通り:

  1. %eflags, %ebp, %espをメモリ上に退避
  2. %espをnext processのものに復元 -> 以下、next processのstack上で作業することになる。
  3. %eipをnext processのスタックに積む
  4. jmp __switch_to実行
  5. __switch_toが終了したので、3で積んでいた値を%eip registerにpopする
  6. 次のinstrcutionは%eipの指示す先で、これは次なるプロセスの文脈のアドレス("1:\t"のラベルのアドレス)になる。

__switch_toを説明していないが、これはnext processのstackを基準にいろんなregisterが復元される。例えば、load_TSSのばあい、

tss->esp0 = next->esp0;でtssのesp0にnext processのesp0を保存している。tssstruct tss_structでinclude/asm-i386/processor.hにDECLARE_PER_CPU(struct tss_struct, init_tss);とあるので、CPUごとに一つだけ存在する変数である。1


続いてコードを詳細に追っていく。popflまでがアセンブリ命令でそれ以外はオペランド制約というものに分かれている。まずはアセンブリ命令から。

  • movl %eax, bとあるのは、%eax -> bの方向に代入すると考えればわかりやすい。

  • jmp命令は上記の通り。ret命令との違いを認識できてるかどうか。

一方、オペランド制約わかんなすぎなので とてもありがたい記事 http://caspar.hazymoon.jp/OpenBSD/annex/gcc_inline_asm.html を元にして一つづつばらしてゆく:

# ("movl %%esp,%0" and ) prev->thread.esp <= %0 ( save %esp of )
:"=m" (prev->thread.esp), \
# ("movl $1f,%1\n\t" and ) prev->thread.eip <= %1
"=m" (prev->thread.eip), \
# last <= %2(register) where `%2 == %eax`
"=a" (last), \
# esi <= %3(register) where `%3 == %esi`
"=S" (esi), \
# edi <= %4(register) where `%4 == %edi`
"=D" (edi), \
# %5 <= next->thread.esp (and  "movl %5,%%esp\n\t"(restore %esp))
:"m" (next->thread.esp), \
# %6 <= next<-thread.eip where "pushl %6\n\t"
"m" (next->thread.eip), \
# %2 <= prev (where %2 == %eax)
"2" (prev), \
# %edx <= next
"d" (next)); \
  • オペランド制約は並んでる順番は意味があって、1つ目のオペランド制約が%0に対応する。ただし、"2"とかあったら、%2を使う。

  • =は出力で、後続の変数に値を流し込んでいく。 例えば、"=a" (last) <=> movl %eax, [last変数のaddress]

  • 何もついてなければ入力で、後続の変数からregisterかメモリ上の指定されたアドレスに値を書き込んでいく。例えば、"2" (prev) <=> movl [prev変数のaddress], %2

  • "=m" はleft side valueがregisterではなくメモリ上のアドレスなので、mを指定している。


これまでで未だ不明の点は以下の通り:

  • __switch_tolastはどの場面で使われるのか?

  • next processがswitch_to終了したらどこに行くのか?

前者は This reference, however, turns out to be useful to complete the process switching (see Chapter 7 for more details).とあり、

後者はIf next_p was never suspended before because it is being executed for the first time, the function finds the starting address of the ret_from_fork( ) function

とあるので、次回に回す。

ちなみにxv6において、後者の場合は、forkrethttps://github.com/mit-pdos/xv6-public/blob/xv6-rev11/proc.c#L113 の部分で指定したものがswtch関数のret命令後に効いてくる。 https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#switching%E5%AE%8C%E4%BA%86%E5%BE%8C らへんの図を参考に〜

追記) ここにもおんなじようなことをやってる人がいた .. http://d.hatena.ne.jp/naoya/20070924/1190653790

GDTとIDT周辺の理解(xv6を例に)

Motivation

Understanding the Linux Kernelを読もうとしたけど、生半可な気持ちでは臨めなさそうなので、xv6で理解の確認しつつ、linux kernel 2.6ではどうなの?という把握をすれば良さそう。

そこで、Understanding the Linux KernelのChapter 2: Memory Addressingに備えてGDTとかIDTってなんやねん、っていうのを抑えておきたい。

Reference

Glosary

未だに用語で混乱するのでまとめておく:

  • TSS(Task State Segment): 104 byte. xv6ではint $T_SYSCALLが発動したときに用いられる。(ss0とesp0がint呼び出しでロードされることに注意) c.f) Figure7.2
  • TR(Task Register): TSS Descriptorの先頭ポインタをロードするためのregister(GDTからのoffset[byte]) c.f) Figure 7.5

  • GDT(Global Descriptor Table): segment descriptorをentryとするtable。

  • GDTR(GDT Register): GDTの先頭ポインタを登録するためのregister (lgdt命令でロード) c.f) Figure 2-6
  • segment descriptor: GDTのentry。64bit(8byte). c.f) Figure 3-8

    • Code & Data Segment Descriptor: segment descriptorの一種。主にsegmentationの設定。
    • TSS Descriptor: 主に、int $T_SYSCALLの発動時に用いられる。xv6ではTSSはprocess(struct proc)に依存するので、switchuvmで都度TSS Descriptorを設定する必要がある。 c.f) Figure 7-3.
      • Base address([63:56], [39:32], [31:16]): TSSの先頭アドレスを指定する。
  • segment register: %cs(code segment), %ds(data segment), %ss(stack segment) registerなど(optionalで%es, %fs, %gs)。xv6では、%csljmp $(SEG_KCODE<<3), $start32で定めている。その他のregisterはbootasm.Sのstart32以降で定めている。

    • segment selector[15:3]: Segment Registerのhidden part(16bit identifier). GDTの先頭ポインタからのoffset[byte]>>3を指定する c.f) Figure 3-6 and Figure3-7
  • %cr3 register: Page Directory Base Register(PDBR)とも言う。page directoryの先頭アドレスを指定する。xv6ではswitchkvmswitchuvmで使用されてる

  • IDT(Interrupt Descriptor Table): Interruptの番号に応じてdispatchされる

  • IDTR: IDTの先頭ポインタを登録するためのregister (lidt命令でロード) c.f) Figure 2-6
  • gate descriptor: IDTのentry. c.f.) Figure 6-2

    • Interrupt Gate Descriptor: 0~31はSystemで定められてるInterrupt. c.f) Section 6.15
      • DPL([46:45]): xv6では3(DPL_USER)としている
      • Segment Selector([31:16]): GDTRからのoffset[byte]。これの設定に応じてDescriptorのCPLが定められる
      • Offset([63:48], [15:0]): interruptが発生したときのentrypointを設定する。
    • Trap gate Descriptor: xv6では64(T_SYSCALL)のentryで指定されてる。
      • DPL([46:45]): xv6では0(DPL_KERNEL)としている
      • Segment Selector[31:16]: GDTRからのoffset[byte]。これの設定に応じてDescriptorのCPLが定められる
      • Offset([63:48], [15:0]): interruptが発生したときのentrypointを設定する。
    • Call Gate Descriptor: linux, xv6では未使用
    • Task Gate Descriptor: linux, xv6では未使用。linuxではDouble Fault Exception(#8)の時のみ使用される。
  • Local Descriptor Table (LDT): xv6では未使用。linux2.6では、GDTの内部にあって、すべてのprocessで共有されるものとして使用されてる


準備

GDTとIDT周りの説明をxv6を例にとって行いたいが、ややわかりにくい事柄を先に処理してしまう。馴染みがなければ、一旦、「xv6でのGDT, IDT」の節まで飛ばして良いと思う。

struct taskstateとstruct trapframeの違い

両者はややわかりにくいので、違いを簡単に述べる。

  • struct trapframe: processのkernel stack内にある構造体。trapret内のiret命令で使われる
  • struct taskstate: struct cpuの内部にある構造体で、TSSのこと。int $T_SYCSCALL発動時にTR(Task Register) -> TSS Descriptor -> TSSとたどることでTSSを発見する。TSSにはkernel stackのpointerであるesp0があるので、esp0を%espにロードすることで、kernel landでの作業ができる。

switchuvm

switchkvmは%cr3 register(Page Directory Base Register(PDBR))にpage directoryの先頭アドレスをさせるだけの処理だが、 switchuvmは%cr3 registerの登録の前に以下のことを行う:

  1. TSS Descriptorを(再)構成
  2. TSSを(再)設定(ss0はGDTのSEG_KDATA、esp0はproc->kstackとする)
  3. TRをセット

switchuvmはuser landからkernel landへの移動の際の道標的な役割を果たす関数である。user landでint $T_SYSCALLしたときに、kernel landに移り、%espもkernel stack上のポインタ(proc->kstack)を指し示す。(一方、kernel land->user landへの移行はiret命令を用いる。)

switchkvmは初期のboot時に使っていたentrypgdirからkpgdirへの移行をするためだけに用いられるのであんまり気にしなくて良い。kpgdirはsetupkvmにより作成される

その他補足

  • GDTは各CPUごとに存在する。xv6ではstruct cpustruct segdesc gdt[NSEGS]というメンバがあるのがそれ。

xv6でのGDT, IDT

main:
  seginit:
    - GDTに segment descriptor(4つ: SEG_KCODE, SEG_KDATA, SEG_UCODE, SEG_UDATA)を設定
    - GDTRを設定
  tvinit:
    - IDTのすべてのentry(0~255)にinterrupt gate descriptorを設定(DPL: 3, CPL: 0)
    - IDTに、T_SYSCALL(64) trap gate descriptorを設定(DPL: 0, CPL: 0)
  user_init:
    allocproc:
      - ptableから未使用のprocAを選ぶ
      - procA->kstackの領域(kstackAとする)をkallocで確保
    - inituvm: initcode.Sを実行するためのユーザー領域(ustack_initcodeとする)をkallocで確保(mem)してmappagesでVirt(mem)-Phys(0)マッピング
    - procA->tf(trapframeA)を埋める(`p->tf->eip = 0`にしてる)
    - procA->state <~ RUNNABLEに
  mpmain->scheduler:
    - RUNNABLEのprocを選ぶ。procAが選ばれるとする
    - switchuvm: TSS descriptor, TSS(cpu->ts)の設定(TSS_Aとする), TRの設定, CR3の設定
    - swtch: 作業領域をkstackAに移す。`ret`で%eipがforkretに移動
  • forkretからinitまで
forkret: inodeの初期化(superblockとlogを読み取り)
  trapret: 
    - trapframeAに格納されていたregisterを復元。
    - iretでユーザーランドに降格する。`p->tf->eip = 0`としていたので、ustack_initcodeに飛ぶ
    initcode.S:
      int $T_SYSCALL:
        (hardware):
        - fetch the n'th descriptor from the IDT, where n is the arguement of `int`
        - check that CPL in %cs(in IDT): 0 is equal to or less than DPL: 0 => OK
        - save %esp and %ss in CPU-internal registers only if PL < CPL
        - load %ss and %sep from TSS(TSS_A)
        - push %ps, %esp, %eflags, %cs, %eip
        - clear the IF(Interrupt enable flag) bit in %eflags
        - set %cs and %eip to the values in the TSS. %eip register tells the computer where to go next to execute the next command and controls the flow of a program.
        vector60:
          - pushl $0, which is errcode
          - push $60, which is trapno
          - jmp alltraps
          alltraps:
            - struct trapframe(trapframeAとする)を構成
            trap->syscall:
              - trapframeAから`curproc->tf->eax`は`SYS_exec`なので、sys_execを実行
              sys_exec: exec("init", {"init", NULL})を実行
                exec:
                  - namei: path(char*)からinode(inode*)を取得
                  - readi: inodeからELF headerとELF program header抜き出す
                  - loaduvm: program segmentをpgdirに反映(mapping)
                  - myproc()->tf(trapframeBとする) を構成 (curproc->tf->eip = elf.entry[init programのentry point])
                  - switchuvm: TSS descriptor, TSS(cpu->ts)の設定(TSS_Bとする), TRの設定, CR3の設定
              - Return falls through to trapret...
              - stack pointerをpopして、trapframeAを崩す
              - `iret`命令呼び出し。trapframeBから、%eipは[init programのentry point]となる。user landに降格。
                init.c->main: openとかforkとかexecとかで`int $T_SYSCALL`が都度呼ばれる(usys.Sを参照)

最後の部分のinit processは基本的にはuser landだが、open, fork, execなどが呼ばれると、int $T_SYSCALLが呼ばれ、kernel landで作業することになる。 TSS_Bで定めたkernel stack(proc->kstack)上でstack pointerが動き回る。

はてブでコメントし続けるとロジカルシンキングの能力がアホみたいに上がった話

社内数人のグループで1、あるビジネス本を読んだ感想文(気づきとか)をお互いに発表する機会があったのだが、個人的に驚くことがあった。 彼(ら)は本の中の一部を引用して、「ここの言葉は自分にとって良かったので、参考にしたいと思いました」と、まるで偉人の名言を自分のセンスで抜粋するかのような書き方をしていた。正直、えっ、コンサルの会社なのにそんなレベルの感想しか書けないの?と思ってしまった。

私自身ははてブを日常的にやっている身なので、ある記事(だいたいはてなでバズった記事)をコメント付きではてブするときは、言葉尻を捉えることなく、著者の言いたいこと(要旨)や行間を読んで、それに対する自分の意見をできるだけ的確にすることを心がけている。2

コンサルってロジカルシンキングの能力必須だと思っていたので、まさか文を引用して「そうだと思いました」みたいなやつを気付きとして発表するなんて想像もつかなかった。ロジカルっていうくらいだから、論理を追っていって著者の論旨を掴んで、シンキングっていうくらいだから、それに対する賛否を考える。。なんてこと朝飯前とは言わずともexcelでsum関数使うくらいのスキルじゃない?

ここで、なんともおこがましいことを考えてしまった。実はその人の感想文のレベルが低いのではなく、はてブのコメントに揉まれているうちに私のレベルが高くなってしまったからだ、と。

この出来事を振り返って、改めてはてブでコメントすることを気に入っている自分に気づいたのだが、せっかくなので、なぜ他のサービスではなく、はてブなのかを考えてみようと思った( PRではなく、あくまで自分の考察 )。理由としては3つある。

一つは匿名性だ。NewsPicksなどの著名人によるコメントとは異なり、はてブコメントは誰が発言したかではなく、何を発言したかで評価される3 (評価とは、この場合星のこと) 。これはすごく良いなと思っていて、例えば、実名制で肩書のすごい人がこうだ、と言ったら、みんなそうなんや、と無意識に受容すると思う。つまり、意見が社会的立場に依存してしまう。私はこれは良くないと思っている。偉いからその人の言うことが尤もだと言うのなら、無名の私は奴隷じゃん。

もう一つは、100字以内でまとめる必要があるということだ。ツイッターよりも更に短い。10字くらいで済む場合もあるが、110字くらいになってしまって、もうちょっとピンポイントに言えないかどうか考える場合もある。書いているうちになんか違う、これも違うと思いながら最後に自分が納得のできる文章を書く場合もある。文字数制限がそこそこ厳しいと、自分の言いたいことをはっきりとロジカルに(誤解のないように)伝える必要性が生じる。自分の思っていることを言語化する作業は、慣れてくると意外と面白いものだ。また、1人たかだか100字なので、一記事で300ユーザーくらいのコメントが有っても数分~十数分で読んでしまえる。自分と全く違う意見だが、面白いなと思うコメントも有ったりして、いつの間にか時間を吸い取られる。

最後の一つは匿名性と絡んでいるが、よほど犯罪めいたコメントをしない限りは炎上を避けることができる、ということだ。ブログなら、「この意見は炎上するかも」という意見でも、はてブなら割と自由にコメントできる、言いたいことを言える。利害関係が発生し得ないのが、実名制と違っていいとこだよね。これは私の体験談なのだが、1年半くらい前、ある弁護士のブログに対してブコメしたら4、総スカンを食らった。ただ自分の意見として間違ったことは言っていない、と思っていたし、消したくないと思っていたので、しばらく放っておいたら勝手に鎮静化した。勿論仕事などに影響が出るはずもない。1,2週間くらいあとにブコメを再開してみたが、全く問題なかった。


勿論、良いことばかりかと言うとそうではなくて、はてな村の(良くない意味での)思想に偏ったり、「ミソジニー」や「N=1」、「睡運瞑菜」など日常生活で滅多に使わない言葉を無駄に覚えたり、リアルで犯罪が起こったり、そういった負の側面もある。が、〇〇とハサミは使いよう、という通り上手に使えば、自分の意見も心置きなく言えるし、ロジカルシンキングの能力も自然に高くなるしということで、個人的には満足している。

ただ、良いコメントしたらお星さまじゃなくて、お金がほしいよねぇ。いや、両方欲しい😊


  1. 正確に言うと、全社員のうちからランダムで7,8人。私自身はエンジニアだが、弊社はエンジニアよりもビジネス側の人が圧倒的に多い。

  2. 勿論大喜利するときも、ふざけたコメントするときもあるよ。また、個人としての適切が、全体にとっての適切ではないことも承知の上です

  3. 早めにブコメした人や、はてな村で有名な人が星を集めやすいというのはある。それは仕方ないっちゃ仕方ないかな

  4. 電車での痴漢冤罪に対する弁護士の意見への自身のブコメ http://b.hatena.ne.jp/entry/337569348/comment/knknkn11626 今だから補足しておくと、インフォームド・コンセントが浸透している医者と、そういう概念が浸透していなさそうな弁護士を比較したかったのだが、「お前の意見は上から目線だ」と言われてしまい、誤解されて伝わったので、炎上ってこえーって思いました。

1月の棚卸し

なるべく月末にやったことの棚卸しをしたいと思うので、毎月継続して書いていくつもり1

1月は7日くらいまでキーボードやVGAFPGAをつないで、プログラム書いて動作確認したりしていた。しかしながら、会社が始まるとなかなか思うように進捗を生み出せず、また、7,8ヶ月くらい一貫して低レイヤーのことばかりをやっていたため、なにか全く別の(できれば自分が今まで全く知らなったことを)息抜きにやってみたほうが良いかな、と思った。

上記の様なことを思った理由をもうちょっと詳しく話すと、もともと低レイヤーの領域をやってみたのは、エンジニアとしてやっていく中で、全く知らない状態で良くないなー、と思ったから。自分は非CS卒なので、去年からやってきて全体像は把握できたかな、という実感を得ている。しかし、次どうしようというところで、消費する時間の割になかなか進捗を生み出せていない事もあって、心の余裕がなくなってきた。また、今の会社はFPGAや組み込みに関する業務は一ミリも扱わないので、報われない無力感を感じ始めていた。


ということで、プログラミングとは別の息抜きごとを探した。最初に、エンジニアの他に法律系の国家資格を取れば、仕事上なんらか有利になるんじゃないかなと考えた。全く違うことをすることで心の余裕も生まれるかも、という思いもあった。また、自分の親戚にぽつぽつ士業の人がいるので、全く向いていないわけではないだろう、とも思った。基本的にはyoutubeに色々動画がある2ので、見たりしていた。

しかしながら、資格取るのに時間費やすとかはあまり得策ではないな、と勉強しながら調べるうちに感じてきた。まず、弁護士、公認会計士などの超高難易度資格者でない限り、資格とっても結構営業の努力は必要で、そんなに甘くはなさそうだ。また、例えば、司法書士行政書士の資格を得たとして、副業としてやっていくにしても、月々の会費がいるので、そもそも本業にしないと黒字化できなさそうだ。うーん。

次に考えたのは、資産運用のためになんかやるor情報を得るということだ。(資産といってもせいぜい社会人4年目の量です) そういえば疎かにしていたなー、と思って。 具体的には、[株式投資始めたい->四季報や決算書が読めない->会計の本を色々読む->財務諸表をだいたい把握した->決算書いくつか読んでみて経験値を上げる]というところの段階まで来た。といっても1月後半くらいから始めたので、2,3週間くらい? 本は何冊か読んだが、以下の本が良かった:

特に、最後の本は決算書について綺麗事でないこと、例えば「BSやPLは費用の先送りである程度利益をごまかせるから、実際のその数字の他に周りの数字も見て信憑性を判断しなさい」的な事が書いてあり、とても良い本だった。と同時に四季報のデータで終わりではなく、隅から隅まで決算書を読み通すのが結局投資の近道なんだな、ということを理解した。


2月はどうするかだが、もうちょっとだけ、決算書を読むことに使っていきたいな、と思う。具体的には6,70%くらい。と言っても今後もずっとそれに時間を費やすことを考えている訳ではなく、あくまでちゃんと自分の中で消化した上で、例えば投資のときに、きちんとした仮説を持てるようになる、位のレベルまで徐々に(3~6ヶ月くらい?)持っていきたいと考えている。

残り30%は、またFPGA再開しようかなぁ(そういえばout of orderの実装を済ませていなかった..)とか、いやUnderstanding the Linux Kernel読んでいないからきちんと読む時間を作ったほうが良いかなぁ、とか考え中。 といっても2月は28日しかないので予定通りにうまくいくかはわからないけどね。


  1. 感想書くと、意外と色々なことを30日の間に考えていて、案外色々やってるやん、という気にさせてくれた(&気持ちも楽になった)ので、今後も月末に自分の考えていること、やったことを棚卸ししていきたい。

  2. https://www.youtube.com/channel/UCs0y1Ho4G0FV7gAUi5pNrPQ とか

今年の自分の感想

今年考えたこととやったこと、やりたいことの棚卸し。

来年8月で30という歳を考え、なんかやばいやろ、みたいな危機感?みたいなのが生まれた結果、今年は6月から本気出した気がする。多分、一日も欠かさず勉強した。

一年を通しての目標としては、低レイヤーの部分を攻めたいという気持ちがあったので、結構達成でき、そこそこ満足感がある。何よりも、一年前に戻りたいか、と悪魔に聞かれたとしても、No, Thank you👿とお断りするだけの努力はした。 モチベーションの源泉としては、密かに尊敬する人ができて、その人が「とりあえず一年はがむしゃらにやろうぜ」みたいなことを言っていて、こんなすごい人でも過去に積み重ねた結果があるからこそなんやな、と感じたため。騙されたつもりでがむしゃらにやってみた。1

1月から6月までは仕事先が変わった&プライベートでいろいろあった ので、rails触ってみたり、周辺のライブラリのコードリーディングしたりみたいなことを主にやっていた。(去年の11, 12月はガッツリrustやっていたが、今年は殆ど触っていない..)

6月からやったこととしては、

  • TLPI ほぼ読む
  • x86 OS(xv6)実装の基本をだいたい把握
  • computer architecture, FPGAの勉強、VHDL書く。

みたいなことをして、あとは型推論コンパイラの分野だけ全然手をつけていないかな、という感じ。(でも、分散とか計算理論的な話とかはあんまりやってないから意外とまだ手をつけていない部分は多いかも。) linux kernelの実装読むとかは結局の所あんまりしなかったが、理由としては、xv6読んだ結果、ハードウェア寄りのことをもっと知りたい、全然知らんかったわと思ったから。現状FPGAVHDL書いたりしている。

FPGAはレゴブロックのように最小の単位で大きなものを作ることができるのが、面白い。(原理を理解して製作する必要があると思う)

あと、twitterも始めた。音楽関連のfollowもそこそこあるが、技術的なことも半分くらいはつぶやいているので、フォローしてね。

プログラミング関連とは全く関係なくやってよかったこと:

  • ヒゲ脱毛 .. 自分は割と童顔な感じの顔つきなので、青ひげで損していたが、ひげの脱毛してかなり良くなった。

  • 携帯の機種変更 .. めんどくさくて5年くらいずっと同じ携帯だったが、とうとう壊れたので携帯変えたら、色々とはかどった

  • プール .. 夏に集中的にプール行ったおかげで、基礎体力が結構ついた


来年 の抱負としては、地に足をつけること。自分のやっているor興味のある分野は万人受けしないし、独り相撲している気持ちになることがある。そういうときに、しょうもない記事や見聞が他人から評価をもらっているのを見ると、なんで自分のやったことに関してはこんな無反応なん?、ってなって弱ってしまう。

そういうときでも、上や下は見ずに、前を見ることを心がけたいと思う。自分のやっていることの方向性は間違っていないと思うので、実を結ぶときは来るはずだ! 少なくともこの一年やってきて、CPUの原理からOSからassemblyからの見通しがかなり良くなったので、コツコツやってよかったと感じている。

あとは、この一年、仕事のBGMとしてYoutubeでかなりの量のクラシック音楽に触れて、「別に再生回数低くても良い演奏はたくさんあるし、僕自身それを良い演奏と判断できるようになってきたから、やっぱり見てる人はちゃんと見てるんちゃうの?」と感じるようになった。エンジニアも似たようなところはあると思う。twitterとかはてな界隈だとすごい人達いるし。一番大事なのは、地に足をつけるという自身の軸がぶれないことなんじゃないかなぁ。技術的にはいろんなものに触れるのは、軸がブレるという意味とはまた違うと思うので、来年も引き続き寄り道していきたい。

個別のやりたいことのトピックとしては、

とかかな?

結局これで良いのかはよくわからんけど、前見て進むしかないわな。


  1. 半年たって、報われているかどうかはまだよくわからないので、来年も引き続き。

cache 付きpipelined CPU実装した知見

github.com においた。

本記事の全体的な言い訳だが、2018/9月の末くらいからcomputer architectureの勉強始めたので、ところどころ言葉の使い方があやしい部分があるかもしれない(というかある)。そこは多めに見てくだせい👀

特徴

  • cache込みで5段pipeline実装(Fetch, Decode, Calculate, MemRead, RegiterWriteBack) (virtual memoryおよび、TLB(Translation Lookaside Buffer)は未実装1。)

  • VHDLで実装

  • architectureはmips(次節のreferenceの1番目を種本としている) risc-vにしなかったのは、そもそもその存在を知らなかったから( ^ω^ )

  • add, sub, and, or, slt, addi, lw, sw, beq, j, (andi, ori, slti, bne) あたりのinstructionでうまくいく(乗算、除算は未実装)

  • GHDL + GtkWaveを用いて、testcaseがすべて通ることを確認。 (実機ではまだ動作確認できてないので、これから確かめます😅)

reference


このブログはqiitaと違って、感想をかくための場所にしているので、どこらへんで困った😥 かと、よかったところ💪を書いていく。

Note) microarchitectureの基本から細かく説明しないので、もし本記事の前提知識を得たい方は、Digital Design Computer Architecture の5章辺りまでがわかりやすい。 mipsの仕様については、自分メモだが、https://qiita.com/knknkn1162/private/3f65ab4c5c30d3b9a5b3 においてる(著作権の関係でprivateです)

全体の構成図

https://twitter.com/knknkn26918/status/1069507872239702016 に汚いスケッチがある (j instruction はFetch Stageの1段で終わるようにしているので、メモが間違い) あるいは、datapath.vhdlを見る。

迷った所

Stateをどうするか?

最終的に、D FlipFlopのenable(または、syncronous reset)をON, OFFをcontrolするためのFSMを構成しさえすれば良いんだ、ということに着目して、正常系と異常系のStateに分離した。つまり、

-- pkg/state_pkg.vhdl
type flopen_statetype is (
    ResetS, LoadS, SuspendS, NormalS, ErrorS
);

みたいな感じにした。ResetS, LoadSはInitializationのときのモード。SuspendSはdata cacheおよび、instruction cacheのcache missが生じたときに突入するモード。controller/flopen_controller.vhdlにて、D-FlipFlopのenableおよび、syncronous reset(**_clr signalと定義されている)を管理、制御している。

以下、試行錯誤した部分:

Digital Design Computer Architecture 7章のmulti-cycle processorでは、FetchS, DecodeS, AddiCalcSなどのStateを定義してFSMを構成していく感じだったので、最初その方針でpipeline実装を行ったが、かなり苦しい実装となった。 pipeline化した場合、カエルの合唱の輪唱のように命令がn重に並列に走るので、上記の方針で行くと、stateの状態空間のn次元のものを管理する必要がある。これは、stallやforwardingの実装をする場合すごく大変だった。

(実は1度目その方針で、 https://github.com/knknkn1162/vhdl_sample/tree/pipeline-3/src/mips にてsandbox的に実装してみたが、controller部分(controller.vhdl)が本当にごちゃごちゃしてしまって残念な感じになってしまった。)

instructionごとにStageの段数が異なる場合の影響

Digital Design Computer Architectureとは異なり[^pipeline_n]、instructionごとにpipelineの段数を可変としている。例えば、ロード命令(lw)では、

  • Fetch -> Decode -> Calc(Addressの計算) -> Data-Cache Read -> Register WriteBack

の5段としている。一方、addiや、R-type instructionでは、

  • Fetch -> Decode -> Calc -> Register Writeback

の4段構成である。

こうすることの影響としては、何も考えずに組むとRegister WriteBackの部分のStageが衝突する。

例えば、

lw $s0, 8($0)
addi $t1, $s1, $0

の場合、なんの対策もしなかったら、

time(CLK) 1 2 3 4 5
lw Fetch Decode Calc Data-Cache Read Register WriteBack
addi Fetch Decode Calc Register Writeback

で5 CLK目に衝突する。あかん。ただし、衝突するのはここのstageのみなので、逐次的にRegisterに値をWriteBackするようにcontrolすれば良い。 結果的に、[component/regw_buffer.vhdl] のように逐次的にRegiterにデータを書き込むようにすることで解決した。(ただ、これはmips architectureに依存するかもしれない)

キャッシュの実装

最も基本的なキャッシュであるdirect mapped cacheを採用し、実装した。data cache, instruction cacheともに、 tag: 20bit, index: 7bit, cache lineを8line(23)として2実装してる(pkg/cache_pkg.vhdlがCONST値の定義場所、data cacheでは、ここらへんに実体を定義してる。instruction cacheでも似たような感じの実装) memoryはmem.vhdlと名が付いているが、L2 cacheかもしれない。

注意) virtual memoryやTLB(Translation Lookaside Buffer)は時間の都合上、実装してない。

コンピュータアーキテクチャ-電子情報通信レクチャーシリーズComputer Organization and Design MIPS Edition のCh5.3 The Basics of Caches を参考にした。 そんなにムズくないやろ、と思っていたら、以下のことを考慮に入れる必要があり、結構実装に時間がかかってしまった:


1: instruction cacheはRead onlyなのに対して、data cacheはRead/Writeなので、2つのキャッシュの実装が少し異なるのを考慮する必要がある。これはまぁ難しい部分ではなかったが、ちょっと頭が混乱する部分だったので、実装に時間がかかった。

--

2: cache missが起こった場合、cache(instr_cache.vhdl or data_cache.vhdl) とmemory(mem.vhdl)3 のやり取りをどのように実装するか?

やり取りの制御は、controller/mem_cache_controller.vhdl に一任した。

プロトコルは、コンピュータアーキテクチャ-電子情報通信レクチャーシリーズ の5.2.1を素直に採用した。つまり、

  1. addressにアクセス(Read or Write)したらcache_missが発生
  2. [古いキャッシュのデータをmemoryに移す(追い出し)]
  3. memory内の必要な部分をreadする
  4. 新しいデータをキャッシュに書き込む(再コピー)

というフロー。それぞれの段階で1 CLK消費するので、cache missが発生したら、最大4 CLK遅延する。ただし、instruction cache(Read only のcacheなので)や、data cacheの特殊な場合4は2番目が不要になるので、3CLK分の遅延のみですむ。


3: instruction cacheとdata cacheが同時にcache missを起こしてしまった場合どうするか?( pipeline化しているなので、十分に起こりうる)

これは実装している最中に気づいた。結果的に、controller/mem_idcache_controller.vhdl で制御を行なっている。

なんでこれが問題なのかというと、instruction cacheとdata cacheが同時にcache missを起こしてしまった場合、上記のプロトコルの2番目、3番目が競合するから。

これを解消するため、instruction cache missとdata cache missを controller/mem_idcache_controller.vhdl にて1 CLKずらした。ずらして、更にこの部分自体をpipeline化すれば、5 CLKの遅延ですむ。

D-flipflopを用いて適切に信号を遅延させる

-- datapath.vhdl を少し改変
  reg_pc0 : flopr_en_clr generic map (N=>32)
  port map (
    clk => clk, rst => rst, en => decode_en, clr => decode_clr,
    a => pc0,
    y => pc1
  );

  -- (skip)

  brplus0 <= immext0(29 downto 0) & "00"
  ja0 <= pc0(31 downto 28) & instr(25 downto 0) & "00";
  br4 <= std_logic_vector(unsigned(brplus0) + unsigned(pc1) + 4);
  pc4 <= std_logic_vector(unsigned(pc0) + 4);

  pc_br_mux2 : mux4 generic map (N=>32)
  port map (
    d00 => pc4,
    d01 => br4,
    d10 => ja0,
    d11 => pc4, -- dummy
    s => decode_pc_br_ja_s,
    y => pcnext0
  );

pcはprogram counterです。ここで問題にしたいのは、上記のコードでpc0pc1はなぜ使い分ける必要があるか? という所。 簡単に言うと、beq, bneの分岐命令は(Fetch Stageでなく)Decode Stageにてbranch takenされるかどうか決定されるから。なので、br4 <= std_logic_vector(unsigned(brplus0) + unsigned(pc0) + 4);とすると、

beq $0, $0, 1
addi $s0, $0, 5
addi $s1, $0, 6
addi $s2, $0, 7

を実行すると、本来addi $s1, $0, 6に飛ぶはずが、4番目のaddi $s2, $0, 7に飛んでしまうことになりだめ。

同様の理由で、ja0 <= pc0(31 downto 28) & instr(25 downto 0) & "00";のところを`ja0 <= pc1(31 downto 28) &....とするとj instructionの部分で失敗する。 ここは、バグ取りの際、原因を把握するのに結構時間のかかったところだった。(signal名の付け方がそもそもの問題なのかもしれないが..)

enable signal か syncronous reset(clear) signal か?

stall時は、calc_clr='1'とすることで、Calc Stageの入力を同期的にresetさっせる。 beqの条件がtrueになる場合も、decode_clr='1'とすることで、Decode Stageの入力を0にする。どちらの場合でもenable signalをOFFにすることで対応はできない。

f:id:knknkn11626:20181213162020j:plain
stall時の挙動
図の棒みたいな奴はD-flipflopのつもり。 もし、Aの部分のsyncronous resetをONする代わりにenableをOFFにすると、CLKの立ち上がり後にCalc Stageにlw $s0, 60($0)が残ってしまう(Data Cache stageにもlw $s0, 60($0)があるにも関わらず)なので、意図しない結果が起こる(実装次第なので、必ずしも予期せぬことが起こるわけではないが、バグの温床となる)

一方で、cache missによるCPUの一時停止の際は、clrで該当のステージの入力を0にresetしてしまうと、本来持っているデータが意図せず消えてなくなるから、ここはenable signalをOFFにすることで対応する。

要するに意図して保存されている値を消したい場合は、syncronous resetを使い、消したくない場合は、enable signalを使い、各ステージの入り口を止めれば良い。

よかったところ

  • controllerを役割別に分離した結果、わかりやすい実装ができた

cached_pipelined_mips/controller at v1.0 · knknkn1162/cached_pipelined_mips · GitHub のように複数のcomponentに分離したことで見通しがよくなった。datapathは一つのファイル(datapath.vhdl)にまとめた。1ファイルに集約することで、ファイルが大きくなる問題はあるが、datapathの全体像を把握しやすいので、実装観点からはあんまり不満はなかった。


  • registerのwritebackのbufferを用意したことで、実装がかなり楽になった

Registerの書き込みを逐次的に行うためにcomponent/regw_buffer.vhdl を用意した。利点はいくつかある:

1: regw_buffer.vhdlではあるregister addressが与えられた時に、buffer内を検索して値を返すように実装している。 これを行うことによって、どのステージ間でforwardingを実装する必要があるかどうかを意識することが不要になった。もし、forwardingを Digital Design Computer Architectureの通りに実装する場合、

  • Calc Stage->Decode Stageの方向にforwardingを実装
  • Data Cache R/W Stage -> Decode Stageの方向にforwardingを実装

の2箇所実装する必要がある。比べて、regw_buffer.vhdlを用意した場合は、このcomponentがregisterのwritebackを一元的に管理してくれるため、regw_buffer-> Decode Stageの1箇所ですむ( https://github.com/knknkn1162/cached_pipelined_mips/blob/v1.0/datapath.vhdl#L308-L309 ) 。

2: パイプラインの段数はlwやaddi, addで異なるように設計しているため、Resiger のwritebackの部分が2つのinstructionで競合してしまう可能性がある。 Registerの書き込みを逐次的に行うことによって、競合を回避することができた。(迷ったところの 「instructionごとにStageの段数が異なる場合の影響」 にも同じようなことを書いた) ただし、これはmips architectureに依存する実装かもしれない。


  • cacheをいい感じに実装できた

cache missが発生した時、数CLK遅延させることで、data cacheおよび、instruction cacheを更新するような実装ができた。箇条書きのStage名はcontroller/cache_controller.vhdl にちなんでいる:

  1. [NormalS] cacheをRead/Writeした時、cache missが起こることを想定する。この時cache_miss_en signalがONに出力される(これはcontroller/cache_controller.vhdlで制御している) cache_miss_en='1'をトリガーとして、[controller/mem_cache_controller.vhdl]のsuspendがONになり、各pipeline ステージの入り口のD-flipflopのenableをOFFおよびsyncrounous resetをONにする

1-0. (CLKの立ち上がり)

1-1. [Cache2MemS] 古いデータをmemory(L2 cache)に保存するためにmem_we='1'とする(これはcontroller/mem_cache_controller.vhdlで制御している)

2-0. (CLKの立ち上がり)

2-1. [Mem2CacheS] memoryからcacheにデータを移動する

3-0. (CLKの立ち上がり)

3-1. [CacheWriteBackS] cacheに書き込むためにcacheのsignalのload_en='1'とする。(これはcontroller/mem_cache_controller.vhdlで制御している)

  1. (CLKの立ち上がり)

4-2. [NormalS] cache hitする。[controller/mem_cache_controller.vhdl]のsuspendがOFFになり、各pipeline ステージのD-flipflopのenableをONにする。

  1. (CLKの立ち上がり)

5-1. 次のinstructionが走る...

見たいな風になった。controllerとdatapathの責務が分離されている状態で実装できているのではないかと思う。(制御がややこしいわりにはごちゃごちゃした実装にならずにすんだ)


  • circleCIでtest回すの自動化した。

これは、小さなことだけどやってみるとやっぱり楽。GHDL compiler + make commandでtestbench通るかどうかを1pushごとに確認している。

感想

  • 巷ではC compilerのフルスクラッチ実装が流行っている(自分は未経験なので、いつかやりたい)が、わかる人にしかわからない言語(VHDL)を用いてCPU実装するのは半分大変で半分楽しかった。大変というのはモチベーション維持の意味。楽しいというのは、なんかなんかよくわからないところからやるので、トンネルを自力で掘っている感があり、探検している感じがある。手を動かしながら、computer architectureを理解するという意味では、大変勉強になった。

  • testbench書く( https://github.com/knknkn1162/cached_pipelined_mips/tree/v1.0/tests )の結構骨折れる(というか、細かく書きすぎ??) デバッグはgtkwave使って波形みて根性で行なった。とはいいつつ、testbench書くのは答え合わせをする作業なので、そんなに苦ではなかった。ただ、効率はそんなによくない感じがあるので、どうしようか..

  • signal名の付け方はオレオレ流なので、これは偉い人の実装とかをコードリーディングするとかで身につけるしかないかな? -> https://scrapbox.io/craftmemo/Verilog_%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%AB%E3%83%BC%E3%83%AB が良いかもしれない

  • Makefileがひどいが、CPU実装できたので直す気があんまりない

  • 次は、Modern Processor Design: Fundamentals of Superscalar Processorsを読んでsuperscaler実装に取り組みたい。architectureは現在慣れているmipsにするかもしれないし、流行りのrisc-vに手を出すかもしれない。その辺は気分で決まりそうだが、risc-vの仕様書を眺めて見たかんじ、x86に比べて、え、そんなんでいいのっていうくらいにはかなりシンプルだし、mipsと結構似ているので、新しいことやるという意味では、risc-vでやってみるのが良いかもしれないですね。。


  1. パタヘネ本の 5.7 virtual memoryが詳しそうです。

  2. cacheの構成はパタハネ本のch.5.3のThe Intrinsity FastMATH Processorを参考にした。cache lineが16line(=24)でなく、8lineで小さめなのは、cache missの頻度をわざと上げたかったから。

  3. L2 cacheといったほうがよい?かもしれない

  4. cache dataの有効ビットがONでない場合(valid_flag='0')や全く「汚れていない」(dirty_flag='0')場合

FPGAでNeural Networkをフルスクラッチ実装している

まだまだ先は長いけれど。

誤差伝搬法のforward, backwardをVHDLで実装中で、forwardのところは、要素要素の部分についてはだいぶ形になってきて、あとは組み立てる作業をやっている。 ゼロから作るDeep Learning をそこそこ参考にしている。

データはMNISTの例の数字の画像のやつで機械学習させることを目標地点としている。

目下の悩みとしては、どのようなsequential logicにすればいいのか? MIPS architectureとかだと、教科書参考にしたこともあり、レジスタの配置についてはあまり考える部分ではなかったが、今回、入力データがそこそこ多いので、全部の入力データを一度にportで受ける訳にはいかない。そこで、clockで細かく切っていきつつ、sequentialに計算させる必要がありそうだ。

今の所、画像一枚ずづ読み取ってNNでforwardするのをclockの単位としているが、それだと、ユニットが大きすぎるかもしれない。

あとは、

  • 1d-array(array(natural range<>) of std_logic_vector(SIZE-1 downto 0)のこと)は、in portの型として許容されるのか

  • 重み行列をportで受けるとサイズが大きすぎで死にそうなので、memoryの読み書きで対応するべきところだよなぁ

とかいっぱい修正したい部分がある。

とりあえず、全くの白紙からそれっぽいのを作りつつあるので、まずは動くように持っていきたい。

MIPS のsingle cycle processorをVHDLで自力実装した

www.amazon.com を下敷きにした。上の本では実装例も載っているが、あんまり参考にしなかった。自分のものにしたという意味で自力。

https://github.com/knknkn1162/vhdl_sample/tree/single_cycle/src/mips でやった。全体設計するのが一番神経使った.. tensorflowの組み立てと近いかもしれない、と感じた。

https://github.com/knknkn1162/vhdl_sample/blob/single_cycle/src/mips/imem.vhdl#L25-L60 のinstructionについては動くようになっている。これで、processorの基本的な部分は把握できたことになる(と思いたい)

次はmulti cycle processorの実装に取り掛かろうかなぁ。