xv6-rev6 読み (6)

kernel

umalloc.c を云々。若干 umalloc.c の中身の理解が微妙。全体を俯瞰しつつ中身を掘ってみました。

基本的な領域の管理

Lions' 本では_リソースマップ_というものを使って空き領域の管理をしているという解説が載ってます。リソースマップは基本的に配列な表現になってますが、x86 だともう少し事情が複雑な模様。
ただ、xv6 でもサイズとアドレスという属性を持っているあたりは v6 を踏襲しているようです。ただ、基本的な考えかたとして

typedef long Align;

union header {
  struct {
    union header *ptr;
    uint size;
  } s;
  Align x;
};

typedef union header Header;

な Header 型を領域の先頭に保持している一塊の領域、という形で管理している模様。また、基本的に sizeof(Header) を基本的な単位として領域の払出しをしている模様です。
malloc の以下のコードも要求された領域の大きさが格納できる sizeof(Header) の倍数の領域に加えて Header 用の領域を確保するためのものな模様。

  nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;

で、s.size 属性が nunits より大きい場合の処理の記述が以下です。

      if(p->s.size == nunits)
        prevp->s.ptr = p->s.ptr;
      else {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }

あ、p は現在処理対象になっている要素を指してるポインタで、prevp がその要素の直前の要素を指すポインタです。s.size 属性と nunits が同値であった場合にはポインタを繋ぎかえて p を戻せば良いわけです (本当は p+1 を戻すのですが)。
また、s.size 属性の値が nunits より大きい場合は末端部分から切り取られているのが分かります。こんな強烈なコード見たのは久しぶり。
中身を掘削してて分かったんですが、freep というポインタは基本的に処理対象となった要素の直前要素を指すポインタで更新される模様です。そういった意味では malloc 手続き先頭部分な以下の記述は最初の一発目のみ、ということになるはず。

  if((prevp = freep) == 0){
    base.s.ptr = freep = prevp = &base;
    base.s.size = 0;
  }

最初の状態としては

  • freep および prevp および base.s.ptr は base のアドレスを値として持つ
  • base.s.size の値は 0

となってますが、最初の morecore 手続き呼び出しで base.s.ptr の値は変わるはず。malloc 手続きのメインループはざっくり以下なんですが、

  for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){

    // 中略

    if(p == freep)
      if((p = morecore(nunits)) == 0)
        return 0;
  }

for で終了条件は無いんですが、ループ末端にある条件分岐 p == freep が一周した、という意味になります (詳細別途)。

時間が無いので

ポイントというかメモを以下に列挙しておきます。詳細別途ということにて。

  • base から始まるリストは循環している
    • 末端要素は base を指している
  • free の処理概要
    • bp の直前要素を p で指す
    • bp の後ろの要素について
      • 連続しているのであれば結合
      • そうでなければ bp->s.ptr に p->s.ptr を代入 (挿入なので
    • bp の前の要素について
      • 連続しているのであれば結合
      • そうでなければ p->s.ptr が bp を指す形に修正 (挿入なので
  • freep は処理対象な要素の直前要素で更新される
    • freep が動いてもリストはループしているので問題無い
    • 更新された近辺にカーソルを置いておくことに付随する効果がある?

とりあえず

別件な TODO がいくつかあるのでそちら対応をしつつ、umalloc.c の中身についてはきっちり掘削可能な状態になってるのかどうなのか。
あ、新規に morecore した場合、確保した領域がどこに挿入されるのか、は確認が必要なのでした。