Plan9 operativsystemet er langt om længe blevet sluppet fri, 30 år for sent til at det kommer til at gøre nogen forskel.
Plan9 blev påbegyndt i 1980'erne, fordi folkene bag UNIX følte at den 'forstening' som UNIX' popularitet og kommercialisering medførte gjorde det umuligt at bruge som en forskningsplatform, så de startede forfra, med et meget stort fokus på telekommunikation, multiprocessorer og heterogene miljøer.
Det er ingen hemmelighed at telekommunikation altid har været et stedbarn i UNIX, det var simpelthen ikke i billedet da UNIX blev udtænkt.
Plan9's koncept for telekommunikation er fra dengang 2400 bps modems var almindelige og 56 kbit/sec var "bredbånd", men hastigheden er ikke nær så vigtig som ideerne og koncepterne.
En af de mest imponerende demo'er jeg har set, var en Plan9 68K cpu der blev træt af at regne og hidkaldte hjælp fra en Cray, som overtog den kørende process og regnede videre med sine vektorinstruktioner.
På en lang køretur i dag fik jeg lejlighede til at tænke over hvad jeg ville fokusere på, hvis jeg skulle starte et nyt OS projekt idag.
Isolation og sikkerhed giver sig selv, her ville jeg række ud efter Robert Watson's CHERI så der aldrig igen opstår tvivl om pointeres rækkevidde.
Unix datamodel med "Unstructured array/stream of bytes" er meget stærk men idag er brugerinterfaces fundamentalt flerdimensionelle.
Serialiseringen har nogle uomtvistelige fordelle, ikke mindst i forhold til telekommunikation, så den ville jeg beholde, men ikke stdin, stdout og stderr.
Plan9, X11, DisplayPostscript og OpenGL har alle vist at man kan serialisere flere dimensioner, men det må kunne gøres endnu bedre.
En af de ting der har forandret sig meget er hardwaren.
UNIX er fra en tid hvor man kunne slå op i manualen og regne ud præcis hvor mange clock-cycles ting ville tage, idag er det i praksis umuligt at forudsige, det skal måles.
Mere fundamentalt er utilitymodellen, hvor man bare åbner for hanen når man har brug for vand, ikke aktuel mere.
Idag skal vi holde øje med chip-temperaturen.
Vi skal beslutte hvor mange og hvilke dele af chippen vi skal fyre op under og med hvilken clockfrekvens.
Vi skal holde hus med batteriet.
Vi bør tage hensyn til om solcellerne laver noget.
Vi skal tilpasse os vildt varierende netværksidentiteter, båndbredder, latency og filtreringer.
...sådan set præcis de samme ting som hvis man skulle planlægge en rumraket.
phk
Jeg har selv kæmpet lidt med at (forsøge) at opnå en accpetabel tidssynkronisering mellem cores på en multicore cpu. Det er jo om noget et samspil mellem hardware og software.
Det er jo helt vildt svært, men rigtig brugbart. Nogen tanker om dette og samspillet mellem det du skriver om variabel clock frekvens i det tænkte OS?
Hvis man ikke klatter entropi væk hele tiden så behøver man heller ikke at nørde rundt med en hel masse "xxx-management" ting.
https://spectrum.ieee.org/computing/hardware/the-future-of-computing-dep...
Der går selvfølgeligt lige et par år før man kan købe en CPU til det :).
Har prøvet at sætte mig ind i "reversible computing" flere gange, men må indrømme det forekommer at være tankespind. Men måske nogen kan forklare det.
Min forståelse:
Facts (som jeg tror alle er enige i): 1) En klassisk computer (der ikke er reversibel) skaber entropi sine beregninger 2) Entropien skal løbende slettes 3) Landauer's limit angiver en grænse for hvad det miminum koster at slippe af med entropi 4) Derfor kan en klassisk computer aldrig være mere effektiv en Landauer's limit tilsiger
Følgende påstand antager jeg er rigtig uden at vide det (og ligger til grund for tilhængere af reversibel computing):
1) Det kan lade sig gøre at lave en computer der er reversibel og derved ikke er underlagt Landauer's limit
Min undren:
Selv alt det ovenstående betyder jo ikke at en reversibel computer er mere effektiv end en klassisk. Det præcis modsatte kunne sagtens være tilfældet. Det betyder bare at den reversible computer er den eneste der har en chance for at være mere effektiv, men indtil det er bevist er det tankespind, og det kan være at der er andre årsager til en sådan reversibel computer er mindre effektiv. Desuden: en klassisk computer i forvejen er hele to størrelsesordener fra at ramme Landauer's limit (fremgår af artiklen) er det Landauer's limit jo slet ikke det der begrænser de nuværende computere. Det må således være en anden begræsning, og det mere relevante spørgsmål er så hvordan reversible computere står i forhold hertil.
I stedet for at fokusere på det teoretiske entropi-perspektiv som en "lækker fortælling" savner jeg man i stedet fokuserer på helt konkrete kredsløb (der så kan være reversible) og hvordan de performer i.f.t. alm. CMOS teknologi eller andre teknologier, ligesom man har gjort i hele historien vedr. chipfabrikation.
I hvad forbindelse har du brug for tidssynkronisering mellem cores? Og hvor jeg antager den alm. synkronisering som anvendes f.eks. i.f.t. 1 core og resten af systemet/omverdenen ikke kan bruges?
Isolation og sikkerhed giver sig selv, her ville jeg række ud efter Robert Watson's CHERI så der aldrig igen opstår tvivl om pointeres rækkevidde.
Problemet er at det spilder en masse resourcer på et problem som i det fleste tilfælde ikke er noget problemer. Som jeg forstår det vil det også betyde at man ikke bare kan flytte C/C++ koder over.
Så hvis koden skal genskrives, så ville jeg lave et OS som kun kan køre en variant af intermidiate code/p-Code/Byte code/Il code. Ikke noget med at acceptere maskinkode fra brugere eller drivere. På den måde kan man verificere at pointere er ok ifbm. den afsluttende on-demand compilering af intermidiate code til maskinkode.
Det er intet der hindrer en sådan mellemkode fra at kunne kompileres til noget der er lige så effektivt som maskinkode og så vil man kunne flytte en hel masse af den logik der ligger i CPU'en til instruction reordering, instruction level parallelisation, etc. til compileren og så skal den kun ske en gang.
Behovet for hardware baseret sikkerhed mellem processer forsvinder også fordi OS+compiler sikrer at en process aldrig kan se en anden process.
Problemet er at det spilder en masse resourcer på et problem som i det fleste tilfælde ikke er noget problemer. Som jeg forstår det vil det også betyde at man ikke bare kan flytte C/C++ koder over.
Jeg ved ikke hvor du har fået den opfattelse, men det du udtrykker er allerede eftertrykkeligt tilbagevist i deres forskning.
Der skal bruges et bit per pointer til at fortælle at det er en pointer.
Det er ikke væsentligt forskelligt fra hvorledes man tilføjer paritet og ecc bits til ram ord.
(ARM's Morello prototype implementerer det f.eks ved at stjæle et ECC bit, så man ikke skal lave særlige RAM chips for at komme i luften.)
De har også flyttet en enorm mængde FOSS software, f.eks hele FreeBSD, uden andre problemer end de fejl de har fundet undervejs.
I hvad forbindelse har du brug for tidssynkronisering mellem cores? Og hvor jeg antager den alm. synkronisering som anvendes f.eks. i.f.t. 1 core og resten af systemet/omverdenen ikke kan bruges?
Der gælder generalt, at du aldrig må have tidsbegrebet på en computer. Du skal betragte CPU'en til at regne uendeligt hurtigt. Moderne compilere, burde nægte at oversætte en bench-mark test. Intet program, må afhænge af hardware, herunder CPU'ens hastighed.
Dette er meget nemt at overholde i praksis, og man kan nemt lave et programmeringssprog, der ikke tillader bench-mark tests. Og hvis de tillades, så er der defineret i sproget, hvad svaret er. Det beror ikke på CPU'ens hastighed.
Det eneste sted, hvor der eksisterer tid, er udenfor computeren - når computeren møder den fysiske verden. Her vil data, der komme ind i computeren, teoretisk kunne have et tidsstempel. Og i nogle sammenhæng, er ikke muligt at løse opgaven uden. Og samme på udgangen. I nogle sammenhæng, så skal data der sendes ud på en udgang, have en tidsstempel. Dette betyder i praksis, at interrupts tidsstempler en indgang. At man kan spørge om en indgangs værdi, på et givet tidspunkt. Og at man kan sætte en udgangs værdi på et given tidspunkt. Spørger man i programmet hvad tiden er, så får man enten ingen svar - eller man får et svar, der afhænger af, hvilket input man har ventet på, og som styrer tid. Står f.eks. vent på en indgang går høj, og går den høj på et givet tidspunkt, så må man godt kunne få at vide herefter, at tiden nu er det. Men, hvis der udføres nogen indstruktioner, der tager tid - så må man ikke kunne få det at vide eller få oplysninger om det i softwaren. Softwaren må aldrig kunne vide, hvor hurtig dens CPU er.
Problemet er så, at lave koden, så at de outputs der skrives skal gå høj eller lav, eller sende en værdi ud, på et givet tidspunkt, kommer ud til tiden. Dette kræver, at CPU'en er hurtig nok. Er den ikke det, må man tage højde for, hvad der skal ske. Man vil altid få at vide, hvis der er timing, som ikke opfyldes. I nogle t ilfælde, tænder en lampe, der indikerer der er sket en timing fejl, det logges måske i en sort boks, og det kan også ske, at man vælger at springe sikringen, fordi det måske er det mest sikre i sådan et tilfælde, for at undgå flere fejl. Det er overvejet på forhånd. Skal der strøm på igen, så skal der måske først undersøges hvad det er sket, hvor det er gået galt, fejlen skal rettes osv. Og man har normalt en black-box, hvor oplysninger kan aflæses.
Fra CPU'ens synspunkt findes ingen tid. Og når du har et multi-core system, så er det samme. På en måde, giver det ingen mening med tidssynkronisering mellem multi-core systemer. Og dog. Vi kan - i visse tilfælde - have shared variable, og dette er ikke kun ved multi-core systemer, men også hvis der er noget parallelt, f.eks. hardware. Ved adgang til shared variable og shared resourcer, så er nødvendigt at dette sker i ordnet rækkefølge. En sådan ordning, kan styres af rækkefølgen som er angivet i koden. I sådan et tilfælde, er ikke altid nødvendigt med et tidsbegreb. Eller, der kan anvendes tidsstemplingen fra inputs. Det er ikke muligt, at tage et valg af rækkefølgen der f.eks. skrives til en shared variabel, hvis de data der skriver til, ikke har tidsinformationer, eller andet der giver en garanteret deterministisk ordning. Det betyder, at man i mange tilfælde, ikke kan lave multi-core computere, og parallel programmering, uden man har tidsstempling af indgange og udgange, ved den fysiske enhed. Det sker altid ved den fysiske enhed, fordi at forsinkelser i busser, netværk, og printbaner, rækkefølge som processer udføres i osv. aldrig må have betydning for resultatet. Det må kun afhænge af inputs, og den tidsstempling de har, hvis de har en tidsstempling. Uden tidsstempling, må det kun afhænge af inputs.
Man kan også have parallelisme uden tidsstempling, men så er ofte ikke muligt med shared variable, da man så skal have en anden deterministisk måde af bestemme adgangen på. Det er kun tilladt at tingene er deterministiske. Ellers, så er det umuligt at få til at fungere. Anvendes alene en kø filosofi mellem parallele processer, og tjekkes ikke på om det er data i køen men ventes altid (om der er data i køen er ikke deterministisk, et tilfældigt tal, der ikke må tjekkes på), så vil man også opnå determinisk parallel programmering.
Man tænker ikke i tider indenfor koden. Man tænker i tidsstempling af inputs, der kommer til koden. Det er altid tidsstemplingen der kommer ind, der afgør et resultat. Et godt sprog, har ikke mulighed for andet. Der findes ingen "intern" tid. Inde i computeren, er tiden ikke eksisterende. Du kan ikke få at vide, hvad kloken er på et givet tidspunkt. Du kan bede om, at få at vide hvad klokken er på et givet tidspunkt, ved at spørge uret, der er sat på en indgang. Og du får så det svar, du har spurgt om.
Jeg kunne godt ønske mig, at dem der udvikler programmeringssprog, lærte lidt elementært datalogi, og havde kendskab til determinisme. Både indenfor sekventiel programmering, og indenfor parallel programmeringen. Det vil løse mange problemer, hvis programmeringssprogene var udviklet til at fungere, i overensstemmelse med datalogiens krav til et determinisk programmeringssprog, hvor man ikke kan få adgang til tilfældige oplysninger fra hardwaren, f.eks. på grund af at hardwaren også er parallel med koden. Dette kræver, at man har forståelse af hardware som en parallel process, og de problemer der kan være med shared variable, og veldefineret rækkefølge til dem, enten tidsstyret ud fra tidsstemplingen af input, eller andet veldefineret. Random, findes kun som random funktionen. Man kan godt have en særlig random, der fortæller om CPU'en kører i sleep mode, eller om den har nok at lave - en sådan random, kan bruges hvis man laver en bench-mark test. Men, det er relativt nemt at se på koden (operativsystemet ved det), at der bruges en random funktion, som afhænger af CPU'ens klokfrekvens, og i mange sammenhænge kan man ikke tillade brug af random, så der vil ikke være adgang til sådan en operation for compileren.
Det er vigtigt at huske, at der ingen tid findes inde i en computer. Tiden er på indgangen og udgangen. Og intet andet sted. Mellem "cores" er noget, som vores compiler gerne skal have styr på. Det er den, som står for at parallelisere koden. Der er ingen forskel på parallel, og sekventiel kode. En computers parallelisme, må vi ikke vide noget om fra software verden. Det er ikke muligt at spørge om antallet af cores. For så har vi gjort en ulovlig handling. Parallelisme, er et tilfældigt tal, ligesom CPU'ens klokfrekevns, og de findes ikke, når vi taler deterministisk kodning. Så er det compileren - eventuelt sammen med operativsystemet - der i fællesskab løser begge dele. Hvordan det gøres, afhænger lidt af om det er et embedded system (her er alt ofte i compileren), eller om det er i en computer med et selvstændigt operativsystem. Her vil compileren og operativsystemet, være to sider af samme sag, da der ikke findes maskinkode for compileren. Maskinkode findes kun i CPU-driveren, der også indeholder CPU'ens boot. Denne står reelt for den maskinære oversættelse til den pågældende CPU, sammen med operativsystemets oversætter der ikke anvender maskinkode. Fidusen er, at man i et sådan operativsystem, ikke har nogen maskinkode, andet end i en CPU driver, og kan køre med forskellige CPU'er, FPGA'er, og anden hardware, til at løse opgaverne, og operativsystemet står for at dele opgaverne ud på de forskellige enheder. Fjernes en enhed, f.eks. en CPU, så fortsætter operativsystemet at køre og udføre koden, med de resourcer der er tilbage, også selvom det er andre CPU'er, med andet indstuktionsæt. Der er ikke noget hardwareafhængigt på normalt kode.
Jeg mener, at det er meget vigtigt at lære om determinisme, fordi at det er den eneste måde, man kan lave kode der har en regulær specifikation. Du skal gerne kunne reproducere kode, og kunne sikre, at ens kode, virker ens. Normalt, så vil vi altid sætte flere hold til at lave eksakt det samme, ud fra en prototype. Og så er vigtigt, at have veldefinerede grænseflader. Det har vi ikke, hvis der er tidsmålinger "internt" på en CPU ledning eller bit eller kø et tilfældigt sted. Er det derimod en tidsinformation, der kommer ind fra hardwaren, så er den veldefineret og identisk for alle de parallele progarmmer der kører, som er skrevet af forskellige programmører. Dette er nødvendigt, når vi laver sikker kodning, hvor vi ikke kan acceptere menneskelige fejl i forbindelse med implementeringen. Her har vi altid flere helt uafhængige koder for det samme, skrevet af uafhængige personer, så der er garanti for at flere kommer til eksakt samme resultat, ned til og med operativsystem niveau, og hardware. Man kan så køre i to modes - debug mode, eller normal mode, hvor man afgør hvad der skal ske, ud fra den som afviger (der tages efter mindretallet), eller der kan køres i sikker tilstand, hvor der tages efter flertallet, og logges hvis der er afvigelse.
Behovet for hardware baseret sikkerhed mellem processer forsvinder også fordi OS+compiler sikrer at en process aldrig kan se en anden process.
Det er faktisk meget mere interessant end som så og igen i stik modsat retning:
Når du kan stole på at hardwaren holder skæg og snot adskilt, behøver OS+Compiler ikke gøre sig de store anstrengelser for det.
Forestil dig at når du booter systemet starter du med en "ur-pointer" der kan læse/skrive/exekvere hele address området.
Alle andre pointere afledes fra denne "ur-pointer" i stadig finere granularitet.
Kernen laver en pointer til sin kode, en pointer til sine data og en pointer for "fri hukommelse", ingen af disse pointere overlapper.
For hver process laves der de klassiske fem pointere fra "fri hukommelse" pointeren: text, data, bss, heap & stack.
Nu kan du droppe hele VM + Protected Mode i havnen og køre kernen og alle dine processer sikkert i et og samme addresserum.
Dermed forsvinder en håndfuld af de hardware-lag der idag forsinker RAM-access og som samtidig åber ladeporten for information-leakage angreb. (write-combine, page-look-aside, page-directory cache osv. osv.)
Værsgo: SPECTRE & Co er elimineret og ting kører hurtigere i stedet for langsommere
Der gælder generalt, at du aldrig må have tidsbegrebet på en computer. Du skal betragte CPU'en til at regne uendeligt hurtigt. Moderne compilere, burde nægte at oversætte en bench-mark test. Intet program, må afhænge af hardware, herunder CPU'ens hastighed.
Sikke noget datalogisk landvås!
Selvfølgelig må programmer afhænge af hardwaren, hvordan fa'en har du ellers tænkt dig at få data ind og ud af computeren ?
Selv noget så primitivt som det gode gamle Centronics parallel printer interface har tidsmæssige krav der skal overholdes.
Det eneste sted, hvor der eksisterer tid, er udenfor computeren [...]
Jeg tror chip-designerne bliver rigtig glade når du fortæller dem at alt det der med clocksignaler og metastabilitet er historie nu, det gør deres job meget nemmere.
Helt ærligt Jens...
I fysikopgaver bruger man endeløse mængder af friktionsløse trisser, punktformige lodder og vægtløse snore i lufttomme rum.
Ude i den virkelige verden må man klare sig uden.
Du er naturligvis på samme måde velkommen til at lave dine datalogiske øvelser på perfekte turingmaskiner med endeløs strimmel i et platonisk univers med kun tre dimensioner.
Men her ude i den virkelige verden er vi nødt til at forholde os til tid hele tiden og det tager altid mere tid end man tror
...Sagde manden der brugte et år på at tidssynkronisere CPU'er til UTC på nanosekund-niveau.
Min mor har en Mac Mini og en mobiltelefon. Jeg er ikke 100% sikker på, hvor de fotos, som hun tager, faktisk befinder sig. Jeg håber at de er endt på Mac Minien med timemachine backup. Folkeskoleelever slæber rundt på laptops og ipads altimens de kunne bruge ting-i-skyen til det meste. Hunden spiste min ~~opgave~~laptop. Jeg sidder med en aptop til youtube/video/spil, men mine filer ligger på en NFS server som jeg tilgår med Ipsec over wifi.
Jeg tror det kunne være nyttigt, hvis et nyt OS fokuserede på at kunne migrere forbrug (data eller CPU) til der hvor det er optimalt. Hvis jeg ikke har brugt en rippet DVD i flere år og padsen på det filsystem er ved at være lidt trang, så kunne OSet flytte det undertræ af filsystemet til et andet sted, f.eks. på minkonto hos lagring-i-skyen.dk. Hvis jeg afspiller en film med et CPU-krævende coden, så brug GPUen på min workstation, lad den suge data fra min filserer, og send resultatet (60fps 1080p) til min laptop. Er min CI-server ved at løbe tør for hukommelse - så flyt et par VMer til min workstation eller til Azure.
Tænk hvis OSet gjorde det uden jeg skulle løfte en finger.
Men jeg ønsker også lidt styring med det. Min browser-instans som jeg bruger til at tilgå sundhed.dk / danskebank.dk / jemogfix.dk ønsker jeg bliver kørt på en af maskinerne derhjemme. Mit email-arkiv ønsker jeg at holde på min filserver, sekundært på en maskine derhjemme. Min kort-applikaton+data ønsker jeg at holde på min mobiltelefon for høj autonomitet, men data kan evt. migreres til lagring-i-skyen.dk, og kort-applikationen kan udføres på en server hos mobilnetværk.dk.
@Ivan: Din og nogle af de andre kommentarer får mig til at tænke på det også er nødvendigt at definere hvad et OS er. Mange af tingene du nævner ligger vel også i middleware eller i hvert fald de højere lag i operativsystemet og næppe kernen.
PHK meget interessant indspark. Hvor man kan læse mere om det? Intel har også introduceret nogle udvidelser til at holde mere styr på pointere (MPX) ved ikke om der er analogier hertil.
Et par spørgsmål:
1) Men de principper du taler om - vil de virke både i user- og kernel space? Hvordan skriver en driver så til hardware... altså hvad er erstatningen for:
char p = (char)0xB8000;
i en (simpel) tekst-driver (idet jeg antager ovenstående linie ikke vil kunne fungere i det nye system)? Er det at alle den type pointere oprettes og uddeles fra en indre del af kernen som måske har adgang til "urpointeren" der kan udstikke til hele lageret?
2) Men ellers er princippet vel at en pointer ikke bare er et tal men også har ekstra information. Du nævner det blot er et par bit men der må vel være noget mere i det f.eks. længden af området? Hvor ligger værdien af det? Som en del af pointeren? Eller i eksterne tabeller?
3) Er selve værdien af pointeren kryptografisk beskyttet? Altså så en pointer har (f.eks.) en 256-bit længde med indbygget MAC-værdi så man ikke bare kan danne falske pointere ud af den tomme luft ud fra literals? Hvis ikke (og det antager jeg) må der jo være en anden beskyttelse og jeg tænker det næsten kun kan være at man ikke bare kan loade en pointer ind i et registre ud fra en værdi i lageret. F.eks. at et sådant pointer register kun kan sættes med specielle instruktioner f.eks. ved at kopeire/restricte en allerede indlæst pointer i et andet register? I så fald, hvordan kan pointere så spilles til memory og passes rundt mellem funktioner (på stakken)? Eller er der måske en ekstern repræsentation af pointeren hvor den er kryptografisk beskyttet (med en nøgle kun kendt inde i CPU'en) så man kan spille til memory. Ind/ud-spilning af pointere må da være en lidt langsommere operation men vil måske kun ske sjældnere hvis der er nok adresseringsregistre.
@Jens: I virkeligheden kom mit spørgsmål af jeg netop var nysgerrig efter at vide hvilken use-case der ligger bag behovet for tidssynkronisering mellem processor. Jeg er nok ikke enig i alt det andet du skriver, men jeg er i hvert fald enig med henblik på man som hovedregel ikke bør tænke i tid i den sammenhæng. I stedet tænker man i "happens-before" relationer. Altså bestemte ting som sproget eller hardwaren (ofte i en flydende kombination afhængigt af netop hardwaren) garanterer sker i en bestemt rækkefølge på tværs af tråde, typisk involverende synkroniserende hændelser. Som programmør bør man betragte hver tråd som kørende i sit helt eget selvstændige land og uden nogen tanke på hvad der sker i de andre tråde (og uden at tilgå andres data). Al tilgang til noget der kunne bruges af en anden tråd bør nøje overvejes om/hvorfor er sikkert, og det eneste tidslige aspekt man kan ræsonnere om i den sammenhæng er ting der kan bindes op på de regler om happens-before relationer der er udtrykkeligt defineret af sproget.
Smertefri migrering og distribuering af data og processer kræver hjælp fra OSet. Kig på f.eks. Amoeba hvor man blot har en "handle" til en fil - hvor filen befinder sig er ligegyldigt for det finder OSet ud af. Eller Erlang-modellen hvor man kan have en "port" (handle) til en process uden at skulle bekymre sig om hvor processen kører. Disse mekanismer ville være alment tilgængelige for alle programmer, og dermed vil jeg betragte dem som hørende hjemme i OSet (uanset om man konstruerer OSet som gigantkernel eller som microkernel).
Du har det allerede i dag hvor programmer kan være ligeglade med om /et/sted/fil er på en lokal disk eller på et NFS-drev. Det kunne man udvide så filen kan migreres "live" uden programmet opdager det udover ændring i tilgangstider. Jeg foreslår at man udvider det koncept til at også understøtte migrering af processer, så de kan flyttes derhen hvor de vil køre mest effektivt. LIve migration af processer findes også allerede i dag: VMWave vMotion, MOSIX. Process migration vil dog være lettere hvis programmer er P-ocde som evt. slutkompileres på udførselsmaskinen.
Hvor man kan læse mere om det?
https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
1) Men de principper du taler om - vil de virke både i user- og kernel space? Hvordan skriver en driver så til hardware... altså hvad er erstatningen for:
char p = (char)0xB8000;
Det gør du ikke.
Den pointer skal laves ved reduktion af den "ur-pointer" systemet bootede med, så din driver bliver nødt til at forklare kernens centrale pointer-fabrik hvad den vil have adgang til og argumentere overbevisende nok til at få det.
2) Men ellers er princippet vel at en pointer ikke bare er et tal men også har ekstra information. Du nævner det blot er et par bit men der må vel være noget mere i det f.eks. længden af området? Hvor ligger værdien af det? Som en del af pointeren? Eller i eksterne tabeller?
Pointers er "Fat" pointers, hvilket vi sige at de består af et (base, length, offset, permissions) set.
Det er imidlertid ikke noget stort problem, hverken i praksis eller performancemæssigt.
Balladen er at hardwaren skal holde styr på hvad der er pointere, således at du f.eks ikke kan overskrive en pointer med memcpy() og derved ændre dens egenskaber.
Det indebærer at alle memory skrivninger skal checkes, ikke alene om de er indenfor den pointer de skriver relativt til, men det skal også sikres at alle de pointere der måtte bliver overskrevet mister deres "this is a pointer" status og bare bliver til almindelige data.
3) Er selve værdien af pointeren kryptografisk beskyttet? Altså så en pointer har (f.eks.) en 256-bit længde med indbygget MAC-værdi så man ikke bare kan danne falske pointere ud af den tomme luft ud fra literals?
Der er folk der har arbejdet med kryptografisk sikrede pointere, men de er meget dyre i runtime. Til gengæld har de nogle muligheder i distribuerede systemer.
I CHERI beskyttes pointere af det ekstra bit i hukommelsen som siger "dette er en pointer", det bit kan ikke sættes, det kan kun nedarves fra pointere der allerede har det og en pointers "capability" kan aldrig øges (men den kan "gennedarves" med andre capabilities, hvis du f.eks har brug for at gøre en stack større.)
Du har det allerede i dag hvor programmer kan være ligeglade med om /et/sted/fil er på en lokal disk eller på et NFS-drev.
Problemet med den model er at ansvaret for at vide hvor ting er ikke forsvinder, bare fordi computeren gør det uigennemsigtigt hvor det måtte være.
Jeg har hørt om hele racks af harddiske der er blevet taget ud af drift på den triste måde, fordi forkerte data var landet "på en af diskene, vi ved ikke hvilken".
Sikke noget datalogisk landvås! Selvfølgelig må programmer afhænge af hardwaren, hvordan fa'en har du ellers tænkt dig at få data ind og ud af computeren ?
Dit programs funktion må ikke afhænge af f.eks. CPU'ens hastighed. Du skal sikre programmet er deterministisk, og det er den ikke hvis den afhænger af hastigheden. Har du flere processer der kører, har du ingen styr på hastigheden, og dit programs funktion bliver totalt kaotisk. Laver du en bench-mark test, er det et eksempel på kode, der giver et totalt kaotisk og random resultat. Dette må du ikke. Det kan ikke bruges til noget.
Den simpleste måde, at lave kode, der ikke afhænger af tiden, er at lave noget sekventielt kode, hvor tiden ikke indgår ved kommunikationen med hardware. Det er f.eks. tilfældet, hvis du bruger køer. Så skriver du et antal data ind eller henter dem ud af en kø, og er der ingen data, så venter du bare - du må ikke kunne læse, om der er data i en kø, for så er du ude i noget tilfældigt.
Det er meget vigtigt, at have styr på, hvad det er tilfældigt, og hvor tilfældighederne opstår. Ofte, så opstår de i forbindelse med parallelisme.
Din hardware er i princippet parallel med din software. Når du laver low-level kode, så er alle variable der deles med hardwaren shared (volatile i C++). Det samme med interrupts. Et interrupt kører parallelt med hovedprogrammet.
Det er derfor også vigtigt, at have styr på parallelisme i denne sammenhæng.
Har vi sharede variable, så er vigtigt, at vi sikre en deterministisk adgang til variablen, altså at rækkefølgen af adgangen er veldefineret. Antager vi, at to processer, anvender samme sharede variabel. Nu skal vi sikre, at det er ligegyldigt, i hvilken rækkefølge at disse to processer kører, så skal resultatet altid være identisk. Vi må ikke have noget tilfælde. Spørgsmålet er, hvordan vi skal gøre det. Vi kan vælge at udføre alt fra process 1 først, så det først er når at process 1 er helt afsluttet, at vi går i gang med process 2. Det vil sige, at vores process 2 må vente, fordi at process 1 står øverst i vores kode. Denne fremgangsmåde betyder reelt, at vores parallelisme tvinges til at køre sekventielt. Vi kan først fortsætte i koden til process 2, når process 1 ikke mere anvender vores sharede variabel. En shared variabel tvinger trådning.
Alt i alt, er derfor ikke nødvendigvis stor forskel på sekventiel og parallel kodning, da at parallel kodning reelt tvinges til at være sekventielt, hvis det anvender samme variable. Vi kan derfor ikke se forskel på, om det er sekventiel eller parallel kode. Det er samme.
I mange tilfælde, har vi brug for timing. I disse tilfælde, må timingen IKKE være inde i cpuen. Det er hardwaren som påklistre timingen. Vi kan også gøre det i operativsystemet med interrupts, men det tager lidt længere tid, så det ikke er helt så præcist.
Det betyder, at hvis du læser noget, fra en hardware port, så er det ikke kun en værdi. Det er altid værdi + tid. Og skriver du noget, er det værdi plus tid. Får du et interrupt, så tidsstemples den, og læser du en port fra en stream / kø fra en interrupt port, så får du data plus tid.
Det er denne tidsstempling du må bruge i din kode. Du må IKKE bruge en eller anden tilfældig tid, der afhænger af printbaners længde, eller den rækkefølge som forskellige processer er udført. Dette giver noget udefineret vås.
Så det er intet problem, at lave tidstyret kode. Men tiden udregnes i koden, f.eks. kan du lave en process, der henter data ind fra en interrupt styret port, negerer data, og sender dem ud et antal millisekunder senere, på en anden port. Det er ikke et problem.
Et klasisk problem er en database, hvor to editerer i databasen samtidigt. Her vil vi gerne "låse den", så kun en har adgang. Det må vi ikke efter CPU'ens interne tid. Det afhænger af, hvem der udefra kommer først, altså den tidsstempling som kommer fra deres tastatur og mus, der afgør hvem der får adgang først. Ellers er det ikke veldefineret, men afhænger af tilfældige ting i din computer. Det er ulovligt.
Antages, at vi har sharede variable, og ønsker at definere, at rækkefølgen skal ske efter den tidsmæssige rækkefølge, og ikke efter den rækkefølge som anvendelsen er i koden (der påtvinger sekventiel rækkefølge). Så kan vi anvende tidsstemplingen til af afgøre, i hvilken rækkefølge at den sharede variabel bruges. Som et eksempel, kan man lave en process man kommunikerer med via nogle køer, og skriver og aflæser til den sharede variabel. Og denne process, kan afgøre rækkefølgen af, at denne sharede variabel skal bruges, f.eks. ud fra tidsstemplingen der kommer fra processerne der ønsker adgang. Her har vi et mindre problem. Antager vi, at to personer, på to computer, der er to forskellige steder på jorden, forsøger at få adgang på samme tidspunkt, og nu skal vi bruge tiden for at afgøre rækkefølgen de skal have adgang. Den ene bor tættere på computeren, end den anden. De får derfor adgang først "internt" i computeren, mens den anden får adgang senere, selvom den faktisk fysisk kom først. Her skal vi vælge efter den, som fysisk kommer først. Ellers er vores funktion ikke veldefineret - to identiske programmer, vil kunne opføre sig forskelligt. Løsningen her er, at vi bliver nød til, at have en lille delay, hvor at data på vores sharede variabel er stabil, før vi må bruge den. I denne tid, sikrer vi os, at der ikke var en anden som i virkeligheden kom først. Vælger vi en for kort delay, så vil det medføre en trap, og vi får logget, at vi ikke har valgt tilstrækkeligt stort delay. I nogle tilfælde, hvor der kan være fare, fordi at rækkefølgen er forkert, så kan vi risikere at man må lukke det hele, indtil fejlen er korrigeret.
Selvom vi ikke direkte må kunne se CPU'ens hastighed fra koden, så har den således alligevel betydning, da den har betydning for at sætte timeouts, og den har betydning, fordi det kan ske at den ikke kan nå at udregne det der skal ud, til det tidspunkt det skal ud. Er tiden f.eks. 13:02, men vores computer har regnet ud, at et output skal ud 13:01, så kan den ikke sætte det ud på udgangen til tiden. I dette tilfælde logges en fejl, og vi ved den ikke har opfyldt timingskravet. Og igen, måske så er nødvendigt, at lukke ned.
Så det er bestemt muligt, at holde styr på tiden via operativsystemet og hardwaren. Og, man skal altid gøre det via tidsstempling på den fysiske port, eller så tæt på som muligt. Kun på den måde, er funktionen defineret.
Inde i computeren er der ingen tid. Har du et program, tager instruktionerne reelt 0ns. Det kan vi se på mange måder. Som nævnt, så er der ingen forskel på sekventiel og parallel. Har du sekventiel kode, og anvender ikke dataene så der ikke er uafhængighed, så kender du ikke rækkefølgen, som koden udføres. Det kan godt ske, at den kode som står nedderst udføres før den der står øverst. Tiden giver derfor ingen mening. Den er ikke nødvendigvis i rækkefølge.
Beder vi om at få tiden, så er bedst at se på, hvad der har medført den pågældende process udføres. Har vi f.eks. en process, der eksekveres på baggrund af interrupt, så kan man returnere, at det er tidspunktet som interruptet fysisk kom, at der eksisterer i koden. Og, hvis det er reset der har startet den, så kan det være tidspunktet som reset fysisk kom. Venter processen på noget, f.eks. den process der er opstartet af reset, har en venteløkke der venter på et input bliver høj, så kan man definere den tid, der er efter vent, til den tid som eksisterer efter inputtet går højt. CPU'ens instruktioners tid findes ikke. Den skal bare være tilstrækkelig hurtig, ellers medfører det trap og noteringer i computerens "sorte bog", samt eventuelt udførsel af nødprocedurer der skal ske i sådanne tilfælde.
Jeg syntes, at det er mega vigtigt at tænke på når man koder, om den kode man laver afhænger af små detaljer, f.eks. den rækkefølge at processer udføres, eller CPU'ens hastighed. Dette er svært at håndtere manuelt. Og derfor, er bedst at man har tools til at verificere at ens kode er i orden, eller at programmeringssproget simpelthen laves, så den ikke har de ord der skal til, for at man kan formulere noget ikke deterministisk lort.
I C++ skal man reelt tænke på, at der kan være problemer, hver eneste gang man bruger ord som volatile. Også når det er i forbindelse med hardware. For vi har her flere parallele processer, der oftest får adgang til noget, i helt tilfældig rækkefølge. Dette ødelægger determinismen i sproget, og gør at det ikke fungerer. Kører vi eksempelvis to personers kode, der gerne skulle fungere ens, eller endog den samme kode, så risikerer vi at det fungerer forskelligt.
Dit programs funktion må ikke afhænge af f.eks. CPU'ens hastighed. Du skal sikre programmet er deterministisk, og det er den ikke hvis den afhænger af hastigheden.
Fortæl mig hvordan jeg skulle have designet det compute-cluster til ESO's ELT teleskop så afleverer data til tiden, hvis jeg "ikke må afhænge af f.eks. CPU'ens hastighed" ?
Når virkeligheden stiller tidsmæssige krav, bliver vi også nødt til at stille krav til CPU'ens hastighed.
Jeg er helt enig med dig I at man skal tænke sig rigtig godt om inden man forlader sig på CPU'ens hastighed, men at nedlægge et veto således som du gør, hører ingen steder hjemme.
Jeg har hørt om hele racks af harddiske der er blevet taget ud af drift på den triste måde, fordi forkerte data var landet "på en af diskene, vi ved ikke hvilken".
Der ville mit hypotetiske migrerings-optimerede OS blot blive bedt om at migrere data væk fra hele det diskarray, samt (afhængig af omstændighederne) markere det som reserveret til specifikt formål.
Jeg har brugt meget tid på diskoptimeringer, partitioner, raid, filesystemer, osv. ifbm. mit arbejde. Men måske bør man kaste det arbejde over på maskinerne selv og dermed frigøre menneskelig kapacitet. Med både ZFS og Oracle ASM smider man blot en disk i, og så finder datamaten ud af resten. Måske er det fremtiden, og bør udvides til at også omfatte andre resourcer (CPU, RAM, GPU, ...)?
Der ville mit hypotetiske migrerings-optimerede OS blot blive bedt om at migrere data væk fra hele det diskarray, samt (afhængig af omstændighederne) markere det som reserveret til specifikt formål.
Det er sikkert fint nok til de fleste almindelige formål.
Men når vi tale om decideret følsomme data, er det ikke godt nok, så skal der kunne redegøres præcist for alle medier disse data har befundet sig på og for al traffik fra samme datamedier, indtil datamedierne bliver destrueret.
Jeg ved ikke hvor du har fået den opfattelse, men det du udtrykker er allerede eftertrykkeligt tilbagevist i deres forskning.
Der skal bruges et bit per pointer til at fortælle at det er en pointer.
Jeg ikke fundet deres forskning så hvis du har et link vil jeg gerne se det.
Jeg forstår godt at man kan sætte en bit i memory til at signalere at noget er en pointer. Men der skal vel også være noget associeret med pointeren til at fortælle hvor stor den block den peger ind i er og hvor blokken starter. Ellers er der meget kode med pointer gymnastik der ikke vil virke. Det skal gemmes et eller andet sted.
I øvrigt er der både pointere til kode og til data og det vil være klogt at kunne adskille dem. Og pointere til forskellige slags data (typer). Hvis man først går den vej så er software vejen renere. En af de fede ting ved Java/C#/VM-sprog er at man aldrig får en overskreven stack serveret som man skal håndtere. Jeg har brugt tilstrækkeligt mange måneder af mit liv til at debugge den slags til at jeg aldrig gider gøre det igen. Hvis man kan enforce den slags på OS niveau vil meget være vundet. Helst uden at tvinge folk til ind i en GC verden.
Behovet for hardware baseret sikkerhed mellem processer forsvinder også fordi OS+compiler sikrer at en process aldrig kan se en anden process
I prinicippet burde hardwaren have lidt mere kendskab til data - f.eks. kendskab til om data er indstruktion, stak, data, eller pointer, om det er const/read only. Og det kan også være relevant, om det er en pointer til kode, stack, data, eller pointer til pointer. En pointer kan eventuelt deles op i to - pointer til rom og pointer til ram - hvor "rom" delen, i OOP typisk vil være VMT tabellen, mens ram delen, vil være den sædvanlige pointer til ram lageret. Dette vil dog medføre at pointere til et opbjekt, vil fylde mere, men det er nemmere at håndtere af hardware, og man vil få VMT loaded samtidigt med at datapointeren hentes, så der ikke skal bruges flere indstruktioner for at loade en objekt pointer.
Det største problem ved pointere i programmeringssprog som C++, er at en pointer til integer, reelt kan pege på hele lageret. Det gør det svært at automatisk parallelisere. Man skal gerne sikre sig, at en pointer KUN kan pege på relevante data. I princippet, kunne vi lave en klasse eller andet, så typen sikrer, at den kun kan pege på relevante data. Men, så længe at sproget supportere at der er pointere til byte, så vil de desværre blive brugt, og så har compileren ikke afgrænset området, som den pågældende pointer har lov at pege på. Man burde nok overveje lidt, hvordan at man laver et sprog, så at den mængde af udfaldsmuligheder en pointer har, er så begrænset som muligt. Det vil kunne gøre compilerne mere optimale. Problemet er, at selv compilerne har svært ved at gennemskue de mulige pointerværdier en pointer kan have, med mindre man afgænser det, ved hjælp af særlige typer, til hver enkelt pointer.
Jeg ikke fundet deres forskning så hvis du har et link vil jeg gerne se det.
https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
ARM er ved at lave en "proof-of-concept" chip med en version af Cheri de kalder "Morello".
Hvis der er danske forskere der vil have fingre i den hardware skal de sende Robert Watson en email ASAP, vinduet lukker meget snart.
Pointers er "Fat" pointers, hvilket vi sige at de består af et (base, length, offset, permissions) set.
Det er imidlertid ikke noget stort problem, hverken i praksis eller performancemæssigt.
Fat pointers er nemme. De kan lave uden overhead.
Men der vil være en del software der breaker enten pga. uautoriseret pointergymnastik eller fordi fat pointers vil fylde for meget.
Balladen er at hardwaren skal holde styr på hvad der er pointere, således at du f.eks ikke kan overskrive en pointer med memcpy() og derved ændre dens egenskaber.
Det indebærer at alle memory skrivninger skal checkes, ikke alene om de er indenfor den pointer de skriver relativt til, men det skal også sikres at alle de pointere der måtte bliver overskrevet mister deres "this is a pointer" status og bare bliver til almindelige data.
Jo men man skal faktisk også se om memory er blevet allokeret til noget andet i mellemtiden. Det kan hurtigt blive dyrt noget hvis hver eneste deallokering af memory skal se efter om nogen har pointers til memory. Det minder en smule om garbage collection.
Jeg tror mere på at undgå pointers. Det kan man selvfølgeligt ikke på maskinkode niveau (tror jeg?) men på compiletime. Der er sprog der er gået den vej der er lige så effektive som C/C++.
Dengang at verden var bit-slice, kunne man opleve, at der kun var lager efter det antal bits der blev brugt. Bits kostede nemligt.
Eksempel. Bit-slice lagermoduler:
Kode: Med indstruktion kode bit bredde kan udbygges, hvis bredere indstruktioner
Data: Med data kode bredde kan udbygges, til flere bit data (efter kommaet)
Peger-kode: Peger til kode med bitbredde afhængigt af kode lagerstørrelse
Peger-data: Peger til data med bitbredde afhængigt af data lagerstørrelse
Peger-peger: Peger til peger med bitbredde bestemt af lagerstørrelse sum(peger-kode + peger-data + peger-peger)
Da konstante ikke står i koden, men i starten af kode/data/og peger lagerne, så er koden helt uafhængigt af indstruktionsbredder og databit bredden. Og det er ikke muligt i koden at se informationer om hardwaren, f.eks. indstruktionerne mv.
Når et program udføres, vil det oversættes af firmware/hardware fra data lageret til kode lageret og initialisere data samt pointer områderne med konstante. Dette går i princippet via noget firmware, da kun firmware kan konvertere fra en datatype til en anden.
Og hvad var så genialt? Jo, der opstod ikke nemt rod i data... For de forskellige typer, havde forskellig bitbredder. Og 64 bits addresser, var bare et par nye moduler.
Er lidt i tvivl om det er den rigtige vej at lægge alt dette i hardware. Måske er det bedre at sikre sig på anden vis - så meget som muligt af softwaren (inklusiv - især - kernen) bør skrives i sprog hvor sikkerheden kan afgøres statisk (f.eks. RUST, uden jeg selv har arbejdet i det) eller alternativt i VM'er/JIT'er der kan sikre integriteten ved kombinationer af statiske/dynamiske checks. Mht. "user space" software er der to muligheder: Enten bevares separationen mellem supervisor og user som i dag. Eller også kan man simplificere hardwaren yderligere og helt fjerne skillelinien mellem user og kernel. Kernen (som reelt bare er første indlæste program) skal så selv sikre isolationen. F.eks. ved at der kun kan afvikles software i en VM i kernen, eller der kun kan afvikles godkendt og evt. signeret software (alt for usikkert!), eller native kode i form af "proof carrying code" (længe siden man har hørt om det?) der indeholder beviset for sin egen sikkerhed. Sidstnævnte er måske lidt komplekst og kunne forestille mig performance-forskellen ift VM er beskeden. Så "VM all the way" i user space er måske vejen. Det koster nok også lidt men tilgengæld bliver mange andre ting billigere da der kun er ét space og dermed ikke kontekst-switches. Man kan have ét stort adresserum, interrupts er bare alm. calls på VM'ens stack o.s.v.
Jo men man skal faktisk også se om memory er blevet allokeret til noget andet i mellemtiden. Det kan hurtigt blive dyrt noget hvis hver eneste deallokering af memory skal se efter om nogen har pointers til memory. Det minder en smule om garbage collection.
Ja, det kan gøres med garbage collection. Ofte er en fordel, at kunne klistre ekstra informationer på pegbare data, f.eks. en dobbeltkædet liste, eller en værdi, der indikerer, hvor mange der peger på data. Vi burde faktisk angive i højniveausprogene, at data er pegbare. Derudover bør man sikre sig, at en pointer kun kan pege på relevante pegbare data - dvs. det må ikke være muligt med f.eks. pointer byte, eller pointer integer, da de fleste bytes eller integers, ingen relevans har med de pågældende data, så eventuelt skal laves en særlig datatype i hver enkelt tilfælde for at reducere pointeren til at kun kunne pege på relevante data. Dette er nødvendigt, for at holde styr på parallelismen i et program, og for at optimere den ordentligt af compileren (optimering af kode er af samme problemstilling som automatisk at parallelisere kode, så fordelene er ens). For at reducere mængden af disse informationer, er det bedst de ikke står på ethvert element i en array, så index pointere til arrays må ikke laves med pointere der peger ind i arrayet, men skal laves ved index additioner, der holdes indenfor grænserne. Compileren kan ofte analysere om grænserne overholdes uden at indbygge et run-time tjek, f.eks. er smart at kunne erklære typer, der har et bestemt interval f.eks. 0..9, så man ved at data ikke går udenfor område, eller bevæger sig cyklisk indenfor området.
Jeg kan ikke udelukke, at det bedste er at helt undgå pointere. Der er mange algoritmer, f.eks. rød-sort træer, heaps, sorteringer osv. der indeholder træstrukturer, der normalt implementers med pointers, men der kan måske findes andre metoder. Comal 80 blev lavet uden pointere i sin tid - vist nok fordi, at han ikke vidste, hvordan han skulle implementere det. Det vidste andre heller ikke, men de vidste ikke, at de ikke vidste det...
Er lidt i tvivl... Er lidt i tvivl om det er den rigtige vej at lægge alt dette i hardware. Måske er det bedre at sikre sig på anden vis - så meget som muligt af softwaren (inklusiv - især - kernen) bør skrives i sprog hvor sikkerheden kan afgøres statisk (f.eks. RUST, uden jeg selv har arbejdet i det) eller alternativt i VM'er/JIT'er der kan sikre integriteten ved kombinationer af statiske/dynamiske checks. Mht. "user space" software er der to muligheder: Enten bevares separationen mellem supervisor og user som i dag. Eller også kan man simplificere hardwaren yderligere og helt fjerne skillelinien mellem user og kernel. Kernen (som reelt bare er første indlæste program) skal så selv sikre isolationen. F.eks. ved at der kun kan afvikles software i en VM i kernen, eller der kun kan afvikles godkendt og evt. signeret software (alt for usikkert!), eller native kode i form af "proof carrying code" (længe siden man har hørt om det?) der indeholder beviset for sin egen sikkerhed. Sidstnævnte er måske lidt komplekst og kunne forestille mig performance-forskellen ift VM er beskeden. Så "VM all the way" i user space er måske vejen. Det koster nok også lidt men tilgengæld bliver mange andre ting billigere da der kun er ét space og dermed ikke kontekst-switches. Man kan have ét stort adresserum, interrupts er bare alm. calls på VM'ens stack o.s.v.
Visse ting, er bedst i hardware, blandt andet har vi meget nemt ved at lave cache. Forestil dig, at du vil kopiere et område, og anvende det nye område til data. I hardware, behøver du intet at kopiere, men kan bruge det nye område med det samme, fordi du skriver i cachen. Mens du i software, får et helvede, og risikerer at du skal vente på at kopiere en bunke af data. I hardware vil ikke være nødvendigt at bruge tid på kopieringen, da data bare læses fra det originale sted, og nye skrevne data læses fra cache - dette koster stort set ikke ektra tid, hvis hardwaren er lavet til det.
Normalt, vil vi helst programmere ens ting ens - dette er en af de grundlæggende idéer bag logik. Hvis ens ting kodes på den samme måde, og vi ikke opfinder nye måder, for at gøre det samme igen og igen, afhængigt af hvor det bruges, så er det både nemmere at regne ud uden at vide det, og det er nemmere at gennemskue, fordi vi har set det før. Dette medfører, at vi helst vil undgå, at gøre ting på forskellig måde. Koden skal være ens, uanset om vi bruger pointere, normale variable, om vi bruger ram lager, eller vi bruger harddisken. Introducerer vi forskelle, så introducerer vi fejl, fordi der er ting vi husker i et tilfælde, og glemmer i de andre, selvom det viser sig, at det er relevant alle steder. Derfor, så har vi heller ikke nogen ram lager på moderne computere - alt er cache, og ram lageret er på harddisk/filer/cloud og set fra et software synspunkt, kan vi ikke se forskel på, om vi bruger ram lageret, harddisk, eller nettet til at opbevare data. Normalt, så plejer vi at åbne en fil kaldet swap, som indeholder hele ram lageret, og ram lageret er en cache for. Hvis vi indbygger features i hardware, f.eks. en kopimaskine, så vil den ikke kun fungere på ram lageret, den vil også gøre det hurtigt at kopiere fra ram til harddisk, harddisk til ram, harddisk til harddisk osv. Så snart vi har sendt kopi ordren af sted, så er det kopieret, hvis det er på samme harddisk, og harddiskens filsystem er i orden. Er det forskellige harddiske, eller harddisk til netværk, så vil det tage tid at kopiere.
Det er en fordel, med en vis sikkerhed i hardwaren.
Det kan hurtigt blive dyrt noget hvis hver eneste deallokering af memory skal se efter om nogen har pointers til memory.
Hele pointen ved at gøre det i hardware, er at den memset(ptr, 0, len) du under alle omstændigheder skal udføre også vil slette 'her er en pointer' bits - helt uden at du skal skrive memset om.
Iflg. folkene i Cambridge er det faktisk meget lidt kode der ikke bare virker uden videre.
Og det er så i min optik præcis den slags software vi skal have renoveret til ikke at gøre den slags, så win-win ?
Tjaa ... så tror jeg det er nemmere skidtet om. Men jeg skal ærligt indrømme at det efterhånden er længe siden jeg har reviewet sourcekode i større målestok for andre C++ projecter end mine egne. Så måske er jeg bare out of touch med current state i netop denne sag.
Iflg. folkene i Cambridge er det faktisk meget lidt kode der ikke bare virker uden videre.
Spændende.
Men hvis jeg har en block af memory som jeg vil deallokere og jeg ikke ved hvem der peger ind i blokken, så skal jeg i princippet løbe hele adresserummet igennem for at se om der er pointere til min block. Det er en O(n) operation på størrelsen af memory. For hver sted hvor der er en pointer skal jeg tjekke om den peger indenfor min block. Det kan gøre mange traditionelle algoritmer til >=O(n^2) .
Man kunne selvfølgeligt opsamle referencer til alle disse blocks og så først lede efter pointere når der ikke var mere memory at tilgå. Sådan at man først invaliderede pointers delayed. Det vil ændre semantikken lidt, men ikke have nogen sikkerhedsproblemer. Det begynder også at lugte af GC (bare på en omvendt måde). Det vil måske også give et mere fragmenteret adresserum.
Eller er der noget jeg ikke har forstået her?
Men hvis jeg har en block af memory som jeg vil deallokere og jeg ikke ved hvem der peger ind i blokken
Så har du et problem, hvad enten du kører CHERI eller ej ?
Jeg tror du kigger på det fra den forkerte ende.
CHERI's mål er at tilføre pointere integritet, ikke at finde en anden måde at lave GC på.
Reglerne er præcis de samme som de altid har været, det eneste nye er at hardwaren fanger det hvis pointere bliver forsøgt overskrevet.
Reglerne er præcis de samme som de altid har været, det eneste nye er at hardwaren fanger det hvis pointere bliver forsøgt overskrevet.
Jeg tror jeg fik formuleret mig forkert.
Hvordan kan hardwaren vide hvilke pointere der er der peger ind i en block, uden at scanne hele memory? Hardwaren skal bruge den viden for at kunne invalidere alle pointere der peger til blokken.
Hardwaren kunne vente med at gøre det til koden senere tilgår pointeren men det lyder dyrt at gøre ved alle pointer accesses.
Hvordan kan hardwaren vide hvilke pointere der er der peger ind i en block, uden at scanne hele memory? Hardwaren skal bruge den viden for at kunne invalidere alle pointere der peger til blokken.
Det er er kun hardwarens opgave hvis du har GC i hardware.
Det CHERI hardwaren kan, er at invalidere alle pointere i blokken, hvis du laver en memcpy(dst, src, len) hen over den.
Det CHERI hardwaren kan, er at invalidere alle pointere i blokken, hvis du laver en memcpy(dst, src, len) hen over den.
Ok. Jeg har åbenbart misforstået noget her.
Tankeeksperiment:
p = malloc(1000) q = p free(p)
Nu peger q (og sikkert også p) til noget frigivet memory. Hvis heap manageren i mellemtiden allokerer dette memory til et andet formål, så står jeg med en pointer til memory jeg ikke burde have adgang til ... Hvad er det jeg fuldstændigt har misforstået her?
Nu peger q (og sikkert også p) til noget frigivet memory. Hvis heap manageren i mellemtiden allokerer dette memory til et andet formål, så står jeg med en pointer til memory jeg ikke burde have adgang til ... Hvad er det jeg fuldstændigt har misforstået her?
Hvilket problem CHERI prøver at løse.
Det CHERI forhindrer er:
p=malloc(100); p = (void*)((uintptr_t)p + 200); strcpy(p, "HEAPSMASH");
Min use case er ikke super relevant for diskussionen. Legen var at der skulle designes et nyt OS med frie hænder til at forholde sig til mangt og meget. Her spørger jeg blot om tidssynkronisering mellem cores er noget der er værd at overveje nu da valg af hvilke cores der skal startes og dynamisk cpu clock er nævnt.
Emnet er svært, men nok ikke irrelevant som et par bidragydere mener.
Men hvis (præcis, eller veldefineret) tid på et OS var irrelevant var der vel heller ikke brug for NTP, eller PTP, usleep(), gettime(), eller on-core clock counters som kan læses med rdtsc instruktioner?
Det var den diskussion jeg ønskede at bringe op, ikke kategoriske svar som
Der gælder generalt, at du aldrig må have tidsbegrebet på en computer. Du skal betragte CPU'en til at regne uendeligt hurtigt.
som for eksempel udelukker ethvert forsøg på at regne data rates ud, hvilket ellers godt kan lade sig gøre i praksis.
Jeg har ikke rigtig nogen holdning til disse, så for min skyld behøver de ikke være en del af Plan10 i den form :-)
Men stdin og stdout konceptet er jo en integreret del af unix pipe implementeringerne for eksempel ved
ls -1 | grep myfile | xargs cat | osv. osv.
hvor 'stdout' fra en process bliver 'stdin' for den næste.
Er der nogle spændende alternativer?
En tråd hvor der dukker lidt kode op. Det er et alt for sjældent syn i en verden hvor den slags ofte er skiftet ud med bil analogier.
Spændende.
Men hvis jeg har en block af memory som jeg vil deallokere og jeg ikke ved hvem der peger ind i blokken, så skal jeg i princippet løbe hele adresserummet igennem for at se om der er pointere til min block. Det er en O(n) operation på størrelsen af memory. For hver sted hvor der er en pointer skal jeg tjekke om den peger indenfor min block. Det kan gøre mange traditionelle algoritmer til >=O(n^2) .
Man kunne selvfølgeligt opsamle referencer til alle disse blocks og så først lede efter pointere når der ikke var mere memory at tilgå. Sådan at man først invaliderede pointers delayed. Det vil ændre semantikken lidt, men ikke have nogen sikkerhedsproblemer. Det begynder også at lugte af GC (bare på en omvendt måde). Det vil måske også give et mere fragmenteret adresserum.
Eller er der noget jeg ikke har forstået her?
Det kunne være smart, hvis alle pegebare elementer blev angivet som pegebare.
Man kan forsøge at analysere hvor pointerne kan gå hen, men jeg er ikke sikker på, at det er muligt i alle tilfælde at analysere alle muligheder statisk på forhånd. Hvis alle pegebare elementer var angivet pegebare, kunne man have en dobbeltkædet liste med de pegere der peger på elementet. Eller, man kan have en tæller, der indikerer om elementet er frit, og må dealokeres. Der er dog et par problemer, f.eks. kan man i C++ have "øer" hvor pegere peger til hinanden, og derved holder hinanden i live, og er ikke er noget der peger til øen, og så kan man ikke få adgang til at slette data eller bruge data. Automatisk garbage collection fanger den type problemer, men tager tid. Jeg tror jeg foretrækker, at man i sproget har to typer pointere - en type, der opbevare data, og som der altid er adgang til, når data eksisterer. Og en anden type, der kun peger på data, og altså ikke indeholder data. I mange sammenhæng er det mere struktureret. Vælger man, at data - uanset hvordan de er defineret, ikke har nogen værdi efter opstart, så kan man sige det svarer til, at deres pointerværdi er null, og der ikke er en værdi. Tildeles en værdi, f.eks. x=5, så svarer det til der laves en new og oprettes x, og den sættes til værdien 5. På den måde, så er ingen forskel på almindelige variable og pointere. Delete virker på begge dele. At gøre ens ting ens, er en del af det at kunne lave et logisk sprog. Det er også smart, hvis man f.eks. laver en klasse eller struct - så kan man lave den "rekursiv", når elementerne ikke er oprettet som pointer. Og en tildeling i strukturen, f.eks. root.left.left.right.data = 7 vil kunne oprette hele stien automatisk, dvs. samtlige pointere, der peger ned til data, hvis de ikke findes. Man får derved en måde, at erklære data på, hvor der er struktur, og ikke er løse elementer der hænger rundt i øer. Og dermed, er nemmere at analysere pointere, da der ikke er øer, som der ikke er adgang til.
Når man laver et programmeringssprog, så er godt at tænke sig om på forhånd, og finde løsningen på alle problemer på forhånd. Så skal de ikke løses bagefter. For det er altid et helvede. Har man løst problemerne på forhånd, og fundet en god løsning, men måske ønsker noget mere optimal kode, der ikke muliggør den samlede kompleksitet, så er bedre at slække på kravene, når man først ved hvordan det skal gøres, og hvad at ens rationalisering giver anledning til.
Desværre, så er det ikke rigtigt den tilgang man har anvendt, når man har lavet nye sprog. Det er mere en god idé + implementering, og så er det fint. Problemerne løses bagefter...
Nu kender jeg så et par sprogdesignere og det ville være synd at sige at de er store jubelfans af det nuværende paradigme indenfor hardware...
Hardware har oprindeligt været styret af, hvad det var nemt. Og det nemme er herefter gjort kompliceret fordi at muligheden har været der, og det har gjort kopieringer mere besværligt.
Re: Hvad med tid? Min use case er ikke super relevant for diskussionen. Legen var at der skulle designes et nyt OS med frie hænder til at forholde sig til mangt og meget. Her spørger jeg blot om tidssynkronisering mellem cores er noget der er værd at overveje nu da valg af hvilke cores der skal startes og dynamisk cpu clock er nævnt.
Emnet er svært, men nok ikke irrelevant som et par bidragydere mener.
Men hvis (præcis, eller veldefineret) tid på et OS var irrelevant var der vel heller ikke brug for NTP, eller PTP, usleep(), gettime(), eller on-core clock counters som kan læses med rdtsc instruktioner?
Det var den diskussion jeg ønskede at bringe op, ikke kategoriske svar som
Der gælder generalt, at du aldrig må have tidsbegrebet på en computer. Du skal betragte CPU'en til at regne uendeligt hurtigt.
som for eksempel udelukker ethvert forsøg på at regne data rates ud, hvilket ellers godt kan lade sig gøre i praksis
I den slags tilfælde, bruger jeg normalt noget der svarer til simuleringskernen i VHDL. Her bruges en heap, for at bestemme næste process der kører.
Normalt bruger man en variant af en heap - en normal heap, vil tage elementerne ud i rækkefølge, f.eks. tidsmæssig rækkefølge. Dette har imidlertid nogle ulemper, hvis der f.eks. bruge float. Så vil computeren med tiden blive "træt", fordi at tallene bliver større og større, og dermed præcisionen mindre.
Mange simuleringskerner bruger alligevel float, så de kan arbejde ned til femtosekunder og mindre, og op til lysår - men heap'en arrangeres, så der ikke er absolutte værdier, men i forhold til det niveau, som er over. På den måde, så undgår man, at den går "træt". Selv når det er integers, gør man det som regel på den måde. Ofte har man også nul-tider (zero delays), og disse håndteres ofte udenfor heap'en, så de tages først.
Det CHERI forhindrer er:
p=malloc(100); p = (void*)((uintptr_t)p + 200); strcpy(p, "HEAPSMASH");
Ok. Men det passer ikke sammen med nedenstående ...
Forestil dig at når du booter systemet starter du med en "ur-pointer" der kan læse/skrive/exekvere hele address området.
Alle andre pointere afledes fra denne "ur-pointer" i stadig finere granularitet.
Kernen laver en pointer til sin kode, en pointer til sine data og en pointer for "fri hukommelse", ingen af disse pointere overlapper.
For hver process laves der de klassiske fem pointere fra "fri hukommelse" pointeren: text, data, bss, heap & stack.
Nu kan du droppe hele VM + Protected Mode i havnen og køre kernen og alle dine processer sikkert i et og samme addresserum.
... med mindre man aldrig kan genbruge hukommelse mellem processer. Hvis process A gemmer en pointer til et stykke memory som så frigives og gives til process B, så er fanden løs. Process A kan nu accesse memory i process B.
Hvis du vil undgå søgning efter pointere sådan at de invalideres hvis de peger til et stykke memory der er frigivet, så kan man ikke bruge CHERI mekanikken (sådan som du har forklaret den) til at undgå traditionel VM+Protecte mode.
Hvordan beskytter CHERI mod at der bruges ugyldige data, som er blevet slettet?
Giver CHERI ekstra sikkerhed, i forhold til når at programmerne er compileret med alle mulige tjek på?
Er CHERI en fordel for alle programmeringssprog - også dem, der er mere sikre end C, eller er det kun en extension, for at løse et problem med C/C++.
Hvis process A gemmer en pointer til et stykke memory som så frigives og gives til process B, så er fanden løs. Process A kan nu accesse memory i process B.
Når process A frigiver memory vil kernen invalidere den mapping der associere pointerens "reach" med fysisk memory, inden den laver en ny til process B.
Den typiske maskinmodel er, at lageret ligger i et sammenhængende adresserum (typisk 64 bit), hvor forskellige processer dog kan binde logiske adresser til forskellige fysiske adresser (og hvor virtuelt lager kan fordele det fysiske lager mellem RAM og disk). Men den model har nogle begrænsninger:
Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal -- det eneste, du kan gøre, er at oprette dem med bestemt størrelse og indholde, følge dem med et offset, og nedlægge dem.
Ved oprettelse angiver du en størrelse og kode til initialisering og får en abstrakt pointer tilbage, som kan tilgås (via ikke-negative offsets) og senere nedlægges. Et forsøg på at gå udenfor grænserne eller tilgå en nedlagt pointer vil give en fejlværdi eller en exception. Du kan ikke skrive til et objekt, efter det er oprettet, og du kan ikke sammenligne to pointere eller danne nye pointere ud fra eksisterende.
Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal
Og så har vi balladen, for så er der stort set ingen af vores nuværende programmeringssprog der virker mere, mindst af alt C og C++.
Det smarte ved CHERI er at, som deres forskning har eftervist, legacykoden kører videre (bortset fra de fejl der findes i den.)
Når process A frigiver memory vil kernen invalidere den mapping der associere pointerens "reach" med fysisk memory, inden den laver en ny til process B.
"pointerens", ental.
Ja, men i et sprog som C++ har du jo mange pointere, der peger på området. Det nytter ikke noget, at den pointer du frigiver bliver sat til frigivet. Alle pegere, skal sættes til frigivet. Det vil sige, at du f.eks. skal have en liste over pegere der peger til området.
Har vi eksempelvis en peger, der peger på en byte i lageret, og en anden peger der peger på samme byte, og frigiver vi den pågældende byte med den første pointer, så skal nummer to pointer også ulovliggøres, da den ellers peger på ikke anvendt lager, eller måske på en byte brugt af en ny pointer.
Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal -- det eneste, du kan gøre, er at oprette dem med bestemt størrelse og indholde, følge dem med et offset, og nedlægge dem.
Ved oprettelse angiver du en størrelse og kode til initialisering og får en abstrakt pointer tilbage, som kan tilgås (via ikke-negative offsets) og senere nedlægges. Et forsøg på at gå udenfor grænserne eller tilgå en nedlagt pointer vil give en fejlværdi eller en exception. Du kan ikke skrive til et objekt, efter det er oprettet, og du kan ikke sammenligne to pointere eller danne nye pointere ud fra eksisterende.
Bit-slice, som jeg beskrev tidligere havde følgende egenskaber:
1) Vi kan ikke fra softwaren se bitbredden på indstruktionsord, og vi kan ikke se deres interne repræsentation.
2) Vi kan ikke fra softwaren se bitbredden på addressebusser eller pointere, og vi kan ikke se deres interne repræsentation.
3) Vi kan - afhængigt af definationen - kende bitbredden på data, men vi kan også have en model, hvor præcisionen kan øges.
Denne tankegang hjælper hardwaren til at selv kunne bestemme dens interne repræsentationer, og giver derfor mulighed for, at vi f.eks. kan kliste flere bits til typer, uden det giver problemer for softwaren.
For at kunne udføre programmer, var dog nødvendigt med en typekonvertering der f.eks. oversatte datatype til kodetype, så visse typer programmer (hardwaredel af oversætter), skulle have adgang i en særlig tilstand.
å man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal -- det eneste, du kan gøre, er at oprette dem med bestemt størrelse og indholde, følge dem med et offset, og nedlægge dem.
Ved oprettelse angiver du en størrelse og kode til initialisering og får en abstrakt pointer tilbage, som kan tilgås (via ikke-negative offsets) og senere nedlægges. Et forsøg på at gå udenfor grænserne eller tilgå en nedlagt pointer vil give en fejlværdi eller en exception. Du kan ikke skrive til et objekt, efter det er oprettet, og du kan ikke sammenligne to pointere eller danne nye pointere ud fra eksisterende.
Ja, I C++ vil compileren skulle omsætte pointer gymnastik (arithmetik) til array indexeringer, så en pointer der peger ind i et array oversættes til en array med index.
Et andet problem er, at det er nødvendigt at vide, hvilke elementer der er pointable/pegbare. Ved pegbar forstås, at det er tilladt, at en pointer peger på elementet.
Endeligt, så er et krav, at man afgrænset det område, som en peger kan pege på så meget som muligt. Det vil sige, at der ikke må være f.eks. pointer byte, der kan pege på enhver byte i lageret. En sådan operation giver bunker af problemer blandt andet med automatisk analyse. Desto mere afgrænset, at en peger kan pege, desto bedre er det.
Og så har vi balladen, for så er der stort set ingen af vores nuværende programmeringssprog der virker mere, mindst af alt C og C++.
Og, det er så ikke helt korrekt. Men, det er korrekt, at C++ har et problem med at kunne oversættes. At et sprog er nonsens og ikke kan oversættes, må være sprogets problem.
Vi kan dog godt lave oversættere, der kan forstå C++ så godt, at det normalt går godt. Og hvis den nægter at oversætte, så er der - med meget stor sandsynlighed - en regulær fejl i koden! Måske har vi bare ikke opdaget fejlen, fordi at problemet kun opstår sjældent.
Jeg vil måske foretrække et bedre sprog, men har det helt fint med at C++ kan importeres. Ved importeringen, vil man så få at vide, alle de fejl man har lavet i C++ programmet.
Jeg synes du skal tage og læse nogle af de glimrende artikler om hvordan CHERI virker, i stedet for at spilde min tid med at gætte dig frem.
Jeg har forsøgt at læse dokumentationen, men jeg syntes ikke det fremgår tydeligt af dokumentationen.
Spørgsmålet syntes jeg egentligt var meget simpel (ja/nej) - tages der hensyn til, at flere pointere peger på samme data i C++ ?
Hvordan det virker, behøver du ikke at skrive.
Jeg har forsøgt at læse dokumentationen, men jeg syntes ikke det fremgår tydeligt af dokumentationen.
Spørgsmålet syntes jeg egentligt var meget simpel (ja/nej) - tages der hensyn til, at flere pointere peger på samme data i C++ ?
Det, som jeg helt præcist ikke kan finde, er mekanismen der beskriver hvordan der holdes styr på, hvornår, og om at alle pointere er frigivet, der peger på et område. Umiddelbart, ser ud til, at man bliver nød til at reservere området for evigt, hvis man ikke holder styr på, at det ikke bruges.
Når process A frigiver memory vil kernen invalidere den mapping der associere pointerens "reach" med fysisk memory, inden den laver en ny til process B.
Ok ... så der er noget yderligere mapping. Men så er vi vist tilbage til noget til stil med page tables eller tager jeg helt fejl?
Som jeg ser det hvis man skal begrænse reach så handler det enten om at udpege en continuert del af memory som kan justeres i størrelse dynamisk (i stil med 80286 segmenter bare uden size limits) eller multiple mappings for adresserummet. Det nemmeste er i stil med pages (hvor hver page kan mappes separat). Man kunne også indsætte et ekstra niveau af indirection for hver eneste pointer (det vil ligne at have 4/8 byte pages). Segment tanken synes dead-on-arrival af rigtigt mange grunde.
Anyway, det synes værd at grave dybere i. Også selvom det nok ikke kommer i kommercielle produkter i den nærmeste fremtid.
Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal -- det eneste, du kan gøre, er at oprette dem med bestemt størrelse og indholde, følge dem med et offset, og nedlægge dem.
Ud over at smide meget C/C++ kode ud, så skal antallet af maskinekode instruktioner også hæves. Rigtigt mange instruktioner giver mening for både tal og adresser. Uden at vi ville få det helt store ud af det. Man det giver naturligtvis god mening i højniveausprog.
[quote] Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal [quote]
Og så har vi balladen, for så er der stort set ingen af vores nuværende programmeringssprog der virker mere, mindst af alt C og C++.
Det er de færreste sprog, der tillader konvertering af pointere til heltal og omvendt (C og C++ er selvfølgelig undtagelser, men f.eks. Java tillader det ikke), og det er en klar kilde til fejl og sikkerhedshuller, og forhindrer visse optimeringer (f.eks. at flytte et allokeret objekt til et andet sted i lageret eller ligefrem til en anden processor).
Ja, man kan lave en masse smart på systemniveau med den slags konverteringer, men udover systemprogrammering er der ikke nogen klar fordel ved det. Og man kunne tillade den slags konvertering med specielle instruktioner, der kun er synlige for processer med særlige privilegier, sådan at kerneprogrammører kan lave deres sædvanlige numre.
Og man kunne tillade den slags konvertering med specielle instruktioner, der kun er synlige for processer med særlige privilegier, sådan at kerneprogrammører kan lave deres sædvanlige numre.
Der er bare meget lidt grund til at lave den slags i hardwaren når nu compilere fint kan tjekke den slags. Hvis man vil bruge det til sikkerhed o.lign. så kan man passende lave sit OS sådan at det kun accepterer en form for bytecode som OS kan verificere og derefter kan OS kompilere bytecode til maskinkode. På den måde kan man også udnytte CPU features som ikke findes i alle CPU'er (fx. Intels AVX512), udnytte co-processorer, lave flere sikkerheds zoner end de traditionelle 2 (superviser vs. user), etc.
Da vel kun hvis man kan håndhæve brugen af netop disse oversættere?
Det kommer an på hvad man er ude efter. Hvis du vil beskytte udvikleren mod ham selv, så er en traditionel compiler fin. Hvis han ønsker at skyde sig i foden, så skal han nok finde en vej. Det behøver man ikke pointere eller andet guf til. Så hvis udvikleren aktivt vælger ikke at ville beskyttes så er det udviklerens problem.
Hvis det handler om at beskytte systemet/andre brugere mod udvikleren, så handler det om at undgå system crashes samt sikkerhed. I det tilfælde gør det ikke så meget hvis jeg kan lave en mystisk pointer o.lign. hvis bare den ikke kan bruges til at tilgå hukommelse som ikke er hans egen.
Der kan man vælge en løsning som CHERI (selvom jeg stadigvæk ikke helt forstår hvordan det håndterer deallokering af memory). Man kan vælge at give adgang til en del af adresserummet (fx vha. segmenter, pages) og så lade CPU'en lukke af for adgangen til resten.
Eller man kan gøre som JVM/CLR (hvis vi glemmer måderne til at lave "unsafe" code): Give brugeren en virtuel verden hvor brugeren ikke har adgang til CPU'en direkte. Hvor brugeren kommer med bytecode der kan verificeres af computeren inden den bliver til maskinkode.
I den forbindelse er der ingen grund til at den virtuelle verden skal inkludere garbage collection eller JIT. Man kan godt vælge en anden memory model eller AOT compilering. Det kan blive lige så effektivt som traditionel C++ compilering og det kan også bruges til systemprogrammering.
Det er de færreste sprog, der tillader konvertering af pointere til heltal og omvendt (C og C++ er selvfølgelig undtagelser, men f.eks. Java tillader det ikke), og det er en klar kilde til fejl og sikkerhedshuller, og forhindrer visse optimeringer (f.eks. at flytte et allokeret objekt til et andet sted i lageret eller ligefrem til en anden processor).
Ja, man kan lave en masse smart på systemniveau med den slags konverteringer, men udover systemprogrammering er der ikke nogen klar fordel ved det. Og man kunne tillade den slags konvertering med specielle instruktioner, der kun er synlige for processer med særlige privilegier, sådan at kerneprogrammører kan lave deres sædvanlige numre.
Du kan godt automatisk omskrive C++ til at bruge array med index, i alle tilfælde hvor der laves pointergymnastik - og koden giver mening. Du indfører at pointere også har et index felt. Normale pointere, der ikke laves arithmetik på, er som de almindelige pointere i C++. Deres index felt er altid nul (kan evt. udelades af optimeringen). Mens pointere der laves aritmetik på, der laves aritmetikken på index feltet alene, og pointeren er således altid en "root" pointer, der peger til starten af et array. En pointer, der laves aritmetik på, skal pege på et array. Ellers giver koden ikke mening.
Når compileren selv indsætter array-pointere med index, så har den nemt ved at optimere (i nogle tilfælde bedre), og den kan identificere at pointere peger på noget valid. Dette sker igen ved at tilføje ekstra felter, f.eks. et match-felt til pointeren. En peger, der peger på statiske variable, porte, fast memory, har en match-felt på et særligt værdi, så den ikke bruges (0), men er sat til at altid være ok. En peger som peger på et felt, der kan være frigivet, har et tilfældigt match-felt, der genereres ud fra det forrige match-felt, således man sikrer sig en lang minimum periode. Det kan også gøres på andre måder end match-felter. Igen, kan compileren optimere, så matchfeltet forsvinder, for pointere hvor den aldrig bruges.
Det er meget enkelt, at indbygge sådanne tjek i C++ compileren. Det er bare at oversætte med tjek på.
Problemet er nok mest, at C++ compilerne ikke har mulighed for tjek.
Dette sker igen ved at tilføje ekstra felter, f.eks. et match-felt til pointeren. En peger, der peger på statiske variable, porte, fast memory, har en match-felt på et særligt værdi, så den ikke bruges (0), men er sat til at altid være ok. En peger som peger på et felt, der kan være frigivet, har et tilfældigt match-felt, der genereres ud fra det forrige match-felt, således man sikrer sig en lang minimum periode. Det kan også gøres på andre måder end match-felter. Igen, kan compileren optimere, så matchfeltet forsvinder, for pointere hvor den aldrig bruges.
Hvis det er 64 bits pointere behøver man ikke match-felt. Så kan man dupplikere lageret f.eks. 65536 gange, hvilket svarer til et match-felt på 16 bits. Når et lagerområde frigives, så bruger men den næste af de 65536 kopier, i stedet for den originale. Pointerne har forskellig addresse de første 64K gange, selvom de peger på samme område. Dette svarer helt til et match-felt, hvis det ikke er muligt med 64 bits pointere i hardware.
Hvis det er 64 bits pointere behøver man ikke match-felt. Så kan man dupplikere lageret f.eks. 65536 gange, hvilket svarer til et match-felt på 16 bits. Når et lagerområde frigives, så bruger men den næste af de 65536 kopier, i stedet for den originale. Pointerne har forskellig addresse de første 64K gange, selvom de peger på samme område. Dette svarer helt til et match-felt, hvis det ikke er muligt med 64 bits pointere i hardware.
Her var jeg lidt for hurtig - der skal for det reserverede lagerområde gemmes en kopi af pointeren, så man sikrer sig, at data kun kan bruges for den korrekte pointer. Så det er stort set ligeså nemt at bruge en match-pointer.
Der kan man vælge en løsning som CHERI (selvom jeg stadigvæk ikke helt forstår hvordan det håndterer deallokering af memory). Man kan vælge at give adgang til en del af adresserummet (fx vha. segmenter, pages) og så lade CPU'en lukke af for adgangen til resten.
Enig!
Men, som jeg har beskrevet, er det ikke et problem at indbygge i compileren, og man kan også indbygge hardwarefeatures til alle former for tjeks, så det ikke tager tid.
Jeg har dog svært ved at se fidusen i CHERI. En bunke af dokumentation og historier - og når man så sammeligner med de reelle problemer, så står ikke nogen løsninger.
Men, som jeg har beskrevet, er det ikke et problem at indbygge i compileren
Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?
En "walled garden" hvor al kode skal afleveres i kildetekstform ?
CHERI prøver at løse det svære problem: Situationen hvor du ikke kan stole på at det binære program er dig venligtsindet.
Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?
En "walled garden" hvor al kode skal afleveres i kildetekstform ?
CHERI prøver at løse det svære problem: Situationen hvor du ikke kan stole på at det binære program er dig venligtsindet.
Vi har her to muligheder:
Vi kan lade C++ compileren bestemme selv, og tillade den gør det rod den gør, bare det ikke går ud over andre programmer. Det er tæt på den model, der bruges i dag.
Vi kan se på, hvordan at C++ compileren skal oversætte, for at gøre det sikkert, og hvordan at fejltjek skal lægges ind. Og vi kan så sikre os, at alle disse problemstillinger, er løst i vores model. Ellers, så risikerer vi, at få noget forkromet bras, der ikke fungerer i virkelighedens verden.
Så min udgangspunkt, hvis jeg skulle lave noget som CHERI, er at jeg først vil gennemgå systematisk samlige problemer der findes i C++. Så vil jeg gennemgå hvordan de løses. Og, til sidst, vil jeg lave dem om til en hardwaremodel, og vise at alle problemerne fra C++ er løste.
Og her er C++ et glimrende sprog. For, har man løst alle problemer der er i C++, så vil andre sprog nok heller ikke give problemer. Ellers, skal de være kreative.
Problemet er at CHERI så vidt jeg kan se, ikke løser problemerne.
Kan heller ikke se hvordan man generelt kan bygge det ind i compileren. Hvis pointeren kan følges med dynamisk indeks kan det jo ikke afgøres af kildeteksten generelt om dette index kan være out-of-bounds. Compileren kan derfor kun løse problemet ved at indsætte kode til runtime check - og det koster! Hvor hardwaren måske kan det gøre det gratis, i hvert fald i tid (blot en ekstra ALU på chippen) men måske ikke i strøm.
"Drømmen" (for nogen) ville måske være et programmerinsgsprog der har abstrakte pointere som Torben beskriver, og hvor programmøren ydermere kan specificere et bevis for at indexet ikke går out of bounds. Vil overraske mig hvis det ikke findes. Men alt det har aldrig rigtig slået an. Meget software ville helt sikkert kunne have gavn af det, og hvis det var mainstream kunne det nok gøres udviklervenligt - uden man skulle have en PhD grad i matematik/datalogi! Et problem med den slags akademisk teknologi er er ofte at der er en masse cool forskningsprojekter, men de tager i sagens natur kun teknologien til et vist niveau f.eks. ét programmeringssprog måske endda kun et fragment heraf. Hvor programmer ude i den store verden består af en masse frameworks og i en masse store sprog, native kode etc. som skal interagere og gør det mere end tungt meningsfyldt at benytte teknikkerne. Dertil bliver den slags systemer sjældent vedligeholdt hvis der er udviklet i forbindelse med en Ph.D. afhandling. Engang imellem kommercialiseres den type teknologi, men ofte i en stærkt cut-down der enten er stært begrænset i anvendelsesområde eller hvor værdien er stærkt fortyndet.
En "walled garden" hvor al kode skal afleveres i kildetekstform ?
Ja, eller i et kode format for operativsystemet, så operativsystemet laver oversættelsen til den pågældende hardware. I princippet, bør intet være skrevet i maskinkode, andet end selve CPU driveren - intet andet må indeholde en eneste maskinkode linje/byte.
Vi har måske en masse ARM og Intel kode, som så ikke umiddelbart vil kunne udføres. Så, skal man lave et kodeformat til et operativsystem, så vil være en god idé, at overveje hvordan man laver en in-time compiler, til både ARM kode, og Intel kode, således at det kan køre ligeså hurtigt simuleret, eller endda hurtigere simuleret, end det kører på hardware.
Kan heller ikke se hvordan man generelt kan bygge det ind i compileren. Hvis pointeren kan følges med dynamisk indeks kan det jo ikke afgøres af kildeteksten generelt om dette index kan være out-of-bounds. Compileren kan derfor kun løse problemet ved at indsætte kode til runtime check - og det koster! Hvor hardwaren måske kan det gøre det gratis, i hvert fald i tid (blot en ekstra ALU på chippen) men måske ikke i strøm.
Ok, jeg gik ikke i detaljer. Fidusen er, at du selv systematisk går frem med alle mulighederne.
En pointer, der bruges til at pege på et array, skal have flere felter: pointerværdi, index værdi, størrelse, og match-værdi.
Hvis du laver pointer aritmetik, så arbejder du med index, og tjekker på størrelsen. Hvis pointeren peger til et område, der kan frigives, tjekkes også på match-værdi. Match-værdien, er en ekstra felt, der oprettes som del af elementet som pegeren peger på, og den oprettes af new/allocate. Eventuelt, kan den lægges på addressen -1 i forhold til data. Denne skal passe med pointerens match værdi. På den måde sikres, at frigivet hukommelse, der bruges igen, får en ny match-værdi, og derved ikke vil være kompatibel. Metoden med match-værdier, er er udmærket til at give en nogenlunde sikkerhed, men den er langt fra god alene. Der skal f.eks. være et felt der holder styr på, hvor mange der peger på data, så vi kan sikre os, at der ikke er nogle pegere, på et element vi frigiver. Og, vi skal også tænke på ø-problemet, altså pegere der peger på sig selv, og holder hinanden i live, selvom vi fjerner den pointer, der giver adgang til dem. Dette kan medføre, at vi får memory leak, fordi vi aldrig kan få adgang til at slette data. Derfor foretrækker jeg at programmeringssproget sikrer der ikke er øer, ved at alle data som pegere kan pege på er arrangeret i struktur der altid er en adgang til, og hvor man kan se hvor mange data der er i strukturen, og dens understrukturer.
Det er således ikke kun pointerne der skal have flere felter. Det er også de data, som pointerne peger på, der skal have ekstra felter. Hver gang, at vi opretter et element med new, så skal der være nogle skjulte felter, til dette element. Dette er relativt nemt at implementere i compileren, at den altid opretter lidt ekstra data, hver gang du bruger new. Bruger du pointere, som ikke peger på data der kan slettes, så behøver du ikke disse felter. Så du kan sagtens have pointere til normale variable der ikke har ekstra felter, hvis variablen er permanent - dette vil ikke nødvendigvis sige permanent, men at pointeren nedlægges før, eller senest sammen med data den peger på.
I C++ vil dine variable oftest eksistere i et skop. Det betyder, at du risikerer din pointer er erklæret udenfor skopet, og de data du sætter den til at pege på er på stakken, og derfor ugyldige udenfor skopet. Her er den nemme måde, at compileren nægter dette. Men, skal vi have det ind i hardwaren, så skal vi også tage stak problematikken, og pointer til stak problematik med.
En løsning, er at gemme en bunke af skjulte felter, til hver eneste byte i ram lageret. Det fylder ekstremt. Nogle har gjort det, at de har defineret at new og allocate altid skal placeres på bestemte addresser, f.eks. modus 16 = 0. På den måde reduceres den mængde ekstra data der er nødvendigt for housekeeping og man gemmer de ekstra felter der skal bruges for hver blok på 16 bytes eller 32 bytes.
Mit forslag er, at man går alle problemerne igennem i C++, samt løsningerne, og definerer et "maskinkode" - der tager højde for det hele. Det er ikke så svært. Jeg har skitseret, nogle af de lidt svære problemer ovenfor.
Compileren kan derfor kun løse problemet ved at indsætte kode til runtime check - og det koster! Hvor hardwaren måske kan det gøre det gratis, i hvert fald i tid (blot en ekstra ALU på chippen) men måske ikke i strøm.
Ja, det er korrekt. De metoder jeg beskriver, er også til run-time tjek. Det koster lidt, men ikke nødvendigvis så meget - runtime tjek kan nemligt udføres parallelt med den kode som udføres, så det øger CPU'ens mulighed for at parallelisere. Hvis vi ved hvad vi har brug for af run-time tjek, så kan vi også nemt gøre dem til del af CPU'ens indstruktionssæt, så de udføres automatisk. Det største problem ved run-time tjek, er ikke tiden de koster, men at softwaren ikke definerer hvad der skal ske ved fejl.
Ved at indlægge tjekket i compileren, så løses dette problem oftest. Man kan statisk "simulere" koden igennem, og lave nogle worst-case analyser på range check for alle variable, og derved i nogle tilfælde bevise, at der ikke sker fejl. Dette tvinger programmøren til, at lave range tjek i selve koden, da den ellers ikke kan oversættes. Det pågældende range-tjek, vil medføre at compileren kan indse, at værdien ikke kan gå udenfor det pågældende range, i den pågældende del af koden, og så kan compileren bevise, at det ikke går galt. Det tager ikke lang tid for compileren at lave sådan en test, da det i princippet er en O(1) analyse, så dens kompleksitet er lig størrelsen af koden. Så glemmer man, at tage højde for ranges i koden, så giver den fejl. Der kan være tilfælde, hvor compileren kræver, at vi tager højde for ranges, ved at f.eks. sammenligne med min/max, også selvom vi måske kan manuelt bevise, at det ikke går galt. På den anden side, så betyder det ikke meget, at skulle lægge noget tjek ind, hvis compileren kræver det.
Selvom de er beregnet til run-time tjek, så er en god idé, at gå dem igennem systematisk, og så eventuelt lave et maskinsprog der garanteret løser alle problemer. Det vil være et stort plus - ingen C++ compilere, kan oversætte C++ til vås mere. Men, igen, stadigt nok bedre, at compileren brokker sig - for vi vil hellere vide på forhånd de fejl vi har begået, end få dem at vide som en kryptisk ulovlig handling oplyst til brugeren.
Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?
En "walled garden" hvor al kode skal afleveres i kildetekstform ?
Nej det tror jeg ikke på. Ikke helt.
Al kode skal leveres i ELF filer indeholdende "Michaels Byte Code™" (MBC). Lidt på samme måde som en JVM kun vil spise Java Byte Code og CLR kun vil spise CIL. Bare uden det manglende typesystem i JVM og uden Garbage Collection.
Så i stedet for at systemet kunne eksekvere ELF filer med x86, x64 eller ARM kode, så kunne det kun eksekvere ELF filer med MBC. Det første operativsystemet gjorde når det skulle eksekvere MBC var at verificere at den leverede code var velformet og herefter ville den blive oversat til x64/ARM code af operativsystemets backend compiler. Resultatet gemmes i en cache der er under operativsystemets kontrol sådan at compileringen kun skal ske en gang. Hvis nogen har lyst kan de fortsætte med JIT compilering senere og således udnytte opsamlet statistik til at optimere yderligere men det er på ingen måde nødvendigt.
Man kan godt oversætte C/C++ til et MBC lignende sprog. Det er ikke fantastisk effektivt fordi runtime intet ved om lifetime af memory på heapen og således vil være nødt til at wrappe dem. Det er ofte problemet med heapen. I runtimes med GC udnyttes at man har et antal root pointer som runtime kender til og at man kender datamodellen. Man kan således traversere alle levende objekter. I traditionel C/C++ kan alt memory i princippet være pointere. Både med CHERI og i den verden jeg forstiller mig vil den mulighed gå væk. Pointere skal gemmes i variable af typen pointer.
Derfor vil sådan en ændring også i praksis kræve et skifte til sprog hvor der er mere klare regler for lifetime og hvor pointers kun kan forefindes hvor datamodellen siger det. Rust synes at være et godt eksempel på et sprog der forener mulighederne og performance fra C/C++ med et stærkere typesystem og viden om lifetime fra mere moderne sprog. Specielt fordi pointers i de fleste tilfælde udskiftes med referencer på samme måde som i moderne C++.
Der er i mine øjne intet der stopper en MBC execution engine fra at blive lige som effektiv som traditionel C/C++ kode. Jeg har læst at de først forsøg på at køre Rust på CLR giver samme performance som Rust native.
PS: MBC behøver ikke stå for Michaels Byte Code.
Og, til sidst, vil jeg lave dem om til en hardwaremodel, og vise at alle problemerne fra C++ er løste.
Problemet med at lave hardware modeller er at hardware modeller helst skal være stabile de næste 20 år. Hvis man lover for meget så bliver det svært at vinde performance i de næste generationer af CPU designet. Transistorcount er også begrænset (fx. har de nyeste CPU'er kun ca. 50 mia. transistorer) og derfor er der fornuft i at bruge dem til noget der er nødvendigt.
Intel lavede en microprocessor der hed i860. Intel havde fundet ud af at designe instruktionssættet sådan at når man udførte en instruktion så kom svaret først to instruktioner længere nede. Det var helt fantastisk for Intel for det simplificerede decoding af instruktioner og implementering af pipelinen. Eksempel (i pseodo kode):
mov 0, r2 mov 2, r1 mov 40, r2 add r1, r2, r3 add r1,r2, r4 ; State: ; r1 = 2 ; r2 = 40 ; r3 = 2 ; r4 = 42
i860 var fantatisk hurtig da den kom frem. Problemet var bare at man havde eksponeret dybden af pipelinen til softwaren og det gjorde det sværere at videreudvikle skidtet. Der kom derfor ganske få versioner af den.
i860 var et godt eksempel på en CPU der lovede noget til softwaren som det blev svært at holde på længere sigt. Intel har også lovet nogle ting omkring cache coherency i x86/x64 linjen som har været dyre at holde gennem årene. Af samme grund mangler samme "løfter" i ARM (så hut jeg visker).
Ovenstående er blot et argument fra at holde ting ude af hardwaren som kan løses af software (incl. compilere).
Re: Tid til at glemme lineære adresserum?
Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?
En "walled garden" hvor al kode skal afleveres i kildetekstform ?
Nej det tror jeg ikke på. Ikke helt.
Al kode skal leveres i ELF filer indeholdende "Michaels Byte Code™" (MBC). Lidt på samme måde som en JVM kun vil spise Java Byte Code og CLR kun vil spise CIL. Bare uden det manglende typesystem i JVM og uden Garbage Collection.
Så i stedet for at systemet kunne eksekvere ELF filer med x86, x64 eller ARM kode, så kunne det kun eksekvere ELF filer med MBC. Det første operativsystemet gjorde når det skulle eksekvere MBC var at verificere at den leverede code var velformet og herefter ville den blive oversat til x64/ARM code af operativsystemets backend compiler. Resultatet gemmes i en cache der er under operativsystemets kontrol sådan at compileringen kun skal ske en gang. Hvis nogen har lyst kan de fortsætte med JIT compilering senere og således udnytte opsamlet statistik til at optimere yderligere men det er på ingen måde nødvendigt.
Man kan godt oversætte C/C++ til et MBC lignende sprog. Det er ikke fantastisk effektivt fordi runtime intet ved om lifetime af memory på heapen og således vil være nødt til at wrappe dem. Det er ofte problemet med heapen. I runtimes med GC udnyttes at man har et antal root pointer som runtime kender til og at man kender datamodellen. Man kan således traversere alle levende objekter. I traditionel C/C++ kan alt memory i princippet være pointere. Både med CHERI og i den verden jeg forstiller mig vil den mulighed gå væk. Pointere skal gemmes i variable af typen pointer.
Derfor vil sådan en ændring også i praksis kræve et skifte til sprog hvor der er mere klare regler for lifetime og hvor pointers kun kan forefindes hvor datamodellen siger det. Rust synes at være et godt eksempel på et sprog der forener mulighederne og performance fra C/C++ med et stærkere typesystem og viden om lifetime fra mere moderne sprog. Specielt fordi pointers i de fleste tilfælde udskiftes med referencer på samme måde som i moderne C++.
Der er i mine øjne intet der stopper en MBC execution engine fra at blive lige som effektiv som traditionel C/C++ kode. Jeg har læst at de først forsøg på at køre Rust på CLR giver samme performance som Rust native.
PS: MBC behøver ikke stå for Michaels Byte Code.
Jeg kan ikke være mere enig.
Du skriver ikke meget om parallelisme. Men, du skal have tanken ind over MBC. Som jeg tidligere har nævnt, så giver tid ikke altid mening. Måler vi tiden, mellem to indstruktioner der tilsyneladende kører i rækkefølge, kan de udføre i omvendt rækkefølge, eller rækkefølgen ændret af optimingen. Så der kan nemt ske, at være negative tid. I nogle tilfælde, så er nødvendigt med et tidsbegreb. Det giver ingen mening internt i CPU'en, men kun mening på I/O. Tid, findes heller ikke inde i en kvantecomputer. Det findes kun på I/O. Tid opstår og findes kun, ved grænsefladen til den fysiske verden.
Problemet med at lave hardware modeller er at hardware modeller helst skal være stabile de næste 20 år. Hvis man lover for meget så bliver det svært at vinde performance i de næste generationer af CPU designet. Transistorcount er også begrænset (fx. har de nyeste CPU'er kun ca. 50 mia. transistorer) og derfor er der fornuft i at bruge dem til noget der er nødvendigt.
Nej, det er egentligt ligegyldigt. Men, du skal altid kunne simulere en gammel hardwaremodel, på en ny computer, ved hjælp af in-time compilering. Vi kender bedst til in-time compilere i java byte kode sammenhæng. Men, du kan gøre det samme, med en helt normal computer indstruktionssæt, stort set ligegyldigt hvordan den er lavet. Det er intet problem at lave in-time compilere, til at oversætte ARM indstruktionssættet, eller Intel indstruktionssættet til fremtidige computere. Jeg har tidligere beskrevet lidt om hvordan det foregår, og det optager lidt hukommelse. Men, på grund af MMU'en, så optager det ikke vildt hukommelse alligevel. Vi kan lave programmeringssprog, der er egnet til trin-vis compilering, og det syntes jeg er bedre. Du kan godt udføre et Intel indstruktionssæt, eller et ARM indstruktionssæt på en computer, der er lavet til trin-vis compilering, og placere compileren i en driver. Det betydre, at du til enhver tid, kan udskifte din CPU med en anden model, med andet indstruktionssprog, og den kan stadigt køre Intel kode, eller ARM kode. Også uden det tager tid at fortolke. I nogle tilfælde, går in-time emulering endda hurtigere, fordi at nogle kan finde på at lægge smarte optimeringer ind. Og, at de processorer som emlulerer, kører normalt også hurtigere, end dem de emulerer.
En svære tilgang, som jeg tror stadigt er lidt i forskningsstadiet, er at lave computere, der "forstår" koden. En sådan computer, kan selv oversætte en emulator kode, der f.eks. emulerer en ARM, til en in-time compiler, og derved tager ikke tid at emulere mere, da alle emulatorer forenkles bort at processoren.
Men, ingen tvivl om, at jeg er tilhænger af MBC kode. Alle operativsystemer burde være skrevet i MBC, også hardware driverne, undtagen CPU driveren. Man kan opdele CPU driveren i to. En hardware driver, der indeholder CPU'ens native indstruktionssæt. Og en MBC del, der står for den del af in-time oversættelsesprocessen, der er hardwareuafhængig. På den måde får hardwareproducenten support fra MBC delen, og det bliver nemmere for dem, at skrive en god hardwaredriver. Og forbedres MBC delen, så forbedres oversættelsesprocessen, uafhængigt af producent af processoren.
Tillykke!
Du har lige genopfundet Java Virtual Machine ?
Den er der som bekendt ingen der har skrevet en operativsystemkerne med endnu ?
Useriøs kommentar.
Der er rigtigt mange ting galt med JVM. Specielt hvis man vil lave et OS, så er GC en rigtig dårlig ting. Det håbløse typesystem er også et problem rigtigt mange steder. På mange måder er Microsofts CLR meget bedre selvom den også har sine problemer og er GC baseret.
Men blot fordi en teknik er brugt til en ting betyder det ikke at den ikke kan bruges til andre ting. En dårlig implementering betyder heller ikke at teknikken er skidt. Jeg gætter på du også kan huske OS kerner der var skrevet mest i maskinkode af performance grunde. Den slags findes vist ikke længere til andet en 8 bit microcontrollere. Alle general purpose operativ systemer er nu næsten 100% skrevet i højniveausprog.
JVM har en fantatisk avanceret optimizer der kigger på statistik for compileret kode og laver inplace replacement af kode med ny og bedre version. Det vil nok være lidt for avanceret for en OS kerne. Men den maskinkode der kommer ud af Microsofts CLR er nogenlunde lige så effektiv som den der kommer ud af en C compiler. Minus for CLR er GC som traditionelt har været håbløs (jeg har ikke fulgt med de sidste år) og under alle omstændigheder er et no no til systemprogrammering.
Men det jeg foreslog var nærmere at tage backenden af compileren og putte ind i OS. Det er en lille del af hvad JVM laver.
Og en MBC del, der står for den del af in-time oversættelsesprocessen, der er hardwareuafhængig. På den måde får hardwareproducenten support fra MBC delen, og det bliver nemmere for dem, at skrive en god hardwaredriver.
Problemet er typisk at der er nogle forskelle omkring memory modeller som man er nødt til at abstrahere væk. Sidst jeg kiggede på ARM og Intel var multiprocessor situationen ganske forskellig. Intel lover som tidligere beskrevet nogle ting omkring cache coherency som ARM ikke lover. Det med at finde en unified memory model som samtidigt er 100% effektiv på alle platforme er ikke helt nemt. Og specielt til operativ systemer er den slags vigtigt (men også til en række andre ting). Det er dog efterhånden længe siden jeg har været ned i det "rabbit hole" så der kan være sket meget.
Useriøs kommentar.
Nej, det er dybt seriøst ment.
Argumenterne for at have JVM og for den sags skyld PASCAL's P-code var præcis de samme som dem du fremførte.
Og det er absolut en brugbar model når man arbejder i en "walled garden".
Men det løser stadig ikke problemerne når vi taler lav-niveau systemprogrammering.
Husk på at CHERI også checker hvis det er skrevet i assembler.
Problemet er typisk at der er nogle forskelle omkring memory modeller som man er nødt til at abstrahere væk. Sidst jeg kiggede på ARM og Intel var multiprocessor situationen ganske forskellig. Intel lover som tidligere beskrevet nogle ting omkring cache coherency som ARM ikke lover. Det med at finde en unified memory model som samtidigt er 100% effektiv på alle platforme er ikke helt nemt. Og specielt til operativ systemer er den slags vigtigt (men også til en række andre ting). Det er dog efterhånden længe siden jeg har været ned i det "rabbit hole" så der kan være sket meget.
Ja, du har ret. Det er ikke selve indstruktionsættet, som det er svært at emulere effektivt med en in-time compiler - men memory modellen.
Jeg anbefaler, at processorer laves med en memory model, der muliggør hurtig flytning og kopiering af data. Det er også rigtigt godt, i forbindelse med dynamisk allokering, at f.eks. kunne indsætte en byte et sted i lageret, ved hjælp af hardware. Det er forholdsvis nemt at implementere, så hardwaren styre det, uden at bruge tid på kopieringen.
Og harddisken tilknyttes memory modellen, således at åbne filer tildeles et område i ram'en, og at den indbyggede kopiering derfor også fungerer på data der kopieres til harddisk, eller mellem filer på harddisken. Det vil være en fordel, at filsystemet håndtere kopierede data, selvom det medfører fragtering. Man kan så have en defragtering til at køre, men det er en stor fordel, at data kopieres øjeblikkeligt, når det er internt på harddisken. Det er næsten en nødvendighed, med en MMU der har harddisken med, når MMUen håndterer hardwarekopiering, uden der fysisk flyttes data i ram'en. Mange MMU'er kan håndtere kopiering af data, men de er lavet til at fungere i segmenter, svarnede til sektorer på harddisken, så det ikke kan ske bytevis. Der mangler et felt i deres MMU der angiver offset, så data kan flyttes skævt, i forhold til organiseringen.
Men det løser stadig ikke problemerne når vi taler lav-niveau systemprogrammering.
Som Michael skriver, så kan du godt have et defineret sprog, der er lavet til lav-niveau systemprogrammering. Timingmæssigt, kan være nogle problemer, hvis du pludseligt laver en oversættelse, midt i et tidskritisk interrupt. Men, det er netop det, at der også skal tages hensyn til i modellen.
Desværre er der mange der tror, at fordi at nogen har gjort et halvhjertet forsøg - f.eks. Java Byte Kode, at så beviser det, at det ikke er muligt at lave noget der er i orden. Den bedste måde, at modbevise noget kan gøres på, er at offentliggøre en afhandling, der demonstrere at man ikke (selv) kan. Herefter, er ingen grund til at andre gør det, for det er forsøgt, og det lykkedes jo ikke.
Jeg går ind for MBC! Bare det, at få et sprog, der fungerer for alt - også hardwaren - det vil være et stort plus. Hardwarefolkene vil elske, at de bare skal plukke en simpel hardwaredriver sammen, og så fungerer deres CPU og hardware uanset hvordan at softwaren er lavet. MBC vil være et stort plus for hardware udvikling. Stort set hvemsomhelst vil kunne lave deres egen hardware, CPU osv. og de vil kunne bruge et operativsystem, og software, der kører på alt.
CHERI is a linear descendant of the CAP on which I worked for my PhD. Good C++ (e.g., see the C++ Core Guidelnines) can run on a capability- based architure. And yes, we need hardware support for better security and fewer bugs.
CHERI is a linear descendant of the CAP on which I worked for my PhD. Good C++ (e.g., see the C++ Core Guidelnines) can run on a capability- based architure. And yes, we need hardware support for better security and fewer bugs.
Is hardware support needed - could we not add compilation with better test to C++ compilers, and obtain the same - maybee with a bit slower handling of pointers?
However, some C++ programs may fail, if we demand that an element need to be free (no pointers points at it), before it can be deleted.
If we accept pointers not to be free, it will take up more time to check, since we need to check not only at new/delete, but also at every use of the pointer that it is valid.
I guess that there will not be much difference on speed in future processors. The check will both if hardware supported, and if coded into software, have the same dependencies, and the hardware will be able to run faster (more parallelisme), if the check is in software.
Så man burde måske gøre pointere til abstrakte objekter, der ikke kan inspiceres ved f.eks. at konvertere dem til tal -- det eneste, du kan gøre, er at oprette dem med bestemt størrelse og indholde, følge dem med et offset, og nedlægge dem.
Yes, I think that it is not a problem in C++. You can see a pointer as an abstract pointer pointing to a random value (start of data area in an allocated block), and an offset pointing to the element. However, it could also be arrays in the sub-structure, and the compiler need to generate code, to verify the pointers that points into arrays, but that should be possible, and be able to validate too. The compiler could make a static analyze the range of the pointers and other variables, and allow it to be determined at compile time, if it goes out of range. If the code has a condition, that elimitantes the possibility, that the variable/pointer is over or under a value, the limits of the variables can be determined as long as the programmer remember to check them. And, in that case, it knows that the variables will be within limits of the arrays, and thereby not need any check. So, checks might not be needed in many cases.
Yes, I think that it is not a problem in C++. You can see a pointer as an abstract pointer pointing to a random value (start of data area in an allocated block), and an offset pointing to the element.
Sorry, it should say and an offset pointing into the element.
In c++ you are able to do calculations on the offset part only - the abstract part is never accesable in C++. Two pointers, need to be pointing to same element (same abstract part), to be comptible and able to subtract, to get the element value. It is only the offset part of abstract pointers, that is used for pointer calculations.
C++ knows, where an array is placed in the offset part, and makes sure, that it only points at beginning of its elements because it multiply its size. It could validate the limits as well. Then we are sure, that there is no errors in pointing to arrays, or sub-elements. To validate abstract pointers, is very easy, because it is possible to keep track of the elements they point at, and how many pointers, that points on an element. Typical, these informations is stored together with the element, that the abstract pointer points at, if it is a dynamic allocated element, but not used if it is static.
If a pointer points on data on stack (in a scope), the compiler could verify or move the pointer into the scope, to make sure it is released together with data it points at (local data), and that the pointer not points to stack data, when it goes out of scope that it is set to point at. In that way, it points to static defined data, and verfication could be done staticly without run-time errors.
Still, I think that a static compiler check, is better than run-time checks. The CHERI model only adds run-time check to hardware, and they should preferly be avoided. We like to know the errors before release, and not to show up at the customers.
Still, I think that a static compiler check, is better than run-time checks. The CHERI model only adds run-time check to hardware, and they should preferly be avoided. We like to know the errors before release, and not to show up at the customers.
If the compiler checks ranges for variables, it also easy could do a NULL check on pointers. In any case, where it could see that a pointer can't be zero, and can't be out of range, and that the pointer points to allocated memory, then it does not need to add any check.
This is the most safe way to do it. Do not accept the code, if the compiler can't do a static analyze that accepts ranges and NULL. The only problem, is to check if a pointer points to allocated memory. That could easy be done run-time. C++ is however a bit difficult to make total safe, because there might exists memory, that we remove the way to access. But CHERI does not check for memory leaks either.
Lifetime and memory safety are checked by the core gidelines static analysis checker that ships with Visual Studio. Clang Tidy also has some CG checks, but it's still a bit behind.
Even given that, I'd like to see hardware support for safety. Hardware and software can complement each other. Jens D Madsen points out that CHERI doesn't prevent memory leaks. On the other hand, the CG checked does that.
Lifetime and memory safety are checked by the core gidelines static analysis checker that ships with Visual Studio. Clang Tidy also has some CG checks, but it's still a bit behind.
I will take your word for it, but there seems to be a lot of gotchas that are hard to check for. I guess that is why you want the hardware checks too.
I did spend 15 years writing C++. I love the ability to control everything but I hate the fact that it just takes one bad programmer (the other guy; not me) to ruin the day for the whole team. I don't write a lot of C++ anymore but I do follow the news. Thus I may be a bit out of touch with the current situation.
What I would really like is a language with all of the flexibility and power of C++ but without the pitfalls that leads to memory corruption. All the other pitfalls I am fine with. It appears that a lot of the stuff after C++98 is there to help avoid those problems.
One of the fantastic things about writing JVM/CLR hosted code is that you never get a stacktrace that has been overwriten. You always get an error when someone attempts to access a "pointer" that is invalid. Obviously that comes with a fairly significant price - one that is not acceptable in many cases.
I would gladly get rid of the ability to end up with dangling pointers for new code. And by getting rid of it, I mean completely. No way of doing it. Code would not compile. Not because of myself, but the other guy you know. The one that makes mistakes.
I am willing to learn a new language and force that on my team. We will write all new code in that language and I do not care if the language is called C++20/Rust/Sodium/XYZ. As long as we at compiletime can ensure that the bad code the other guy write or the library he downloaded from the internet which runs only once a month, cannot screw up my code due to memory corruption. Also for multithreaded code.
Og det er absolut en brugbar model når man arbejder i en "walled garden".
Men det løser stadig ikke problemerne når vi taler lav-niveau systemprogrammering.
Jeg er selvfølgeligt enig i at der skal skrives en p-Code compiler. Og en bootloader. Men jeg kan ganske enkelt ikke se hvorfor lav-niveau systemprogrammering ikke kan ske på en måde der først bliver til en form for p-Code. p-Code kunne ligne mellemcode i compileren. For kernen i operativsystemet kunne compileringen fra p-Code til maskinkode i princippet ske i byggefasen. Det vil selvfølgeligt kræve et nyt OS skrevet i et nyt sprog der har en p-Code der kan verificeres safe. Der synes bevægelser i den retning med Rust. Blot uden p-Code.
Husk på at CHERI også checker hvis det er skrevet i assembler.
Ja ... men hvor mange linjer assembler kode findes i et OS? Eller andre typer system applicationer?
Ja ... men hvor mange linjer assembler kode findes i et OS? Eller andre typer system applicationer?
Ca. 2% sidst jeg kiggede efter.
Noget af det fordi der ikke er andre måder at gøre det på (specielle registre og instruktioner), men det mest af det af performance-hensyn.
Du er velkommen til at lave din p-code kerne, men jeg vil stadig foretrækker at kunne køre den på CHERI hardware.
Jeg er selvfølgeligt enig i at der skal skrives en p-Code compiler. Og en bootloader. Men jeg kan ganske enkelt ikke se hvorfor lav-niveau systemprogrammering ikke kan ske på en måde der først bliver til en form for p-Code. p-Code kunne ligne mellemcode i compileren. For kernen i operativsystemet kunne compileringen fra p-Code til maskinkode i princippet ske i byggefasen. Det vil selvfølgeligt kræve et nyt OS skrevet i et nyt sprog der har en p-Code der kan verificeres safe. Der synes bevægelser i den retning med Rust. Blot uden p-Code.
Husk på at CHERI også checker hvis det er skrevet i assembler.
Ja ... men hvor mange linjer assembler kode findes i et OS? Eller andre typer system applicationer?
Jeg er enig med dig - jeg tror at den eneste årsag til, at vi ikke har set det, er producenterne af processorer, helst ser programmerne er bundet til at blive brugt af en bestemt CPU. Om der er en form for lampekartel ved jeg ikke.
Et sprog som C++ oversættes meget ideelt til maskinkode, og der er reelt ikke nogen årsager til maskinkode. Der er nogle få CPU features, der har særlige indstruktioner, som måske skal med i sproget, for at alt kan skrives i en "p-code", byte-code, MBC eller hvad vi kalder det.
En af årsagerne til, at jeg foretrækker en sådan operativsystem kode, er at vi kan definere sproget, så det er muligt at automatisk parallelisere vores sekventielle kode. Det virker måske umiddelbart uoverskueligt - hvordan skal man kunne automatisk parallelisere et sprog som C++ ? Antager vi, at vi har en byte pointer, så kan den jo pege til og modificere et vilkårligt del af lageret, og så tvinger vi en rækkefølge og hindrer parallelisering.
Imidlertid kan vi godt analysere C++ meget grundigere, end de fleste compilere gør i dag. Eksempel
if (p==NULL) {
her ved compileren, at p er NULL
} else if p < min {
her ved compileren, at p er mindre end l
} else if p > max {
her ved compileren, at p er større end r
} else {
her ved compileren, at p er indenfor det tilladte område min..max
}
Det er muligt, at tjekke samtlige variables intervaller på ovenstående måde med en statisk analyse, og derved opdage mange typer fejl. Hvis compileren kan indse på forhånd, at det ikke er nødvendigt med et run-time tjek, så behøver run-time tjek ikke at tage tid. Og, man kan ligefrem kræve, at compileren skal kunne indse, at alle brugte områder der peges på er valid på oversættelsestidspunktet. Det er ikke nødvendigvis kompatibelt, med alle nuværende c++ programmer, men det er relativt nemt at sikre, ved at programmørerne tvinges til, at indlægge tjek i softwaren, for ellers vil compileren ikke oversætte det. Dette er mere sikkert end run-time tjek, hvor en fejl sendes videre i hovdet på brugeren. Er der ikke taget for compileren synligt hensyn til fejlene i koden, så er den ikke muligt at oversætte.
Ved parallelisering medfører sådan en analyse også, at bruges af lageret kan deles op i områder, så en peger ikke kan pege på alt, men man ved den er indenfor et afgrænset område. Tager vi et eksempel som merge-sort, så kan den laves som en rekursiv procedure. Det er teoretisk muligt at parallelisere den delvist, men svært at gennemskue, fordi at der anvendes samme array, som der sorteres dele af. Ofte, så vil det medføre en trådning, fordi det er samme array, som i pointer tilfældet, hvor en pointer kunne pege på ethvert sted i lageret.
Selv i eksemplet med arrays, kan man i nogle tilfælde udfolde den rekursive funktion, og ud fra den udfoldede funktion udregne, at den kan paralleliseres.
Det er naturligvis ikke nødvendigt at gå så vidt. Men, det vil være rigtigt smart, at alt software paralleliseres automatisk, og at de parallele tasks prioriteres godt af operativsystemet.
Som minimum, så bør vi i et sprog som C++ kunne opnå parallelisme, ved at skrive to rutiner, der ikke direkte påtvinges trådning imellem. Det kan vi nemt, hvis compileren har styr på pointerne, som jeg skriver. Vi skal så have mulighed for at kunne kommunikere mellem disse parallele dele af programmet, ved der tilføres streams til operativsystemet (fifoer, eller beskedskøer, der bruges mellem parallele tasks). Det vil gøre C++ til et parallelt sprog, fordi vi skriver koden sekventielt, og opnår parallelisme, ved at kommunikere mellem den sekventielle kode med fifoer. Kan man ikke tjekke på, om der er elementer i en fifo, bliver det tilmed deterministisk parallel programmering.
Når vi laver et nyt element med new, så er det også et nyt element, der kan bruges parallelt med andre elementer, med mindre noget i programmet påtvinger trådning.
Vi kan umiddelbart indse at det er muligt at ændre størrelsen af pointere i C++ f.eks. til 64 bits.
Disse bits, kan bestå af f.eks. en abstrakt 32 bit pointer, og en 32 bit offset. Når vi laver pointer arithmetik i C++, vil vi reelt altid kun lave beregninger på offset. Den abstrakte del, giver ikke mening at lave pointer beregninger på.
Når vi laver et nyt element med new, eller frigiver den med del, så er det altid den abstrakte pointer der initialiseres, og første element har typisk offset 0.
Det interessante er, at C++ har kendskab til strukturen som en abstrakt pointer peges på (altså, denne del, der styres med offset). Har vi eksempelvis at den består af en struct, bestående af byte, herefter en array, en pointer, og en array, så kan compileren regne ud, om et givet offset er indenfor disse områder, og tjekke at de ikke overskrider det tilladte område.
Og, fordi at C++ også kan tjekke, at vi faktisk har lavet vores kode, så vi tager hensyn til out-of-range problematikken, så er det mere sikkert, at vi sætter et compilerflag der indstruere compileren til at lave denne tjek statisk, end at begynde med run-time optimeringen.
Alt i alt, så behøver vi stort set ikke runtime tjek.
En af de store fiduser, ved at oversætte til en binær kode, der kan automatisk paralleliseres af operativsystemet er, at parallelisering er noget som ikke kan ske statisk. Det kan kun ske dynamisk, da det afhænger af de programmer vi har til at køre, og prioriteten.
Det er vigtigt, at parallelisere til et stort set uendeligt antal processer, og herefter sekventialisere dem på det antal cores der er tilgængeligt. Dette giver mulighed for, at processerne kan prioriteres, så at vores kode ikke kører i den rækkefølge, som den er indtastet. Vi kan dog ikke måle det ud fra koden. Men kunne vi - teoretisk - få oplyst tidspunktet, hvor en given sætning udføres, så vi nemt kunne opleve, at det viser sig at en del af koden tager negativ tid at udføre.
Vi skal satse på så meget statisk analyse som muligt, og så lidt run-time tjek som muligt. Når først, at et program kommer ud til kunden, så koster run-time tjek penge og kundetilfredshed. Så jeg ser egentligt helst, at det ikke indbygges i hardware. Lad os få så meget lagt ind i compileren som vi kan. Run-time tjek, er en forbandelse, vi helst skal undvære... Dog bedre, end en fatal fejl.
What I would really like is a language with all of the flexibility and power of C++ but without the pitfalls that leads to memory corruption.
If your program is in clean C++11 or later, then all the traditional memory errors are pretty much gone. Havn't seen a stray meory access, memory leak or double-free in such code because it's simply semantically impossible.
I have seen new classes of bugs though, that are due to the ever increasing complexity of the C++ language.
Det er muligt, at tjekke samtlige variables intervaller på ovenstående måde med en statisk analyse, og derved opdage mange typer fejl. Hvis compileren kan indse på forhånd, at det ikke er nødvendigt med et run-time tjek, så behøver run-time tjek ikke at tage tid.
Nu er det mange år siden jeg har rodet med den slags, men man ender meget nemt med at det state man skal holde på for et givet sted i koden bliver meget stort. Ikke i dit eksempel, men når der er funktionskald.
Ved parallelisering medfører sådan en analyse også, at bruges af lageret kan deles op i områder, så en peger ikke kan pege på alt, men man ved den er indenfor et afgrænset område.
Med Intels i860 processer forsøgte man netop at overlade parallelisering af instruktioner til compileren. Det blev ikke nogen success. Itanium det samme. Jeg har dog svært ved at se det som en umulighed at få det til at virke og compileren burde have bedre tid til det end CPU'en. Man skal dog ikke se bort fra at CPU'ens optimeringer lidt kan sammenlignes med JIT kode generering fordi den også har adgang til eksekverings metrikker (fx. til branch prediction).
Men i det store spil tror jeg ikke på auto-parallelisering. Jeg mener at Apples M1 CPU lige nu er king of the hill og teoretisk kan nå 8 instruktioner per cycle - hvor meget de når i praksis ved jeg ikke. Jeg har set teoretiske betragtninger på at man kan nå helt til 64 ... men det lyder meget meget højt.
Jeg gætter på at dit forsøg på at parallelisere merge-sort på den måde vil være meget svært. I mine øjne er parallelisering noget programmøren skal rode med og gerne i så store klumper som muligt. Det gør koden mere simpel at skrive, teste og læse. Testing af kode der indeholder en masse parallel logik er ikke sjov fordi det pludseligt ikke er deterministisk. Jeg har i øvrigt endnu ikke set nogen få det helt store ud af at processere containers/collections parallelt blot ved at sætte et flag et sted. Som sagt: parallelisering bør i større chunks sådan at man undgår det meste synkronisering mellem threads.
Ca. 2% sidst jeg kiggede efter.
He he ... der lærte jeg noget nyt. Det er sgu for længe siden jeg har rodet med operativ systemer. Jeg skal ærligt erkende at jeg havde regnet med at der var et par hundrede instruktioner som pænt kunne pakkes ind.
Du er velkommen til at lave din p-code kerne, men jeg vil stadig foretrækker at kunne køre den på CHERI hardware.
Hvis jeg kan få det uden at det koster noget andre steder så er jeg også med. Men hvis det begynder at koste noget så er det en anden sag.
Det er muligt, at tjekke samtlige variables intervaller på ovenstående måde med en statisk analyse, og derved opdage mange typer fejl. Hvis compileren kan indse på forhånd, at det ikke er nødvendigt med et run-time tjek, så behøver run-time tjek ikke at tage tid.
Nu er det mange år siden jeg har rodet med den slags, men man ender meget nemt med at det state man skal holde på for et givet sted i koden bliver meget stort. Ikke i dit eksempel, men når der er funktionskald.
Ja, i nogen tilfælde kan det blive stort. Men, vi kan også gøre det sådan, at vi lægger run-time tjek ind, og herefter optimerer. Måske kan vi ikke optimere alt væk, fordi vi ikke gidder. Men, programmøren kan altid skrive sin kode, så det bliver så tydeligt for compileren, at den gidder at optimere run-time tjekket bort. Som eksempel mit tilfælde. Og, gør vi det nu til et krav, at compileren altid skal kunne optimere run-time tjek bort, så ved vi at koden er stabil, fordi programmøren har taget højde for det.
Med Intels i860 processer forsøgte man netop at overlade parallelisering af instruktioner til compileren. Det blev ikke nogen success. Itanium det samme. Jeg har dog svært ved at se det som en umulighed at få det til at virke og compileren burde have bedre tid til det end CPU'en. Man skal dog ikke se bort fra at CPU'ens optimeringer lidt kan sammenlignes med JIT kode generering fordi den også har adgang til eksekverings metrikker (fx. til branch prediction).
Generalt, så kan du ikke parallelisere alene med compileren. Compileren kan hjælp, men styringen af de paralle proceser er ikke muligt at compileren, såfremt den beror på statisk analyse. Det skal gøres dynamisk. Du kan gøre det med en in-time compiler. Og, den kan ofte gøre det bedre end hardware! Hardware er meget primitiv i forbindelse med paralleliseringen, og dens parallelisering kan nærmest beskrivet som ingen. Skriver du eksempelvis to stykker kode i C++ hvor der ikke er afhængigheder, så kan hardwaren ikke se det. Den kan ikke analysere parallelisme. Den kan automatisk generere en VLIW indstruktion, hvor indstruktionerne adskilles over ikke afhængige, men det har ikke meget med at parallelisere at gøre. Dine sekventielle programmer bliver ikke paralle ved sådan en operation, og det kan diskuteres, om processoren bliver hurtigere. Man kan gøre det, at man undlader at parallelisere, og bare klasker indstruktionerne sammen i et langt indstruktionsord, inklussiv afhængigheder. Det viser sig, at disse afhængigheder ikke er et problem, på den måde som software analysen angiver, fordi at den hardwaremæssige afhængighed på bitniveau, ikke er det samme som den topologiske afhængighed. Så reelt, så giver det ikke hurtigere computere - tværtimod, ofte langsommere, hvis den ikke kan udføre en meget parallelisering. Havde den bare klasket det ned i et indstruktionsord uanset afhængigheder, så vil afhængighederne måske alligevel ikke tage tid, eller næsten ingen tid. Mens, at paralleliseringen der får flere indstruktioner til at udføres samtidigt, reelt bliver langsommere, hvis det ikke kan opnås fra et topologisk niveau.
Men i det store spil tror jeg ikke på auto-parallelisering. Jeg mener at Apples M1 CPU lige nu er king of the hill og teoretisk kan nå 8 instruktioner per cycle - hvor meget de når i praksis ved jeg ikke. Jeg har set teoretiske betragtninger på at man kan nå helt til 64 ... men det lyder meget meget højt.
Igen, det har intet med parallelisering at gøre. Prøv at skriv et par rutiner i C++ uden afhængigheder, og se om processoren udfører dem parallelt. Det gør den ikke. Som jeg skrev, så er ofte bedre at ikke parallelisere i CPUen end det som producenterne gør. Det eneste de gør, er at de omdanner flere indstruktioner til en VLIW indstruktion, over et meget lille vindue af indstruktioner. Og det er som regel bedre, at bare placere indstruktionerne i en VLIW indstruktion med afhængigheder. Man gør det, at man analyserer i hardware, om en indstruktion bruger output fra en af de andre indstruktioner i VLIW indstruktionen, og forwarder resultatet direkte, så der opnås en kombinatorisk kredsløb, der direkte tager hardware resultatet og bruger. Det er præcist som forwarding i en piplene på n niveauer, men her er det så foldet ud, så at pipelinen udfører et antal indstruktioner. Dette antal kan være vilkårligt stort. Der sker så automatisk parallelisering af hardwaren men på bit niveau, fordi at hardware arbejder parallelt. Og det betyder, at det dermed også tages hensyn til bittenes indhold. Et eksempel er, at du lægger en til 2. Det giver 3. Det er kun en enkelt bit som skifter. Dette tager ikke lang tid, fra et hardware view, så hvis du forwarder data direkte, tager det ikke nær den tid, som det tager at lave en 32 bit addition. Eller lægges 0 til, så tager det ikke tid. De indbyggede paralleliseringer som producenterne propper ind, tager ikke hensyn til værdier, men kun til topologi. Så det er faktisk bedre, at ikke parallelisere, men bare optråde et netværk, så indstruktionerne direkte leverer data til hinanden, og bliver parallele fordi at hardwaren er parallel. Man bruger så to signaler, en til "0" og en til "1", og nulstiller CPU'en først. Man kan derved se, hvornår at "0" og "1" kommer, og dermed ved man at resultatet foreligger. Hardwaren laves så der ikke kan komme spikes på hverken "0" eller "1" linjen. Adgang til ram mv. laves ved at man har nogle memorymappede registre, så der direkte anvendes en cachet del af hukommelsen. Alt i alt, så bliver processorerne meget hurtigere end f.eks. Intels og ARM's.
Jeg gætter på at dit forsøg på at parallelisere merge-sort på den måde vil være meget svært. I mine øjne er parallelisering noget programmøren skal rode med og gerne i så store klumper som muligt.
Nej, sekventiel og parallelt software er identisk. Der er ingen forskel. Den eneste forskel er, at programmøren måske syntes koden er mere logisk, når den skrives parallelt. Det er meget nemt at analysere.
Du kan ikke analysere det i software. Dels, så gidder programmørerne ikke. Og, de kan ikke. Det er derimod udtroligt nemt at gøre automatisk. Men, man skal kunne lave en dataflow graf, som opdeles i flere uafhængige dataflow grafer. Der findes to former for parallelisme. Der,hvor vi har mulighed for at sætte elastikker ind. F.eks. kan vi tage en løkke. Her kan vi dele den op i flere. Master løkken er den, som bestemmer antallet af gange den gennemløbes. Det vil sige, at vi søger at trække det ud af løkken, som styrer antallet af gennemløb, og placerer i master løkken. Dette antal, angiver så det antal som sker i slave løkkerne, hvor så meget som muligt skubbes ud i, og gøres uafhængigt af hinanden. Derved, får vi elastikker imellem løkkerne. Og de kan udføres med års forsinkelse imellem hinanden. Vi deler parallelismen op i to typer - den, hvor vi har vores processer så de er uafhængige og har elastikker imellem. Og den, hvor at vi altid udfører indstruktionerne samlet, men de kan opstilles parallelt (det som sker indbygget i CPU'en). Det er kun den sidste form for parallelisme, der er indbygget i hardwaren. Men den kunne fint også gøres i en in-time compiler, og ofte bedre end i hardwaren - og altid ligeså godt.
Problemet er, at parallelisme ikke findes på nutidens computere. De har ingen operativsystemer, der håndterer parallelisme.
Testing af kode der indeholder en masse parallel logik er ikke sjov fordi det pludseligt ikke er deterministisk.
Jo, hvis computeren automatisk paralleliserer sekventiel kode, så fungerer det eksakt som sekventiel kode, og derfor er det også deterministisk.
Samtidigt får du fordelene ved at det paralleliseres, selv på en computere med en enkelt kerne. Antag, som eksempel, at du laver noget kode, der sendes ud til printeren. Og noget andet, der sendes ud til skærmen. Du ønsker nu at speede den kode op, som sendes ud til skærmen. Det kan du gøre ved, at følge flowet igennem træet med de parallele processer. Du får derved kun aktiveret den del af den sekventielle kode, der leverer dette output. Du kan som eksempel angive i operativsystemet, at output til skærmen, har større prioritet end output til printeren, og computeren vil så udføre de operationer der giver output til skærmen først. Ofte, så vil paralleliseringen også medføre kode optimeres bort. Hvis vi som eksempel har et output, der ikke bruges til noget, f.eks. sletter skærmen, så vil det som der er skrevet på den slettede skærm ikke blive udregnet. Dette kører på en adskildt CPU, og denne leverer nu ikke output. Så den sættes på som dummy, der intet laver. Laver du eksempelvis en uendelig løkke i programmet, og ikke bruger resultatet, så vil denne havne som en parallel process, der aldrig udføres, og slettes når den ved dataene ikke bruges fra den. Man prioriterer også løkker, således at løkker der går mange gange igennem får lavere prioritet. Det betyder, at en langsom løkke ikke kan blokere noget.
Trods det, så kan du på ingen måde fra din kode se, at den ikke virker sekventiel.
Du har mulighed for at kommunikere på tværs af den sekventielle kode, så du sender beskeder fra en del, til en anden. Og også den modsatte vej. Her bruges fifoer.
Er det så deterministisk? Ja, det er deterministisk. Det eneste som gør, at parallel kode ikke er deterministisk, er at der aflæses data af ikke deterministisk art. Det kan f.eks. være at du læser om der er data i en kø. Dette afhænger af, hvordan at cpuen udfører rækkefølgen internt, om der er data i en kø. Derfor, er det ikke noget vi må spørge om. Spørger vi, er svaret altid, at der er data. For er der ikke data, så venter vi, og bruger hellere processorkraften på at gøre noget andet fornuftigt, fremfor at komme med et svar der sandsyligvis alligevel er urelevant kort tid efter, når svaret er at der er data. Svares altid, at der er data, så er svaret determinisisk, og vores parallele kode er altid deterministisk, så længe at kommunikationen laves med køer, og aldrig med shared variable.
Årsagen til, at jeg syntes parallelisering skal med når man laver en operativsystem kode, er at det også medfører man får tænkt lidt grundigere over om der er overblik over programmets flow-graf, altså om den kan separeres. Dette er omtrent samme problematik som sikkerhed.
Du kan ikke analysere det i software. Dels, så gidder programmørerne ikke. Og, de kan ikke. Det er derimod udtroligt nemt at gøre automatisk. Men, man skal kunne lave en dataflow graf, som opdeles i flere uafhængige dataflow grafer.
Tjah, jeg fik rodet rundt flere steder i teksten - beklager.
Der skulle stå, at det er muligt at analysere parallelismen i software.
Ja, i nogen tilfælde kan det blive stort.
Som regel, så er nok at se på minimum, maximum, og NULL-værdi for pointere. Compileren behøver at huske et minimum, maximum, og om NULL værdi er muligt, internt i for compileren for pointerne. En given portion af koden, vil sætte en minimum, maximum, og om pointeren kan have en null værdi, så det er ikke svært at analysere.
Vi behøver ikke at lave en perfekt test. Det vigtige er, at compileren nemt kan gennemskue, at programmøren har taget højde for tilfældet, at en pointer kan gå udenfor dens område. Kan compileren ikke gennemskue det, må programmøren tilføje nogle linjer i koden, så compileren kan egennemskue, at programmøren har medtaget tilfældet.
Hvis compileren nægter, så skal man bare kunne tilføje linjer som i mit eksempel, og så skal den kunne komme igennem: Det er programmørens ansvar, at sikre det.
Bare for at blive lidt konkret, så er C++ compilere blevet meget gode til at eliminere køretids bounds checks. Lad os prøve følgende på https://godbolt.org/, med -std=c++17 -O2:
int main(unsigned int i) { std::vector v {1, 2, 3}; i = i % 4; return v.at(i); }
.at(size_t index) funktionen skal kaste en exception, hvis index er uden for range, og vi kan se, at compileren tilføjer checket "cmpl $3, %eax".
Men hvis vi skriver "i % 3" så fjernes checket.
Selvfølgelig findes der problemer, som ikke er mulige at checke statisk. Hvis vi har en vector af aktiekurser over tid, og vi itererer fremad ind til vi finder et dyk i kursen, så afhænger indexeringen af værdier, som kun er kendt på køretid.
Hvis man er sikker på, at ens kode er korrekt, og performance er meget vigtig, kan man bruge [] subscript indexering, som aldrig vil checke på køretid.
I øvrigt - C++11 introducerede constexpr (garanteret evaluering af udtryk og funktioner på compiletid) og lempede kravene til, hvad såddanne udtryk måtte indeholde (if, else, aritmetik, etc) i C++17. Et gæt (og det er kun et gæt) er, at det måske har muliggjort at eliminere endnu flere køretidschecks, også af ikke-constexpr udtryk...
