kubo39's blog

ただの雑記です。

Why my rust program cannot merge string literals?

こういう文字列の末尾が共通となるような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_STRINGSSHF_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_entsizereadelf -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のコンストラクタの定義は以下のようになっている。

/// 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 *TyConstant *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.rsscalar_to_backend関数である。

    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型となる。

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_MERGESHF_STRINGSに影響することが以下の関数でわかる。

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が意図してこのような文字列リテラルの実装になっているかまでは調べきることはできなかったが、機会があればまた調査したい。

ざっくりバイナリ・メモリの世界 for D言語を考えてみた、elfutils便利、そしてcapacityが重い操作というはなし

KOBA789さんのYouTube配信みてて、似たような内容書くとどうなるかな、と考えてたが所有権もライフタイムもどっかいってしまった。。

Hello, World!?

バイナリの気持ちを考えるところから、なのでハードルが高いんだよな。 なんとかついていこう。

import std.stdio;

void main()
{
    writeln("Hello, World!");
}

LDCの以下のバージョンを使うこととする。

$ ldc2 --version| head -2
LDC - the LLVM D compiler (1.36.0):
  based on DMD v2.106.1 and LLVM 17.0.6
$ ldc2 -c hello.d

readelfを使って眺めてみよう。

$ readelf -W -S hello.o
There are 63 section headers, starting at offset 0x4088:

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 000000 00      0   0  0
  [ 1] .strtab           STRTAB          0000000000000000 003228 000e5d 00      0   0  1
  [ 2] .text             PROGBITS        0000000000000000 000040 000000 00  AX  0   0  4
  [ 3] .text._Dmain      PROGBITS        0000000000000000 000040 000019 00  AX  0   0 16
  [ 4] .rela.text._Dmain RELA            0000000000000000 002208 000030 18   I 62   3  8
  [ 5] .text._D3std5stdio__T7writelnTAyaZQnFNfQjZv PROGBITS        0000000000000000 000060 0000c4 00  AX  0   0 16
  [ 6] .rela.text._D3std5stdio__T7writelnTAyaZQnFNfQjZv RELA            0000000000000000 002238 0000a8 18   I 62   5  8
  [ 7] .gcc_except_table._D3std5stdio__T7writelnTAyaZQnFNfQjZv PROGBITS        0000000000000000 000124 000018 00   A  0   0  4
  [ 8] .text.main        PROGBITS        0000000000000000 000140 000028 00  AX  0   0 16
  [ 9] .rela.text.main   RELA            0000000000000000 0022e0 000030 18   I 62   8  8
  [10] .text._D3std5stdio4File17LockingTextWriter__T3putTAyaZQjMFNfMQlZv PROGBITS        0000000000000000 000170 0000ba 00  AX  0   0 16
  [11] .rela.text._D3std5stdio4File17LockingTextWriter__T3putTAyaZQjMFNfMQlZv RELA            0000000000000000 002310 000078 18   I 62  10  8
  [12] .text._D3std5stdio4File17LockingTextWriter__T3putTaZQhMFNfMaZv PROGBITS        0000000000000000 000230 00025b 00  AX  0   0 16
  [13] .rela.text._D3std5stdio4File17LockingTextWriter__T3putTaZQhMFNfMaZv RELA            0000000000000000 002388 000180 18   I 62  12  8
  [14] .text._D3std5stdio__T13trustedFwriteTaZQsFNbNiNePOS4core4stdcQBx8_IO_FILExAaZm PROGBITS        0000000000000000 000490 000030 00  AX  0   0 16
  [15] .rela.text._D3std5stdio__T13trustedFwriteTaZQsFNbNiNePOS4core4stdcQBx8_IO_FILExAaZm RELA            0000000000000000 002508 000018 18   I 62  14  8
  [16] .text._D3std9exception__T7enforceHTCQBcQBb14ErrnoExceptionZ__TQBlTiZQBrFNfiLAxaAyamZi PROGBITS        0000000000000000 0004c0 00006d 00  AX  0   0 16
  [17] .rela.text._D3std9exception__T7enforceHTCQBcQBb14ErrnoExceptionZ__TQBlTiZQBrFNfiLAxaAyamZi RELA            0000000000000000 002520 000018 18   I 62  16  8
  [18] .text._D3std5stdio4File17LockingTextWriter__T3putTAyaZQjMFMQjZ12__dgliteral3MFNaNbNiNfZAxa PROGBITS        0000000000000000 000530 00000d 00  AX  0   0 16
  [19] .text._D3std5stdio4File17LockingTextWriter__T3putTyaZQiMFNfMyaZv PROGBITS        0000000000000000 000540 00025b 00  AX  0   0 16
  [20] .rela.text._D3std5stdio4File17LockingTextWriter__T3putTyaZQiMFNfMyaZv RELA            0000000000000000 002538 000180 18   I 62  19  8
  [21] .text._D3std9exception__T7bailOutHTCQBcQBb14ErrnoExceptionZQBiFNfAyamMAxaZNn PROGBITS        0000000000000000 0007a0 0000c4 00  AX  0   0 16
  [22] .rela.text._D3std9exception__T7bailOutHTCQBcQBb14ErrnoExceptionZQBiFNfAyamMAxaZNn RELA            0000000000000000 0026b8 0000d8 18   I 62  21  8
  [23] .text._D6object__T4idupTxaZQjFNaNbNdNfAxaZAya PROGBITS        0000000000000000 000870 000023 00  AX  0   0 16
  [24] .rela.text._D6object__T4idupTxaZQjFNaNbNdNfAxaZAya RELA            0000000000000000 002790 000018 18   I 62  23  8
  [25] .text._D4core8internal5array11duplication__T4_dupTxaTyaZQmFNaNbNeMAxaZAya PROGBITS        0000000000000000 0008a0 000047 00  AX  0   0 16
  [26] .rela.text._D4core8internal5array11duplication__T4_dupTxaTyaZQmFNaNbNeMAxaZAya RELA            0000000000000000 0027a8 000048 18   I 62  25  8
  [27] .text._D4core8internal5array11duplication__T8_dupCtfeTxaTyaZQqFNaNbNfMAxaZAya PROGBITS        0000000000000000 0008f0 0000cd 00  AX  0   0 16
  [28] .rela.text._D4core8internal5array11duplication__T8_dupCtfeTxaTyaZQqFNaNbNfMAxaZAya RELA            0000000000000000 0027f0 000048 18   I 62  27  8
  [29] .text._D4core8internal5array9appending__T17_d_arrayappendcTXHTAyaTyaZQBcFNaNbNcNeMNkKQxmZQBb PROGBITS        0000000000000000 0009c0 00005c 00  AX  0   0 16
  [30] .rela.text._D4core8internal5array9appending__T17_d_arrayappendcTXHTAyaTyaZQBcFNaNbNcNeMNkKQxmZQBb RELA            0000000000000000 002838 000030 18   I 62  29  8
  [31] .text._D3std3utf__T6strideTAaZQlFNaNfQkZk PROGBITS        0000000000000000 000a20 00006f 00  AX  0   0 16
  [32] .rela.text._D3std3utf__T6strideTAaZQlFNaNfQkZk RELA            0000000000000000 002868 000048 18   I 62  31  8
  [33] .text._D3std3utf__T11decodeFrontVEQBa8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAaZQDnFNaNfKQmZw PROGBITS        0000000000000000 000a90 00001f 00  AX  0   0 16
  [34] .rela.text._D3std3utf__T11decodeFrontVEQBa8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAaZQDnFNaNfKQmZw RELA            0000000000000000 0028b0 000018 18   I 62  33  8
  [35] .text._D3std3utf__T6encodeVEQu8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0ZQDdFNaNfJG1wwZm PROGBITS        0000000000000000 000ab0 0000ca 00  AX  0   0 16
  [36] .rela.text._D3std3utf__T6encodeVEQu8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0ZQDdFNaNfJG1wwZm RELA            0000000000000000 0028c8 000078 18   I 62  35  8
  [37] .text._D3std5range10primitives__T5emptyTAaZQkFNaNbNdNiNfMKQsZb PROGBITS        0000000000000000 000b80 000014 00  AX  0   0 16
  [38] .text._D3std3utf__T11decodeFrontVEQBa8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAaZQDnFNaNeMKQnJmZw PROGBITS        0000000000000000 000ba0 0001ea 00  AX  0   0 16
  [39] .rela.text._D3std3utf__T11decodeFrontVEQBa8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAaZQDnFNaNeMKQnJmZw RELA            0000000000000000 002940 000168 18   I 62  38  8
  [40] .text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFNaQkKmZw PROGBITS        0000000000000000 000d90 0002e9 00  AX  0   0 16
  [41] .rela.text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFNaQkKmZw RELA            0000000000000000 002aa8 000288 18   I 62  40  8
  [42] .text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ10invalidUTFMFNaNbZCQFfQFe12UTFException PROGBITS        0000000000000000 001080 00001e 00  AX  0   0 16
  [43] .rela.text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ10invalidUTFMFNaNbZCQFfQFe12UTFException RELA            0000000000000000 002d30 000030 18   I 62  42  8
  [44] .text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ__T9exceptionTQBbZQpFNaNbNfQBoQDrZCQFuQFt12UTFException PROGBITS        0000000000000000 0010a0 00023c 00  AX  0   0 16
  [45] .rela.text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ__T9exceptionTQBbZQpFNaNbNfQBoQDrZCQFuQFt12UTFException RELA            0000000000000000 002d60 000150 18   I 62  44  8
  [46] .text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ11outOfBoundsMFNaNbZCQFgQFf12UTFException PROGBITS        0000000000000000 0012e0 00001e 00  AX  0   0 16
  [47] .rela.text._D3std3utf__T10decodeImplVbi1VEQBd8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0TAxaZQDrFQiKmZ11outOfBoundsMFNaNbZCQFgQFf12UTFException RELA            0000000000000000 002eb0 000030 18   I 62  46  8
  [48] .text._D3std3utf__T13_utfExceptionVEQBc8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0ZQDmFNaNfQCiwZw PROGBITS        0000000000000000 001300 0000cf 00  AX  0   0 16
  [49] .rela.text._D3std3utf__T13_utfExceptionVEQBc8typecons__T4FlagVAyaa19_7573655265706c6163656d656e744463686172ZQCai0ZQDmFNaNfQCiwZw RELA            0000000000000000 002ee0 0000a8 18   I 62  48  8
  [50] .rodata.str1.1    PROGBITS        0000000000000000 0013cf 00000e 01 AMS  0   0  1
  [51] .rodata.str1.16   PROGBITS        0000000000000000 0013e0 000169 01 AMS  0   0 16
  [52] .data._D5hello12__ModuleInfoZ PROGBITS        0000000000000000 001550 000010 00  WA  0   0  8
  [53] __minfo           PROGBITS        0000000000000000 001560 000008 00 WAR  0   0  8
  [54] .rela__minfo      RELA            0000000000000000 002f88 000018 18   I 62  53  8
  [55] .group            GROUP           0000000000000000 0018f8 00000c 04     62  94  4
  [56] .data.DW.ref._d_eh_personality PROGBITS        0000000000000000 001568 000008 00 WAG  0   0  8
  [57] .rela.data.DW.ref._d_eh_personality RELA            0000000000000000 002fa0 000018 18   G 62  56  8
  [58] .comment          PROGBITS        0000000000000000 001570 000014 01  MS  0   0  1
  [59] .note.GNU-stack   PROGBITS        0000000000000000 001584 000000 00      0   0  1
  [60] .eh_frame         X86_64_UNWIND   0000000000000000 001588 000370 00   A  0   0  8
  [61] .rela.eh_frame    RELA            0000000000000000 002fb8 000270 18   I 62  60  8
  [62] .symtab           SYMTAB          0000000000000000 001908 000900 18      1  37  8
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  R (retain), D (mbind), l (large), p (processor specific)

大量のシンボルが出力されている。

Hello, World!はここにある。

$ readelf -x .rodata.str1.1 hello.o

Hex dump of section '.rodata.str1.1':
  0x00000000 48656c6c 6f2c2057 6f726c64 2100     Hello, World!.

セクション.rodata.str1.1の中に置かれている。

次に実行ファイルをみてみよう。

$ readelf -W -S hello                                                [12/17561]There are 35 section headers, starting at offset 0x119f10:                                                                                                                                                                                              Section Headers:                                                                                                              [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        0000000000000350 000350 00001c 00   A  0   0  1
  [ 2] .note.gnu.property NOTE            0000000000000370 000370 000020 00   A  0   0  8
  [ 3] .note.gnu.build-id NOTE            0000000000000390 000390 000024 00   A  0   0  4
  [ 4] .note.ABI-tag     NOTE            00000000000003b4 0003b4 000020 00   A  0   0  4
  [ 5] .gnu.hash         GNU_HASH        00000000000003d8 0003d8 000024 00   A  6   0  8
  [ 6] .dynsym           DYNSYM          0000000000000400 000400 000ea0 18   A  7   1  8
  [ 7] .dynstr           STRTAB          00000000000012a0 0012a0 000815 00   A  0   0  1
  [ 8] .gnu.version      VERSYM          0000000000001ab6 001ab6 000138 02   A  6   0  2
  [ 9] .gnu.version_r    VERNEED         0000000000001bf0 001bf0 000100 00   A  7   4  8
  [10] .rela.dyn         RELA            0000000000001cf0 001cf0 021138 18   A  6   0  8
  [11] .rela.plt         RELA            0000000000022e28 022e28 000d68 18  AI  6  27  8
  [12] .init             PROGBITS        0000000000024000 024000 00001b 00  AX  0   0  4
  [13] .plt              PROGBITS        0000000000024020 024020 000900 10  AX  0   0 16
  [14] .plt.got          PROGBITS        0000000000024920 024920 000008 08  AX  0   0  8
  [15] .text             PROGBITS        0000000000024930 024930 057670 00  AX  0   0 16
  [16] .fini             PROGBITS        000000000007bfa0 07bfa0 00000d 00  AX  0   0  4
  [17] .rodata           PROGBITS        000000000007c000 07c000 018e57 00   A  0   0 16
  [18] .eh_frame_hdr     PROGBITS        0000000000094e58 094e58 004994 00   A  0   0  4
  [19] .eh_frame         PROGBITS        00000000000997f0 0997f0 013e60 00   A  0   0  8
  [20] .gcc_except_table PROGBITS        00000000000ad650 0ad650 000bc8 00   A  0   0  4
  [21] .tdata            PROGBITS        00000000000af400 0ae400 000008 00 WATo  0   0 16
  [22] .tbss             NOBITS          00000000000af410 0ae408 0001c1 00 WAT  0   0 16
  [23] .init_array       INIT_ARRAY      00000000000af410 0ae410 000040 08  WA  0   0  8
  [24] .fini_array       FINI_ARRAY      00000000000af450 0ae450 000010 08  WA  0   0  8
  [25] .data.rel.ro      PROGBITS        00000000000af460 0ae460 00a470 00  WA  0   0 16
  [26] .dynamic          DYNAMIC         00000000000b98d0 0b88d0 000220 10  WA  7   0  8
  [27] .got              PROGBITS        00000000000b9af0 0b8af0 000510 08  WA  0   0  8
  [28] .data             PROGBITS        00000000000ba000 0b9000 00db70 00  WA  0   0 64
(...)

.rodata.str1.1はなくなってしまっている。 .rodataは実行ファイルを作るときにはマージされてしまう。

そうすると.rodataのどこにあるんだよという話になるが、これをreadelf -x .rodataで探すとなると折り返しとかもあってなかなか探しにくい。

こういう時はelfutilsのreadelfの--stringsオプションが役に立つ。

$ eu-readelf --strings=.rodata hello| grep Hello
  [     0]  Hello, World!

こいつは.rodataセクションの先頭からオフセット0のところにあることがわかる。

$ readelf -x .rodata hello| head

Hex dump of section '.rodata':
  0x0007c000 48656c6c 6f2c2057 6f726c64 21000000 Hello, World!...

ltrace

D言語はlibcのstdioを使っているので、GoやRustのようにwrite(2)をバッファリングするところを自前でもたずにlibcに丸投げしている。

ltraceを単純にかけてみるとわかる。

$ ldc2 hello.d
$ ltrace ./hello
(...)
fwide(0x7fb53048a780, 0)                                                    = 0
flockfile(0x7fb53048a780, 0, 0, 11)                                         = 0
fwrite("Hello, World!", 1, 13, 0x7fb53048a780)                              = 13
fputc_unlocked(10, 0x7fb53048a780, 0x5616b898eabc, 0x5616b716800dHello, World!
)          = 10                                                                                                             funlockfile(0x7fb53048a780, 0x5616b898eab0, 0xffffffff, 0x7fb530384697)     = 1
(...)

改行込みなのでwrite(2)に渡すのは長さ14になるが、fwrite(3)には長さ13にない。 その下でfputc_unlockedが改行を入れてるのだが、libc内でバッファリングしてるためwrite(2)に渡すときはちゃんと一度に渡せるのだ。

スタック/ヒープ?

ヒープはGCってやつがなんとかしてくれるらしいです(は?)

エイリアス

デフォルト?だと代入構文はポインタのエイリアスになる。 だいたいの言語はそうだろという気になってしまうが、Rust(ムーヴセマンティクス)やNim(デフォルトだとコピーになってそれぞれの変数は別のメモリアドレスへの参照になる)なんかもある。

再割り当てが起きたタイミングで別のメモリアドレスを指し示す。

このへんはGCがうまくやってくれている。

import std.stdio;

void main()
{
    auto a = [1, 2, 3];
    auto b = a;
    assert(a is b);
    b ~= 4;
    writeln(a);  // [1, 2, 3]
    writeln(b);  // [1, 2, 3, 4]
    assert(a !is b);
}

再割り当てが起きない場合は?

先頭のアドレスは同じでも長さ情報が異なるので同値性判定はfalseになる。 このあたりはランタイムが面倒をみてくれる。

import std.stdio;

void main()
{
    auto a = [1, 2, 3];
    auto b = a;
    assert(a is b);
    b = b[0..2];
    writeln(a);  // [1, 2, 3]
    writeln(b);  // [1, 2]
    assert(a.ptr == b.ptr);
    assert(a !is b);  // 長さが異なるので同値性判定はfalse
   
}

あとついでに書いとくとCoWとかではない。

import std.stdio;

void main()
{
    int[] a = [1, 2];
    auto b = a;
    b[0] = 42;
    writeln(a);  // [42, 2]
}

コピー

思ったより書くこと思いつかなくてびっくりした(オワリ)

auto b = a.dup;  // コピー
auto c = a.idup; // immutableなコピー

いやそんなことはないのだが、コピーコンストラクタとか@disable thisとか、そのへんもあるので割愛する。

realloc

動的配列について考えてみよう。

こんな感じのデータがスタック上に置かれてるイメージ。 まああとでわかります。

struct DArray
{
    size_t length;
    void* ptr;
}

以下のようなコードを実行してみる。

import std.stdio;

void f()
{
    int[] s = [1, 2, 3, 4, 5];
    writefln("s = %s", s);

    writeln("s.sizeof: ", s.sizeof);  // --> 16

    writeln("&s: ", &s);
    writeln("*cast(size_t*) &s: ", *cast(size_t*) &s);  // .length
    writeln("*((cast(size_t**) &s) + 1): ", *((cast(size_t**) &s) + 1));  // .ptr

    writeln("&s[0]: ", &s[0]);
    writeln("s.ptr: ", s.ptr);

    writeln("s.length: ", s.length);
    writeln("s.capacity: ", s.capacity);

    // realloc
    s ~= [6, 7, 8];
    writefln("s = %s", s);

    writeln("s.sizeof: ", s.sizeof);  // --> 16

    writeln("&s: ", &s);
    writeln("&s[0]: ", &s[0]);
    writeln("s.ptr: ", s.ptr);

    writeln("s.length: ", s.length);
    writeln("s.capacity: ", s.capacity);
}

void main()
{
    f();
}
$ ldc2 -run main.d
s = [1, 2, 3, 4, 5]
s.sizeof: 16
&s: 7FFE9ACCA400
*cast(size_t*) &s: 5
*((cast(size_t**) &s) + 1): 7FA7F0609000
&s[0]: 7FA7F0609000
s.ptr: 7FA7F0609000
s.length: 5
s.capacity: 7
s = [1, 2, 3, 4, 5, 6, 7, 8]
s.sizeof: 16
&s: 7FFE9ACCA400
&s[0]: 7FA7F060A000
s.ptr: 7FA7F060A000
s.length: 8
s.capacity: 11
  • &sは再割り当て前後で変わっていない(スタック)
  • s.ptrは変わってる
    • reallocが起きたのでもちろん変わる
    • 元のヒープはGCがfreeしてくれる(デフォルトのGCだと割り当てタイミング)
  • s.lengthは変わってる
    • だれかがスタック上の値を書き換えてる!
  • s.capacityはスタック上にない!

てきとうなコードでLLVM-IRみてみる。

pragma(mangle, "foo")
void foo()
{
    int[] s = [1, 2, 3, 4, 5];
    s ~= [6, 7, 8];
}

コンパイルするぞい。

$ ldc2 -O2 --output-ll lowered.d

するとこんなIRになる。

; Function Attrs: uwtable
define void @foo() local_unnamed_addr #0 {
if.i:
  %pxx.i.i = alloca { i64, ptr }, align 8         ; [#uses = 6, size/byte = 16]
  %.gc_mem = tail call { i64, ptr } @_d_newarrayU(ptr nonnull @_D11TypeInfo_Ai6__initZ, i64 5) #1 ; [#uses = 1]
  %.ptr = extractvalue { i64, ptr } %.gc_mem, 1   ; [#uses = 3]
  store <4 x i32> <i32 1, i32 2, i32 3, i32 4>, ptr %.ptr, align 4
  %0 = getelementptr inbounds [5 x i32], ptr %.ptr, i64 0, i64 4 ; [#uses = 1, type = ptr]
  store i32 5, ptr %0, align 4
  call void @llvm.lifetime.start.p0(i64 16, ptr nonnull %pxx.i.i)
  store i64 5, ptr %pxx.i.i, align 8
  %1 = getelementptr inbounds { i64, ptr }, ptr %pxx.i.i, i64 0, i32 1 ; [#uses = 2, type = ptr]
  store ptr %.ptr, ptr %1, align 8
  %2 = call { i64, ptr } @_d_arrayappendcTX(ptr nonnull @_D11TypeInfo_Ai6__initZ, ptr nonnull dereferenceable(16) %pxx.i.i, i64 3) #3 ; [#uses = 0]
  %.ptr1.i.i = load ptr, ptr %1, align 8          ; [#uses = 3]
  %.len2.i.i = load i64, ptr %pxx.i.i, align 8    ; [#uses = 2]
  call void @llvm.lifetime.end.p0(i64 16, ptr nonnull %pxx.i.i)
  %bounds.cmp.i = icmp ugt i64 %.len2.i.i, 5      ; [#uses = 1]
  br i1 %bounds.cmp.i, label %bounds.ok6.i, label %bounds.fail.i

bounds.ok6.i:                                     ; preds = %if.i
  %3 = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 5 ; [#uses = 1, type = ptr]
  store i32 6, ptr %3, align 1
  %__arrayliteral_on_stack3.sroa.2.0..sroa_idx = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 6 ; [#uses = 1, type = ptr]
  store i32 7, ptr %__arrayliteral_on_stack3.sroa.2.0..sroa_idx, align 1
  %__arrayliteral_on_stack3.sroa.3.0..sroa_idx = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 7 ; [#uses = 1, type = ptr]
  store i32 8, ptr %__arrayliteral_on_stack3.sroa.3.0..sroa_idx, align 1
  ret void

bounds.fail.i:                                    ; preds = %if.i
  call void @_d_arraybounds_index({ i64, ptr } { i64 75, ptr @.str }, i32 95, i64 5, i64 %.len2.i.i) #2
  unreachable
}

ランタイムの気持ちを考えてグっと睨むと

  • _d_newarrayUがlengthとptrの組を返してる(これがスタックにおかれてる)
  • _d_arrayappendcTXで再割り当てをしている
    • この関数がスタック上の.lengthの値を書き換えていた
  • capacity分の容量確保はどちらも__arrayAllocでやってる

のようなことがわかる。

capacityは?

こいつ結局スタックいないじゃん。

じゃあちょっとコード変えてみるか。

pragma(mangle, "foo")
auto foo()
{
    int[] s = [1, 2, 3, 4, 5];
    s ~= [6, 7, 8];
    return s.capacity();
}

こんなLLVM IRを吐く。

define i64 @foo() local_unnamed_addr #0 {
if.i:
  %arr.i = alloca { i64, ptr }, align 8           ; [#uses = 5, size/byte = 16]
  %pxx.i.i = alloca { i64, ptr }, align 8         ; [#uses = 6, size/byte = 16]
  %.gc_mem = tail call { i64, ptr } @_d_newarrayU(ptr nonnull @_D11TypeInfo_Ai6__initZ, i64 5) #1 ; [#uses = 1]
  %.ptr = extractvalue { i64, ptr } %.gc_mem, 1   ; [#uses = 3]
  store <4 x i32> <i32 1, i32 2, i32 3, i32 4>, ptr %.ptr, align 4
  %0 = getelementptr inbounds [5 x i32], ptr %.ptr, i64 0, i64 4 ; [#uses = 1, type = ptr]
  store i32 5, ptr %0, align 4
  call void @llvm.lifetime.start.p0(i64 16, ptr nonnull %pxx.i.i)
  store i64 5, ptr %pxx.i.i, align 8
  %1 = getelementptr inbounds { i64, ptr }, ptr %pxx.i.i, i64 0, i32 1 ; [#uses = 2, type = ptr]
  store ptr %.ptr, ptr %1, align 8
  %2 = call { i64, ptr } @_d_arrayappendcTX(ptr nonnull @_D11TypeInfo_Ai6__initZ, ptr nonnull dereferenceable(16) %pxx.i.i, i64 3) #3 ; [#uses = 0]
  %.ptr1.i.i = load ptr, ptr %1, align 8          ; [#uses = 4]
  %.len2.i.i = load i64, ptr %pxx.i.i, align 8    ; [#uses = 3]
  call void @llvm.lifetime.end.p0(i64 16, ptr nonnull %pxx.i.i)
  %bounds.cmp.i = icmp ugt i64 %.len2.i.i, 5      ; [#uses = 1]
  br i1 %bounds.cmp.i, label %bounds.ok6.i, label %bounds.fail.i

bounds.ok6.i:                                     ; preds = %if.i
  %3 = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 5 ; [#uses = 1, type = ptr]
  store i32 6, ptr %3, align 1
  %__arrayliteral_on_stack3.sroa.2.0..sroa_idx = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 6 ; [#uses = 1, type = ptr]
  store i32 7, ptr %__arrayliteral_on_stack3.sroa.2.0..sroa_idx, align 1
  %__arrayliteral_on_stack3.sroa.3.0..sroa_idx = getelementptr inbounds i32, ptr %.ptr1.i.i, i64 7 ; [#uses = 1, type = ptr]
  store i32 8, ptr %__arrayliteral_on_stack3.sroa.3.0..sroa_idx, align 1
  call void @llvm.lifetime.start.p0(i64 16, ptr nonnull %arr.i)
  store i64 %.len2.i.i, ptr %arr.i, align 8
  %arr_arg.fca.1.gep.i = getelementptr inbounds { i64, ptr }, ptr %arr.i, i64 0, i32 1 ; [#uses = 1, type = ptr]
  store ptr %.ptr1.i.i, ptr %arr_arg.fca.1.gep.i, align 8
  %4 = call i64 @_d_arraysetcapacity(ptr nonnull @_D11TypeInfo_Ai6__initZ, i64 0, ptr nonnull %arr.i) #3 ; [#uses = 1]
  call void @llvm.lifetime.end.p0(i64 16, ptr nonnull %arr.i)
  ret i64 %4

bounds.fail.i:                                    ; preds = %if.i
  call void @_d_arraybounds_index({ i64, ptr } { i64 75, ptr @.str }, i32 95, i64 5, i64 %.len2.i.i) #2
  unreachable
}

_d_arraysetcapacity??

こいつの新たにセットするcapacityに0を渡してることがわかる。現在のcapacity情報は配列の実体が割り当てられてるGCのblkinfoから毎回計算してるのだ。

まとめ

  • eu-readelfはときどき便利!
  • 代入のセマンティクスはデフォルトだと参照のエイリアス
  • 再割り当てが起きると指し示すメモリアドレスが変わる
  • capacityは意外と重い操作!
  • もう全部GCに任せたらええ!(ほんまか?(小声))

追記(2024/01/30)

これGNU binutilsのreadelfの-pオプションでいいな。elfutils便利とはなんだったのか。。

$ readelf -p .comment hello

String dump of section '.comment':
  [     0]  GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
  [    2b]  ldc version 1.36.0
  [    3e]  clang version 15.0.6

LDC: LLVMとmemcpyとRVOのはなし

Addressing Rust optimization failures in LLVMのはなしで、これがLDCだとどうなるか。

以下のようなコードでどうなるかみてみる。 このコードはRustのcodegen testを移植したもの。

import std.algorithm : sum;

pragma(mangle, "ThreeSlices")
struct ThreeSlices
{
    uint[] a;
    uint[] b;
    uint[] c;
}

pragma(mangle, "sum_slices")
uint sum_slices(immutable ThreeSlices val)
{
    immutable val2 = val;
    return sum(val2);
}

pragma(inline, false)
pragma(mangle, "sum")
uint sum(immutable ref ThreeSlices val)
{
    return val.a.sum + val.b.sum + val.c.sum;
}

コンパイラがちゃんとLLVM17でビルドされてるか確認。

$ ldc2 --version | head -2
LDC - the LLVM D compiler (1.36.0):
  based on DMD v2.106.1 and LLVM 17.0.6
ldc2 -O2 --output-ll app.d

生成されるLLVM IRは以下のようになった。

(...)
; Function Attrs: nofree nosync nounwind memory(read, argmem: readwrite, inaccessiblemem: none) uwtable
define i32 @sum_slices(ptr nocapture readonly byval(%app.ThreeSlices) align 8 %val) local_unnamed_addr #2 {
  %val2 = alloca %app.ThreeSlices, align 8        ; [#uses = 2, size/byte = 48]
  call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 8 dereferenceable(48) %val2, ptr noundef nonnull align 8 dereferenceable(48) %val, i64 48, i1 false)
  %1 = call i32 @sum(ptr nonnull dereferenceable(48) %val2) #8 ; [#uses = 1]
  ret i32 %1
}
(...)

Rustのようにならなかった理由としてはnoalias attributeが付与されていないためである。この最適化が効くためにはnoaliasとnocaptureが付与されてなければならない。

これはimmutableなポインタにnoaliasを付与するPRが入ることで解決する。

実際にそうなるか確認してみよう。 現在リリースされているLDCではldc.attributes.restrictをつけることで同じ挙動にできる。

import std.algorithm : sum;
import ldc.attributes : restrict;

pragma(mangle, "ThreeSlices")
struct ThreeSlices
{
    uint[] a;
    uint[] b;
    uint[] c;
}

pragma(mangle, "sum_slices")
uint sum_slices(@restrict immutable ThreeSlices val)
{
    immutable val2 = val;
    return sum(val2);
}

pragma(inline, false)
pragma(mangle, "sum")
uint sum(immutable ref ThreeSlices val)
{
    return val.a.sum + val.b.sum + val.c.sum;
}

同じコンパイルオプションでビルドするとちゃんとmemcpyが排除されることが確認できる。

(...)
; [#uses = 0]
; Function Attrs: nofree nosync nounwind memory(read, argmem: readwrite, inaccessiblemem: none) uwtable
define i32 @sum_slices(ptr noalias nocapture readonly byval(%app.ThreeSlices) align 8 %val) local_unnamed_addr #2 {
  %1 = call i32 @sum(ptr nonnull dereferenceable(48) %val) #7 ; [#uses = 1]
  ret i32 %1
}
(...)

実はLDCにはこれ以外にもnoaliasが付与される条件がある。 RVOが適用されるとき、ポインタにnoaliasがつく。

そのため、以下のようなコードでもmemcpyを除去できる。 (ただしこんなコードを書いてはいけない)

import std.algorithm : sum;
import ldc.attributes : restrict;

pragma(mangle, "ThreeSlices")
struct ThreeSlices
{
    uint[] a;
    uint[] b;
    uint[] c;
}

uint gSum;

pragma(mangle, "sum_slices")
ThreeSlices sum_slices()
{
    ThreeSlices val = void;
    auto val2 = val;
    gSum = sum(val2);
    return val;
}

pragma(inline, false)
pragma(mangle, "sum")
uint sum(ref ThreeSlices val)
{
    return val.a.sum + val.b.sum + val.c.sum;
}

このコードをコンパイルすると以下のようなLLVM IRになることが確認できる。

; [#uses = 0]
; Function Attrs: nofree nosync nounwind memory(readwrite, inaccessiblemem: none) uwtable
define void @sum_slices(ptr noalias nocapture readonly sret(%app.ThreeSlices) align 8 %.sret_arg) local_unnamed_addr #2 {
  %1 = tail call i32 @sum(ptr nonnull dereferenceable(48) %.sret_arg) #7 ; [#uses = 1]
  store i32 %1, ptr @_D3app4gSumk, align 4
  ret void
}

これはRVOが適用されたときのみ起きるので、明示的に変換後のようなコードを渡すと効果はない。

// sum_slicesをこのように書き換えてもだめ
pragma(mangle, "sum_slices")
void sum_slices(ref ThreeSlices val)
{
    auto val2 = val;
    gSum = sum(val2);
}
(...)

結果を確認するとmemcpyが生成されている。

(...)
; Function Attrs: nofree nosync nounwind memory(readwrite, inaccessiblemem: none) uwtable
define void @sum_slices(ptr nocapture readonly dereferenceable(48) %val) local_unnamed_addr #2 {
  %val2 = alloca %app.ThreeSlices, align 8        ; [#uses = 2, size/byte = 48]
  call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 8 dereferenceable(48) %val2, ptr noundef nonnull align 1 dereferenceable(48) %val, i64 48, i1 false)
  %1 = call i32 @sum(ptr nonnull dereferenceable(48) %val2) #8 ; [#uses = 1]
  store i32 %1, ptr @_D3app4gSumk, align 4
  ret void
}
(...)

2024やりたいこと

とくに毎年振り返りとかしてないしできてないし意味あるんかな。。

LDCのxtensa対応してマイクロマウス

Pi:Co V2という練習用のマイクロマウスがあるそうで、 これはCPUにESP32-S3、そして組み立て済なのでたぶんハンダとかなしでできる。ほんまかな。

それなら自分でも遊べそうだな、というわけでLDCのxtensa対応へのモチベーションが出てきた。

LLVMのxtensaバックエンド対応はすでにupstreamに取り込まれているのであとはLDC側で詰まりポイントがなければそんなに時間はかからないはず。

詰まりポイントとしてはABI対応くらいか。

ほっといたら先にだれかが対応してくれるかもしれない、それでもぜんぜんいいな。

LDC internals

まだどういった内容を書くか決めてないけど、LDC internalsをちまちま書いていく予定。

HinaOSのD言語移植

別言語での再実装のおすすめ選択肢にはあがってないが、まあできるだろう。 できるというのがみえてるので逆にめんどくさいという部分もあるが(は?)、実際にやると意外なところで問題にぶちあたったりするのが世の常なので実際にやるのとでは雲泥の差があるものです。

当面は1000行OSのほうで疑問点を出し尽くしてしまうか。

各言語処理系からみるLLVMインラインアセンブラ、主にmemory clobberについて

雑メモです。LLVMの実装追いきれてないからなんか間違ってたら、、スマンコ!w

前提

LLVMインラインアセンブラCodeGenの実体としてはnaked function相当。そのため、codegenには関数属性なんかを渡しているし、ジッサイこれが最適化に効いている!

また、RustのドキュメントによるとLLVMインラインアセンブラはmemory clobber(~{memory}的なやつ)をconstraintsとして渡しても無視する。

(一応LLVMの公式ドキュメントにはそれらしい話が書いているが、後述のclangとRustの実装をみる感じではあてにしていなさそうだ)、かわりにmemory constraintがひとつでもあればread/write memoryが起きていると仮定している。

(追記: LLVMでclobberのチェックを行っている箇所のコードではやはりレジスタについてしかチェックしていないようだ)

その代わりに相当する関数属性を付与する(デフォルトで与えられるReadWriteMemory属性)ことで同様の機能を実現している。

LLVMの関数属性のそれぞれの意味は下のリンクを都度参照。

LLVMの関数属性: https://llvm.org/docs/LangRef.html#function-attributes

clang

LLVMに渡している箇所は以下のようになっている。

https://github.com/llvm/llvm-project/blob/6ce23ea0ab6370c944f5e426a20217f93f41aa15/clang/lib/CodeGen/CGStmt.cpp#L2840C1-L2842C63

  llvm::InlineAsm *IA = llvm::InlineAsm::get(
      FTy, AsmString, Constraints, HasSideEffect,
      /* IsAlignStack */ false, AsmDialect, HasUnwindClobber);

ざっくり

  • HasSideEffect: volatile相当
  • IsAlignStack: スタックポインタがalignされてることの保証
  • AsmDialect: AT&T記法かIntel記法か
  • HasUnwindClobber: throwできるか

LLVMを呼ぶところで常にIsAlignStack=falseになっているのが特徴。

memory clobberに関してclangの場合はどうしてるかというと、自前でパースした際にReadOnly/ReadNoneの変数をfalseにセットしている。

https://github.com/llvm/llvm-project/blob/6ce23ea0ab6370c944f5e426a20217f93f41aa15/clang/lib/CodeGen/CGStmt.cpp#L2770

    if (Clobber == "memory")
      ReadOnly = ReadNone = false;

この変更が入ったパッチをみると、

Currently, clang/llvm handles inline-asm instructions in a very conservative manner, choosing not to eliminate the instructions or hoisting them out of a loop even when it's safe to do so. This patch makes changes to clang to attach a readonly or readnone attribute to an inline-asm instruction, which enables passes such as LICM and EarlyCSE to move or optimize away the instruction.

とあり、後述のコメントで参照されているGCCドキュメントの文言:

The "memory" clobber tells the compiler that the assembly code performs memory reads or writes to items other than those listed in the input and output operands (for example, accessing the memory pointed to by one of the input parameters).

I took it to mean that you have to add "memory" to an inline-asm statement's clobber list in the case it reads from memory using one of the input registers. If you don't, gcc will treat it as a read-none statement.

asm ("movl (%1), %0" : "=r" (res) : "r" (ptr) : "memory");

と合わせて、これはLLVMインラインアセンブラではmemory clobberは効果がないとみてよさそうだ。

これらの変数は関数属性の付与に使われる。

  // An inline asm can be marked readonly if it meets the following conditions:
  //  - it doesn't have any sideeffects
  //  - it doesn't clobber memory
  //  - it doesn't return a value by-reference
  // It can be marked readnone if it doesn't have any input memory constraints
  // in addition to meeting the conditions listed above.
  bool ReadOnly = true, ReadNone = true;

volatileを付与している場合はmemory clobberは常に付与されているとみなしてもよさそう。

  // Attach readnone and readonly attributes.
  if (!HasSideEffect) {
    if (ReadNone)
      Result.setDoesNotAccessMemory();
    else if (ReadOnly)
      Result.setOnlyReadsMemory();
  }

Rust

Rustは独自のasm!構文を持っている: https://doc.rust-lang.org/reference/inline-assembly.html

LLVMに渡してるところはここ

extern "C" LLVMValueRef
LLVMRustInlineAsm(LLVMTypeRef Ty, char *AsmString, size_t AsmStringLen,
                  char *Constraints, size_t ConstraintsLen,
                  LLVMBool HasSideEffects, LLVMBool IsAlignStack,
                  LLVMRustAsmDialect Dialect, LLVMBool CanThrow) {
  return wrap(InlineAsm::get(unwrap<FunctionType>(Ty),
                             StringRef(AsmString, AsmStringLen),
                             StringRef(Constraints, ConstraintsLen),
                             HasSideEffects, IsAlignStack,
                             fromRust(Dialect), CanThrow));
}

以下のコメントにあるように、LLVMはmemory constraintを解釈しない。

        if !options.contains(InlineAsmOptions::NOMEM) {
            // This is actually ignored by LLVM, but it's probably best to keep
            // it just in case. LLVM instead uses the ReadOnly/ReadNone
            // attributes on the call instruction to optimize.
            constraints.push("~{memory}".to_string());
        }

NOMEMが指定された場合どうするかというと、関数属性に渡すMemoryEffectsが変わっている。LLVMはこの関数属性をみて最適化可能性を判断する。(Rustのasm!オプションPURE=volatile相当とかは別口だけど)

        let mut attrs = SmallVec::<[_; 2]>::new();
        if options.contains(InlineAsmOptions::PURE) {
            if options.contains(InlineAsmOptions::NOMEM) {
                attrs.push(llvm::MemoryEffects::None.create_attr(self.cx.llcx));
            } else if options.contains(InlineAsmOptions::READONLY) {
                attrs.push(llvm::MemoryEffects::ReadOnly.create_attr(self.cx.llcx));
            }
            attrs.push(llvm::AttributeKind::WillReturn.create_attr(self.cx.llcx));
        } else if options.contains(InlineAsmOptions::NOMEM) {
            attrs.push(llvm::MemoryEffects::InaccessibleMemOnly.create_attr(self.cx.llcx));
        } else {
            // LLVM doesn't have an attribute to represent ReadOnly + SideEffect
        }
        attributes::apply_to_callsite(result, llvm::AttributePlace::Function, &{ attrs });

以下のコードはC言語のinline assemblyとLLVMの関数属性の対応でいうと、

  • volatileなし + memory clobberなし: READ_NONE + WILL_RETURN
  • volatileなし + memory clobberあり
    • RustのREADONLYオプションあり: READ_ONLY + WILL_RETURN
    • RustのREADONLYオプションなし: WILL_RETURN
  • volatileあり + memory clobberなし: InAccessibleMemOnly
  • volatileあり + memory clobberあり: ReadWriteMemory (デフォルト)

と、実に細かく設定できる。

Rustはclangと違い、デフォルトでは IsAlignStack=true に設定している。

https://github.com/rust-lang/rust/blob/558ac1cfb7c214d06ca471885a57caa6c8301bae/compiler/rustc_codegen_llvm/src/asm.rs#L275

        let alignstack = !options.contains(InlineAsmOptions::NOSTACK);

ここの設計判断はこのコメントが詳しく解説している。

また、他のassembly構文にない特徴として preserves_flags というオプションを渡すことができる。Rustはデフォルトで各アーキテクチャのflagレジスタをconstraintsに追加するようになっており、このオプションを追加することでその機能を無効にできる。

総論として、Rustはasm!構文でC言語とは異なる構文を設定しておりデフォルトで安全側に倒すような設計としつつ、最適化について細かく制御可能となっている。

LDC

https://wiki.dlang.org/LDC_inline_assembly_expressions

LDCは常に sideeffect = true を渡しているのでいわゆるvolatile相当が常に付与されている状態となっている。

  // build asm call
  bool sideeffect = true;
  llvm::InlineAsm *ia = llvm::InlineAsm::get(FT, code, constraints, sideeffect);

また、LDCは関数属性をデフォルトからいじるようなことはしていないので、memory clobberをつけなくても同様の効果(ReadWriteMemory属性)にはなる(clangのように自前でパースしてどうこう、というようなことはやらない)。

安全側に倒した実装になっているが、最適化を細かくやる余地は残されていない。

まとめ

いかがでしたか? 個人的には、LLVMインラインアセンブラ実装けっこう思ってたんとちがう!って感じで調べてておもしろかったです。

Writing OS in 1000 lines をD言語でやった

Writing an OS in 1000 Linesという自作OSを学ぶための教材があり、これをD言語(LDCコンパイラ)で行った記録です。

先行事例

他言語実装という枠では、RustやZigですでにやられている方がいました。

Rust

Zig

成果物

レポジトリはココです。オリジナル同様に ./run.sh で起動するようになっています。

記録

ハマったところ

shellプログラムの開始アドレスがおかしい

こちらの内容で、shell.elf.text.start セクションが実行アドレスの先頭に配置されて 0x1000000 アドレスにstart関数がきてほしいのに、0x01000054 になってしまっている、という現象です。

$ llvm-objdump -d shell.elf

shell.elf:      file format elf32-littleriscv

Disassembly of section .text:

01000054 <start>:
 1000054: 37 05 01 01   lui     a0, 4112
 1000058: 13 05 85 07   addi    a0, a0, 120
 100005c: 13 01 05 00   mv      sp, a0
 1000060: 97 00 00 00   auipc   ra, 0
 1000064: e7 80 40 01   jalr    20(ra)
 1000068: 97 00 00 00   auipc   ra, 0
 100006c: e7 80 80 00   jalr    8(ra)

01000070 <exit>:
 1000070: 6f 00 00 00   j       0x1000070 <exit>

01000074 <main>:
 1000074: 6f 00 00 00   j       0x1000074 <main>

shell.Map をみてみると、例外情報を入れるための .eh_frame セクションが先頭にきてしまっていることがわかりました。

     VMA      LMA     Size Align Out     In      Symbol
       0        0  1000000     1 . = 0x1000000
 1000000  1000000       54     4 .eh_frame
 1000000  1000000       14     1         shell.o:(.eh_frame+0x0)
 1000014  1000014       3c     1         shell.o:(.eh_frame+0xb4)
 1000054  1000054       24     4 .text
 1000054  1000054       1c     4         shell.o:(.text.start)
(...)

これはリンカスクリプトの側で .eh_frame を入れることで対処しました。

(...)
    /DISCARD/ : {
        *(.eh_frame)
    }
(...)

デバッグコンソールへの入力判定がおかしい

こちらの内容で、 sbi_call が常に ret.error で0になってしまう、という問題です。

long getchar()
{
    printf("kernel: getchar called\n");
    sbiret ret = sbi_call(0, 0, 0, 0, 0, 0, 0, 2);
    printf("sbiret.error = %d\n", ret.error);
    printf("sbiret.value = %d\n", ret.value);
    return ret.error;
}
$ ./run.sh
(...)
Hello, World from shell!
> kernel: getchar called
sbiret.error = 0
sbiret.value = 0
kernel: getchar called
sbiret.error = 0
sbiret.value = 0
kernel: getchar called
sbiret.error = 0
sbiret.value = 0
kernel: getchar called

これはABIの解釈の問題でした。

RISC-V 32ビットのInteger ABI・ilp32 では int, long, pointers are 32bitとなっています。

一方でD言語のlongはどの環境でも64ビット固定なので、ここでズレが生じていました。

構造体を適切な型に修正することで解決しました。

struct sbiret
{
    int error;
    int value;
}

バッファが意図しない壊れ方をする

以下のようなシェルプログラムを実行した際に、`cmdline[1] が \0 に上書きされてしまうような現象に遭遇しました。

        char[8] cmdline;
        for (int i = 0;; i++)
        {
            char ch = cast(char) getchar();
            putchar(ch);
            if (i == cmdline.sizeof - 1)
            {
                printf("command line too long\n");
                for (;;) {}
                goto prompt;
            }
            else if (ch == '\r')
            {
                printf("\n");
                printf("cmdline[1]: %d\n", cmdline[1]);
                cmdline[i] = '\0';
                printf("cmdline[%d]: %d\n", i, cmdline[i]);
                printf("cmdline[1]: %d\n", cmdline[1]);
                break;
            }
            else
            {
                cmdline[i] = ch;
            }
        }
        for (int j = 0; j < 8; j++)
        {
            printf("*cmdline[%d]: %d\n", j, cmdline[j]);
        }
Hello, World!
1 + 2 = 3, 1234abcd
> hello
cmdline[1]: 101
cmdline[5]: 0      <-- ここが '\0' になるのはいい
cmdline[1]: 0      <-- なぜかここも '\0' になる!
*cmdline[0]: 104
*cmdline[1]: 0
*cmdline[2]: 108
*cmdline[3]: 108
*cmdline[4]: 111
*cmdline[5]: 255   <-- ここは書き変わってない!
*cmdline[6]: 255
*cmdline[7]: 255

これは最適化を外したら期待どおり動き、また --disable-loop-unrolling しても期待通りに動いた点から、cmdline(というよりスタックポインタ)がアラインメントされてないときに最適化すると壊れてしまうLLVM RISC-Vバックエンドのバグではないかと疑っていました。

その後、PG_MANAさんの調査により、スタックポインタは16byte-alignedされていなければならないというRISC-Vの仕様があり、リンカスクリプトがその仕様を守っていなかったのが原因であることがわかりました。

こちらのバグはPG_MANAさんがすでに報告し、修正対応済となっています。PG_MANAさん、ありがとうございました!

strcmp関数がヌル終端文字の次の要素を比較してしまう

strcmp関数の実装は正しいはずなのに、ヌル終端文字の次の要素を比較してしまうためにコマンド名の一致判定が正しく行われないという現象が起きました。

これはmemcmp関数のバグが原因だったのだが、究明を難しくしたのがLLVMのsimplificaion of libcallsという最適化です。

LLVMは最適化オプションをつけると、よくあるライブラリ関数で可能な最適化を名前ベースでad-hocに置き換えます。そのためここではstrcmp関数をmemcmp関数に置き換えた結果、strcmp関数の実装をいくら修正しても正しく実装できませんでした。

これで --disable-simplify-libcalls オプションを外せそうですが、新しいLLVMではprintf関数をad-hocにputs関数に置き換えるようになっており、puts関数を実装していない場合はエラーになってしまいます。

s$ ./run.sh
+ QEMU=qemu-system-riscv32
+ LDC=/home/kubo39/dev/build-ldc/bin/ldc2 # 自分がLDC開発してる版のバイナリ
+ DFLAGS='--mtriple=riscv32-none-unknown --mattr=+m --mabi=ilp32 -O2 --betterC --boundscheck=off --checkaction=halt --defaultlib= -relocation-model=static -g -gcc=clang'
+ OBJCOPY=/usr/bin/llvm-objcopy
+ /home/kubo39/dev/build-ldc/bin/ldc2 --mtriple=riscv32-none-unknown --mattr=+m --mabi=ilp32 -O2 --betterC --boundscheck=off --checkaction=halt --defaultlib= -relocation-model=static -g -gcc=clang -Xcc=--target=riscv32 -Xcc=-march=rv32im -Xcc=-mabi=ilp32 -Xcc=-ffreestanding -Xcc=-nostdlib -Xcc=-Wl,-Tuser.ld -Xcc=-Wl,-Map=shell.Map -of=shell.elf shell.d user.d common.d
ld.lld: error: undefined symbol: puts
>>> referenced by common.d:0
>>>               shell.o:(main)
>>> referenced by shell.d:10
>>>               shell.o:(main)
>>> referenced by shell.d:10
>>>               shell.o:(main)
clang: error: ld.lld command failed with exit code 1 (use -v to see invocation)
Error: /usr/bin/clang failed with status: 1

この手のめんどうを回避したいので(まあ今後触る機会があるかわからないが)、引き続き上記オプションをつけるようにしています。

LDC特有の話

LDC inline assemly expressions

C言語だとこんな感じレジスタを指定して値を入れるコードが素直に書けず冗長になってしまいますが、LDCのインラインアセンブリではいい感じに書けます。

sbiret sbi_call(int arg0, int arg1, int arg2, int arg3, int arg4,
                int arg5, int fid, int eid)
{
    return __asm!sbiret(
        "ecall",
        "={a0},={a1},{a0},{a1},{a2},{a3},{a4},{a5},{a6},{a7},~{memory}",
        arg0, arg1, arg2, arg3, arg4, arg5, fid, eid
    );
}

現状LDCLLVM inline assemlyを最適化で消すようなコードにはなっていないのでvolatileの指定はないですが(注: ここでsideeffect=trueを常に指定しているが、これはvolatile相当の振る舞いになる)、将来的には変わる可能性はあります。

他の言語だとRustも独自asm構文持ってていい感じに書けてますね。

align指定

Rustと違う点として、D言語構造体のフィールド単位でのアラインメントを指定できます

struct virtio_virtq
{
align(1):
    virtq_desc[VIRTQ_ENTRY_NUM] descs;
    virtq_avail avail;
    align(PAGE_SIZE) virtq_used used;
    int queue_index;
    ushort* used_index;
    ushort last_used_index;
}

まあC言語はあるわけですが、これはRustとかZigなんかだと意外とないっぽいみたいです。なくてもなんとかなるっちゃなるもんですが、今後機能追加されるんでしょうかね。

さいごに

まずはこちらの素晴らしい資料を作成していただいたseiyaさんに感謝します。 特にqemuでのデバッグについてここまで親切に書かれている入門資料はなかなかないのではないでしょうか。是非大勢の人に挑戦して欲しいなと思います。

あとは、なんやかんや全部実装終えるのに一週間くらいかかってしまいました。。もっと自作OSの練度上げたいですね。。

あとLLVMのsimplification of libcalls最適化には驚かされました(婉曲表現)。 これは自作OSデバッグの難易度を上げてくれる機能で闘いがいがありますね(白目)。

DMDの-fPIE/-fPICとリロケーションタイプのはなし

https://twitter.com/yukicoder/status/1703772579511836745 という話がTwitter、あいやX(旧Twitter)あった。

これはLinux環境でbrewで入れたDMDdmd.confに-fPICがついていないのが原因だった、っぽい。

DMDコンパイル時の初期化設定ファイルを読み込む動作をまず行って、ここで指定されている環境変数を読み込む。たとえば明示的にphobosへのパスを指定していなくてもちゃんとリンクしてくれるのはこのファイルから環境変数を読み込んでいるためだ。 その初期設定ファイルは、Linuxではdmd.confという名前で保持している。 ちなみにこれはコンパイラごとに固有で、LDCもldc2.confというファイルで同じようなフォーマットで保持している。

で、installerとかで入るDMDにはdmd.confのほうで勝手に付与されるために意識する必要がなかったという話だったようで、macOSなんかだとbrewで入れるケースが多いけど自動でPICが有効になるためにみんな気がつかなかったという話っぽい。

ここまではよいのだが、ふと-fPIEと-fPICでDMDが生成するバイナリはなにか変わるんだろうか?と気になった。

前提として-fPIEが有効になる環境はLinuxのみである。

ひとつはpredefined versionでD_PIED_PICがそれぞれ定義されるという違いがある。 まあこれはいいだろう。

より重要な部分として、コード生成での違いがある。

まずbackconfig.dのコードを読むと、PICの場合はPICのフラグのみだがPIEの場合はPICとPICの両方のフラグが有効になる。

        switch (pic)
        {
            case 0:         // PIC.fixed
                break;

            case 1:         // PIC.pic
                cfg.flags3 |= CFG3pic;
                break;

            case 2:         // PIC.pie
                cfg.flags3 |= CFG3pic | CFG3pie;
                break;

PIEのときの条件分岐を追っていくと違いがみえてきそうだ。

実際にコードを読んでみると、内容的に重複していたり使われていない箇所などもあるが、PIEだとより効率的なコードが生成できるって点だけおさえとけばいいんじゃないかと思う。

具体的な話でいえばPIEを使った場合よりコストの低いリロケーションタイプを使うことができる。

一例としてはこんな感じで、リロケーションタイプの割り当てが異なっている。

        case SC.locstat:
            if (I64)
            {
                if (s.Sfl == FLtlsdata)
                {
                    if (config.flags3 & CFG3pie)
                        relinfo = R_X86_64_TPOFF32;
                    else
                        relinfo = config.flags3 & CFG3pic ? R_X86_64_TLSGD : R_X86_64_TPOFF32;
                }

PIC(-fPIC)だとGlobal-DynamicなTLSモデルを使う必要があり、__tls_get_addr経由でGOTに確保したオフセット情報を元に相対計算をして変数を探す。この際常にTLSデータ全体を舐めるので遅い。

PIE(-fPIE)を使った場合、実行ファイル内の静的TLSブロックはリンク時にオフセットの値が確定するので、相対計算はずっと速く完了する。

というわけで今までなんとなくdmd.confに書かれてた-fPICをそのまま使っていたが、速度を考える必要が出た場合は-fPIEを検討することもよいかもしれない。

また、余談になるが他のコンパイラ、たとえばLLVM系のLDCではrelocation-modelに関してもコンパイルオプションで指定することができる。もちろんPIC/PIEなどのオプションとの兼ね合いになるだろうが、DMDよりも柔軟に調整できるんだろうか。

2023/09/26 追記

よく考えると-fPIEでTLSモデルをlocal-exec相当に暗黙仮定してcodegenしてるのアグレッシブ過ぎないか…? あとdmd.confで-fPICを指定している弊害か、だれもfPIEを使っていないためにバグりちらかしているという問題もあり。。

参考資料