swap/swapRangesのはなし

ふと、swapみたいな単純なコードでも標準ライブラリの実装を呼び出した方がいいよ、という例として

import core.int128 : Cent;
import std.algorithm.mutation : swap;

struct Huge
{
    Cent[128] data;
    alias this = data;
}

void f(ref Huge x, ref Huge y)
{
    swap(x, y);
}

みたいなコードを使おうと思ったんだけど、ぜんぜんそんなことはなかった。

$ ldc2 -O -c swap.d
$ objdump -dr --demangle=dlang -Mintel swap.o
(...)
0000000000000000 <swap.f(ref swap.Huge, ref swap.Huge)>:
   0:   41 57                   push   r15
   2:   41 56                   push   r14
   4:   53                      push   rbx
   5:   48 81 ec 00 08 00 00    sub    rsp,0x800
   c:   48 89 f3                mov    rbx,rsi
   f:   49 89 fe                mov    r14,rdi
  12:   49 89 e7                mov    r15,rsp
  15:   ba 00 08 00 00          mov    edx,0x800
  1a:   4c 89 ff                mov    rdi,r15
  1d:   4c 89 f6                mov    rsi,r14
  20:   e8 00 00 00 00          call   25 <swap.f(ref swap.Huge, ref swap.Huge)+0x25>
            21: R_X86_64_PLT32  memcpy-0x4
  25:   ba 00 08 00 00          mov    edx,0x800
  2a:   4c 89 f7                mov    rdi,r14
  2d:   48 89 de                mov    rsi,rbx
  30:   e8 00 00 00 00          call   35 <swap.f(ref swap.Huge, ref swap.Huge)+0x35>
            31: R_X86_64_PLT32  memcpy-0x4
  35:   ba 00 08 00 00          mov    edx,0x800
  3a:   48 89 df                mov    rdi,rbx
  3d:   4c 89 fe                mov    rsi,r15
  40:   e8 00 00 00 00          call   45 <swap.f(ref swap.Huge, ref swap.Huge)+0x45>
            41: R_X86_64_PLT32  memcpy-0x4
  45:   48 81 c4 00 08 00 00    add    rsp,0x800
  4c:   5b                      pop    rbx
  4d:   41 5e                   pop    r14
  4f:   41 5f                   pop    r15
  51:   c3                      ret    
(...)
0000000000000000 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)>:
   0:   41 57                   push   r15
   2:   41 56                   push   r14
   4:   53                      push   rbx
   5:   48 81 ec 00 08 00 00    sub    rsp,0x800
   c:   48 89 f3                mov    rbx,rsi
   f:   49 89 fe                mov    r14,rdi
  12:   49 89 e7                mov    r15,rsp
  15:   ba 00 08 00 00          mov    edx,0x800
  1a:   4c 89 ff                mov    rdi,r15
  1d:   4c 89 f6                mov    rsi,r14
  20:   e8 00 00 00 00          call   25 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x25>
            21: R_X86_64_PLT32  memcpy-0x4
  25:   ba 00 08 00 00          mov    edx,0x800
  2a:   4c 89 f7                mov    rdi,r14
  2d:   48 89 de                mov    rsi,rbx
  30:   e8 00 00 00 00          call   35 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x35>
            31: R_X86_64_PLT32  memcpy-0x4
  35:   ba 00 08 00 00          mov    edx,0x800
  3a:   48 89 df                mov    rdi,rbx
  3d:   4c 89 fe                mov    rsi,r15
  40:   e8 00 00 00 00          call   45 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x45>
            41: R_X86_64_PLT32  memcpy-0x4
  45:   48 81 c4 00 08 00 00    add    rsp,0x800
  4c:   5b                      pop    rbx
  4d:   41 5e                   pop    r14
  4f:   41 5f                   pop    r15
  51:   c3                      ret    

実装みてもそんな感じしないけど

void swap(T)(ref T lhs, ref T rhs)
if (is(typeof(lhs.proxySwap(rhs))))
{
    lhs.proxySwap(rhs);
}

/// ditto
void swap(T)(ref T lhs, ref T rhs) @trusted pure nothrow @nogc
if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))))
{
    import std.traits : hasAliasing, hasElaborateAssign, isAssignable,
                        isStaticArray;
    static if (hasAliasing!T) if (!__ctfe)
    {
        import std.exception : doesPointTo;
        assert(!doesPointTo(lhs, lhs), "Swap: lhs internal pointer.");
        assert(!doesPointTo(rhs, rhs), "Swap: rhs internal pointer.");
        assert(!doesPointTo(lhs, rhs), "Swap: lhs points to rhs.");
        assert(!doesPointTo(rhs, lhs), "Swap: rhs points to lhs.");
    }

    static if (hasElaborateAssign!T || !isAssignable!T)
    {
        if (&lhs != &rhs)
        {
            static if (__traits(compiles, lhs.tupleof = rhs.tupleof))
            {
                if (__ctfe)
                {
                    // can't reinterpret cast
                    foreach (i, ref e; lhs.tupleof)
                        swap(e, rhs.tupleof[i]);
                    return;
                }
            }

            // For structs with non-trivial assignment, move memory directly
            ubyte[T.sizeof] t = void;
            auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof];
            auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof];
            t[] = a[];
            a[] = b[];
            b[] = t[];
        }
    }
    else
    {
        //Avoid assigning overlapping arrays. Dynamic arrays are fine, because
        //it's their ptr and length properties which get assigned rather
        //than their elements when assigning them, but static arrays are value
        //types and therefore all of their elements get copied as part of
        //assigning them, which would be assigning overlapping arrays if lhs
        //and rhs were the same array.
        static if (isStaticArray!T)
        {
            if (lhs.ptr == rhs.ptr)
                return;
        }

        // For non-elaborate-assign types, suffice to do the classic swap
        static if (__traits(hasCopyConstructor, T))
        {
            // don't invoke any elaborate constructors either
            T tmp = void;
            tmp = lhs;
        }
        else
            auto tmp = lhs;
        lhs = rhs;
        rhs = tmp;
    }
}

なんかうまく最適化してくれそうだからここにきてほしいんだよな。

            // For structs with non-trivial assignment, move memory directly
            ubyte[T.sizeof] t = void;
            auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof];
            auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof];
            t[] = a[];
            a[] = b[];
            b[] = t[];

hasElaborateAssign!T || !isAssignable!Tを満たしてないのか。

import core.int128 : Cent;
import std.algorithm.mutation : swap;
import std.traits : isAssignable, hasElaborateAssign;

struct Huge
{
    Cent[128] data;
    alias this = data;
}

void f(ref Huge x, ref Huge y)
{
    pragma(msg, hasElaborateAssign!Huge);
    pragma(msg, !isAssignable!Huge);
    swap(x, y);
}

だめだった。

$ ldc2 -O -c swap.d
false
false

disable this(this)を足そう。

import core.int128 : Cent;
import std.algorithm.mutation : swap;
import std.traits : isAssignable, hasElaborateAssign;

struct Huge
{
    @disable this(this);
    Cent[128] data;
    alias this = data;
}

void f(ref Huge x, ref Huge y)
{
    pragma(msg, hasElaborateAssign!Huge);
    pragma(msg, !isAssignable!Huge);
    swap(x, y);
}

$ ldc2 -O -c swap.d
true
true

これでいけるかな。

$ objdump -dr --demangle=dlang -Mintel swap.o
(...)
0000000000000000 <swap.f(ref swap.Huge, ref swap.Huge)>:
   0:   48 39 f7                cmp    rdi,rsi
   3:   74 5c                   je     61 <swap.f(ref swap.Huge, ref swap.Huge)+0x61>
   5:   41 57                   push   r15
   7:   41 56                   push   r14
   9:   53                      push   rbx
   a:   48 81 ec 00 08 00 00    sub    rsp,0x800
  11:   48 89 f3                mov    rbx,rsi
  14:   49 89 fe                mov    r14,rdi
  17:   49 89 e7                mov    r15,rsp
  1a:   ba 00 08 00 00          mov    edx,0x800
  1f:   4c 89 ff                mov    rdi,r15
  22:   4c 89 f6                mov    rsi,r14
  25:   e8 00 00 00 00          call   2a <swap.f(ref swap.Huge, ref swap.Huge)+0x2a>
            26: R_X86_64_PLT32  memcpy-0x4
  2a:   be 00 08 00 00          mov    esi,0x800
  2f:   b9 00 08 00 00          mov    ecx,0x800
  34:   41 b8 01 00 00 00       mov    r8d,0x1
  3a:   4c 89 f7                mov    rdi,r14
  3d:   48 89 da                mov    rdx,rbx
  40:   e8 00 00 00 00          call   45 <swap.f(ref swap.Huge, ref swap.Huge)+0x45>
            41: R_X86_64_PLT32  _d_array_slice_copy-0x4
  45:   ba 00 08 00 00          mov    edx,0x800
  4a:   48 89 df                mov    rdi,rbx
  4d:   4c 89 fe                mov    rsi,r15
  50:   e8 00 00 00 00          call   55 <swap.f(ref swap.Huge, ref swap.Huge)+0x55>
            51: R_X86_64_PLT32  memcpy-0x4
  55:   48 81 c4 00 08 00 00    add    rsp,0x800
  5c:   5b                      pop    rbx
  5d:   41 5e                   pop    r14
  5f:   41 5f                   pop    r15
  61:   c3                      ret    
(...)
0000000000000000 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)>:
   0:   48 39 f7                cmp    rdi,rsi
   3:   74 5c                   je     61 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x61>
   5:   41 57                   push   r15
   7:   41 56                   push   r14
   9:   53                      push   rbx
   a:   48 81 ec 00 08 00 00    sub    rsp,0x800
  11:   48 89 f3                mov    rbx,rsi
  14:   49 89 fe                mov    r14,rdi
  17:   49 89 e7                mov    r15,rsp
  1a:   ba 00 08 00 00          mov    edx,0x800
  1f:   4c 89 ff                mov    rdi,r15
  22:   4c 89 f6                mov    rsi,r14
  25:   e8 00 00 00 00          call   2a <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x2a>
            26: R_X86_64_PLT32  memcpy-0x4
  2a:   be 00 08 00 00          mov    esi,0x800
  2f:   b9 00 08 00 00          mov    ecx,0x800
  34:   41 b8 01 00 00 00       mov    r8d,0x1
  3a:   4c 89 f7                mov    rdi,r14
  3d:   48 89 da                mov    rdx,rbx
  40:   e8 00 00 00 00          call   45 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x45>
            41: R_X86_64_PLT32  _d_array_slice_copy-0x4
  45:   ba 00 08 00 00          mov    edx,0x800
  4a:   48 89 df                mov    rdi,rbx
  4d:   4c 89 fe                mov    rsi,r15
  50:   e8 00 00 00 00          call   55 <std.algorithm.mutation.swap!(swap.Huge).swap(ref swap.Huge, ref swap.Huge)+0x55>
            51: R_X86_64_PLT32  memcpy-0x4
  55:   48 81 c4 00 08 00 00    add    rsp,0x800
  5c:   5b                      pop    rbx
  5d:   41 5e                   pop    r14
  5f:   41 5f                   pop    r15
  61:   c3                      ret    
(...)
0000000000000000 <std.algorithm.mutation.swap!(core.int128.Cent[128]).swap(ref core.int128.Cent[128], ref core.int128.Cent[128])>:
   0:   48 39 f7                cmp    rdi,rsi
   3:   74 51                   je     56 <std.algorithm.mutation.swap!(core.int128.Cent[128]).swap(ref core.int128.Cent[128], ref core.int128.Cent[128])+0x56>
   5:   41 57                   push   r15
   7:   41 56                   push   r14
   9:   53                      push   rbx
   a:   48 81 ec 00 08 00 00    sub    rsp,0x800
  11:   48 89 f3                mov    rbx,rsi
  14:   49 89 fe                mov    r14,rdi
  17:   49 89 e7                mov    r15,rsp
  1a:   ba 00 08 00 00          mov    edx,0x800
  1f:   4c 89 ff                mov    rdi,r15
  22:   4c 89 f6                mov    rsi,r14
  25:   e8 00 00 00 00          call   2a <std.algorithm.mutation.swap!(core.int128.Cent[128]).swap(ref core.int128.Cent[128], ref core.int128.Cent[128])+0x2a>
            26: R_X86_64_PLT32  memcpy-0x4
  2a:   ba 00 08 00 00          mov    edx,0x800
  2f:   4c 89 f7                mov    rdi,r14
  32:   48 89 de                mov    rsi,rbx
  35:   e8 00 00 00 00          call   3a <std.algorithm.mutation.swap!(core.int128.Cent[128]).swap(ref core.int128.Cent[128], ref core.int128.Cent[128])+0x3a>
            36: R_X86_64_PLT32  memcpy-0x4
  3a:   ba 00 08 00 00          mov    edx,0x800
  3f:   48 89 df                mov    rdi,rbx
  42:   4c 89 fe                mov    rsi,r15
  45:   e8 00 00 00 00          call   4a <std.algorithm.mutation.swap!(core.int128.Cent[128]).swap(ref core.int128.Cent[128], ref core.int128.Cent[128])+0x4a>
            46: R_X86_64_PLT32  memcpy-0x4
  4a:   48 81 c4 00 08 00 00    add    rsp,0x800
  51:   5b                      pop    rbx
  52:   41 5e                   pop    r14
  54:   41 5f                   pop    r15
  56:   c3                      ret    

ぜんぜんだめ。 (というか_d_array_slice_copyはmemcpyにloweringされてほしいのだがエイリアス情報がないのでだめか。@restrictをつけるとできそうだが。)

sliceのコピーがそもそもだめなのか。

export void myswap(ref Huge lhs, ref Huge rhs)
{
    ubyte[Huge.sizeof] t = void;
    auto a = (cast(ubyte*) &lhs)[0 .. Huge.sizeof];
    auto b = (cast(ubyte*) &rhs)[0 .. Huge.sizeof];
    t[] = a[];
    a[] = b[];
    b[] = t[];  
}

そうらしい。

$ ldc2 -O -c swap.d
$ objdump -dr --demangle=dlang -Mintel swap.o
(...)
0000000000000000 <swap.myswap(ref swap.Huge, ref swap.Huge)>:
   0:   41 57                   push   r15
   2:   41 56                   push   r14
   4:   53                      push   rbx
   5:   48 81 ec 00 08 00 00    sub    rsp,0x800
   c:   48 89 f3                mov    rbx,rsi
   f:   49 89 fe                mov    r14,rdi
  12:   49 89 e7                mov    r15,rsp
  15:   ba 00 08 00 00          mov    edx,0x800
  1a:   4c 89 ff                mov    rdi,r15
  1d:   4c 89 f6                mov    rsi,r14
  20:   e8 00 00 00 00          call   25 <swap.myswap(ref swap.Huge, ref swap.Huge)+0x25>
            21: R_X86_64_PLT32  memcpy-0x4
  25:   be 00 08 00 00          mov    esi,0x800
  2a:   b9 00 08 00 00          mov    ecx,0x800
  2f:   41 b8 01 00 00 00       mov    r8d,0x1
  35:   4c 89 f7                mov    rdi,r14
  38:   48 89 da                mov    rdx,rbx
  3b:   e8 00 00 00 00          call   40 <swap.myswap(ref swap.Huge, ref swap.Huge)+0x40>
            3c: R_X86_64_PLT32  _d_array_slice_copy-0x4
  40:   ba 00 08 00 00          mov    edx,0x800
  45:   48 89 df                mov    rdi,rbx
  48:   4c 89 fe                mov    rsi,r15
  4b:   e8 00 00 00 00          call   50 <swap.myswap(ref swap.Huge, ref swap.Huge)+0x50>
            4c: R_X86_64_PLT32  memcpy-0x4
  50:   48 81 c4 00 08 00 00    add    rsp,0x800
  57:   5b                      pop    rbx
  58:   41 5e                   pop    r14
  5a:   41 5f                   pop    r15
  5c:   c3                      ret    

と思ってみてみたらswapRangesってのがあるのか。

import core.int128 : Cent;
import std.algorithm.mutation : swapRanges;

struct Huge
{
    Cent[128] data;
    alias this = data;
}

void f(ref Huge x, ref Huge y)
{
    swapRanges(x[], y[]);
}

あ、これでいいですね。

0000000000000000 <swap.f(ref swap.Huge, ref swap.Huge)>:
swap.f(ref swap.Huge, ref swap.Huge):
   0:   31 c0                   xor    eax,eax
   2:   66 66 66 66 66 2e 0f    data16 data16 data16 data16 cs nop WORD PTR [rax+rax*1+0x0]
   9:   1f 84 00 00 00 00 00 
  10:   0f 10 04 07             movups xmm0,XMMWORD PTR [rdi+rax*1]
  14:   0f 29 44 24 e8          movaps XMMWORD PTR [rsp-0x18],xmm0
  19:   0f 10 04 06             movups xmm0,XMMWORD PTR [rsi+rax*1]
  1d:   0f 11 04 07             movups XMMWORD PTR [rdi+rax*1],xmm0
  21:   0f 28 44 24 e8          movaps xmm0,XMMWORD PTR [rsp-0x18]
  26:   0f 11 04 06             movups XMMWORD PTR [rsi+rax*1],xmm0
  2a:   0f 10 44 07 10          movups xmm0,XMMWORD PTR [rdi+rax*1+0x10]
  2f:   0f 29 44 24 e8          movaps XMMWORD PTR [rsp-0x18],xmm0
  34:   0f 10 44 06 10          movups xmm0,XMMWORD PTR [rsi+rax*1+0x10]
  39:   0f 11 44 07 10          movups XMMWORD PTR [rdi+rax*1+0x10],xmm0
  3e:   0f 28 44 24 e8          movaps xmm0,XMMWORD PTR [rsp-0x18]
  43:   0f 11 44 06 10          movups XMMWORD PTR [rsi+rax*1+0x10],xmm0
  48:   48 83 c0 20             add    rax,0x20
  4c:   48 3d 00 08 00 00       cmp    rax,0x800
  52:   75 bc                   jne    10 <swap.f(ref swap.Huge, ref swap.Huge)+0x10>
  54:   c3                      ret    

Disassembly of section .text._D3std9algorithm8mutation__T10swapRangesTAS4core6int1284CentTQuZQBkFNaNbNiNfQBjQBmZSQDe8typecons__T5TupleTQCnTQCrZQp:

0000000000000000 <std.algorithm.mutation.swapRanges!(core.int128.Cent[], core.int128.Cent[]).swapRanges(core.int128.Cent[], core.int128.Cent[])>:
std.algorithm.mutation.swapRanges!(core.int128.Cent[], core.int128.Cent[]).swapRanges(core.int128.Cent[], core.int128.Cent[]):
   0:   48 89 f8                mov    rax,rdi
   3:   48 85 f6                test   rsi,rsi
   6:   40 0f 94 c7             sete   dil
   a:   48 85 c9                test   rcx,rcx
   d:   41 0f 94 c1             sete   r9b
  11:   41 08 f9                or     r9b,dil
  14:   75 4d                   jne    63 <std.algorithm.mutation.swapRanges!(core.int128.Cent[], core.int128.Cent[]).swapRanges(core.int128.Cent[], core.int128.Cent[])+0x63>
  16:   31 ff                   xor    edi,edi
  18:   0f 1f 84 00 00 00 00    nop    DWORD PTR [rax+rax*1+0x0]
  1f:   00 
  20:   0f 10 02                movups xmm0,XMMWORD PTR [rdx]
  23:   0f 29 44 24 e8          movaps XMMWORD PTR [rsp-0x18],xmm0
  28:   41 0f 10 00             movups xmm0,XMMWORD PTR [r8]
  2c:   0f 11 02                movups XMMWORD PTR [rdx],xmm0
  2f:   0f 28 44 24 e8          movaps xmm0,XMMWORD PTR [rsp-0x18]
  34:   41 0f 11 00             movups XMMWORD PTR [r8],xmm0
  38:   48 83 c2 10             add    rdx,0x10
  3c:   49 83 c0 10             add    r8,0x10
  40:   4c 8d 14 3e             lea    r10,[rsi+rdi*1]
  44:   4c 8d 4f ff             lea    r9,[rdi-0x1]
  48:   49 83 fa 01             cmp    r10,0x1
  4c:   74 0f                   je     5d <std.algorithm.mutation.swapRanges!(core.int128.Cent[], core.int128.Cent[]).swapRanges(core.int128.Cent[], core.int128.Cent[])+0x5d>
  4e:   4c 8d 14 0f             lea    r10,[rdi+rcx*1]
  52:   49 ff ca                dec    r10
  55:   4c 89 cf                mov    rdi,r9
  58:   4d 85 d2                test   r10,r10
  5b:   75 c3                   jne    20 <std.algorithm.mutation.swapRanges!(core.int128.Cent[], core.int128.Cent[]).swapRanges(core.int128.Cent[], core.int128.Cent[])+0x20>
  5d:   4c 01 c9                add    rcx,r9
  60:   4c 01 ce                add    rsi,r9
  63:   48 89 30                mov    QWORD PTR [rax],rsi
  66:   48 89 50 08             mov    QWORD PTR [rax+0x8],rdx
  6a:   48 89 48 10             mov    QWORD PTR [rax+0x10],rcx
  6e:   4c 89 40 18             mov    QWORD PTR [rax+0x18],r8
  72:   c3                      ret

どうもLLVMは1バイトずつswapする処理をうまく最適化できるらしい。 swapRangesもこのような実装になっている。

Tuple!(InputRange1, InputRange2)
swapRanges(InputRange1, InputRange2)(InputRange1 r1, InputRange2 r2)
if (hasSwappableElements!InputRange1 && hasSwappableElements!InputRange2
    && is(ElementType!InputRange1 == ElementType!InputRange2))
{
    for (; !r1.empty && !r2.empty; r1.popFront(), r2.popFront())
    {
        swap(r1.front, r2.front);
    }
    return tuple(r1, r2);
}

いままでのswapのはなしはなんだったの？なんだったんですかね。。

Conclusion

• 複数のelementがあるデータのswapがしたいときはswapRangesを使おう

Linuxサンドボックス環境の比較 2025年版

あらすじ

近年、supply-chain attackとかこわい。 特にCLIでnpmやらcodexやらclaude codeやらgeminiやら動かすのに裸んぼでは心もとないのではないか。

というわけでナウなLinuxサンドボックスを調べて比較してみる。

比較のやつ

• firejail
• nsjail
• systemd-nspawn
• bubblewrap(bwrap)
• bubblejail
• crabjail
• cage
• landrun

firejail

老舗？のイメージ。 利用方法などはarch wikiがまとまっている。 わりと使いやすい、かつsuid+chroot+namespace+seccomp-bpfという必要なのがそろっている構成で、experimentalだがlandlockサポートも入っている。 じゃあfirejailでいいじゃん、という気もするのだが、そもそもfirejail使うでいいのか？というところが出発点でもある。

余談だがfirejailのコードはけっこう学びが多かった、このhackとかfirejailで知ったはず。

nsjail

officialなやつではないけどgoogleのやつ。 これもけっこう老舗感ある。 あまりfirejailと違わないような？出てきたときはnamespace対応だったり(ns-prefixはそこからきたんだったはず)があったかもしれないけど。 ebpfとかなんかがんばってる雰囲気。けどやっぱりあんまり違いはわからない。

systemd-nspawn

systemd-nspawnはデフォルトで存在しているのでそこは便利なのだが、決して使いやすいものではない。Nix(内部的にsystemd-nspawn使ってる)にするのがどうせならいいけど、これはこれで重い作業なんだよな。

そういえばfirejailは不十分なことがあってsystemd-nspawn(+systemd-run)にしてるってはなしあるけどよくわからんな。

まあでもプロセス隔離ならchroot+Linux namespace+seccomp-bpfでよくて、image buildやらpull/pushとかしたいとかでなければ要らん気もするな。

bubblewrap

flatpackで使われている(sandbox部分を切り出した？)setuidサンドボックス環境。 unshareのラッパーみたいなプリミティブなやつで、下で紹介するbubblejailのほうもあるんだけど、bubblewrap自体もbwrapコマンドでお手軽にサンドボックス環境を作ることはできる。 まあやっぱりfirejailと変わらない雰囲気。

これは直接本論とは関係ないのだが、OCamlのパッケージマネージャであるopamをLinuxで利用する場合にbubblewrapが必要となる(opamはsandbox環境でコマンドを実行することを強制しているのだ、賢い！)

bubblejail

bubblejailは上のbubblewrap(bwrap)の土台にしたもの。 READMEにfirejailとの違いがあって、

firejailの最大の問題点の1つは、誤ってサンドボックス化されていないアプリケーションを実行しても気付かない可能性があることです。 bubblejailは既存のホームディレクトリを透過的に上書きしようとする代わりに独立したホームディレクトリを作成します。 各インスタンスは独立したホームディレクトリを表します。通常、サンドボックス化されたアプリケーションはそれぞれ独自のホームディレクトリを持ちます。

とのこと。 あとまあbwrapは全部引数で渡す必要があるので設定ファイルで分離するとか。

crabjail

これもbubblewrap相当のcrablockというプログラムのラッパーになっている。 crablock自体bubblewrapのようにコマンドとして利用でき、crabjailはcrablockを呼び出す構造になっている。 特徴としてはcrablockも含めてRustで書かれている点とかか。

cage

内部実装にlandlockを使っている。 landlockはこんな話もあって、うーん不十分！ｗという気もする。

クロスプラットフォームなのが特徴といえばそうなのだが、とくに求めていないしな。 macOSの人はこれ使ったらいいと思いました。seatbeltよく知らないけど。

landrun

だいたいcageと同じと思われる。

結論

人類車輪の再発明好きすぎでは？ bubblejailがよさそうな雰囲気あるけどbubblewrapのラッパーを自作するのがいい気がしてきたのでやる(はいまた車輪の再発明を繰り返す)(高速な伏線回収)

プログラミング言語処理系とサポートしているOS・アーキテクチャがどうなっているか

D言語コンパイラのDMDが次のバージョンからBCryptGenRandomを利用するようになる。 これはWindows Vistaから追加されたAPIであるが、ふと各プログラミング言語およびその処理系がどのようにプラットフォームのバージョンを管理・あるいは管理してなかったりするかが気になった。

Python

やや古いもので非公式だがコアコミッターの記載したリストがある。

意外にもWindowsとかばんばんきってる。

Ruby

特定のバージョンについて記載があるわけではないが、各OS/distroに担当者が記載されている。

ミニマムサポートのバージョンについては特に記載がない。

るりまのほうにもプラットフォームの言及があるがメンテされていなさそう。

Rust

プラットフォーム/アーキテクチャごとにTier表にまとめられている。

Linuxやglibcなんかはミニマムサポートバージョンも記載されている箇所があるが、全部についているわけではない(FreeBSDなどは最新のものをサポート？)

Go

OSとアーキテクチャのミニマムサポートバージョンがまとまられている。

バージョンで更新があった際の履歴も残ってるのがいい。

D言語

各コンパイラごとにサポートしているOSとアーキテクチャがまとまっている。

一応まとまってはいるがミニマムサポートは不明。たぶんWindowsは8になると思うが。

• 2024年時点でXPはサポートしていない

Nim

主要なOSとアーキテクチャについては公式サポートをうたっている組み合わせがある。

Windows XPとかMac OS X 10.04(ppc64!)とかほんとにいまだにサポートしてるのか謎。

Windows

• 2022年1月にXP対応の修正パッチが取り込まれている
• 2022年2月に乱数ライブラリのXP対応修正パッチが出ているが、こちらはクローズされている
  • 2021年にsys/randを追加した際にすでにBcryptoAPIが使われていた

標準ライブラリではWindows8が実質のミニマムサポート？

macOS

たぶんだれも気にしてないわこれ。

---

所感

GoとRustは真面目にやっててえらい。 Pythonもいい方なんだけど非公式なんだよな。 他はもっと頑張ってくれ。

各プログラミング言語のWindowsでのMutex実装

特に結論があるわけではなく、よく同じこと調べてしまうので記事にまとめてしまう。

Windowsの各同期APIについてはRust Atomics and Locksのwindows prmitivesの説明も参考に

Mutex(Win32API)派閥

Mutex Objects

Ruby

• CreateMutex使ってる箇所
• critical sectionに移行しようとしたが失敗したらしい

Critical Section派閥

Critical Section Objects

D言語

• D言語は再入ロックであることが暗黙に求められているのもある
  • 元はJava由来と思われる
• XP対応とかはもう考えなくてもいいが

Nim

• NimはREADMEにXPサポートを書いてるので、新しいAPIは使いにくい？
  • といってもちゃんとメンテナがいるわけでもない雰囲気
    • これとか

SRWLock派閥

Zig

• SRWLockのほうがWaitOnAddressより速いらしい
• WaitOnAddressをベースにしたFutex実装もある
  • std.Thread.Futex addition #9070

WaitOnAddress派閥

Waiting on an Address

Rust

• Windows: Implement condvar, mutex and rwlock using futex #121956

最近チャイコフスキーにハマってる

最近チャイコフスキーにハマってる。 というわけで最近聴いた中でよかったなというやつを書き出してみる。

三大バレエ

白鳥の湖

カラヤン&ベルリン・フィルがベスト。 第2曲のワルツは小澤征爾&ボストン交響楽団もよい。

とくによく聴いてる曲目は以下。

• 第1幕:第2曲 ワルツ
• 第2幕:第10曲 情景
• 第2幕:第13曲-D 白鳥の踊り:羽の白鳥の踊り

くるみ割り人形

カラヤン&ベルリン・フィル、小澤征爾&ボストン交響楽団がよい。 ロジェストヴェンスキー&ボリショイ劇場オーケストラもいいけど花のワルツはそんなにだった。 花のワルツはやっぱりカラヤンがベスト。

とくによく聴いてる曲目は以下。

• 第1幕:第1曲 序曲
• 第1幕:第2曲 行進曲
• 第2幕:第12曲-D ロシアの踊り:トレパーク
• 第2幕:第12曲-E 葦笛の踊り
• 第2幕:第13曲 花のワルツ

弦楽セレナード 作品48

小澤征爾&サイトウ・キネン・オーケストラがベスト。 カラヤン&ベルリン・フィルもいい。

交響曲第6番:<悲愴> 第3楽章、第4楽章

チャイコフスキーの交響曲といえば第4番・第5番・第6番がとくに評価が高いが、その中でも第6番:<悲愴>を聴く頻度が高い。

交響曲全般でいえるが、ムラヴィンスキー&レニングラード・フィルハーモニー管弦楽団、カラヤン&ベルリン・フィル、小澤征爾&サイトウ・キネン・オーケストラがよかった。 ムラヴィンスキーのは1960年の録音がよい。 癖はあるけどロジェストヴェンスキーも迫力がある。

ピアノ協奏曲第1番

以下の組み合わせがよかった。

• キーシン & カラヤン with ベルリン・フィル
• アシュケナージ & マゼール with ロンドン交響楽団
• アルゲリッチ & アバド with ベルリン・フィル

SIEVEキャッシュについて

SIEVEというキャッシュアルゴリズムが2023年に発表された。 これはLRUよりシンプルであることを謳っており、実際にかなりシンプルなアルゴリズムだが、S3-FIFOやTinyLFUといった既存の優れたキャッシュアルゴリズムと同等の性能が出るらしい。ただしスキャン耐性などはアルゴリズムのデザインとして入っておらず、あくまでWebキャッシュ(CDNとか)への用途を目的とするものであることに注意。

ちなみにsieveというのは日本語で「篩」という意味で、エラトステネスの篩とかもこれである。

アルゴリズム

SIEVEのウェブサイトの How does SIEVE work? のアニメーションをみればだいたいわかるが、各操作について書き下してみる。

シンプルなアルゴリズムであるが、LRUのようにひとことで説明するのはなかなかむずかしい。論文中で触れられているように、LRUよりもむしろページ置換アルゴリズムで用いられているCLOCKやセカンドチャンス・FIFO-Reinsertionといったキャッシュアルゴリズムに近い。

データ構造

SIEVEキャッシュは、最大容量・キャッシュのサイズ・単一の双方向連結リストとそれをキーで参照するハッシュマップを内部的に持つ。また、連結リストの先頭と末尾、そして各操作(get/insert)の最後に参照したノードへの参照であるハンドを持つ。 また、連結リストの各ノードはキーと値の組・前後のノードへの参照、さらに各ノードへのアクセス状態を記録するvisitedというフラグを持つ。

取得

内部のハッシュマップを経由して、キーに対応したノードが保持する値を取得する。 ノードはvisitedフラグを更新するが、LRUと違って連結リストの順序を並べ替えるような操作は行わない。

挿入

挿入操作は新規にエントリが追加される場合と、すでに存在しているキーと対応する値を更新する場合の二種類がある。

1. 新規にエントリが追加される場合:

   キャッシュが制限容量に達している場合に、いずれかのエントリの削除を行う必要がある。ここのアルゴリズムがSIEVEの肝となる。 この操作は直近で操作を行ったノードへの参照であるハンドから連結リストの先頭に向かってエントリを辿っていく。その最中にvisitedフラグがたっているノードはvisitedフラグをfalseにし、visitedフラグがたっていないノードを見つけたらそのノードを削除して処理を終了する。先頭まで辿っていっても見つからければ末尾に移動して、再度先頭に向かって辿っていく。事前にvisitedフラグをfalseにする操作があるので、二週目で必ず削除対象のノードが出現するようになっている。 論文では、このハンドの位置の持ち方によって古くから生存しているエントリがリストの末尾のほうに集まっていくことが重要としている。

2. 既存のエントリの値を更新する場合:

   この場合は値の更新とvisitedフラグを立てておくだけ。

削除

削除操作はpaperには記載されていないが、基本的にはハッシュマップと連結リストから当該エントリを削除するだけ。

ただし、ハンドが削除対象のエントリを指している場合、削除対象の一つ前のエントリを指すか、削除対象が先頭である場合は末尾を指すようにしたほうがよいと思われる。

各言語の実装

便宜的に各操作で内部的にロックを取得しているものをスレッドセーフな実装と書いてるが、そうでない実装であってもキャッシュに対する操作を自前でロックしてやればよい。

C

• 1a1a11a/libCacheSim
  • 論文著者のリファレンス実装
  • paperの実装に加えて、expireの設定やハッシュマップからの削除を行うかどうかなどのカスタマイズが可能となっている

Go

• scalalang2/golang-fifo
  • スレッドセーフな実装
    • キャッシュへの全操作にロックをとる
  • S3FIFOキャッシュも提供している
  • オリジナルのアルゴリズムに加えてexpireの仕組みが追加されている
  • star数が多い
• opencoff/go-sieve
  • スレッドセーフな実装
    • キャッシュへの全操作にロックをとる

JavaScript(TypeScript)

• kurtextrem/js-sieve
  • 非スレッドセーフな実装

Rust

• jedisct1/rust-sieve-cache
  • 内部的にはロックをとらない、非スレッドセーフな実装
  • encrypted-dns-serverの実装はSieveCacheをスレッドセーフに扱うようにラップしている
    • キャッシュへの操作ができるスレッドを同時に一つに制限している

Java

• linux-china/sieve-cache
  • スレッドセーフな実装

C++

• kassane/sieve-cache-cpp
  • スレッドセーフな実装

D言語

• kubo39/sieve-cache-d
  • スレッドセーフな実装とそうでない実装を提供
  • shared型によってロックを取得する実装としない実装を切り分けている
  • シングルスレッドで不要なロック操作が起きない

Nim

• lost22git/sieve_cache
  • 内部的にはロックをとらない、非スレッドセーフな実装

Ruby

• thelibrarian/sieve_cache
  • スレッドセーフな実装
  • テストがない

Python

• daipham3213/sieve.cache
  • スレッドセーフな実装
  • 他の実装はだいたいMITライセンスだが、これはApache 2.0

Swift

• nixberg/sieve-swift
  • 内部的にはロックをとらない、非スレッドセーフな実装

C

• lostmsu/SIEVE
  • 内部的にはロックをとらない、非スレッドセーフな実装

Elixir

• alanwang67/sieve
  • LICENSEファイルがない

Why my rust program cannot merge string literals?

追記(2025/05/18)

Rust側で対応が入りました。

github.com

以下オリジナル記事

こういう文字列の末尾が共通となるようなRustのコードがある。

fn main() {
    print!("foobar\n");
    print!("bar\n");
}

こうなってしまう。

$ rustc hoge.rs
$ readelf -p .rodata hoge| grep bar
  [     0]  invalid args/rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/fmt/mod.rsfoobar\n
            bar\n

これは当然ふたつめのbar\nが不要なので消えていてほしい。

なぜこうなってしまうのか。

まず文字列リテラルがnull終端でないのが気になる。 少しコードを変更してみよう。

fn main() {
    print!("dummy\n\0");
    print!("foobar\n\0");
    print!("bar\n\0");
}

出力はちょっとましになったが、相変わらず期待した結果にならない。

$ readelf -p .rodata hoge| grep bar
  [    5e]  foobar\n
  [    66]  bar\n

リンカの問題だろうか。lldを試してみよう。

$ rustc -C link-arg=-fuse-ld=lld hoge.rs
$ readelf -p .comment hoge

String dump of section '.comment':
  [     0]  GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
  [    2b]  rustc version 1.75.0 (82e1608df 2023-12-21)
  [    58]  Linker: Ubuntu LLD 14.0.0

$ readelf -p .rodata hoge| grep bar
  [    70]  foobar\n
  [    98]  thread 'extern "bar\n

なんだか変な並びになってわかりにくい。 ちょっと元のコードをいじってわかりやすくする。 あまりよいコードの変更ではないが、とりあえず。

e$ cat hoge.rs
fn main() {
    print!("\0foobar\n\0");
    print!("\0bar\n\0");
}
$ rustc -C link-arg=-fuse-ld=lld hoge.rs
$ readelf -p .rodata hoge| grep bar
  [    58]  foobar\n
  [    61]  bar\n

実はLLDはoptimizeフラグを明示的にいじってやらないとtail-optimized stringsの最適化をやってくれない。

• lld/OutputSections.cpp

static MergeSyntheticSection *createMergeSynthetic(StringRef name,
                                                   uint32_t type,
                                                   uint64_t flags,
                                                   uint32_t addralign) {
  if ((flags & SHF_STRINGS) && config->optimize >= 2)
    return make<MergeTailSection>(name, type, flags, addralign);
  return make<MergeNoTailSection>(name, type, flags, addralign);
}

これを引数に与えてみよう。

$ rustc -C link-arg=-fuse-ld=lld -C link-arg=-O2 hoge.rs
$ readelf -p .rodata hoge| grep bar
  [    58]  foobar\n
  [    61]  bar\n

残念、効果がないみたいだ。

さて、LLDのコードをみてみるとSHF_STRINGSというフラグの有無をみている。 こいつはそのセクションに含まれているものが文字列であることを示す。 また、実はmergeが行われるためにはSHF_MERGEというフラグでmergeableであることを示していなければならない。これもついでにみていこう。

これらはリンク前のセクションについている必要がある。 そのためrustcでリンク前のオブジェクトファイルを生成して、文字列リテラルが含まれているセクションについて確認していく。

$ rustc --emit obj hoge.rs
$ readelf -WS hoge.o
There are 46 section headers, starting at offset 0x1260:

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
(省略)
  [25] .rodata..L__unnamed_2 PROGBITS        0000000000000000 000278 000000 00   A  0   0  8
  [26] .rodata..L__unnamed_7 PROGBITS        0000000000000000 000278 00000c 00   A  0   0  1
  [29] .rodata..L__unnamed_8 PROGBITS        0000000000000000 000298 00004b 00   A  0   0  1
  [32] .rodata..L__unnamed_9 PROGBITS        0000000000000000 000300 000009 00   A  0   0  1
  [35] .rodata..L__unnamed_10 PROGBITS        0000000000000000 000320 000006 00   A  0   0  1

$ readelf -p .rodata..L__unnamed_9 hoge.o

String dump of section '.rodata..L__unnamed_9':
  [     1]  foobar\n

$ readelf -p .rodata..L__unnamed_10 hoge.o

String dump of section '.rodata..L__unnamed_10':
  [     1]  bar\n

フラグを表すのはFlgである。 どうやら文字列リテラルを含んでいるセクションのフラグにはSHF_STRINGSとSHF_MERGEはついてないということがわかった。

実はここでsh_entsizeの値についても確認しておく必要がある。 というのも、リンカはここの値が0の場合mergeableと判定してくれないからだ。

• lld:ELF/InputFiles.cpp

template <class ELFT>
bool ObjFile<ELFT>::shouldMerge(const Elf_Shdr &sec, StringRef name) {
  // On a regular link we don't merge sections if -O0 (default is -O1). This
  // sometimes makes the linker significantly faster, although the output will
  // be bigger.
  //
  // Doing the same for -r would create a problem as it would combine sections
  // with different sh_entsize. One option would be to just copy every SHF_MERGE
  // section as is to the output. While this would produce a valid ELF file with
  // usable SHF_MERGE sections, tools like (llvm-)?dwarfdump get confused when
  // they see two .debug_str. We could have separate logic for combining
  // SHF_MERGE sections based both on their name and sh_entsize, but that seems
  // to be more trouble than it is worth. Instead, we just use the regular (-O1)
  // logic for -r.
  if (config->optimize == 0 && !config->relocatable)
    return false;

  // A mergeable section with size 0 is useless because they don't have
  // any data to merge. A mergeable string section with size 0 can be
  // argued as invalid because it doesn't end with a null character.
  // We'll avoid a mess by handling them as if they were non-mergeable.
  if (sec.sh_size == 0)
    return false;

  // Check for sh_entsize. The ELF spec is not clear about the zero
  // sh_entsize. It says that "the member [sh_entsize] contains 0 if
  // the section does not hold a table of fixed-size entries". We know
  // that Rust 1.13 produces a string mergeable section with a zero
  // sh_entsize. Here we just accept it rather than being picky about it.
  uint64_t entSize = sec.sh_entsize;
  if (entSize == 0)
    return false;

sh_entsizeはreadelf -Sの出力のESに対応する。 各文字列リテラルを含むセクションはここの値が0になっていることがわかる。

なぜそのようなオブジェクトファイルを出力しているのか？というのはrustcのソースコードを読みにいかねばわからない。

まずrustcが生成するLLVM IRを読んで、文字列リテラルがどのような実装になっているかの雰囲気をつかもう。

$ rustc --emit llvm-ir hoge.rs

以下は関係ありそうな箇所を抜粋したもの。

(省略..)
@alloc_33edafb4635cba7fe9b343830eb4d654 = private unnamed_addr constant <{ [9 x i8] }> <{ [9 x i8] c"\00foobar\0A\00" }>, align 1
@alloc_0dc7dcbb24079b5067fcd16f8d1d6fab = private unnamed_addr constant <{ ptr, [8 x i8] }> <{ ptr @alloc_33edafb4635cba7fe9b343830eb4d654, [8 x i8] c"\09\00\00\00\00\00\00\00" }>, align 8
@alloc_82ad759880ed30affa0db4ee70a74cbc = private unnamed_addr constant <{ [6 x i8] }> <{ [6 x i8] c"\00bar\0A\00" }>, align 1
@alloc_170c2fea5b9cc064c6e9c015b7a41c15 = private unnamed_addr constant <{ ptr, [8 x i8] }> <{ ptr @alloc_82ad759880ed30affa0db4ee70a74cbc, [8 x i8] c"\06\00\00\00\00\00\00\00" }>, align 8

ここで、たとえば\0foobar\n\0は@alloc_33edafb4635cba7fe9b343830eb4d654 = private unnamed_addr constant <{ [9 x i8] }> <{ [9 x i8] c"\00foobar\0A\00" }>, align 1のように表現されていることがわかる。

private unnamed_addr constantとはなんぞや？

まずprivateはわかりやすいが、これはlinkage typesで同一モジュール内からのアクセスのみが許可されていることを表す。

unnamed_addrはちょっとわかりにくいが、これはアドレスは重要ではなく内容のみが重要であることを表す。またconstantもこのセクションで説明されているとおりで、まあ定数となる(変更されない)くらいで解釈して問題ない。

次に<{ [9 x i8] }> <{ [9 x i8] c"\00foobar\0A\00" }>, align 1をみてみよう。 まず<{ [9 x i8] }>についてだが、LLVMの型定義をみると、これは要素にarray typeをひとつ含んだpacked struct typeということになる。packedなstruct typeであるので、末尾にalign 1も付与されている。

次に<{ [9 x i8] c"\00foobar\0A\00" }>の意味だが、これはLLVMでの定数を表す表現で、中に文字列定数を一つ格納するstructの定数となる。

と、上記記述をみてみると、Rustの文字列リテラルは文字列定数をひとつ格納するstruct型の定数としてLLVMのGlobal Variableで表現されているようだ。 なのでllvm::GlobalVariableを生成している箇所を追っていこう。

Topic: LDCの場合

Rust側のコードを覗く前に、ここまでちゃんと生成できてない例しかみてないので、そもそもちゃんと動くの？前提が正しいのか？みたいな話がある。 そこで別のLLVMベースのコンパイラ・LDCでみてみる。

まずはそもそもLLDで文字列リテラルのmergeがちゃんと行われているのか？を実験してみよう。

$ cat app.d
import std.stdio;

void main()
{
    writeln("foobar");
    writeln("bar");
}
$ ldc2 --linker=lld app.d
$ readelf -p .rodata app| grep bar
  [   a5b]  foobar
  [   ea6]  bar
$ ldc2 --linker=lld -L-O2 app.d
$ readelf -p .rodata app| grep bar
  [   392]  foobar

リンカオプションに最適化フラグを与えるとちゃんとmergeしてくれていることがわかる。

次にセクションのフラグ情報をみてみる。

$ ldc2 --output-o app.d
$ readelf -WS app.o | grep \.rodata
  [50] .rodata.str1.1    PROGBITS        0000000000000000 0013df 00000b 01 AMS  0   0  1
  [51] .rodata.str1.16   PROGBITS        0000000000000000 0013f0 000169 01 AMS  0   0 16
$ readelf -p .rodata.str1.1 app.o

String dump of section '.rodata.str1.1':
  [     0]  foobar
  [     7]  bar

.rodata.str1.1セクションのsh_entsizeが1に、フラグがAMSになっている(=mergeとstringsがセットされている)ことが確認できた。

これで期待どおりにバイナリを吐いている、ということはわかったが、LDCはできてRustができてないのはなんで？となる。

生成するLLVM IRをみてみよう。

$ ldc2 --output-ll app.d
$ cat app.ll
(省略)
@.str = private unnamed_addr constant [7 x i8] c"foobar\00" ; [#uses = 1]
@.str.1 = private unnamed_addr constant [4 x i8] c"bar\00" ; [#uses = 1]

private unnamed_addr constantだから、Rust同様にLLVMのGlobalVariableな実装になっている。

LDCのコードは比較的追いやすい。

まず、このGlobalVariableを生成している箇所はgen/irstate.cppのgetCachedStringLiteralImpl関数にある。

• ldc:gen/irstate.cpp

template <typename F>
LLGlobalVariable *
getCachedStringLiteralImpl(llvm::Module &module,
                           llvm::StringMap<LLGlobalVariable *> &cache,
                           llvm::StringRef key, F initFactory) {
  auto iter = cache.find(key);
  if (iter != cache.end()) {
    return iter->second;
  }

  LLConstant *constant = initFactory();

  auto gvar =
      new LLGlobalVariable(module, constant->getType(), true,
                           LLGlobalValue::PrivateLinkage, constant, ".str");
  gvar->setUnnamedAddr(LLGlobalValue::UnnamedAddr::Global);

  cache[key] = gvar;

  return gvar;
}

GlobalVariableのコンストラクタの定義は以下のようになっている。

• llvm:include/llvm/IR/GlobalVariable.h

/// GlobalVariable ctor - This creates a global and inserts it before the
  /// specified other global.
  GlobalVariable(Module &M, Type *Ty, bool isConstant, LinkageTypes Linkage,
                 Constant *Initializer, const Twine &Name = "",
                 GlobalVariable *InsertBefore = nullptr,
                 ThreadLocalMode = NotThreadLocal,
                 std::optional<unsigned> AddressSpace = std::nullopt,
                 bool isExternallyInitialized = false);

Type *TyとConstant *Initializerが重要そうだ。 なのでinitFactoryにわたってくる関数をみてみる。D言語の文字列リテラルの場合はgen/llvmhelper.cppのbuildStringLiteralConstant関数が渡されてくる。

• ldc:gen/llvmhelper.cpp

llvm::Constant *buildStringLiteralConstant(StringExp *se,
                                           uint64_t bufferLength) {
  const auto stringLength = se->numberOfCodeUnits();
  assert(bufferLength >= stringLength);

  if (se->sz == 1 && bufferLength <= stringLength + 1) {
    const DString data = se->peekString();
    const bool nullTerminate = (bufferLength == stringLength + 1);
    return llvm::ConstantDataArray::getString(
        gIR->context(), {data.ptr, data.length}, nullTerminate);
  }

  Type *dtype = se->type->toBasetype();
  Type *cty = dtype->nextOf()->toBasetype();
  LLType *ct = DtoMemType(cty);
  LLArrayType *at = LLArrayType::get(ct, bufferLength);

  std::vector<LLConstant *> vals;
  vals.reserve(bufferLength);
  for (uint64_t i = 0; i < stringLength; ++i) {
    vals.push_back(LLConstantInt::get(ct, se->getCodeUnit(i), false));
  }
  const auto nullChar = LLConstantInt::get(ct, 0, false);
  for (uint64_t i = stringLength; i < bufferLength; ++i) {
    vals.push_back(nullChar);
  }
  return LLConstantArray::get(at, vals);
}

文字列リテラルが直接渡されてくる今回の場合は以下のケースだけ着目すればよい。

    const DString data = se->peekString();
    const bool nullTerminate = (bufferLength == stringLength + 1);
    return llvm::ConstantDataArray::getString(
        gIR->context(), {data.ptr, data.length}, nullTerminate);

なのでここではllvm::ConstantDataArrayが返ってきてる。

constant->getType()が返す型はこのArray型の要素となるので、この場合はint8_tになる。

よってこのセクションは、

• 要素の型がint8_tなConstantDataArray型のconstantなGlobalVariable
• 内部のデータはnull終端な文字列リテラル

で構成されている。

rustcコードリーディング

rustcが直接LLVMのGlobalVariableを生成しているコードは二箇所ある。 この2つの関数をrustc_codegen_llvm内でいろいろな箇所から呼んでいる。

• rust:compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp

extern "C" LLVMValueRef
LLVMRustGetOrInsertGlobal(LLVMModuleRef M, const char *Name, size_t NameLen, LLVMTypeRef Ty) {
  Module *Mod = unwrap(M);
  StringRef NameRef(Name, NameLen);

  // We don't use Module::getOrInsertGlobal because that returns a Constant*,
  // which may either be the real GlobalVariable*, or a constant bitcast of it
  // if our type doesn't match the original declaration. We always want the
  // GlobalVariable* so we can access linkage, visibility, etc.
  GlobalVariable *GV = Mod->getGlobalVariable(NameRef, true);
  if (!GV)
    GV = new GlobalVariable(*Mod, unwrap(Ty), false,
                            GlobalValue::ExternalLinkage, nullptr, NameRef);
  return wrap(GV);
}

extern "C" LLVMValueRef
LLVMRustInsertPrivateGlobal(LLVMModuleRef M, LLVMTypeRef Ty) {
  return wrap(new GlobalVariable(*unwrap(M),
                                 unwrap(Ty),
                                 false,
                                 GlobalValue::PrivateLinkage,
                                 nullptr));
}

先にも述べた通り、これらの関数はいろいろな箇所から呼ばれており、逐一探すのは骨が折れる。なのでちょっとアドホックなやり方で特定しよう。

rustcが生成するLLVM IRの出力をちょっと振り返ってみよう。

(省略..)
@alloc_33edafb4635cba7fe9b343830eb4d654 = private unnamed_addr constant <{ [9 x i8] }> <{ [9 x i8] c"\00foobar\0A\00" }>, align 1
@alloc_0dc7dcbb24079b5067fcd16f8d1d6fab = private unnamed_addr constant <{ ptr, [8 x i8] }> <{ ptr @alloc_33edafb4635cba7fe9b343830eb4d654, [8 x i8] c"\09\00\00\00\00\00\00\00" }>, align 8
@alloc_82ad759880ed30affa0db4ee70a74cbc = private unnamed_addr constant <{ [6 x i8] }> <{ [6 x i8] c"\00bar\0A\00" }>, align 1
@alloc_170c2fea5b9cc064c6e9c015b7a41c15 = private unnamed_addr constant <{ ptr, [8 x i8] }> <{ ptr @alloc_82ad759880ed30affa0db4ee70a74cbc, [8 x i8] c"\06\00\00\00\00\00\00\00" }>, align 8

ここで各GlobalVariableの定義は、alloc_xxxxx...のような命名規則になっていることがわかる。 この命名規則を利用しているのは、rustc_codegen_llvm/src/common.rsのscalar_to_backend関数である。

• rust:compiler/rustc_codegen_llvm/src/common.rs

    fn scalar_to_backend(&self, cv: Scalar, layout: abi::Scalar, llty: &'ll Type) -> &'ll Value {
        let bitsize = if layout.is_bool() { 1 } else { layout.size(self).bits() };
        match cv {
            Scalar::Int(int) => { (省略...) }
            Scalar::Ptr(ptr, _size) => {
                let (prov, offset) = ptr.into_parts();
                let (base_addr, base_addr_space) = match self.tcx.global_alloc(prov.alloc_id()) {
                    GlobalAlloc::Memory(alloc) => {
                        let init = const_alloc_to_llvm(self, alloc);
                        let alloc = alloc.inner();
                        let value = match alloc.mutability {
                            Mutability::Mut => self.static_addr_of_mut(init, alloc.align, None),
                            _ => self.static_addr_of(init, alloc.align, None),
                        };
                        if !self.sess().fewer_names() && llvm::get_value_name(value).is_empty() {
                            let hash = self.tcx.with_stable_hashing_context(|mut hcx| {
                                let mut hasher = StableHasher::new();
                                alloc.hash_stable(&mut hcx, &mut hasher);
                                hasher.finish::<Hash128>()
                            });
                            llvm::set_value_name(value, format!("alloc_{hash:032x}").as_bytes());
                        }
                        (value, AddressSpace::DATA)
                    }

llvm::GlobalVariableを生成しているのはstatic_addr_of関数内になる。 (実際の呼び出し階層はstatic_addr_of->static_addr_of_mut->define_private_global(rustc_codegen_llvm/src/declare.rs)->LLVMRustInsertPrivateGlobal(RustWrapper.cpp)のようになっている)

なんでstatic_addr_ofのほうかとわかるのかというと、llvm::LLVMSetGlobalConstant(gv, True);を呼んでるのがこちらのパスだけなので、LLVM IRの内容と照らし合わせるとこちらになるとわかる。

ここまででどのパスでGlobalVariableの生成するかはわかった が型情報をコードから追うのはなかなか大変そうだ。 (追記: 別にそんなことはなかった)

ここの型を決める箇所は以下のコードで常にconst_structを呼び出しており、これはConstStruct型となる。

• rust:compiler/rustc_codegen_llvm/src/consts.rs

pub fn const_alloc_to_llvm<'ll>(cx: &CodegenCx<'ll, '_>, alloc: ConstAllocation<'_>) -> &'ll Value {
    let alloc = alloc.inner();
    let mut llvals = Vec::with_capacity(alloc.provenance().ptrs().len() + 1);
(省略...)
    cx.const_struct(&llvals, true)
}

ここで再びLLVM IRに目を戻してみる。

@alloc_33edafb4635cba7fe9b343830eb4d654 = private unnamed_addr constant <{ [9 x i8] }> <{ [9 x i8] c"\00foobar\0A\00" }>, align 1

ここでLDCでの定義を思い返してみると、ここはarray type(正確にはArrayDataType)だった。これでだんだんみえてきた。ここの型がArray-likeでなければSHF_MERGE/SHF_STRINGSは付与されない、ということだろう。

rustcの中でこれらのフラグをつけているわけではないことがわかったので、ここでLLVMのコード生成側に返ってみよう。

型情報によってmergeable判定を決めている箇所は、LLVMのTargetLoweringObjectFile.cppのgetKindForGlobal関数となっている。

• llvm:lib/Target/TargetLoweringObjectFile.cpp

SectionKind TargetLoweringObjectFile::getKindForGlobal(const GlobalObject *GO,
                                                       const TargetMachine &TM){
(省略...)
      // If initializer is a null-terminated string, put it in a "cstring"
      // section of the right width.
      if (ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
        if (IntegerType *ITy =
              dyn_cast<IntegerType>(ATy->getElementType())) {
          if ((ITy->getBitWidth() == 8 || ITy->getBitWidth() == 16 ||
               ITy->getBitWidth() == 32) &&
              IsNullTerminatedString(C)) {
            if (ITy->getBitWidth() == 8)
              return SectionKind::getMergeable1ByteCString();
            if (ITy->getBitWidth() == 16)
              return SectionKind::getMergeable2ByteCString();

            assert(ITy->getBitWidth() == 32 && "Unknown width");
            return SectionKind::getMergeable4ByteCString();
          }
        }

SectionKind::Mergeable1ByteCStringやSectionKind::Mergeable4ByteCStringを返す条件として、セクションの型が整数型のArrayTypeにキャスト可能な型であること・セクション内の文字列がnull終端となっていることなどが求められている。

これらのSectionKindはSHF_MERGEとSHF_STRINGSに影響することが以下の関数でわかる。

• llvm:lib/CodeGen/TargetLoweringObjectFileImpl.cpp

static unsigned getELFSectionFlags(SectionKind K) {
  unsigned Flags = 0;
(省略...)
  if (K.isMergeableCString() || K.isMergeableConst())
    Flags |= ELF::SHF_MERGE;

  if (K.isMergeableCString())
    Flags |= ELF::SHF_STRINGS;

  return Flags;
}

まとめ

結論としては、Rustは文字列リテラルをLLVMの世界では要素として文字列定数をひとつ持つpacked struct型の定数をグローバル変数として表現するが、LLVMはArray型の定数でかつnull終端である文字列定数しかMerge可能な文字列と判定できないため、文字列リテラルを格納しているセクションにmergeableかつstringsであることを表すフラグを付与できないということになる。

今回Rustが意図してこのような文字列リテラルの実装になっているかまでは調べきることはできなかったが、機会があればまた調査したい。