Plan10 - Det er faktisk raketvidenskab

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...

Ja, i nogen tilfælde kan det blive stort.

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.

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 skulle stå, at det er muligt at analysere parallelismen i software.

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.</p>
<p>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.

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.

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.

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.

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.

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.

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.</p>
<p>Husk på at CHERI også checker hvis det er skrevet i assembler.</p>
<p>Ja ... men hvor mange linjer assembler kode findes i et OS? Eller andre typer system applicationer?

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.

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.

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".</p>
<p>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?

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.

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.

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.

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.

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.

Good C++ (e.g., see the C++ Core Guidelnines) can run on a capability- based architure.

... which is overwhelmingly demonstrated by the CHERI groups work.

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.

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.

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.

Men det løser stadig ikke problemerne når vi taler lav-niveau systemprogrammering.

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.

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.

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.

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.

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.

Tillykke!</p>
<p>Du har lige genopfundet Java Virtual Machine ?</p>
<p>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.

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.

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.

Re: Tid til at glemme lineære adresserum?</p>
<p>Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?</p>
<p>En "walled garden" hvor al kode skal afleveres i kildetekstform ?</p>
<p>Nej det tror jeg ikke på. Ikke helt.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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++.</p>
<p>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.</p>
<p>PS: MBC behøver ikke stå for Michaels Byte Code.

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.

Al kode skal leveres i ELF filer indeholdende "Michaels Byte Code™"

Tillykke!

Du har lige genopfundet Java Virtual Machine ?

Den er der som bekendt ingen der har skrevet en operativsystemkerne med endnu ?

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).

Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?</p>
<p>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.

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.

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.

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.

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.

En "walled garden" hvor al kode skal afleveres i kildetekstform ?

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.

"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.

Men hvordan sikrer du at al kode er compileret med din "sikre" compiler?</p>
<p>En "walled garden" hvor al kode skal afleveres i kildetekstform ?</p>
<p>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.

1. 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.

2. 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.

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.

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.

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.

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.

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 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).</p>
<p>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.

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.

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.

Der er bare meget lidt grund til at lave den slags i hardwaren når nu compilere fint kan tjekke den slags.

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.

sådan at kerneprogrammører kan lave deres sædvanlige numre.

For "sædvanlige numre" læs "få ting til overhovedet at virke til at begynde med" ;-)

Men ja, det er helt klart systemprogrammering CHERI primært sigter efter.

[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]</p>
<p>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.

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.

Jeg har forsøgt at læse dokumentationen, men jeg syntes ikke det fremgår tydeligt af dokumentationen.</p>
<p>Spørgsmålet syntes jeg egentligt var meget simpel (ja/nej) - tages der hensyn til, at flere pointere peger på samme data i C++ ?

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.

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.

Ja, men i et sprog som C++ har du jo mange pointere, der peger på området.

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.

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++.

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.

å 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.</p>
<p>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.

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.

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.</p>
<p>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.

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.

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

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.)

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:

1. Du kan ikke umiddelbart udvide et lagret objekt uden at flytte det. Du kan komme et stykke af vejen ved at allokere objekter i forskellige dele af et stort logisk adresserum, så de i princippet hver har et stort logisk adresserum for sig selv, men selv med 64 bit adresserum løber man tør, hvis hvert objekt skal have flere GB logisk adresserum for sig selv, og da den mindste enhed fysisk RAM, der kan tilføjes til et logisk adresserum er flere kilobyte, spilder man en masse fysisk plads i form af intern fragmentering. Det er derfor heap managers kan dele pages op i mindre objekter, mens de tillader store objekter at bruge hele pages.
2. Selv om fat pointers forhindrer en pointer i at pege udenfor sit allokerede område, så afslører pointerens værdi noget om objektets placering, f.eks.hvilke af to objekter, der ligger først i lageret. Det er måske ikke det størst tænkelige sikkerhedshul, men denne information ødelægger noget af abstraktionen i at have en reference til uspecificeret lager.
3. Når objekter kan muteres, giver det synkroniseringsproblemer for parallele processer, der kan læse og skrive til delte objekter.

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.

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.

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++.

Det CHERI forhindrer er:</p>
<p>p=malloc(100);<br />
p = (void*)((uintptr_t)p + 200);<br />
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.</p>
<p>Alle andre pointere afledes fra denne "ur-pointer" i stadig finere granularitet.</p>
<p>Kernen laver en pointer til sin kode, en pointer til sine data og en pointer for "fri hukommelse", ingen af disse pointere overlapper.</p>
<p>For hver process laves der de klassiske fem pointere fra "fri hukommelse" pointeren: text, data, bss, heap & stack.</p>
<p>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.

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.</p>
<p>Emnet er svært, men nok ikke irrelevant som et par bidragydere mener.</p>
<p>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?</p>
<p>Det var den diskussion jeg ønskede at bringe op, ikke kategoriske svar som</p>
<p>Der gælder generalt, at du aldrig må have tidsbegrebet på en computer. Du skal betragte CPU'en til at regne uendeligt hurtigt.</p>
<p>som for eksempel udelukker ethvert forsøg på at regne data rates ud, hvilket ellers godt kan lade sig gøre i praksis

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.

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...

Desværre, så er det ikke rigtigt den tilgang man har anvendt, når man har lavet nye sprog.

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...

Spændende.</p>
<p>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) .</p>
<p>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.</p>
<p>Eller er der noget jeg ikke har forstået her?

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...

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.

Er der nogle spændende alternativer?

UNIX pipes er en-dimensionale.

TSO/pipes havde ikke den begrænsning, men der skal findes en bedre måde at udtrykke det på.

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?