@comment $OpenXM: OpenXM/src/asir-doc/int-parts/gc.texi,v 1.3 2012/12/27 05:50:01 noro Exp $
\JP @chapter メモリ管理
\EG @chapter Memory management

\JP @section メモリ管理機構
\EG @section Machinery for memory management

\BJP
@code{risa} におけるメモリ管理は, [Boehm,Weiser] によるものを用いている. 
このメモリ管理機構の特徴は, タグ付けを必要とせず, 自動的にガーベッジコレ
クション(GC) を行なうことである. 従ってユーザは必要な領域を取りっぱなし
にしてよい. 欠点としては, 一回の GC ですべてのガーベッジを回収できるとは
かぎらないことと, コンパクションを行なわないことであるが, 実用上十分な機
能を持つ. メモリ割り当て器に現れるマクロはすべてこのメモリ管理のもとでメ
モリの割り当てを行なっている. GC は, その時点における, スタック, レジス
タ, 静的領域からマーキングを始め, これにより到達できない領域をすべて回収
する. コンパイラの最適化により, 最初領域の先頭を指していたポインタが, 領
域の内部を指している場合にも, GC 正しくその領域が使用中と判断する.

注意すべきことは, 通常の @code{malloc()} により割り当てられた領域内はス
キャンされないことである. よって, @code{malloc()} は, その他の C のライ
ブラリの中から呼ばれる場合を除いて使用は避けなければならない. また, 一つ
の領域は, 複数の領域から参照されている可能性があるため, ユーザが開放する
ことは危険である. ただし, 作業用のバッファなど, 明らかに他からの参照がな
いものに関しては開放して構わない. メモリ管理関係の主な函数は次の通り.
\E
\BEG
\E

\BJP
@example
void GC_init()
初期化ルーチン. 起動時に実行する. 

void *GC_malloc(int n)
n bytes の領域を割り当てる. 領域は 0 で初期化される. 

void *GC_malloc_atomic(int n)
ポインタを含むことがないと保証される n bytes の領域を割り当てる.

GC_free(void *p)
p の指す領域を開放する. Risa では, ある領域がどこからどの位指されている
か一般には判断できないので, 通常はこの関数が使用されることはない. 
関数内で割り当てたバッファの開放などに用いることはできる. 
@end example
@noindent
通常は @code{GC_malloc()} を使用するが, 多倍長数用の領域など, 内部にポイ
ンタを含まないことが分かっている領域用に @code{GC_malloc_atomic()} が用
意されている. GC ルーチンは, @code{GC_malloc_atomic()} により割り当てら
れた領域の内部はスキャンしないので, GC の効率が良くなる. 

なお, version 7 以降の GC を用いている場合, これらの関数を直接呼び出して
はいけない. 必ず前後処理つきの関数 (@code{Risa_}をつけたもの)を呼び出すこと.
\E
\BEG
@example
void GC_init()

void *GC_malloc(int n)

void *GC_malloc_atomic(int n)

GC_free(void *p)
@end example
@noindent
\E

\JP @section Risa におけるメモリの使用
\EG @section Usage of memory in Risa

\BJP
Risa における各演算関数について共通の振舞いとして, 結果として生成される
object の内部で, 入力である object の各部への参照が行われている可能性
がある, ということがある. 

次の例は, 多項式の加算関数である. この中で, 例えば先頭の項の次数が異なる
場合には, 係数(へのポインタ)がそのまま結果にコピーされている. また, 
引数の一方の次数係数リストの末尾までたどった時に, 一方の次数係数リストが
残っている場合には, その残りがそのまま結果の次数係数リストにつながれる. 
\E
\BEG
\E

@example
#include "ca.h"

void addp(vl,p1,p2,pr)
VL vl;
P p1,p2,*pr;
@{
  DCP dc1,dc2,dcr0,dcr;
  V v1,v2;
  P t;

  if ( !p1 ) 
    *pr = p2;
  else if ( !p2 ) 
    *pr = p1;
  else if ( NUM(p1) )
    if ( NUM(p2) ) 
      addnum(vl,p1,p2,pr);
    else 
      addpq(p2,p1,pr);
  else if ( NUM(p2) ) 
    addpq(p1,p2,pr);
  else if ( ( v1 = VR(p1) ) ==  ( v2 = VR(p2) ) ) @{
    for ( dc1 = DC(p1), dc2 = DC(p2), dcr0 = 0; dc1 && dc2; )
      switch ( cmpq(DEG(dc1),DEG(dc2)) ) @{
        case 0: 
          addp(vl,COEF(dc1),COEF(dc2),&t);
          if ( t )  @{
            NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc1); COEF(dcr) = t;
          @}
          dc1 = NEXT(dc1); dc2 = NEXT(dc2); break;
        case 1:
          NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc1); COEF(dcr) = COEF(dc1);
          dc1 = NEXT(dc1); break;
        case -1:
          NEXTDC(dcr0,dcr); DEG(dcr) = DEG(dc2); COEF(dcr) = COEF(dc2);
          dc2 = NEXT(dc2); break;
      @}
    if ( !dcr0 ) 
      if ( dc1 )
        dcr0 = dc1;
      else if ( dc2 ) 
        dcr0 = dc2;
      else @{
        *pr = 0;
        return;
      @}
    else 
      if ( dc1 ) 
        NEXT(dcr) = dc1;
      else if ( dc2 ) 
        NEXT(dcr) = dc2;
      else 
        NEXT(dcr) = 0;
    MKP(v1,dcr0,*pr);
  @} else @{
    while ( v1 != VR(vl) && v2 != VR(vl) ) 
      vl = NEXT(vl);
    if ( v1 == VR(vl) ) 
      addptoc(vl,p1,p2,pr);
    else 
      addptoc(vl,p2,p1,pr);
  @}
@}
@end example

\BJP
このように, Risa の演算関数では, 一見不要になった中間的な結果でも, その
部分式が最終結果に用いられていることがあるため, 注意が必要である. 特に, 
配列を書き換える必要がある場合などには, 配列そのものを新しく生成して, 成
分をコピーしてから用いる必要がある.
\E
\BEG
\E

\JP @section GC version 7 に関する注意
\EG @section Notices on GC version 7

\BJP
version 6 までの Boehm GC においては, GC に入る前にすべての signal をマスクし,
出たあとマスクをクリアする, という操作を自動的に行っていた. 結果として, 
GC 中に受けた signal は保留され, GC 中に signal により大域脱出するという危険はなく,
また, GC 中の signal は GC 後に確実に処理することができた.

しかし, version 7 においてはこの仕組みが廃止された. この結果, 例えば, GC 中に SIGINT が
処理されてしまうと, メモリ管理のテーブルが破壊され, それ以降予期せぬ状態になる可能性
がある. 実際, 大域変数に保持されているデータが参照できなくなったり, 書き換わったりという
ことが起きた.

これに対する対処法として, @code{GC_malloc()} などの割り当て関数を直接呼び出さず, これらに対する
前後処理を行う関数を呼び出すようにした. 例えば @code{GC_malloc()} に対する関数は次のようになる.

@example
int in_gc, caught_intr;

void *Risa_GC_malloc(size_t d)
@{
  void *ret;

  in_gc = 1;
  ret = (void *)GC_malloc(d);
  in_gc = 0;
  if ( caught_intr ) @{ caught_intr = 0; int_handler(); @}
  if ( !ret )
    error("GC_malloc : failed to allocate memory");
  return ret;
@}
@end example
@code{in_gc} が 1 のとき, GC 中であること示す. 
また, @code{caught_intr} が 1 のとき, @code{in_gc}が1 の間に SIGINT を受けたことを表す.
この場合, SIGINT handler である @code{int_handler()}
では, 単に @code{caught_intr} を 1 にして何もせずに return する.
@example
extern int ox_int_received, critical_when_signal;
extern int in_gc, caught_intr;

void int_handler(int sig)
@{
  extern NODE PVSS;
  NODE t;


  if ( do_file ) @{
    ExitAsir();
  @}
  if ( critical_when_signal ) @{
    ox_int_received = 1;
    return;
  @}
  if ( in_gc ) @{
    caught_intr = 1;
    return;
  @}
  ...
@end example
GC 中に SIGINT があった場合, @code{in_gc}が 0 となったあとに,
@code{caught_intr} を0 にして SIGINT 処理関数 @code{int_handler()} を呼
び出す. このようにすることで, version 6 と同様に, GC 内で受けた SIGINT
の処理の保留および GC後の処理を行うことができる.

なお, OX server として動作中には SIGINT の他に
SIGUSR1 を受け取る可能性がある. この場合,
中断できない OX 通信関数の前後で@code{begin_critical()},
@code{end_critical()}が実行され, @code{ciritical_when_signal},
@code{ox_usr1_sent} によりSIGUSR1 処理の保留が実現されている.

@example
int ox_usr1_sent, ox_int_received, critical_when_signal;
void ox_usr1_handler(int sig)
@{
  NODE t;

  signal(SIGUSR1,ox_usr1_handler);
  if ( critical_when_signal ) @{
    fprintf(stderr,"usr1 : critical\n");
    ox_usr1_sent = 1;
  @} else @{
    ox_flushing = 1;
    ...
    ox_resetenv("usr1 : return to toplevel by SIGUSR1");
  @}
@}

void begin_critical() @{
  critical_when_signal = 1;
@}

void end_critical() @{
  critical_when_signal = 0;
  if ( ox_usr1_sent ) @{
    ox_usr1_sent = 0;
  ox_usr1_handler(SIGUSR1);
  @}
  if ( ox_int_received ) @{
    ox_int_received = 0; int_handler(SIGINT);
  @}
@}
@end example
@noindent
この場合, OX server 内での GC 中に受け取った SIGINT をどうするかという
問題が生ずる. これについては, OX server 内での GC 中に受け取った
SIGINT は @code{ox_int_received} に記録するだけとする. 
(@code{int_handler()} 内で, @code{in_gc} より先に
@code{critical_when_signal} を見ていることに注意.)
結果として, 対応
する @code{int_handler()} の処理は, 次に @code{end_critical()} が呼ばれたと
きについでに実行されることになり, 即応性がなくなるが, SIGINT は 手動で
のみ送られるので, この点は気にする必要はない.  

前後処理つきのメモリ割り当て関数 @samp{parse/gc_risa.c} で定義されている.
@example
void *Risa_GC_malloc(size_t d)
void *Risa_GC_malloc_atomic(size_t d)
void *GC_malloc_atomic(int n)
void *Risa_GC_malloc_atomic_ignore_off_page(size_t d)
void *Risa_GC_realloc(void *p,size_t d)
void Risa_GC_free(void *p)
@end example
それぞれ, @code{Risa_} がない関数に対応している. 
また, @samp{include/ca.h}内のメモリ割り当て関連マクロも, すべて
これらの前後処理つき関数を呼ぶように変更した.
\E
\BEG
\E