読者です 読者をやめる 読者になる 読者になる

タダノキロク

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

詳細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;
}