La vie est mal configurée

Aller au contenu | Aller au menu | Aller à la recherche

vendredi, mars 6 2015

Les boucles terminent toujours

En cette époque troublée où les certitudes vacillent et les théories du complot se répandent, nous cherchons des points de repère. C'est pourquoi je ne sais s'il faut se réjouir ou s'indigner du paragraphe 6.8.5:6 de la norme C 2011 :

An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.

Je comprends. Mais dois-je approuver ?

(Merci à Xavier Leroy et Pascal Cuoq.)

vendredi, juin 6 2014

Replaying execution traces in a processor simulator

Dear all,

Next week, my student Julien Henry will give a talk at LCTES 2014 on a method for computing precise upper bounds on the execution time of loop-free (e.g. with small loops unrolled) programs. We turn this problem into an optimization problem (in the mathematical sense) and solve it with a satisfiability modulo theory solver. The low-level architectural analysis (e.g. pipelines and caches) is delegated to other tools (we used OTAWA but Absint's aIT tool could possibly be used).

Lire la suite...

jeudi, mai 15 2014

Parallélisé au trois quarts

Il y a 9 ans, je publiais un article sur une version parallélisée de l'analyseur statique Astrée. En résumé, le temps de calcul sur n processeurs (normalisé) est en 0,75/n+0,25.

Je viens de programmer, à titre d'exercice, une bibliothèque de BDD. Pareil, temps de calcul en 0,78/n+0,22.

Y a-t-il quelque chose de particulier à la proportion « 75% parallélisable, 25% non parallélisable » ? ;-)

jeudi, avril 24 2014

Buffer overflows and waterboarding, waterboarding and buffer overflows...

Lors de son exposé à l'Institut Henri Poincaré, Xavier Leroy a rappelé la distinction que l'on fait en matière de sûreté de fonctionnement de logiciels entre

  1. ceux dont les pannes sont certes énervantes et sources de pertes de productivité, mais sans plus (p.ex. traitement de texte qui « plante »)
  2. ceux dont les pannes peuvent causer des pertes financières importantes ou des problèmes majeurs de relations publiques (p.ex. trous de sécurité comme Heartbleed)
  3. ceux dont les pannes peuvent causer des pertes de vies humaines, en plus des problèmes précédents (p.ex. pilotages de trains ou d'avions).

Il me semble que cette distinction est quelque peu optimiste. De nos jours, les communications des opposants politiques passent notamment par des moyens de communication électroniques. Nous savons depuis un moment déjà que divers services occidentaux, notamment américains, espionnent les communications, y compris de leurs citoyens, avec le concours des grands industriels des réseaux et des services en ligne. Nous savons que des entreprises occidentales ont vendu à des régimes dictatoriaux et brutaux des systèmes d'interception de communication, sous des prétextes fallacieux. Nous savons que certaines entreprises font commerce des « trous de sécurité » qu'elles découvrent, auprès des gouvernements. Nous pouvons raisonnablement conjecturer que les grands industriels de l'informatique incorporent des trous de sécurité et autres « portes de derrière » dans les produits qu'ils commercialisent, à la demande des services spéciaux. Nous savons que les pays occidentaux collaborent parfois avec des états brutaux et dictatoriaux, suivant les alliances et les priorités du moment.

Nous pouvons donc conclure que certains des dysfonctionnements de niveau 2 peuvent fort bien conduire des opposants politiques à la torture et à la mort. Autrement dit, une inattention, une négligence, dans une bibliothèque comme OpenSSL peut avoir des conséquences bien plus grave que la dissémination de numéros de carte bancaire ou de mots de passe de comptes Twitter.

Malheureusement, en faisant ce constat, je n'apporte pas de solution.

mardi, juin 25 2013

Qu'ai-je donc fait à ce compilateur

Soit le programme suivant :

int valeur;
volatile int bidule;
void toto() {
if (bidule) {
valeur = 65;
} else {
valeur = 33;
}
if (bidule) {
valeur++;
} else {
valeur--;
}
}

Pourquoi LLVM le compile-t-il ainsi :

define void @toto() #0 {
entry:
%0 = load volatile i32* @bidule, align 4, !tbaa !0
%tobool = icmp eq i32 %0, 0
%. = select i1 %tobool, i32 33, i32 65
store i32 %., i32* @valeur, align 4
%1 = load volatile i32* @bidule, align 4, !tbaa !0
%tobool1 = icmp eq i32 %1, 0
%storemerge5.v = select i1 %tobool1, i32 -1, i32 1
%storemerge5 = add i32 %storemerge5.v, %.
store i32 %storemerge5, i32* @valeur, align 4
ret void
}

Pourquoi met-il deux instructions STORE vers la même variable @valeur ?

Pourquoi ?

Pourquoi ??

N'ai-je donc tant vécu que pour cette infamie  ?

vendredi, mai 3 2013

Debian et ses patches amusants

Je viens de me rendre compte que Debian (et donc Ubuntu) modifie le comportement du compilateur OCaml... en cassant au passage la possibilité d'utiliser ocamldebug ou les traces de piles sur lancers d'exception sur le code lié avec des bibliothèques en code machine (option -custom).

Pour obtenir le comportement normal, il faut passer OCAML_COMPAT=c dans l'environnement du compilateur.

Je ne trouve rien qui documente cela dans /usr/share/doc/ocaml*, ni même la moindre explication de ce qui change et d'une raison de le faire.

L'informatique pratique est suffisamment difficile sans que l'on rajoute des chausse-trappes.

mercredi, avril 3 2013

Turtles all the way down ? Not yet, but...

J'ai connu l'époque où programmer un micro-ordinateur était simple. Vous vouliez allumer un pixel ? Vous écriviez la valeur qui allait bien dans la case mémoire correspondant au pixel. Vous vouliez écrire sur un port d'entrée-sortie ? Une documentation vous expliquait quelle valeur mettre dans quel port. On écrivait en assembleur et on ne s'embarrassait pas de compilateurs, éditeurs de liens et autres bibliothèques dynamiques. Un gros bouquin suffisait à documenter entièrement la machine et le système d'exploitation.

Lire la suite...

mercredi, janvier 4 2012

Fermez la porte, ils rentreront par la fenêtre

Lorsque j'étais passé il y a un an voir mes collègues de Microsoft Research dans leur joli bâtiment à Redmond, l'un d'eux, Patrice Godefroid je crois, un peu désabusé, m'avait dit que maintenant que Microsoft avait fait un réel effort sur les trous de sécurité dans Windows, Office, Internet Explorer etc., les pirates, tout simplement, visaient Adobe Acrobat ou Adobe Flash, qui sont eux aussi installés sur la plupart des machines.

C'est vrai que parmi les courriers que nous répercute notre administrateur système, il y a beaucoup d'avertissements de vulnérabilités dans ces outils.... mais aussi, dans Firefox. Sans doute la rançon du succès.

Il est vrai que la complexité des navigateurs Web modernes, incluant par exemple des compilateurs dynamiques de Javascript, rend les trous de sécurité très probables. Quand on sait quelles techniques d'optimisation sont à l'œuvre, par exemple pour les accès aux champs des objets Javascript, on s'étonne que cela fonctionne...

(Tout ceci veut sans doute dire qu'au fond, Javascript est mal conçu, ou du moins n'est pas conçu pour le déploiement d'applications de grande taille telles que celles actuellement proposées par Flickr, Google Documents, etc.)

mercredi, décembre 21 2011

Compilation noyau Linux 3.2.0rc5 + patch rt8

Cela partait d'un bon sentiment : je voulais installer un noyau Linux temps-réel sur un ordinateur pour

  1. raisons professionnelles : m'informer sur l'état de fonctionnement de ces fameuses extensions temps-réel, regarder quelles latences on obtient, expérimenter en chargeant la barque, etc.
  2. raisons personnelles : avoir un audio à faible latence pour utiliser Jack.

La machine est une Ubuntu 10.04LTS amd64.

Comme souvent avec ce qui part d'un bon sentiment, les choses ont été pénibles et ont pris des tournants imprévus, et comme souvent avec l'informatique « pratique » dès qu'on touche à un bout, on a des dépendances inattendues.

  1. make-kpkg m'a fait des misères parce que le noyau s'appellait 3.2.0-rc5-rt8 et qu'il n'aimait pas le rt8 (erreurs bizarroïdes)
  2. Je vous passe les problèmes de place disque.
  3. Ensuite, le pilote nvidia ne s'installait plus via dkms, ce qui empêchait la création du initrd à l'installation des paquets noyau.
  4. Il s'avère que le pilote nvidia livré avec ma distribution a des tests codés en dur dans des scripts et ailleurs qui supposent que le noyau est en version 2.x, et le simple fait de passer à 3.x puis 3.2 fait planter ces tests vu qu'ils ne vérifient parfois que la première décimale (je sais, c'est ballot).
  5. J'ai donc pris le dernier pilote nvidia mais il ne compile pas parce que si l'on utilise le noyau intégralement préemptif, les symboles migrate_enable et migrate_disable sont GPL-only.
  6. Il semble que l'impossibilité de compiler les pilotes nvidia gêne la création normale du initrd.
  7. Je ne peux pas utiliser le pilote nv libre, parce qu'il envoie n'importe quoi sur l'écran externe de ce portable.

Bon, avec linux-3.2.0-rc5-rt8 CONFIG_PREEMPT_RT_FULL + NVidia 285 ça ne fonctionne pas, écran noir bloqué au lancement de Xorg. Je garde CONFIG_PREEMPT, CONFIG_PREEMPTLL (low latency desktop) et je vire CONFIG_PREEMPT_FULL. Bien entendu, nulle documentation n'explique la différence entre CONFIG_PREEMPTLL et CONFIG_PREEMPT_RTB.

PS linux-3.2.0-rc5-rt8 CONFIG_PREEMPT__LL + NVidia 285, utiliser rtirq, couper l'USB2 → 4 ms de latence au lieu de 64 auparavant.

lundi, août 1 2011

Annotation automatique

J'aurais une petite question pour ceux de mes lecteurs qui programment.

Lire la suite...

jeudi, juillet 28 2011

Quines

Le théorème de la récursion de Kleene (voir p.ex. Machtey & Young, An introduction to the general theory of algorithms, th 3.4.1) garantit l'existence, dans tout système acceptable de programmation, de programmes dont l'exécution imprime leur propre code source (et ce bien sûr sans aller chercher leur code source dans un quelconque système de fichiers).

Douglas Hofstadter a nommé ce genre de programmes des « quines », par allusion à un philosophe logicien bien connu (enfin, sauf en France). L'article Wikipédia sur le sujet liste des « quines » astucieusements construits à la main. Pour ma part, j'ai voulu en construire un effectivement par application de la construction du point fixe.

J'ai besoin pour cela d'une machine universelle, Invoke.eval(x, y) qui lance le programme x sur l'entrée y : pour cela, je lance le compilateur Java et je charge la classe résultante, et d'une fonction auxiliaire JavaUtil.writeEscaped qui « échappe » les chaînes de caractères (plus précisément, qui transforme une chaîne de caractères en un lexème littéral qui représente cette chaîne). Sinon, c'est du Java 6 standard. Par commodité, un programme est supposé avoir une fonction public static String run(String x).

Voici le « quine » obtenu. Tous les fichiers ayant servi à sa préparation sont disponibles.

class Recursor {
  public static String run(String y) {
    final String x = "class Composed {\n  static class First {\n      public static String run(String x) {\n  	try {\n  	    java.io.StringWriter out = new java.io.StringWriter();\n  	    out.write(\"class Printer {\\n\");\n  	    out.write(\"  public static String run(String dummy) {\\n\");\n  	    out.write(\"    return \\\"\");\n  	    JavaUtil.writeEscaped(out, x);\n  	    out.write(\"\\\";\\n\");\n  	    out.write(\"  }\\n\");\n  	    out.write(\"}\\n\");\n  	    return out.toString();\n  	} catch (java.io.IOException exn) {\n  	    throw new RuntimeException(\"printer\", exn);\n  	}\n      }    \n  }\n  static class Second {\n      static String run(String x) {\n  	try {\n  	    java.io.StringWriter out = new java.io.StringWriter();\n  	    out.write(\"class Recursor {\\n\");\n  	    out.write(\"  public static String run(String y) {\\n\");\n  	    out.write(\"    final String x = \\\"\");\n  	    JavaUtil.writeEscaped(out, x);\n  	    out.write(\"\\\";\\n\");\n  	    out.write(\"    return Invoke.eval(Invoke.eval(x, new String[] { x }), new String[] { y });\\n\");\n  	    out.write(\"  }\\n\");\n  	    out.write(\"}\\n\");\n  	    return out.toString();\n  	} catch (java.io.IOException exn) {\n  	    throw new RuntimeException(\"fixpoint\", exn);\n  	}\n      }\n  }\n  public static String run(final String x) {\n    return First.run(Second.run(x));\n  }\n}\n";
    return Invoke.eval(Invoke.eval(x, new String[] { x }), new String[] { y });
  }
}

vendredi, avril 22 2011

Produits de matrices sur un semi-anneau

Que savons-nous sur les produits de matrices denses en moins de O(n³) quand les coefficients sont dans un semi-anneau ? (Je veux dire que l'addition est non inversible.) Je suis notamment intéressé par le cas des anneaux tropicaux.

Évidemment, je sais que pour les anneaux, il y a Strassen et plus rapide encore.

mercredi, mars 2 2011

COBOL forever

Je suis abonné à une mailing-liste IEEE-754 et en ce moment ça discute de la compatibilité de la norme avec COBOL.

Je sens que quand je serai à la retraite (à 75 ans si on suit les tendances), on aura des machines massivement parallèles avec des tétrachiées de mémoire, et on fera encore tourner du COBOL dessus.

(Vous saviez que les juifs orthodoxes ne se servent pas d'interrupteurs électriques le samedi, mais qu'ils peuvent se servir d'un cadenas à code mécanique ? Oui, il y a un rapport avec ce que je dis ci-dessus.)

mardi, janvier 25 2011

Build systems

(J'ai cherché comment on disait build system en français, et aucune expression ne m'est venue à l'esprit. Je préfère utiliser un terme que tout le monde comprend qu'une traduction personnelle hasardeuse.)

Quand j'étais petit, les gens, sur PC (DOS puis Windows) utilisaient des environnements de développement intégrés (Turbo Pascal, Turbo C++). Enfin, je dis ça, mais quand j'étais vraiment petit, les gens tapaient du BASIC sur des Thomson MO5, des Apple II ou des Amstrad CPC464 ; en fait je parle de mon époque lycée.

Les unixiens utilisaient l'outil make, mais l'écriture des fameux "Makefile" était parfois fastidieuse, aussi utilisait-on des outils censés faciliter la gestion des Makefile. Il y avait donc les imakefiles, xmkmf et autres joyeusetés. Je dis « censés » car en pratique...

Puis GNU est arrivé avec ses autotools (autoconf, automake, etc.) et ses scripts configure. Honnêtement, cela fait une dizaine d'année que j'utilise ces trucs et je n'ai jamais vraiment bien compris comment cela fonctionne. En tout cas, ils font hurler de nombreuses personnes. L'avantage des autotools, c'est que quand ça fonctionne, c'est plus simple que de tripatouiller le Makefile à la main. Le désavantage est que quand ça ne fonctionne pas, c'est incompréhensible.

Sur Java, on utilise plutôt ant, qui se paramètre avec des fichiers XML. Quel bonheur ; au fait, qu'y a-t-il comme éditeur XML agréable ? Parce que le XML à la main dans un éditeur texte, c'est pénible...

Je m'aperçois que des programmes récents n'utilisent plus make, mais un outil Python appelé scons. D'autres préfèrent un outil appelé waf.

Je serais preneur d'un bon comparatif.

mercredi, décembre 1 2010

Pampers

J'ai un programme Sage qui occupe 2 GiB de mémoire, puis termine (2 GiB est le maximum adressable dans un processus sur la machine utilisée). Je soupçonne une fuite de mémoire. Je fais comment ?

(J'ai déjà eu au moins une segfault, donc il y a un problème dans Sage...)