[rust]ZST/DSTによるflexible array memberの実現

  • flexible array memberとは
  • ZSTを使う方法
  • DSTを使う方法

flexible array memberとは

flexible array memberとはずばり,C言語で以下のようなサイズ定義を持たない構造体メンバのことです(C99から標準).

struct X{
    size_t len;
    char value[];
}

この構造体は以下のようにして使うことができます.

size_t len = 10;
struct X *p = (struct X*)malloc(sizeof(struct X) + len);
p->len = len;
p->value[0] = 'a';
p->value[1] = 'b';
...

このように,flexible array memberを使用することで(ヘッダ+可変サイズなデータ)を持つ構造を簡潔に表現できます.普通はvalueは適当なポインタで持てばいいと思いますが,メモリ的にヘッダとデータが連続して欲しい場合,あるいは連続したバッファが与えられてそこにデータ構造を作成する場合などに有用です. ちなみにsizeof(struct X)の値はflexible array memberを除いたサイズ(上の例だと実質的にsizeof(size_t))になります.

ZSTを使う方法

rustにおいて,flexible array memberそのものとずばり対応するものはありません. 似たようなことをしたい場合は,Zero Sized Types (ZSTs) あるいは Dynamically Sized Types (DSTs)を使います.

最初に言っておくと,ZSTを使う場合はなんちゃってflexible array memberになります.

ZSTはその名の通りサイズが0の型で,例えば()がそれに相当します. これはもともと例えばSetを実現するためにSet<Key> = Map<Key, ()>として,Mapの実装を利用しつつ無駄な領域が割り当てられないようにするといった機能のために用意されたもののようです.

ZSTを利用する場合,最初のC言語の例と同じような構造は以下のようにして定義できます.

#[derive(Debug)]
#[repr(C)]
struct X {
    len: usize,
    val: [u8; 0],
}

ここではvalZSTになります.valのサイズは0なので,std::mem::size_of::<X>()は実質的にstd::mem::size_of::usize()と同じ値を返します.

以下のようにしてこのstructを利用することができます.

#![feature(allocator_api)]
use std::heap::{Alloc, Heap, Layout};

unsafe fn alloc(len: usize) -> *mut u8 {
    let layout = Layout::from_size_align(len, std::mem::align_of::<usize>()).unwrap();
    Heap.alloc(layout.clone()).unwrap() as *mut u8
}

unsafe fn free(p: *mut u8, len: usize) {
    let layout = Layout::from_size_align(len, std::mem::align_of::<usize>()).unwrap();
    Heap.dealloc(p, layout);
}

fn zst() {
    unsafe {
        // メモリの確保
        let value_len = 3;
        let header_len = std::mem::size_of::<X>();
        let total_len = header_len + value_len;
        let p = alloc(total_len);

        // 確保したバッファ先頭をstruct Xにキャスト
        let header: &mut X = std::mem::transmute(p);
        header.len = value_len;

        // valにアクセスするためのスライスの作成
        let val: &mut [u8] =
            std::slice::from_raw_parts_mut(p.offset(header_len as isize), header.len);
        val[0] = 1;
        val[1] = 2;
        val[2] = 3;

        // get_unchecked_mutを利用したアクセス
        *header.val.get_unchecked_mut(0) = 100;
        // これは index out of bounds error
        //header.val[0] = 100;

        println!("header_len = {}", header_len);
        println!("value_len  = {}", value_len);
        println!("header     = {:?}", header);
        println!("val        = {:?}", val);
        println!(
            "p          =  {:?}",
            std::slice::from_raw_parts(p, total_len)
        );

        free(p, total_len);
    }
}

実行結果は以下のようになります.

header_len: 8
value_len: 3
header: X { len: 3, val: [] }
val: [100, 2, 3]
p: [3, 0, 0, 0, 0, 0, 0, 0, 100, 2, 3]

やっていることはC言語の場合とほぼ同じで,まず適当な方法(ここではstd::heap::Alloc)でヘッダ(元々のstructの大きさ)+可変長サイズのデータの長さ分のメモリを確保します.メモリ確保方法の詳細は前回のエントリを参照して下さい.

        let value_len = 3;
        let header_len = std::mem::size_of::<X>();
        let total_len = header_len + value_len;
        let p = alloc(total_len);

その後確保したメモリをtransmuteXへのreferenceにしてヘッダにアクセスします.

        let header: &mut X = std::mem::transmute(p);
        header.len = value_len;

valに関してはfrom_raw_parts_mutでsliceを作成してアクセスします.

        let val: &mut [u8] =
            std::slice::from_raw_parts_mut(p.offset(header_len as isize), header.len);
        val[0] = 1;
        val[1] = 2;
        val[2] = 3;

valget_unchecked_mutを使えばヘッダからのアクセスも一応可能です.普通にアクセスしようとした場合は境界値エラーになります.

        // get_unchecked_mutを利用したアクセス
        *header.val.get_unchecked_mut(0) = 100;
        // これは index out of bounds error
        //header.val[0] = 100;

実のところこの方法は(valへのアクセスに基本的にはスライスを作ることになるので)flexible array memberと呼べるのか微妙なものですが,使うのは楽だと思います.

ちなみに,この方法ではスタック上に変数を確保することはできません.というか,

let x = X{len : 10, val:[]};

とやれば確保できますが,valは必ずemptyでなければならないので実質的に使えません.

DSTを使う方法

DSTを使うことで,本来のflexible array memberに近いものが実現できます. ここでの方法はHacker Newsのコメントから知りました.

DSTはコンパイル時にはサイズが定まらず,実行時にサイズが求まる型のことで,代表的なDSTの一つはスライス[T]です.structは一番最後の要素にDSTを持つことができます.この場合,そのstruct自体がDSTになります.

例えば,以下のようにしてDSTなstructを定義できます.

#[repr(C)]
struct Y{
    len: usize,
    value: [u8],
}

で,このようなstructが定義できるのは良いですが,実のところをこれを直接構成する方法はないです. これは扱いにくいので,代わりに以下のような?Sizedなgeneric data typeを利用します.

#[repr(C)]
struct Y<T: ?Sized> {
    len: usize,
    val: T,
}

コンパイル時に大きさが分かっている場合

そもそもflexible array memberを使いたい目的が動的にデータを割り当てたいという目的からなので,コンパイル時に大きさが分かっている状況というのは本末転倒な状況ですが,この場合は以下のようにして上記のstructをスタック上に構成することができます.

fn as_raw_bytes<T: ?Sized>(x: &T) -> &[u8] {
    unsafe { std::slice::from_raw_parts(x as *const T as *const u8, std::mem::size_of_val(x)) }
}

fn dst1() {
    let len = 10;
    let val: [u8; 10] = [1; 10];
    let y = Y { len, val };

    println!("y      = {:?}", y);
    println!("y      = {:?}", as_raw_bytes(&y));
    println!("&y     = {:p}", &y);
    println!("&y.len = {:p}", &y.len);
    println!("&y.val = {:p}", &y.val);
    println!("size_of_val(&y)     = {}", std::mem::size_of_val(&y));
    println!("size_of_val(&y.len) = {}", std::mem::size_of_val(&y.len));
    println!("size_of_val(&y.val) = {}", std::mem::size_of_val(&y.val));
    println!(
        "size_of(Y<[u8;10]>) = {}",
        std::mem::size_of::<Y<[u8; 10]>>()
    );
    // NG
    //println!("size_of(y) = {}", std::mem::size_of::<Y>());
    //println!("size_of(y) = {}", std::mem::size_of::<Y<[u8]>>());
}

実行結果

y      = Y { len: 10, val: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] }
y      = [10, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 134, 2, 1, 0, 0, 0]
&y     = 0x7fff5d398b68
&y.len = 0x7fff5d398b68
&y.val = 0x7fff5d398b70
size_of_val(&y)     = 24
size_of_val(&y.len) = 8
size_of_val(&y.val) = 10
size_of(Y<[u8;10]>) = 24

ここで,y.lenのサイズは8, y.valはサイズは10ですが,メモリは8バイト単位で確保されるようでy自体のサイズは24になっています.

この場合,DST coercionsを利用して,以下のような関数を呼び出すことが可能になります.

fn f<T: std::fmt::Debug>(y: &Y<[T]>) {
    println!("f: y = {:?}", y);
    // f: y = Y { len: 10, val: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] }
}

fn dst1(){
    let len = 10;
    let val: [u8; 10] = [1; 10];
    let y = Y { len, val };
    f(&y);
}

ちなみに,このコード例において,最初のDSTな構造体

#[repr(C)]
struct Y{
    len: usize,
    value: [u8],
}

を使った場合,以下のようなエラーが発生します.

error[E0308]: mismatched types
   --> src/main.rs:149:22
    |
149 |     let y = Y { len, val };
    |                      ^^^ expected slice, found array of 10 elements
    |
    = note: expected type `[u8]`
               found type `[u8; 10]`

ヒープに割り当てたい場合は,例えば以下のようにVecが利用できます.

    let len = 10;
    let mut vec = Vec::<Y<[u8; 10]>>::with_capacity(1);
    unsafe {
        vec.set_len(1);
    }
    let y = &mut vec[0];
    y.len = len;
    for i in 0..len {
        y.val[i] = i as u8;
    }

動的にサイズを割り当てる

さて,それではようやく本題で,実行時にDSTなstructを構成する方法について説明します.

以下で説明する方法は,servoの一部のコードを参考にその処理を簡略化したものです.元のコードに丁寧にコメントが書いてあるので,興味のある方は一読を勧めます.

fn dst2() {
    let len = 10;

    // サイズの計算
    let fake_slice_ptr: *const u8 = std::mem::align_of::<Y<[u8; 1]>>() as *const u8;
    let fake_slice: &[u8] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) };
    let fake_ptr: *const Y<[u8]> = fake_slice as *const [u8] as *const Y<[u8]>;
    let fake_ref: &Y<[u8]> = unsafe { &*fake_ptr };
    let size = std::mem::size_of_val(fake_ref);

    println!("size_of(fake_ref)   = {}", size);
    println!(
        "size_of(fake_slice) = {}",
        std::mem::size_of_val(fake_slice)
    );
    println!("fake_slice.len      = {}", fake_slice.len());
    println!("fake_ref.val.len    = {}", fake_ref.val.len());

    unsafe {
        let p = alloc(size);

        let fake_slice: &mut [u8] = std::slice::from_raw_parts_mut(p as *mut u8, len);
        let ptr = fake_slice as *mut [u8] as *mut Y<[u8]>;
        let y: &mut Y<[u8]> = &mut *ptr;

        y.len = len;
        for i in 0..len {
            y.val[i] = i as u8;
        }

        println!("y.len     = {}", y.len);
        println!("y.val.len = {}", y.val.len());
        println!("size_of_val(y)    = {}", std::mem::size_of_val(y));
        println!("size_of_val(&ptr) = {}", std::mem::size_of_val(&ptr));
        println!("ptr = {:?}", as_raw_bytes(&ptr));

        free(p, size);
    }
}

実行結果

size_of(fake_ref)   = 24
size_of(fake_slice) = 10
fake_slice.len      = 10
fake_ref.val.len    = 10
y.len     = 10
y.val.len = 10
size_of_val(y)    = 24
size_of_val(&ptr) = 16
ptr = [32, 0, 66, 15, 1, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0]

まず,このコードの前半部分では確保するメモリの大きさを計算します.

    len = 10;
    let fake_slice_ptr: *const u8 = std::mem::align_of::<Y<[u8; 1]>>() as *const u8;
    let fake_slice: &[u8] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) };
    let fake_ptr: *const Y<[u8]> = fake_slice as *const [u8] as *const Y<[u8]>;
    let fake_ref: &Y<[u8]> = unsafe { &*fake_ptr };
    let size = std::mem::size_of_val(fake_ref);

ここで何をやっているかというと,

  • 長さがlen[u8]のfat pinterを作成
  • それを長さがlenY<u8>のポインタにし,さらにそれをreferenceにする
  • size_of_valを使ってサイズを求める.

どうしてこれでサイズが求まるのかというと,DSTな要素は必ずfat pointer経由でアクセスしますが,このときfat pinterは(アドレス,長さ)を持ちます.このとき,この長さというのはDSTなstructの場合は,structの末尾の要素の長さを意味することになります.上のコードはまず最初にfrom_raw_part()を使って長さがlen[u8]のfat pointerを作成した後,それを*const Y<[u8]>のfat pointerにキャストし,そしてさらにそれをreferenceに変換してサイズを計算している訳です. 上の実行結果のptrを見ると,後半8byteで長さ(10)を保持していることが分かります.

    unsafe {
        let p = alloc(size);

        let fake_slice: &mut [u8] = std::slice::from_raw_parts_mut(p as *mut u8, len);
        let ptr = fake_slice as *mut [u8] as *mut Y<[u8]>;
        let y: &mut Y<[u8]> = &mut *ptr;

        y.len = len;
        for i in 0..len {
            y.val[i] = i as u8;
        }
    }

確保すべきメモリサイズが分かったら,メモリを確保して,サイズ計算時と同様にキャストしてY<[u8]>のreferenceを取得し,それを利用してデータ構造を操作します.

確保すべきサイズ計算のところは

let len = 10;
let size = std::mem::size_of::<Y<()>>() + len;

でもいいんじゃないかと思いましたが,この場合はsizeは18になります.前述の通りrustはメモリを(この環境では)8byte単位で確保しているようで,今回の場合はsize_of_val()で得られる値と齟齬が生じることになります.といっても確保したメモリ外にはアクセスしないので大丈夫じゃないかなと思いますが..

実際に利用する場合には,以下のようにしてgeneric data typeを利用すると汎用性が上がります.

fn dst3<T>(len: usize) -> (*mut Y<[T]>, usize) {
    let fake_slice_ptr: *const T = std::mem::align_of::<Y<[T; 1]>>() as *const T;
    let fake_slice: &[T] = unsafe { std::slice::from_raw_parts(fake_slice_ptr, len) };
    let fake_ptr: *const Y<[T]> = fake_slice as *const [T] as *const Y<[T]>;
    let fake_ref: &Y<[T]> = unsafe { &*fake_ptr };
    let size = std::mem::size_of_val(fake_ref);

    unsafe {
        let p = alloc(size);

        let fake_slice: &mut [T] = std::slice::from_raw_parts_mut(p as *mut T, len);
        let ptr = fake_slice as *mut [T] as *mut Y<[T]>;
        (ptr, size)
    }
}

fn f<T: std::fmt::Debug>(y: &Y<[T]>) {
    println!("f: y = {:?}", y);
}

fn main(){
    let len = 10;
    let (ptr, size) = dst3::<u8>(len);
    unsafe {
        let y: &mut Y<[u8]> = &mut *ptr;
        y.len = len;
        for i in 0..len {
            y.val[i] = i as u8;
        }
        f(&y);
        // f: y = Y { len: 10, val: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] }
        free(ptr as *mut u8, size);
    }
}

未初期化領域への代入の注意点

ここまで例ではprimitive typeしか扱ってないので未初期化の領域にそのまま代入していますが,Drop型を実装している型の場合はservoの例のようにstd::ptr::writeを使って書き込まないと未初期化のデータに対してDropが実行されてしまいます.詳細はnomiconに書いてあります.

まとめ

Cにおけるflexible array memberをrustで実現するための方法として,ZSTとDSTを利用する方法について書きました.実のところ両方ともあまりunsafeなコード量は変わらず,本来のflexible array memberに相当するのはDSTを使う方法ですが,状況によってはZSTの方が使いやすいかなと思いました.