忘れないうちにメモをしろ 2003-08〜


 プログラミングにまつわることで、思い出したこと、考えたこと、気になること など、ともかく低レベルでもみっともなくても中途半端でいいからメモを取ろう、 と思うページ(忘れてしまって困るのは己なのだ)...

※ ろくにチェックせずにアップしとりますんで、鵜呑みにせず、ソースもバグってるかも で気いつけたってください。





 2003-08-10 組込向 malloc (有限メモリの管理)


 malloc を作ってみる。
 と言っても os 環境下用じゃなく、 べたーと連続した固定サイズのメモリ範囲で遣り繰りする、 (コンシューマ)ゲーム機や組み込み用途など有限のメモリ環境下用、って代物。 (まあ os 環境下でも、特定用途用の malloc を作る場合にでも、と)。

 とりあえずの、ソース。 (以下、例によって、とりあえず書いてみただけのソースでチェック不十分なんで、 そのへん信用しないでやってください^^;)

typedef union Header {
    struct {
        union Header *ptr;
        unsigned     size;
    } s;
    double x;
} Header;

static Header *base;
static Header *freep;

void MallocInit(void *mem, unsigned memSz) {
    base = (Header*)(((unsigned long)mem+sizeof(Header)-1) & ~(sizeof(Header)-1));
    base->s.ptr   = base + 1;
    base->s.size  = 0;
    freep         = base->s.ptr;
    freep->s.ptr  = base;
    freep->s.size = ((char*)mem + memSz - (char*)freep) / sizeof(Header);
}

void *Malloc(unsigned nbytes) {
    unsigned nunits = (nbytes + sizeof(Header)-1) / sizeof(Header) + 1;
    Header   *prevp = freep;
    Header   *p;
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) break;
        if (p == freep)          return 0;
    }
    if (p->s.size == nunits) {
        prevp->s.ptr = p->s.ptr;
    } else {
        p->s.size -= nunits;
        p         += p->s.size;
        p->s.size  = nunits;
    }
    freep = prevp;
    return (void *)(p + 1);
}

void Free(void *ap) {
    Header *bp = (Header *)ap - 1;
    Header *p;
    for (p = freep; !(p < bp && bp < p->s.ptr); p = p->s.ptr) {
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) break;
    }
    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr  =  p->s.ptr->s.ptr;
    } else {
        bp->s.ptr  =  p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr  =  bp->s.ptr;
    } else {
        p->s.ptr  =  bp;
    }
    freep = p;
}

 これ、見ただけでバレちゃう人もいると思うけど、 ものは、Cの教科書(K&R 2nd) 8.7(Unixインターフェース "記憶割り当") に あるソースを元に、osからメモリを取得している部分を捨てて MallocInit() で初期化する仕組みに修正しただけのモノ。 あとテストし易いように、ライブラリ付属のmallocと名前がぶつからないように 最初の一文字を大文字に変更してる( ... ああ、作るっちゅーより改造ですね)。

 ...たかだか 60行位のソースなんだですよね。
(行数減らすために、コメント外したり、改行詰めたりしてるけど^^;)

 もともと そんな量のないソースだけれど、 os からのメモリ取得の件をばっさり取っ払ったので、さらに単純。 (os 管理下での malloc の工夫所って os からのメモリ取得/返上の あたりの話だったりするし)。

 そうはいっても一読で何やってるか、 わかるくらい単純明快ではないけど... 難解というほどでもないと思う。

で、どのように断片化(フラグメンテーション)が起こるか、 くらいは知っていたほうがいいな、と。
 いい例が浮かばないけれど、

int main(void) {
    char *p,*q,*r;
    double buf[0x10000/sizeof(double)];
    MallocInit(buf, sizeof(buf));   // ヒープ全体で64Kバイトとする。bufはアライメント済。
    p = Malloc(0x8000);             // 実際には0x8000+8バイト使う
    printf("p=%#x\n",p);
    q = Malloc(1);                  // 領域としては16バイト使う
    printf("q=%#x\n",q);
    Free(p);                        // 開放するから0x10000-16バイトが空きだけど..
    r = Malloc(0xC000);             // q で確保したメモリが途中にいて...
    printf("r=%#x\n",r);
    return 0;
}
なんてやったら、qのメモリに分断されて連続サイズのメモリがなく r が確保できない、 てのは、(机上で追っかけたりアドレス表示で実行したりしたらば)、 なんとなく分かる...かな?

 ヒープサイズの半分以上を要求するなんてのは、そうそうないだろうけれど、 実際には、もっと多くの(コマゴマとした) malloc/free の繰り返しに よって、このような瞬間が発生する場合があって... 大抵はちゃんと動いているのに、たまに起こる、あるいは、 長時間たったら起こる、というような、 不安定で対処しにくいバグに化けやすく... malloc(メモリ分断化)のいやらしいところです。

os支援/仮想メモリのない環境下では致命的なんで、 だから昔は malloc の使用を避ける人も結構いましたし... 今はメモリが増え、使わないとやってられない規模だけど。

 で、ま、教科書通りのmallocっていろんな所で使われているように思うし (メーカー提供のターゲット機向けライブラリのmalloc が 同様にモロ教科書どおりのソースだったこともあるし、 ソース無くても挙動からすると教科書通りだよなあと思えるものもあるし)、 有限のメモリの環境向けにソフト作ってるんなら、 (教科書の) malloc の挙動ぐらい知っといたほうがええんちゃう? と思ってしまうわけで... 魔法じゃないんだから、と。

1回の malloc でせいぜい数十キロバイト、瞬間のトータルが4,500K位 なら、1Mバイトのヒープでもなんとかなるんじゃないかなあー、と 思えるけど、 5Mバイトしかないヒープに 4Mバイトの領域を確保したい、 というのは、なんの工夫(手順)もなしに行うと破綻するだろー、 くらいは、当たり前に判断してほしいなあ、とかね。

 もっとも、メモリ分断化の対策方法は、と、いうと、 特効薬のようなものはなくて、ソフトごとに、工夫することになるのだけれど。

 と、思い出せるものを書き出してみたけれど、他にもあるでしょう。
全く malloc を使わない、ってのは小規模なターゲットのときだけでしょうかね(携帯とか)。

 手段の変形/組み合わせは、ソフトの規模、扱うデータの規模/種類、 移植なら移植元の具合なんかで変わるし、チームや人によって、それまでにやってきた 手段の影響も受けるしで...

 ターゲットのリソースを目一杯使うようなソフトの場合、 メモリ分断化を考慮しないで作ると馬鹿にされてもしゃーないだろうが、 ほどほど余裕があるなら、なるべく、余計な制限つけず手間取らずに、 作れるほうがよいに決まってるもんなあ。

※ ちなみに、上記のK&R改造のMallocは比較的メモリ分断がおきやすい方法になっていると思います。 といっても K&R の元ソースが悪いのじゃなくて前提条件の違う(OS管理下でない)用途に そのまま流用したせいなのですが……ただ結構な(組み込み系の)人が同じ過ちを犯して 余計にmallocの印象を悪くしてたんじゃないかなあ、と、いう気もします。


2003-08-28

K&R2ndを見直していて間抜けに気づく(T T)。 KR2ndのままにbaseを最初から用意しとけば余計なNULLチェックは不要やん。 で、またも修正。




 2003-08-11 組込向 malloc の改造: calloc/_msize/realloc, best-fit


とりあえず
 なんか、当初の予定では先のルーチンを改造していくはずが、 違う流れに書き進めてしまったので、仕切りなおし^^;

 で早速、先のmalloc は、行数短くするために殺ぎ落とした分もあるので 直前のバージョンが

mlc_smp_2.c
2003-08-28 K&R2ndを見直していて間抜けに気づく(T T)。 KR2ndのままに base を最初から用意しとけば余計なNULLチェックや繋ぎ替えは不要やん。 で、またも修正。
...なんか、コメントのせいでかえって、ごちゃごちゃしちゃうけど。
 前回のとの違いは、ヘッダのアライメントを参照元(K&R 2nd)の まま一旦 typedef で Align 型を用意してるのと、 メモリ取得の基本単位を UNIT_SZ というdefineマクロでバイト数を設定 するようにしてるのと、初期化で領域を0x55で埋めている、て ところですかね。

 基本サイズを最長アライメント単位でなく、それより大きい 別の値(といっても2のn乗限定)にできるようにしたのは、 ターゲット機によって DMA 転送で使うアドレスの制限が 32バイトだったり 64バイトだったり することがあるので、そういうことを考慮して、てのが、まず一点。
 他に別途あるデータ専用のmallocルーチンとした場合、256バイトなり1024バイトなりのある 程度まとまったサイズ単位で処理することが多いなら、予めそのサイズを基本とすることで、 多少メモリ効率が落ちてもメモリ断片化率を減らそう、と考える場合もあると。

(追記)  アライメントってことでは、os/ライブラリによっちゃアライメント指定付きのメモリ取得関数 (un*x系だと memalign とか vcでも似たようなものとか)があって、そういうのを用意しとくほうが 筋なような気もするけれど... 使い分けるのが面倒(てか使い分けてくれない人がいるとか)とか ターゲットで要求されるアライメントは1つなんだから汎用にする必要もねーな、で...いや、ま、 作るのが面倒臭そーなんです^^;

 ヒープ領域の初期化を 0x55 とかでやるのは、 プログラム作成中未初期化でメモリを参照してしまったときに、 デバッガでみて未初期化だと気づきやすくするため、ですね。 値は別に 0x55 でなくてよいけど、見て分かりやすい値。 文字列とかで埋めるのも手(実際そういうターゲットあったし:-)。 ただ、値は奇数のほうがいいかも。誤って未初期化のポインタとして 使われたときに(x86じゃないCPUの場合)アドレスエラーで落ちやすいだろう、で。

 また、この初期化で 0や 0xff(-1) を使っちゃうと、意味のある値に化けやすく、 未初期化のまま使っていることに気づかず、起動直後はちゃんと動くけど、時間がたつとおかしくなる、 なんてバグが発生したりするので、通常のmalloc用としては、やめたほうがいいでしょうね。



calloc,realloc,msize の追加

malloc,free 以外も一応、書いてみましょうか。といっても、お手軽(手抜き)版だけれども。

/// 配列を想定した引数で、かつ、0クリアされるメモリ確保
void *Calloc(unsigned num, unsigned asz)
{
    unsigned sz = asz * num;
    void     *m = Malloc(sz);
    if (m)
        memset(m, 0, sz);
    return m;
}

/// mallocされたメモリの領域サイズを返す
unsigned Msize(void *mp)
{
    return ((Header*)mp - 1)->s.size * UNIT_SZ;
}

/// mallocしたメモリのサイズ変更(手抜き版)
void *Realloc(void *s, unsigned dsz)
{
    unsigned ssz = Msize(s);
    void     *d  = Malloc(dsz);
    if (ssz > dsz)
        ssz = dsz;
    if (d)
        memcpy(d, s, ssz);
    Free(s);
    return d;
}

 calloc は、メモリクリアを memset でやっちゃってるけど、 UNIT_SZ/アライメントに依存して幅広の型で 0クリアするように 書き換えたりするかな。

 realloc は、ターゲット環境用では自分ではまず使うことないなあ、 なんで、端から手抜き^^;。

 Msize(p) ってなってるのはc標準関数では無いですが、 vcとかbccなら _msize(p) として用意されている関数で、 他のコンパイラでも同様な機能の関数が用意されていると思う。 (仕組みを考えたら、まずあるだろう、と)。




ベスト・フィット法

 いままでのが、ファーストフィット法で...〜法、とかいうと、タイソウなモノのような気になるが、 こいつも別段たいしたことじゃなくて.

 空ブロックを管理するリストから、今回リクエストされたサイズのメモリを 取得するにあたって、first-fit法だと要求サイズを満たす空きブロックの、 最初に見つかった所から必要量を取っちゃうんですが、 best-fit法だと、要求サイズになるべく近いサイズのブロックを探す(一通り空きブロック をチェックする)、となります。

とりあえず、該当部分のみを修正してみるとこんな感じですかね。

void *Malloc(unsigned nbytes)
{
    // ヘッダ部を含めた必要メモリのサイズ(Header単位)を求める
    unsigned nunits = (nbytes + UNIT_SZ-1) / UNIT_SZ + 1;
    Header   *prevp = freep;
    Header   *p;
    Header   *f = NULL;

    assert(freep);
    // 空きブロック一覧を順繰りにナめる。
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
        // 要求サイズを満たし、初発見、または現在の発見分よりジャストに近い
        // サイズ、また同一サイズならなるべく高アドレスの場合、それを選択。
        if (p->s.size >= nunits && (f == NULL || p->s.size < f->s.size || p > f))
            f = p;
        if (p == freep) {           // 空き一覧の先頭に戻ったのなら
            if (f == NULL)
                return NULL;        // 空きが無かったら帰る
            p = f;                  // 見つかったものを設定
            break;
        }
    (後略)


 ジャストのサイズなら、これ以上の分断化にはならないし、分断する場合でも、 なるべく近いサイズを選ぶことで、それよりも大きな空き領域ブロックが 分断化されることを防ぎます。将来の、より大きなサイズのリクエストに 備えて、大きな空きは大きなまま残しておこう、てとこでしょうか。

 使い方(mallocサイズやmalloc/free)の順番によっては、 first-fit よりもメタメタになってしまう場合もあるかもですが。

 速度ですが、一般的には、first-fitのほうが検索量が少なく すむので有利ってことになるみたいです。 が、first-fitは細切れになりやすいので、 あまりに分断化された空きリストが増えると、 分断化が抑えられているbest-fit法のほうがかえって早く 検索が終わる、って状況もありえるかも、と。

 あと上記ソースですが、正確にはベストフィットをちょっと弄ってます(?)。 ジャストのサイズがほしいだけならば、ジャストのメモリがあった時点で 打ち切れば速度的にも有利なんですが、 上記ソースでは、成るべく取得するメモリは、高アドレスのメモリに なるよう、チェックを加え、空きを全てなめるようにしています。
 高アドレスなのは、空き領域の後半/高アドレスからメモリを取るというのが 基本の仕組みだからですが、ようはヒープバッファの片方に偏らせることで 反対側が成るべく広くあく可能性がありそうですし、 ある程度コントロールしてmalloc/freeを行う場合に動作を把握しやくすく するためでもあります。

 first-fit法でも、malloc/free を順番をきっちり守って行えば スタック(push/pop)のように破綻せず空きブロックも1つのままになるけど... それじゃ malloc でなくスタック式の管理を使えばええやん^^;、てことになるので... malloc/free を使う以上は、ある程度自由なタイミングで行いたい、わけで。

 ただ、ある程度の自由(遊び)はあるけれど、ある程度は制御可能...かも、って あたりを期待するわけで...ううと、  偏らせて把握しやくする、っという意味では、 高アドレスに寄せるだけにして、 best-fit にしないほうが、よいかもなー、とも思えたり^^;


 このソースの場合、 最初に見つけた空きを即採用するから分断しやすい、ってのよりも、 実のところ、Malloc() の最後のほうの

 freep = prevp;

や Free() の最後の

 freep = p;

ってのが、ミソで、今回メモリを分離取得した空きブロック、または、 今回開放した所の空きブロックが、次回の検索の初っ端になる、って 仕様になってることのほうが原因なんかなあ、と。

	MallocInit(buf,0x10000);
	p = Malloc(0x1000);
	q = Malloc(0x1000);
	Free(p);
	r = Malloc(0x2000);
	s = Malloc(0x1000);
なんて、ことをした場合、best-fit法やヒープの片端寄せを している場合は s のアドレスは p になるでしょうが、 KR な first-fit法だと新たなブロックから取得して、 p の空きは使わずになってしまうんですね。

 このようなことが、どんどん繰り返されると、ボロボロの空き状態に 成りやすいかもー、と。

 なんでメモリ断片化対策としては freep の更新をやめちゃうほうが マシになるんちゃうかなあ、と... ただこのソースだと、空き領域からの切り取り方法と管理リンクの向きがあってないようで 止めるだけだでは、あまり、よくはなさそーにも思うし...

 で、結局、空き領域リンクの向きをかえて高アドレスから検索するようにすれば (ヒープの片端に寄せれば) よさそうかな、と。 まあ、よい方法かどうかは結局運営方法しだいなんですが、 己の都合にはよさうに思えたり... このへんは、後述。


(固定位置開始のfirst-fitと、再開位置が転々とするbest-fitでは、 どちらが安定なんかなあ、とか^^;)

...(追記)己ルーチンでは"固定位置開始のfirst-fit"のほうが安定してそでした... というか、、上記例のはやっぱりあんましよくないかも、です。 なんか後述のテストをbest-fitで試すとメタメタ...(バグってるのかとも)。



※ベスト・フィットの参考としては こちらとか。 OS環境下の汎用のmallocのソースだけれど、各種コンパイラ/OSのmallocルーチンの比較解説とかがあって読み物としても。




 2003-08-24 組込向 malloc の改造: チェックを付加


 前回の続き、てか前回の書き残しをば...

 こういう単純なメモリ範囲での管理なんで、 ポインタが Malloc されたかどうかくらい簡単にチェックできるのだからヤラなきゃ損、てことで、 チェックを追加しときます。 範囲チェックだけだとあれなんで、id チェックもしちゃいましょうか。 とりあえず前回後付したcallocやらfast-fitのことは除けて、 mlc_smp_2.c を修正して、

mlc_smp_4.c
 色つきの辺りが追加分で、そのうち行末に★があるのは id チェックに関するもの。 (CHECK_HDR_PTRの引数の分は置いといて、と^^;)

 idの為に管理ヘッダのサイズが増えてしまうのは、 用途によってはちょっといやなんで、 実際には やっぱり id チェック無しにしたり、 idチェック関係を #if で囲んでデバッグ時のみにしたり、 あるいは、
    struct {
        union Header *ptr;
        unsigned short size;
        unsigned short id;
    } s;
のように size と id を unsigned short(2バイト) にしてヘッダを小さく(8バイト)したり、でしょうか。
 size と id を (unsigned)short にしたときは、念のため、MallocInit() に
assert(memSz < 0x10000*UNIT_SZ);
を付加しといたほうが無難かも…… ええ、間抜け者なので見事にハマったことあります(T T) 基本メモリ 2Mバイトな環境(PS,SS)で十分使いこんでるから安心ルーチンのつもりで そのまま32Mバイトな環境(PS2)で10Mバイト確保して使ってたら挙動不安定... なるわな^^;

 id の値ですが、適当です。めったに使わなそうな値ならで何でも... 正常なポインタに見間違えそうな値にはしないほうが無難で、例によって 奇数のほうがベターかなと。

 ポインタの範囲チェックのほうですが、リンクをナめるループのなかで、 CHECK_HDR_PTR() で毎度呼び出してますが、 ターゲット環境やmallocの 使用頻度によっては、やっぱり速度が気になることもあるので、 精度は悪くなるけどループ内のはコメントアウトして、ループアウトした ところで CHECK_HDR_PTR() を呼び出すほうが良いかもです。 というか、普通はこっちのほうが無難かも。 リンクの整合性チェックについては、それを行う関数を別途用意して 要所要所で呼び出してチェックすれば、と (ゲームの場合は根元の毎フレーム(int)のループ内で呼べば、で)。

 ああと CHECK_HDR_PTR は inline 指定で、(c++でなく) c コンパイラによっては_inline だったりインラインできなかったりなんですが... c 用としての汎用性を高めようと思うと#define にしとくのがベターでしょうが 見易さと現状の目の前のコンパイラを思うとそこまで手間かける必要ないわなあ、で。 (c++としてコンパイルするなりコマンドラインで-Dinline=_inlineでするなり、と)。

 あとできそうなチェックとしては、malloc()で返す使用中メモリについても 空きリストと同様な使用中リスト(リンク)を作って、 合計サイズチェックやリンクの正当性チェック、 を行ったりするのも考えられます...が、 実際にやってみた時の感触としては、 他のチェックをやっていれば 手間(リンクの作成/検索のコスト/速度)に見合わないような気はしました^^; (と、いいつつ、それで見つけたバグも無くも無いな...)

 Free の最初のNULLチェックは単に前回のソースでの書き忘れの追加です。 己的には、あえてエラーチェックに引っ掛けたい場合のほうが多いし、 さらにもう1クッション上ッかぶせでNULLチェック&エラー処理 付きのMalloc,Freeを用意したりすることが多いので (コンパイラ/ライブラリのmalloc,freeの違いを吸収する場合もありで)、 ないほうが都合がよいかなあ、って気もありますが、 NULLを素通りさせるのが普通(仕様)なのかもで、とりあえず。

2003-08-28 K&R2ndを見直していて間抜けに気づき、ソース&本文修正




 2003-08-24 組込向 malloc の改造: ヘッダサイズとブロックサイズの分離


 アライメントは32バイト,64バイト単位にしたいけれど、でもヘッダは 8〜16バイト くらいしか使ってない、てのは、どうも無駄が大いように感じてしまう もんでして... 32バイト単位でヘッダ16バイトなら16バイト、64バイト単位でヘッダ12バイトなら 52バイトも無駄にすることに....大きいなメモリを少々取得するだけなら気に ならないけど、小さいメモリを大量にmallocする場合は、やはり気になる、なあ、で。 ...なんかロートルだから、ですみそうな気もしてますけどね^^;

 隙間を別の用途(ファイルキャッシュ等向けに名前付きメモリにしたりとか) に使うのも手なんですが、ちょっと改造して、ヘッダサイズと単位サイズを 別々にする(ヘッダの管理と単位サイズの管理を分離する)、 てのが正当でしょう(たぶん)。

 今までのソースは Header 型でヘッダの管理と 単位サイズの管理/アドレス計算を行っていたので、それを先に分離しましょうか。  ちと面倒だけどとりあえず、 mlc_smp_4.c を動作同じままアドレス計算の 部分などを修正して

mlc_smp_5.c
に。#define マクロでごてごてしてきちゃうけど。

 で。
 malloc で返す先頭アドレスが、32なり64なりでアライメント された値になってほしい、てのは、ようは、ヘッダのケツが丁度アライメントされた アドレスになればいい→アライメントされたアドレスからヘッダサイズ分、前にした位置を ヘッダ込みのブロックの先頭アドレスにしてあげればいい、ってコトになります。

 さらにこのソースではbaseで指しているヘッダは、まさにヘッダサイズだけで十分なんで そのサイズもアライメントとしたアドレスの手前に置くことにします。 (ああ *base に関するアライメントは他のときと違ってきちゃうため、 アドレスチェックではbaseを例外扱いにする必要がでてきます)。

 てことで、ヘッダサイズを12バイト、単位サイズを64バイト、ということにしたソースが

mlc_smp_6.c



2003-08-28
K&R2ndを見直していて間抜けに気づき、ソース&本文修正.

2007-07
サンプルのままだと問題ないけれど、UNIT_SZ<HDR_SZに設定した場合、 メモリ破壊バグになってしまってたのを修正.




 2003-08-24 組込向 malloc の改造: ヒープバッファの片端に寄せる


 ベスト・フィットのところでもちょこっト触れた、ヒープバッファの片端寄せ、についてです。

 検索の開始を不特定でなく、高アドレスの空きブロックからにしちゃおう、 freep を毎度更新するんじゃなくてなるべく変更しないように、って方針です。

 検索開始は base からでいいので、freep が必要なくなります。

 その代わり高アドレスから検索するように、空き領域リストのリンク方向を逆に します...なんで基本的に Malloc はそんなに代わらないけれど、Free 側は結構書き換え。

あ、s.ptrが逆向きになったので、ヘッダチェックも若干修正が必要ですね。

 ちなみに、もともとのルーチンが、空き領域の高アドレス/後半からメモリを取ってくるのは、 たぶん、このほうが、リンクの更新とかが若干簡単になるから、だろうなと、思います (以前、低アドレスから取得のルーチンを作ってみたときに感じからすると)。
つうことで、ソースは、mlc_smp6.cを修正して
mlc_smp_7.c

といったところ。


 あと、いくつかの関数

// 以前例に出したもの
void *Calloc(unsigned asz, unsigned num);
void *Realloc(void *s, unsigned dsz);
unsigned Msize(void *mp);

// 今回の追加
/// ポインタがMallocされたもの(1)か(0)か
int IsMallocPtr(void *mp);
/// 1度に Malloc できる最大サイズを返す
unsigned MaxSize(void);
/// 空き領域の、MaxSize(), 空きサイズの合計, 分割数 を変数にいれる。
/// 復帰値は、空き領域リンクが正常なら 1、壊れていたら 0を返す。
int GetEmptySize(int *maxSz, int *totalSz, int *split);
を追加して、
mlc_smp_6a.c (ヒープ片端寄せ無し)
mlc_smp_7a.c (ヒープ片端寄せあり)
というようなソースにしときます。
(ついでにMalloc,Freeでの検索ループ内で行っていたポインタチェックをループ外のみに変更)。

で、適当にテストして、と。


て感じでしょうか...なんかお題目どおりのような...
ただサンプルが、偏ったものなので、 も少し違うチェックしたら違ってくるかもだけど。 (FIFO的にmalloc/freeしてるので空きバッファが連結しやすい)

(問題は、これで、best-fit 法を同様にテストしてみたら、 ひどくメタメタな結果となってしまったのでした... NULLが返りまくる... ひょっとすると、以前出したルーチンはどこかバグバグなのかもとも思えてくる... が単に、best-fitに不利なサンプルになってるだけかな、とも思う... とりあえず、サンプルには上げていません^^;)


 しかし、難産だった...この片端寄せは。 以前に c++ で書いたものがあって、それを今回のソースに合わせて書き直したのだけど... テストしたらハング...T T(c++版がカキッぱだったのもあるけど)。 おかげで、バグが発見できたわけですが (Freeしたメモリが、ちょうど一つしかない空きブロックの直前に合体して一つになるときの ポインタのつなぎ替えがバグってる)...時間食う食う。 ああc++で書いた片端ヒープと両端ヒープのソースも修正せんといかんなあ、はあ... (もともと、そのc++で書いた片端/両端 malloc をネタに頁書くつもりが ちょっとKRから引用したらずるずると...本末転倒...いやバグが取れてよかったんだけど)

2003-08-28 追記
 と K&R2ndを見直していて、間抜けに気づく... K&Rのままに base(絶対削除されない0サイズの 空き)を用意していれば、いままで発生したバグは起きなかったんだよな(T T)。 ちょっと削ったばかりにえらい遠回りをしてしまった模様...はあ。

2007-07
サンプルのままだと問題ないけれど、UNIT_SZ<HDR_SZに設定した場合、 メモリ破壊バグになってしまってたのを修正.





 2003-09-21 WinCVSの Build ChangeLog で日本語...


 うーmalloc系のネタが結構面倒な書き方をしてしまったためにちと息切れ... もっともっと手抜きに書くようにせんと>己。 直接のプログラミング以外のネタもね。 当初は書くつもりがなんか書きづらくなってしまって別項にしたらやっぱ続かんのだし。

 と愚痴はほどほどにして、題のネタ。

 と、まあ、お仕事なんぞで、WinCVS を使ってるわけで。 といっても日本語でないとダメな人間の集まりなんで、最新版でなく1.2な ごった煮版だったり、 サーバ用意せずにローカルだけでやってる(のでたまにヤバゲな事故したり) ちとヘタレなんですが。

 使ってて、ちょっと悔しいのが、マクロの Build ChangeLog が日本語に対応して くれていないこと。日本語が ???? に変換されてる... お陰で、変更履歴を別途 書く羽目に...なんだかなあ、で(いや、別途流れを見通して書くのは意味あるだろうけど)。

 最新のWinCVSにすれば対応するのかなあ、いや、 マクロ言語は別インストールの tcl が用いられているだから そちらが日本語対応してりゃ...あ、とうに"国際化"されているらしい... じゃなんで?オプション設定か何か?とそこで気力はててしばらく忘去...だったが、 今回別件検索でひっかかった Tcl/Tk入門な頁を ぱらぱら見てて"国際化" でやっと気付く。 ソース中のどっかで encoding の指定がされてるだろうなあ。案の定 macros/cvs2cl.tcl には

 69:            fconfigure $flog -encoding iso8859-1 -translation auto
270:    fconfigure $fCLog -encoding iso8859-1
なんてある(行番号はごったに版に同梱されてる版のもの)。 iso8859-1 ってのが日本語(シフトJIS)使う上でまずいんだろうなあ、で、
 69:            fconfigure $flog -encoding shiftjis -translation auto
270:    fconfigure $fCLog -encoding shiftjis
と shiftjis に置き換えたところ、あっけなく、シフトJISテキストで ChangeLog が 生成できたのでした。お手軽にすんでちょとラッキー。
 あ、うちの場合は、リポジトリもSJISのままなんで。


 リポジトリ側が EUC なら どちらかを euc-jp にしたらいいのかも...と思い 仮のリポジトリをEUCで用意して試すがこれは失敗。 どこかでへんに文字コード変換があるんかなあ。 何か設定/手順が悪いだけのような気もするけれど。

※ChangeLog にはあまり関係ないけど、"更新ログを日本語EUCで記録"って まさに"更新ログ"のみEUCでソース本体は変換されない(ShiftJISのまま)だったのね... いや、サーバ使用でknjwrp設定すりゃ大丈夫なのかな?... CVSのeuc/sjis相互変換モジュール というものがあるようなんで差し替えればリポジトリ側EUCにできそだけど (ChangeLog 対策にはならんかな)。


 と。
 ためしに(英語版のままの) WinCVS 1.3β13 にて ChangeLog 生成すると、 ちゃんと日本語で生成出来たのでした...ううむ^^;。
 リポジトリ側のログが ShiftJIS なら ShiftJIS で、EUC-JPならEUC-JPでって感じですが (コード判定しているのか否かはようわからんけど)。 EUC-JPをShiftJISにしたい場合はやっぱ何ぞ修正しないとダメなんやろなあ、て気はする。

 あ、マクロ言語が 1.3 からは Python になってるぽいです。 tcl のも残っているけど、デフォルトは Python という感じ。 簡単な試しなんだから Tcl 使だけつかわしてくれたらいいのに Pythonインストールせんことにはマクロが選べない(T T)。 しゃーないので、日本語(SJIS)環境対応版 Pythonをインストールしてしのぐ。 (てことで生成できた Build ChangeLog は Python版ね。 tcl版はちょっとバージョンアップしてたみたいだけどencodingについてはかわりなし)。

 その他ちょっと触った感じ、右クリックメニューの import がちゃんとその場でimport できるようになっててヨシなんですが...相変わらず シフトJISテキストはバイナリ扱い。 結局、1.2ごった煮版を使い続けるのね。
(※追記 1.3β14 にすると .c 等ソースではSJISがあると範囲外の文字コードがあるってエラー言われるけれど オプション自体はテキストで処理してくれるようになった模様)

※しかし、またも何か根本的に間抜けなためにしなくていい苦労をしてしまってるような 気がしないでもない...


その他、CVS関係のサイトへのリンクメモ:  入門 CVS サポートページ  CVS, WinCVSについてのメモ  /nishi/cvs/ml-log  CVS NT をPserverでインストールする  28wincvs  CVS 1.11 manual 日本語訳  (1.9)  The CVS Book 日本語訳  ExamDiff (日本語化)  CvsIn  WinStay



[前] [次] [戻る]