| gar|IG | het woord is aan wli |
|---|
| gar|IG | Tijdens deze presentatie zou ik willen uitleggen wat pgcl is |
|---|
| gar|IG | ten eerste, pcgcl is een afkorting van page clustering. ik heb het zo genoemd om dat er al precedenten waren in oudere operating systems alhoewel ze niet alle aspecten hebben geimplementeerd |
|---|
| gar|IG | ten tweede, het is in feite een forward port van de "larpage" patches van Hugh Dickins naar 2.6. Er is echter nieuw materiaal dat 2.6 specifiek is en door de nogal ingrijpende veranderingen was het onmogelijk om oudere code te herbruiken zonder significante updates ervan of algoritmische aanpassingen |
|---|
| gar|IG | er zijn 2 belangrijke componenten in pgcl |
|---|
| gar|IG | de eerste is een verandering van de definitie van "page" en het maken van een nieuw onderscheid tussen de pages die de kernel gebruikt voor allocatie en de pages die de cpu gebruikt voor adres vertaling |
|---|
| gar|IG | in pgcl, PAGE_SIZE representeert nu wat de page allocater teruggeeft voor een 0-order allocatie en wat een struct page beschrijft |
|---|
| gar|IG | er is een andere notie van page size, MMU_PAGE_SIZE, gebruikt door VM specifieke code, die beschrijft hoe groot de area pagetable maps zijn en dikwijls gebruikt wordt om hardware beschrijvingen te interpreteren |
|---|
| gar|IG | deze 2 groottes zijn met elkaar gerelateeerd daar PAGE_SIZE een macht van 2 veelvoud van MMU_PAGE_SIZE moet zijn |
|---|
| gar|IG | er is een 2de component in pgcl die het doet verschillen in zijn oudere os voorgangers |
|---|
| gar|IG | namelijk dat pgcl de ABI behoudt, om duidelijk te maken wat dit betekent zal ik [wat nu volgt is onvertaalbaar in het nederlands] |
|---|
| gar|IG | toen BSD voor de eerste keer geport werd naar VAX draaide het op machines met erg weinig geheugen |
|---|
| gar|IG | de VAX was niet anders in dit opzicht maar had 512B pages, dit creerde enorme problemen ivm de geheugen footprint |
|---|
| gar|IG | BSD gebruikte een 16 B data structuur voor iedere pagina, een zogeheten cmap_t (analoog met linux' struct page) en er een gebruiken voor elke 512B ram was zeer "duur" |
|---|
| gar|IG | dus het groepeerde hardware pages en pretendeerde dat dat de pagesize was |
|---|
| gar|IG | een onderscheid tussen de 2 noties van page size werd gemaakt door het gebruik van macros met namen zoals PAGE_SIZE en MMUPAGE_SIZE |
|---|
| gar|IG | in feite, dit systeem bestaat nog altijd in sommige open source BSD's |
|---|
| gar|IG | maar dit had een effect op userspace, voordien kon deze mmap() op een 512B grens |
|---|
| gar|IG | maar om met deze wijziging te werken moest het hercompileerd worden om een 2 KB of 4 KB grens te werken |
|---|
| gar|IG | dit is waar het werk van Hugh Dickin's en vandaar ook pgcl substantieel van elkaar verschillen. inplaats van PAGE_SIZE overal in de VM te gebruiken, leert het dingen die naar de pagetables kijken om toe te laten dat fragmenten van een page (toch naar het idee van de kernel) kunnen mmap()'d worden en kunnen ingefault worden [technische termen zijn altijd moeilijk te vertalen] |
|---|
| gar|IG | mmap() is niet moeilijk om te begrijpen, het gaat hier over het delen van getallen door MMUPAGE_SIZE ipv PAGE_SIZE |
|---|
| gar|IG | fault handling daarentegen is meer geavanceerd, fault handlers vinden een pagetable en de MMUPAGE -uitgelijnde offset in de file naar waar het faulting adres correspondeert |
|---|
| gar|IG | deze moeten nu geleerd worden om de rest van MMUPAGE_SIZE fragmenten te gebruiken zodat zij geen geheugen verkwanselen |
|---|
| gar|IG | er is een term die min of meer beschrijft wat het doet, "faultahead". in faultahead zoek je dichtbijzijnde pagetable ingangen die je invult wanneer een fault gebeurd in de hoop dat je page faults kan vermijden in de omgevende virtualspace |
|---|
| gar|IG | in pgcl is dit bijna een vereiste, zeker voor anonymous geheugen. men kan het ook als een performantie vereiste beschouwen |
|---|
| gar|IG | het verschil hier is dat omgevende pagetable entries eigenlijk "de rest van de pagina" betekenen ipv "omgevende pagina's" |
|---|
| gar|IG | na deze inspanning gebeurd iets wonderlijks. de voordelen (die ik nog niet beschreven heb) komen bijna zonder kostprijs |
|---|
| gar|IG | userspace kan het verschil niet zien wanneer het mmap() gebruikt |
|---|
| gar|IG | applicaties moeten niet hercompileerd worden zodat hun secties (data, read-only data, text etc) op de kernel software PAGE_SIZE (de cluster pagina's) grenzen vallen |
|---|
| gar|IG | dit is zeer belangrijk voor legacy applicaties en voor flexibiliteit in de keuze van PAGE_SIZE sinds er een grens moet gekozen worden wanneer je executables gaat linken |
|---|
| gar|IG | dus, nu we weten wat pgcl min of meer doet, laat ons bespreken wat het probeert te bereiken |
|---|
| gar|IG | oorspronkelijk had de oude BSD implementatie van pgcl als doel de geheugen footprint van de kernel te verkleinen |
|---|
| gar|IG | pgcl kan daar ook voor gebruikt worden |
|---|
| gar|IG | aangezien je per structuur meer dingen kan volgen heb je er minder nodig |
|---|
| gar|IG | de linux struct page is groot, het zijn 40 B op 32 bit machines en 80B op 64 bit. soms is het zelfs meer, dit hangt af van sommige architectuur specifieke opties |
|---|
| gar|IG | dit geeft 2.5 MB op een 266 MB 32 bit machine en 5 MB op een 64 bit machine met dezelfde hoeveelheid geheugen |
|---|
| gar|IG | er van uitgaande dat je een 4 KB PAGE_SIZE gebruikt zoals in de mainline kernel |
|---|
| gar|IG | op sommige machines zoals ia32 PAE machines, is de ruimte voor de per-page structuren constant, terwijl de totale hoeveelheid geheugen zeer groot kan zijn |
|---|
| gar|IG | dit was een enorme footprint in absolute termen maar in relatieve maar 1 % ofzo |
|---|
| gar|IG | voor 64 bit machines is de situatie erger omdat de pointers er groter zijn |
|---|
| gar|IG | dus, om de megabytes swap terug te krijgen kan men pgcl gebruiken |
|---|
| gar|IG | echter, het 2.4 werk had andere doelen |
|---|
| gar|IG | in linux zijn vele bestandssystemen block-based en ze gebruiken een basis API die gebaseerd is op structures die de IO status beschrijven van fragmenten van pagina's , de zogeheten buffer_heads |
|---|
| gar|IG | deze structuren kunnen enkel IO statussen beschrijven (IO bezig, IO gedaan, IO niet gedaan, etc) van stukken geheugen die kleiner zijn de de page size van de kernel |
|---|
| gar|IG | of eraan gelijk zijn |
|---|
| gar|IG | er is een algemene wens om blocks te gebruiken die zo groot mogelijk tot een zeker limiet om het aantal IO vragen en "seeks' tussen de verschillende delen van de disk te verkleinen |
|---|
| gar|IG | de redenering is dat je met grote blocks de IO naar een oppervlakte van een bestand kan bedekken met een kleiner aantal gebieden van de disk. waardoor de disk niet moet wachten tot de platter geroteerd is [weer te technisch om goed te vertalen] |
|---|
| gar|IG | of tenminste niet zoveel roteren |
|---|
| gar|IG | het gebruik van een API die er vanuit gaat dat blocks kleiner moeten zijn dan pages is een obstakel om dit te doen |
|---|
| gar|IG | de aanpak is om de notie in de kernel van de page size te vergroten en dan kunnen blocks zo groot zijn als die page grootte |
|---|
| gar|IG | een ander voordeel is iets dat ik daarnet vermeld heb, "faultahead" |
|---|
| gar|IG | wanneer programma's het geheugen gebruiken dat gevraagd is via mmap() faulten ze juist genoeg in om 1 pagetable ingang per keer te vullen in de mainline kernel |
|---|
| gar|IG | cpu's zijn sneller gworden in rechte lijn uitvoering van instructies maar jumps en exceptions zijn relatief gegroeid tov de rechte lijn uitvoerings paden |
|---|
| gar|IG | elke fault om een pte in te vullen is een van die uitzonderingen waarvan het gebruikt stilletjesaan trager is geworden |
|---|
| gar|IG | dit was origineel niet vermeld als een voordeel maar als iemand die normaal gezien volgt wat de VM doet heb ik de faults geteld tijdens de uitvoering van verschillende programma's. pgcl verkleint het aantal faults significant |
|---|
| gar|IG | er is nog een ander voordeel, analoog aan faultahead dat bijna natuurlijk te verwachten is |
|---|
| gar|IG | pages worden bijgehouden op verschillende plaatsen, zoals de LRU, de pagecache radix trees en per-inode lijsten en de VM en bestandssysteem algoritmen doen lookups en itereren over deze structuren |
|---|
| gar|IG | het kan heel veel page structures vereisen in bovenstaande structuren waardoor deze heel diep kunnen worden |
|---|
| gar|IG | de radix trees hebben bijvoorbeeld een branching factor van 64 |
|---|
| gar|IG | om al het cached geheugen voor een 32 MB file weer te geven vereist het een radix tree van 3 niveaus (in de mainline kernel) |
|---|
| gar|IG | met een 64 KB PAGE_SIZE zou dit slechts 2 niveaus nodig hebben |
|---|
| gar|IG | tijdens de writeback, bv voor fsync(), wordt er geitereerd over de lijst van alle pages die aan een inode verbonden zijn |
|---|
| gar|IG | met een 4 KB PAGE_SIZE , zou je voor een file van 32 MB over een lijst van 8192 pages moeten itereren |
|---|
| gar|IG | met een 64 KB PAGE_SIZE wordt dit verkleint meet een factor 16 tot 512 |
|---|
| gar|IG | dus, na al de te verwachten voordelen beschreven te hebben, wat heb ik er eigenlijk kunnen uithalen ? |
|---|
| gar|IG | het antwoord is eigenlijk dat de patch nog in zeer premature staat is |
|---|
| gar|IG | het heeft stabiliteitsproblemen tijdens sommige benchmarks en er zitten slechte algoritmen in die nog vervangen moeten worden |
|---|
| gar|IG | er is echter wel goed nieuws |
|---|
| gar|IG | sommige versies, rond 2.5.74 en 2.5.65 hadden een betere performantie dan mainline op de tiobench, de redenen waarom deze voorsprong niet behouden is kunnen blijven hebben nog onderzoek nodig nadat de stabiliteitsproblemen zijn opgelost |
|---|
| gar|IG | de originele patch verbeterde de performantie op een multiuser systeem met 5 % |
|---|
| gar|IG | de geheugen footprints voordelen zijn duidelijk aangetoond. het is geport naar sommige ia32 PAE machines en resultaten tonen aan dat de PAE (resource) schaalbaarheid verbeteren (dit is ook gepost op lkml). in feite is dit de eerste posting van linux dat draait op een 64GB ia32 machine en dit in een nuttige ziin |
|---|
| gar|IG | samengevat, pgcl is een manier om op een constante manier voordelen te halen uit elk algoritme in de VM en heeft geen nadelen ivm de ABI. ik kijk ernaar uit om het in een toestand te brengen waar het algemeen bruikbaar zal zijn |
|---|
| gar|IG | voila, dit was het. zijn er vragen ? |
|---|
| gar|IG | precies niet, ofwel heb ik ze allemaal in slaap gebabbeld :) |
|---|
| gar|IG | <einde vertaling> |
|---|
| Geryon | woot :) |
|---|
