| Linuxové noviny | Květen 1998 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Slovo na úvodV 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óduNejdří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 (viz výpis Volání jádra na procesorech Intel).
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 $0x80neboli 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í souboruNyní 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í.
Věnujme se nejprve krátce formátu a.out. Jeho hlavička vypadá takto:
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:
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 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.outSoubor 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 Elf32_Ehdr (existuje i 64-bitová varianta Elf64_Ehdr):
a druhá je hlavička segmentu (tedy položka v tabulce segmentů) čili Elf32_Phdr:
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ý:
Začneme opět s formátem a.out (viz výpis Zdrojový text pro a.out v jazyce hex), neboť je významně jednodušší.
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 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í... Výsledný program vypadá tak, jak je zobrazeno na výpise Finální zdrojový text pro formát a.out.
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ě (viz výpis Zdrojový text pro ELF v jazyce hex).
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. Program pak bude vypadat tak, jak je na výpisu Finální zdrojový text pro formát ELF.
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.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![[ dword ]](dword.gif){kind=small}
![[ word ]](word.gif){kind=small}
