Skip to content

Instantly share code, notes, and snippets.

@S-Shimotori

S-Shimotori/GettingStarted.md

Last active September 13, 2017 07:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save S-Shimotori/2b073bcacaebcb5c51a19b26c989e676 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save S-Shimotori/2b073bcacaebcb5c51a19b26c989e676 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
GettingStarted.md

Regions

プログラムをクラッシュさせたりセキュリティを侵害する別の潜在的な原因は，ダングリングポインタを参照解除することで，これは割り当てが解除されたストレージへのポインタのことである．このエラーはすぐに現れない可能性があるので，油断のならないバグである．例えば，次のCのコードを見てみよう:

struct Point {int x; int y;};

struct Point *newPoint(int x,int y) {
  struct Point result = {x,y};
  return &result;
}

void foo(struct Point *p) {
  p->y = 1234;
  return;
}

void bar() {
  struct Point *p = newPoint(1,2);
  foo(p);
}

このコードには明らかなバグがある．関数 newPoint は，ローカルで定義した変数( result )への記憶領域がたとえ関数の終了時に割り当て解除されていても，この変数へのポインタを返す．この記憶領域は，微妙なバグやセキュリティ問題につながるような再利用をされる可能性がある(例えば後の手続きが呼び出す)．例えば，上のコードでは bar が newPoint を呼び出した後，そのポインタの記憶領域を foo の呼び出しの起動レコードの情報を格納するために再利用する．これにはポインタ p のコピーと foo の戻り値のアドレスが含まれる．したがって， p->y は実際には foo の戻り値のアドレスを指しているかもしれない．その場所に整数 1234 を代入すると， foo がメモリ内の任意のコードの塊に"戻る"ことになる．それにもかかわらず，Cの型チェッカーはこのコードを容易に認めてしまう．

Cycloneでは，上記のような問題を避けるために，型チェッカーによってこのコードは拒否される．このコードが拒否されるのは，Cycloneコンパイラがオブジェクトの存続期間を追跡し，オブジェクトがまだ割り当て解除されていないときにのみオブジェクトへのポインタが参照解除できることが確実になっているからである．

Cycloneは各オブジェクトに対し，オブジェクトが割り当てられているメモリ領域に対応するシンボリック領域を割り当てることでこれを実現する．さらに，全てのポインタについて，Cycloneはそのポインタがどの領域を指しているのかを追跡する．指し示される領域はポインタ型の一部として記述できるが，通常は領域を省略することができる–コンパイラは賢いので多くの場合自動的に領域を検出する．

例えば，上記コード中の変数 result は関数 newPoint の呼び出しに対応する領域内に存在する． `newPoint のように，この領域の名前をバッククォートを用いて明示的に記述する． result は領域 `newPoint に存在するので，式 &result は領域 `newPoint へのポインタである．明示的な領域を持つ &result の完全なCyclone型は struct Point * @region(`newPoint) である．

起動レコードのようなレキシカルブロックに対応する領域は，それがランタイムスタックの一部に対応することからスタック領域と呼ばれる．制御フローがブロックを脱出すると，そのブロックの記憶領域(つまりスタック領域)は割り当て解除される．Cycloneは，各制御フローのポイントで割り当てられた領域と割り当て解除された領域の集合を追跡し，割り当てられた領域へのポインタを参照解除するだけであることを確かにする．例えば，次の悪いCycloneコードの断片を見てみよう:

int f() {
   int x = 0;
   int *@region(`f) y = &x;
   L:{ int a = 0;
       y = &a;
     }
   return *y;
}

上記の関数 f では，変数 x と y は関数の最も外側のブロックで宣言されていて，関数のブロックのデフォルトの領域名が `<function name> であることから，領域 `f 内に存在する．これらの変数の記憶領域は関数の呼び出しと同じ長さだけ存続する． y が x のポインタであることから， y の型は int *@region(`f) であり， y が領域 `f を指していることに注意する．

変数 a は L トラベルづけされた内側のブロックで宣言されているため，領域 `f 内には存在しない． 内側のブロック L への記憶領域は，この関数自身が復帰する前にブロックの終了時に割り当て解放される．正確に言えば， a の記憶領域はコードの6行目で割り当て解放される．したがって，7行目のように残りの計算でこの記憶領域にアクセスしようとするとエラーになる．

Cycloneは式 &a に int *@region(`L) 型を与えるのでそのエラーを検出する．これは，この値が領域 `L へのポインタであることを意味する．そのため， y は `L ではなく領域 `f へのポインタを保持することを期待されるので， y = &a の割り当ては型チェックに失敗する．Cと比較すると，ポインタの型は全領域の代わりに1つの領域を示す制約がある．

Region Inference

全てのポインタ型に @region 修飾子を記述しなければならないとすると，コードを書くのが不愉快になるだろう．幸い，Cycloneには書くべき領域アノテーションを減らす様々なメカニズムが用意されている．

まず，他の修飾子の後ろに領域名を書きさえすれば， @region 修飾子キーワードを省略し単純に領域名(例えば `r )を書くことができる．例えば， int *@notnull @region(`r) と書く代わりに，単純に int @`r と書くことができる．明確にするために，明示的に @region 修飾子を用いることがあるが，ライブラリやその他のサンプルプログラムで省略形が頻繁に使われているのがわかるだろう．

さらに，Cycloneはプログラマが情報を与えずともポインタの領域を把握することがよくある．これを領域推論と呼ぶ．たとえば，領域アノテーションやブロックへのラベル付けなしに関数 f を書き換えることができる．

int f() {
   int x = 0;
   int *y = &x;
   { int a = 0;
     y = &a;
   }
   return *y;
}

Cycloneは y が領域 `f のポインタだとわかり， &a は異なる(今や無名の)領域へのポインタなので，このコードは拒否される．

以下に示すように，何かが特定領域を指し示しているか，あるいは2つが同じ領域を指し示していることを型チェッカーに確信させるために，コードに明示的な領域アノテーションを挿入する必要性が生じる場合がある．さらに，ドキュメンテーションの目的で領域アノテーションを追加したり型エラーの不透明感をなくしたりするのはしばしば便利である．領域推論に関する詳細な情報はType Inferenceを見よ．

効果的なCycloneプログラマであるために，領域についてもう少し詳しく理解する必要がある: ヒープ領域，LIFO領域，領域ポリモーフィズム，関数のパラメータに対するデフォルト領域アノテーション．次のセクションではこれらのトピックの概要を説明する．ユニーク及び参照カウント領域を含む追加の領域ベースの構文や，動的領域に関する情報はMemory Management Via Regionsにある．

ヒープ領域

トップレベル変数や new や malloc で割り当てされたデータのための記憶領域の全てを保持するヒープ用の特別な領域があり， `H と書く．たとえば，トップレベルに以下の宣言を書くとする:

struct Point p = {0,1};
struct Point *ptr = &p;

すると，Cycloneは ptr がヒープ領域を指していると判断する．これを明示的に反映させるために，望むなら ptr の型に領域を追加することができる．

struct Point p = {0,1};
struct Point *@region(`H) ptr = &p;

別の例として，次の関数では Point をヒープ割り当てし，それを呼び出し元に返す．明示的にするためにここに領域を追加する:

struct Point *@region(`H) good_newPoint(int x,int y) {
  struct Point *@region(`H) p =
    malloc(sizeof(struct Point));
  p->x = x;
  p->y = y;
  return p;
}

あるいは，結果をヒープ割り当てし初期化するために new が使える:

struct Point *@region(`H) good_newPoint(int x,int y) {
  return new Point{x,y};
}

LIFO領域

スタック上の記憶領域はブロックの出入り時に暗黙的に割り当てられリサイクルされる．ヒープ中の記憶領域は new または malloc により明示的に割り当てられるが，ヒープ中のオブジェクトを明示的に解放するためのサポートはCycloneにはない．その理由は，Cycloneは一般的にヒープ内の個々のオブジェクトの生存期間を正確に追跡できないため，ヒープへのポインタを参照解除して問題が発生するかどうかを確かめられないからである．代わりに，特にしていない限り，ヒープ内に割り当てられたデータを再利用するために控えめなガベージコレクタが用いられる．プログラマが手動で安全に解放できるユニークポインタや参照カウントポインタもサポートしているが，これらの機能の説明はMemory Management Via Regionsで行う.

メモリの再利用のためにガベージコレクタを使用することは多くのアプリケーションにおいて適切である．例えば，Cycloneコンパイラはヒープ割り当てされたデータを使用し，プログラムをコンパイルするときに作成する多くのオブジェクトをリサイクルするべくコレクタに依存する．しかしガベージコレクタはプログラムの一時停止を引き起こす可能性があり，汎用メモリ管理としてはアプリケーションに合わせたルーチンほどには時間や空間効率が悪い可能性がある，

こういったアプリケーションに対処するため，CycloneはLIFO領域をサポートしている．LIFO領域は，その存続期間がレキシカルスコープ(last-in-first-outあるいはLIFO)だが動的割り当てを可能にしている点でスタック領域に似ている．次の構文を考えてみよう:

{ region<`r> h;
   ...
}

これは領域ハンドル h とともに新しい領域 `r を宣言している．ハンドルは領域 `r 内のオブジェクトに動的割り当てをするために用いられる．スタック領域と同様，領域に対する記憶領域の全ては閉じ括弧の時点で割り当て解除される．スタック領域と異なるのは，LIFO領域に割り当てたオブジェクトの数(とサイズ)がコンパイル時に固定されないことである．この点においてLIFO領域はヒープによく似ている． h がその領域のハンドルであるとき，拡張可能な領域内のオブジェクトへの割り当てには rnew(h) や rmalloc(h, ...) を使うことができる．

例えば，次のコードは整数 n を受け取って新しい動的領域を作り， rnew を用いてその領域内にサイズnの配列を割り当てる．

int k(int n) {
  int result;
  { region<`r> h;
    int ?arr = rnew(h) {for i < n : i};
    result = process(h, arr);
  }
  return result;
}

次に，これは処理関数に対して領域のハンドルと配列を渡す．処理関数は与えられたハンドルを使って領域 `r 内にオブジェクトを自由に割り当てることに注意する．配列を処理したのち，配列を割り当て解放する領域を終了し，計算結果を返す．

LIFO領域はこのような状況で特に有用である: つまり，関数呼び出しの結果を呼び出し元の中に割り当てたいが，必要なスペースがどのくらいかわからないときである．もう1つの例として，Cycloneライブラリの関数 rprintf の使用例を考えてみよう．

  { region<`r> h;
    char ?`H s = get_username();
    char ?`r z = rprintf(h,"hello %s\n");
    emit(z);
  }

領域を割り当ててユーザ名を取得した後，領域ハンドルはライブラリ関数 rprintf に渡される． rprintf は sprintf と似ているが，固定サイズのバッファには出力しない．代わりに，領域内にバッファを割り当て，そのバッファ内にフォーマットされた出力を置き，そのバッファへのポインタを返す．上の例では， z はユーザ名の後に"hello"が続く文字列へのポインタで初期化され， z は h の領域に割り当てられる． sprintf と異なり，バッファオーバーフローのリスクはなく， snprintf と異なり，小さすぎるバッファを渡されるリスクもない．さらに，割り当てられたバッファはスタック割り当てされたバッファと同様，その領域がスコープ外になった時に解放される．

最後に，ヒープが無制限のスコープを持つLIFO領域であると考えるのが役立つかもしれないことに注目する．実際には，グローバル変数 Core::heap_region をヒープのハンドルとして使うことができ， new と malloc(...) はそれぞれ rnew(Core::heap_region) と rmalloc(Core::heap_region, ...) の省略形である．

Region Polymorphism

理解すべきもう1つの重要な概念は領域ポリモーフィズムである．これは，Cycloneにおいて，特定のオブジェクトが存続している限りそのオブジェクトがどの特定領域に存在するか気にしない関数を書けるということを示す素晴らしい方法である．例えば，この章の最初の foo 関数は領域ポリモーフィズム関数である．これを明確にするために，上の foo 関数を書き直して引数の領域を明確にしよう:

void foo(struct Point *@region(`r) p) {
  p->y = 1234;
  return;
}

この関数は領域変数 r によってパラメータ化され，領域 r に存在する Point へのポインタを受け入れる． foo が呼ばれると， ヒープ H を含む任意の領域か，関数に対するローカル領域で r が _instantiated_ される．例えば次のように書くことができる．

void g() {
  struct Point p = {0,1};
  struct Point *@region(`g) ptr1 = &p;
  struct Point *@region(`H) ptr2 = new Point{2,3};
  foo(ptr1);
  foo(ptr2);
}

foo の最初の呼び出しでは領域 g へのポインタを渡し， foo の2回目の呼び出しではヒープへのポインタを渡していることに注意する．最初の呼び出しでは， r は g で，2回目の呼び出しでは H で暗黙的にインスタンス化される．

領域ポリモーフィズムは．以下で説明するように，Cycloneが一般的にサポートしているパラメータポリモーフィズムの特定の形式である．

Default Region Annotations

Cyclone automatically assigns region variables to function arguments that have pointer type, so you rarely have to write them. For instance, foo can be written simply as:

void foo(struct Point * p) {
  p->y = 1234;
  return;
}

As another example, if you write the following:

void h(struct Point * p1, struct Point * p2) {
  p1->x += p2->x;
  p2->x += p2->y;
}

then Cyclone fills in the region parameters for you by assuming that the points p1 and p2 can live in any two regions, and so it generates assigns fresh names for the region variables of p1 and p2 , e.g. something like r1 and r2 . To make this explicit, we would write:

void h(struct Point *@region(`r1) p1,
       struct Point *@region(`r2) p2) {
  p1->x += p2->x;
  p2->x += p2->y;
}

Now we can call h with pointers into any two regions, or even two pointers into the same region. This is because the code is type-correct for all regions r1 and r2 .

Occasionally, you will have to put region parameters in explicitly. This happens when you need to assert that two pointers point into the same region. Consider for instance the following function:

void j(struct Point * p1, struct Point * p2) {
  p1 = p2;
}

Cyclone will reject the code because it assumes that in general, p1 and p2 might point into different regions. The error is roughly the following:

foo.cyc:2: type mismatch:
     struct Point *`GR0 != struct Point *`GR1
  `GR1 and `GR0 are not compatible.
     (variable types are not the same)

Cyclone has picked the name GR1 for p1 ’s region, and GR2 for p2 ’s region. That is, Cyclone fills in the missing regions as follows:

void j(struct Point *@region(`GR1) p1,
       struct Point *@region(`GR2) p2) {
  p1 = p2;
}

Now it is clear that the assignment does not type-check because the types of p1 and p2 differ. In other words, `GR1 and `GR2 might be instantiated with different regions, in which case the code would be incorrect. For example, we could call j as follows:

void g() {
  struct Point p = {0,1};
  struct Point *@region(`g) ptr1 = &p;
  struct Point *@region(`H) ptr2 = new Point{2,3};
  j(ptr2,ptr1);
}

Doing this would effectively allow us to assign ptr1 to ptr2 , which is unsafe in general, since the heap outlives the stack region for g .

But you can require that j ’s regions be instantiated with the same region by explicitly specifying the same explicit region variable for each pointer. Thus, the following code does type-check:

void j(struct Point *@region(`r) p1,
       struct Point *@region(`r) p2) {
  p1 = p2;
}

This would prevent the situation in function g above, since the arguments passed to j must be allocated in the same region.

So, Cyclone assumes that each pointer argument to a function is in a (potentially) different region unless you specify otherwise. The reason we chose this as the default is that (a) it is often the right choice for code, (b) it is the most general type in the sense that if it does work out, clients will have the most lattitude in passing arguments from different regions or the same region to the function.

What region variable is chosen for return-types that mention pointers? Here, there is no good answer because the region of the result of a function cannot be easily determined without looking at the body of the function, which defeats separate compilation of function definitions from their prototypes. Therefore, we have arbitrarily chosen the heap as the default region for function results. Consequently, the following code type-checks:

struct Point * good_newPoint(int x,int y) {
  return new Point{x,y};
}

This is because the new operator returns a pointer to the heap, and the default region for the return type is the heap.

This also explains why the newPoint function (page [??][13]) for allocating a new Point does not type-check:

struct Point *newPoint(int x,int y) {
  struct Point result = {x,y};
  return &result;
}

The expression &result is a pointer into region `newPoint but the result type of the function must be a pointer into the heap (region `H ).

If you want to return a pointer that is not in the heap region, then you need to put the region in explicitly. For instance, the following code:

int * id(int *x) {
  return x;
}

will not type-check. To see why, let us rewrite the code with the default region annotations filled in. The argument is assumed to be in a region `GR1 , and the result is assumed to be in the heap, so the fully elaborated code is:

int *@region(`H) id(int *@region(`GR1) x) {
  return x;
}

Now the type-error is manifest. To fix the code, we must put in explicit regions to connect the argument type with the result type. For instance, we might write:

int *@region(`r) id(int *@region(`r) x) {
  return x;
}

or using the abbreviation:

int *`r id(int *`r x) {
  return x;
}

Region Summary

要約すると，Cycloneの各ポインタは指定された領域を指しており，この領域はポインタの型に反映される．Cycloneでは，割り当て解除された領域を指すポインタを参照解除することはできない．関数内で宣言されたレキシカルブロックはある領域(スタック領域)の型に対応していて，ブロック内で宣言された変数は領域内の記憶領域に割り当てられる．その記憶領域はブロック終了時に割り当て解除される．LIFO領域は，領域ハンドルを用いて領域内に動的なオブジェクト数を割り当てられるという点を除いて同様である．スタック領域もLIFO領域も構造化された存続期間を持つ．最後に，ヒープ領域 `H はデッドオブジェクトがガベージコレクションされる特別な領域である．

領域ポリモーフィズムと領域推論により，型にある多くの領域アノテーションを省略することができる．デフォルトでは，関数内のアノテーションのないポインタ引数は別の領域に存在し，アノテーションのない結果のポインタはヒープにあるとCycloneはみなす．これらの前提は完全ではないが，プログラマは明示的な領域アノテーションを与えることでその前提を修正することができ，これによりCycloneファイルを個別にコンパイルすることができる．

Cycloneの領域ベースの型システムはおそらくこの言語の複雑な側面である．大部分は，メモリ管理が難しく扱いにくい行いだからである．私たちはオブジェクトの存続期間の制御についてプログラマを犠牲にせず，(常に)ガベージコレクションを頼らずに，スタック割り当てと領域ポリモーフィズム関数を使いやすくした．より高度な機能として，オブジェクトの存続期間をより細かく制御することもできるが，ユニーク領域や参照カウント領域によりプログラマの多くの作業を犠牲にしている．LIFO領域のようにランタイム割り当てをサポートしている動的領域を作成するためにこれらを使用できるが，この領域は動的スコープを持つ．これらや一般的な領域に関する情報についてはMemory Management Via Regionsを参照せよ．

Raw
Introduction to Regions.md

Introduction to Regions

C gives programmers complete control over how memory is managed. An expert programmer can exploit this to write very fast and/or space-efficient programs. However, bugs that creep into memory-management code can cause crashes and are notoriously hard to debug.

Languages like Java and ML use garbage collectors instead of leaving memory management in the hands of ordinary programmers. This makes memory management much safer, since the garbage collector is written by experts, and it is used, and, therefore, debugged, by every program. However, removing memory management from the control of the applications programmer can make for slower programs.

Safety is the main goal of Cyclone, so we provide a garbage collector. But, like C, we also want to give programmers as much control over memory management as possible, without sacrificing safety. Cyclone’s region system is a way to give programmers more explicit control over memory management.

In Cyclone, objects are placed into regions. A region is simply an area of memory that is allocated and deallocated all at once (but not for our two special regions; see below). So to deallocate an object, you deallocate its region, and when you deallocate a region, you deallocate all of the objects in the region. Regions are sometimes called “arenas” or “zones.”

Cyclone has four kinds of region:

Stack regions

As in C, local variables are allocated on the runtime stack; the stack grows when a block is entered, and it shrinks when the block exits. We call the area on the stack allocated for the local variables of a block the stack region of the block. A stack region has a fixed size–it is just large enough to hold the locals of the block, and no more objects can be placed into it. The region is deallocated when the block containing the declarations of the local variables finishes executing. With respect to regions, the parameters of a function are considered locals–when a function is called, its actual parameters are placed in the same stack region as the variables declared at the start of the function.

Lexical regions

Cyclone also has lexical regions, which are so named because, like stack regions, their lifetime is delimited by the surrounding scope. Unlike stack regions, however, you can can add new objects to a lexical region over time. You create a lexical region in Cyclone with a statement,

  region _ identifier_; _ statement_

This declares and allocates a new lexical region, named identifier, and executes statement. After statement finishes executing, the region is deallocated. Within statement, objects can be added to the region (see Region Allocation).

Typically, statement is a compound statement:

  { region _identifier_;
    _ statement_1
    ...
    _ statement__n_
  }

The heap region

Cyclone has a special region called the heap. There is only one heap, whose type is denoted `H, and it is never deallocated. New objects can be added to the heap at any time (the heap can grow). Cyclone uses a garbage collector to automatically remove objects from the heap when they are no longer needed. You can think of garbage collection as an optimization that tries to keep the size of the heap small. (Alternatively, you can avoid garbage collection all together by specifying the -nogc flag when building the executable.)

Dynamic regions

Stack and lexical regions obey a strictly last-in-first-out (LIFO) lifetime discipline. This is often convenient for storing temporary data, but sometimes, the lifetime of data cannot be statically determined. Such data can be allocated in a dynamic region. A dynamic region supports deallocation at (essentially) any program point. However, before the data in a dynamic region may be accessed, the dynamic region must be opened. The open operation fails by throwing an exception if the dynamic region has already been freed. Note that each data access within a dynamic region does not require a check. Rather, you can open a given dynamic region once, access the data many times with no additional cost, and then exit the scope of the open. Thus, dynamic regions amortize the cost of checking whether or not data are still live and localize failure points. We describe dynamic regions in detail in Section Dynamic Regions.

Cyclone forbids dereferencing dangling pointers. This restriction is part of the type system: it’s a compile-time error if a dangling pointer (a pointer into a deallocated region or to a deallocated object) might be dereferenced. There are no run-time checks of the form, “is this pointing into a live region?” As explained in Region Common Uses, each pointer type has a region and objects of the type may only point into that region.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment