gitのソースコードを読む２: freeは不要？

昨日の続き。 *1 今日が本題。

C言語で構造体を領域をどのように確保するのがいいのかを調べるのが目標。
コミット 7fa6b4e を主に読む。

全てのデータの基本となる構造体 struct object

struct object {
	unsigned parsed : 1;
	unsigned used : 1;
	unsigned int flags;
	unsigned char sha1[20];
	const char *type;
	struct object_list *refs;
};

parsedやusedフラグにはビットフィールドが付いている。初めて見た。C言語でbool値はこうやって格納するのね…。
他は、sha1のサイズが20バイトと決まっているので長さを書いている。
typeはcommitやtreeなどが入る変数なので長さの上限が決まっているのだが、ここではポインタになっている。
refsは使われていない。

typeは各ソースで

const char *commit_type = "commit";

などと定義されており、それを代入するようだ。なるほど。const なので共有して使っても安全。

コミットデータを格納する構造体

struct commit {
	struct object object;
	unsigned long date;
	struct commit_list *parents;
	struct tree *tree;
};

大体は見たまま。第一メンバにポインタではない struct object がある。これが重要。

コミットを探す lookup_commit 関数

struct commit *lookup_commit(unsigned char *sha1)
{
	struct object *obj = lookup_object(sha1);
	if (!obj) {
		struct commit *ret = malloc(sizeof(struct commit));
		memset(ret, 0, sizeof(struct commit));
		created_object(sha1, &ret->object);
		return ret;
	}
	if (obj->parsed && obj->type != commit_type) {
		error("Object %s is a %s, not a commit", 
		      sha1_to_hex(sha1), obj->type);
		return NULL;
	}
	return (struct commit *) obj;
}

lookup_commit関数でオブジェクトが見つかったら、それを struct commit にキャストして返している。
struct commit の第一メンバが struct object なので、両者は同じアドレスを指す。これで継承のようなことができる。

見つからなかった場合は malloc でメモリを確保して初期化し、create_objectを呼び出している。

struct object **objs;
int nr_objs;
static int obj_allocs;

static int find_object(unsigned char *sha1)
{
	int first = 0, last = nr_objs;
        while (first < last) {
                int next = (first + last) / 2;
                struct object *obj = objs[next];
                int cmp;

                cmp = memcmp(sha1, obj->sha1, 20);
                if (!cmp)
                        return next;
                if (cmp < 0) {
                        last = next;
                        continue;
                }
                first = next+1;
        }
        return -first-1;
}

void created_object(unsigned char *sha1, struct object *obj)
{
	int pos = find_object(sha1);

	obj->parsed = 0;
	memcpy(obj->sha1, sha1, 20);
	obj->type = NULL;
	obj->refs = NULL;
	obj->used = 0;

	if (pos >= 0)
		die("Inserting %s twice\n", sha1_to_hex(sha1));
	pos = -pos-1;

	if (obj_allocs == nr_objs) {
		obj_allocs = alloc_nr(obj_allocs);
		objs = realloc(objs, obj_allocs * sizeof(struct object *));
	}

	/* Insert it into the right place */
	memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * 
		sizeof(struct object *));

	objs[pos] = obj;
	nr_objs++;
}

いきなり難解になった。たぶんmemcmpとmemmoveでメモリ上の二分探索をやっている(自信なし)。最新版のソースではハッシュに変わっているので探索アルゴリズムについては置いておく。
二分探索やハッシュの実装を、この文章を書くくらいにさらっと書けるようになりたいものだが。
objsグローバル変数にobjectを詰め込んでいるが、malloc(sizeof(struct commit));で取得した struct commit のアドレスでもある。一瞬 object より commit の方がサイズが大きいのだから重なってしまうような気がしたが当然そんなわけはない。配列にデータを代入していっているのではなくポインタを並べているので。

alloc_nrは

#define alloc_nr(x) (((x)+16)*3/2)

となっていて、初期値 16 からメモリを1.5倍ずつ増やしているようだ。メモリの増やし方については
http://ymotongpoo.hatenablog.com/entry/20110515/1305420256
この辺参考。
このブログに

危険なコード

次のコードが色々と危険をはらんでいるのでキチンと対応する必要があると教わった。
buffer = realloc(buffer, old_size * 2);

と書いてあるが、create_object関数にはもろに

		objs = realloc(objs, obj_allocs * sizeof(struct object *));

と書かれている。全体的にメモリ確保関係のチェックが無い。というかfreeも無い。
ちょっと検索すると、malloc/free論争というのがあることを知った。mallocとfreeはセットじゃなくて良いんだね。

valgrindで調べると

zsh % valgrind --tool=memcheck --leak-check=full --show-reachable=no ./rev-tree $(cat .git/HEAD)
...
==11826== LEAK SUMMARY:
==11826==    definitely lost: 0 bytes in 0 blocks
==11826==    indirectly lost: 0 bytes in 0 blocks
==11826==      possibly lost: 0 bytes in 0 blocks
==11826==    still reachable: 584 bytes in 10 blocks
==11826==         suppressed: 0 bytes in 0 blocks
...

このようになった。

still reachable

おそらく問題無し. 開放すべきメモリを開放していない部分はあるが, これはごく一般的で利にかなっている. この警告を表示したくない場合 --show-reachable=yes のオプションはつけないこと.

https://gist.github.com/mooz/402878

どういうことかと言うと、

#include <stdio.h>
#include <stdlib.h>


static char *alloc(int size)
{
    char *p = malloc(size);
    return p;
}

int main(void)
{
    alloc(1024);
    return 0;
}

これはリークしている。というかlostしている。いざ開放しようと思ったときに開放できない。

#include <stdio.h>
#include <stdlib.h>

static char *buf;

static char *alloc(int size)
{
    return buf = malloc(size);
}

int main(void)
{
    alloc(1024);
    return 0;
}

これはlostしていない。freeは無いが、いつでもbufを開放できる。という理解であってる？

object.c に合わせると

#include <stdio.h>
#include <stdlib.h>

static char **buf;
static int nr;

static char *alloc(int size)
{
    char *p = malloc(size);
    buf = realloc(buf, (nr + 1) * sizeof(char *));
    buf[nr] = p;
    return buf[nr++];
}

int main(void)
{
    alloc(1024);
    return 0;
}

こんな感じになる？

プログラム起動から終了までの間でずっと使うデータなんだからグローバルに確保して保持しておきましょう、という話なのかな。
開発段階だからfreeがしてなくて、今はあるのかと思って調べてみた。

zsh % valgrind --tool=memcheck --leak-check=full --show-reachable=no git ls-tree 8ab1c16619f28975406a9928b3661232643db7cd
...
==17767== HEAP SUMMARY:
==17767==     in use at exit: 41,687 bytes in 12 blocks
==17767==   total heap usage: 66 allocs, 54 frees, 196,478 bytes allocated
==17767== 
==17767== LEAK SUMMARY:
==17767==    definitely lost: 0 bytes in 0 blocks
==17767==    indirectly lost: 0 bytes in 0 blocks
==17767==      possibly lost: 0 bytes in 0 blocks
==17767==    still reachable: 41,687 bytes in 12 blocks
==17767==         suppressed: 0 bytes in 0 blocks
...

普通に開放していない。

最新バージョンでの struct object はこう。

struct object {
	unsigned parsed : 1;
	unsigned used : 1;
	unsigned type : TYPE_BITS;
	unsigned flags : FLAG_BITS;
	unsigned char sha1[20];
};

refsは使わないので消えている。
TYPE_BITSは3。FLAG_BITSは27。上の1 + 1 と合わせて32。なんだかチューニングがすごい。

object.c には

static struct object **obj_hash;
static int nr_objs, obj_hash_size;

相変わらずグローバルに保持している。単純なリストからハッシュに変わったようだ。

まとめ
- 構造体の継承っぽいものが使えそうなら使う。
- フラグ変数はビットフィールドを指定する。
- enum的な文字列定数は const char *でグローバルに書けば良い。
- freeは必須ではない。ただしlostはダメ。
- ポインタ演算を使え。ポインタ演算は p++ とかいう生易しいものではない。
- やっつけ探索を作るときは **objs と memmove。

free に関する参考
http://kmaebashi.com/programmer/c_yota/malloc.html
http://www2s.biglobe.ne.jp/~hig/q_a/Programing_QA03.html
http://www.tohoho-web.com/lng/199912/99120076.htm

*1: http://d.hatena.ne.jp/n314/20130905/1378383066