【C】「プログラミング言語C」の malloc と free 関数のコード

プログラミング言語C 第2版 ANSI規格準拠」の P225 付近に載っている malloc のコードです。

 

  • 10数年前に作成したコードが見つかりました。
  • C言語の学習のためにコメントを色々と書き込んでいるようです
    • 自身への解説書まで残していました*1
    • また、学習のために free 関数も作成していたようです。

10年以上前のコードなので色々と不備があるかと思いますが、これも資産のひとつなので書き残しておきます。*2

コード

// [プログラミング言語C] p225
// 本の「記憶割当て」プログラムにメモリ解放処理関数 afree() を加えてみた

#define    DEBUG

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

#if    defined(DEBUG)
#define    DBP    printf
#else
#define    DBP
#endif

typedef    long    Align;

union    header
{
  struct
  {
    union    header * ptr;  // 4bytes (Pen4)
    unsigned          size; // 4bytes (Pen4)
  } s;
  Align  x;    // 4bytes (on Pen4)
};

typedef    union    header    Header;

static    Header    base;
static    Header  * freep = NULL;

#define    NALLOC    4     // 極端に小さくする(== 2)とデバッグ出来る

void * alloc(unsigned nbytes);
void   afree(void *p);
void   add_FreeNode_to_FreeList(void *ap);
static  Header    *morecore(unsigned nu);

int
main(int argc, char *argv[])
{
  char    *str;
  int    i = 1;

  if (argc == 1)
  {
    fprintf(stderr, "Usage: %s <arguments>\n", *argv);
    exit(2);
  }

  while (*++argv)
  {
    DBP("\n\nmain(): ********* (char *)alloc(strlen(\"%s\")+1) => (char *)malloc(%d)*********\n",
      *argv, strlen(*argv) + 1);
    str = (char *)alloc(strlen(*argv) + 1);
    strcpy(str, *argv);
    printf("answer: %s\n", str);
    afree(str); //メモリを解放する
  }

  return 0;
}

// メモリ解放処理関数
// 0 クリア後にフリーリストに登録する
void
afree(void *p)
{
  int    i;
  //unsigned    size;
  Header *fp = (Header *)p;    // ヘッダは含まない
  Header *hp = (Header *)p - 1;    // ヘッダを含む(ヘッダ部参照用) -0x00000008

  DBP("\nafree(): ************* free memory(%p) *************\n", p);

  // 以前にアロケートして使用していた領域を 0 クリアする(取り敢えず memset() を使わず)
  for (i = (hp->s.size * sizeof(Header) + sizeof(Header)); i > 0; i--) {
    *(char *)p = (char)0;
    p++;
  }
  hp->s.ptr = 0;    // 次のフリーノードへのポインタは, この後の add_FreeNode_to_FreeList()
          // で設定されるのでNULLクリアしなくても別に良い

  // フリーノードにしたのでフリーリストに登録する
  DBP("afree(): call add_FreeNode_to_FreeList(%p)\n", fp);
  add_FreeNode_to_FreeList((void *)fp); // フリーノードのヘッダ部のアドレスは渡さなくて良い
}


// フリーリストから nbytes を確保出来るフリーノードを探し,その領域のアドレスを返す
// フリーリストが無い場合は、morecore() をコールし、メモリをもらう
void *
alloc(unsigned nbytes)
{
  Header *p, *prevp;
  Header *morecore(unsigned);
  unsigned nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

  // 初期状態では freep == NULL となっている
  // 2回目以降の alloc() では、前回 freep で記憶させておいたアドレスが利用される
  if ((prevp = freep) == NULL)    /* no freelist */
  {
      // 初期状態ではフリーリストが無いので 
      // base 自身をポイントするようにしておく
    base.s.ptr = freep = prevp = &base;
    base.s.size = 0;
  }

  // フリーリストを辿って使用可能なフリーノードを探す
  DBP("alloc(): ********* Search free-node at alloc(%d byte) *********\n", nbytes);
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
  {
    DBP("alloc(): (p, p->s.ptr, p->s.size) = (%p, %p, %dblk)\n",
      p, p->s.ptr, p->s.size);
    // 見つかったフリーノードには要求分以上のブロックがあるか?
    if (p->s.size >= nunits)
    {
      // 丁度、要求分だけフリーノードがあった
      if (p->s.size == nunits)
      {
        DBP("alloc(): found free-node just fit size(%d blk)\n", p->s.size);
        // p がポイントしているフリーノードを全部使い切るので,
        // フリーリストから削除する
        prevp->s.ptr = p->s.ptr;
      }
      // p がポイントしているフリーノードから nunitsブロック分拝借する
      else
      {
        // 使用する領域はフリーノード内の末尾から使用する
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
        DBP("alloc(): found free-node(%p, %dblk)\n", p, p->s.size);
      }
      // p が現在ポイントしているよりも1つ前のフリーノードのアドレスを
      // freep に記憶させておく. 次に alloc() が呼ばれたときは freep 
      // で記憶させておいたフリーノードから探索を開始する(フリーリスト
      // は循環構造になっているので全てのノード探索は可能)
      freep = prevp;
      DBP("alloc(): Point to freep(%p)\n", freep);

      // ヘッダ部(s.ptr, s.size)を除いたメモリ領域へのアドレスを返す
      // (void *)p+1 だと +0x00000001 になってしまうので注意
      DBP("alloc(): alloc() return new area(%p)\n", (void *)(p + 1));
      return    (void *)(p + 1);
    }

    // 初期状態では base をポイントしている
    // base.s.ptr = freep = prevp = &base;
    if (p == freep)    // フリーリストを一周したか?
    {
#if defined(DEBUG)    
      DBP("alloc(): Not found free-node. (p, freep) = (%p, %p)\n",
        p, freep);
      DBP("alloc(): call morecore(%d blk)\n", nunits);
#endif
      // フリーリストを一周探索したが、フリーノードは見つからなかったので
      // morecore(ブロック数) をコールし、メモリを取得する
      if ((p = morecore(nunits)) == NULL) {
        return    NULL;    // 割り当て可能なメモリが無い
      }
    }
  }
}

static
Header * morecore(unsigned nu)
{
  char *cp, *sbrk(int);
  Header *up;

  // sbrk() を呼ぶのはコストが高いので, 何度もコールしなくて良いように,
  // 最低 NALLOC からブロックサイズを要求するようにしておく
  if (nu < NALLOC)
  {
    nu = NALLOC;
  }
  DBP("morecore(): ********** require %dblk,  %dByte *********\n", nu, nu * sizeof(Header));

  // メモリ領域(x ユニット数)を取得し, ヒープ領域を広げる
  // 新しい領域の先頭へのポインタを返し cp に代入しておく
  DBP("morecore(): call sbrk(%d * %d)\n", nu, sizeof(Header));
  cp = sbrk(nu * sizeof(Header));

  // sbrk() に失敗した場合はアドレスに -1 が返されているが、
  // void *sbrk(int) であるため,キャストして確認する
  if (cp == (char *)-1)
  {
    return    NULL;
  }

  // 先ほど sbrk() で取得したヒープ領域へのポインタ cp を up にコピーし、
  // ヘッダ(up->s.size) に使用可能なブロックサイズ値を持たせておく
  up = (Header *)cp;
  up->s.size = nu;
  DBP("morecore(): allocated New free-node (address=%p, block size=%d)\n", up, up->s.size);
  DBP("morecore: call add_FreeNode_to_FreeList(%p), Add New free-node(%p) to FREE-LIST\n", (void *)(up + 1), up);
  // add_FreeNode_to_FreeList() にて、sbrk() で新たに取得した
  // フリーノードをフリーリストへ登録する
  add_FreeNode_to_FreeList((void *)(up + 1));// ヘッダ部(s.ptr, s.size)を除いたブロック領域の先頭アドレス

  return    freep;
}


void    add_FreeNode_to_FreeList(void *ap)
{
  Header *bp, *p;

  bp = (Header *)ap - 1;    // フリーノード全体、つまり、ヘッダ部(s.ptr, s.size)を含む
              // フリーノードへのアドレスを bp にコピーする

  DBP("add_FreeNode_to_FreeList(): ********* \
        START!! add new free-node(%p) to free-list *********\n", freep);

  // 2つの既存のフリーノード間か、フリーリストの終端に追加される
  // forループ内にてフリーリストを探索し、「2つの既存のフリーノード間か、
  // フリーリストの終端」に該当する箇所があれば、break する
  for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
  {
    // forの継続条件は (bp <= p || bp >= p->s.ptr) ということであり、
    // 「現在のフリーノードのアドレス > sbrk() で取得した領域のアドレス」
    //  or「次のフリーノードのアドレス < sbrk() で取得した領域のアドレス」の場合に
    // 探索が継続される

    // フリーリストの先頭 あるいは 末尾であるか?
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) {
      // フリーリストを一周し(p >= p->s.ptr), かつ, 
      // [現在のフリーノードが sbrk() で取得した領域よりも低アドレスにある]
      // あるいは [次のフリーノードが sbrk() で取得した領域よりも高アドレスにある]
      // なお、if(p >= p->s.ptr) だけではフリーリストの終端が見つけられない
#ifdef    DEBUG
      if (bp > p)
      {
        DBP("add_FreeNode_to_FreeList(): bp(%p) > p(%p)\n", bp, p);
      }
      else if (bp < p->s.ptr)
      {
        DBP("add_FreeNode_to_FreeList(): bp(%p) < p->s.ptr(%p)\n", bp, p->s.ptr);
      }
#endif
      break; // p はフリーリストの先頭ノードあるいは終端ノードをポイントしている
    }
  }

  // まずは [新フリーノード] と [既存の次のフリーノード] を繋ぐ
  // [現在のフリーノード]   [新フリーノード] => [既存の次のフリーノード]
  if (bp + bp->s.size == p->s.ptr)
  {
    // sbrk()で取得した領域よりも高アドレスに次のフリーノードがある場合に、
    // bp から要求されたブロック分(bp->s.size)だけポインタを進めたアドレスが
    // 丁度、次のフリーリストと同じアドレスだった場合は、2つの領域を合併する
    DBP("add_FreeNode_to_FreeList(): bp->s.size(%d) + p->s.ptr->s.size(%d) = %d\n",
      bp->s.size, p->s.ptr->s.size, bp->s.size + p->s.ptr->s.size);
    bp->s.size += p->s.ptr->s.size;
    bp->s.ptr = p->s.ptr->s.ptr;
  }
  else
  {
    bp->s.ptr = p->s.ptr;    // リンクする
    DBP("add_FreeNode_to_FreeList(): Linking [New free-node(%p)] => [next free-node(%p)]\n",
      bp, bp->s.ptr);
  }

  // 次に [新フリーノード] と [既存の現在のフリーノード] を繋ぐ
  // [現在のフリーノード] => [新フリーノード] => [既存の次のフリーノード]
  if (p + p->s.size == bp)
  {
    // 現在のフリーノードにブロック分(s.size)だけアドレスを進めると
    // sbrk()で確保した領域の先頭アドレスと同じになる場合, 現在の
    // フリーリスト領域と bp 領域を併せてしまう 
    p->s.size += bp->s.size;
    p->s.ptr = bp->s.ptr;
  }
  else
  {
    p->s.ptr = bp;        // bp は新たに与えられたフリー領域へのポインタ
  }
  // 以上により 新フリーノード がフリーリストに登録出来た

  DBP("add_FreeNode_to_FreeList(): FINISH!! new free-node added to free-list\n");
  DBP("add_FreeNode_to_FreeList(): p(%p) ---> bp(%p) ---> p->s.ptr(%p)\n", p, bp, bp->s.ptr);
  freep = p;
}

 

備忘録(解説?)

/*=========================================*/
   if(NALLOC == 2), demand 2byte(alloc(2)) 
/*=========================================*/
(1) get 2block(== NALLOC) by morecore(), because memory pool is not exists.
(2) link free_list at add_FreeNode_to_FreeList()
     +------+
 +---|*base |
 |   +------+
 |    
 |   +------+------+------+------+ 
 +-->| *ptr | size |      |      |  # size is block count.(size == 2)
     +------+------+------+------+ 
     <-- 8byte ---> <-- 8byte --->

(3) allocate 2block(just size!!) at alloc(). unlink block from free_list.
    return address(A).
     +------+
 +---|*base |<--+
 |   +------+   |
 +--------------+

     +------+------+------+------+ 
     | *ptr | size | (A)  |      |  # size is block count.(size == 2)
     +------+------+------+------+ 
     <-- 8byte ---> <-- 8byte --->


/*=========================================*/
   if(NALLOC == 4), demand 2byte(alloc(2))
/*=========================================*/
(1) get 4block(== NALLOC) by morecore(), because memory pool is not exists.
(2) link free_list at add_FreeNode_to_FreeList()
     +------+
 +---|*base |
 |   +------+
 |    
 |   +------+------+------+------+ 
 +-->| *ptr | size |      |      |  # size is block count.(size == 4)
     +------+------+------+------+  # total size 32 btye
     |      |      |      |      |  
     +------+------+------+------+ 
     <-- 8byte ---> <-- 8byte --->

(3) allocate 2block at alloc().
    return address(B).

     +------+
 +---|*base |
 |   +------+
 |    
 |   +------+------+------+------+ 
 +-->| *ptr | size |      |      |  # size is block count.(size == 4)
     +------+------+------+------+  # total size 32 btye
     |      |      | (B)  |      |  
     +------+------+------+------+ 
     <-- 8byte ---> <-- 8byte --->


[MEMO]
        Low 00000000
        +------------+
        |            |
        +------------+
        |   text     |
        +------------+
        |   data     |
        +------------+
        |   bss      |
        +------------+
        |   Heap     |
        |            |
        +------------+
        |            |
        |            |
        +------------+
        |   stack    |
        |            |
        |            |
        +------------+
        High




/*================================================================*/

初回の alloc() コール時のシーケンス
main()
	(char *)alloc(2);

alloc()
	必要なブロック数の計算(1ブロック= 8 byte)で 2ブロック確保

	最初, フリーリストのポインタは base をポイント(a)するように設定され、
	次のフリーリストも base 自身をポイントするように設定される.
	同様に freep, prevp も base をポイントするように設定される.
	また保持しているサイズ情報も 0 と設定される.

	プールしておいた領域はないのでシステムにブロック単位(2ブロック)で
	メモリを要求する(morecore()をコール)


morecore()
	sbrk()により、ブロック数(2) * メモリ単位(8byte)だけヒープ領域を高アド
    レス方向へ拡張し、フリーリストの先頭ノードでsbrk()が返したアドレス(b)
    とブロック数を ポインタ名:up で保持する

	その後、afree((void *)(up + 1)) をコールしているが、これはヘッダ部分
    である ptr, size を除いた部分のアドレスとなる. (void *)(up + 1)は, 
    sbrk()が返したアドレス + 0x00000008 ということ
	

afree(void *)
	morecore() から br情報(アドレスと空きサイズ)へのポインタを受け取る

	『フリーリストの末尾が見付かるまで』検索する(詳細)
	--------------------------------------------------------------------------------
	[現在のフリーリストが sbrk()で確保出来た領域内]
	あるいは
	[次のフリーリスト(p->s.ptr)が sbrk()が返した値よりも前]
	となるフリーリストノードへのポインタを探して、次の条件に該当するか確認する。

	if(
	   (現在のフリーリストのアドレスが次のフリーリストのアドレスよりも高位になった)
	   &&
	   (
	     (sbrk()で取得した領域のアドレス > フリーリストのアドレス)
	     ||
	     (sbrk()で取得した領域のアドレス < フリーリストのアドレス)
	   )
	  )
	初回は, if(p >= p->s.ptr && bp > p) となり, フリーリストの末尾が見付かったので
	break する(初回はノードは一つで base をポイントしている)
	--------------------------------------------------------------------------------

	現在のフリーノード(base)の次のノードとして、
	sbrk() で取得した領域をポイントするよう設定する

alloc()
	今回はフリーノード(sbrk()+1 のアドレス 注意1)を返す

	リターンするアドレスから 0x00000008 進めたアドレスを設定し(freep = p;)、
	ヘッダ情報(s.ptr, s.size)を 省いた領域へのアドレスを返す(return (void *)(p+1);)

	注意1
		+1 しているのはヘッダ情報(s.ptr, s.size)へポイントしないようにするため
/*================================================================*/

*1:10数年ぶりに突然見ても内容が意味不明ですが

*2:一生懸命に学習していたことが思い出されます^_^;