xv6-rev6 読み (7)
umalloc.c に記載されている一連の手続きについて。
昨日エントリにて malloc 手続きのメインループに関するナニのフォローから。
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){
// 中略
}
if(p == freep)
if((p = morecore(nunits)) == 0)
return 0;
}base から始まるリストは循環、というあたりの確認から。umalloc.c ローカルで private な静的変数が二つ定義されてます。
static Header base; static Header *freep;
Header 型の定義については直前エントリ確認して頂ければと。で、これらは起動時に 0 で初期化されます。umalloc.c に定義されている手続き群のうち、いっちゃん最初に動くと思われるのは malloc 手続きのはずなのでこちらをエントリポイントと見ると直前エントリで確認した以下の条件分岐の中身が実行されるはずです。
if((prevp = freep) == 0){
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}上述の通り、freep はゼロ値ですね。これで
- freep は base の先頭アドレスを指す
- base.s.ptr も base の先頭アドレスを指す
という最初のループ状態が生成されます。このままメインループに突入してみます。
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){prevp は base のアドレスを指しているので p には base のアドレス (base.s.ptr) が格納されます。で、base.s.size の値は 0 なので条件式の評価は偽ですな。条件分岐の中身はスルーで以下の式の評価に移ります。
if(p == freep)
if((p = morecore(nunits)) == 0)
return 0;freep と p の値は base のアドレスなので条件分岐の中身が評価され、morecore 手続きが呼び出されます。morecore の中では
- 領域の確保
- 確保した領域の先頭を Header な領域として値を設定
- 確保した領域を free して freep を戻す
ということをしてます。手続き定義は以下。
static Header*
morecore(uint nu)
{
char *p;
Header *hp;
if(nu < 4096)
nu = 4096;
p = sbrk(nu * sizeof(Header));
if(p == (char*)-1)
return 0;
hp = (Header*)p;
hp->s.size = nu;
free((void*)(hp + 1));
return freep;
}これも private メソドですね。手続きの中で触っていない freep を戻すということは freep は free 手続きの中で操作されるのか。ちなみに morecore の戻り値は p に代入されて for 文の記述が以下なので
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){p にはリストに追加された直前要素になっていないといけないんですね。てか freep がそうなっていないといけないのか。
とりあえず
free の中身を云々なんですが、直前エントリにも書いた free の処理概要の
-
- bp の直前要素を p で指す
ということを以下な部分で云々してるはずなんですが
bp = (Header*)ap - 1;
for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break;最初って freep は base を指してて要素はこれだけでループしてるはず。base はデータセグメントにあるはずなので bp よりは小さい (bp は sbrk で後から追加されたものなのでデータセグメントよりもアドレス的に後ろであると類推)はず。
ということで if の条件式は真判定されるはずで break するのか。p は base のアドレスが格納されたまま、ということになりますね。
ちなみによく分かっていないのは二度目の morecore 呼び出しで確保された領域は、どこに挿入されるのだろうか、ということだったりしてます。でもこれって freep がどこを指してるか次第なのかどうなのか。
元に戻って、その後は連続してればマージする処理ですね。
- bp + bp->s.size と p->s.ptr は同値ではないので bp->s.ptr に p->s.ptr が代入される
- bp->s.ptr は base のアドレスが格納される
- p + p->s.size と bp は同値ではないので p->s.ptr に bp が格納される
最後に freep に p が格納されてますが freep は base のアドレスであることは変わりないですね。また、リストとして
- base の s.ptr には今確保した領域のアドレスが格納されている
- 今確保した領域の Header の s.ptr 属性には base のアドレスが格納されている
という状態になりますね。
これで呼び出し元の malloc 手続きに戻っても p には freep (base のアドレスが格納) が代入されて、無事に処理が進むことになる訳ですか。
もう少し
p を bp の直前とする、という以下なナニですが
for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break;単純に base はデータセグメントで、sbrk で追加される領域は順に後ろに確保される、って前提にするとイメージしやすいですね。
- p >= p->s.ptr という条件式は p が base に戻る要素を指している、という意味になるので、p が末端要素の場合、という理解で良いはず
- (bp > p && bp < p->s.ptr) という条件式は要素間に挟まれた領域を解放するケイス、と見て良いはず
って考えるに、if 文の条件式は若干冗長なのかどうなのか。
