Jak jsem pěstoval trpaslíky
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Thus spake the master programmer:
"Though a program be but three lines long, someday it will have to
be maintained."
-- Geoffrey James, "The Tao of Programming"
Pavel Kaňkovský, 7. května 1998
Slovo na úvod
V dubnovém čísle Linuxových novin byla vyhlášena soutěž
o nejmenší soubor spustitelný pod Linuxem. Když jsem se dozvěděl,
že program může dělat úplně cokoli, je-li to dobře definováno,
zaujalo mne to a také jsem se zúčastnil.
Smršťování kódu
Nejdříve jsem si položil otázku: Jaký je nejmenší možný kód
(bez hlaviček a podobného smetí), který ještě pod Linuxem dělá něco
smysluplného? Je zřejmé, že takový program napsaný v jazyce C by
vypadal například takto:
int main()
{
return 0;
}
to jest nedělá nic jiného, než že skončí.
Ovšem takový program je ve skutečnosti obalen kódem knihovny,
která po návratu z funkce main() volá funkci exit(), která pak
volá stejnojmené systémové volání, které ukončí život procesu. Což
znamená, že program je možno "zjednodušit" takto (případné varování
překladače, že nezná návratovou hodnotu, budeme ignorovat):
#include <syscall.h>
int main()
{
syscall(SYS_exit, 0);
}
Nyní musíme volání funkce (resp. makra) syscall() "rozložit
na prvočinitele". Nahlédneme do souboru /usr/include/asm/unistd.h a
podíváme se, jak se provádí volání jádra na procesorech Intel:
#define _syscall1(type,name,type1,arg1) \
type name(type1 arg1) \
{ \
long __res; \
__asm__ volatile ("int 0x80" \
: "=a" (__res) \
: "0" (__NR_##name),"b" ((long)(arg1))); \
if (__res >= 0) \
return (type) __res; \
errno = -__res; \
return -1; \
}
Poněkud kryptické, není-liž pravda? Nicméně cvičené oko odhalí,
že je vhodné nastavit registr eax na číslo systémového volání
(v našem případě je to číslo 1), registr ebx nastavit na hodnotu
argumentu tohoto volání (tedy nulu) a vyvolat přerušení číslo 0x80.
Nyní již opusťme (relativně) pohostinné končiny jazyka C
a přepišme celý program do assembleru (neboli "jazyka symbolických
adres" pro přátele starých pořádků):
.text
.globl _start
_start:
mov 1, %eax
mov 0, %ebx
int 0x80
Takový program se už obejde bez podpory podobných zbytečností,
jako jsou knihovny, takže už nebudeme ani předstírat nějakou
funkci main() a rovnou definujeme symbol _start (a ušetříme si
jeden parametr při volání linkeru, neboť _start je implicitní
název vstupního bodu programu, který se obyčejně nachází v
/usr/lib/crt1.o).
Náš zdrojový text nazveme například program.s a přeložíme
příkazem cc -c program.s. Výsledkem bude následujících 12 bajtů
strojového kódu (objdump --disassemble --show-raw-insn program.o):
00000000 <_start> b8 01 00 00 00 movl 0x1,%eax
00000005 <_start+5> bb 00 00 00 00 movl 0x0,%ebx
0000000a <_start+a> cd 80 int 0x80
Je vidět, že značné rezervy jsou v nastavení obou registrů: 10
bajtů se zdá být značným plýtváním prostorem. Assemblerový expert
by kód upravil například takto:
.text
.globl _start
_start:
xor %eax, %eax
mov %eax, %ebx
inc %eax
int 0x80
což vytvoří následujících 7 bajtů kódu:
00000000 <_start> 31 c0 xorl %eax,%eax
00000002 <_start+2> 89 c3 movl %eax,%ebx
00000004 <_start+4> 40 incl %eax
00000005 <_start+5> cd 80 int 0x80
Ale to ještě není konec! Ukazuje se (a lze to ověřit nahlédnutím
do zdrojových textů jádra), že registr eax je již při vstupu do
programu vynulován - jako by docházelo k úspěšnému návratu ze
systémového volání execve(). Proto lze vynechat první instrukci.
Nutným předpokladem ovšem je, že náš kód je skutečně to první,
co bude vykonáno, nikoli dynamický linker nebo něco podobného, proto
je žádoucí při linkování používat parametr -static.
Nyní lze přistoupit k zřejmě již definitivně poslední
optimalizaci: nastavení registru ebx spotřebovává dva bajty. Tomu se
jen těžko lze vyhnout, má-li mít nulovou (nebo jedničkovou) hodnotu,
nicméně zadání vyžaduje, aby měl hodnotu "dobře definovanou".
Iniciální hodnota při spuštění tuto podmínku bohužel - narozdíl od
registru eax - nesplňuje. Naštěstí je jedna vhodná hodnota hned po
ruce: jedná se o počet argumentů programu (známý pod přezdívkou
argc), který je jádrem uložen na samotný vrchol zásobníku. Náš
program je tedy možné zkrátit na tři instrukce zvíci pouhých čtyř
bajtů:
00000000 <_start> 40 incl %eax
00000001 <_start+1> 5b popl %ebx
00000002 <_start+2> cd 80 int 0x80
neboli ve zdrojové formě (která je teď pro změnu uvedena jako
druhá):
.text
.globl _start
_start:
inc %eax
pop %ebx
int 0x80
což je víceméně ekvivalent tohoto céčkového programu:
int main(int argc)
{
return argc;
}
Tento kód již vypadá celkem minimálně, takže z něj zkusíme
vytvořit spustitelný soubor:
cc -c program.s
ld -static program.o
ls -l a.out
-rwxr-xr-x 1 peak users 675 May 3 22:00 a.out
Ó jé! Takový malý kód a tak velký soubor! S tím se musí něco
udělat.
Smršťování souboru
Nyní je třeba řešit další zásadní problém: Jak vyrobit co
nejmenší spustitelný soubor?
Linux zná několik druhů spustitelných souborů: základní jsou
a.out, ELF a skripty (tj. soubory začínající znaky \#!). Skripty
vynecháme, protože nevyhovují původnímu zadání.
a.out je starší a jednodušší formát. Jeho kořeny sahají někam do
šerého unixového dávnověku, ale v dnešní době se už prakticky
nepoužívá. Má několik variant, které se liší způsobem načítání do
paměti. Viz include/linux/asm/a.out.h a fs/binfmt_aout.c.
ELF je novější a složitější formát. Byl vyvinut pro potřeby System
V. Ve své úplnosti je tak složitý, že pro jeho dekódování
existuje zvláštní knihovna (libelf), ale nás zajímá jen malá část
- přesně ta, co zajímá jádro. Viz {\tt include/linux/asm/elf.h
a fs/binfmt_elf.c.
Věnujme se nejprve krátce formátu a.out. Jeho hlavička vypadá takto:
a_info "magické číslo"
a_text délka kódu
a_data délka inicializovaných dat
a_bss délka neinicializovaných dat
a_syms velikost tabulky symbolů v bajtech
a_entry startovací adresa
a_trsize velikost relokační tabulky pro kód
a_drsize velikost relokační tabulky pro data
Spustitelný soubor je tvořen hlavičkou a za sebou následujícími
úseky kódu, inicializovaných dat a tabulky symbolů (neinicializovaná
data nejsou pochopitelně v souboru obsažena). Soubor nesmí obsahovat
žádná relokační data a příslušné hodnoty v hlavičce musí být nulové.
"Magické číslo" popisuje variantu formátu. Nabývá jedné
z následujících hodnot:
OMAGIC tzv. "impure executable"; zbytek souboru je načten do paměti
od adresy 0, zápis je povolen všude (pozn. tato varianta bývala
používána i pro objektové soubory formátu a.out(*.o)
NMAGIC tzv. "pure executable" zbytek souboru je načten do paměti od
adresy 0, ale do oblasti kódu je zakázán zápis
ZMAGIC tzv. "demand-paged executable" soubor počínaje pozicí 4096
je namapován do paměti od adresy 0x1000, v prostoru první stránky
není nic namapováno
QMAGIC jiná varianta "demand-paged executable", celý soubor je
namapován do paměti od adresy 0x1000, narozdíl od předchozí
varianty není na začátku souboru jedna prakticky nevyužitá
stránka
Zkusíme vytvořit soubor ve formátu a.out pomocí standardních
nástrojů. Jediný problém je v tom, že musíme linkeru dát parametr -m
i386linux nebo -b a.out-i386-linux, protože (pokud není provozovaná
verze opravdu letitá) bez těchto parametrů by byl vytvořen soubor
ve formátu ELF. Parametrem -N si vyžádáme vytvoření varianty {\tt
OMAGIC} (i když stejně dobře by posloužila varianta NMAGIC vyvolaná
parametrem -n). Navíc (narozdíl od příkladu v předchozí kapitole)
nezapomeneme odstranit ladící informace pomocí příkazu strip (což je
kupodivu účinnější než použití parametru -s při linkování).
ld -static -m i386linux -N program.o
strip a.out
ls -l a.out
-rwxr-xr-x 1 peak users 40 May 3 22:05 a.out
Soubor obsahuje 32 bajtů hlavičky a 4 bajty kódu zvětšené o 4
bajty výplně. To je docela pěkný výsledek, ale, jak uvidíme záhy,
není zdaleka nejlepší možný.
Přikročme nyní ke studiu formátu ELF. Ten má dvě zajímavé
hlavičky. První je hlavička souboru známá pod názvem 15Elf32_Ehdr
(existuje i 64-bitová varianta Elf64_Ehdr):
e_ident identifikace souboru
e_type typ souboru
e_machine platforma
e_version verze formátu souboru
e_entry startovací adresa
e_phoff začátek tabulky segmentů (v souboru)
e_shoff začátek tabulky sekcí (v souboru)
e_flags různé příznaky
e_ehsize velikost hlavičky souboru v bajtech
e_phentsize velikost záznamu segmentu
e_phnum počet záznamů v tabulce segmentů
e_shentsize velikost záznamu sekce
e_shnum počet záznamů v tabulce sekcí
e_shstrndx index sekce obsahující jména
a druhá je hlavička segmentu (tedy položka v tabulce segmentů)
čili Elf32_Phdr:
p_type druh segmentu
p_offset počátek segmentu v souboru
p_vaddr virtuální adresa v paměti
p_paddr fyzická adresa v paměti
p_filesz velikost segmentu v souboru
p_memsz velikost segmentu v paměti
p_flags příznaky segmentu
p_align zarovnání adresy segmentu
Spustitelný soubor ve formátu ELF je tvořen hlavičkou souboru
a "volným prostorem", ve kterém jsou víceméně libovolně rozloženy
ostatní části souboru: tabulky segmentů a sekcí a samotné segmenty
a sekce. Tyto části se mohou libovolně překrývat (nenaruší-li
to integritu jejich obsahu).
První položkou v hlavičce souboru je identifikace: 16 bajtů,
které určují, že se jedná o soubor ve formátu ELF a popisuje jeho
základní vlastnosti (LSB/MSB, 32/64 bitů, verzi formátu hlavičky
souboru). Celkem je obsazeno pouze 7 bajtů, zbylých 9 by mělo mít
nulovou hodnotu, ale nutné to není. Později toho bude využito.
Položka e_type určuje typ souboru, spustitelné soubory zde mají
hodnotu 2, symbolicky ET_EXEC. Položka e_machine určuje hardwarovou
platformu, pro kterou je soubor určen - v našem případě to bude
3, symbolicky EM_I386. Položka e_version určuje verzi formátu, která
zatím existuje pouze jediná s číslem 1.
Důležité položky hlavičky souboru jsou ještě e_entry,
která určuje adresu, od které bude náš program vykonáván, e_phoff
obsahující polohu tabulky segmentů v souboru, e_phnum udávající
počet segmentů a e_phentsize, která musí obsahovat velikost hlavičky
segmentu, v bajtech, tedy číslo 32.
Zbylé položky nejsou při načítání souboru do paměti jádrem nijak
interpretovány, takže mohou mít prakticky libovolné hodnoty.
Segment je ta část souboru, která má být při spouštění programu
jádrem načtena či namapována do paměti, tedy kód nebo data. Existují
sice také některé druhy segmentů mající speciální význam, ale my
budeme blíže zkoumat pouze právě popsaný typ PT_LOAD, číselně se
jedná o typ 1.
V hlavičce segmentu je (narozdíl od hlavičky souboru) důležitá
většina údajů s výjimkou p_paddr (neboť mapování na konkrétní
fyzické adresy není možné) a p_align (segmenty jsou vždy zarovnány
na celé stránky). Zvláštní pozornost zaslouží p_flags, který
popisuje, jestli bude možno namapovaný segment číst (PF_R, 4),
vykonávat (PF_X, 1), resp. zda do něj bude možno zapisovat (PF_W,
2).
Zkusme nyní vyrobit co nejmenší spustitelný soubor ve formátu
ELF. Nejprve použijeme linker a strip, jako v případě formátu a.out:
ld -static program.o
strip a.out
ls -l a.out
-rwxr-xr-x 1 peak users 364 May 3 22:23 a.out
Výsledek je to rozhodně lepší než předtím, ale pořád to není
ono. Přeložený soubor ve skutečnosti obsahuje velké množství smetí,
jak nám ukáže program objdump:
objdump -h a.out
a.out: file format elf32-i386
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00000004 08048074 08048074 00000074 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .data 00000000 08049078 08049078 00000078 2**2
CONTENTS, ALLOC, LOAD, DATA
2 .bss 00000000 08049078 08049078 00000078 2**2
ALLOC
V souboru jsou obsaženy tři sekce, ale jediná potřebná z nich
je sekce .text, která obsahuje spustitelný kód. Pokusíme se soubor
zmenšit odstraněním ostatních sekcí. K tomu použijeme program
objcopy:
objcopy -R .data -R .bss a.out
ls -l a.out
-rwxr-xr-x 1 peak users 276 May 3 22:29 a.out
Soubor obsahuje 52 bajtů hlavičky souboru, jednu hlavičku
segmentu o velikosti 32 bajtů, pak 32 bajtů nul a 4 bajty kód,
dohromady jeden segment o velikosti 120 bajtů, po kterém pak
následuje 156 bajtů s tabulkou sekcí a tabulkou jmen, což jsou ovšem
věci pro vlastní chod programu celkem nepodstatné (je-li linkován
staticky, u dynamicky linkovaných programů je to trochu jinak).
O mnoho více již s pomocí standardních nástrojů nelze dokázat.
Nejjednodušší bude asi vyrobit celý soubor ručně...
Bitové inženýrství
Zkusme si tedy vyrobit nějaký spustitelný soubor sami - bajt
po bajtu. Pro tento účel je vhodné použít nějaký "překladač", který
nám umožní zapsat binární data v nějaké čitelné textové podobě.
Já jsem si jednu takovou jednoduchou pomůcku pro tento účel vyrobil
a nazval jsem ji hex. Jazyk překladače hex je opravdu jednoduchý:
- vše počínaje znakem \uv{\#} je až do konce řádku ignorováno
- obsah souboru je interpretován po slovech oddělených bílými znaky
- slovo obsahující "L" je interpretováno jako 4-bajtová hodnota
(long), slovo obsahující \uv{W} jako 2-bajtová (word), vše
ostatní je jednobajtová hodnota; vícebajtové hodnoty jsou ukládány
od nejméně významného bajtu k nejvýznamnějšímu (little-endian)
- slovo obsahující "x" je interpretováno v šestnáctkové soustavě,
slovo obsahující "o" v osmičkové soustavě, ostatní v desítkové
Začneme opět s formátem a.out neboť je významně jednodušší.
# a.out hlavicka
Lx00640107 # a_info (OMAGIC)
L4 # a_text
L0 # a_data
L0 # a_bss
L0 # a_syms
L0 # a_entry
L0 # a_trsize
L0 # a_drsize
# kod
x40 # inc %eax
x5b # pop %ebx
xcd # int
x80 # 0x80
Tento "zdrojový soubor" se po průchodu překladačem hex změní na
36 bajtový soubor, který je jádro Linuxu ochotno načíst a spustit.
Uspořili jsme zatím čtyři bajty výplně. Někdo může namítnout,
že vhodnější volbou parametrů překladu bychom mohli dosáhnout téhož.
Ale ještě jsme neskončili!
Všimněme si nyní dvou věcí: za prvé, pokud změníme typ souboru
na {\tt QMAGIC, bude do paměti načten - resp. namapován - celý
soubor (i když jádro bude poněkud "nervózní" z toho, že délka
souboru není násobek 4096 bajtů), za druhé, pokud vynecháme koncovou
část hlavičky, domyslí si na tom místě jádro nuly (těžko říci,
zda je to chyba nebo úmysl). Náš kód má pouze čtyři bajty, takže
by ho bylo možno vecpat do některé položky v hlavičce a ještě ji na
konci uříznout. Ač to zní překvapivě, možné to je: kód lze vložit do
položky a_bss, ačkoli podle zdravého rozumu by něco takového nemělo
jádro vůbec spustit (velikost neinicializovaných dat je větší než
2GB). Spustí...
# a.out hlavicka
Lx006400cc # a_info (QMAGIC)
L20 # a_text
L0 # a_data
# L0 # a_bss
# kod (na miste a_bss!)
x40 # inc %eax
x5b # pop %ebx
xcd # int
x80 # 0x80
L0 # a_syms
Lx100c # a_entry
# ty tady nemusi byt, protoze jsou nulove
# (poznamenejme, ze nulove byt MUSI)
# L0 # a_trsize
# L0 # a_drsize
Hrůza! Ale na druhou stranu má výsledný spustitelný soubor
velikost pouhých 24 bajtů (tedy o 8 méně než je regulérní velikost
hlavičky). Menší spustitelný soubor už asi nikdo nevyrobí. Škoda
jen, že při každém spuštění jádro vypíše executable not page
aligned.
A co formát ELF? Začneme opět konzervativně:
# Elf32_Ehdr
# e_ident
x7f x45 x4c x46 # \177ELF
x01 x01 x01 x00 # 32bit, LSB, current version
L0
L0
# dalsi polozky
W2 # e_type = ET_EXEC
W3 # e_machine = EM_386
L1 # e_version
Lx1054 # e_entry
Lx34 # e_phoff
L0 # e_shoff
L0 # e_flags
Wx34 # e_ehsize
Wx20 # e_phentsize
W1 # e_phnum
Wx28 # e_shentsize
W0 # e_shnum
W0 # e_shstrnum
# Elf34_Phdr
L1 # p_type = PT_LOAD
L0 # p_offset
Lx1000 # p_vaddr
Lx1000 # p_paddr
L88 # p_filesz
L88 # p_memsz
L5 # p_flags = PF_R | PF_X
Lx1000 # p_align
# kod
x40 # inc %eax
x5b # pop %ebx
xcd # int
x80 # 0x80
Nejprve 52 bajtů hlavičky souboru, pak 32 bajtů hlavičky
segmentu a pak čtyři bajty kódu. Dohromady 88 bajtů.
Zkusme nyní ušetřit nějaké místo. Prvním krokem bude asi využití
prázdného místa v e_ident: nejjednodušší bude do něj přesunout kód
- tím soubor zkrátíme o čtyři bajty. Lepší by bylo někam přesunout
hlavičku segmentu, ale ta je moc velká, do e_ident se rozhodně
nevejde, ani kdybychom odtud odstranili kód, který jsme tam zrovna
umístili... Ovšem pozor! V hlavičce souboru je spousta zbytečného
místa: umístíme-li začátek hlavičky segmentu na stejné místo jako
e_shoff, dojde k jediné významné kolizi: druhý bajt p_vaddr bude na
stejném místě jako e_phentsize, což je jednoduché vyřešit - stačí
vhodně zvolit adresu, na kterou program v paměti umístíme. Tím
ušetříme 20 bajtů, další čtyři ještě můžeme získat useknutím položky
e_align, kterou jádro postrádat nebude.
# Elf32_Ehdr
# e_ident
x7f x45 x4c x46 # \177ELF
x01 x01 x01 x00 # 32bit, LSB, current version
# kod (pres zbytek e_ident)
x40 # inc %eax
x5b # pop %ebx
xcd # int
x80 # 0x80
L0 # tady je jeste mista....
# dalsi polozky
W2 # e_type = ET_EXEC
W3 # e_machine = EM_386
L1 # e_version
Lx200008# e_entry
Lx20 # e_phoff
# Elf34_Phdr
L1 # e_shoff p_type = PT_LOAD
L0 # e_flags p_offset
W0 # e_ehsize p_vaddr = 0x00200000
Wx20 # e_phentsize (!)
W1 # e_phnum p_paddr = 0x00280001
Wx28 # e_shentsize
Lx20 # e_shnum p_filesz
# e_shstrnum
Lx20 # p_memsz
L5 # p_flags = PF_R | PF_X
# p_align (vynechano)
Celková velikost je neuvěřitelných 60 bajtů! Navíc takový
program funguje, jádro si na nic nestěžuje a program file ho správně
identifikuje:
ls -l elf_tiny
-rwxr-xr-x 1 peak users 60 May 3 22:47 elf_tiny
file elf_tiny
elf_tiny: ELF 32-bit LSB executable, \
Intel 80386, version 1,
statically linked, stripped
./elf_tiny 1 2 3; echo ?
4
A to je vše, přátelé! Menší programy jsem už opravdu vyrobit
nedokázal.
výheň