🐡
straceでdiffのシステムコールを明らかにして自前で実装する
はじめに
diffを書きたいと思い、思いつきでやってみました。
これは公式diffコマンドの公開された挙動（システムコール）を観察したものであり、ソースコードの流用はありません。
マシンスペック
MacBook Air M2 arm64
Docker上で実施
準備
Dockerfileの作成
FROM ubuntu:24.04
RUN apt-get update && \
apt-get install -y \
build-essential \
strace \
vim \
python3 \
python3-pip
WORKDIR /work
ビルド、起動
mkdir c-diff-trace && cd c-diff-trace
vim Dockerfile # 上記をコピペ
docker build -t c-diff-trace .
docker run --rm -it -v "$PWD":/work c-diff-trace bash
diff用のファイル作成
# a.txt
12345
# b.txt
調査
diffを確認
diff a.txt b.txt
1c1
< 12345
---
> 12354
straceで確認
strace diff a.txt b.txt
execve("/usr/bin/diff", ["diff", "a.txt", "b.txt"], 0xffffdbfa4a80 /* 8 vars */) = 0
brk(NULL) = 0xaaab02cc9000
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffffa1e12000
faccessat(AT_FDCWD, "/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=9359, ...}) = 0
mmap(NULL, 9359, PROT_READ, MAP_PRIVATE, 3, 0) = 0xffffa1e0f000
close(3) = 0
openat(AT_FDCWD, "/lib/aarch64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0\267\0\1\0\0\0\360\206\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1722920, ...}) = 0
mmap(NULL, 1892240, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_DENYWRITE, -1, 0) = 0xffffa1c0c000
mmap(0xffffa1c10000, 1826704, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0) = 0xffffa1c10000
munmap(0xffffa1c0c000, 16384) = 0
munmap(0xffffa1dce000, 49040) = 0
mprotect(0xffffa1daa000, 77824, PROT_NONE) = 0
mmap(0xffffa1dbd000, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x19d000) = 0xffffa1dbd000
mmap(0xffffa1dc2000, 49040, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xffffa1dc2000
close(3) = 0
set_tid_address(0xffffa1e12ff0) = 30
set_robust_list(0xffffa1e13000, 24) = 0
rseq(0xffffa1e13640, 0x20, 0, 0xd428bc00) = 0
mprotect(0xffffa1dbd000, 12288, PROT_READ) = 0
mprotect(0xaaaac94ce000, 8192, PROT_READ) = 0
mprotect(0xffffa1e18000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0xffffa1e0f000, 9359) = 0
getrandom("\xf4\xe6\x2b\x5e\x40\x7d\x49\x1c", 8, GRND_NONBLOCK) = 8
brk(NULL) = 0xaaab02cc9000
brk(0xaaab02cea000) = 0xaaab02cea000
openat(AT_FDCWD, "/proc/self/maps", O_RDONLY) = 3
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffffa1e10000
lseek(3, 0, SEEK_SET) = 0
read(3, "aaaac94a0000-aaaac94bc000 r-xp 0"..., 8192) = 1535
read(3, "", 6657) = 0
close(3) = 0
munmap(0xffffa1e10000, 8192) = 0
sigaltstack({ss_sp=0xaaaac94d07c0, ss_flags=0, ss_size=65536}, NULL) = 0
rt_sigaction(SIGSEGV, {sa_handler=0xaaaac94b15c0, sa_mask=[HUP INT QUIT USR1 USR2 PIPE ALRM TERM CHLD URG XCPU XFSZ VTALRM PROF WINCH IO PWR], sa_flags=SA_ONSTACK|SA_SIGINFO}, NULL, 8) = 0
rt_sigaction(SIGSEGV, {sa_handler=0xaaaac94b15c0, sa_mask=[HUP INT QUIT USR1 USR2 PIPE ALRM TERM CHLD URG XCPU XFSZ VTALRM PROF WINCH IO PWR], sa_flags=SA_ONSTACK|SA_SIGINFO}, NULL, 8) = 0
fcntl(0, F_GETFD) = 0
fcntl(1, F_GETFD) = 0
fcntl(2, F_GETFD) = 0
newfstatat(AT_FDCWD, "a.txt", {st_mode=S_IFREG|0644, st_size=6, ...}, 0) = 0
newfstatat(AT_FDCWD, "b.txt", {st_mode=S_IFREG|0644, st_size=6, ...}, 0) = 0
openat(AT_FDCWD, "a.txt", O_RDONLY) = 3
openat(AT_FDCWD, "b.txt", O_RDONLY) = 4
read(3, "12345\n", 4096) = 6
read(3, "", 4090) = 0
read(4, "12354\n", 4096) = 6
read(4, "", 4090) = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0), ...}) = 0
write(1, "1c1\n", 41c1
) = 4
write(1, "< 12345\n", 8< 12345
) = 8
write(1, "---\n", 4---
) = 4
write(1, "> 12354\n", 8> 12354
) = 8
close(3) = 0
close(4) = 0
close(1) = 0
exit_group(1) = ?
+++ exited with 1 +++
観測できました。
実際に私たちが目に見えているところは下記のあたりでしょうか。
execve("/usr/bin/diff", ["diff", "a.txt", "b.txt"], 0xffffdbfa4a80 /* 8 vars */) = 0
...略
openat(AT_FDCWD, "a.txt", O_RDONLY) = 3
openat(AT_FDCWD, "b.txt", O_RDONLY) = 4
read(3, "12345\n", 4096) = 6
read(3, "", 4090) = 0
read(4, "12354\n", 4096) = 6
read(4, "", 4090) = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0), ...}) = 0
write(1, "1c1\n", 41c1
) = 4
write(1, "< 12345\n", 8< 12345
) = 8
write(1, "---\n", 4---
) = 4
write(1, "> 12354\n", 8> 12354
)
読み取り専用でファイルを読み込み、diffのアルゴリズムを実装し、writeシステムコールで画面の表示を行う。
ということが大まかにわかりました。straceでは具体的なdiffのアルゴリズムはわからないため、以降は私の思うdiffのアルゴリズムを考えて実装してみます。
実装
今回は簡単に一行ずつの比較になります。本当のdiffはもっと厳密だと考えられます。
def diff(file1, file2):
with open(file1) as f1, open(file2) as f2:
lines1 = f1.readlines()
lines2 = f2.readlines()
maxlen = max(len(lines1), len(lines2))
for i in range(maxlen):
l1 = lines1[i].rstrip('\n') if i < len(lines1) else ''
l2 = lines2[i].rstrip('\n') if i < len(lines2) else ''
if l1 != l2:
print(f"{i+1}c{i+1}")
print(f"< {l1}")
print("---")
print(f"> {l2}")
if __name__ == "__main__":
import sys
if len(sys.argv) != 3:
print(f"Usage: {sys.argv[0]} file1 file2")
exit(1)
diff(sys.argv[1], sys.argv[2])
実験・結果
Pythonのdiffコードを実施。
python3 diff.py a.txt b.txt
1c1
< 12345
---
> 12354
strace python3 diff.py a.txt b.txt
execve("/usr/bin/python3", ["python3", "diff.py", "a.txt", "b.txt"], 0xfffff0c4d0f8 /* 8 vars */) = 0
brk(NULL) = 0x6f86000
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffffb7a27000
faccessat(AT_FDCWD, "/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=9595, ...}) = 0
mmap(NULL, 9595, PROT_READ, MAP_PRIVATE, 3, 0) = 0xffffb7a24000
close(3)
...
ioctl(4, TCGETS, 0xfffff2d4faa0) = -1 ENOTTY (Inappropriate ioctl for device)
lseek(4, 0, SEEK_CUR) = 0
read(3, "12345\n", 8192) = 6
read(3, "", 8192) = 0
read(4, "12354\n", 8192) = 6
read(4, "", 8192) = 0
close(4) = 0
close(3) = 0
write(1, "1c1\n", 41c1
) = 4
write(1, "< 12345\n", 8< 12345
) = 8
write(1, "---\n", 4---
) = 4
write(1, "> 12354\n", 8> 12354
) = 8
brk(0x7045000) = 0x7045000
rt_sigaction(SIGINT, {sa_handler=SIG_DFL, sa_mask=[], sa_flags=SA_ONSTACK}, {sa_handler=0x6c89e0, sa_mask=[], sa_flags=SA_ONSTACK}, 8) = 0
munmap(0xffffb7a17000, 16384) = 0
exit_group(0) = ?
+++ exited with 0 +++
システムコールから観測して、似た様な挙動を確認できました。
※実際のtraceは長かったため、一部省略しています。
まとめ
diffをstraceからアプローチして確認してみました。皆さんの学習の一助となれば幸いです。
Discussion