NSA - Non Solo Amiga

SOFTWARE => Sistemi Operativi => Altri & "Nerd OS" => Topic aperto da: dsar - 01 Dicembre 2014, 10:45:57

Titolo: Muen Separation Kernel
Inserito da: dsar - 01 Dicembre 2014, 10:45:57
.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 01 Dicembre 2014, 17:25:12
Ma non sempre è possibile prevederli. Per questo motivo ho lavorato a una nuova tecnologia per accelerare in hardware il controllo dei bound; a breve sottoporrò il draft al comitato per i brevetti, e poi vediamo cosa mi diranno.

Comunque ADA è troppo complesso come linguaggio. La sintassi, da pascaliano, mi piace molto, ma se il linguaggio diventa troppo grande la facilità di scrittura del codice tipica di Pascal & co. va a farsi benedire, e non mi piace affatto.
Titolo: Re:Muen Separation Kernel
Inserito da: TheKaneB - 02 Dicembre 2014, 11:14:48
Vorrei ricordare che questo kernel fa "Muuuuueen". Coincidenze? Io non credo :D
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 02 Dicembre 2014, 22:12:04
Ma non sempre è possibile prevederli.

Dipende, con il range type (bounded) esempi classici che delegano il range checking in runtime possono essere controllati in compile time, per esempio: buffer[f()]; il ritorno di f() deve essere lo stesso range type che utilizza l'array del tipo buffer. Andando sul generale non puoi iterare quel buffer con un indice che non è dichiarato dello stesso range type. Se l'array viene dichiarato con un tipo range bounded, il type checking implica il range checking.
Chiaro.
Citazione
Il range checking avviene per gli unbounded range, in cui il tipo range è conosciuto solo durante il runtime (ma nel mission critical non si usano mai). Il range checking di Ada in compile time si comporta molto bene in questi casi, soprattutto quando l'array non è guarded nei cicli (for i in buffer'Range), in particolare nei cicli generici non ti permette di accedere ad un array se l'index non è controllato nella condizione.
Onestamente non ho trovato casi in cui un unbounded range non venisse catchato in compile time, sicuramente saranno casi eccessivamente complicati.. ma qui ci vuole un po' di software engineering e buon senso, casi così delicati vanno trattati con estrema semplicità per essere il più possibile padroneggiati. In ogni caso c'è il bounds checking in runtime, che protegge i casi in cui il guard sull'array non può essere garantito.
E' troppo pesante. Per questo motivo sono state sviluppate soluzioni, anche hardware, per evitarlo. Ad esempio Intel ha tirato fuori di recente la tecnologia MPX (https://software.intel.com/en-us/blogs/2013/07/23/intel-memory-protection-extensions-intel-mpx-design-considerations) allo scopo (un altro utile link che ne parla è questo (https://code.google.com/p/address-sanitizer/wiki/IntelMemoryProtectionExtensions)), che sarà disponibile nei prossimi processori. Ma c'è parecchio fermento, e si trovano diverse altre soluzioni o ricerche in merito. Qui (https://code.google.com/p/address-sanitizer/wiki/ComparisonOfMemoryTools) trovi altra roba.

Le motivazioni sono molto semplici: si tratta di problematiche molto comuni e frequenti, e per le quali c'è forte richiesta (ma non posso dire altro, mi spiace) di tecnologie per la loro accelerazione in hardware.
Citazione
Il vero problema comunque sono gli array dinamici, che oltre ad essere pericolosi per la sicurezza (buffer overflow, il resize non è altro che un free()/malloc() quindi tutti i reference diventano dangling pointer, etc) offre delle pessime performance se fai tantissime operazioni di modifica.
Esistono delle politiche per ridurre l'impatto di queste operazioni. O... altro, ma anche di questo non posso parlarne per adesso.
Citazione
Morale della favola, evitare gli array dinamici ed utilizzare solo ed esclusivamente strutture dati. Questo è uno dei motivi per cui Wirth non implementò mai gli array dinamici nei suoi linguaggi.
Non sono d'accordo perché sono strumenti molto utili.

Tra l'altro con tecnologia adeguata si possono gestire in scioltezza e riducendo al minimo problematiche di robustezza e sicurezza.

Questo è anche il motivo per cui ho speso un po' di mesi per sviluppare una mia idea che mi trascinavo da anni: dimostrare che si può ottenere bound checking in hardware a un costo minimo sia a livello implementativo sia, soprattutto, a runtime. Fortunatamente dove lavoro adesso ho avuto la possibilità di svilupparla e perfezionarla ulteriormente, ma soprattutto c'è la concreta possibilità di vederla implementata su silicio (SE l'idea piacerà, e passerà poi tutta la trafila burocratica, che purtroppo è lunghetta).

Ma non sempre è possibile prevederli. Per questo motivo ho lavorato a una nuova tecnologia per accelerare in hardware il controllo dei bound;

mi sa che non sei il primo ad averci pensato, anche se in quel caso non ne e' valsa la candela: idee varie in OpenRISC!
Non conosco OpenRISC e come abbiano affrontato il problema, ma certamente non sono affatto l'unico ad averci pensato. C'è parecchia letteratura in merito, progetti, e... richieste di avere soluzioni efficienti (e che non penalizzino troppo le prestazioni). Se Intel ha sviluppato MPX, non l'ha fatto certo per caso. ;)
Citazione
esattamente cosa presenti ?
Mi spiace, ma a questo stadio non posso rilasciare alcuna informazione in merito. L'unica cosa che posso dirti è che si tratta di un'intera tecnologia che aiuta a risolvere o limitare fortemente le problematiche di bound-checking, protezione dei buffer (anche di sottoinsiemi/slice di buffer esistenti), e dangling-pointer.

E' una soluzione hardware che ha un impatto trascurabile a runtime, al contrario di altre tecnologie.
Citazione
hai un nodello HDL ?
No, nessun modello HDL: lo sai che le mie conoscenze in merito sono nulle. :'(

Al momento ho scritto un lunghissimo draft che espone tutti i dettagli, dall'implementazione all'interno di un processore fino all'applicazione che esegue il codice, con l'analisi di diversi casi d'uso e comparazione con tecnologie esistenti e concorrenti (MPX è una di esse, ma ce ne sono altre, anche in forma di sola idea interna). Ma devo ridurre notevolmente questo draft, perché per sottometterlo alla commissione brevetti il testo deve occupare al massimo un paio di paginette, e scritte in maniera quanto più chiara e intelligibile possibile.

Se dovesse andare bene, io mi fermerò qui. Al massimo sarei chiamato come consulente per la scrittura del brevetto (che viene realizzata da gente che lavora in questo campo, inclusi legali ovviamente), e forse per discutere qualcosa riguardo all'implementazione su silicio (ma ne dubito, perché quegli ingegneri non ne avranno sicuramente bisogno).

Non so se ti rendi conto dell'idea totalmente insana, ci metteresti due/tre mesi per finire di compilarlo

per questa porcata lavoro sotto QEMU/MIPS su un muletto di ordine almeno i2
fossi matto ad usare un SoC a 800Mhz che performa meno di un P3
pero' anche cosi' il cross compilare e' un bel macello, e metterlo a posto anche peggio

in compenso per PowerPC si trovano bootstrap (l'ho fatto, funge)
e anche per ARM c'e' qualcosa (non l'ho provato di persona)
Alla fine emuli i MIPS con gli x86, eh! ;D Ma lasciali perdere e dedicati direttamente a questi ultimi. 8)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 02 Dicembre 2014, 23:29:17
Alla fine emuli i MIPS con gli x86, eh! ;D Ma lasciali perdere e dedicati direttamente a questi ultimi. 8)

per forza, non ho abbastanza quattrini per comprare hw + carrozzato, volendo dalla Cina ci sarebbe pure qualcosa di + potente della + potente CPU mips che ho in casa, un R16K a 800Mhz, che non accendo quasi masi, si succhia 600Watt e' un 4 CPU.

mi costa di meno usare un muletto intel per QEMU/MIPS-catalyst (che crede di fare compilazione nativa)
Vedremo con Edison, per ora non c'e' alcun rimpiazzo, da parte mia, per i SoC MIPS
in compenso ho definitivamente abbandonato PowerPC: Cerbero, di cui vedi le foto nell'altro thread e' l'ultimo progetto, poi metto la parola fine.
E pure sulle HP.
Uno in meno. Quando smetterai con MIPS stapperemo una bottiglia di spumante. ;D
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 02 Dicembre 2014, 23:45:15
Ne resterà soltanto uno. 8)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 03 Dicembre 2014, 18:33:36
Citazione
Morale della favola, evitare gli array dinamici ed utilizzare solo ed esclusivamente strutture dati. Questo è uno dei motivi per cui Wirth non implementò mai gli array dinamici nei suoi linguaggi.
Non sono d'accordo perché sono strumenti molto utili.

Per esempio? Allargare l'array di una hash table
E' un ottimo esempio, visto che si tratta di un strumento molto utilizzato. Se prendiamo Python, ad esempio, la virtual machine è permeata sull'utilizzo di oggetti PyDictObject, che sono rappresentati in questo modo:
Codice: [Seleziona]
typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */

    /* The table contains ma_mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t ma_mask;

    /* ma_table points to ma_smalltable for small tables, else to
     * additional malloc'ed memory.  ma_table is never NULL!  This rule
     * saves repeated runtime null-tests in the workhorse getitem and
     * setitem calls.
     */
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
Penso che l'utilizzo sia abbastanza chiaro: se a un certo punto il numero di entry allocate predefinitamente non sarà più sufficiente, ma_table verrà "allungato" (o ridotto) a seconda dell'esigenza.

Puoi fornire un'implementazione che sia più robusta e altrettanto efficiente?
Citazione
od avere stringhe di larghezza infinitamente arbitraria?
Non è questo che genera il problema, ma se le stringhe sono mutabili. Ma ne hai parlato dopo.
Citazione
Il primo l'ho sempre reputato un aborto computazionale,
Sarà un aborto, ma funziona benissimo e garantisce ottime prestazioni. Considerato quanto sia utilizzato un dizionario (hash table / map) in Python, puoi immaginare quanto sia stato ottimizzato nel tempo questo strumento / struttura dati, e quella esposta sopra rimane lo stato dell'arte (almeno per CPython). Ma, di nuovo: esiste un'implementazione più robusta e che mantenga almeno la stessa efficienza?
Citazione
il secondo non ne vale assolutamente la pena ed è pessimizzante a mai finire, potrei accettarlo solo per stringhe che poi non verranno più toccate.
In Python le stringhe sono "illimitate" e immutabili, anche se internamente la virtual machine prevede delle specifiche ottimizzazioni in casi particolari, per cui una stringa può venire modificata "in-place".
Citazione
Ormai sono abituato a ragionare con chunk di dati (con possibilità di essere cachati per velocizzare le operazioni) e mi trovo non bene ma benissimo.
Prova a generare in maniera efficiente una pagina web. Se non ricorri a un oggetto StringBuilder / StringIO / buffer che si allunga a dismisura, i tempi di generazione della pagina saranno estremamente elevati.

Come lo risolvi diversamente, e in maniera più "sicura", questo problema?
Citazione
Dai poi un'occhiata ai principali software che garantiscono (o cercano di farlo) un security by design, nessuno di loro utilizza array allocati dinamicamente.
Non è il mio campo, per cui non ne conosco. Ma stiamo parlando di casi molto particolari nel panorama attuale.
Citazione
Lasciando perdere poi il problema sicurezza e inadeguatezza per i dati, il fatto che un puntatore possa puntare a qualcosa di diverso da record/struct/class rende lento e complesso il garbage collector di oltre il 50%, ci sono almeno una quindicina di block descriptor in più solo per gestire il caso degli array allocati dinamicamente, contro un solo block descriptor per record/struct/class, poi la situazione peggiora se un puntatore può puntare "in mezzo" all'array ma fortunatamente questo è un problema dei linguaggi C/C++ . (Ok questo è più un problema implementativo che non riguarda il programmatore/utilizzatore).
Purtroppo è un problema generale e molto comune. Non possiamo riscrivere tutto il software esistente in maniera "secure by design", magari con un linguaggio di programmazione diverso. La realtà è costituita da miliardi di righe di codice con cui dobbiamo convivere, e per le quali trovare soluzioni "a buon mercato" per renderli più robusti è una strada percorribile e, anzi, abbastanza richiesta.
Citazione
Da premettere che per me è un "non problema", spostare una delle tante possibili soluzioni lato hardware non mi ispira tantissimo.. abbiamo già architetture abbastanza complesse. Secondo me ultimamente nel mondo dell'informatica si sta perdendo quel concetto di semplicità che spesso è la soluzione migliore per il controllo della complessità di oggi.
Sei un fautore della filosofia RISC. :) Però anche i RISC moderni hanno ormai centinaia di istruzioni, anche molto specializzate. E questo perché accelerare determinati ambiti / tipi di algoritmi è divenuto una necessità. ;)
Citazione
(Con questo non voglio sminuire ciò che stai facendo, che sono sicuro sia un ottimo lavoro)
No, assolutamente. Mi spiace soltanto che non possa mostrarti il draft per chiederti un parere. Una cosa che ho imparato dove lavoro è che il peer review è fondamentale, e che le critiche sono importanti sia per un reality check (per non galoppare troppo con la fantasia) sia per riuscire a rendermi conto dei limiti o proprio del valore dell'idea.
Citazione
P.S. ho letto dell'MPX, non risolve però i problemi dei dangling pointer
No, infatti, e non l'ho mai detto. Il suo ambito è il bound-checking e il tracciamento dell'uso dei puntatori / buffer.
Citazione
e comunque ci sono delle problematiche che il runtime check non ha (i falsi positivi)
Non è una tecnologia perfetta, e anche la mia non garantisce una soluzione perfetta della problematica in oggetto (idem per i dangling pointer: la mia tecnologia è utile anche in quest'ambito, ma non risolve definitivamente il problema). Si tratta di soluzioni che limitano molto i danni del codice; un buon compromesso, insomma.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 07:06:38
Sorry per il ritardo ma non ho avuto respiro
Va benissimo (per me è uguale, e da un po' sto rosicchiando ore alle notte pur di riuscire a fare qualcosa), anzi grazie per la risposta. :)
Citazione
Puoi fornire un'implementazione che sia più robusta e altrettanto efficiente?

Mi sono preso un po' di tempo (in quel poco che ho) per guardare il .h e un po' il .c, in particolare il commento di documentazione.

Mi permetto una critica perché sulle hash table ho un'esperienza di quasi un decennio. Il fatto che quel codice usi open address al posto del chaining ed una tabella eccessivamente piccola è già una scelta discutibile in un linguaggio che fa largo uso di dict ed è facile che degradi presto a linear list (ovvio che poi richiede il resizing della tabella). Se sono tanto preoccupati per le performance di mallocing, basta utilizzare una migliore allocation strategy oppure ci sono altri metodi di open addressing che non richiedono il resize della tabella. Nell'open address non ha senso partire con una tabella piccola e poi allargarla, ed è nato proprio per evitare l'uso di heap (e per un numero limitato di entry).

Quindi quale "efficienza"? L'unica cosa che vedo è solo una riduzione della memoria utilizzata, ma non della computazione generale.
Serve un po' di tutto, perché i casi di utilizzo di un dizionario sono diversi. Ma ne parlo meglio dopo.
Citazione
E poi non è bello sapere queste cose per un programmatore Python :-)
ROFL ;D Non pensavo, onestamente. Quindi sarà una sofferenza lavorare ogni giorno in PHP. :-/
Citazione
ora che lo so userei in modo diverso le dict, in genere mi piace pensare che ci siano casi ottimizzati in generale, non nel particolare (e mi pare di vedere che ce ne siano tanti), per esempio vedo che hanno ottimizzato in un certo senso il caso di dict piccole per le kwargs, e questo è buono perché è molto importante
Fa parte di uno dei casi di utilizzo di un dizionario in Python. Ne posto un breve elenco, che farà meglio capire il perché di quelle scelte che sono frutto di un compromesso.

I dizionari sono usati per memorizzare:
- le variabili d'istanza di un oggetto;
- le variabili globali di un modulo;
- le keyword di una funzione che consente il passaggio di un numero arbitrario di parametri passati per nome e valore;
- dati (le tradizionali "mappe").

Usi comuni sono:
- il lookup per controllare se una chiave (o variabile per i primi due casi; lo sottolineo perché è importante) esiste;
- il recupero del valore;
- l'iterazione di tutte le chiavi;
- l'hashing (calcolare un valore che "rappresenti" il dizionario e ciò che conserva).

Com'è possibile vedere, i casi sono tanti e coprono utilizzi anche molto diversi. L'attuale soluzione rappresenta, dunque, un buon compromesso fra velocità (in particolare per il lookup, che è fondamentale per i primi due casi, altrimenti ammazzerebbe le prestazioni della virtual machine) e spazio occupato (usando un dizionario per tutti i casi elencati, è facile che l'utilizzo della memoria esploda. Infatti per i casi più comuni / utili / necessari, che sono i primi due, si alloca immediatamente un piccolo numero di entry).

Non è possibile scegliere implementazioni diverse a seconda del caso d'uso, perché i dizionari vengono utilizzati in tutti questi ambiti e sono intercambiabili (ad esempio posso rimpiazzare le variabili d'istanza di un oggetto con un altro dizionario).

Internamente si potrebbe anche fare, ma a prezzo di complicare notevolmente l'implementazione, e probabilmente finendo per penalizzare i casi più importanti.
Citazione
Prova a generare in maniera efficiente una pagina web. Se non ricorri a un oggetto StringBuilder / StringIO / buffer che si allunga a dismisura, i tempi di generazione della pagina saranno estremamente elevati.

Come lo risolvi diversamente, e in maniera più "sicura", questo problema?

Ma in quel modo non ho a che fare con oggetti che non si allungano a dismisura, anzi.. lavorare con chunk di dati è molto meglio, non deallochi/riallochi l'intero dato (causando dangling pointer) ma aggiungi solo ciò che ti serve.
Aggiungi -> prima o poi lo spazio finisce e devi effettuare il resize (quindi, di nuovo, allocare e deallocare).

Utilizzare strutture dinamiche, come liste concatenate (FIFO), richiede più memoria ed è decisamente più lento rispetto a un array con accesso diretto alle sue entry.
Citazione
L'array allocato dinamicamente è una pessima idea in generale, pensa che molti per risolvere il problema dei dangling pointer utilizzano un puntatore a puntatore (quindi si avrà sempre un riferimento al nuovo array allocato), ma si ha due livello di indirizzamento che rallenta di parecchio l'accesso (questo era il metodo utilizzato dalle glib, non so se le cose siano cambiate).
Chiaro. E' una soluzione che non userei.

Però immagina il tipo PyList, un altro di quelli che viene spesso utilizzato (oppure StringIO, che viene molto usato per generare pagine web o, in generale, buffer di dati che vengono costruiti): cosa utilizzeresti per implementarlo in maniera efficiente a run-time?
Citazione
A proposito di Glib, implementa un "cesso" di array dinamico (che cresce ad ogni elemento aggiunto), ad ogni g_array_append_val() veniva fatto un malloc(), copia e free() con performance a dir poco VOMITEVOLI! Se si voleva evitare la riallocazione frequente bisognava crearlo con g_array_sized_new() (anziché g_array_new()) per preallocare una buona porzione dati, ma ciò col tempo non bastava (diamine!) che ricominciava col suo diabolico malloc(), copia e free(). Non capisco come mi piaceva quella cagata pazzesca di glib e gtk+, errori di gioventù (avevo 17 anni o su di lì). Spero che oggi sia un tantino ottimizzato, ma non ho interesse a guardarne il codice o la guida
Ho visto soltanto una volta in che modo gestiscono gli oggetti, e... m'è bastato. ;D
Citazione
Purtroppo è un problema generale e molto comune. Non possiamo riscrivere tutto il software esistente in maniera "secure by design", magari con un linguaggio di programmazione diverso. La realtà è costituita da miliardi di righe di codice con cui dobbiamo convivere, e per le quali trovare soluzioni "a buon mercato" per renderli più robusti è una strada percorribile e, anzi, abbastanza richiesta.

Purtroppo gran parte del codice che c'è (a mio parere) è codice merda, che è meglio riscrivere.
Riscrivere ha un costo, anche molto elevato. Non si può riscrivere tutto, lo sai. Sarebbe bello, ma... è impossibile.
Citazione
Io sono molto a favore dei runtime check (soprattutto se non sono eccessivamente invasivi ma economici), ci si lamenta tanto di come questi runtime check rallentino il software che poi in realtà i veri bottleneck sono altrove.
Ci sono studi che dimostrano che il bound-checking a runtime è molto costoso. Per questo si cercano soluzioni, sia software (usando l'MMU, ad esempio, e disponendo i dati allocati in un certo modo per generare appositi fault) sia hardware (MPX, o l'accelerazione hardware proposta per AddressSanitizer; ma ce ne sono altre).
Citazione
Ci sono una miriade di problemi a cui deve badare il programmatore, se un gruppo di questi problemi si può evitare selezionando solo certe tecniche, abilitando certe feature ed evitandone altre, posso solo reputarlo "good engineering". Infatti apprezzo molto quei progetti che hanno delle linee guida, in particolare definiscono un subset degli strumenti a disposizione e soprattutto ne danno una motivazione, uno può non essere d'accordo.. ma che ci sia è una cosa da apprezzare
OK, ma... non si può fare con tutto il codice esistente. Ormai esiste e bisogna conviverci. Col tempo il codice viene riscritto, ma è sempre una goccia d'acqua in un oceano, purtroppo.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 17:57:14
cmq io mi sa che come soluzione bovina hw punto di prepotenza alle classiche (per i MIPS) TLB entries
in salsa bovina: virtual memory for sandboxing everything
Che non risolve o allieva il problema dei buffer overflow, purtroppo.
semplicemente perche' so come funzionano, e + o - posso pensare a come implementarlo.
per chiudere il giro, e' la stessa conclusione a cui sono giunti in OpenRISC :P
Quindi OpenRISC è simile ai MIPS per quanto riguarda la gestione delle TLB?
nella versione HP della CPU emulator per motorola 332 EVS
c'era una opzione che permetteva di tracciare TUTTI i puntatori
giusto per vedere se si sfora dal range

quel debugger HP lo fa in hw, ci sono dei comparatori di memoria
per armare i comparatori gli si passa la base del puntatore, ed il size
ci sono trigger che si armano solo quando il PC raggiunge istruzioni
che fanno uso di una EA in cui e' coinvolto un puntatore da controllare

quindi nella parte sw vengono tracciati i punti del codice assembly
dove si fa riferimento al puntatore che si desidera monitorare

tutto viene etichettato in modo incrementale
e gestito in hw con un numero limitato di possibili controlli ( mi pare siano 8 )

dopo di che, in esecuzione, ogni volta che viene incontrata l'istruzione incriminata
scatta il via libera per il comparatore hw, e si controlla l'EA finale
e se sfora si alza una exception
facendo sapere all'utente chi/dove/perche' ha sforato

molto primitivo ma apprezzato
costava un bel po' negli anni '90
Interessante soluzione. Il problema è che è troppo limitata, con soli 8 comparatori.

MPX ha 4 bound register, però ha pure la possibilità di gestire qualunque puntatore perché sfrutta una cosiddetta "Bound Table", che è simile a una Page Table, per mappare tutti i bound da tracciare; soluzione che occupa memoria e risulta un po' costosa.

La mia soluzione, invece, non ha nessun comparatore dedicato e nessun bound register. Ma non posso aggiungere altro, al momento.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:19:22
Sì, ma abbiamo sempre problematiche simili, te l'assicuro.

Anche per questo MPX ha soltanto 4 bound register, anche se poi c'è la Bound Table dalla quale scaricare all'occorrenza.

Il problema di queste soluzioni è che richiedono l'uso del compilatore, per generare le apposite istruzioni per gestire il tutto. Con tutti i limiti del caso.

La mia soluzione, invece, funziona anche con applicazioni già esistenti, ma sotto certe condizioni.

Comunque MPX, come pure il classico bound checking a runtime, comportano un calo delle prestazioni, a causa delle istruzioni aggiuntive da eseguire, e al fatto che il compilatore non può emettere codice altamente ottimizzato (perché deve memorizzare l'indice e/o il puntatore in un registro, per poi fare il controllo).
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:21:21
gdb funziona circa in quel modo, cerca di seguire un po' il codice
ma ha tipicamente senso quando il codice segmenta, e non prima
ovvero si cerca grossolanamente il punto dove segmenta
e poi lo si analizza nel dettaglio, seguendo istruzione per istruzione
con strumenti che analizzano lo spazio dei puntatori
Però se non conservi informazioni sul flusso eseguito, non te ne fai nulla: puoi andare indietro soltanto fino a un certo punto, facendo poca strada.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:28:18
Capito. Allora è qualcosa di diverso dall'operato di MPX e del classico bound checking eseguito a runtime.

Comunque quelle di cui hai parlato sono soluzioni complesse, e credo anche molto più onerose.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:30:03
Allo stato attuale, appunto. ::)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:32:46
Purtroppo è molto diffuso, e... si usa quello. Anche Intel ha puntato molto su GDB.

Adesso c'è pure LLDB. Se è fatto bene, magari riuscirà a soppiantarlo.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:39:20
Sì, immaginavo che esistessero soluzioni proprietarie / commerciali. Ma limitatamente a roba open source / gratuita, non credo ci sia molto in giro.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:42:51
C'è anche un debugger molto comodo perché hacker / cracker / reverser-oriented, solo per Windows, ma adesso non ricordo il nome. Open source.
Titolo: Re:Muen Separation Kernel
Inserito da: TheKaneB - 05 Dicembre 2014, 18:52:41
C'è anche un debugger molto comodo perché hacker / cracker / reverser-oriented, solo per Windows, ma adesso non ricordo il nome. Open source.

ce ne sono diversi, uno che mi viene in mente è IDA Pro: https://www.hex-rays.com/products/ida/debugger/index.shtml
Supporta il deASM da praticamente tutte le architetture, molto utile per reversare firmware di cose esotiche, compresi microcontroller :)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 18:56:46
IDA lo conosco, e mi sembra ci fosse già ai tempi dell'Amiga (dove c'era anche il fantastico Resourcer).

Ma quello a cui mi riferivo è un altro.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 20:21:18
tornando a quanto dicevo, anche OpenBSD !

Citazione
OpenBSD took an interesting approach in the 3.8 release:

During the development cycle of the 3.8 release, changes were made to the malloc memory management functions. In traditional Unix operating systems, malloc allocates more memory by extending the Unix data segment, a practice that has made it difficult to implement strong protection against security problems. The malloc implementation now in OpenBSD makes use of the mmap system call, which was modified so that it returns random memory addresses and ensures that different areas are not mapped next to each other. In addition, allocation of small blocks in shared areas are now randomized and the free function was changed to return memory to the kernel immediately rather than leaving it mapped into the process. A number of additional, optional checks were also added to aid in development. These features make program bugs easier to detect and harder to exploit: instead of memory being corrupted or an invalid access being ignored, they often result in a segmentation fault and abortion of the process. This has brought to light several issues with software running on OpenBSD 3.8, particularly with programs reading beyond the start or end of a buffer, a type of bug that would previously not be detected directly but can now cause an error. These abilities took more than three years to implement without considerable performance loss and are similar in goals to that of the Electric Fence malloc debugging library by Bruce Perens.
Utilizza l'MMU, come spiegavo sopra. Ma con tutti i limiti che ha un sistema di paginazione della memoria, che è legato a dimensioni fisse delle pagine, per cui tanti piccoli sforamenti dei buffer non possono essere rilevati.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 05 Dicembre 2014, 20:44:59
MPX arriverà a breve. Vedremo se quelli di OpenBSD, sempre così attenti alla sicurezza, saranno i primi ad adottarla.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 13 Dicembre 2014, 21:21:38
Aggiungi -> prima o poi lo spazio finisce e devi effettuare il resize (quindi, di nuovo, allocare e deallocare).

C'è una grossa differenza però, se io ho una struttura dati, posso deallocare solo alcune parti (e non ci sono operazioni di copia, etc). Nel riallocare un blocco intero di memoria, per esempio com'è comune nei buffer anche due mega o più, non è detto che l'allocator possa garantirti un'allocazione del genere (ovvero in una zona "continua" se c'è molta frammentazione)
Me ne rendo conto, ma in generale l'allocazione di memoria può fallire a prescindere che venga usato il resize o meno.

Con uno spazio d'indirizzamento a 64-bit (e le MMU) è estremamente difficile che ciò accada, data l'enorme disponibilità di zone di memoria.
Citazione
Utilizzare strutture dinamiche, come liste concatenate (FIFO), richiede più memoria ed è decisamente più lento rispetto a un array con accesso diretto alle sue entry.
[...]
Però immagina il tipo PyList, un altro di quelli che viene spesso utilizzato (oppure StringIO, che viene molto usato per generare pagine web o, in generale, buffer di dati che vengono costruiti): cosa utilizzeresti per implementarlo in maniera efficiente a run-time?

A parte il fatto che per evitare continui realloc dovresti partire con un buffer molto grande e non credo che questo consumi meno memoria rispetto ad una struttura dati.
La politica di allocazione per le liste è questa:
Codice: [Seleziona]
/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
Per cui c'è una preallocazione, ovviamente, ma in genere è minore rispetto alla necessità di creare una struttura "Node" per ogni entry, che comporta come minimo l'aggiunta di un puntatore "di link". Un oggetto PyList in Python viene implementato come un array di puntatori, dove questi ultimi puntano alla struttura dell'oggetto referenziato. Utilizzando una lista concatenata semplice, invece, ci sarebbero il doppio di puntatori.

Confrontando i due approcci e tenendo conto del pattern di allocazione attualmente utilizzato, soltanto nel caso secondo caso (4) la soluzione adottata in CPython occuperebbe più di memoria (4 puntatori anziché 2 nel caso di una PyList di un solo elemento). In tutti gli altri casi il consumo sarebbe al massimo uguale, con una generale tendenza a essere nettamente minore. Inoltre non serve continuamente allocare (e alla fine deallocare) le strutture Node richieste da un'implementazione che faccia uso di liste.

Grazie alla preallocazione il resize viene ammortizzato, e ha tempo lineare, che mi sembra un buon risultato.

Tirando le somme, mi sembra che la soluzione utilizzata attualmente sia senz'altro migliore rispetto a una possibile che faccia uso di liste concatenate per evitare il resize. Senza tenere conto, poi, che l'accesso agli elementi è costante attualmente, mentre sarebbe lineare nel caso della lista concatenata.
Citazione
Non conosco in dettaglio StringIO, ma se non utilizzano una lista che per il sequential access è davvero molto efficiente, sicuramente stanno adottando un strategia di ottimizzazione sbagliata.
La struttura dati usata internamente è questa:
Codice: [Seleziona]
typedef struct {
  PyObject_HEAD
  char *buf;
  Py_ssize_t pos, string_size;
} IOobject;
Citazione
Attualmente la linear list è la struttura dati più veloce per il sequential access ed anche per il direct access (se si hanno poche entry, ma vedi dopo).
Non è il caso di oggetti come StringIO, dove il buffer contiene generalmente diversi dati (è per questo che viene usata questa struttura, altrimenti una normale lista sarebbe sufficiente allo scopo).

Inoltre, anche se più raramente utilizzato, un oggetto di questo tipo consente lo spostamento del "puntatore" all'interno del buffer, perché è sostanzialmente un file in memoria.

Nonostante tutto, sono d'accordo che utilizzare una classica lista concatenata sarebbe la soluzione migliore per come NORMALMENTE viene utilizzato l'oggetto (appendere roba fino a quando non si fa richiesta di ottenere una stringa unica che rifletta l'intero contenuto del buffer).

Il problema è cambiare l'implementazione attuale, mantenendo la stessa interfaccia (cioé far funzionare l'oggetto come un file, quando richiesto; ad esempio spostando il puntatore alla posizione attuale).
Citazione
Nel dictnotes.txt trovi che una possibile ottimizzazione per poche entry è il linear search, soprattutto se viene fatta in una zona continua di memoria. Mentre hashi la chiave, probabilmente il linear search ha già finito :-)
Infatti normalmente un dizionario utilizza poche entry già pre-allocate. ;)
Citazione
Per l'ottimizzazione del direct access, le tree sono abbastanza efficienti, ma in alcune librerie ho visto che molti per semplificare utilizzano sempre liste con skip-list (per saltare direttamente in alcune parti di memoria) ed offrono performance superiori alle tree (in realtà "dipende", ma il discorso è un po' lungo).
Comprendo perfettamente. L'idea del tree può essere interessante, ma è da valutare per bene.
Citazione
Ovviamente non sono paragonabili a delle zone di memoria allocate, ma come detto prima non è sempre possibile garantire una riallocazione più grande (ed il fatto che oggi il computer più scarso ha 4gb di ram, non è un motivo per adottare tale soluzione).
Su questo vedi sopra. Comunque la riallocazione si faceva già coi computer a 32 bit, senza particolari problematiche. D'altra parte dobbiamo tenere conto del fatto che il carico di lavoro è stato generalmente commisurato alla potenza di calcolo e allo storage a disposizione in un determinato momento.

In ogni caso oggi le architetture più comuni sono a 64-bit, e certi problemi possiamo sostanzialmente dimenticarceli. ;)
Citazione
E questa non è una cosa scoperta di recente, gli anni 80 sono stati gli anni del "linear search rediscovered". A tal proposito vorrei incollare una parte del libro The School of Niklaus Wirth, The Art of the Simplicity, un libro che da ex-Pascalliano ti consiglio cdimauro :-)
Codice: [Seleziona]
books_to_read.append("The School of Niklaus Wirth, The Art of the Simplicity");D
Citazione
Citazione
                                                          I still vividly remember the day that Wirth
decided to replace the elegant data structure used in the compiler’s symbol table
handler by a mundane linear list. In the original compiler, the objects in the symbol
table had been sorted in a tree data structure (in identifier lexical order) for fast
access, with a separate linear list representing their declaration order. One day Wirth
decided that there really weren’t enough objects in a typical scope to make the
sorted tree cost-effective. All of us Ph.D. students were horrified: it had taken time
to implement the sorted tree, the solution was elegant, and it worked well – so why
would one want to throw it away and replace it by something simpler, and even
worse, something as prosaic as a linear list? But of course, Wirth was right, and the
simplified compiler was both smaller and faster than its predecessor.
Molto interessante. Questo succede quando si tiene conto  del solo punto di vista teorico.
Citazione
All'inizio ero molto scettico, soprattutto dopo aver passato anni ad usare hash table e poi tree (che mi piacciono da morire) per ottimizzare il lookup o l'accesso,
La pensiamo allo stesso modo. :) Una ventina d'anni fa ho ideato e implementato (in Turbo Pascal 8)) un nuovo tipo di tree proprio per aiutarmi nella ricerca di stringhe per un mio algoritmo di compressione. Però oggi non so se lo rifarei, perché ho sputato sangue per implementarlo, con tutti quei casi particolari da gestire.
Citazione
ho dovuto fare vari benchmark e poi in alcuni programmi sostituire strutture dati incasinate con le liste per convincermi che dipende che dati vai a trattare, sono dannatamente veloci
Concordo. Anch'io sono per la soluzione più semplice per un problema. Se poi mi rendo conto che coi dati reali non funziona bene, ne cerco un'altra che meglio calzi in quel caso.
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 09:07:25
Ma è per lavoro, o per "naturale" smanettamento da geek? ;D

Comunque riflettendo con quanto discusso con dsar m'è venuto in mente un algoritmo che stavo implementando una ventina d'anni fa in Turbo Pascal, e che potrebbe essere utile nel caso di strutture dati che contengono un numero dinamico di elementi. Non fa uso di riallocazione né di liste. E' un po' complicato, e infatti avevo implementato soltanto i casi di inserimento (append, sostanzialmente; il classico insert è problematico, ma lo è pure per un array o una normale lista), ma mancano ancora i casi per la rimozione.

Intanto me lo segno, perché potrebbe essere utile recuperarlo quando (SE) avrò un po' di tempo per smanettare di nuovo con CPython. :P Però va contro "The Art of the Simplicity": è decisamente complicato. ;D
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 10:39:56
stavo pensando, secondo me i 64bit di indirizzamento non mitigano troppo il problema anche per il fatto che poi la MMU si vede tipicamente block_size + larghi e quindi non vorrei che finisse per i discorsi analoghi che si fanno sui filesystem dove per il block_allocator, se non si prendono utili provvedimenti, dopo un po' non riesce piu' a garantire in modo alcuno continuità di blocco. Per il filesystem non e' critico, semplicemente le prestazioni calano (e la frammentazione aumenta), per un memory allocator invece potrebbe essere meno piacevole, e chiaro cmq che dipende da come lavora la MMU e da quanta memoria usano le tabelle. Meno memoria usa per le tabelle e + ram deve gestire la MMU + grossi si fanno i block_size.
Vero, ma lo spazio d'indirizzamento è talmente grande che riesci sempre a trovare un buco in cui infilare il megabuffer, fosse anche di diversi GB. ;)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 10:55:46
Can be, ma non posso giudicare, perché non conosco cosa fa OS X e come usa effettivamente la RAM. Lo sai che sono Windowsiano. :P
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 13:41:24
Non mi pare che Windows attui queste politiche. E' anche vero che con 16GB di RAM è difficile accorgersene. ;D
Titolo: Re:Muen Separation Kernel
Inserito da: Z80Fan - 14 Dicembre 2014, 16:02:29
@legacy:

sei sicuro che quelle misure non siano riferite alla memoria virtuale allocata, e non quella fisica?
Cioè, un programma può anche avere 16 GB di memoria virtuale allocata, ma avere solo 8 KB fisici mappati. :P
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 16:18:28
Lo swap (su Windows 8.1) l'ho disattivato. Con 16GB è del tutto inutile. 8)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 16:24:40
Ho preso un desktop apposta: no limits. 8) Ed è pure silenziosissimo: se non fosse perché all'avvio le ventole le spara al massimo, non si sentirebbe mai.
Titolo: Re:Muen Separation Kernel
Inserito da: Z80Fan - 14 Dicembre 2014, 16:35:18
Lo swap (su Windows 8.1) l'ho disattivato. Con 16GB è del tutto inutile. 8)
Lo volevo fare anche sul mio (sia su Windows che su Linux): 6 GB non sono mai riuscito a riempirli, tranne nel caso in cui avevo per sbaglio creato un ciclo infinito che allocava memoria a ripetizione. ;D

Sai dirmi come posso disattivarlo, in Windows 8.1? E' un'operazione indolore?

beati voi che potete  :D

Ho trovato questo, potresti provarlo:
http://wiki.summercode.com/how_to_disable_or_enable_swapping_in_mac_os_x
(ho visto anche altri link ma dicono tutti la stessa cosa)
Titolo: Re:Muen Separation Kernel
Inserito da: cdimauro - 14 Dicembre 2014, 16:43:30
Esplora risorse. Tasto destro su Computer. Proprietà. Proprietà di sistema avanzate. Prestazioni / Impostazioni. Avanzate. Memoria Virtuale / Cambia.  Togli la prima spunta in alto. Seleziona Nessuna paginazione. Premi Imposta. OK, OK, OK, Riavvia.

Se hai abbastanza memoria, non dovrebbero esserci controindicazioni.
Titolo: Re:Muen Separation Kernel
Inserito da: Z80Fan - 14 Dicembre 2014, 16:54:38
Esplora risorse. Tasto destro su Computer. Proprietà. Proprietà di sistema avanzate. Prestazioni / Impostazioni. Avanzate. Memoria Virtuale / Cambia.  Togli la prima spunta in alto. Seleziona Nessuna paginazione. Premi Imposta. OK, OK, OK, Riavvia.

Se hai abbastanza memoria, non dovrebbero esserci controindicazioni.

Grazie, proverò. :)

(che avevo gia' provato e non funziona, mentre riempire il disco mette la parola FINE al problema)

Brutte storie. :(
Eh però, Mac OS X è il sistema operativo più avanzato al mondo... ::)