created at 2023/04/19
Althea(アルテア)というプログラミング言語を開発しました。
https://github.com/yagipy/althea
Altheaは所有権と参照カウントを組み合わせた所有権付き参照カウントというメモリ管理手法を備えています。
所有権と参照カウントはそれぞれ単体でもメモリ管理手法として使用されますが、組み合わせることでそれぞれの欠点を打ち消し合うことができます。
この手法を用いることで、プログラミング時に発生する「性能が安定しない」「手動メモリ管理による脆弱性」「学習コストの増大」という3つの課題を解決しました。
SecHack365で作成したポスターと動画にもAltheaに関する情報がありますので、良ければご覧ください。
変数定義は以下のように行います。
let a: i32 = 1
let str: string = "Hello, World"
let arr: [i8; 8] = [1; 8]
数値、文字列、固定長配列、列挙型、構造体を定義することができます。
上記コードでは数値、文字列、固定長配列を定義しています。(列挙型、構造体の定義は後述します)
数値は型を指定しなかった場合、i32
型となります。
列挙型の宣言は以下のように行います。
enum Result {
Ok(i32),
Err(string),
}
列挙子にはデータを持たせることができます。(Rustのenumと同様)
このデータは列挙子ごとに別の型を持つことができます。
列挙型の定義は以下のように行います。
let result = Result::Ok(1)
構造体の宣言は以下のように行います。
struct User {
id: i32,
name: string,
email: string,
}
構造体の定義は以下のように行います。
let user: User = User {
id: 1,
name: "name string",
email: "email@example.com",
}
構造体はヒープ領域に確保され、所有権付き参照カウントによって管理されます。
関数定義は以下のように行います。
func add(a: i32, b: i32) i32 {
a + b
}
return
は不要です。
関数呼出は以下のように行います。
add(1, 2)
if文は以下のように書きます。
if a <= 0 {
0
} else if a == 1 {
1
} else {
2
}
パターンマッチはmatch
を使用して以下のように書きます。
enum Result {
Ok(i32),
Err(string),
}
struct Foo {
bar: i32,
}
func main() i32 {
let foo: Foo = Foo {
bar: Result::Ok(1),
}
match foo { // パターンマッチ
Foo { bar: bar } => match bar {
Result::Ok(val) => {
println("foo.bar is Ok.\n")
}
},
}
}
数値、列挙型、構造体のパターンマッチが可能です。
標準出力は組み込み関数であるprintln
で行います。\n
で改行が可能です。
println("Hello, World!")
組み込み関数のlisten_and_serve
でHTTPサーバーの起動が可能です。
第1引数にポート番号、第2引数にリクエストハンドラを渡します。
listen_and_serve(80, func handle() string {
"Hello, World!"
})
内部ではsocket
、bind
、listen
等のシステムコールを呼び出しています。
実装言語はRustです。LLVMバックエンドを使用しています。
実行ファイル生成フローは以下のようになっています。(ポスターから引用しています)
Althea IRによって所有権付き参照カウントのアルゴリズムを独立させ、かつCodegenの実装をシンプルにすることができました。
所有権付き参照カウントは参照カウントと所有権を組み合わせたメモリ管理手法です。
参照カウントと所有権は、それぞれ単体でもメモリ管理手法として使用されますが、Altheaでは組み合わせて使用しています。
ここでは、それぞれの仕組みと課題について紹介した後に組み合わせるとどうなるかについて書いていきます。
所有権は、変数がメモリ上の1データ(以下オブジェクト)を所有しそのオブジェクトを解放する責任を持つ仕組みです。所有権を採用している言語としてはRustが有名です。
所有権は以下のようなルールに従います。
これらの仕組みによって、変数のスコープとオブジェクトの寿命をマッチさせて管理することができます。
ただ、このルールのみだと変数を別の変数に入れた際や関数に渡した際の挙動に対応できないため、参照、借用、クローン、ムーブという仕組みも合わせて使用します。
上記のような仕組みを使用した場合、変数を別の変数に入れた際や関数に渡した際に何度も状況に合わせた判断をする必要があり、管理や理解に時間がかかることが課題として挙げられます。
この課題をRustのコードを使用して簡単に説明します。
下記コードはString
型のfoo
をbar
に代入しています。RustのString型は可変かつ伸長可能なテキストをサポートするためにコンパイル時には不明な量のメモリをヒープ領域に確保します。
fn main() {
let foo = String::from("foo");
let bar = foo;
println!("{}", foo);
}
上記コードをコンパイルすると以下のようなエラーが発生します。
error[E0382]: borrow of moved value: `foo`
--> src/main.rs:4:18
|
2 | let foo = String::from("foo");
| --- move occurs because `foo` has type `String`, which does not implement the `Copy` trait
3 | let bar = foo;
| --- value moved here
4 | println!("{}", foo);
| ^^^ value borrowed here after move
|
= note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider cloning the value if the performance cost is acceptable
|
3 | let bar = foo.clone();
| ++++++++
これはfoo
をbar
に代入する際に所有者(所有権)がfoo
からbar
にムーブしたのにも関わらず、その後にfoo
を使用しようとしたために発生するエラーとなっています。
String型はCopyトレイトを実装していないためデフォルトでムーブとなります。(元々Rustの変数代入時のデフォルト挙動はムーブですが、Copyトレイトを実装している型は代入時にコピーとなります)
そしてムーブの場合、スタックにあるポインタ、長さ、キャパシティがムーブ先の変数(ここではbar
)にコピーされ、ムーブ元の変数(ここではfoo
)は使用できなくなります。
ちなみにポインタが指すヒープ領域のデータはコピーされません。shallow copyと似ていますがムーブ元の変数が使えなくなるという点で異なるため、ムーブと呼ばれているようです。
このようにして、ムーブ元の変数(ここではfoo
)が所有権を失い使用することができないことによるエラーであると分かります。
このエラーを解決する方法はいくつもあり、それらを文脈に合わせて適切に使い分ける必要があります。
この項では所有権の管理や理解に時間がかかることを伝えることが目的であるため、代表的な解決方法を軽く紹介するだけにします。
bar
定義時foo
のクローンを渡すfoo
とbar
それぞれ別オブジェクトの所有権を持ちます。そのため実行コストは高く、データは別々に管理されます。fn main() {
let foo = String::from("foo");
let bar = foo.clone();
println!("{}", foo);
}
bar
定義時foo
の参照を渡すfoo
のままで、bar
はfoo
の参照を保持します。bar
は所有者ではないため、スコープを抜けてもオブジェクトは解放されません。(ここではfoo
とbar
のスコープが一緒なので少し紛らわしいですが。。。)fn main() {
let foo = String::from("foo");
let bar = &foo;
println!("{}", foo);
}
foo
定義時Rc
を使用するRc
は参照カウント方式のスマートポインタです。deep copyと違い、ヒープ領域のデータは共有管理されます。foo
とbar
両方がスコープから抜けたら解放されます。use std::rc::Rc;
fn main() {
let foo = Rc::new(String::from("foo"));
let bar = Rc::clone(&foo);
println!("{}", foo);
}
他にも以下のような方法があります。
foo
定義時Box
を使用するBox
を使用することでヒープ領域に割り当てることができます。Box::clone
を使用することでクローンを行うことができます。foo
定義時Arc
を使用するRc
ではなくArc
を使用します。Rc
やArc
の参照先の値を変更したい時はCell
、RefCell
、Mutex
、RwLock
を使用することができます。このように所有権の管理や理解には様々な知識が必要であり学習コストがかかります。
オブジェクトを参照している変数をカウントし、カウントが0になったらオブジェクトを解放するという仕組みです。参照カウントを採用している言語としてはPython、Swiftが有名です。あと、C++11以降では参照カウントでオブジェクトを管理するためのクラステンプレートとしてstd::shared_ptr
が存在します。
参照カウントは以下のようなルールに従います。
参照カウントは、メモリ管理コストを処理全体に分散することができ、かつオブジェクトが不要になった際にすぐに解放することができます。
しかし、無駄なカウント管理処理が発生しやすいことが課題として挙げられます。
この課題をコード例(Rust)を用いて説明します。
下記は参照カウント方式のスマートポインタ(std::rc::Rc
)を使用してオブジェクトを管理している例です。
use std::rc::Rc;
fn main() {
let foo = Rc::new(String::from("foo"));
println!("do_fn関数呼出前: {}", Rc::strong_count(&foo));
do_fn(Rc::clone(&foo));
println!("do_fn関数呼出後: {}", Rc::strong_count(&foo));
}
fn do_fn(do_arg: Rc<String>) {
println!("do_fn関数内: {}", Rc::strong_count(&do_arg));
println!("{}", do_arg);
}
上記コードを実行すると、下記のような出力が得られます。
do_fn関数呼出前: 1
do_fn関数内: 2
foo
do_fn関数呼出後: 1
do_fn
関数呼出前は、オブジェクトの参照カウント数が1であることが分かります。これはfoo
変数からの参照のみであることを意味します。
do_fn
関数内は、オブジェクトの参照カウント数が2であることが分かります。これはfoo
変数からの参照とdo_arg
変数からの参照があることを意味します。
do_fn
関数呼出後は、オブジェクトの参照カウント数が1に戻ります。これはdo_arg
変数からの参照がなくなり、foo
変数からの参照のみになったことを意味します。
do_fn
関数によって参照カウントが増減していますが、do_fn
関数内はdo_arg
をprintln
のみで使用しているため、本来は借用で十分であり参照カウントの増減処理は必要ありません。
このように参照カウントは無駄な増減処理が発生してしまうことがあります。
所有権と参照カウントを組み合わせることで、先ほどのそれぞれの課題を打ち消し合うことができます。
所有権の課題である「管理や理解に時間がかかる」は、変数を別の変数に入れた際や関数に渡した際に何度も状況に合わせた判断をする必要があることが原因の1つとして挙げられますが、この判断をする際に参照カウントを使用することで解消することができると考えています。
参照カウントの課題である「無駄なカウント管理処理が発生しやすい」は、ヒープ領域割り当てごとに所有権を割り当て、その後の利用を基本的に借用とする(参照カウントの使用タイミングを最小限にする)ことで解消することができると考えています。
これらを整理すると下記のルールに従うことになります。
具体的に、変数代入時は「左辺は右辺の値を所有したい」、関数呼出時は「仮引数は実引数の値を借用したい」ものとして扱います。
右辺値と実引数値はそれぞれリテラルと変数を使用でき、リテラルは「所有されたい」、変数は「借用させたい(所有したままにしたい)」として扱います。
そして、それぞれのパターンでマッチングを行います(2x2=4パターン)。オブジェクトの解放はスコープから抜けるタイミングで行われます。
これらのルールを所有権付き参照カウントと呼んでいます。
上記で説明した4パターンのマッチングについて、入力値のAltheaコードと出力値のLLVM IRを示しつつ説明していきます。
Altheaコードは以下のようになります。
struct Foo {
bar: i32,
}
func main() i32 {
let foo: Foo = Foo {
bar: 1,
}
0
}
出力されるLLVM IRは以下のようになります。
; ModuleID = 'alc'
source_filename = "example/gc_check/assign_literal_to_variable.alt"
declare i32 @printf(i8*)
declare i32 @socket(i32, i32, i32)
declare i32 @bind(i32, { i16, [14 x i8] }*, i32)
declare i32 @listen(i32, i32)
declare i32 @accept(i32, { i16, [14 x i8] }*, i32*)
declare i64 @recv(i32, i8*, i64, i32)
declare i64 @send(i32, i8*, i64, i32)
declare i32 @close(i32)
declare i32 @snprintf(i8*, i64, i8*, ...)
declare i64 @strlen(i8*)
declare i16 @htons(i16)
declare i8* @malloc(i64)
declare void @free(i8*)
define i32 @main() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
ret i32 0
}
変数代入時は「左辺は右辺の値を所有したい」、リテラルは「所有されたい」として扱います。
マッチングに成功しているため、特に特別な処理はせず変数定義したスコープにヒープ領域を確保(@main
関数の2行目)し、スコープを抜けるタイミングで解放(@main
関数の7行目)します。
Altheaコードは以下のようになります。
struct Foo {
bar: i32,
}
func main() i32 {
let foo: Foo = Foo {
bar: 1,
}
let foo2: Foo = foo
0
}
出力されるLLVM IRは以下のようになります。(抜粋)
define i32 @main() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%rc_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 1
%rc = load i32, i32* %rc_ptr, align 4
%increment_rc = add i32 %rc, 1
store i32 %increment_rc, i32* %rc_ptr, align 4
%rc_ptr1 = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 1
%rc2 = load i32, i32* %rc_ptr1, align 4
%decrement_rc = sub i32 %rc2, 1
store i32 %decrement_rc, i32* %rc_ptr1, align 4
%is_zero = icmp sle i32 %decrement_rc, 0
br i1 %is_zero, label %free, label %else
free: ; preds = %entry
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
br label %else
else: ; preds = %free, %entry
ret i32 0
}
変数代入時は「左辺は右辺の値を所有したい」、変数は「借用させたい(所有したままにしたい)」として扱います。
左辺値も右辺値も所有したいということになるため、参照カウントを使用(@main
関数の7~9行目)します。
Altheaコードは以下のようになります。
struct Foo {
bar: i32,
}
func main() i32 {
let baz_val: i32 = baz(Foo {
bar: 1,
})
baz_val
}
func baz(foo: Foo) i32 {
0
}
出力されるLLVM IRは以下のようになります。(抜粋)
define i32 @main() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%alc_2 = call i32 @baz({ i32, i32 }* %alc_1)
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
ret i32 %alc_2
}
define i32 @baz({ i32, i32 }* %0) {
entry:
ret i32 0
}
関数呼出時は「仮引数は実引数の値を借用したい」、リテラルは「所有されたい」として扱います。
関数呼出時のタイミングではリテラルのデータを保持するヒープ領域は確保されていないため、関数呼出したスコープに無名変数でヒープ領域を確保(@main
関数の2行目)します、
その後、スコープを抜けるタイミングで解放(@main
関数の8行目)します。
Altheaコードは以下のようになります。
struct Foo {
bar: i32,
}
func main() i32 {
let foo: Foo = Foo {
bar: 1,
}
let baz_val: i32 = baz(foo)
baz_val
}
func baz(foo: Foo) i32 {
0
}
出力されるLLVM IRは以下のようになります。(抜粋)
define i32 @main() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%alc_2 = call i32 @baz({ i32, i32 }* %alc_1)
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
ret i32 %alc_2
}
define i32 @baz({ i32, i32 }* %0) {
entry:
ret i32 0
}
関数呼出時は「仮引数は実引数の値を借用したい」、変数は「借用させたい(所有したままにしたい)」として扱います。
マッチングに成功しているため、特に特別な処理はせず借用(@main
関数の6行目)を行います。
ここからは、所有権付き参照カウントを用いることでプログラミング時に発生する「性能が安定しない」「手動メモリ管理による脆弱性」「学習コストの増大」という3つの課題を解決することができたかを見ていきます。
現在主流の言語で採用されているGCの多くはStop The Worldという処理が完全に停止する期間があるため、安定した性能を実現するのが難しいことが多いです。具体例としてDiscordのRead Statesサービスや、DMMのCassandraサーバーがあります。
Altheaでは参照カウントをベースとしているため、メモリの解放処理が処理全体に分散し性能が安定します。
HTTPサーバーを起動するコードを例として見ていきます。
struct Foo {
bar: i32,
}
func main() i32 {
listen_and_serve(80, func handle() string {
let foo: Foo = Foo {
bar: 1,
}
"response string"
})
}
以下は出力されるLLVM IRの一部です。リクエストハンドラであるhandle内で構造体のメモリを解放(@handle
関数の7行目)しているため、基本的に1リクエストごとにメモリが解放されることが分かります。
define i8* @handle() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
%malloccall1 = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ([14 x i8]* getelementptr ([14 x i8], [14 x i8]* null, i32 1) to i32))
%return_tmp = bitcast i8* %malloccall1 to [14 x i8]*
store [14 x i8] c"Hello, world!\00", [14 x i8]* %return_tmp, align 1
%return_tmp2 = getelementptr inbounds [14 x i8], [14 x i8]* %return_tmp, i32 0, i32 0
ret i8* %return_tmp2
}
手動でメモリ管理を行う言語は、Use-after-freeやメモリリークなどの問題が発生する可能性があり、場合によっては重大な脆弱性につながります。具体例として、Chromiumでは深刻なセキュリティバグの約70%がメモリ安全でないことが起因となっています。
Altheaではコンパイラが自動的にメモリ管理を行うため、手動メモリ管理による問題や脆弱性は発生しません。
以下のAltheaコードとLLVM IRでは、構造体用に確保したヒープ領域を、その構造体を所有している変数がスコープから抜けるタイミングで自動的に解放しています。
struct Foo {
bar: i32,
}
func main() i32 {
let foo: Foo = Foo {
bar: 1,
}
0
}
define i32 @main() {
entry:
%malloccall = tail call i8* bitcast (i8* (i64)* @malloc to i8* (i32)*)(i32 ptrtoint ({ i32, i32 }* getelementptr ({ i32, i32 }, { i32, i32 }* null, i32 1) to i32))
%alc_1 = bitcast i8* %malloccall to { i32, i32 }*
%field_0_ptr = getelementptr inbounds { i32, i32 }, { i32, i32 }* %alc_1, i32 0, i32 0
store i32 1, i32* %field_0_ptr, align 4
%raw = bitcast { i32, i32 }* %alc_1 to i8*
call void @free(i8* %raw)
ret i32 0
}
@main
関数のret
直前で@free
関数が呼び出されていることが分かると思います。
課題の①と②を解決するために所有権を使う言語がありますが、所有権を使う言語は学習コストが高いと考えられています。
実際に2016年に行われたRustの調査ではRustの課題について1900人以上から回答があり、その中の4人に1人が学習曲線についてコメントをしているようです。さらに、その調査の中で所有権に関連する仕組みに言及しているコメントが複数紹介されています。
"Borrow checker is hard to grasp for a beginner."
"ボローチェッカーは初心者にはわかりにくい"
"The borrow system, albeit powerful, can be difficult to learn."
"借用システムは、強力とはいえ、習得が困難です。"
Altheaでは所有権をコンパイラが自動で管理するため、コードを書く時に所有権の管理や理解に時間がかかりません。
RustではコンパイルエラーになるコードでもAltheaでは一部実行可能になります。
具体例として、下記のRustコードはコンパイルエラーになりますが、
fn main() {
let foo = String::from("foo");
let bar = foo;
println!("{}", foo);
}
error[E0382]: borrow of moved value: `foo`
同じような挙動の下記Altheaコードは実行可能です。
func main() i32 {
let foo = "foo"
let bar = foo
println(foo)
0
}
foo
参照カウントがベースなので循環参照対策が必要なのですが、現在は未対策です。
個人的に興味がある分野をベースに大きく2つの方針を考えています。
Stop The Worldによって性能要件を満たすことが難しいサーバーや大規模にメモリを使用するサーバーにより効果的だと考えています。
サポートが進んでおり、現在以下の2ファイルでHTTPサーバーを立てることが可能になっています。今後は様々なHTTPメソッドのハンドリングやクエリパラメータの取得をサポートする予定です。
FROM yagipy/althea:bullseye
WORKDIR /app
COPY . .
RUN althea main.alt --gc=ownrc -o /usr/local/bin/benchmark-server-althea
CMD ["benchmark-server-althea"]
func main() i32 {
listen_and_serve(80, func handle() string {
"
<meta charset='UTF-8'>
<h1>Althea</h1>
このサーバーはAltheaを使用しています</br>
Altheaのコードは<a href='https://github.com/yagipy/althea'>こちら</a></br>
サーバーのコードは<a href='https://github.com/yagipy/althea/tree/main/example/server'>こちら</a></br>
"
})
}
Altheaは大規模なメモリを使用する際に効果的なため、インメモリDBを開発する際にも効果的だと考えています。
インメモリDB開発のために、様々なデータ構造を標準ライブラリから提供することで簡単に高性能なインメモリDBを開発できることを目指していきたいと考えています。
こちらは今後の開発予定であり、まだサポートはされていません。
Altheaの開発にあたり、SecHack365に関わる方々には様々な形でサポートしていただきました。ありがとうございました。