低レイヤから見るindex out of bounds
これはEventHub Advent Calendar 2023の6日目の記事です。昨日は未経験から人事に挑戦! 入社3年目の大反省会でした。
最近index out of boundsの話になったので、それについて調べていく。index out of boundsとは配列に対してインデックスでアクセスした際、配列自体の長さを超えたアクセスに対して発生するエラーのこと。代表的な言語を2つ挙げ、どういった実装になっているのか、なぜこの挙動になるのか、を調べていく。低レイヤと書いたのは、結果的にアセンブリまで見ることになったので。
調べた順に調べた内容をただ書いていくので、まとまった情報を求めている人には向かないかもしれない。
Rust
まずは一般的な (?) index out of boundsの挙動をする言語としてRustを取り上げる。ここでは固定長配列であるarray type ([T; N]) を対象とする。が、まあVecも根本的にはあまり変わらないのではないかと予測している。
まずはindex out of boundsする
fn at(arr: [i32; 4], idx: usize) -> i32 {
arr[idx]
}
fn main() {
let arr = [1,2,3,4];
println!("at(arr, 4) = {}", at(arr, 4));
}
を実行すると、
$ cargo run
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Running `target/debug/pg`
thread 'main' panicked at src/main.rs:2:5:
index out of bounds: the len is 4 but the index is 4
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
ハイ。
実装を追う
arr[idx]の処理を知りたいので、rustcのソースコードを探っていく。(対象commitは、これを書いている時点のHEAD。)
Rustではindexing operationはIndex traitで定義される。arrayのIndex実装はここだが、潜っていくとここにたどり着くはず。
unsafe impl<T> SliceIndex<[T]> for usize {
type Output = T;
...
#[inline]
fn index(self, slice: &[T]) -> &T {
// N.B., use intrinsic indexing
&(*slice)[self]
}
...
}
「arr[idx]がなにをやっているのか」という疑問の答えを探していたのに、「&(*slice)[self] = &(*&arr)[idx]をやっているよ」という答えが返ってきてしまった。これはどういうことかというと、arr[idx]の処理について、このrustc core libraryの中で実装するではなく、このrustc core libraryをビルドするRustコンパイラのビルトインの処理を使っている (コメントの"using intrinsic indexing"というのはそうした意味)。これはちゃんと考え出すと結構複雑なのだが、なんにせよarr[idx]の処理内容はここには書いていない。
というわけでじゃあどうするかというと諦めてアセンブリを見る。
アセンブリを見る
pub fn at(arr: [i32; 4], idx: usize) -> i32 {
arr[idx]
}
というコードをアセンブリにコンパイルする。(Compiler Explorer使用。Rust 1.73.0) 出力は次の通り。処理内容はコメントした。
example::at:
sub rsp, 24
mov qword ptr [rsp + 8], rdi
mov qword ptr [rsp + 16], rsi
; ここで`arr`のサイズ4と`idx`を比較している。
; idxが4未満であれば`.LBB0_1`に、4以上であれば`.LBB0_2`にjumpする。
cmp rsi, 4
setb al
test al, 1
jne .LBB0_1
jmp .LBB0_2
; index out of boundsにならない場合の処理。
.LBB0_1:
mov rax, qword ptr [rsp + 8]
mov rcx, qword ptr [rsp + 16]
; ここで`arr[idx]`を実行している。
; arr + idx * 4
; - arr = `arr`の実データのアドレス
; - 4 = `arr`の1要素のサイズ (i32なので4 bytes)
mov eax, dword ptr [rax + 4*rcx]
add rsp, 24
ret
; index out of boundsになる場合の処理。
.LBB0_2:
mov rdi, qword ptr [rsp + 16]
lea rdx, [rip + .L__unnamed_1]
; なんか多分`rip + core::panicking::panic_bounds_check@GOTPCREL`に
; index out of boundsのためのpanicコードがあるっぽい。
mov rax, qword ptr [rip + core::panicking::panic_bounds_check@GOTPCREL]
mov esi, 4
call rax
ud2
.L__unnamed_2:
.ascii "/app/example.rs"
.L__unnamed_1:
.quad .L__unnamed_2
.asciz "\017\000\000\000\000\000\000\000\002\000\000\000\005\000\000"
arrのサイズはアセンブリに直接4と書かれている。これはRustのarray typeがcompile time時点でサイズが明らかなので、コンパイラが書き込んでいる (はず)。Vecだとこれが固定長ではなくなるのでruntimeにサイズが変わる。だからおそらくもっと処理がめんどうになりそう。(実際にVecでアセンブリ出力したところ大変なコード量になったので、ここでは触れない。)
Rustまとめ
array ([T; N]) はcompile timeにサイズが明らかになっている。コンパイラはこれを利用し、インデックスアクセス処理の前に、インデックスの大きさを検証するコードを挿入する。
C
次にindex out of boundsが発生せず、どこにでもアクセスさせてくれるC言語を取り上げる。
gccとclangの違い？
gcc (GCC) 13.2.1 20230801とclang version 16.0.6を使ってLinux上で実験する。
コード1
#include <stdio.h>
int main() {
int arr[4] = {1,2,3,4};
printf("arr[16] = %d\n", arr[16]);
}
$ gcc -Wall -Wextra -o main main.c && ./main
arr[16] = -1802207168
$ clang -Wall -Wextra -o main main.c && ./main
main.c:18:30: warning: array index 16 is past the end of the array (that has type 'int[4]') [-Warray-bounds]
printf("arr[16] = %d\n", arr[16]);
^ ~~
main.c:17:5: note: array 'arr' declared here
int arr[4] = {1,2,3,4};
^
1 warning generated.
arr[16] = -1693265856
こう見るとgccは無言でやばいindexしてくるが、clangはwarningくらいは出してくれるように見える。
コード2
#include <stdio.h>
int get(int arr[], int idx) {
return arr[idx];
}
int main() {
int arr[4] = {1,2,3,4};
printf("arr[16] = %d\n", get(arr, 16));
}
$ gcc -Wall -Wextra -o main main.c && ./main
arr[16] = 1157128256
$ clang -Wall -Wextra -o main main.c && ./main
arr[16] = 1834926144
というわけで、まあたいして変わらん。
arrayとpointer
Cはpointerとは別にarray typeを持つ。だから、arrayと、arrayの最初の要素へのpointerは異なる。例えば次のようになる。
#include <stdio.h>
int main() {
int arr[4] = {1,2,3,4};
int *p = &arr[0];
printf("sizeof(arr) = %ld\n", sizeof(arr));
// => sizeof(arr) = 16
printf("sizeof(p) = %ld\n", sizeof(p));
// => sizeof(p) = 8
arr++; // error!
p++; // pointer arithmetic
printf("*p = %d\n", *p);
// => *p = 2
}
しかしarrayが関数の引数に渡されると、arrayはpointerにconvertされる (decay)。
#include <stdio.h>
int get(int arr[], int idx) {
printf("sizeof(arr) = %ld\n", sizeof(arr));
// => sizeof(arr) = 8
arr++;
printf("arr[0] = %d\n", arr[0]);
// => arr[0] = 2
return arr[idx];
}
int main() {
int arr[4] = {1,2,3,4};
printf("get(arr, 0) = %d\n", get(arr, 0));
// => get(arr, 0) = 2
}
int get(int arr[], int idx)がint get(int *arr, int idx)と同じなら、当然コンパイラはarrのサイズを知らない。このためindex out of boundsという高等なことはできない。
(だが、int arr[4] = {1,2,3,4}; arr[4];というコードは明らかにできるはずではある…。)
アセンブリを見る
Rustで見たので、Cでもアセンブリを見てみる。
int get(int arr[8], int idx) {
return arr[idx];
}
というコードをアセンブリにコンパイルする。(int arr[8]としてみた。これはarrayのサイズ表記がなんの効果もないことを示したいため。)
get:
push rbp
mov rbp, rsp
mov QWORD PTR [rbp-8], rdi // arr
mov DWORD PTR [rbp-12], esi // idx
mov eax, DWORD PTR [rbp-12]
cdqe
; arr + idx * 4 を計算する。
; (4はarrの要素のintのサイズ)
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-8] // arr
add rax, rdx
; arr + idx * 4 のアドレスから値を取っている。
mov eax, DWORD PTR [rax]
pop rbp
ret
まあ見ると分かるが、arrayのサイズ情報はどこにも含まれていない。そもそもpointerなのだからサイズもなにもないのだが。
Cまとめ
array自体は自身のサイズを知っているが、暗黙的にpointerにconvertされるケースが多く、その際にサイズ情報を失う。いずれにしても、そもそもコンパイラはインデックスアクセス処理に付加的な処理を加えない。コンパイラが余計なことをせず、ユーザーに任せる言語設計なのかも？
ちなみにRustもCっぽいインデックスアクセスができる
Rustでもindex out of boundsを発生させない、検証なしのインデックスアクセスができる。
pub fn at(arr: [i32; 4], idx: usize) -> i32 {
unsafe {
*(&arr).get_unchecked(idx)
}
}
fn main() {
let arr: [i32; 4] = [1,2,3,4];
println!("{}", at(arr, 16));
}
$ cargo r
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Running `target/debug/pg`
-1887539200
実装はここにあり、これはC言語のpointer arithmeticを使った処理と同じ。
#[inline]
unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
....
unsafe {
...
slice.as_ptr().add(self)
}
}
まとめ
以上では固定長配列のインデックスアクセスの処理とindex out of boundsを実現する方法を調べた。
Rustでは、compile timeにarrayのサイズが明らかであることを利用し、arrayのサイズを出力に直接埋め込むことで、インデックスの大きさを検証する処理を実現する。Cでは、そもそもindex out of boundsの処理が付加されないし、arrayがpointerにconvertされるために検証が不可能なケースもよくある。
可変長配列はcompile timeにはサイズが明らかではない。しかし該当構造体が内部的にサイズを保持しているので、runtimeのインデックスアクセスのたびにそのときのサイズ値を取ってきてインデックスを検証する。
まあ考えるとそうなって当然のことではあるが、細かいところまで明らかになったのは良かった。
EventHubでは、各ポジションの採用活動を強化しています。ご興味がある方はぜひご連絡ください！(採用ページ：https://jobs.eventhub.co.jp/)
Discussion