正規表現からLLVM IRを生成する
正規表現は文字列マッチングなどに広く用いられている形式言語であるが， 等価な決定性有限オートマトン(DFA)に変換できることが知られている． google/redgrep は与えられた正規表現から等価なDFAに相当するネイティブコードを LLVMにより生成する． ここではredgrepを改造して 正規表現からどのようなLLVM IRが生成されるのかをみてみる．
redllというツールを追加した．コードは
に置いてある．
使い方
最初にLLVMのソースコードをダウンロードして ビルドしてローカルの適当な場所にインストールしておく． redgrepは新しいLLVMを要求するのでLLVM 8.0.0あたりを入れておく． redgrepのビルドが通るようにパスを通す．
$ export LLVM_CONFIG=/path/to/bin/llvm-config
とかやってからredgrepをビルドする．
$ ./redll "regex"
で遊べる．
例: "a"
試しに正規表現パターン"a"がどのようになるのかを以下に示す．
$ ./redll "a"
; dfa is 3 states
; ModuleID = 'M'
source_filename = "M"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
; Function Attrs: norecurse nounwind readonly
define i1 @F(i8* nocapture readonly, i64) local_unnamed_addr #0 {
entry:
%2 = icmp eq i64 %1, 0
br i1 %2, label %return_true, label %3
return_true: ; preds = %3, %entry
ret i1 false
; <label>:3: ; preds = %entry
%4 = load i8, i8* %0, align 1
%cond = icmp eq i8 %4, 97
br i1 %cond, label %5, label %return_true
; <label>:5: ; preds = %3
%6 = icmp eq i64 %1, 1
ret i1 %6
}
attributes #0 = { norecurse nounwind readonly }
ここではFという関数があり，
入力が0であればfalseを返し，
そうでなければ入力から1文字取り出し
97=aであれば1=trueを返す，
というような状態機械になっていることがわかる．
まとめ
他にも色々面白く遊べるはずなので試してほしい．
参考文献
春の秋山郷の行き方 (2019年3月版)
2019年3月21日から24日かけて開催された「カーネル／VMキャンプ #9」[1]に参加した． 開催場所は秋山郷結東温泉「かたくりの宿」という元小学校校舎の宿[2]である． 東京から「かたくりの宿」までの公共交通機関でのアクセスがやや変則的なのでここにまとめておく．
概要
「かたくりの宿」のWebページに書かれている通り，東京からは以下の通りの行程となる[3]．
- 東京 - (上越新幹線) -> 越後湯沢
- 越後湯沢 - (急行バス森宮野原行) -> 津南役場前
- 津南役場前 - (見玉行バス) -> 見玉
- 見玉 - (デマンドタクシー) -> かたくりの宿
前日17:00までにタクシーの予約
基本この通りに行けばいいのだが， デマンドタクシーを前日17:00までに予約する必要がある[4]． タクシーとはいうものの，1日3本の片道300円の路線バスの延長のようなものである． なお，私はこの事実に前日16:58に気づき電話で予約した．危なかった．
越後湯沢から見玉まで
JR越後湯沢駅を降り，東口4番から急行森宮野原行のバズに乗車，津南役場前で降車． 津南役場前から見玉行のバスに乗車，見玉で降車． ここまでは案内の通りに行けるはずである． なお，電子マネーは利用できず，かつ五千円札や一万円札での支払いは車内でできないため， 事前に崩して小銭を作るか乗車券を案内所で購入しておく必要がある．
見玉からかたくりの宿まで
事前に予約したデマンドタクシーが来るはずなので，それに乗ればかたくりの宿まで連れて行ってくれる． デマンドタクシーは見玉までのバスから乗り継ぎができるように時刻表が組まれている． なので，例えば11:49見玉着であれば11:50のデマンドタクシーはバスの到着を待ってくれるはずである．
私の場合
しかし，私はこの事実に気づかなかったため，遅い14:30見玉発のデマンドタクシーを予約してしまい， かつ11:49見玉着のバスに乗ってしまったため，2時間半ほど見玉でデマンドタクシーを待つことになった． 完全にアホである．
見玉には見玉不動尊とその周辺に土産物屋がいくつかある． が，冬季のためか土産物屋は全て閉まっており，かつ見玉不動尊も雪で覆われていて奥まで見ることができなかった． 幸いなことにdocomo回線は繋がっていて，バス停の裏の屋根のある場所にベンチを見つけたため， その場で作業をしつつ[5][6]バスを待つことができた．
参考文献
- [1] https://kernelvm.connpass.com/event/123580/
- [2] http://www.tsumari-artfield.com/katakuri/
- [3] http://www.tsumari-artfield.com/katakuri/stay/#access
- [4] http://www.tsumari-artfield.com/katakuri/wp-content/themes/katakuri/pdf/201810_akiyamagou.pdf
- [5] https://github.com/retrage/llvm/commit/2c6d52911ae64f9b1ec69d5a643fe14ff0a54044
- [6] https://github.com/retrage/llvm/commit/f1a318e44a7a54c0b318849c4e5fed2e2aaeb7eb
LinuxにおけるEFI Variableをみてみる
この記事は Linux Advent Calendar 2018 の20日目の記事として書かれた． ここではLinux kerenlにおけるEFI Variableのコードをみていく．
EFI Variableとは
UEFIでは，EFI varibale(EFI変数)というものが存在する． これは不揮発性メモリ(NVRAM)に値が書き込まれるため， 電源を切っても値が失われることなく保存される． EFI Variableは起動時の起動の順番などが保存される．
UEFIにはEFI Variablesへの読み書きを行うための機能が Runtime Servicesに存在する． このため後述するように，OSの起動後もEFI Variableが Runtime Servicesを通して利用可能となっている． 関連する関数は具体的には以下の4つである．
GetVariablesGetNextVariablesNameSetVariablesQueryVairableInfo
EFI Variableはkey-valueの形式になっており，
文字列keyを入力として，GetVariables/SetVariablesにより
valueの読み/書きができる．
Valueを得るために必要なkeyはGetNextVariableName
により得ることができる．
QueryVairbaleInfoではEFI Variable全体のについての情報を得ることができる．
Linux kernelにおけるEFI Variable
Linux kernelでは，EFI Variableは
擬似ファイルシステムとして表現され，
/sys/firmware/efi/efivarsにマウントされる．
(なお，過去にはsysfs経由でのサポートだったようだが，
sysfsの制限のため，別実装となったようである)
ここで実際のefivarsを例示してみる．
$ ls /sys/firmware/efi/efivars # snip Boot0000-8be4df61-93ca-11d2-aa0d-00e098032b8c Boot0001-8be4df61-93ca-11d2-aa0d-00e098032b8c Boot0002-8be4df61-93ca-11d2-aa0d-00e098032b8c Boot0003-8be4df61-93ca-11d2-aa0d-00e098032b8c # snip
$ cat /sys/firmware/efi/efivars/Boot0000-8be4df61-93ca-11d2-aa0d-00e098032b8c
bubuntu??H??yC??Y??ä?4\EFI\UBUNTU\SHIMX64.EFI?%
このように，0000には現在起動しているUbuntuについてのパスが保存されていることがわかる．
efivarsの実装
ではここから実際にefivarsの実装をみていく．
トップダウンにefivarfsの実装から
どのようにEFI Variableがファイルにマップされるかを見て，
次にRuntime Servicesがどのように呼ばれるかを見ていく．
参照するLnux kernelはmainlineのv4.20-rc2(ccda4af0f4b92f7b4c308d3acc262f4a7e3affad)
である．
efivarfsの初期化
efivarfsの実装はfs/efivarfs/にある．
最初にfs/efivarfs/super.cをみる．
static __init int efivarfs_init(void) { if (!efi_enabled(EFI_RUNTIME_SERVICES)) return -ENODEV; if (!efivars_kobject()) return -ENODEV; return register_filesystem(&efivarfs_type); }
Linux kernel初期化時にefivarfsの初期化が
efivarfs_initにより行われてefivarfsがマウントされる．
static struct file_system_type efivarfs_type = { .owner = THIS_MODULE, .name = "efivarfs", .mount = efivarfs_mount, .kill_sb = efivarfs_kill_sb, };
static struct dentry *efivarfs_mount(struct file_system_type *fs_type, int flags, const char *dev_name, void *data) { return mount_single(fs_type, flags, data, efivarfs_fill_super); }
辿っていくと，efivarfs_fill_superが
mount_singleにより実行される．
static int efivarfs_fill_super(struct super_block *sb, void *data, int silent) { struct inode *inode = NULL; struct dentry *root; int err; efivarfs_sb = sb; sb->s_maxbytes = MAX_LFS_FILESIZE; sb->s_blocksize = PAGE_SIZE; sb->s_blocksize_bits = PAGE_SHIFT; sb->s_magic = EFIVARFS_MAGIC; sb->s_op = &efivarfs_ops; sb->s_d_op = &efivarfs_d_ops; sb->s_time_gran = 1; inode = efivarfs_get_inode(sb, NULL, S_IFDIR | 0755, 0, true); if (!inode) return -ENOMEM; inode->i_op = &efivarfs_dir_inode_operations; root = d_make_root(inode); sb->s_root = root; if (!root) return -ENOMEM; INIT_LIST_HEAD(&efivarfs_list); err = efivar_init(efivarfs_callback, (void *)sb, true, &efivarfs_list); if (err) __efivar_entry_iter(efivarfs_destroy, &efivarfs_list, NULL, NULL); return err; }
ここでファイルシステムの中身を作成している．
最初に/sys/firmware/efi/efivarが作成され，
efivar_initによりefivarfs_listに
EFI Variableのエントリが追加される．
/** * efivar_init - build the initial list of EFI variables * @func: callback function to invoke for every variable * @data: function-specific data to pass to @func * @atomic: do we need to execute the @func-loop atomically? * @duplicates: error if we encounter duplicates on @head? * @head: initialised head of variable list * * Get every EFI variable from the firmware and invoke @func. @func * should call efivar_entry_add() to build the list of variables. * * Returns 0 on success, or a kernel error code on failure. */ int efivar_init(int (*func)(efi_char16_t *, efi_guid_t, unsigned long, void *), void *data, bool duplicates, struct list_head *head) { const struct efivar_operations *ops = __efivars->ops; unsigned long variable_name_size = 1024; efi_char16_t *variable_name; efi_status_t status; efi_guid_t vendor_guid; int err = 0; /* snip */ do { variable_name_size = 1024; status = ops->get_next_variable(&variable_name_size, variable_name, &vendor_guid); switch (status) { case EFI_SUCCESS: if (duplicates) up(&efivars_lock); variable_name_size = var_name_strnsize(variable_name, variable_name_size); /* * Some firmware implementations return the * same variable name on multiple calls to * get_next_variable(). Terminate the loop * immediately as there is no guarantee that * we'll ever see a different variable name, * and may end up looping here forever. */ if (duplicates && variable_is_present(variable_name, &vendor_guid, head)) { dup_variable_bug(variable_name, &vendor_guid, variable_name_size); status = EFI_NOT_FOUND; } else { err = func(variable_name, vendor_guid, variable_name_size, data); if (err) status = EFI_NOT_FOUND; } if (duplicates) { if (down_interruptible(&efivars_lock)) { err = -EINTR; goto free; } } break;
efivar_initでは，
ops->get_next_variableにより
実際にRuntimeServices->GetNextVariableが呼ばれ，
EFI Variableが読み出される．
なお，コメントにあるように，いくつかのUEFI Firmwareの実装では
複数のGetNextVariableの呼び出しにより同じEFI Variableが得られてしまう
というバグがあるため，重複があった場合，dup_variable_bugにより
これを処理し，do-whileを抜けるようになっているようである．
さて，問題がない場合は，引数として渡されるfuncを呼び出す．
これはefivarfs_callbackとなっている．
static int efivarfs_callback(efi_char16_t *name16, efi_guid_t vendor, unsigned long name_size, void *data) { struct super_block *sb = (struct super_block *)data; struct efivar_entry *entry; struct inode *inode = NULL; struct dentry *dentry, *root = sb->s_root; unsigned long size = 0; char *name; int len; int err = -ENOMEM; bool is_removable = false; /* snip */ inode = efivarfs_get_inode(sb, d_inode(root), S_IFREG | 0644, 0, is_removable); if (!inode) goto fail_name; dentry = efivarfs_alloc_dentry(root, name); if (IS_ERR(dentry)) { err = PTR_ERR(dentry); goto fail_inode; } efivar_entry_size(entry, &size); err = efivar_entry_add(entry, &efivarfs_list); if (err) goto fail_inode;
efivarfs_callbackでは，
得られたEFI Variableに対応するファイルを作成して追加する．
以上がefivarfsの初期化の流れとなっている．
efivarfsのread/write
次にefivarfsでのread/write時の動作をみてみる．
const struct file_operations efivarfs_file_operations = { .open = simple_open, .read = efivarfs_file_read, .write = efivarfs_file_write, .llseek = no_llseek, .unlocked_ioctl = efivarfs_file_ioctl, }
より，efivarfs_file_readとefivarfs_file_writeに集約されている．
read時
static ssize_t efivarfs_file_read(struct file *file, char __user *userbuf, size_t count, loff_t *ppos) { struct efivar_entry *var = file->private_data; unsigned long datasize = 0; u32 attributes; void *data; ssize_t size = 0; int err; /* snip */ size = efivar_entry_get(var, &attributes, &datasize, data + sizeof(attributes));
int efivar_entry_get(struct efivar_entry *entry, u32 *attributes, unsigned long *size, void *data) { const struct efivar_operations *ops = __efivars->ops; efi_status_t status; if (down_interruptible(&efivars_lock)) return -EINTR; status = ops->get_variable(entry->var.VariableName, &entry->var.VendorGuid, attributes, size, data); up(&efivars_lock); return efi_status_to_err(status); }
このように，
efivarfs_file_read->efivar_entry_get->get_variable
によりread時にRuntimeServices->GetVariableを呼び出していることがわかる．
write時
static ssize_t efivarfs_file_write(struct file *file, const char __user *userbuf, size_t count, loff_t *ppos) { struct efivar_entry *var = file->private_data; void *data; u32 attributes; struct inode *inode = file->f_mapping->host; unsigned long datasize = count - sizeof(attributes); ssize_t bytes; bool set = false; /* snip */ bytes = efivar_entry_set_get_size(var, attributes, &datasize, data, &set); /* snip */ if (bytes == -ENOENT) { drop_nlink(inode); d_delete(file->f_path.dentry); dput(file->f_path.dentry); } else { inode_lock(inode); i_size_write(inode, datasize + sizeof(attributes)); inode_unlock(inode); }
int efivar_entry_set_get_size(struct efivar_entry *entry, u32 attributes, unsigned long *size, void *data, bool *set) { const struct efivar_operations *ops = __efivars->ops; efi_char16_t *name = entry->var.VariableName; efi_guid_t *vendor = &entry->var.VendorGuid; efi_status_t status; int err; /* snip */ status = ops->set_variable(name, vendor, attributes, *size, data); if (status != EFI_SUCCESS) { err = efi_status_to_err(status); goto out; } *size = 0; /* * Writing to the variable may have caused a change in size (which * could either be an append or an overwrite), or the variable to be * deleted. Perform a GetVariable() so we can tell what actually * happened. */ status = ops->get_variable(entry->var.VariableName, &entry->var.VendorGuid, NULL, size, NULL); if (status == EFI_NOT_FOUND) efivar_entry_list_del_unlock(entry); else up(&efivars_lock);
write時も同様にして
efivarfs_file_write->efivar_entry_set_get_size->set_variable
により与えられたデータをEFI Variableとして書き込んでいる．
コメントにあるように，RuntimeServices->GetVariableを実行し，
データの追加や上書き，削除のどれがなされたかをsizeにより判定する．
efivar_entry_set_get_sizeの返り値bytesにより，
ファイルを削除するか，サイズを変更するなどの操作を行う．
Runtime Servicesの呼び出しに関するTips
static efi_status_t virt_efi_get_variable(efi_char16_t *name, efi_guid_t *vendor, u32 *attr, unsigned long *data_size, void *data) { efi_status_t status; if (down_interruptible(&efi_runtime_lock)) return EFI_ABORTED; status = efi_queue_work(GET_VARIABLE, name, vendor, attr, data_size, data); up(&efi_runtime_lock); return status; }
Linux kernelにおいて，
UEFI Runtime Servicesを呼び出す場合には，
efi_runtime_lockセマフォをdownしてから
実行すべきUEFIサービスをefi_queue_workキューに挿入して
実行させ，最後にセマフォをupさせている．
(例外もあり，nonblockingな呼び出しも存在する)
OSを自作する際にも参考にしたい工夫である．
ebcvm: A Usermode EFI Byte Code Virtual Machine
この記事は 自作OS Advent Calendar 2018 の19日目の記事として書かれた． ここでは，フルスクラッチで開発したEFI Byte Code Virtual Machineである ebcvm[1]と開発したのELVMのEBCバックエンド[2]について紹介する．
続きを読むEFI stubなArch Linuxのインストール
QEMU上の仮想マシンにEFI stubなArch Linuxをインストールする。 ここでのホストはUbuntu 16.04.4 TLSとする。 なお[1][2][3][4]を参考にした。
OVMFのダウンロードとArch Linuxのインストールディスクのダウンロード
最初にOVMFをダウンロードして解凍する。 OVMFはTianoCoreをベースにした仮想マシン向けのUEFI実装である。
$ wget https://www.kraxel.org/repos/jenkins/edk2/edk2.git-ovmf-x64-0-20180508.84.g7cd8a57599.noarch.rpm $ rpm2cpio edk2.git-ovmf-x64-0-20180508.84.g7cd8a57599.noarch.rpm | cpio -idmv $ cp usr/share/edk2.git/ovmf-x64/OVMF_CODE-pure-efi.fd . $ cp usr/share/edk2.git/ovmf-x64/OVMF_VARS-pure-efi.fd .
Arch Linuxのインストールディスクをダウンロードする。
$ wget http://ftp.jaist.ac.jp/pub/Linux/ArchLinux/iso/2018.05.01/archlinux-2018.05.01-x86_64.iso
インストール先のディスクイメージを作成する。
$ qemu-img create -f raw arch-amd64.img 32G
仮想マシンの起動と設定
インストールディスクから起動する。 これ以降は仮想マシンでの操作となる。
$ qemu-system-x86_64 -enable-kvm -k ja -m 2048 -localtime -drive if=pflash,format=raw,readonly,file=OVMF_CODE-pure-efi.fd -drive if=pflash,format=raw,file=OVMF_VARS-pure-efi.fd -hda arch-amd64.img -net nic,model=e1000 -net user -cdrom archlinux-2018.05.01-x86_64.iso -boot d
キーボードレイアウトを設定。
# loadkeys jp106
gdiskでパーティションを作成。
ここでは/dev/sda1を512MBのEFIパーティション、
/dev/sda2を残りのすべての容量としたLinuxパーティションとした。
# gdisk /dev/sda
Command (? for help):o
Command (? for help):n Permission number: 1 First sector : Last sector : +512M Hex code or GUID : ef00
Command (? for help):n Permission number: 2 First sector : Last sector : Hex code or GUID : 8300
最後に書き込みを行う。
Command (? for help):w
各パーティションをフォーマット
# mkfs.vfat -F32 /dev/sda1 # mkfs.ext4 /dev/sda2
それぞれをマウント。
# mount /dev/sda2 # mkdir -p /mnt/boot # mount /dev/sda1 /mnt/boot
ダウンロードのミラーサイトを設定。
# nano /etc/pacman.d/mirrorlist
システムのインストール。
# pacstrap -i /mnt base base-devel
fstabの生成。
# genfstab -U -p /mnt >> /mnt/etc/fstab
localeの設定。
# locale-gen # echo LANG=en_US.UTF-8 > /etc/locale.conf # export LANG=en_US.UTF-8
キーボードマップの設定。
# echo KEYMAP=jp106 > /etc/vconsole.conf
localtimeの設定。
# rm /etc/localtime # ln -s /usr/share/zoneinfo/Asia/Tokyo /etc/localtime
# hwclock -u -w
ホスト名の設定。
# echo "arch-vm" > /etc/hostname
DHCPクライアントの設定。
# systemctl enable dhcpcd.service
パスワードの設定。
# passwd
GRUB2の代わりにefibootmgrでEFI Variableを設定。
# efibootmgr -d /dev/sda -p 1 -c -L "Arch Linux" -l /vmlinuz-linux -u "root=dev/sda2 rw initrd=initramfs-linux.img" # efibootmgr -v
exitしてhalt。
# exit # halt
以下で正しく起動することを確認。
$ qemu-system-x86_64 -enable-kvm -k ja -m 2048 -localtime -drive if=pflash,format=raw,readonly,file=OVMF_CODE-pure-efi.fd -drive if=pflash,format=raw,file=OVMF_VARS-pure-efi.fd -hda arch-amd64.img -net nic,model=e1000 -net user
EFI stubなLinux kernelのビルド
先の説明でインストールしたArch LinuxはEFI stubとなっている。 ここでは、ホストでLinux kernelをビルドしそれを仮想マシンにインストールしてみる。
Linuxカーネルのビルド
カーネルをダウンロードする。
$ git clone https://kernel.googlesource.com/pub/scm/linux/kernel/git/torvalds/linux.git --branch v4.17 --depth 1
ホストのconfigをコピーして多少の修正を行い、ホスト上でビルドする。
make menuconfigでCONFIG_EFI_STUB=yとなっていることを確認する。
makeするときのjob数はホストのCPUのコア数に応じて変更する。
$ cp /boot/config-4.15.0-33-generic .config $ make menuconfig $ make -j9
Linux kernelの仮想マシンへのインストール
仮想マシンのディスクイメージをマウントする。
# /sbin/kpartx -av arch-amd64.img # mount /dev/mapper/loop0p2 /mnt
# make INSTALL_MOD_PATH=/mnt modules_install # mkdir -p /mnt/var/tmp # cp System.map /mnt/var/tmp # cp arch/x86_64/boot/bzImage /mnt/var/tmp # umount /mnt
最後に仮想マシン上でホストでビルドしたbzImageとSystem.mapをコピーし、 initramfsを生成する。
# cp -f /var/tmp/bzImage /boot/vmlinuz-linux # cp -f /var/tmp/System.map /boot/System.map # mkinitcpio -c /etc/mkinitcpio.conf -g /boot/initramfs-linux.img
最後に再起動し、ビルドしたバージョンのカーネルであることを確認する。
参考文献
技術書典5で「UEFI読本 基礎編 Linux編」を頒布
2018年10月8日に池袋サンシャインシティで開催される 技術書典5において「海洋軟件」として 「UEFI読本 基礎編 Linux編」を頒布する． 配置先は「お09」である．
UEFI読本 基礎編 Linux編
以下，本書「はじめに」より抜粋．
UEFIが2005年に登場してから10年以上が経過した。 現在のx86系CPUを搭載したコンピュータのほとんどが UEFIに対応しており、かつOSも当然のように対応している。 しかし、UEFIやそこからの起動を解説をした文書は非常に少なく、 規格書かソースコードを読み解くしかなかった。 本書はそのような現状に応えるべく企画された。
本書は「UEFI読本 基礎編 Linux編」というUEFIについての解説書である。 「基礎編」と「Linux編」の2部構成となっており、 「基礎編」ではUEFIでのOSの起動を知るためのUEFIの基礎について解説を行い、 「Linux編」ではLinux kernelのソースコードを実際に追跡してみていく。
LKL.js: Linux kernelを直接JavaScript上で動かす
Linux kernelを直接JavaScript上で動かした． つまり，JSLinuxのようにEmulatorをJavaScriptで作成し， その上でLinuxを動かすのではなく， JavaScriptで書かれたLinuxを生成し，それを動かす，ということである．
リポジトリは以下の通り．
なお lkl.js Demo にデモを用意した． SharedArrayBufferを有効にして試してみてほしい．
続きを読む