CのLimbo用モジュールの開発（パート2）

パート1

内容

• ヒープ
  
  
  • 私の記憶には何が...
  • ガベージコレクションについて少し
  • ヒープ内のオブジェクト型
  • ヒープに複雑な構造を作成する
• 配列
  
  
  • adtおよびref adt
• Gc
  
  
  • ヒープ内のオブジェクトをGCから切断する

ヒープ

Limboコードが動作するCの複雑な構造を正しく作成および破棄するには、それらがメモリにどのように格納されているかを想像する必要があります。 Infernoでのヒープの編成方法。 ヒープを操作するための以下のすべての関数はlibinterp/heap.c



で説明されており、構造体はinclude/interp.h



で説明されています。

私の記憶には何が...

ヒープ内のn



バイトを選択して解放するには、次の操作を行う必要があります。

 Heap *h; uchar *data; h = nheap(256); data = H2D(uchar*, h); ... //   data  256  destroy(data);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

物理的には、メモリには256 +ヒープヘッダーバイトのサイズが割り当てられ、先頭にはヘッダーがあり、ユーザーデータがあります。 ヘッダーは、 Heap



構造で説明されています。さらに、ヒープヘッダーへのポインターをデータへのポインターに変換するための2つのマクロがあります（さらに、便宜上、型キャストですぐに） H2D()



およびその逆D2H()



。 destroy()



関数は、 D2H()



を使用して、長さが不明なユーザーデータの先頭へのポインターの代わりにヒープヘッダーを取得し、解放する必要があるバイト数を調べます。

 struct Heap { int color; /* Allocation color */ ulong ref; Type* t; ulong hprof; /* heap profiling */ }; #define H2D(t, x) ((t)(((uchar*)(x))+sizeof(Heap))) #define D2H(x) ((Heap*)(((uchar*)(x))-sizeof(Heap)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ガベージコレクションについて少し

ヒープヘッダーには何がありますか？ hprof



については何もhprof



しませんが、ヒーププロファイリングは理解できませんでしたが、残りのフィールドは非常に重要です。



まず、Infernoのガベージコレクターについて少し説明します。 2つの戦略が同時に使用されます。ほとんどの構造に十分な単純な参照カウンターと、循環リンクを持つ構造を選択するための3色マーキングのテーマのバリエーションです。 したがって、 ref



は参照カウンタであり、3色マーキングにcolor



使用されます。 nheap()



または別の同様の関数が新しいオブジェクトをヒープに割り当てると、そのヒープヘッダーのref



値は1に設定されますnheap()



が呼び出されると、 ref



の値が1減少します。メモリ。



したがって、 nheap()



（または他の同様の関数）によって返される値を1つの変数に格納している間、このオブジェクトへの参照は1つだけで、そのref



は1です。このリンクを別の変数にコピーするとすぐに、参照カウンターを増やす必要がありますさらに 、3色アルゴリズムに通知します。 これは次のように行われます（ Setmark()



もマクロですが、これに対処するには、現在必要とされていない3色アルゴリズムの動作を理解する必要があります）。

 Heap *h; uchar *data, *data2; data = H2D(uchar*, nheap(256)); data2 = data; h = D2H(data2); h->ref++; Setmark(h); //   h->color destroy(data); //       destroy(data2); //     
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

もちろん、ヒープ内のオブジェクトを選択し、 *f->ret



書き込むことでユーザーに返した場合、 ref



とcolor



追加する必要はありません。関数が終了すると、関数のローカル変数からリンクが削除されます。ユーザーは、関数によって返された値を保存した変数に、このオブジェクトへのリンクを持っています。 リンクのコピーではなく、移動がありました。



リンクの移動に関連する暗黙のニュアンスが1つあります。 前の例では、戻り値を使用して、新しく作成されたばかりのリンクが移動され、そこに追加の必要はありません。 ただし、リンクを既存の変数/構造から別の既存の変数/構造に移動した場合は、 Setmark()



呼び出して3色アルゴリズムに通知する必要があります（これはこのアルゴリズムの機能にも関連しており、以下で説明します）：

 dst->data = src->data; src->data = H; Setmark(D2H(dst->data));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ヒープ内のオブジェクト型

上記のnheap()



例は、実際のコードではほとんど使用されません。 Limboには、このデータ型はありません：nバイト。 したがって、 nheap()



選択したオブジェクトがLimboから取得したり、Limboに戻ったりすることはありません。 また、Cモジュールの内部ニーズにメモリを割り当てるために、原則として、 free()



で十分な通常のmalloc()



があります。



Limboが操作できるヒープ内のすべてのオブジェクトは、 Type



構造体で記述された何らかのタイプでなければなりません。 これにより、オブジェクト内のすべてのリンクの自動検出の問題を解決できます。

• このオブジェクトにメモリを割り当てます（その中のすべてのポインタをH
  
  
  
  aka nil
  
  
  
  に設定します）;
• destroy()
  
  
  
  実行destroy()
  
  
  
  オブジェクトをメモリから削除するときに、それがref
  
  
  
  するすべてのオブジェクトのref
  
  
  
  を削除または削減します）。
• ガベージコレクターの作業（メモリ内のすべてのオブジェクトをトラバースするときに、他の複雑なオブジェクト内で参照されるオブジェクトを考慮するため）。

 struct Type { int ref; void (*free)(Heap*, int); void (*mark)(Type*, void*); int size; int np; void* destroy; void* initialize; uchar map[STRUCTALIGN]; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

標準タイプ（非参照フィールド、またはdestroy()



String*



destroy()



を介して解放できる通常のヒープオブジェクトへのリンクを持つフィールドdestroy()



String*



やArray*



）を含むadt / tuple / structureの場合、 np



フィールドとmap



フィールドが使用されます。 map



フィールドには、ビットマスク、adt / tuple / structureの4バイトごとに1ビット（最初のバイトの最上位ビットから始まる）が含まれます。セットビットは、対応する4バイトがヒープオブジェクトへのポインターであることを意味します。 （ np



フィールドには、 map



フィールドの長さがバイト単位で含まれています。）



一部のデータ型は、メモリをまったく標準的な方法では使用しません。 典型的な例はString



とArray



。最初のString



にはchar*



フィールドが含まれており、 free()



解放する必要があります。 2番目はスライスにすることができ、その中に「親」配列へのリンクを含めることができます。 Type



構造体を使用すると、メモリの割り当て/初期化時にdestroy()



およびガベージコレクターから呼び出されるこれらの型に対して、 free



、 mark



、 destroy



、およびinitialize



非標準ハンドラー関数を指定できます。



size



フィールドには、このタイプの構造体のサイズが含まれています（この構造体にメモリを割り当てるときに、すべて同じようにタイプを指定する必要があるため、タイプ内の構造体のサイズを保存すると、毎回構造体のサイズを追加せずに、タイプのみを指定できるようになります）



ref



フィールドは、このタイプのヒープ内のオブジェクトの現在の数を格納するために使用されます。 実際、型のリストは、標準のstring



、 array of



などに限定されません。 -オンザフライで記述されたタプルは、 Type



構造を使用して独自の説明が必要な別個のタイプです。 いくつかのタイプは、その場でLimboによって作成され、同じヒープに格納され、このタイプのすべてのオブジェクトが削除されたらすぐにメモリから削除する必要があることがわかります。 したがって、あるタイプの新しいオブジェクトを作成する場合、このタイプのref



を増やす必要があります。このオブジェクトを削除すると、 destroy()



はこのオブジェクトのタイプと同じ方法でref



を自動的に減らします（ ref



が0になった場合はメモリから削除します）。



標準型のType



値は、 ref



を1に設定して静的に宣言され（したがって、 ref



が1未満になることはなく、メモリから削除されることもありません）、 libinterp/head.c



冒頭で説明されていlibinterp/head.c



。

 Type Tbyte = { 1, 0, 0, 1 }; Type Tword = { 1, 0, 0, sizeof(WORD) }; Type Tptr = { 1, 0, markheap, sizeof(WORD*), 1, 0, 0, { 0x80 } }; Type Tarray = { 1, freearray, markarray, sizeof(Array) }; Type Tstring = { 1, freestring, noptrs, sizeof(String) }; ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ヒープに複雑な構造を作成する

独自のadt / tuples /構造体の型は、場合によってはlibinterp/runt.h



によって決定できます（ Type.size



構造体のサイズとType.map



とType.np



ポインターフィールドのビットマスクを計算することによって）。自分で（たとえば、C関数からタプルを作成して返すため）。 これらは通常、 dtype()



関数を使用してモジュールを初期化するときに作成されます（たとえば、Exampleモジュールで戻ります）。 そして、メモリはnheap(n_bytes)



ではなく、 heap(&Tsometype)



を介して割り当てられ、初期化されます。

• module/example.m
  
  
  
  
  
  

   Example: module { ... MyData: adt{ i: int; s: string; new: fn(i: int): ref MyData; }; };
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• libinterp/runt.h
  
  
  
  （ module/example.m
  
  
  
  から自動的に生成されmodule/example.m
  
  
  
  ）
  
  

   typedef struct Example_MyData Example_MyData; struct Example_MyData { WORD i; String* s; }; #define Example_MyData_size 8 #define Example_MyData_map {0x40,} void MyData_new(void*); typedef struct F_MyData_new F_MyData_new; struct F_MyData_new { WORD regs[NREG-1]; Example_MyData** ret; uchar temps[12]; WORD i; };
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

値Example_MyData_map 0x40は、ビットマスク010000 ...、つまり 構造の最初の4バイトはポインター（WORD）ではなく、2番目はポインター（String *）です。

• libinterp/example.c
  
  
  
  
  
  

   static Type* TMyData; static uchar MyData_map[] = Example_MyData_map; void examplemodinit(void) { ... TMyData = dtype(freeheap, Example_MyData_size, MyData_map, sizeof(MyData_map)); } void MyData_new(void *fp) { F_MyData_new *f; int i; Example_MyData* mydata; f = fp; i = f->i; mydata = H2D(Example_MyData*, heap(TMyData)); mydata->i = i; destroy(*f->ret); *f->ret = mydata; }
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• testexample.b
  
  
  
  
  
  

   ... example: Example; MyData: import example; ... init(nil: ref Draw->Context, nil: list of string) { ... mydata := MyData.new(5); sys->print("i = %d, s = %q\n", mydata.i, mydata.s); } ; testexample ... i = 5, s = '' ;
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

配列

配列の操作を検討してください。 メモリでは、配列は次のように配置されます：ヒープヘッダー、配列ヘッダー、配列要素。 したがって、配列にメモリを割り当てるには、要素のサイズと数を知る必要があります。 これらの要素を初期化し（ H



に設定する必要があるリンクが突然あります）、後でそれらをメモリから正しく削除するには、これらの要素のタイプを知る必要があります（サイズを指定する必要はなく、タイプ内で既に示されています）。

 struct Array { WORD len; Type* t; Array* root; uchar* data; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、 len



は配列のサイズ、 t



は要素のタイプ、 root



親配列へroot



ポインター（この配列がスライスの場合）、 data



配列の最初の要素へのポインターです（配列が独立している場合は配列構造の後の次のバイト、または要素間のスライスの最初の要素のアドレス）親配列）。



別の配列のスライスを作成しない場合、 Array



構造自体よりも多くのメモリを割り当てる必要があります（それに応じて、 Tarray.size



で指定されたものよりもTarray.size



）。 したがって、以前に使用したheap()



関数を介して配列にメモリを割り当てることはできません。 幸いなことに、これには便利なheaparray()



関数があります。 array[16] of byte



を割り当てる例：

 Array *arr; arr = H2D(Array*, heaparray(&Tbyte, 16));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

配列スライスを返す関数の例： http : //code.google.com/p/inferno-cjson/source/browse/libinterp/cjson.c#59

adtおよびref adt

LidboとCには、adtとref adtの処理方法に暗黙的な違いがあります。 Limboレベルで、それらの操作が（ほぼ）同じように見える場合：

 a := array[10] of MyData; b := array[10] of ref MyData; for(i := 0; i < len b; i++) b[i] = ref MyData; a[0].i = b[0].i;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cレベルでは、これらは完全に異なる配列です。

 Array *a, *b; int i; Example_MyData* adata; Example_MyData** bdata; a = H2D(Array*, heaparray(TMyData, 10)); adata = (Example_MyData*)a->data; b = H2D(Array*, heaparray(&Tptr, 10)); bdata = (Example_MyData**)b->data; for(i = 0; i < b->len; i++) bdata[i] = H2D(Example_MyData*, heap(TMyData)); adata[0].i = bdata[0]->i;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Gc

3色アルゴリズムの一般的な説明は、 Wikipediaにあります。 Infernoでは、これら3つの「色」はmutator



、 marker



sweeper



と呼ばれます。



新しいオブジェクトはh->color=mutator



設定されます。



gcサイクルが完了するたびに、 mutator



、 marker



、およびsweeper



変数の値が円で変化し、ヒープ内のすべてのオブジェクトのh->color



値が変化します。

 mutator -> marker marker -> sweeper sweeper -> mutator //    ..  sweeper  
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

操作中にgc h->color==sweeper



場合、 h



はメモリから削除されます。



Setmark()



とは何で、なぜそれが必要なのか。

 #define Setmark(h) if((h)->color!=mutator) { (h)->color = propagator; nprop=1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに、ガベージコレクターは非常に長い時間動作し、他のすべてがこの時点で停止するため、Infernoではガベージコレクターは細かく動作します-一時停止するオブジェクトの一部をバイパスし、他のコードを機能させ、前回停止した場所から続行します。 ただし、このアルゴリズムでは、メモリ内のすべてのオブジェクトを1回のパスでアトミックにチェックする必要があります。そうでない場合、未使用のオブジェクトを一意に識別することはできません。 そのため、Infernoガベージコレクターは、GCの起動時に潜在的に興味深いオブジェクトが変更されたかどうかを判断できるメカニズムを実装しています。



このメカニズムはSetmark()



呼び出しです。 彼がnprop



たnprop



フラグは、必要に応じて、GCに対して、ヒープ内のオブジェクトトラバーサルの現在のサイクルの終わりに、未使用のオブジェクトを削除することは不可能であることを示しますが、サイクルを最初から繰り返す必要があります。



値h->color==propagator



は、次にgcを実行するときに、このオブジェクトを表示する必要があることを意味します。 オブジェクトを表示するとき、 h->color



mutator



設定されます。 （同じpropagator



値は、新しいGCサイクルの開始時に「ルート」オブジェクトに設定されますが、これはこのコンテキストでは重要ではありません。）

ヒープ内のオブジェクトをGCから切断する

GCはref



値に関係なく、「ルート」オブジェクト（おそらく動作中のDisスレッド、ロードされたモジュールなどを含む）から参照されていないすべてのオブジェクトをメモリから削除するため、問題が発生します：ヒープオブジェクトへのリンクを外部に保存する方法たとえば、Cモジュールのグローバル変数にスレッドを配置し、GCがそれを強制終了しないようにしますか？ これを行うには、 poolimmutable()



を使用してこのヒープオブジェクトを制御してはならないことをGCに通知する必要がありpoolmutable()



オブジェクトをGCに接続するためにpoolmutable()



があり、これらの関数はすべてemu/port/alloc.c



）：

• libinterp/example.c
  
  
  
  
  
  

   ... static Array* EmptyArray; void examplemodinit(void) { ... EmptyArray = H2D(Array*, heaparray(&Tbyte, 0)); poolimmutable(D2H(EmptyArray)); }