Cyber Bird

9日目できましたー。本当は2週間ほど前にできていたんですが…。

今回は、マウスが動くようになったという事で、メモリ管理に進んでいます。

今回のソースコードはこちら。

では続きからどうぞ。

今回は、前半で「メモリ容量のチェック」、後半で「メモリの確保と解放」を行っています。
前半の内容に関しては非常にハードウェア臭い内容で、僕が改めて説明しても
ただの二番煎じにしかならないので割愛します＾＾；

後半のメモリの確保と解放については、自作本中の説明がコメント頼りになっている
部分があり、もしかするとわかりづらい方もいらっしゃるのではと思うので、
そこは説明を加えたいと思います。
メモリ管理の大まかなアルゴリズムは、自作本の通りですので割愛しますね。

僕が解説を加えるのは、最後に登場するmemman_alloc関数とmemman_free関数です。
（あまり命名の仕方が好みではない(!?)ので、僕のソースではmemmanのmanを省略しています

では、その部分だけ抜粋します。


・mem_alloc関数

// メモリ確保
dword mem_alloc(MEMORY_MANAGE *man, dword size) {
	dword i, a;
	for(i= 0; i < man->frees; i++) {
		// 十分な広さの空きを発見した場合
		if(man->free[i].size >= size) {
			a = man->free[i].address;
			man->free[i].address += size;
			man->free[i].size -= size;
			// free[i]がなくなったので前に詰める
			if(man->free[i].size == 0) {
				man->frees--;
				for(; i < man->frees; i++) man->free[i] = man->free[i+1];
			}
			return a;
		}
	}
	return 0;	// 空きがない
}

自作本から型名等を変えています。ただの好みですｗ
MEMORY_MANAGEはMEMMANです。
dwordはtypes.hで定義されているのですが、unsigned intの略記です。
過去にも登場していますが、unsigned系の型をtypes.hでtypedefしています。

unsigned char  -> byte
unsigned short -> word
unsigned int   -> dword

では、中身に入ります。

この関数がやっていることは、管理している空きメモリから、必要としているサイズのメモリを
確保して、先頭アドレスを返すことです。

forループでMEMORY_MANAGE中のFREEINFOを走査し、確保したいサイズより
大きい空きメモリ情報があれば(58行目)、その空きメモリの先頭アドレスを返し(59&67行目)、
空きメモリを先頭から必要な分だけ確保します(60～61行目)。



もし、確保したいサイズが空きメモリ情報のサイズと一致していたら、
この空きメモリ情報はサイズが0になり不要になるので、捨てます。

それをやっているのが、63～66行目です。
空きメモリ情報の個数を1つ減らして、これより後の情報をすべて1つ前に移動させてつめます。

最初は「配列の中身を一つ一つコピーするの？リストの方が向いてるでしょ…」って思ったんですが、
よく考えると、そもそも今作っているのはmalloc関数なので、リスト自体作れないんですよね。
なんという自己矛盾。

このifの中身はこの後も度々登場するので、一つの関数にした方がいいと思うんですが…


・mem_free関数

// メモリ解放
int mem_free(MEMORY_MANAGE *man, dword address, dword size) {
	int i, j;

	// 解放するメモリをどこに入れるか決める
	for(i = 0; i < man->frees; i++) {
		if(man->free[i].address > address) break;
	}

	// 前があるとき
	if(i > 0) {
		// 前の領域にまとめられるとき
		if(man->free[i-1].address + man->free[i-1].size == address) {
			man->free[i-1].size += size;
			// 後ろもあるとき
			if(i < man->frees) {
				// 後ろの領域もまとめられるとき
				if(address += size == man->free[i].address) {
					man->free[i-1].size += man->free[i].size;

					// man->free[i]がなくなったので削除
					man->frees--;
					for(; i < man->frees; i++)
						man->free[i] = man->free[i+1];
				}
			}
			return 0;
		}
	}

	// 前にはまとめられなかったとき
	if(i < man->frees) {
		// 後ろがあるとき
		if(address += size == man->free[i].address) {
			man->free[i].address = address;
			man->free[i].size += size;
			return 0;
		}
	}

	// 前とも後ろともまとめられないとき
	if(man->frees < MEMMAN_FREES) {
		// free[j]よりも後ろを、後ろへずらして、隙間を作る
		for(j = man->frees; j > i; j--) 
			man->free[j] = man->free[j-1];
		man->frees++;
		if(man->maxfrees < man->frees) {
			man->maxfrees = man->frees;
		}
		man->free[i].address = address;
		man->free[i].size = size;
		return 0;
	}

	// 記憶領域を越えているとき
	man->losts++;
	man->lostsize += size;
	return -1;	// 失敗
}

此方の関数は、自作本中ではコメントだけでテキストによる説明がなく、少々イメージし辛い
気もするので、図を交えながらまとめます。

この関数は随分と長いですが、やっていることはaddress番地からsizeだけメモリを開放して
空きメモリ情報に加えることです。
具体的には下のようになっています。

int mem_free(MEMORY_MANAGE *man, dword address, dword size) {
	for(i = 0; i < man->frees; i++) {
		// 解放するメモリをどこに入れるか決める(77～80)
	}

	// 前があるとき(82～101)
	if(i > 0) {
		// 前後とうまくまとめる
	}

	// 前にはないとき(103～111)
	if(i < man->frees) {
		// 後ろとうまくまとめる
	}

	// 前とも後ろともまとめられないとき(113～125)
	if(man->frees < MEMMAN_FREES) {
		// 新しい情報を追加する
	}

	// それでも駄目だったら
	// 大人しく諦めて捨てる
}

だいたいこんな感じです。


はじめに、今解放するメモリを追加する「空きメモリ情報のインデックス」を決めます。
空きメモリ情報はFREEINFO構造体の配列になっていますが、この配列では保持している
空きメモリのアドレスが若い順に並ぶようにします。

実際に若い順に並べるのは116～123行目の辺りですが、ここでは若い順に並んでいるのを
乱さないように、空きメモリを戻す場所を決めます。


次に、空きメモリを戻す場所を決めた後、今から空きメモリを返すFREEINFO構造体より前に
別のFREEINFO構造体があるか、を調べます。
要するに、今から空きメモリを返すのがfree[0]でないかどうか、ということです。

i != 0ならば、前後の情報とまとめられる可能性があります。
もし、今から戻す空きメモリの先頭アドレスがひとつ前の空きメモリ情報の最後のアドレスと
等しいなら、ひとつ前の空きメモリ情報にまとめられます。


うしろの空きメモリ情報と境界が一致しているときも同様ですね。


さて、次は空き情報の前がなかったとき、つまりi = 0のときです。
これは先ほどとやっていることはほとんど同じです。
ただ、前に空き情報がないので、前の空き情報とまとめることが絶対にできないだけです。
後ろの空き情報とまとめられないかだけ調べます。


この後は、空き情報がまだまとめられていないときです。
今から戻す空きメモリが前とも後ろともまとめられないとき、新しく空き情報を追加します。

そして、新しく空き情報が追加できない（配列の最大値）のときは、諦めて
空きメモリを捨てます。この仕組みのままだと、永遠にこのメモリは使われません。

---

やはり説明がうまくできなかった気がします…。
ソースコードをよく読めば(ry

今回は、普段OSから提供されているだけのmallocやfreeの仕組みに触れることが
できて、良かったと思います。
OS開発の勉強の醍醐味は、このようにブラックボックスの中身を覗くことではないかと思っています。