Mˇ eˇ ren´ı ˇ casu Rozhoduje-li Quality of Service (QoS) router kdy poˇsle kter´ y paket, je tˇreba ujasnit ot´azku dostateˇcnˇe rychl´eho a pˇresn´eho mˇeˇren´ı ˇcasu, aby pˇri dnes bˇeˇzn´ ych des´ıtk´ach tis´ıc paket˚ u za vteˇrinu nedoch´azelo k technick´ ym probl´em˚ um poruˇsuj´ıc´ım pˇredpoklady pouˇz´ıvan´ ych algoritm˚ u. Poul-Henning Kamp, dlouholet´ y pˇrispˇevatel do syst´emu FreeBSD, napsal ˇcl´anek vysvˇetluj´ıc´ı nˇekter´e z´akladn´ı principy ohlednˇe mˇeˇren´ı ˇcasu v j´adˇre bˇeˇz´ıc´ım na v´ıce procesorech z´aroveˇ n [PHKtime] a mimo jin´e definoval: Pˇ resnost jako vzd´alenost namˇeˇren´ ych hodnot od uv´adˇen´e frekvence ˇcasovaˇce, korigovatelnou pˇriˇcten´ım nebo odeˇcten´ım nˇejak´e konstanty. Stabilitu jako velikost odchylky od uv´adˇen´e hodnoty (coˇz je nepˇredv´ıdateln´e). Rozliˇ sen´ı jako d´elku jednoho kroku ˇcasovaˇce (pˇrevr´acen´a hodnota frekvence). Roli hraje i rychlost pˇreˇcten´ı aktu´aln´ı hodnoty z hardware a u ˇcasovaˇc˚ u s nastaviteln´ ym intervalem vyvol´avan´eho pˇreruˇsen´ı t´eˇz rychlost jeho nastaven´ı. ˇ e teoreticky, m´a-li s´ıt’ov´e rozhran´ı kapacitu 10 gigabit˚ Cistˇ u (1010 bit˚ u) za sekundu (Full Duplex (FDX)), stihne takov´e zaˇr´ızen´ı za 1 µs pˇren´est 10 000 bit˚ u, tedy 1250 B. Pokud bychom tedy mˇeli k dispozici mˇeˇren´ı ˇcasu s rozliˇsen´ım 1 µs, mˇely by naˇse algoritmy pˇridˇeluj´ıc´ı rychlost pˇresnost v ˇr´adu odeslan´ ych kilobajt˚ u. Rozliˇsen´ı tedy hraje v´ yznamnou roli; protoˇze je vˇsak velmi z´avisl´e na pouˇzit´em hardware1 , vysvˇetleme zde pouˇz´ıvan´e metody na architektuˇre IA-32 a jej´ı 64-bitov´e verzi, kter´e jsou dnes nejrozˇs´ıˇrenˇejˇs´ı. Kaˇzd´ y syst´em m´a ˇcip ˇr´ıd´ıc´ı hodiny re´aln´eho ˇcasu, Real Time Clock (RTC), kter´ y je pro naˇse potˇreby nedostateˇcn´ y a j´ım vr´acen´ y ˇcas m´a v´ yznam pouze dlouhodob´ y. Historick´ ym poz˚ ustatkem je Programmable Interrupt Timer (PIT), nejˇcastˇeji vidˇen´ y jako ˇcip Intel 8254, pouˇz´ıvaj´ıc´ı hodinov´ y sign´al o frekvenci 1,193182 MHz. Uˇz od nepamˇeti je pˇripojen k IRQ 0. Pomoc´ı instrukce outb se na jeho I/O portu d´a nastavit dˇel´ıc´ı registr (divisor ), aby ˇcip vyvol´aval pˇreruˇsen´ı po dan´em zlomku sv´eho hodinov´eho sign´alu. Kv˚ uli n´ızk´emu rozliˇsen´ı a sloˇzit´e2 komunikaci pomoc´ı I/O port˚ u se dnes pouˇz´ıv´a v´ yhradnˇe jako z´aloha, nem´a-li dan´ y syst´em ˇza´dn´ y jin´ y spolehliv´ y zdroj ˇcasu k dispozici. Od procesor˚ u ˇrady Intel Pentium se objevila podstatnˇe pˇresnˇejˇs´ı a rychlejˇs´ı metoda z´ısk´av´an´ı informace o uplynul´em ˇcase – jednoduch´e poˇc´ıtadlo procesorov´ ych tik˚ u zvan´e Time Stamp Counter (TSC). P˚ uvodn´ı verze pˇrinesla instrukci RDTSC, kter´a do registr˚ u EDX:EAX naˇcetla 64-bitov´ y poˇcet uplynul´ ych tik˚ u od restartu procesoru. Znal-li program´ator frekvenci sv´eho procesoru, mohl z n´ı odvodit vzorec pˇrevodu poˇctu tik˚ u na dostateˇcnˇe pˇresn´ yu ´daj v nanosekund´ach. TSC ale p˚ uvodnˇe nebyl urˇcen jako zdroj hodin re´aln´eho ˇcasu, n´ ybrˇz k mˇeˇren´ı velmi kr´atk´ ych kus˚ u k´odu za u ´ˇcelem optimalizace. Z´amˇernˇe zcela postr´adal moˇznost naˇcasovat pˇreˇruˇsen´ı, k ˇcemuˇz zat´ım slouˇzil jen nevyhovuj´ıc´ı PIT. Prvn´ı n´ahradu ˇcip˚ u i8254 pˇrinesla norma Advanced Configuration and Power Interface (ACPI) a jmenovala se Power Management Timer [ACPI1.0]. Frekvence 3,579545 MHz a atomicky ˇciteln´e 24-bitov´e, resp. 32-bitov´e (podle tabulky FACP) ˇc´ıtaˇce pˇrinesly kolem roku 1996 znateln´e vylepˇsen´ı. Dalˇs´ı n´ahrada PIT se jmenovala multimedia timer, nebo ˇcastˇeji High Precision Event Timer (HPET). ˇ o 32-bitov´e ˇcasovaˇce s minim´aln´ı frekvenc´ı 10 MHz. Aˇz 32 nez´avisl´ Slo ych ˇcasovaˇc˚ u nab´ızelo sv´e ˇctec´ı i nastavovac´ı registry oznamovan´e pomoc´ı tabulky HPET. Umˇely jak periodick´ y reˇzim ( bud´ık“, ” kter´ y se po obsluze pˇreruˇsen´ı opˇet nat´ahne na p˚ uvodn´ı hodnotu) tak one-shot reˇzim, kdy se po obsluze implicitnˇe nedˇeje nic. Toho mohl vyuˇz´ıvat tzv. tickless kernel, kter´ y si takto napl´anoval pˇreruˇsen´ı dle sv´e potˇreby a nepl´ ytval energi´ı pˇreruˇsen´ımi, kter´e by v meziˇcase nemˇely ˇz´adn´ y v´ yznam. Posledn´ım vylepˇsen´ım je ˇcasovaˇc um´ıstˇen´ y na lok´aln´ım Advanced Programmable Interrupt Controller 1 2
Nen´ı vhodn´e ke kaˇzd´emu routeru kupovat pˇrij´ımaˇc GPS ˇci atomov´e hodiny. A pomal´e; ˇcip je pˇripojen 8-bitovou sbˇernic´ı!
1
(APIC) kaˇzd´eho procesoru, oznaˇcovan´ y jako LAPIC timer. Frekvence nˇekter´e ze sbˇernic u dan´eho procesoru je zde vydˇelena hodnotou dˇel´ıc´ıho registru. Kromˇe periodick´eho a one-shot reˇzimu um´ı na nˇekter´ ych procesorech t´eˇz tzv. TSC-deadline m´od, kdy ˇcasovaˇc pos´ıl´a pˇreruˇsen´ı jakmile je hodnota TSC vyˇsˇs´ı neˇz nastaven´a hodnota (a procesor nen´ı v SMM). Pˇekn´e shrnut´ı vˇcetnˇe pˇr´ıklad˚ u je na str´ance http://wiki.osdev.org/APIC_timer. Nejnovˇejˇs´ı s´ıt’ov´e ˇcipy umˇej´ı vkl´adat informaci o ˇcase pˇrijet´ı paketu do sv´ ych deskriptor˚ u. [i217, i82599] Linux toto um´ı pouˇz´ıvat; vizte ethtool -T.
Probl´ emy s TSC K pˇresn´e informaci o ˇcase u ud´alosti s paketem nepotˇrebujeme zdroj ˇcasu schopn´ y pˇreruˇsovat CPU a ˇc´ım rychlejˇs´ı m´ame s´ıt’, t´ım vyˇsˇs´ı vyˇzadujeme od hodin rozliˇsen´ı. TSC tedy vypad´a jako ide´aln´ı kandid´at, avˇsak pr´ace s n´ım nebyla vˇzdy jednoduch´a. Uved’me zde jeho nejzn´amˇejˇs´ı nev´ yhody, jak se s nimi d´a pracovat a jak na nˇe zareagovali v´ yrobci procesor˚ u. Z´ avisel na taktu procesoru, na kter´em jsme RDTSC vykonali. Procesory pot´e zaˇcaly disponovat sofistikovan´ ymi mechanizmy spr´avy nap´ajen´ı (power management), kter´e pˇri neˇcinnosti sniˇzovaly jejich takt a t´ım i spotˇrebu. Bohuˇzel, s t´ım i naˇsi pˇredpokl´adanou frekvenci ˇc´ıtaˇce instrukc´ı. Zmˇena frekvence nav´ıc nebyla okamˇzit´a a zjistit kdy, jestli a na jak dlouho k n´ı doˇslo nebylo principi´alnˇe provediteln´e. Zhruba3 od uveden´ı ˇrady Intel Core m´ıvaj´ı procesory podporu tzv. invariantn´ıho TSC, coˇz zaruˇcuje (mimo jin´e) rychlost tohoto ˇc´ıtaˇce nez´avislou na P-, Cani T- stavech dan´eho procesoru, kter´e mohou ovlivˇ novat jeho frekvenci[IA32sdm, svazek 3, kapitola 17.13.1][AMD-TSC, AMD64ref]. Manu´aly doslova p´ıˇs´ı, ˇze je moˇzn´e pouˇz´ıvat invariantn´ı TSC jako zdroj re´aln´eho ˇcasu. Kaˇ zd´ y procesor mˇ el sv˚ uj, tedy ve v´ıceprocesorov´ ych syst´emech re´alnˇe hrozilo, ˇze se aplikaci po pˇrepl´anov´an´ı na jin´ y procesor posunul ˇcas dozadu. To mˇelo mnohdy fat´aln´ı d˚ usledky, zejm´ena v na toto nepˇripraven´ ych (TSC-sensitive) interaktivn´ıch aplikac´ıch. Aˇckoli to verze manu´alu dostupn´a bˇehem psan´ı pr´ace explicitnˇe neuv´ad´ı, spoleˇcnost Intel m´a patent [ITSCpat] na sv´e ˇreˇsen´ı, kde je TSC synchronizovan´e na vˇsech j´adrech dan´eho procesoru a nedojde-li k pˇrepisu tohoto ˇcitaˇce nebo k odpojen´ı a pˇripojen´ı nˇekter´eho z procesor˚ u, jsou tyto ˇc´ıtaˇce stejn´e na vˇsech procesorech[IntelInit]. Superskal´ arn´ı procesory s jeho ˇ cten´ım h´ ybaly a bylo nutn´e pouˇz´ıvat serializaˇcn´ı instrukce jako CPUID, kter´e vytv´aˇrely bubliny v pipeline a naruˇsovaly pˇrirozen´ y pr˚ ubˇeh mˇeˇren´eho programu, o rychlosti vykon´av´an´ı nemluvˇe. Podrobnˇe to popisuje ˇcl´anek od firmy Intel, vydan´ y kr´atce ˇ po uveden´ı procesoru Pentium II [RDTSC97]. Reˇsen´ım byla nov´a serializuj´ıc´ı varianta p˚ uvodn´ı instrukce: RDTSCP, kter´a nav´ıc atomicky naˇcte ˇc´ıslo logick´eho procesoru, takˇze je moˇzn´e nejen sledovat zmˇeny mezi procesory, ale t´eˇz detekovat pˇrepl´anov´an´ı mˇeˇren´e aplikace na jin´ y procesor. Frekvenci procesoru se ne vˇ zdy podaˇ r´ı pˇ resnˇ e zjistit, proˇceˇz musej´ı syst´emy prov´est minim´alnˇe pˇri spuˇstˇen´ı kalibraci nˇejak´ ym jin´ ym zdrojem ˇcasu. Ofici´aln´ı n´avod od spoleˇcnosti Intel [iCPUID] rad´ı naj´ıt ˇretˇezec Hz“ v modelu procesoru vr´acen´em instrukc´ı CPUID a rozparsovat ˇc´ıslo s po” tenci´aln´ı desetinnou ˇc´arkou pˇred n´ım. Spoleˇcnost VMware pouˇz´ıv´a speci´aln´ı backdoor“ I/O ” port, kter´ ym m˚ uˇze virtualizovan´ y OS zjistit mimo jin´e i frekvenci sv´eho procesoru [OpenVMT]. Pro u ´plnost zmiˇ nme, ˇze TSC lze tak´e ˇc´ıst z Machine Specific Register (MSR), tudy jej lze i zmˇenit a jeho ˇcten´ı lze dokonce zak´azat ˇci emulovat. 3
Pˇresnˇe to zjist´ıme instrukc´ı CPUID s EAX=0x80000007, m´a-li EDX nastaven´ y bit 8 [IA32sdm].
2
Existuj´ıc´ı implementace Linux D˚ uvody pro existenci nˇekolika zd´anlivˇe r˚ uzn´ ych API pro n´ızko- i vysokofrekvenˇcn´ı mˇeˇren´ı ˇcasu najde ˇcten´aˇr v Documentation/timers/hrtimers.txt [LiSrc]. Subsyst´em zvan´ y hrtimer poˇc´ıt´a ˇcas v nanosekund´ach uloˇzen´ ych v 64-bitov´e hodnotˇe typu ktime_t. Jak j´adro zajist´ı dostateˇcnou pˇresnost z´avis´ı na zvolen´em clocksource, kter´ y se dozv´ıme v adres´aˇri /sys/devices/system/clocksource/ a v j´adˇre jej popisuje stejnojmenn´a struktura. V k´odu discipl´ın t´eˇz najdeme funkci psched_get_time, kter´a vˇsak internˇe pouˇz´ıv´a ktime_get. OpenBSD V minulosti se odstranˇen´ım vol´an´ı microtime(9) nad kaˇzd´ ym paketem v´ yraznˇe zv´ yˇsila propustnost nˇekter´ ych zaˇr´ızen´ı, nicm´enˇe v ˇc´astech Alternate Queueing (ALTQ) je ˇcas st´ale potˇreba. Spr´avce m˚ uˇze zvolit zdroj ˇcasu nastaven´ım sysctl kern.timecounter – kaˇzd´e zaˇr´ızen´ı schopn´e vydat informaci o ˇcase m´a svoji strukturu timecounter a hodnotu, kter´a ˇc´ım vyˇsˇs´ı, t´ım vˇetˇs´ı m´a dan´ y zdroj pˇrednost pˇred ostatn´ımi. Dizertaˇcn´ı pr´ace popisuj´ıc´ı implementaci ALTQ [Altq04] p´ıˇse, ˇze m´ısto pˇrepoˇc´ıt´av´an´ı TSC na re´aln´ y ˇcas pro kaˇzd´ y paket ˇsk´aluje subsyst´em svoje parametry na TSC. Protoˇze vˇsak oba syst´emy musej´ı fungovat i na architektur´ach podobn´ y mechanizmus neobsahuj´ıc´ıch, toto se v nich nedˇeje. M´ısto toho se obˇe API snaˇz´ı vyh´ ybat drah´ ym instrukc´ım dˇelen´ı a aproximuj´ı pˇrevodn´ı operace napˇr´ıklad bitov´ ymi posuny a pˇriˇc´ıt´an´ım konstant. ˇ ve virtu´ Cas aln´ıch stroj´ıch Instrukce RDTSC vyvol´av´a trap do hypervizoru a jednoduch´a mˇeˇren´ı potvrzuj´ı, ˇze KVM jednoduˇse pˇred´a svoji hodnotu (coˇz je o pozn´an´ı rychlejˇs´ı) [LiSrc, arch/x86/kvm/emulate.c], zat´ımco VMware (patrnˇe kv˚ uli determinizaci tohoto procesu pro fault-tolerant migraci procesem vMotion) prov´ad´ı daleko n´aroˇcnejˇs´ı operace, takˇze rozd´ıl oproti nab´ızen´ ym ACPI hodin´am nen´ı zvl´aˇst’ v´ yrazn´ y. V´ yborn´ y popis pˇr´ımo od spoleˇcnosti VMware [vmtime] rozeb´ır´a situaci v nejpouˇz´ıvanˇejˇs´ıch syst´emech na trhu. Implementaci TSC v syst´emu Xen popisuje Dan Magenheimer. [xentime]
Reference [PHKtime] Kamp, Poul-Henning. Timecounters: Efficient and precise timekeeping in SMP kernels. [online]. Dostupn´e z: http://phk.freebsd.dk/pubs/timecounter.pdf [AMD64ref] AMD. AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions. Verze 3.21. [online], ˇr´ıjen 2013. Dostupn´e z: http://support.amd.com/ TechDocs/24594.pdf [IA32sdm] Intel. Intel 64 and IA-32 Architectures Software Developer’s Manual. Obj. ˇc. 325462047US. [online], ˇcerven 2013. Dostupn´e z: http://download.intel.com/products/processor/ manual/325462.pdf [AMD-TSC] Brunner, Richard. TSC and Power Management Event on AMD Processors. [online], listopad 2005. Dostupn´e z: https://lkml.org/lkml/2005/11/4/173 3
[ITSCpat] Dixon, Martin G., Rajesh S. Parthasarathy, Jeremy J. Shrall, Controlling Time Stamp Counter (TSC) Offsets For Mulitple Cores And Threads 4 . US Patent 20110154090 A1 [online], ˇcerven 2011. Dostupn´e z: http://www.google.com/patents/US20110154090 [IntelInit] Levicki, Igor, P-State invariant TSC on Nehalem platforms with multi-packages. [online], ˇcerven 2010. Dostupn´e z: http://software.intel.com/en-us/forums/topic/289368 [LiSrc] The Linux Kernel Archives. [online]. Dostupn´e z: http://kernel.org/ [iCPUID] Intel. Intel Processor Identification and the CPUID Instruction. Application Note 485. [online], 2012. Dostupn´e z: http://www.intel.com/content/dam/www/public/us/en/ documents/application-notes/processor-identification-cpuid-instruction-note. pdf [xentime] Magenheimer, Dan. TSC MODE HOW-TO. [online]. Dostupn´e z: http://xenbits. xen.org/docs/4.2-testing/misc/tscmode.txt [vmtime] Timekeeping in VMware Virtual Machines. Information Guide. [online]. Dostupn´e z: http://www.vmware.com/files/pdf/techpaper/ Timekeeping-In-VirtualMachines.pdf [RDTSC97] Intel. Using the RDTSC Instruction for Performance Monitoring. [online], 1997. Dostupn´e z: http://www.ccsl.carleton.ca/~jamuir/rdtscpm1.pdf, p˚ uvodnˇe z: http://developer.intel.com/drg/pentiumII/appnotes/RDTSCPM1.HTM [ACPI1.0] Intel, Microsoft, Toshiba Advanced Configuration and Power Interface Specification. Verze 1.0. [online], 1996. Dostupn´e z: http://www.acpi.info/spec10.htm [OpenVMT] VMware. Open Virtual Machine Tools. [online]. Dostupn´e z: http://open-vm-tools.sourceforge.net/ [i217] Intel. Intel Ethernet Controller I217 Datasheet. [online], verze 2.0, duben 2013. Dostupn´e z: http://www.intel.com/content/dam/www/public/us/en/documents/datasheets/ i217-ethernet-controller-datasheet.pdf [i82599] Intel. Intel 82599 10 GbE Controller Datasheet. [online], verze 2.76, z´aˇr´ı 2012. Dostupn´e z: http://www.intel.com/content/dam/doc/datasheet/ 82599-10-gbe-controller-datasheet.pdf [Altq98] Cho, Kenjiro. A Framework for Alternate Queueing: Towards Traffic Management by PCUNIX Based Routers. In: Proceedings of USENIX 1998 Annual Technical Conference. [online], ˇcerven 1998. Dostupn´e z: http://www.sonycsl.co.jp/person/kjc/kjc/papers/usenix98/ [Altq04] Cho, Kenjiro. ALTQ: Alternate Queueing for BSD UNIX. [online], 2004. Dostupn´e z: http: //www.sonycsl.co.jp/person/kjc/kjc/software.html#ALTQ
4
Pˇreklep je opravdu souˇc´ ast´ı n´ azvu patentu.
4
Seznam pouˇ zit´ ych zkratek ACPI Advanced Configuration and Power Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 ALTQ Alternate Queueing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 APIC Advanced Programmable Interrupt Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 FDX Full Duplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 HPET High Precision Event Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 MSR Machine Specific Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 PIT Programmable Interrupt Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 QoS Quality of Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 RTC Real Time Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 TSC Time Stamp Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
5
