Visita

Oggi al mio laboratorio c'era Thomas Gleixner a fare un talk su "Multicore scalability in Linux, more questions than answers". Thomas (nick: tglx) e' sviluppatore di Linux, cofondatore di Linutronix, maintainer della preemption patch nel kernel Linux.

Tanto per darvi un'idea del tipo: ha cominciato il suo talk con la seguente domanda:

How many cores are a problem for scalability of the Linux kernel?

E la risposta e' stata:

42

(Come dite? Questo post e' arabo? no, it's nerdish, actually)

Filosofi e programmazione

Questa è carina.

E sono anche d'accordo con l'autore del post: Ruby va assegnato a Tommaso D'Aquino! (infatti, a me danno noia tutti e due! senza offesa ovviamente).

Quine

No, non parlerò di quel Quine, non direttamente almeno!

Nello slang dei programmatori si dice quine un programma che produce il suo stesso listato (*) come output. E naturalmente sì, si chiama quine in onore di quel Willard van Orman Quine. Quindi, in fondo si ritorna sempre lì!

Ecco ad esempio un semplice quine in C:

char*f="char*f=%c%s%c;main() {printf(f,34,f,34,10);}%c"; main(){printf(f,34,f,34,10);}

Per vedere come funziona, su Linux copiate la linea su un file quine.c, usando un normale editor. Poi, compilate il file con

   gcc quine.c

Quindi, eseguite il file eseguibile ottenuto (a.out) su un terminale con

./a.out

Se siete su Windows, per vedere cosa viene fuori dovete avere un compilatore C/C++. Se non l'avete, scaricatelo da qui, e non fatevi spaventare dalla dicitura "beta". Dopo aver compilato, lanciate il file exe sempre da terminale.

In realtà, il quine di cui sopra è piuttosto banale, anche se non banalissimo da "inventare". Su questo sito troverete una intera collezione di quines nei principali linguaggi di programmazione.

Collegati ai quine ci sono i programmi C offuscati (**).


Il programma in figura (che potete trovare qui), stampa un frattale, ed ha la forma di un frattale!

Esiste ancora "The International Obfuscated C Code Contest (IOCCC)", una vera a propria gara a chi scrive il programma C più incredibile (nel senso che riesce a dare l'output più inaspettato). Dagli archivi del sito, tiro fuori questa fantastica realizzazione:

#define P(X)j=write(1,X,1)
#define C 39
int M[5000]={2},*u=M,N[5000],R=22,a[4],l[]={0,-1,C-1,-1},m[]={1,-C,-1,C},*b=N,
*d=N,c,e,f,g,i,j,k,s;main(){for(M[i=C*R-1]=24;f|d>=b;){c=M[g=i];i=e;for(s=f=0;
s<4;s++)if((k=m[s]+g)>=0&&k=16!=M[k]>=16))a[f++
]=s;if(f){f=M[e=m[s=a[rand()/(1+2147483647/f)]]+g];j=j < f?f:j;f+=c&-16*!j;M[g]=
c|1<< s;m[*d++=e]=f|1<<(s+2)%4;}else e="d">b++?b[-1]:e;}P(" ");for(s=C;--s;P("_")
)P(" ");for(;P("\n"),R--;P("|"))for(e=C;e--;P("_ "+(*u++/8)%2))P("| "+(*u/4)%2
);}

(clicca qui per scaricare il file shapiro.c)

Sembra una accozzaglia casuale di caratteri, non è vero? Invece, non riuscirete mai a indovinare l'output di questo programma, a meno che non proviate a compilarlo ed ad eseguirlo!

L'ultimo programmino che vi propongo oggi:

typedef struct n{int a:3,
b:29;struct n*c;}t;t*
f();r(){}m(u)t*u;{t*w,*z;
z=u->c,q(z),u->b=z->b*10,
w=u->c=f(),w->a=1,w->c=z->
c;}t*k;g(u)t*u;{t*z,*v,*p,
*x;z=u->c,q(z),u->b=z->b,v
=z->c,z->a=2,x=z->c=f(),x
->a=3,x->b=2,p=x->c=f(),p
->c=f(),p->c->a=1,p->c->c=
v;}int i;h(u)t*u;{t*z,*v,*
w;int c,e;z=u->c,v=z->c,q(
v),c=u->b,e=v->b,u->b=z->b
,z->a=3,z->b=c+1,e+9>=c&&(
q(z),e=z->b,u->b+=e/c,w=f(
),w->b=e%c,w->c=z->c,u->c=
w);}int(*y[4])()={r,m,g,h};
char *sbrk();main(){t*e,*p,*o;
o=f(),o->c=o,o->b=1,e=f(),
e->a=2,p=e->c=f(),p->b=2,
p->c=o,q(e),e=e->c,(void)write
(1,"2.",2);for(;;e=e->c){q(e),
e->b=write(1,&e->b["0123456789"],
1);}}t*f(){return i||(i=1000,
k=(t*)sbrk(i*sizeof(t))),k+--i;
}q(p)t*p;{(*y[p->a])(p);}

(clicca qui per scaricare il file august.c)

Se non lo fermate con control-C, prima o poi questo vi andrà in core dump...
ma vi darà in dono l'espansione decimale del numero di nepero!

Ce ne sono molti altri da riscoprire. Alcuni di essi purtroppo non compilano più: i compilatori moderni non permettono certe "porcate" come quelli di una volta! Io però mi diverto ancora come una volta a rivedere certe "oddities"!

(*) Mamma mia da quanto tempo non usavo la parola listato. Saranno 20 anni, per lo meno. Mi sento proprio un dinosauro!

(**) Quando ero più giovane (sigh), sul mio HD c'era un bella collezione di questi programmini strani. Poi, il tempo passa e io non ho più ritrovato quella preziosa directory. Stasera ero in vena di nostalgie, e il magico google ha fatto il resto.

Indovinello

Stimolato da un'intervista a Paolo Gargini segnalatami da Francesco vorrei cominciare a parlare di qualcosina che ha a che fare con la mia ricerca. E comincio da un indovinello semplice semplice.

Mario è un esperto di barbecue e adora cucinare le bistecche sulla graticola per sua moglie e suo figlio. Il suo fornellino è piccolo, e ci sta su una sola bistecca. Per cuocere un lato di una bistecca ci mette circa 3 minuti. Quindi, per cuocere 3 bistecche ci mette 18 minuti (3 minuti per ogni lato di ogni bistecca). Per ridurre l'attesa decide di comprare un altro fornellino identico, cosicché egli possa cuocere due bistecche in parallelo.

1) Qual'è il tempo minimo necessario per cuocere tutte e 3 le bistecche sui due fornellini?

2) Supponiamo di avere N bistecche e K fornellini, con N > K (ad esempio 5 bistecche su 3 fornelli). Riuscite a ricavare una formula per calcolare il tempo minimo necessario?

Le soluzioni e un po' di discussione nei prossimi post.

Corsi e ricorsi

Febbraio 2000
Sto per terminare il mio dottorato, e giustamente comincio a guardarmi intorno. La ricerca? sì, bella, ma chissà se mi darà da mangiare. Mando un po' di curriculum in giro. Alcuni miei ex-colleghi di università e cari amici lavorano alla Ericsson a Milano, vediamo se riesco a far arrivare un curriculum alla persona giusta (perché anche nel privato funziona così, in Italia).
Mi chiamano, viaggetto a Milano, per l'esattezza a Vimodrone, fermata della metro: "Cascina Burrone". Scendo alla fermata, non c'è niente intorno tranne l'edificio della Ericsson, e i campi intorno. Un po' di nebbiolina, che non guasta mai a Milano.
Colloquio tecnico con il capo reparto.
- Che cosa hai studiato?
- Ho fatto una tesi su sistemi operativi, nella mia ricerca mi sono occupato di sistemi real-time, e sistemi embedded, ho anche programmato un sistema operativo insieme a un mio collega
- No, qui quelle cose non le facciamo, non ci interessano più di tanto.
- Ah...
Mi viene da dirgli che invece dovrebbero interessargli, a quanto ne so. Ma sono ancora un pivellino, e poi è meglio stare coperti.
- E di elettronica che sai?
- Non molto, in realtà sono ingegnere informatico.
- Beh, ma qui non abbiamo molto da programmare, a dire la verità, facciamo altro.
- Ah ... (boh?)

Poi, il colloquio con la psicologa. Solite menate: quali sono i tuoi obiettivi, come ti vedi da qui a 5 anni, come mai non continui a fare ricerca, ecc. Mi rivedo seduto su quella sedia, con lo sguardo triste a guardare fuori dalla finestra la nebbia e i campi, mentre la psicologa mi fa le domande. Tutta la vita qui, così. Sono sicuro?

Non devo aver fatto un gran impressione alla psicologa. Infatti, non mi richiamano. Faccio altri colloqui. Ricevo 2 offerte molto buone, ma alla fine le rifiuto e mi butto: vinco il concorso da ricercatore e comincia l'avventura.

Giugno 2008
Scendo alla fermata di "Cascina Burrone". Ho difficoltà a trovare l'edificio giusto. Adesso è tutto un susseguirsi di capannoni, costruiti piuttosto alla rinfusa senza una chiara viabilità (ma non discendiamo dai Romani? e non erano i Romani quelli che costruivano le strade ordinatamente? e quando ci siamo scordati di come si costruiscono le strade e le città?). I campi ci sono ancora da una parte, ma spariranno presto, vedrete, altri 5 anni massimo ...

Entro, mi presento, mi danno il badge. Sono venuto ad insegnare sistemi operativi, un corso di formazione per dipendenti della Ericsson (anzi, adesso si chiama Marconi). Alla fine programmano, altro che, e usano sistemi operativi real-time, loro malgrado.

Piccola rivincita? Mah, non so. Non mi sento tanto in vena di rivincite. Il posto è ancora più triste di quanto fosse 8 anni fa, se possibile. "Ericsson Lab Italia" è in difficoltà, stanno per chiudere la sede storica di Roma, mentre Milano resiste ancora. Speriamo che si riprendano presto. I dipendenti, però, non sono propriamente su di giri.

Le lezioni, dopo un primo momento stagnante iniziale, vanno piuttosto lisce. I pochi ascoltatori sono decentemente interessati. Mi piace insegnare, veramente. Ne ho anche approfittato per sistemare ulteriormente i miei appunti, prima o poi raggiungerò questa benedetta perfezione. Alla fine c'è una bella interazione con i ragazzi (sebbene "ragazzi" non è appropriato, qualcuno è più vecchio di me in realtà). Sono perfino riuscito a fargli risolvere un esercizio dei miei. Domani finisco e torno via.

E' andata bene così, dopotutto.

Post scriptum: mi scuso con tutti gli abitanti di Vimodrone! Oggi durante la pausa pranzo ho fatto un salto "in centro", ed effettivamente le vie sono dritte e squadrate che neanche gli antichi Romani. Solo, nella zona industriale si sono distratti un'attimo e hanno fatto un bel casino di viabilità!

La sconfitta del drago

Per un programmatore di sistema, una delle attività più rognose e purtroppo anche più frequenti, è la programmazione di un device driver.

Cos'è un device driver?
Avete presente quando comprate un nuovo computer e vi danno un CD o DVD con i "driver"? Quelle cose che rischiano di far piantare tutto? Insomma, quelle cose che stanno facendo fallire il nuovo Windows Vista. No, eh? Va beh, proviamo a spiegarlo per bene in 2 righe (ossimoro).
Un device driver è un modulo di codice software che fa da interfaccia fra il processore principale e un dispositivo esterno. Ad esempio, un modem è un dispositivo esterno che connette il computer alla linea telefonica. Sulla linea telefonica passano segnali analogici; il modem li trasforma in segnali digitali; il software di controllo del modem li carica nella memoria del computer perché possano essere elaborati. Il mouse, il video, la scheda sonora, la scheda wireless, sono tutti esempi di dispositivi esterni che necessitano di un "driver".
Il driver dipende dal modello del dispositivo esterno: modem diversi (cioè di marche diverse, o modelli diversi di una stessa marca) funzionano in modo differente, e quindi necessitano di un programma di controllo differente.

Capito? no? va beh, non importa, potete continuare a leggere comunque.

Si diceva che scrivere sto maledetto codice per i "driver" è rognoso. Qualche volta può essere anche molto semplice, come: 1, 2, 3, fatto. Alle volte è come... catturare un drago armati solo di spada e corda! (*). Quello che ci è capitato questa settimana era come un draghetto, se così si può dire.

Mesi fa abbiamo aquistato una scheda di rete per il nostro sistema "embedded" da utilizzare in un progetto ('sto troiaio qui). Ci arriva la scheda da montare con il solito CD contenente il codice del driver. Indovina? mai funzionato veramente. Prove su prove: riceveva dei dati per un po', poi inspiegabilmente si piantava. Filippo, il ragazzo che ci lavorava era quasi alla disperazione. Alcuni mesi dopo la scadenza del progetto, la scheda ancora non funziona, e abbiamo ormai l'acqua alla gola. Che si fa? La settimana scorsa chiamo Filippo, parliamo un po' e poi la decisione: "Filippo! Si riscrive il codice del driver da capo, dai!". Filippo mi ha guardato come se lo avessi appena condannato a morte, mandandolo a combattere contro il Leviatano in persona.

Filippo è un programmatore inesperto. E' con noi da poco, mai fatto il programmatore di sistema. Esperienze precedenti: programmazione in Visual Basic, Web, robetta così insomma. Scrivere device driver non l'aveva mai fatto. Per questo era terrorizzato: si vedeva altri 3 - 4 mesi legato a quella sedia a sputare bit. Allora ho deciso di affiancarlo, quattro occhi vedono meglio di 2, e poi un pochinino di esperienza in più di Filippo ce l'ho. Lunedì ci siamo imbarcati in questa insana impresa.

Parentesi: scrivere device driver è anche un po' un'arte. Ci vuole esperienza, e pazienza. Il paragone con il drago non è tanto fantasioso. Quando si scrive il codice di un programma normale (ad esempio un'applicazione web), il programmatore ha a disposizione un bel po' di strumenti sofisticati. Se il codice non funziona, pazienza, correggi l'errore e si riparte subito.
Il programmatore di device driver invece è come lavorasse a mani nude (pardon: a cervello nudo): spesso non riesce neanche a vedere le stampe a video perché il PC ti si pianta completamente prima di vedere qualcosa.

C'è poi un altro problema. Di solito, per scrivere un device driver, si comincia prendendo il manuale tecnico del dispositivo per capire come funziona. Sapete che c'è? che il manuale non collima mai con il dispositivo. Mai. Sembra che gli ingegneri elettronici che progettano queste schede lo facciano apposta per odio contro gli ingegneri informatici che devono scrivere il device driver. Se per cominciare a trasferire un dato bisogna scrivere il valore "5" nella locazione di memoria "13678", sul manuale ci sarà scritto che invece bisogna scriverci "10". Naturalmente, provi a scriverci 10, e non funziona. Allora partono e-mail imploranti verso il support tecnico che, trattandoti da pezza di piedi, ti dice che bisogna scrivere "5" e non "10", non hai letto la FAQ sulla pagina del loro sito web, accessibile cliccando sul link seminascosto in basso a destra? quale link? quello in basso a destra... che non funziona! Insomma, mi avete capito.

Partiamo lunedì, dicevo. Giorni per studiarlo prima da lontano, poi per stanarlo, accerchiarlo. Una lotta acerrima a colpi di LOG_error, e interrupt disable, e interrupt mask, e buffer, e poi giovedì sera il colpo finale: "disabilitiamo gli interrupt in questo punto!", e pochi minuti dopo il drago è caduto.

Giovedì sera il nostro codice ha ricevuto ininterrottamente 5 milioni di pacchetti dati senza mai piantarsi. Non è che sia un codice perfetto: il fornitore dichiara una velocità di trasferimento di 25 Mbit (seee buonanotte), noi se va bene sfioriamo gli 8Mbit. Ah, funziona solo in una modalità, nelle altre si pianta sempre. Però funziona!

Catturare draghi sarà pure difficile, ma il sorriso stampato sulla faccia stanca di Filippo giovedì sera mi ha ripagato di tutto! Vai, avanti il prossimo!

(*) scusate l'analogia, sono stato Dungeon Master da giovane