P/ECEのソースを読む。

ヒープ管理

P/ECEでのheap管理は、主に heapman.c で行われています。ここでは、heapman.cのv1.03(2001.11.20)版に基づいて説明します。

heapの構造

P/ECEのheapは1方向のリンクリストになっています。各リンクのノードはHEAPMEM構造体になっていて、ノードとノードの隙間が記憶領域として使われます。

heaptop
 |
 |        chain                 chain
 |     +----------------+     +---------------+ 
 |     |                |     |               |
 V     |                V     |               V
 +-------+--------------+-------+-------------+-------+----
 |HEAPMEM|              |HEAPMEM|             |HEAPMEM|  ...
 +-------+--------------+-------+-------------+-------+----
            ↑記憶領域その1        ↑記憶領域その2

HEAPMEM構造体の定義はpiece.hにあります。

HEAPMEM
+-----+    
|mark |unsigned short
+-----+
|owner|unsigned short
+-----+
|chain|(HEAPMEM *)
|     |
|     |
+-----+

HEAPMEM構造体は3つのメンバーからなります。

mark: メモリがheapとして使われていることを識別するためのマークです。 heapとして使われる場合、HEAPMEMMK(0xa431)が設定されます。
owner: ノードの所有者を表します。使用されている場合、通常 HMO_DEFAULT_USER(0x1)、システムが利用している場合はHMO_SYSTEM(0xffff)、使用されていない場合は0になります。
chain: 次のHEAPMEMへのリンク(ポインタ)です。

これらがchainのポインタによって数珠つなぎにリンクされています。

個々のHEAPMEMノードが確保するメモリの大きさは、mark->chain - mark になります。そのうち sizeof(HEAPMEM)はheap管理用に使用されるので、実際に記憶領域として使われるのは「mark->chain - mark - sizeof(HEAPMEM)」になります。

関数

static void heapbroken(HEAPMEM *phm)

エラー(APIErr)を吐き、heapが壊れている旨を通知します。 heapが壊れていた場合に呼び出して使います。

static void SetHEAPMEM(HEAPMEM phm, int owner, void chain)

HEAPMEMのsetterです。phmが指すheapに対し、 markにはHEAPMEMKを、そしてownerとchainには、それぞれ与えられた引数を代入します。

static void CombineFreeHEAPMEM(HEAPMEM *phm)

連結するheap領域をつなぎ合わせて一つにします。

heap領域の合わせ方ですが、まず、与えられたHEAPMEMへのポインタphmをphm0 として覚えておきます。これ以降、

phm0: 最初にphmとして与えられたheap領域へのポインタ
phm: 現在注目しているheap領域へのポインタ

という役割分担になります。

phmを動かしながら順にHEAPMEMのノードをなぞっていきます。現在注目しているheapが未使用であれば(phm->ownerが0なら)、 phm->chainをその後に続くHEAPMEMへのポインタにつけ変える、という処理を繰返します。

phm0
|
|
V
+-------+-   -+-------+-   -+-------+-   -+-------+-
|HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
+-------+-   -+-------+-   -+-------+-   -+-------+-
A
|
phm


phm0     phm0->chain
|      +------+
|      |      |
V      |      V
+-------+-   -+-------+-   -+-------+-   -+-------+-
|HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
+-------+-   -+-------+-   -+-------+-   -+-------+-
              A
              |
              phm


phm0     phm0->chain
|      +--------------------+
|      |                    |
V      |                    V
+-------+-   -+-------+-   -+-------+-   -+-------+-
|HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
+-------+-   -+-------+-   -+-------+-   -+-------+-
                            A
                            |
                            phm

phm0     phm0->chain
|      +----------------------------------+
|      |                                  |
V      |                                  V
+-------+-   -+-------+-   -+-------+-   -+-------+-
|HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
+-------+-   -+-------+-   -+-------+-   -+-------+-
                                          A
                                          |
                                          phm

最終的に、使用中のheap領域(phm->owner が0でないheap領域)に辿りつくまで、phm0->chainの指すアドレスは更新し続けます。

さて、こうして連結できるheap領域が求まりました。とはいえ、 phm0からphmまでの連結されるheap領域について、その内容を0x0で初期化する、といったようなことは特に行いません。単にphm->chainポインタの内容が書き換わるだけです。ですが、phmの指すアドレスからphm->chainの指すアドレスまでが一つのheap領域として扱われるため、 phm0からphmまでが一つの大きなheap領域として確保できたことになるわけです。

phm0    phm0->chain
|      +----------------------------------+
|      |                                  |
V      |                                  V
+-------+-   -+-------+-   -+-------+-   -+-------+-
|HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
+-------+-   -+-------+-   -+-------+-   -+-------+-
           ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
       chainをつけ替えると、複数のheap領域(とその隙間)が、

                       ↓

phm0    phm0->chain
|      +----------------------------------+
|      |                                  |
V      |                                  V
+-------+---------------   ---------------+-------+-
|HEAPMEM|               ...               |HEAPMEM| ...
+-------+---------------   ---------------+-------+-
           ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
       一つの大きなheap領域を表していることになる。

static void AllocHEAPMEM(HEAPMEM *phm1, unsigned long size, unsigned long size1)

新しくheap領域を割り当てたり(pceHeapAlloc)、 heap領域の大きさを変更する(pceHeapRealloc)時に呼び出される内部関数です。

sizeは割り当てたい大きさ、size1は割り当てるのに使おうとしている heap領域の大きさを表します。

phm1
 |
 |       |<--size1--------------->|
 |       |                        |
 |       |<--size -->|            |
 |       |           |            |
 V       |           |            |
 +-------+------------------------+-------+--
 |HEAPMEM|                        |HEAPMEM|  ...
 +-------+------------------------+-------+--
       |                          A
       |                          |
       +--------------------------+
         phm1->chain

             ↓

phm1
 |
 |       |<--size1--------------->|
 |       |                        |
 |       |<--size -->|            |
 |       |           |            |
 V       |           |            |
 +-------+-----------+-------+----+-------+--
 |HEAPMEM|           |HEAPMEM|    |HEAPMEM|  ...
 +-------+-----------+-------+----+-------+--
       |             A      |     A
       |             |      |     |
       +-------------+      +-----+
         phm1->chain       phm1->chain->chain (== phm2)

対象となるheap領域のうち、sizeの大きさの分が新しいheap領域として、また残りの size1-size の大きさの分が未使用のheap領域として、 SetHEAPMEM関数によって割り当てられます。前者のownerはHMO_DEFAULT_USERに、後者のownerは0になります。そして、未使用領域はCombinedFreeHEAPMEM 関数によって、後続の未使用領域との連結が行われます。

なお、sizeが変わらない場合には、単にownerが替わるだけです。

void *pceHeapAlloc(unsigned long size0)

大きさsize0のヒープ領域を割り当てます。成功すればそのヒープ領域へのポインタが、失敗すればNULLが返されます。

割りあての戦略は、「best-fit方式」とよばれるものです。これは、 heapのリンクリストを最初から最後までなぞっていき、そのなかで、割り当てたいサイズよりは大きいもののうち、一番小さいものを使います。

割り当てる場所が決まれば、そこから必要な分だけ heap領域を切り出します。空いている領域が、使いたい記憶領域の大きさよりも大きければ、その領域のうち必要な分だけをheapとして切り出します。

+-------+--------------+-------+--
|HEAPMEM|              |HEAPMEM|  ...
+-------+--------------+-------+--
          ↑空き記憶領域

phmは現在注目しているheap領域のアドレスを指すポインタとして、 phm1は割り当て候補のheap領域のアドレスを指すポインタとして使われています。このうちphm1は、割り当て候補が見つかった場合、最後にHEAPMEMの大きさの分だけずらされ、またHEAPMEM構造体を指すポインタとしてキャストされて、返り値となります。

phm1
 |
 V
 +-------+--------------+-------+--
 |HEAPMEM|              |HEAPMEM|  ...
 +-------+--------------+-------+--

            ↓phm1がsizeof(HEAPMEM)分ずらされる

        phm1
         |
         V
 +-------+--------------+-------+--
 |HEAPMEM|              |HEAPMEM|  ...
 +-------+--------------+-------+--

なお、best-fit方式は、理論的にはメモリの断片化が起きやすい、という意見もあります(クヌース『The Art of Programming 基本算法／情報構造』228ページ)が、実測ではそれほどでもないそうです。 (参考: <URL:http://www.memorymanagement.org/glossary/b.html#best.fit> )

int pceHeapFree(void *memp)

割り当てられているheap領域を解放します。

単純に未使用領域とするだけなら、phm->ownerに0を代入すればOKです。が、それでは間違ったポインタが渡された場合にデータを壊してしまいますし、解放された領域も分割されたままです。

そこで、heaptopから順にheapを辿っていき、そのような領域が見つからない場合はエラーを返すようにしています。また、見つかった場合には、ownerを0にしてから、CombineFreeHEAPMEMを呼んで、連結を試みます。

なお、ここでの連結は、解放された領域の一つ前の領域から行います。これは、ちょうど解放する際、その一つ前の領域へのポインタを保存しているためです。下の図で言うと、mempが与えられ、 mempに対応するHEAPMEM構造体を指すポインタphmのheap領域を解放する場合、phmの直前が未使用であれば、 phmbが指す領域から合わせて解放されるのです。

XXX            phmb          phm     memp
 |             |             |       |
 V             V             V       V
 +-------+-   -+-------+-   -+-------+-   -+-------+-
 |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ... |HEAPMEM| ...
 +-------+-   -+-------+-   -+-------+-   -+-------+-
           ↑            ↑            ↑
           未使用        未使用        未使用

int pceHeapRealloc(void *memp, unsigned long size)

割り当てられたheap領域の大きさを変更します。この変更は、再配置は行いません。同じ場所で拡大・縮小を試み、拡大できない場合にはエラーを返します。

ここでも、与えられたmempが実際にheap領域を差しているかどうか、一度heap領域のリンクリストを辿って確認します。

また、sizeが4の倍数になるように調整を行います。 sizeを+3してから切り捨てを行うので、実際には余りは切り上げられています。

これらが済むと、いよいよ領域の変更です。縮小する場合は、単にAllocHEAPMEMを呼ぶだけです。一方、拡大する場合は、領域の後ろに空きがあるか、つまり直後のheapが未使用で、かつ大きさが十分にあるかどうかを調べます。この2つの条件が満たされない場合にはエラー番号を返します。エラー番号は、

mempがheapではない: 1
後ろに空きがない: 2
後ろの空きが足りない: 3

となっています。

十分な空きがあった場合、heapを拡大します。 AllocHEAPMEMで領域を用意し、SetHEAPMEMで初期化します。

なお、後ろの空きが複数つながってる場合でも、直後の一つしか見ません。ここはCombinedFreeHEAPMEMを呼んで連結してもよかったのではないかと思います。

int pceHeapGetMaxFreeSize(void)

未使用のheap領域のうち、最大のものの大きさを返します。

この関数は単純です。リンクリストをなぞっていき、大きさを調べていきます。そして、大きいものの値を覚えておき、終端にたどりついた時にその時点で最大のものを返す、という流れです。

void ResetHeap(void *memp)

mempをheapの先頭にして、heapを初期化します。 mempが0でなかった場合には、そこからsramの最後まで全体を heapとして扱うようにしています。

heaptop                                    sysytem_info.sram_end
 |                                                       |
 |                                                       |
 V                                                       V
 +-------+---------------------------------------+-------+
 |HEAPMEM|                                       |HEAPMEM|
 +-------+---------------------------------------+-------+
  ↑                                              ↑
 ownerなし(未使用)で初期化                ownerはHMO_SYSTEMに設定

void InitHeapman(void)

__PCEKN__ がセットされている場合、各公開APIをPIECEカーネルサービステーブルに設定します。

履歴

2002/07/04: 公開
2002/07/06: APIのインターフェースを一部訂正。すみません。さらに、スタイルシートを変更。

文責など

この文書の内容に関する一切の保証はありません。この文書の使用により発生したいかなる損害についても、筆者は一切責任を負いません。あしからずご了承ください。

この文書の転載は、この文書の筆者と、この文書が無保証であることが明らかである限りにおいて、変更の有無に関わらず、どのような形で再配布されても構いません。