タダノキロク

日々の考えたことの記録 主に無駄なこと

詳細Linuxカーネル プロセス管理周りのシステムコール 7/3

詳細Linuxカーネル プロセス管理周りのシステムコール 7/3

今日は、プロセス管理のシステムコールforkを見ることにする。

https://kernelreading.doorkeeper.jp/events/44499

プロセス管理は詳解Linuxだと3章辺りなるので、そこを中心に見てみる。

そもプロセスってなんだ?

詳解Linux曰く、

プロセスをプログラムの実行している状態であるとします。
(中略)
カーネルから見ると、プロセスの目的はシステム資源(CPU時間やメモリなど)を割り当てて実体として動かすこと。

プルグラムが何らかの実行単位で処理を実行している状態がプロセス。 この際に必要なリソースは

  • 命令コード向けメモリ(テキスト)
  • プロセス固有データ領域向けメモリ(スタック/ヒープ)
  • プロセッサ状態(コンテキスト):CPUに設定されている情報(SP/PCなど)

辺り。

これらのリソースを各プロセスは所有している。 これに対して、カーネルがプロセスに物理資源(CPU/物理メモリ)をスケジュール管理して割り当てる。

プロセスが生成される時は、基本的にこれらのリソースは親とほぼ同じものを所有している。
ただし、同じものの所有時には、命令コード(テキスト)は共有するが、 それ意外のリソース(スタック/ヒープ)は複製を作成してプログラムを実行する。

このようなプロセスの単位で複数の処理を同時に実行しようとしても、プロセス間での簡単なデータ共有ができない。子プロセスを作る度に、スタック/ヒープといったメモリの複製を作成する必要があり、プロセス作成によるオーバヘッドがある。

なので、データは共有するけど、処理を分けたいという要望があった。そのなかでマルチスレッドの考え方がうまれた。データ領域の一部を共有して複数の処理を同時に実行する。これのような実行形態をマルチスレッドのアプリケーションと呼ぶ。

この考えに対応するためにLinuxでは軽量プロセスを提供している。軽量プロセスでは、幾つかのリソースを共有する。これにより、スレッドのアプリケーションも動作している。

プロセスってどうやって作成するか

カーネルはプロセス生成のためにforkexecの2つのシステムコールを準備している。

  • forkは現在のプロセスをコピーして新たなリソースを作成する。
  • execは自プロセスを別の実行プログラムを読み込み実行する。

今回はタイトルにも在るように、forkシステムコールを読んでいく。
読んでいるkernelは4.2.0

システムコールの呼び出し

毎度ながらLinuxソース上のシステムコールSYSCALL_DEFINEのマクロが使われている。
forkももちろん同様で下記のようにソースは記述されている。

#ifdef __ARCH_WANT_SYS_FORK
SYSCALL_DEFINE0(fork)
{ 
#ifdef CONFIG_MMU
  return _do_fork(SIGCHLD, 0, 0, NULL, NULL, 0);
#else
  /* can not support in nommu mode */
  return -EINVAL;
#endif
}
#endif

これを見ると実体は_do_forkになっており、 clone_flag = SIGCHLDを指定している。
_do_forkはその他のclonevforkシステムコールからも呼び出されるが、処理はclone_flagにて変わるっぽい。

こっから先はざっと目を通したのみ。(全然進んでいない・・・) とりあえず、forkcloneで違いが在る部分、言い換えれば、clone_flagにて処理が変わっている部分に着目してみる。
_do_forkの処理は下記の通リ

  1. copy_processでプロセスディスクリプタカーネルデータ構造の初期化を実施。
  2. get_task_pidで未使用のPIDを探して、子プロセスに新しいPIDを割り当てる

ってところで時間切れ。 とりあえず、なんとなくでもプロセスとスレッドの関係がわかって良かった。

詳細Linuxカーネル 15章 ページキャッシュ 6/12

詳細Linuxカーネル 15章 ページキャッシュ 6/12

前回と同じページキャッシュの章を読む。
今日は、ページ検索関数を見ることにする。

https://kernelreading.doorkeeper.jp/events/43901

15.1.3 ページキャッシュの操作関数

15.1.3.1 ページの検索

ページ検索はfind_get_page()関数で実施している。
アドレス空間構造体のポインタaddress_space *mappingとオフセット値pgoff_t offsetが引数で、返り値は見つけたアドレスか、見つからなければNULL
実体はfind_get_page() -> pagecache_get_page() pagecache_get_page()をcallするときには、fgp_flagsgfp_maskなる引数が追加されるがどっちも0で入力。この引数によっていろいろ処理をしているっぽいが、ここでは何も意味がなさげ。
結果、pagecache_get_page()のやってることは下記の部分のみ。

  page = find_get_entry(mapping, offset);
  if (radix_tree_exceptional_entry(page))
        page = NULL;
  return page;

このよくわからん引数による処理はどこで使うのだろうか?

find_get_entry

まずは、find_get_entryを見る。

rcu_read_lock()でロックをとる。(この間にページキャッシュを更新されないため? ->具体的にはradix_tree_replace_slotにてSlotが修正されないようにするため らしい。)
mapping->page_treeで指定されたRadix Treeにoffsetをキーにpageが在るか検索する。 検索はradix_tree_lookup_slot()をコール。

実体は__radix_tree_lookup()関数。
__radix_tree_lookup()ではまず、rcu_dereference_raw()なる処理をしているが、よくわからん。 ロックの状態の確認なのか?なんとなくデバッグ目的っぽい。

noderadix_tree_rootradix_tree_nodeのポインタで、 このポインタが指すアドレスの最下位bitのフラグを確認するのがradix_tree_is_indirect_ptr()。 名前からして、間接アクセスが必要かどうかをチェックしているっぽい。 (このポインタの最下位ビットを1にするのは何なのか?ページ機能とかと関連が在る?)
間接アクセスが必要であれば、indirect_to_ptr()nodeのポインタを変換する。 この時も、単に、ポインタの最下位ビットをマスクするだけ。

これで、nodeの正しいポインタになったぽい。
ほしいindex(offset)のページがnode内にあるかどうかを確認する。 nodeの持つツリーの深さhightから分かる最大index数と知りたいindexの数を比較。 最大を超えていればページは見つからないためNULLで帰る。

これ以降は、一段づつほしいidexに近づくようにSlotを探索していく。
ソースの中にコメントしてみた。

rcuのところと、最初のindirecr_to_ptr()がよくわかってない。

void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
        struct radix_tree_node **nodep, void ***slotp)
{
  struct radix_tree_node *node, *parent;
  unsigned int height, shift;
  void **slot;

  node = rcu_dereference_raw(root->rnode); //lockの確認とnodeのポインタに変換?
  if (node == NULL)
    return NULL;

  if (!radix_tree_is_indirect_ptr(node)) { //nodeポインタの最下位ビット=1 か判定(目的がわからない・・・)
    if (index > 0)
      return NULL;

    if (nodep)
      *nodep = NULL;
    if (slotp)
      *slotp = (void **)&root->rnode;
    return node;
  }
  node = indirect_to_ptr(node);  //ポインタを変換(最下位ビットをマスク)

    //こっからがnodeツリーに期待するindex(offset)のページがあるかを判定
  height = node->path & RADIX_TREE_HEIGHT_MASK;
  if (index > radix_tree_maxindex(height))
    return NULL;

    // indexから次の子ノードを探すためにシフトする数を求める
  shift = (height-1) * RADIX_TREE_MAP_SHIFT;

  do {
    parent = node;
    // treeの次の構造に行くためのSlot検索
        // indexの一部がSlotの番号になっているからそのポインタを取得
        slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK);
        // 次のノードのポインタ(slotそのもの)を取得
    node = rcu_dereference_raw(*slot);
    if (node == NULL)
      return NULL;

  // 一回目が終わったので、シフトするサイズを減らす。
    shift -= RADIX_TREE_MAP_SHIFT;
    height--;
  } while (height > 0);

  if (nodep)
    *nodep = parent;
  if (slotp)
    *slotp = slot;
  return node;
}

詳細Linuxカーネル 15章 ページキャッシュ 5/28

詳細Linuxカーネル 15章 ページキャッシュ 5/28

ページキャッシュの章を読む。
キャッシュは一般的にはディスクデータへのアクセスのキャッシュして RAM上に保存してシステム高速化するのが目的。

https://kernelreading.doorkeeper.jp/events/42463

15.1章 ページキャッシュとは

ページキャッシュはカーネルが使うディスクキャッシュで、 ディスクへの読み書きの際にページキャッシュを参照する。

read要求があった場合のざっくりの動作。

  1. 要求のあったデータ(ページ?)がキャッシュ上に在るか検索
  2. キャッシュ上にあればそのデータを返答
  3. キャッシュ上になければディスクから読み取りキャッシュにデータ格納。
  4. 格納したデータを返答

write要求があった場合のざっくりの動作

  1. 対応するデータ(ページ?)がキャッシュに在るか検索
  2. キャッシュ上になけれ新しいキャッシュ領域を確保
  3. キャッシュ上に書き込みデータを格納
  4. データ書き込みは適当なタイミングで実施

当たり前だがそれぞれの目的は・・・
readキャッシュの目的:同じディスク領域への複数のreadを1回のディスクアクセスにまとめる。
writeキャッシュの目的:同じディスク領域への複数のwriteを1回のディスクアクセスにまとめる。

これらの目的を満たすためには、 単なる2回のディスクアクセスより上記の手順による2回のデータアクセスが早く無いと損するはず。
そのために、以下の要件を満たしてページキャシュが実装されているらしい。
* データを含むページの迅速な検索。 (プロセスからデータアクセス時に指定してる形式はなんだっけ?忘れてる・・・)
* ページ内の内容を読み書きする手段の管理。(管理をつけた意味は?)

15.1.1 アドレス空間構造体

ページキャッシュのメインはアドレス空間(adress_space)構造体
この構造体はiノードオブジェト内に存在(inode->i_mapping)する
そのほかの構造体の関係はここがわかりやすい。

http://wiki.bit-hive.com/linuxkernelmemo/pg/PageCache

つまるところ、adress->page_treeから当該データのページディスクリプタのポインタを検索してページディスクリプタのフラグでページの状態を確認する。
adress->page_treeは基数ツリーのルートを表す。
基数ツリーの各ノードは、別のノードもしくはページのポインタを64(=26)個(配列slots)とノード内に存在するポインタ数を持つ。(その他にフラグなどある)
この基数ツリーのノードはルートからの位置indexで一意に指定している。
インデックスはファイルの先頭からのオフセットと同じ意味。
例えば、基数ツリーの深さが2つしか無いならばindex=131=64*2 + 3は ルートノードのSlot[2] -> 次のノードのSlot[3]でページディスクリプタのポインタに辿れる。

     struct radix_tree_node {
       unsigned int  path; /* Offset in parent & height from the bottom */
       unsigned int  count;
       union {
         struct {
           /* Used when ascending tree */
           struct radix_tree_node *parent;
           /* For tree user */
           void *private_data;
         };
         /* Used when freeing node */
         struct rcu_head rcu_head;
       };
      /* For tree user */
      struct list_head private_list;
      void __rcu  *slots[RADIX_TREE_MAP_SIZE];
      unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
    };

基数ツリーの最大インデックスは232-1まで。 4kB単位のページだと最大ファイルサイズは4G個 * 4kB =16TB
メモリが16TB以上とかの世界になったらどうなんだろうって思ったが、
ファイルサイズを最大16TBのことで、使えるキャッシュサイズが16TBでは無いのか。

この前提にページキャッシュの検索について見る。

この時点でざっくり性能を考えてみる。
まずは、アドレス空間構造体からページキャッシュにあるかどうかを判定するまで性能。
ファイルサイズが1GB〜64GBの範囲(階層3)と仮定する。
アドレス空間構造体からページノードにたどり着くまでに、 メモリアクセスが少なくとも4回必要(3つのノード+ページヘのポインタ参照)。
メモリが0.1μs、HDDドライブが100μs、SSDが・・・

ここからは少し考えてみる。

15.1.3 ページキャッシュの操作関数

15.1.3.1 ページの検索

ページ検索はfind_get_page()関数で * アドレス空間構造体のポインタとオフセット値を引数にする

次回は検索を見る。

詳細Linuxカーネル 11章 シグナル 5/15

詳細Linuxカーネル 11章 シグナル 5/15

カーネルのシグナル処理方法とプロセス間でシグナル交換するためのシステムコールを学ぶ。

https://kernelreading.doorkeeper.jp/events/42462

11.1章 シグナルの役割

シグナルはプロセスに送る短いメッセージのこと。 シグナルの利用目的は
* ある事象が発生したことをプロセスに通知。
* プロセスのコード無いにあるシグナルハンドラをシグナルを受けたプロセスに実行
の2つ。ただし、多くの場合は2つが同時に実行される。
(ある事象Aが起きたからある処理[1]を実施のような使われ方)

通常のシグナルはシグナル番号1-31を使用して、 リアルタイムシグナルは32-64を使用する。
2つの違いは同じ種類のシグナルの実行回数。
通常のシグナルは同じ種類のシグナルを2回以上プロセスが受けても、 1つだけ受信して処理を行う。
リアルタイムシグナルは待ち行列に並んで、順に実施される。

(通常のシグナルを受けた場合の動作は[終了/停止/ダンプ]といった、
2回以上実施に意味のないものだからか?)

シグナルの送信やシグナル受診時の動作を決めるためのシステムコールが準備されている。

シグナルの送受信は以下の2段階で実施。
1. シグナルの生成
送信元がシグナルの送信先(受信側)プロセスのデータ構造にシグナル情報を追加。
シグナル情報は保留中シグナルとして追加される(&signals->list)。
これは、シグナル送信時に送信先プロセスがCPU上で動作していない可能性があり、シグナル処理を遅延させるため。

  1. シグナルの配信

シグナル到着の感知は割込みハンドラや例外ハンドラの終了しユーザモードに復帰するたびに実施。
シグナル到着を感知したカーネルが、プロセスの実行状態の変更及び登録しているシグナルハンドラの実行をプロセスにさせる。

11.3章 シグナルの役割

シグナルの配信について具体的に見ることにする。
プロセスディスクリプタTIF_SIGPENDINGフラグの確認によって感知する。
ブロックしていない保留シグナルは、カーネルdo_signalでシグナル配信を行う。

static void do_signal(struct pt_regs *regs)
{
  struct ksignal ksig;

  if (get_signal(&ksig)) {
    /* Whee!Actually deliver the signal.  */
    handle_signal(&ksig, regs);
    return;
  }

get_signalの主な処理はシグナルキューにいるsignalの情報をdequeue_signal(実体は__dequeue_signal)でシグナルの情報siginfo_t ksig->infoを取ってくる。
シグナル情報にはシグナル番号/シグナルの発生元のコード(表11-8参照)のようなメンバがある。

signr = dequeue_signal(current, &current->blocked, &ksig->info);

取ってきたシグナル番号のハンドラ持ってくる。

  ka = &sighand->action[signr-1];

もってきたハンドラがデフォルトのハンドラでなければハンドラの情報をコピー。
これを繰り返して遅延しているハンドラをすべて取得。
最後に、ハンドラを追加する。

メモ

"致命的" = プロセスがシグナルハンドラによらずカーネルによって殺されること。
SIGKILLシグナルや、標準設定動作が終了でありながらプロセスが捕捉しない場合などが"致命的"となる。

詳細Linuxカーネル 19章 プロセッサ間通信 4/10

詳細Linuxカーネル 19章 プロセッサ間通信 4/10

kernelreading.doorkeeper.jp

ユーザモードプロセッサ間の同期及びデータ交換の方法を学ぶ。
簡単にやろうとすれば、ファイルシステムのロック機能を用いた同期、
共有ファイルによるデータ共有があるが、面倒。
なので、ファイルシステム無しでの同期/共有のシステムコールが用意されている。

  • パイプとFIFO
  • セマフォ
  • メッセージ
  • 共有メモリリージョン
  • ソケット

巨大なメモリ空間を共有するのに便利そうなIPC共有メモリ当たりを見てみることにする。 (19.3.5章)

19.3章 SystemVのIPC

IPCはプロセス間通信の略(InterProcess Communication)
プロセスから以下のことを行うための仕組み
* プロセス間の同期(セマフォを使用)
* メッセージ送受信
* メモリ領域を他のプロセスと共有

IPC資源は動的に作成されて、複数の資源を同時に使用可能になっている。
同時使用のために、カーネルはIPC識別子をプロセスが決めたIPCキーから作成。

19.3.5 IPC共有メモリ

複数のプロセスから共有データ構造にアクセスする方法。

とりあえず提供されているシステムコール

  1. shmget()
    IPC共有メモリ向けのIPC識別子を取得
  2. shmat()
    共有メモリリージョンをプロセルのアドレス空間に関連付ける
  3. shmdt()
    共有メモリリージョンをプロセスのアドレス空間の関連付から取り除く

共有メモリの割当管理に関して興味があるのでshmat()を見てみる。

shmat()の引数

システムコールなので、実体はdo_shmatっぽい。 引数は * shmid :IPC識別子
* shmaddr :共有メモリリージョンに割り当てたいアドレス
(通常はNULLで勝手にマップしてもらう。) * shmflag :IPC共有メモリ向けのモード設定

47 /* mode for attach */  
48 #define SHM_RDONLY  010000  /* read-only access */  
49 #define SHM_RND   020000  /* round attach address to SHMLBA boundary */  
50 #define SHM_REMAP 040000  /* take-over region on attach */  
51 #define SHM_EXEC  0100000 /* execution access */  

shmat()の処理

  1. 引数の確認
    shmidが正でなければエラー
    shmaddrにあればページサイズにマスク
    shmflagに合わせてページの属性設定
  2. ips_ns を取得
  3. shm_obtain_object_check

なんでもいいからここまで。

詳細Linuxカーネル 14章 ブロック型デバイスドライバ 3/12

詳細Linuxカーネル 14章 ブロック型デバイスドライバ 3/12

@詳解Linuxカーネル読書会

ブロックデバイスへのI/Oドライバは、 平均アクセス時間が非常に長いことを前提に作られている。
(大体msオーダー/CPUメモリはnsオーダー)

この特徴が入っているソースの部分を読んで行こうと思う。

ブロック型デバイスの管理

とりあえず全体のアーキテクチャ。(14.1章を参照)

LinuxでのブロックデバイスへのReadアクセスは以下のレイアを踏む(図14−1)

  1. VFS
    情報(ファイルディスクリプタとファイルの位置)からRAM上に
  2. マッピングレイヤ
    ファイルデータの物理的な位置を特定
  3. 汎用ブロック層
    読み込み操作発行(ブロックI/O)する。デバイス毎の特性は隠蔽
  4. I/Oスケジューラ層
    I/Oデータの転送要求の並べ替えを行う。
  5. ブロック型デバイスドライバ
    ハードのディスクコントローラにて適切なコマンドを転送し、データ転送。

この後、データサイズに関して書いてある。 * セクタ(ブロックデバイスの物理サイズ)
* ブロック(ファイル・システムが管理する最小単位)
* セグメント(アクセスを連続で行うために物理的な隣接ブロックのまとまり)
* ページ(RAM上にキャッシュするサイズ)

ブロックデバイスを性能を気にしていそうなのは、I/Oスケジューラ層な感じ。 14.3章I/Oスケジューラを読むことにする。

I/Oスケジューラ

14.3参照

ブロックデバイスへのアクセスを可能限り複数のセクタをまとめて取り扱う。 その結果、ドライブデバイスのヘッド移動回数を減らす。 セクタ単位のI/O処理はブロック型デバイス要求を生成で実施。 カーネルは要求をI/O操作のスケジュールに追加して処理は遅延させる。 そしてスケジュールを連続するセクタへのアクセスに並び替えを行う。

!!この辺は当たり前かな・・・

具体的な実現方法は、汎用ブロック層がI/Oスケジューラを呼び出し、 新しいブロック型要求を新たに生成するか、 すでにある要求を拡張して(連続していたら要求をひっくるめる)新たには要求を生成しない。
要求は物理ブロックデバイス毎に1つの要求キューを持っていいて、
* 要求キューディスクリプタ(14.3.1章)
* 要求ディスクリプタ(14.3.2章)
で管理する。
ディスクリプタ(bio構造体から構成)がそれぞれの要求を示す。 I/Oスケジューラが要求に対して既存のbioに追加 or 別のbio構造体と結合して、 要求を拡張する。 要求キューはそれらのデイスクリプタの並べかえを行うために使う。

I/Oスケジューリングアルゴリズム(14.3.4章)

新しい要求をキューに追加するときは、 I/Oスケジューラが幾つかのアルゴリズムに基づき追加する。

基本的には"エレベータ"で実施。セクタ番号順に並び替えるようにする。 Linux2.6では単なるエレベータではなく、4種類がアルゴリズムとして提供
* 予測(Anticipatory)
* 期限付き(Deadline)
* 完全公平型(Complete Fairness Queueing)
* 無処理(No Operation)

Linux2.6では予測エレベータが最も洗練されていると行ってたが、 wikiを見ると完全公平型(CFQ)がデフォルト見たい。 ただ、ブロックデバイスにHDDよりSSDが採用されている2016年、 これらのアルゴリズムは邪魔なのかもしれない。

このアルゴリズムの詳細を追うのもいいが、 一旦要求を拡張するところ当たりを見てみたい。

I/Oスケジューラに対する要求の発行(14.3.5章)

I/Oスケジューラへの要求は関数__make_queueで実装。
引数は
* 要求キュー(request_queue)ディスクリプタq
* bioディスクリプタbio
現在のカーネルだとraid10.cにしか__make_queueが定義されてない。 多分違う関数になっているのでは?->そうみたい。

qのメンバで関数ポインタmake_request_fnに入れられているのは、
* blk_mq_make_request
* blk_sq_make_request
* blk_queue_bio
* brd_make_request
* drbd_make_request
* pkt_make_request
* cached_dev_make_request
* flash_dev_make_request
* dm_make_request
* pmem_make_request
他いろいろある。ブロックデバイス向けはblk_mq_make_requestかな。
探し方はデバイスドライバの初期化で、blk_queue_make_requestに格納されている関数ポインタかな。

もし続けるならblk_mq_make_requestからかな。 =>ちがうらしい。blk_queue_bioが実体らしい。 以上ここまで。

5章同期処理#2 20160207Linux Kernel 勉強会 #18

詳細Linuxカーネル 5章 同期処理を読む(続き)

前回力尽きた、カーネルが使用している同期技法のスピンロックを読む。

スピンロックの確保 spin_lock()

スピンロックを確保するための関数 spin_lock()は、
spinlock_t構造体のアドレスを引数にとる。

Spin_lock()raw_spin_lock()->_raw_spin_lock()ー>__raw_spin_lock()-の順にコール/マクロ化され、実体は__raw_spin_lockになる。

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
  preempt_disable();
  spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
  LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}
  1. preempt_disable()をコール
      カーネル内のプリエンプションを禁止(5.1章に書いているから後で読む)

  2. spin_acuore()をコール
      デバック用の関数っぽい。あとでみる

  3. LOCK_CONTENDEDのマクロを実行

    1. 第二引数(try)の do_raw_spin_trylockに第一引数(_lock)のraw_spinlock_t *lockでスピンロックが取れているか確認。
      実体はarch_spin_trylock。ここでなにかしてるっぽい。
      ここから新規
      よくわからんがticketの概念が在るらしい。共用体とか使ってて分かりづらい。
      一旦、TICKET_SLOWPATH_FLAGは無視する。
      以下 arch_spin_trylockの動作。 現在のlockoldに確保。 oldの先頭headと末尾tailを比較する。
    2. 一致(XORで0になれば)で0をリターン。
    3. 一致でなければ現在のlock.head_tailの最上位ビットを1にする。
      すでに確保したoldと今lockを比較して一致すればnewlockに書き込む。
      (cmpxchgを使用する)
      リターンはold==lockならばoldを、old!=lockならばnewを返す。
    4. lockheadtailが一致していたからlock取得?の場合。
    5. lock_contendedを実行
      いろいろやってるが、__lock_contendedが実体かな?
      なんだかlockdep.cのロック処理チェッカーの関数なので飛ばす。

    6. 第三引数(lock)のdo_raw_spin_lockに第一引数(_lock)で実行。
      (spinlock.hにある。関数の引数の間に__aquires(lock)がついてる関数)
      実体はarch_spin_lockにある。

      1. lock->ticketstailに最下位ビットだけ立てたincxadd
        incには元のlock->ticketsが入っている
        (xaddはデータを交換してから加算)
      2. incheadtailを比較して一致すれば抜ける。
      3. 一致していない場合は、
        • inc.headに最新のlock->tickets.headをリード。
          • inc.tail(元々)とinc.head(最新)を比較(__tickets_equal)。
          • 一致するまでSPIN_THRESHOLD回繰り返す。
          • 一致したら(goto clear_slowpath)で後処理をするらしい。
            ここまでで時間切れ!

疑問点。 * どこでぐるぐるスピンロックを待っているのか。
* tryでロックが取れないと終わっているように見える。

#define LOCK_CONTENDED(_lock, try, lock)      \
do {                \
  if (!try(_lock)) {          \
    lock_contended(&(_lock)->dep_map, _RET_IP_);  \
    lock(_lock);          \
  }             \
  lock_acquired(&(_lock)->dep_map, _RET_IP_);     \ 
} while (0)
static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
{
  arch_spinlock_t old, new;

  old.tickets = READ_ONCE(lock->tickets);  //現在のlockからticketsを確認
  if (!__tickets_equal(old.tickets.head, old.tickets.tail)) // 
    return 0;

  new.head_tail = old.head_tail + (TICKET_LOCK_INC << TICKET_SHIFT);
  new.head_tail &= ~TICKET_SLOWPATH_FLAG;

  /* cmpxchg is a full barrier, so nothing can move before it */
  return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head    _tail;
}
static __always_inline void arch_spin_lock(arch_spinlock_t *lock)
{
  register struct __raw_tickets inc = { .tail = TICKET_LOCK_INC };

  inc = xadd(&lock->tickets, inc);
  if (likely(inc.head == inc.tail))
    goto out;
      
  for (;;) {
    unsigned count = SPIN_THRESHOLD;
    
    do {
      inc.head = READ_ONCE(lock->tickets.head);
      if (__tickets_equal(inc.head, inc.tail))
        goto clear_slowpath;
      cpu_relax();
    } while (--count);
    __ticket_lock_spinning(lock, inc.tail);
  }
clear_slowpath:
  __ticket_check_and_clear_slowpath(lock, inc.head);
out:
  barrier();  /* make sure nothing creeps before the lock is taken */
}